1 /* 2 Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft 3 Permission is hereby granted, free of charge, to any person obtaining a copy 4 of this software and associated documentation files (the "Software"), to deal 5 in the Software without restriction, including without limitation the rights 6 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 7 copies of the Software, and to permit persons to whom the Software is 8 furnished to do so, subject to the following conditions: 9 10 The above copyright notice and this permission notice shall be included in 11 all copies or substantial portions of the Software. 12 13 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 14 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 15 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 16 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 17 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 18 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 19 SOFTWARE. 20 */ 21 22 #define HASHINDEXnot 23 24 using System; 25 using System.Diagnostics; 26 using SCG = System.Collections.Generic; 27 28 namespace C5 29 { 30 /// <summary> 31 /// A list collection class based on a doubly linked list data structure. 32 /// </summary> 33 [Serializable] 34 public class LinkedList<T> : SequencedBase<T>, IList<T>, SCG.IList<T> 35 #if HASHINDEX 36 #else 37 , IStack<T>, IQueue<T> 38 #endif 39 { 40 #region Fields 41 /// <summary> 42 /// IExtensible.Add(T) always does AddLast(T), fIFO determines 43 /// if T Remove() does RemoveFirst() or RemoveLast() 44 /// </summary> 45 bool fIFO = true; 46 47 #region Events 48 49 /// <summary> 50 /// 51 /// </summary> 52 /// <value></value> 53 public override EventTypeEnum ListenableEvents { get { return underlying == null ? EventTypeEnum.All : EventTypeEnum.None; } } 54 55 #endregion 56 57 //Invariant: startsentinel != null && endsentinel != null 58 //If size==0: startsentinel.next == endsentinel && endsentinel.prev == startsentinel 59 //Else: startsentinel.next == First && endsentinel.prev == Last) 60 /// <summary> 61 /// Node to the left of first node 62 /// </summary> 63 Node startsentinel; 64 /// <summary> 65 /// Node to the right of last node 66 /// </summary> 67 Node endsentinel; 68 /// <summary> 69 /// Offset of this view in underlying list 70 /// </summary> 71 #if HASHINDEX 72 int? offset; 73 #else 74 int offset; 75 #endif 76 77 /// <summary> 78 /// underlying list of this view (or null for the underlying list) 79 /// </summary> 80 LinkedList<T> underlying; 81 82 //Note: all views will have the same views list since all view objects are created by MemberwiseClone() 83 WeakViewList<LinkedList<T>> views; 84 WeakViewList<LinkedList<T>>.Node myWeakReference; 85 86 /// <summary> 87 /// Has this list or view not been invalidated by some operation (by someone calling Dispose()) 88 /// </summary> 89 bool isValid = true; 90 91 92 #if HASHINDEX 93 HashDictionary<T, Node> dict; 94 /// <summary> 95 /// Number of taggroups 96 /// </summary> 97 int taggroups; 98 /// <summary> 99 /// 100 /// </summary> 101 /// <value></value> 102 int Taggroups 103 { 104 get { return underlying == null ? taggroups : underlying.taggroups; } 105 set { if (underlying == null) taggroups = value; else underlying.taggroups = value; } 106 } 107 #endif 108 109 #endregion 110 111 #region Util 112 equals(T i1, T i2)113 bool equals(T i1, T i2) { return itemequalityComparer.Equals(i1, i2); } 114 115 #region Check utilities 116 /// <summary> 117 /// Check if it is valid to perform updates and increment stamp of 118 /// underlying if this is a view. 119 /// <para>This method should be called in every public modifying 120 /// methods before any modifications are performed. 121 /// </para> 122 /// </summary> 123 /// <exception cref="InvalidOperationException"> if check fails.</exception> updatecheck()124 protected override void updatecheck() 125 { 126 validitycheck(); 127 base.updatecheck(); 128 if (underlying != null) 129 underlying.stamp++; 130 } 131 132 /// <summary> 133 /// Check if we are a view that the underlyinglist has only been updated through us. 134 /// <br/> 135 /// This method should be called from enumerators etc to guard against 136 /// modification of the base collection. 137 /// </summary> 138 /// <exception cref="InvalidOperationException"> if check fails.</exception> validitycheck()139 void validitycheck() 140 { 141 if (!isValid) 142 throw new ViewDisposedException(); 143 } 144 145 /// <summary> 146 /// Check that the list has not been updated since a particular time. 147 /// </summary> 148 /// <param name="stamp">The stamp indicating the time.</param> 149 /// <exception cref="CollectionModifiedException"> if check fails.</exception> modifycheck(int stamp)150 protected override void modifycheck(int stamp) 151 { 152 validitycheck(); 153 if ((underlying != null ? underlying.stamp : this.stamp) != stamp) 154 throw new CollectionModifiedException(); 155 } 156 #endregion 157 158 #region Searching contains(T item, out Node node)159 bool contains(T item, out Node node) 160 { 161 #if HASHINDEX 162 if (dict.Find(item, out node)) 163 return insideview(node); 164 #else 165 //TODO: search from both ends? Or search from the end selected by FIFO? 166 node = startsentinel.next; 167 while (node != endsentinel) 168 { 169 if (equals(item, node.item)) 170 return true; 171 node = node.next; 172 } 173 #endif 174 return false; 175 } 176 177 /// <summary> 178 /// Search forwards from a node for a node with a particular item. 179 /// </summary> 180 /// <param name="item">The item to look for</param> 181 /// <param name="node">On input, the node to start at. If item was found, the node found on output.</param> 182 /// <param name="index">If node was found, the value will be the number of links followed higher than 183 /// the value on input. If item was not found, the value on output is undefined.</param> 184 /// <returns>True if node was found.</returns> find(T item, ref Node node, ref int index)185 bool find(T item, ref Node node, ref int index) 186 { 187 while (node != endsentinel) 188 { 189 //if (item.Equals(node.item)) 190 if (itemequalityComparer.Equals(item, node.item)) 191 return true; 192 193 index++; 194 node = node.next; 195 } 196 197 return false; 198 } 199 dnif(T item, ref Node node, ref int index)200 bool dnif(T item, ref Node node, ref int index) 201 { 202 while (node != startsentinel) 203 { 204 //if (item.Equals(node.item)) 205 if (itemequalityComparer.Equals(item, node.item)) 206 return true; 207 208 index--; 209 node = node.prev; 210 } 211 212 return false; 213 } 214 215 #if HASHINDEX insideview(Node node)216 bool insideview(Node node) 217 { 218 if (underlying == null) 219 return true; 220 return (startsentinel.precedes(node) && node.precedes(endsentinel)); 221 } 222 #endif 223 224 #endregion 225 226 #region Indexing 227 /// <summary> 228 /// Return the node at position pos 229 /// </summary> 230 /// <param name="pos"></param> 231 /// <returns></returns> get(int pos)232 Node get(int pos) 233 { 234 if (pos < 0 || pos >= size) 235 throw new IndexOutOfRangeException(); 236 else if (pos < size / 2) 237 { // Closer to front 238 Node node = startsentinel; 239 240 for (int i = 0; i <= pos; i++) 241 node = node.next; 242 243 return node; 244 } 245 else 246 { // Closer to end 247 Node node = endsentinel; 248 249 for (int i = size; i > pos; i--) 250 node = node.prev; 251 252 return node; 253 } 254 } 255 256 /// <summary> 257 /// Find the distance from pos to the set given by positions. Return the 258 /// signed distance as return value and as an out parameter, the 259 /// array index of the nearest position. This is used for up to length 5 of 260 /// positions, and we do not assume it is sorted. 261 /// </summary> 262 /// <param name="pos"></param> 263 /// <param name="positions"></param> 264 /// <param name="nearest"></param> 265 /// <returns></returns> dist(int pos, out int nearest, int[] positions)266 int dist(int pos, out int nearest, int[] positions) 267 { 268 nearest = -1; 269 int bestdist = int.MaxValue; 270 int signeddist = bestdist; 271 for (int i = 0; i < positions.Length; i++) 272 { 273 int thisdist = positions[i] - pos; 274 if (thisdist >= 0 && thisdist < bestdist) { nearest = i; bestdist = thisdist; signeddist = thisdist; } 275 if (thisdist < 0 && -thisdist < bestdist) { nearest = i; bestdist = -thisdist; signeddist = thisdist; } 276 } 277 return signeddist; 278 } 279 280 /// <summary> 281 /// Find the node at position pos, given known positions of several nodes. 282 /// </summary> 283 /// <param name="pos"></param> 284 /// <param name="positions"></param> 285 /// <param name="nodes"></param> 286 /// <returns></returns> get(int pos, int[] positions, Node[] nodes)287 Node get(int pos, int[] positions, Node[] nodes) 288 { 289 int nearest; 290 int delta = dist(pos, out nearest, positions); 291 Node node = nodes[nearest]; 292 if (delta > 0) 293 for (int i = 0; i < delta; i++) 294 node = node.prev; 295 else 296 for (int i = 0; i > delta; i--) 297 node = node.next; 298 return node; 299 } 300 301 /// <summary> 302 /// Get nodes at positions p1 and p2, given nodes at several positions. 303 /// </summary> 304 /// <param name="p1"></param> 305 /// <param name="p2"></param> 306 /// <param name="n1"></param> 307 /// <param name="n2"></param> 308 /// <param name="positions"></param> 309 /// <param name="nodes"></param> getPair(int p1, int p2, out Node n1, out Node n2, int[] positions, Node[] nodes)310 void getPair(int p1, int p2, out Node n1, out Node n2, int[] positions, Node[] nodes) 311 { 312 int nearest1, nearest2; 313 int delta1 = dist(p1, out nearest1, positions), d1 = delta1 < 0 ? -delta1 : delta1; 314 int delta2 = dist(p2, out nearest2, positions), d2 = delta2 < 0 ? -delta2 : delta2; 315 316 if (d1 < d2) 317 { 318 n1 = get(p1, positions, nodes); 319 n2 = get(p2, new int[] { positions[nearest2], p1 }, new Node[] { nodes[nearest2], n1 }); 320 } 321 else 322 { 323 n2 = get(p2, positions, nodes); 324 n1 = get(p1, new int[] { positions[nearest1], p2 }, new Node[] { nodes[nearest1], n2 }); 325 } 326 } 327 #endregion 328 329 #region Insertion 330 #if HASHINDEX insert(int index, Node succ, T item)331 void insert(int index, Node succ, T item) 332 { 333 Node newnode = new Node(item); 334 if (dict.FindOrAdd(item, ref newnode)) 335 throw new DuplicateNotAllowedException("Item already in indexed list"); 336 insertNode(true, succ, newnode); 337 } 338 339 /// <summary> 340 /// Insert a Node before another one. Unchecked version. 341 /// </summary> 342 /// <param name="succ">The successor to be</param> 343 /// <param name="newnode">Node to insert</param> 344 /// <param name="updateViews">update overlapping view in this call</param> insertNode(bool updateViews, Node succ, Node newnode)345 void insertNode(bool updateViews, Node succ, Node newnode) 346 { 347 newnode.next = succ; 348 Node pred = newnode.prev = succ.prev; 349 succ.prev.next = newnode; 350 succ.prev = newnode; 351 size++; 352 if (underlying != null) 353 underlying.size++; 354 settag(newnode); 355 if (updateViews) 356 fixViewsAfterInsert(succ, pred, 1, 0); 357 } 358 #else 359 /// <summary> 360 /// 361 /// </summary> 362 /// <param name="index">The index in this view</param> 363 /// <param name="succ"></param> 364 /// <param name="item"></param> 365 /// <returns></returns> insert(int index, Node succ, T item)366 Node insert(int index, Node succ, T item) 367 { 368 Node newnode = new Node(item, succ.prev, succ); 369 succ.prev.next = newnode; 370 succ.prev = newnode; 371 size++; 372 if (underlying != null) 373 underlying.size++; 374 fixViewsAfterInsert(succ, newnode.prev, 1, Offset + index); 375 return newnode; 376 } 377 #endif 378 #endregion 379 380 #region Removal remove(Node node, int index)381 T remove(Node node, int index) 382 { 383 fixViewsBeforeSingleRemove(node, Offset + index); 384 node.prev.next = node.next; 385 node.next.prev = node.prev; 386 size--; 387 if (underlying != null) 388 underlying.size--; 389 #if HASHINDEX 390 removefromtaggroup(node); 391 #endif 392 return node.item; 393 } 394 395 #if HASHINDEX dictremove(T item, out Node node)396 private bool dictremove(T item, out Node node) 397 { 398 if (underlying == null) 399 { 400 if (!dict.Remove(item, out node)) 401 return false; 402 } 403 else 404 { 405 //We cannot avoid calling dict twice - have to intersperse the listorder test! 406 if (!contains(item, out node)) 407 return false; 408 dict.Remove(item); 409 } 410 return true; 411 } 412 #endif 413 #endregion 414 415 #region fixView utilities 416 /// <summary> 417 /// 418 /// </summary> 419 /// <param name="added">The actual number of inserted nodes</param> 420 /// <param name="pred">The predecessor of the inserted nodes</param> 421 /// <param name="succ">The successor of the added nodes</param> 422 /// <param name="realInsertionIndex"></param> fixViewsAfterInsert(Node succ, Node pred, int added, int realInsertionIndex)423 void fixViewsAfterInsert(Node succ, Node pred, int added, int realInsertionIndex) 424 { 425 if (views != null) 426 foreach (LinkedList<T> view in views) 427 { 428 if (view != this) 429 { 430 #if HASHINDEX 431 if (pred.precedes(view.startsentinel) || (view.startsentinel == pred && view.size > 0)) 432 view.offset += added; 433 if (view.startsentinel.precedes(pred) && succ.precedes(view.endsentinel)) 434 view.size += added; 435 if (view.startsentinel == pred && view.size > 0) 436 view.startsentinel = succ.prev; 437 if (view.endsentinel == succ) 438 view.endsentinel = pred.next; 439 #else 440 if (view.Offset == realInsertionIndex && view.size > 0) 441 view.startsentinel = succ.prev; 442 if (view.Offset + view.size == realInsertionIndex) 443 view.endsentinel = pred.next; 444 if (view.Offset < realInsertionIndex && view.Offset + view.size > realInsertionIndex) 445 view.size += added; 446 if (view.Offset > realInsertionIndex || (view.Offset == realInsertionIndex && view.size > 0)) 447 view.offset += added; 448 #endif 449 } 450 } 451 } 452 fixViewsBeforeSingleRemove(Node node, int realRemovalIndex)453 void fixViewsBeforeSingleRemove(Node node, int realRemovalIndex) 454 { 455 if (views != null) 456 foreach (LinkedList<T> view in views) 457 { 458 if (view != this) 459 { 460 #if HASHINDEX 461 if (view.startsentinel.precedes(node) && node.precedes(view.endsentinel)) 462 view.size--; 463 if (!view.startsentinel.precedes(node)) 464 view.offset--; 465 if (view.startsentinel == node) 466 view.startsentinel = node.prev; 467 if (view.endsentinel == node) 468 view.endsentinel = node.next; 469 #else 470 if (view.offset - 1 == realRemovalIndex) 471 view.startsentinel = node.prev; 472 if (view.offset + view.size == realRemovalIndex) 473 view.endsentinel = node.next; 474 if (view.offset <= realRemovalIndex && view.offset + view.size > realRemovalIndex) 475 view.size--; 476 if (view.offset > realRemovalIndex) 477 view.offset--; 478 #endif 479 } 480 } 481 } 482 483 #if HASHINDEX 484 #else fixViewsBeforeRemove(int start, int count, Node first, Node last)485 void fixViewsBeforeRemove(int start, int count, Node first, Node last) 486 { 487 int clearend = start + count - 1; 488 if (views != null) 489 foreach (LinkedList<T> view in views) 490 { 491 if (view == this) 492 continue; 493 int viewoffset = view.Offset, viewend = viewoffset + view.size - 1; 494 //sentinels 495 if (start < viewoffset && viewoffset - 1 <= clearend) 496 view.startsentinel = first.prev; 497 if (start <= viewend + 1 && viewend < clearend) 498 view.endsentinel = last.next; 499 //offsets and sizes 500 if (start < viewoffset) 501 { 502 if (clearend < viewoffset) 503 view.offset = viewoffset - count; 504 else 505 { 506 view.offset = start; 507 view.size = clearend < viewend ? viewend - clearend : 0; 508 } 509 } 510 else if (start <= viewend) 511 view.size = clearend <= viewend ? view.size - count : start - viewoffset; 512 } 513 } 514 #endif 515 516 /// <summary> 517 /// 518 /// </summary> 519 /// <param name="otherView"></param> 520 /// <returns>The position of View(otherOffset, otherSize) wrt. this view</returns> viewPosition(LinkedList<T> otherView)521 MutualViewPosition viewPosition(LinkedList<T> otherView) 522 { 523 #if HASHINDEX 524 Node otherstartsentinel = otherView.startsentinel, otherendsentinel = otherView.endsentinel, 525 first = startsentinel.next, last = endsentinel.prev, 526 otherfirst = otherstartsentinel.next, otherlast = otherendsentinel.prev; 527 if (last.precedes(otherfirst) || otherlast.precedes(first)) 528 return MutualViewPosition.NonOverlapping; 529 if (size == 0 || (otherstartsentinel.precedes(first) && last.precedes(otherendsentinel))) 530 return MutualViewPosition.Contains; 531 if (otherView.size == 0 || (startsentinel.precedes(otherfirst) && otherlast.precedes(endsentinel))) 532 return MutualViewPosition.ContainedIn; 533 return MutualViewPosition.Overlapping; 534 #else 535 int end = offset + size, otherOffset = otherView.offset, otherSize = otherView.size, otherEnd = otherOffset + otherSize; 536 if (otherOffset >= end || otherEnd <= offset) 537 return MutualViewPosition.NonOverlapping; 538 if (size == 0 || (otherOffset <= offset && end <= otherEnd)) 539 return MutualViewPosition.Contains; 540 if (otherSize == 0 || (offset <= otherOffset && otherEnd <= end)) 541 return MutualViewPosition.ContainedIn; 542 return MutualViewPosition.Overlapping; 543 #endif 544 } 545 disposeOverlappingViews(bool reverse)546 void disposeOverlappingViews(bool reverse) 547 { 548 if (views != null) 549 { 550 foreach (LinkedList<T> view in views) 551 { 552 if (view != this) 553 { 554 switch (viewPosition(view)) 555 { 556 case MutualViewPosition.ContainedIn: 557 if (reverse) 558 { } 559 else 560 view.Dispose(); 561 break; 562 case MutualViewPosition.Overlapping: 563 view.Dispose(); 564 break; 565 case MutualViewPosition.Contains: 566 case MutualViewPosition.NonOverlapping: 567 break; 568 } 569 } 570 } 571 } 572 } 573 574 #endregion 575 576 #endregion 577 578 #region Constructors 579 580 /// <summary> 581 /// Create a linked list with en external item equalityComparer 582 /// </summary> 583 /// <param name="itemequalityComparer">The external equalityComparer</param> LinkedList(SCG.IEqualityComparer<T> itemequalityComparer)584 public LinkedList(SCG.IEqualityComparer<T> itemequalityComparer) 585 : base(itemequalityComparer) 586 { 587 offset = 0; 588 size = stamp = 0; 589 startsentinel = new Node(default(T)); 590 endsentinel = new Node(default(T)); 591 startsentinel.next = endsentinel; 592 endsentinel.prev = startsentinel; 593 #if HASHINDEX 594 //It is important that the sentinels are different: 595 startsentinel.taggroup = new TagGroup(); 596 startsentinel.taggroup.tag = int.MinValue; 597 startsentinel.taggroup.count = 0; 598 endsentinel.taggroup = new TagGroup(); 599 endsentinel.taggroup.tag = int.MaxValue; 600 endsentinel.taggroup.count = 0; 601 dict = new HashDictionary<T, Node>(itemequalityComparer); 602 #endif 603 } 604 605 /// <summary> 606 /// Create a linked list with the natural item equalityComparer 607 /// </summary> LinkedList()608 public LinkedList() : this(EqualityComparer<T>.Default) { } 609 610 #endregion 611 612 #region Node nested class 613 614 /// <summary> 615 /// An individual cell in the linked list 616 /// </summary> 617 [Serializable] 618 class Node 619 { 620 public Node prev; 621 622 public Node next; 623 624 public T item; 625 626 #region Tag support 627 #if HASHINDEX 628 internal int tag; 629 630 internal TagGroup taggroup; 631 precedes(Node that)632 internal bool precedes(Node that) 633 { 634 //Debug.Assert(taggroup != null, "taggroup field null"); 635 //Debug.Assert(that.taggroup != null, "that.taggroup field null"); 636 int t1 = taggroup.tag; 637 int t2 = that.taggroup.tag; 638 639 return t1 < t2 ? true : t1 > t2 ? false : tag < that.tag; 640 } 641 #endif 642 #endregion 643 644 [Tested] Node(T item)645 internal Node(T item) { this.item = item; } 646 647 [Tested] Node(T item, Node prev, Node next)648 internal Node(T item, Node prev, Node next) 649 { 650 this.item = item; this.prev = prev; this.next = next; 651 } 652 ToString()653 public override string ToString() 654 { 655 #if HASHINDEX 656 return String.Format("Node: (item={0}, tag={1})", item, tag); 657 #else 658 return String.Format("Node(item={0})", item); 659 #endif 660 } 661 } 662 663 #endregion 664 665 #region Taggroup nested class and tag maintenance utilities 666 #if HASHINDEX 667 /// <summary> 668 /// A group of nodes with the same high tag. Purpose is to be 669 /// able to tell the sequence order of two nodes without having to scan through 670 /// the list. 671 /// </summary> 672 [Serializable] 673 class TagGroup 674 { 675 internal int tag, count; 676 677 internal Node first, last; 678 679 /// <summary> 680 /// Pretty print a tag group 681 /// </summary> 682 /// <returns>Formatted tag group</returns> ToString()683 public override string ToString() 684 { return String.Format("TagGroup(tag={0}, cnt={1}, fst={2}, lst={3})", tag, count, first, last); } 685 } 686 687 //Constants for tag maintenance 688 const int wordsize = 32; 689 690 const int lobits = 3; 691 692 const int hibits = lobits + 1; 693 694 const int losize = 1 << lobits; 695 696 const int hisize = 1 << hibits; 697 698 const int logwordsize = 5; 699 gettaggroup(Node pred, Node succ, out int lowbound, out int highbound)700 TagGroup gettaggroup(Node pred, Node succ, out int lowbound, out int highbound) 701 { 702 TagGroup predgroup = pred.taggroup, succgroup = succ.taggroup; 703 704 if (predgroup == succgroup) 705 { 706 lowbound = pred.tag + 1; 707 highbound = succ.tag - 1; 708 return predgroup; 709 } 710 else if (predgroup.first != null) 711 { 712 lowbound = pred.tag + 1; 713 highbound = int.MaxValue; 714 return predgroup; 715 } 716 else if (succgroup.first != null) 717 { 718 lowbound = int.MinValue; 719 highbound = succ.tag - 1; 720 return succgroup; 721 } 722 else 723 { 724 lowbound = int.MinValue; 725 highbound = int.MaxValue; 726 return new TagGroup(); 727 } 728 } 729 730 731 /// <summary> 732 /// Put a tag on a node (already inserted in the list). Split taggroups and renumber as 733 /// necessary. 734 /// </summary> 735 /// <param name="node">The node to tag</param> settag(Node node)736 void settag(Node node) 737 { 738 Node pred = node.prev, succ = node.next; 739 TagGroup predgroup = pred.taggroup, succgroup = succ.taggroup; 740 741 if (predgroup == succgroup) 742 { 743 node.taggroup = predgroup; 744 predgroup.count++; 745 if (pred.tag + 1 == succ.tag) 746 splittaggroup(predgroup); 747 else 748 node.tag = (pred.tag + 1) / 2 + (succ.tag - 1) / 2; 749 } 750 else if (predgroup.first != null) 751 { 752 node.taggroup = predgroup; 753 predgroup.last = node; 754 predgroup.count++; 755 if (pred.tag == int.MaxValue) 756 splittaggroup(predgroup); 757 else 758 node.tag = pred.tag / 2 + int.MaxValue / 2 + 1; 759 } 760 else if (succgroup.first != null) 761 { 762 node.taggroup = succgroup; 763 succgroup.first = node; 764 succgroup.count++; 765 if (succ.tag == int.MinValue) 766 splittaggroup(node.taggroup); 767 else 768 node.tag = int.MinValue / 2 + (succ.tag - 1) / 2; 769 } 770 else 771 { 772 Debug.Assert(Taggroups == 0); 773 774 TagGroup newgroup = new TagGroup(); 775 776 Taggroups = 1; 777 node.taggroup = newgroup; 778 newgroup.first = newgroup.last = node; 779 newgroup.count = 1; 780 return; 781 } 782 } 783 784 785 /// <summary> 786 /// Remove a node from its taggroup. 787 /// <br/> When this is called, node must already have been removed from the underlying list 788 /// </summary> 789 /// <param name="node">The node to remove</param> removefromtaggroup(Node node)790 void removefromtaggroup(Node node) 791 { 792 793 TagGroup taggroup = node.taggroup; 794 795 if (--taggroup.count == 0) 796 { 797 Taggroups--; 798 return; 799 } 800 801 if (node == taggroup.first) 802 taggroup.first = node.next; 803 804 if (node == taggroup.last) 805 taggroup.last = node.prev; 806 807 //node.taggroup = null; 808 if (taggroup.count != losize || Taggroups == 1) 809 return; 810 811 TagGroup otg; 812 // bug20070911: 813 Node neighbor; 814 if ((neighbor = taggroup.first.prev) != startsentinel 815 && (otg = neighbor.taggroup).count <= losize) 816 taggroup.first = otg.first; 817 else if ((neighbor = taggroup.last.next) != endsentinel 818 && (otg = neighbor.taggroup).count <= losize) 819 taggroup.last = otg.last; 820 else 821 return; 822 823 Node n = otg.first; 824 825 for (int i = 0, length = otg.count; i < length; i++) 826 { 827 n.taggroup = taggroup; 828 n = n.next; 829 } 830 831 taggroup.count += otg.count; 832 Taggroups--; 833 n = taggroup.first; 834 835 const int ofs = wordsize - hibits; 836 837 for (int i = 0, count = taggroup.count; i < count; i++) 838 { 839 n.tag = (i - losize) << ofs; //(i-8)<<28 840 n = n.next; 841 } 842 } 843 844 845 /// <summary> 846 /// Split a tag group to make rom for more tags. 847 /// </summary> 848 /// <param name="taggroup">The tag group</param> splittaggroup(TagGroup taggroup)849 void splittaggroup(TagGroup taggroup) 850 { 851 Node n = taggroup.first; 852 int ptgt = taggroup.first.prev.taggroup.tag; 853 int ntgt = taggroup.last.next.taggroup.tag; 854 855 Debug.Assert(ptgt + 1 <= ntgt - 1); 856 857 int ofs = wordsize - hibits; 858 int newtgs = (taggroup.count - 1) / hisize; 859 int tgtdelta = (int)((ntgt + 0.0 - ptgt) / (newtgs + 2)), tgtag = ptgt; 860 861 tgtdelta = tgtdelta == 0 ? 1 : tgtdelta; 862 for (int j = 0; j < newtgs; j++) 863 { 864 TagGroup newtaggroup = new TagGroup(); 865 866 newtaggroup.tag = (tgtag = tgtag >= ntgt - tgtdelta ? ntgt : tgtag + tgtdelta); 867 newtaggroup.first = n; 868 newtaggroup.count = hisize; 869 for (int i = 0; i < hisize; i++) 870 { 871 n.taggroup = newtaggroup; 872 n.tag = (i - losize) << ofs; //(i-8)<<28 873 n = n.next; 874 } 875 876 newtaggroup.last = n.prev; 877 } 878 879 int rest = taggroup.count - hisize * newtgs; 880 881 taggroup.first = n; 882 taggroup.count = rest; 883 taggroup.tag = (tgtag = tgtag >= ntgt - tgtdelta ? ntgt : tgtag + tgtdelta); ofs--; 884 for (int i = 0; i < rest; i++) 885 { 886 n.tag = (i - hisize) << ofs; //(i-16)<<27 887 n = n.next; 888 } 889 890 taggroup.last = n.prev; 891 Taggroups += newtgs; 892 if (tgtag == ntgt) 893 redistributetaggroups(taggroup); 894 } 895 896 redistributetaggroups(TagGroup taggroup)897 private void redistributetaggroups(TagGroup taggroup) 898 { 899 TagGroup pred = taggroup, succ = taggroup, tmp; 900 double limit = 1, bigt = Math.Pow(Taggroups, 1.0 / 30);//????? 901 int bits = 1, count = 1, lowmask = 0, himask = 0, target = 0; 902 903 do 904 { 905 bits++; 906 lowmask = (1 << bits) - 1; 907 himask = ~lowmask; 908 target = taggroup.tag & himask; 909 while ((tmp = pred.first.prev.taggroup).first != null && (tmp.tag & himask) == target) 910 { count++; pred = tmp; } 911 912 while ((tmp = succ.last.next.taggroup).last != null && (tmp.tag & himask) == target) 913 { count++; succ = tmp; } 914 915 limit *= bigt; 916 } while (count > limit); 917 918 //redistibute tags 919 int lob = pred.first.prev.taggroup.tag, upb = succ.last.next.taggroup.tag; 920 int delta = upb / (count + 1) - lob / (count + 1); 921 922 Debug.Assert(delta > 0); 923 for (int i = 0; i < count; i++) 924 { 925 pred.tag = lob + (i + 1) * delta; 926 pred = pred.last.next.taggroup; 927 } 928 } 929 #endif 930 931 #endregion 932 933 #region Position, PositionComparer and ViewHandler nested types 934 class PositionComparer : SCG.IComparer<Position> 935 { 936 static PositionComparer _default; PositionComparer()937 PositionComparer() { } 938 public static PositionComparer Default { get { return _default ?? (_default = new PositionComparer()); } } Compare(Position a, Position b)939 public int Compare(Position a, Position b) 940 { 941 #if HASHINDEX 942 return a.Endpoint == b.Endpoint ? 0 : a.Endpoint.precedes(b.Endpoint) ? -1 : 1; 943 #else 944 return a.Index.CompareTo(b.Index); 945 #endif 946 } 947 } 948 /// <summary> 949 /// During RemoveAll, we need to cache the original endpoint indices of views 950 /// </summary> 951 struct Position 952 { 953 public readonly LinkedList<T> View; 954 public bool Left; 955 #if HASHINDEX 956 public readonly Node Endpoint; 957 #else 958 public readonly int Index; 959 #endif PositionC5.LinkedList.Position960 public Position(LinkedList<T> view, bool left) 961 { 962 View = view; 963 Left = left; 964 #if HASHINDEX 965 Endpoint = left ? view.startsentinel.next : view.endsentinel.prev; 966 #else 967 Index = left ? view.Offset : view.Offset + view.size - 1; 968 #endif 969 } 970 #if HASHINDEX PositionC5.LinkedList.Position971 public Position(Node node, int foo) { this.Endpoint = node; View = null; Left = false; } 972 #else PositionC5.LinkedList.Position973 public Position(int index) { this.Index = index; View = null; Left = false; } 974 #endif 975 } 976 977 //TODO: merge the two implementations using Position values as arguments 978 /// <summary> 979 /// Handle the update of (other) views during a multi-remove operation. 980 /// </summary> 981 struct ViewHandler 982 { 983 ArrayList<Position> leftEnds; 984 ArrayList<Position> rightEnds; 985 int leftEndIndex, rightEndIndex, leftEndIndex2, rightEndIndex2; 986 internal readonly int viewCount; ViewHandlerC5.LinkedList.ViewHandler987 internal ViewHandler(LinkedList<T> list) 988 { 989 leftEndIndex = rightEndIndex = leftEndIndex2 = rightEndIndex2 = viewCount = 0; 990 leftEnds = rightEnds = null; 991 if (list.views != null) 992 foreach (LinkedList<T> v in list.views) 993 if (v != list) 994 { 995 if (leftEnds == null) 996 { 997 leftEnds = new ArrayList<Position>(); 998 rightEnds = new ArrayList<Position>(); 999 } 1000 leftEnds.Add(new Position(v, true)); 1001 rightEnds.Add(new Position(v, false)); 1002 } 1003 if (leftEnds == null) 1004 return; 1005 viewCount = leftEnds.Count; 1006 leftEnds.Sort(PositionComparer.Default); 1007 rightEnds.Sort(PositionComparer.Default); 1008 } 1009 #if HASHINDEX skipEndpointsC5.LinkedList.ViewHandler1010 internal void skipEndpoints(int removed, Node n) 1011 { 1012 if (viewCount > 0) 1013 { 1014 Position endpoint; 1015 while (leftEndIndex < viewCount && ((endpoint = leftEnds[leftEndIndex]).Endpoint.prev.precedes(n))) 1016 { 1017 LinkedList<T> view = endpoint.View; 1018 view.offset = view.offset - removed;//TODO: extract offset.Value? 1019 view.size += removed; 1020 leftEndIndex++; 1021 } 1022 while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Endpoint.precedes(n)) 1023 { 1024 LinkedList<T> view = endpoint.View; 1025 view.size -= removed; 1026 rightEndIndex++; 1027 } 1028 } 1029 if (viewCount > 0) 1030 { 1031 Position endpoint; 1032 while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Endpoint.prev.precedes(n)) 1033 leftEndIndex2++; 1034 while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Endpoint.next.precedes(n)) 1035 rightEndIndex2++; 1036 } 1037 } 1038 /// <summary> 1039 /// To be called with n pointing to the right of each node to be removed in a stretch. 1040 /// And at the endsentinel. 1041 /// 1042 /// Update offset of a view whose left endpoint (has not already been handled and) is n or precedes n. 1043 /// I.e. startsentinel precedes n. 1044 /// Also update the size as a prelude to handling the right endpoint. 1045 /// 1046 /// Update size of a view not already handled and whose right endpoint precedes n. 1047 /// </summary> 1048 /// <param name="removed">The number of nodes left of n to be removed</param> 1049 /// <param name="n"></param> updateViewSizesAndCountsC5.LinkedList.ViewHandler1050 internal void updateViewSizesAndCounts(int removed, Node n) 1051 { 1052 if (viewCount > 0) 1053 { 1054 Position endpoint; 1055 while (leftEndIndex < viewCount && ((endpoint = leftEnds[leftEndIndex]).Endpoint.prev.precedes(n))) 1056 { 1057 LinkedList<T> view = endpoint.View; 1058 view.offset = view.offset - removed; //TODO: fix use of offset 1059 view.size += removed; 1060 leftEndIndex++; 1061 } 1062 while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Endpoint.precedes(n)) 1063 { 1064 LinkedList<T> view = endpoint.View; 1065 view.size -= removed; 1066 rightEndIndex++; 1067 } 1068 } 1069 } 1070 /// <summary> 1071 /// To be called with n being the first not-to-be-removed node after a (stretch of) node(s) to be removed. 1072 /// 1073 /// It will update the startsentinel of views (that have not been handled before and) 1074 /// whose startsentinel precedes n, i.e. is to be deleted. 1075 /// 1076 /// It will update the endsentinel of views (...) whose endsentinel precedes n, i.e. is to be deleted. 1077 /// 1078 /// PROBLEM: DOESNT WORK AS ORIGINALLY ADVERTISED. WE MUST DO THIS BEFORE WE ACTUALLY REMOVE THE NODES. WHEN THE 1079 /// NODES HAVE BEEN REMOVED, THE precedes METHOD WILL NOT WORK! 1080 /// </summary> 1081 /// <param name="n"></param> 1082 /// <param name="newstart"></param> 1083 /// <param name="newend"></param> updateSentinelsC5.LinkedList.ViewHandler1084 internal void updateSentinels(Node n, Node newstart, Node newend) 1085 { 1086 if (viewCount > 0) 1087 { 1088 Position endpoint; 1089 while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Endpoint.prev.precedes(n)) 1090 { 1091 LinkedList<T> view = endpoint.View; 1092 view.startsentinel = newstart; 1093 leftEndIndex2++; 1094 } 1095 while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Endpoint.next.precedes(n)) 1096 { 1097 LinkedList<T> view = endpoint.View; 1098 view.endsentinel = newend; 1099 rightEndIndex2++; 1100 } 1101 } 1102 } 1103 #else 1104 /// <summary> 1105 /// This is to be called with realindex pointing to the first node to be removed after a (stretch of) node that was not removed 1106 /// </summary> 1107 /// <param name="removed"></param> 1108 /// <param name="realindex"></param> skipEndpointsC5.LinkedList.ViewHandler1109 internal void skipEndpoints(int removed, int realindex) 1110 { 1111 if (viewCount > 0) 1112 { 1113 Position endpoint; 1114 while (leftEndIndex < viewCount && (endpoint = leftEnds[leftEndIndex]).Index <= realindex) 1115 { 1116 LinkedList<T> view = endpoint.View; 1117 view.offset = view.offset - removed; 1118 view.size += removed; 1119 leftEndIndex++; 1120 } 1121 while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Index < realindex) 1122 { 1123 LinkedList<T> view = endpoint.View; 1124 view.size -= removed; 1125 rightEndIndex++; 1126 } 1127 } 1128 if (viewCount > 0) 1129 { 1130 Position endpoint; 1131 while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Index <= realindex) 1132 leftEndIndex2++; 1133 while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Index < realindex - 1) 1134 rightEndIndex2++; 1135 } 1136 } updateViewSizesAndCountsC5.LinkedList.ViewHandler1137 internal void updateViewSizesAndCounts(int removed, int realindex) 1138 { 1139 if (viewCount > 0) 1140 { 1141 Position endpoint; 1142 while (leftEndIndex < viewCount && (endpoint = leftEnds[leftEndIndex]).Index <= realindex) 1143 { 1144 LinkedList<T> view = endpoint.View; 1145 view.offset = view.Offset - removed; 1146 view.size += removed; 1147 leftEndIndex++; 1148 } 1149 while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Index < realindex) 1150 { 1151 LinkedList<T> view = endpoint.View; 1152 view.size -= removed; 1153 rightEndIndex++; 1154 } 1155 } 1156 } updateSentinelsC5.LinkedList.ViewHandler1157 internal void updateSentinels(int realindex, Node newstart, Node newend) 1158 { 1159 if (viewCount > 0) 1160 { 1161 Position endpoint; 1162 while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Index <= realindex) 1163 { 1164 LinkedList<T> view = endpoint.View; 1165 view.startsentinel = newstart; 1166 leftEndIndex2++; 1167 } 1168 while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Index < realindex - 1) 1169 { 1170 LinkedList<T> view = endpoint.View; 1171 view.endsentinel = newend; 1172 rightEndIndex2++; 1173 } 1174 } 1175 } 1176 #endif 1177 } 1178 #endregion 1179 1180 #region Range nested class 1181 1182 class Range : DirectedCollectionValueBase<T>, IDirectedCollectionValue<T> 1183 { 1184 int start, count, rangestamp; 1185 Node startnode, endnode; 1186 1187 LinkedList<T> list; 1188 1189 bool forwards; 1190 1191 Range(LinkedList<T> list, int start, int count, bool forwards)1192 internal Range(LinkedList<T> list, int start, int count, bool forwards) 1193 { 1194 this.list = list; this.rangestamp = list.underlying != null ? list.underlying.stamp : list.stamp; 1195 this.start = start; this.count = count; this.forwards = forwards; 1196 if (count > 0) 1197 { 1198 startnode = list.get(start); 1199 endnode = list.get(start + count - 1); 1200 } 1201 } 1202 1203 public override bool IsEmpty { get { list.modifycheck(rangestamp); return count == 0; } } 1204 1205 [Tested] 1206 public override int Count { [Tested]get { list.modifycheck(rangestamp); return count; } } 1207 1208 1209 public override Speed CountSpeed { get { list.modifycheck(rangestamp); return Speed.Constant; } } 1210 1211 Choose()1212 public override T Choose() 1213 { 1214 list.modifycheck(rangestamp); 1215 if (count > 0) return startnode.item; 1216 throw new NoSuchItemException(); 1217 } 1218 1219 1220 [Tested] GetEnumerator()1221 public override SCG.IEnumerator<T> GetEnumerator() 1222 { 1223 int togo = count; 1224 1225 list.modifycheck(rangestamp); 1226 if (togo == 0) 1227 yield break; 1228 1229 Node cursor = forwards ? startnode : endnode; 1230 1231 yield return cursor.item; 1232 while (--togo > 0) 1233 { 1234 cursor = forwards ? cursor.next : cursor.prev; 1235 list.modifycheck(rangestamp); 1236 yield return cursor.item; 1237 } 1238 } 1239 1240 1241 [Tested] Backwards()1242 public override IDirectedCollectionValue<T> Backwards() 1243 { 1244 list.modifycheck(rangestamp); 1245 1246 Range b = (Range)MemberwiseClone(); 1247 1248 b.forwards = !forwards; 1249 return b; 1250 } 1251 1252 1253 [Tested] Backwards()1254 IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); } 1255 1256 1257 [Tested] 1258 public override EnumerationDirection Direction 1259 { 1260 [Tested] 1261 get 1262 { return forwards ? EnumerationDirection.Forwards : EnumerationDirection.Backwards; } 1263 } 1264 } 1265 1266 1267 #endregion 1268 1269 #region IDisposable Members 1270 1271 /// <summary> 1272 /// Invalidate this list. If a view, just invalidate the view. 1273 /// If not a view, invalidate the list and all views on it. 1274 /// </summary> Dispose()1275 public virtual void Dispose() 1276 { 1277 Dispose(false); 1278 } 1279 Dispose(bool disposingUnderlying)1280 void Dispose(bool disposingUnderlying) 1281 { 1282 if (isValid) 1283 { 1284 if (underlying != null) 1285 { 1286 isValid = false; 1287 if (!disposingUnderlying && views != null) 1288 views.Remove(myWeakReference); 1289 endsentinel = null; 1290 startsentinel = null; 1291 underlying = null; 1292 views = null; 1293 myWeakReference = null; 1294 } 1295 else 1296 { 1297 //isValid = false; 1298 //endsentinel = null; 1299 //startsentinel = null; 1300 if (views != null) 1301 foreach (LinkedList<T> view in views) 1302 view.Dispose(true); 1303 //views = null; 1304 Clear(); 1305 } 1306 } 1307 } 1308 1309 #endregion IDisposable stuff 1310 1311 #region IList<T> Members 1312 1313 /// <summary> 1314 /// </summary> 1315 /// <exception cref="NoSuchItemException"> if this list is empty.</exception> 1316 /// <value>The first item in this list.</value> 1317 [Tested] 1318 public virtual T First 1319 { 1320 [Tested] 1321 get 1322 { 1323 validitycheck(); 1324 if (size == 0) 1325 throw new NoSuchItemException(); 1326 return startsentinel.next.item; 1327 } 1328 } 1329 1330 1331 /// <summary> 1332 /// </summary> 1333 /// <exception cref="NoSuchItemException"> if this list is empty.</exception> 1334 /// <value>The last item in this list.</value> 1335 [Tested] 1336 public virtual T Last 1337 { 1338 [Tested] 1339 get 1340 { 1341 validitycheck(); 1342 if (size == 0) 1343 throw new NoSuchItemException(); 1344 return endsentinel.prev.item; 1345 } 1346 } 1347 1348 /// <summary> 1349 /// Since <code>Add(T item)</code> always add at the end of the list, 1350 /// this describes if list has FIFO or LIFO semantics. 1351 /// </summary> 1352 /// <value>True if the <code>Remove()</code> operation removes from the 1353 /// start of the list, false if it removes from the end. THe default for a new linked list is true.</value> 1354 [Tested] 1355 public virtual bool FIFO 1356 { 1357 [Tested] 1358 get { validitycheck(); return fIFO; } 1359 [Tested] 1360 set { updatecheck(); fIFO = value; } 1361 } 1362 1363 /// <summary> 1364 /// 1365 /// </summary> 1366 public virtual bool IsFixedSize 1367 { 1368 get { validitycheck(); return false; } 1369 } 1370 1371 /// <summary> 1372 /// On this list, this indexer is read/write. 1373 /// <exception cref="IndexOutOfRangeException"/> if i is negative or 1374 /// >= the size of the collection. 1375 /// </summary> 1376 /// <value>The i'th item of this list.</value> 1377 /// <param name="index">The index of the item to fetch or store.</param> 1378 [Tested] 1379 public virtual T this[int index] 1380 { 1381 [Tested] 1382 get { validitycheck(); return get(index).item; } 1383 [Tested] 1384 set 1385 { 1386 updatecheck(); 1387 Node n = get(index); 1388 // 1389 T item = n.item; 1390 #if HASHINDEX 1391 1392 if (itemequalityComparer.Equals(value, item)) 1393 { 1394 n.item = value; 1395 dict.Update(value, n); 1396 } 1397 else if (!dict.FindOrAdd(value, ref n)) 1398 { 1399 dict.Remove(item); 1400 n.item = value; 1401 } 1402 else 1403 throw new ArgumentException("Item already in indexed list"); 1404 #else 1405 n.item = value; 1406 #endif 1407 (underlying ?? this).raiseForSetThis(index, value, item); 1408 } 1409 } 1410 1411 /// <summary> 1412 /// 1413 /// </summary> 1414 /// <value></value> 1415 public virtual Speed IndexingSpeed { get { return Speed.Linear; } } 1416 1417 /// <summary> 1418 /// Insert an item at a specific index location in this list. 1419 /// <exception cref="IndexOutOfRangeException"/> if i is negative or 1420 /// > the size of the collection.</summary> 1421 /// <param name="i">The index at which to insert.</param> 1422 /// <param name="item">The item to insert.</param> 1423 [Tested] Insert(int i, T item)1424 public virtual void Insert(int i, T item) 1425 { 1426 updatecheck(); 1427 insert(i, i == size ? endsentinel : get(i), item); 1428 if (ActiveEvents != EventTypeEnum.None) 1429 (underlying ?? this).raiseForInsert(i + Offset, item); 1430 } 1431 1432 /// <summary> 1433 /// Insert an item at the end of a compatible view, used as a pointer. 1434 /// <para>The <code>pointer</code> must be a view on the same list as 1435 /// <code>this</code> and the endpoitn of <code>pointer</code> must be 1436 /// a valid insertion point of <code>this</code></para> 1437 /// </summary> 1438 /// <exception cref="IncompatibleViewException">If <code>pointer</code> 1439 /// is not a view on the same list as <code>this</code></exception> 1440 /// <exception cref="IndexOutOfRangeException"><b>??????</b> if the endpoint of 1441 /// <code>pointer</code> is not inside <code>this</code></exception> 1442 /// <exception cref="DuplicateNotAllowedException"> if the list has 1443 /// <code>AllowsDuplicates==false</code> and the item is 1444 /// already in the list.</exception> 1445 /// <param name="pointer"></param> 1446 /// <param name="item"></param> Insert(IList<T> pointer, T item)1447 public void Insert(IList<T> pointer, T item) 1448 { 1449 updatecheck(); 1450 if ((pointer == null) || ((pointer.Underlying ?? pointer) != (underlying ?? this))) 1451 throw new IncompatibleViewException(); 1452 #warning INEFFICIENT 1453 //TODO: make this efficient (the whole point of the method: 1454 //Do NOT use Insert, but insert the node at pointer.endsentinel, checking 1455 //via the ordering that this is a valid insertion point 1456 Insert(pointer.Offset + pointer.Count - Offset, item); 1457 } 1458 1459 /// <summary> 1460 /// Insert into this list all items from an enumerable collection starting 1461 /// at a particular index. 1462 /// <exception cref="IndexOutOfRangeException"/> if i is negative or 1463 /// > the size of the collection. 1464 /// </summary> 1465 /// <param name="i">Index to start inserting at</param> 1466 /// <param name="items">Items to insert</param> 1467 /// <typeparam name="U"></typeparam> 1468 [Tested] 1469 public virtual void InsertAll<U>(int i, SCG.IEnumerable<U> items) where U : T 1470 { 1471 insertAll(i, items, true); 1472 } 1473 1474 void insertAll<U>(int i, SCG.IEnumerable<U> items, bool insertion) where U : T 1475 { 1476 updatecheck(); 1477 Node succ, node, pred; 1478 int count = 0; 1479 succ = i == size ? endsentinel : get(i); 1480 pred = node = succ.prev; 1481 #if HASHINDEX 1482 TagGroup taggroup = null; 1483 int taglimit = 0, thetag = 0; 1484 taggroup = gettaggroup(node, succ, out thetag, out taglimit); 1485 try 1486 { 1487 foreach (T item in items) 1488 { 1489 Node tmp = new Node(item, node, null); 1490 if (!dict.FindOrAdd(item, ref tmp)) 1491 { 1492 tmp.tag = thetag < taglimit ? ++thetag : thetag; 1493 tmp.taggroup = taggroup; 1494 node.next = tmp; 1495 count++; 1496 node = tmp; 1497 } 1498 else 1499 throw new DuplicateNotAllowedException("Item already in indexed list"); 1500 } 1501 } 1502 finally 1503 { 1504 if (count != 0) 1505 { 1506 taggroup.count += count; 1507 if (taggroup != pred.taggroup) 1508 taggroup.first = pred.next; 1509 if (taggroup != succ.taggroup) 1510 taggroup.last = node; 1511 succ.prev = node; 1512 node.next = succ; 1513 if (node.tag == node.prev.tag) 1514 splittaggroup(taggroup); 1515 size += count; 1516 if (underlying != null) 1517 underlying.size += count; 1518 fixViewsAfterInsert(succ, pred, count, 0); 1519 raiseForInsertAll(pred, i, count, insertion); 1520 } 1521 } 1522 #else 1523 foreach (T item in items) 1524 { 1525 Node tmp = new Node(item, node, null); 1526 node.next = tmp; 1527 count++; 1528 node = tmp; 1529 } 1530 if (count == 0) 1531 return; 1532 succ.prev = node; 1533 node.next = succ; 1534 size += count; 1535 if (underlying != null) 1536 underlying.size += count; 1537 if (count > 0) 1538 { 1539 fixViewsAfterInsert(succ, pred, count, offset + i); 1540 raiseForInsertAll(pred, i, count, insertion); 1541 } 1542 #endif 1543 } 1544 raiseForInsertAll(Node node, int i, int added, bool insertion)1545 private void raiseForInsertAll(Node node, int i, int added, bool insertion) 1546 { 1547 if (ActiveEvents != 0) 1548 { 1549 int index = Offset + i; 1550 if ((ActiveEvents & (EventTypeEnum.Added | EventTypeEnum.Inserted)) != 0) 1551 for (int j = index; j < index + added; j++) 1552 { 1553 #warning must we check stamps here? 1554 node = node.next; 1555 T item = node.item; 1556 if (insertion) raiseItemInserted(item, j); 1557 raiseItemsAdded(item, 1); 1558 } 1559 raiseCollectionChanged(); 1560 } 1561 } 1562 1563 /// <summary> 1564 /// Insert an item at the front of this list. 1565 /// </summary> 1566 /// <param name="item">The item to insert.</param> 1567 [Tested] InsertFirst(T item)1568 public virtual void InsertFirst(T item) 1569 { 1570 updatecheck(); 1571 insert(0, startsentinel.next, item); 1572 if (ActiveEvents != EventTypeEnum.None) 1573 (underlying ?? this).raiseForInsert(0 + Offset, item); 1574 } 1575 1576 /// <summary> 1577 /// Insert an item at the back of this list. 1578 /// </summary> 1579 /// <param name="item">The item to insert.</param> 1580 [Tested] InsertLast(T item)1581 public virtual void InsertLast(T item) 1582 { 1583 updatecheck(); 1584 insert(size, endsentinel, item); 1585 if (ActiveEvents != EventTypeEnum.None) 1586 (underlying ?? this).raiseForInsert(size - 1 + Offset, item); 1587 } 1588 1589 /// <summary> 1590 /// Create a new list consisting of the results of mapping all items of this 1591 /// list. 1592 /// </summary> 1593 /// <param name="mapper">The delegate defining the map.</param> 1594 /// <returns>The new list.</returns> 1595 [Tested] Map(Fun<T, V> mapper)1596 public IList<V> Map<V>(Fun<T, V> mapper) 1597 { 1598 validitycheck(); 1599 1600 LinkedList<V> retval = new LinkedList<V>(); 1601 return map<V>(mapper, retval); 1602 } 1603 1604 /// <summary> 1605 /// Create a new list consisting of the results of mapping all items of this 1606 /// list. The new list will use a specified equalityComparer for the item type. 1607 /// </summary> 1608 /// <typeparam name="V">The type of items of the new list</typeparam> 1609 /// <param name="mapper">The delegate defining the map.</param> 1610 /// <param name="equalityComparer">The equalityComparer to use for the new list</param> 1611 /// <returns>The new list.</returns> Map(Fun<T, V> mapper, SCG.IEqualityComparer<V> equalityComparer)1612 public IList<V> Map<V>(Fun<T, V> mapper, SCG.IEqualityComparer<V> equalityComparer) 1613 { 1614 validitycheck(); 1615 1616 LinkedList<V> retval = new LinkedList<V>(equalityComparer); 1617 return map<V>(mapper, retval); 1618 } 1619 map(Fun<T, V> mapper, LinkedList<V> retval)1620 private IList<V> map<V>(Fun<T, V> mapper, LinkedList<V> retval) 1621 { 1622 if (size == 0) 1623 return retval; 1624 int stamp = this.stamp; 1625 Node cursor = startsentinel.next; 1626 LinkedList<V>.Node mcursor = retval.startsentinel; 1627 1628 #if HASHINDEX 1629 double tagdelta = int.MaxValue / (size + 1.0); 1630 int count = 1; 1631 LinkedList<V>.TagGroup taggroup = null; 1632 taggroup = new LinkedList<V>.TagGroup(); 1633 retval.taggroups = 1; 1634 taggroup.count = size; 1635 #endif 1636 while (cursor != endsentinel) 1637 { 1638 V v = mapper(cursor.item); 1639 modifycheck(stamp); 1640 mcursor.next = new LinkedList<V>.Node(v, mcursor, null); 1641 cursor = cursor.next; 1642 mcursor = mcursor.next; 1643 #if HASHINDEX 1644 retval.dict.Add(v, mcursor); 1645 mcursor.taggroup = taggroup; 1646 mcursor.tag = (int)(tagdelta * count++); 1647 #endif 1648 } 1649 1650 #if HASHINDEX 1651 taggroup.first = retval.startsentinel.next; 1652 taggroup.last = mcursor; 1653 #endif 1654 retval.endsentinel.prev = mcursor; 1655 mcursor.next = retval.endsentinel; 1656 retval.size = size; 1657 return retval; 1658 } 1659 1660 /// <summary> 1661 /// Remove one item from the list: from the front if <code>FIFO</code> 1662 /// is true, else from the back. 1663 /// <exception cref="NoSuchItemException"/> if this list is empty. 1664 /// </summary> 1665 /// <returns>The removed item.</returns> 1666 [Tested] Remove()1667 public virtual T Remove() 1668 { 1669 updatecheck(); 1670 if (size == 0) 1671 throw new NoSuchItemException("List is empty"); 1672 T item = fIFO ? remove(startsentinel.next, 0) : remove(endsentinel.prev, size - 1); 1673 #if HASHINDEX 1674 dict.Remove(item); 1675 #endif 1676 (underlying ?? this).raiseForRemove(item); 1677 return item; 1678 } 1679 1680 /// <summary> 1681 /// Remove one item from the front of the list. 1682 /// <exception cref="NoSuchItemException"/> if this list is empty. 1683 /// </summary> 1684 /// <returns>The removed item.</returns> 1685 [Tested] RemoveFirst()1686 public virtual T RemoveFirst() 1687 { 1688 updatecheck(); 1689 if (size == 0) 1690 throw new NoSuchItemException("List is empty"); 1691 1692 T item = remove(startsentinel.next, 0); 1693 #if HASHINDEX 1694 dict.Remove(item); 1695 #endif 1696 if (ActiveEvents != EventTypeEnum.None) 1697 (underlying ?? this).raiseForRemoveAt(Offset, item); 1698 return item; 1699 } 1700 1701 /// <summary> 1702 /// Remove one item from the back of the list. 1703 /// <exception cref="NoSuchItemException"/> if this list is empty. 1704 /// </summary> 1705 /// <returns>The removed item.</returns> 1706 [Tested] RemoveLast()1707 public virtual T RemoveLast() 1708 { 1709 updatecheck(); 1710 if (size == 0) 1711 throw new NoSuchItemException("List is empty"); 1712 1713 T item = remove(endsentinel.prev, size - 1); 1714 #if HASHINDEX 1715 dict.Remove(item); 1716 #endif 1717 if (ActiveEvents != EventTypeEnum.None) 1718 (underlying ?? this).raiseForRemoveAt(size + Offset, item); 1719 return item; 1720 } 1721 1722 /// <summary> 1723 /// Create a list view on this list. 1724 /// </summary> 1725 /// <exception cref="ArgumentOutOfRangeException"> if the start or count is negative</exception> 1726 /// <exception cref="ArgumentException"> if the range does not fit within list.</exception> 1727 /// <param name="start">The index in this list of the start of the view.</param> 1728 /// <param name="count">The size of the view.</param> 1729 /// <returns>The new list view.</returns> 1730 [Tested] View(int start, int count)1731 public virtual IList<T> View(int start, int count) 1732 { 1733 checkRange(start, count); 1734 validitycheck(); 1735 if (views == null) 1736 views = new WeakViewList<LinkedList<T>>(); 1737 LinkedList<T> retval = (LinkedList<T>)MemberwiseClone(); 1738 retval.underlying = underlying != null ? underlying : this; 1739 retval.offset = offset + start; 1740 retval.size = count; 1741 getPair(start - 1, start + count, out retval.startsentinel, out retval.endsentinel, 1742 new int[] { -1, size }, new Node[] { startsentinel, endsentinel }); 1743 //retval.startsentinel = start == 0 ? startsentinel : get(start - 1); 1744 //retval.endsentinel = start + count == size ? endsentinel : get(start + count); 1745 1746 //TODO: for the purpose of Dispose, we need to retain a ref to the node 1747 retval.myWeakReference = views.Add(retval); 1748 return retval; 1749 } 1750 1751 /// <summary> 1752 /// Create a list view on this list containing the (first) occurrence of a particular item. 1753 /// </summary> 1754 /// <exception cref="ArgumentException"> if the item is not in this list.</exception> 1755 /// <param name="item">The item to find.</param> 1756 /// <returns>The new list view.</returns> ViewOf(T item)1757 public virtual IList<T> ViewOf(T item) 1758 { 1759 #if HASHINDEX 1760 Node n; 1761 validitycheck(); 1762 if (!contains(item, out n)) 1763 return null; 1764 LinkedList<T> retval = (LinkedList<T>)MemberwiseClone(); 1765 retval.underlying = underlying != null ? underlying : this; 1766 retval.offset = null; 1767 retval.startsentinel = n.prev; 1768 retval.endsentinel = n.next; 1769 retval.size = 1; 1770 return retval; 1771 #else 1772 int index = 0; 1773 Node n = startsentinel.next; 1774 if (!find(item, ref n, ref index)) 1775 return null; 1776 //TODO: optimize with getpair! 1777 return View(index, 1); 1778 #endif 1779 } 1780 1781 /// <summary> 1782 /// Create a list view on this list containing the last occurrence of a particular item. 1783 /// <exception cref="ArgumentException"/> if the item is not in this list. 1784 /// </summary> 1785 /// <param name="item">The item to find.</param> 1786 /// <returns>The new list view.</returns> LastViewOf(T item)1787 public virtual IList<T> LastViewOf(T item) 1788 { 1789 #if HASHINDEX 1790 return ViewOf(item); 1791 #else 1792 int index = size - 1; 1793 Node n = endsentinel.prev; 1794 if (!dnif(item, ref n, ref index)) 1795 return null; 1796 return View(index, 1); 1797 #endif 1798 } 1799 1800 /// <summary> 1801 /// Null if this list is not a view. 1802 /// </summary> 1803 /// <value>Underlying list for view.</value> 1804 [Tested] 1805 public virtual IList<T> Underlying { [Tested]get { validitycheck(); return underlying; } } 1806 1807 /// <summary> 1808 /// 1809 /// </summary> 1810 /// <value></value> 1811 public virtual bool IsValid { get { return isValid; } } 1812 1813 /// <summary> 1814 /// </summary> 1815 /// <value>Offset for this list view or 0 for a underlying list.</value> 1816 [Tested] 1817 public virtual int Offset 1818 { 1819 [Tested] 1820 get 1821 { 1822 validitycheck(); 1823 #if HASHINDEX 1824 if (offset == null && underlying != null) 1825 { 1826 //TODO: search from both ends simultaneously! 1827 Node n = underlying.startsentinel; 1828 int i = 0; 1829 while (n != startsentinel) { n = n.next; i++; } 1830 offset = i; 1831 } 1832 #endif 1833 return (int)offset; 1834 } 1835 } 1836 1837 /// <summary> 1838 /// Slide this list view along the underlying list. 1839 /// </summary> 1840 /// <exception cref="NotAViewException"> if this list is not a view.</exception> 1841 /// <exception cref="ArgumentOutOfRangeException"> if the operation 1842 /// would bring either end of the view outside the underlying list.</exception> 1843 /// <param name="offset">The signed amount to slide: positive to slide 1844 /// towards the end.</param> 1845 [Tested] Slide(int offset)1846 public IList<T> Slide(int offset) 1847 { 1848 if (!TrySlide(offset, size)) 1849 throw new ArgumentOutOfRangeException(); 1850 return this; 1851 } 1852 1853 //TODO: more test cases 1854 /// <summary> 1855 /// Slide this list view along the underlying list, perhaps changing its size. 1856 /// </summary> 1857 /// <exception cref="NotAViewException"> if this list is not a view.</exception> 1858 /// <exception cref="ArgumentOutOfRangeException"> if the operation 1859 /// would bring either end of the view outside the underlying list.</exception> 1860 /// <param name="offset">The signed amount to slide: positive to slide 1861 /// towards the end.</param> 1862 /// <param name="size">The new size of the view.</param> Slide(int offset, int size)1863 public IList<T> Slide(int offset, int size) 1864 { 1865 if (!TrySlide(offset, size)) 1866 throw new ArgumentOutOfRangeException(); 1867 return this; 1868 } 1869 1870 /// <summary> 1871 /// 1872 /// </summary> 1873 /// <param name="offset"></param> 1874 /// <returns></returns> TrySlide(int offset)1875 public virtual bool TrySlide(int offset) { return TrySlide(offset, size); } 1876 1877 /// <summary> 1878 /// 1879 /// </summary> 1880 /// <param name="offset"></param> 1881 /// <param name="size"></param> 1882 /// <returns></returns> TrySlide(int offset, int size)1883 public virtual bool TrySlide(int offset, int size) 1884 { 1885 updatecheck(); 1886 if (underlying == null) 1887 throw new NotAViewException("List not a view"); 1888 1889 #pragma warning disable 472 1890 if (this.offset == null) //Note: only possible with HASHINDEX 1891 #pragma warning restore 472 1892 { 1893 #pragma warning disable 162 1894 try 1895 { 1896 getPair(offset - 1, offset + size, out startsentinel, out endsentinel, 1897 new int[] { -1, this.size }, new Node[] { startsentinel, endsentinel }); 1898 //TODO: maybe-update offset field 1899 } 1900 catch (NullReferenceException) 1901 { 1902 return false; 1903 } 1904 #pragma warning restore 162 1905 } 1906 else 1907 { 1908 if (offset + this.offset < 0 || offset + this.offset + size > underlying.size) 1909 return false; 1910 int oldoffset = (int)(this.offset); 1911 getPair(offset - 1, offset + size, out startsentinel, out endsentinel, 1912 new int[] { -oldoffset - 1, -1, this.size, underlying.size - oldoffset }, 1913 new Node[] { underlying.startsentinel, startsentinel, endsentinel, underlying.endsentinel }); 1914 } 1915 this.size = size; 1916 this.offset += offset; 1917 return true; 1918 } 1919 1920 1921 //TODO: improve the complexity of the implementation 1922 /// <summary> 1923 /// 1924 /// <para>Returns null if <code>otherView</code> is strictly to the left of this view</para> 1925 /// </summary> 1926 /// <param name="otherView"></param> 1927 /// <exception cref="IncompatibleViewException">If otherView does not have the same underlying list as this</exception> 1928 /// <returns></returns> Span(IList<T> otherView)1929 public virtual IList<T> Span(IList<T> otherView) 1930 { 1931 if ((otherView == null) || ((otherView.Underlying ?? otherView) != (underlying ?? this))) 1932 throw new IncompatibleViewException(); 1933 if (otherView.Offset + otherView.Count - Offset < 0) 1934 return null; 1935 return (underlying ?? this).View(Offset, otherView.Offset + otherView.Count - Offset); 1936 } 1937 1938 1939 //Question: should we swap items or move nodes around? 1940 //The first seems much more efficient unless the items are value types 1941 //with a large memory footprint. 1942 //(Swapping will do count*3/2 T assignments, linking around will do 1943 // 4*count ref assignments; note that ref assignments are more expensive 1944 //than copying non-ref bits) 1945 /// <summary> 1946 /// Reverse the list so the items are in the opposite sequence order. 1947 /// </summary> 1948 [Tested] Reverse()1949 public virtual void Reverse() 1950 { 1951 updatecheck(); 1952 if (size == 0) 1953 return; 1954 1955 Position[] positions = null; 1956 int poslow = 0, poshigh = 0; 1957 if (views != null) 1958 { 1959 CircularQueue<Position> _positions = null; 1960 foreach (LinkedList<T> view in views) 1961 { 1962 if (view != this) 1963 { 1964 switch (viewPosition(view)) 1965 { 1966 case MutualViewPosition.ContainedIn: 1967 (_positions ?? (_positions = new CircularQueue<Position>())).Enqueue(new Position(view, true)); 1968 _positions.Enqueue(new Position(view, false)); 1969 break; 1970 case MutualViewPosition.Overlapping: 1971 view.Dispose(); 1972 break; 1973 case MutualViewPosition.Contains: 1974 case MutualViewPosition.NonOverlapping: 1975 break; 1976 } 1977 } 1978 } 1979 if (_positions != null) 1980 { 1981 positions = _positions.ToArray(); 1982 Sorting.IntroSort<Position>(positions, 0, positions.Length, PositionComparer.Default); 1983 poshigh = positions.Length - 1; 1984 } 1985 } 1986 1987 Node a = get(0), b = get(size - 1); 1988 for (int i = 0; i < size / 2; i++) 1989 { 1990 T swap; 1991 swap = a.item; a.item = b.item; b.item = swap; 1992 #if HASHINDEX 1993 dict[a.item] = a; dict[b.item] = b; 1994 #endif 1995 if (positions != null) 1996 mirrorViewSentinelsForReverse(positions, ref poslow, ref poshigh, a, b, i); 1997 a = a.next; b = b.prev; 1998 } 1999 if (positions != null && size % 2 != 0) 2000 mirrorViewSentinelsForReverse(positions, ref poslow, ref poshigh, a, b, size / 2); 2001 (underlying ?? this).raiseCollectionChanged(); 2002 } 2003 mirrorViewSentinelsForReverse(Position[] positions, ref int poslow, ref int poshigh, Node a, Node b, int i)2004 private void mirrorViewSentinelsForReverse(Position[] positions, ref int poslow, ref int poshigh, Node a, Node b, int i) 2005 { 2006 #if HASHINDEX 2007 int? aindex = offset + i, bindex = offset + size - 1 - i; 2008 #else 2009 int aindex = offset + i, bindex = offset + size - 1 - i; 2010 #endif 2011 Position pos; 2012 #if HASHINDEX 2013 while (poslow <= poshigh && (pos = positions[poslow]).Endpoint == a) 2014 #else 2015 while (poslow <= poshigh && (pos = positions[poslow]).Index == aindex) 2016 #endif 2017 { 2018 //TODO: Note: in the case og hashed linked list, if this.offset == null, but pos.View.offset!=null 2019 //we may at this point compute this.offset and non-null values of aindex and bindex 2020 if (pos.Left) 2021 pos.View.endsentinel = b.next; 2022 else 2023 { 2024 pos.View.startsentinel = b.prev; 2025 pos.View.offset = bindex; 2026 } 2027 poslow++; 2028 } 2029 #if HASHINDEX 2030 while (poslow < poshigh && (pos = positions[poshigh]).Endpoint == b) 2031 #else 2032 while (poslow < poshigh && (pos = positions[poshigh]).Index == bindex) 2033 #endif 2034 { 2035 if (pos.Left) 2036 pos.View.endsentinel = a.next; 2037 else 2038 { 2039 pos.View.startsentinel = a.prev; 2040 pos.View.offset = aindex; 2041 } 2042 poshigh--; 2043 } 2044 } 2045 2046 /// <summary> 2047 /// Check if this list is sorted according to the default sorting order 2048 /// for the item type T, as defined by the <see cref="T:C5.Comparer`1"/> class 2049 /// </summary> 2050 /// <exception cref="NotComparableException">if T is not comparable</exception> 2051 /// <returns>True if the list is sorted, else false.</returns> IsSorted()2052 public bool IsSorted() { return IsSorted(Comparer<T>.Default); } 2053 2054 /// <summary> 2055 /// Check if this list is sorted according to a specific sorting order. 2056 /// </summary> 2057 /// <param name="c">The comparer defining the sorting order.</param> 2058 /// <returns>True if the list is sorted, else false.</returns> 2059 [Tested] IsSorted(SCG.IComparer<T> c)2060 public virtual bool IsSorted(SCG.IComparer<T> c) 2061 { 2062 validitycheck(); 2063 if (size <= 1) 2064 return true; 2065 2066 Node node = startsentinel.next; 2067 T prevItem = node.item; 2068 2069 node = node.next; 2070 while (node != endsentinel) 2071 { 2072 if (c.Compare(prevItem, node.item) > 0) 2073 return false; 2074 else 2075 { 2076 prevItem = node.item; 2077 node = node.next; 2078 } 2079 } 2080 2081 return true; 2082 } 2083 2084 /// <summary> 2085 /// Sort the items of the list according to the default sorting order 2086 /// for the item type T, as defined by the Comparer[T] class. 2087 /// (<see cref="T:C5.Comparer`1"/>). 2088 /// The sorting is stable. 2089 /// </summary> 2090 /// <exception cref="InvalidOperationException">if T is not comparable</exception> Sort()2091 public virtual void Sort() { Sort(Comparer<T>.Default); } 2092 2093 // Sort the linked list using mergesort 2094 /// <summary> 2095 /// Sort the items of the list according to a specific sorting order. 2096 /// The sorting is stable. 2097 /// </summary> 2098 /// <param name="c">The comparer defining the sorting order.</param> 2099 [Tested] Sort(SCG.IComparer<T> c)2100 public virtual void Sort(SCG.IComparer<T> c) 2101 { 2102 updatecheck(); 2103 if (size == 0) 2104 return; 2105 disposeOverlappingViews(false); 2106 #if HASHINDEX 2107 if (underlying != null) 2108 { 2109 Node cursor = startsentinel.next; 2110 while (cursor != endsentinel) 2111 { 2112 cursor.taggroup.count--; 2113 cursor = cursor.next; 2114 } 2115 } 2116 #endif 2117 // Build a linked list of non-empty runs. 2118 // The prev field in first node of a run points to next run's first node 2119 Node runTail = startsentinel.next; 2120 Node prevNode = startsentinel.next; 2121 2122 endsentinel.prev.next = null; 2123 while (prevNode != null) 2124 { 2125 Node node = prevNode.next; 2126 2127 while (node != null && c.Compare(prevNode.item, node.item) <= 0) 2128 { 2129 prevNode = node; 2130 node = prevNode.next; 2131 } 2132 2133 // Completed a run; prevNode is the last node of that run 2134 prevNode.next = null; // Finish the run 2135 runTail.prev = node; // Link it into the chain of runs 2136 runTail = node; 2137 if (c.Compare(endsentinel.prev.item, prevNode.item) <= 0) 2138 endsentinel.prev = prevNode; // Update last pointer to point to largest 2139 2140 prevNode = node; // Start a new run 2141 } 2142 2143 // Repeatedly merge runs two and two, until only one run remains 2144 while (startsentinel.next.prev != null) 2145 { 2146 Node run = startsentinel.next; 2147 Node newRunTail = null; 2148 2149 while (run != null && run.prev != null) 2150 { // At least two runs, merge 2151 Node nextRun = run.prev.prev; 2152 Node newrun = mergeRuns(run, run.prev, c); 2153 2154 if (newRunTail != null) 2155 newRunTail.prev = newrun; 2156 else 2157 startsentinel.next = newrun; 2158 2159 newRunTail = newrun; 2160 run = nextRun; 2161 } 2162 2163 if (run != null) // Add the last run, if any 2164 newRunTail.prev = run; 2165 } 2166 2167 endsentinel.prev.next = endsentinel; 2168 startsentinel.next.prev = startsentinel; 2169 2170 //assert invariant(); 2171 //assert isSorted(); 2172 #if HASHINDEX 2173 { 2174 Node cursor = startsentinel.next, end = endsentinel; 2175 int tag, taglimit; 2176 TagGroup t = gettaggroup(startsentinel, endsentinel, out tag, out taglimit); 2177 int tagdelta = taglimit / (size + 1) - tag / (size + 1); 2178 tagdelta = tagdelta == 0 ? 1 : tagdelta; 2179 if (underlying == null) 2180 taggroups = 1; 2181 while (cursor != end) 2182 { 2183 tag = tag + tagdelta > taglimit ? taglimit : tag + tagdelta; 2184 cursor.tag = tag; 2185 t.count++; 2186 cursor.taggroup = t; 2187 cursor = cursor.next; 2188 } 2189 if (t != startsentinel.taggroup) 2190 t.first = startsentinel.next; 2191 if (t != endsentinel.taggroup) 2192 t.last = endsentinel.prev; 2193 if (tag == taglimit) 2194 splittaggroup(t); 2195 } 2196 #endif 2197 (underlying ?? this).raiseCollectionChanged(); 2198 } 2199 mergeRuns(Node run1, Node run2, SCG.IComparer<T> c)2200 private static Node mergeRuns(Node run1, Node run2, SCG.IComparer<T> c) 2201 { 2202 //assert run1 != null && run2 != null; 2203 Node prev; 2204 bool prev1; // is prev from run1? 2205 2206 if (c.Compare(run1.item, run2.item) <= 0) 2207 { 2208 prev = run1; 2209 prev1 = true; 2210 run1 = run1.next; 2211 } 2212 else 2213 { 2214 prev = run2; 2215 prev1 = false; 2216 run2 = run2.next; 2217 } 2218 2219 Node start = prev; 2220 2221 //assert start != null; 2222 start.prev = null; 2223 while (run1 != null && run2 != null) 2224 { 2225 if (prev1) 2226 { 2227 //assert prev.next == run1; 2228 //Comparable run2item = (Comparable)run2.item; 2229 while (run1 != null && c.Compare(run2.item, run1.item) >= 0) 2230 { 2231 prev = run1; 2232 run1 = prev.next; 2233 } 2234 2235 if (run1 != null) 2236 { // prev.item <= run2.item < run1.item; insert run2 2237 prev.next = run2; 2238 run2.prev = prev; 2239 prev = run2; 2240 run2 = prev.next; 2241 prev1 = false; 2242 } 2243 } 2244 else 2245 { 2246 //assert prev.next == run2; 2247 //Comparable run1item = (Comparable)run1.item; 2248 while (run2 != null && c.Compare(run1.item, run2.item) > 0) 2249 { 2250 prev = run2; 2251 run2 = prev.next; 2252 } 2253 2254 if (run2 != null) 2255 { // prev.item < run1.item <= run2.item; insert run1 2256 prev.next = run1; 2257 run1.prev = prev; 2258 prev = run1; 2259 run1 = prev.next; 2260 prev1 = true; 2261 } 2262 } 2263 } 2264 2265 //assert !(run1 != null && prev1) && !(run2 != null && !prev1); 2266 if (run1 != null) 2267 { // last run2 < all of run1; attach run1 at end 2268 prev.next = run1; 2269 run1.prev = prev; 2270 } 2271 else if (run2 != null) 2272 { // last run1 2273 prev.next = run2; 2274 run2.prev = prev; 2275 } 2276 2277 return start; 2278 } 2279 2280 /// <summary> 2281 /// Randomly shuffle the items of this list. 2282 /// <para>Will invalidate overlapping views???</para> 2283 /// </summary> Shuffle()2284 public virtual void Shuffle() { Shuffle(new C5Random()); } 2285 2286 2287 /// <summary> 2288 /// Shuffle the items of this list according to a specific random source. 2289 /// <para>Will invalidate overlapping views???</para> 2290 /// </summary> 2291 /// <param name="rnd">The random source.</param> Shuffle(Random rnd)2292 public virtual void Shuffle(Random rnd) 2293 { 2294 updatecheck(); 2295 if (size == 0) 2296 return; 2297 disposeOverlappingViews(false); 2298 ArrayList<T> a = new ArrayList<T>(); 2299 a.AddAll(this); 2300 a.Shuffle(rnd); 2301 Node cursor = startsentinel.next; 2302 int j = 0; 2303 while (cursor != endsentinel) 2304 { 2305 cursor.item = a[j++]; 2306 #if HASHINDEX 2307 dict[cursor.item] = cursor; 2308 #endif 2309 cursor = cursor.next; 2310 } 2311 (underlying ?? this).raiseCollectionChanged(); 2312 } 2313 2314 #endregion 2315 2316 #region IIndexed<T> Members 2317 2318 /// <summary> 2319 /// <exception cref="IndexOutOfRangeException"/>. 2320 /// </summary> 2321 /// <value>The directed collection of items in a specific index interval.</value> 2322 /// <param name="start">The low index of the interval (inclusive).</param> 2323 /// <param name="count">The size of the range.</param> 2324 [Tested] 2325 public IDirectedCollectionValue<T> this[int start, int count] 2326 { 2327 [Tested] 2328 get 2329 { 2330 validitycheck(); 2331 checkRange(start, count); 2332 return new Range(this, start, count, true); 2333 } 2334 } 2335 2336 /// <summary> 2337 /// Searches for an item in the list going forwrds from the start. 2338 /// </summary> 2339 /// <param name="item">Item to search for.</param> 2340 /// <returns>Index of item from start.</returns> 2341 [Tested] IndexOf(T item)2342 public virtual int IndexOf(T item) 2343 { 2344 validitycheck(); 2345 Node node; 2346 #if HASHINDEX 2347 if (!dict.Find(item, out node) || !insideview(node)) 2348 return ~size; 2349 #endif 2350 node = startsentinel.next; 2351 int index = 0; 2352 if (find(item, ref node, ref index)) 2353 return index; 2354 else 2355 return ~size; 2356 } 2357 2358 /// <summary> 2359 /// Searches for an item in the list going backwords from the end. 2360 /// </summary> 2361 /// <param name="item">Item to search for.</param> 2362 /// <returns>Index of of item from the end.</returns> 2363 [Tested] LastIndexOf(T item)2364 public virtual int LastIndexOf(T item) 2365 { 2366 #if HASHINDEX 2367 return IndexOf(item); 2368 #else 2369 validitycheck(); 2370 2371 Node node = endsentinel.prev; 2372 int index = size - 1; 2373 2374 if (dnif(item, ref node, ref index)) 2375 return index; 2376 else 2377 return ~size; 2378 #endif 2379 } 2380 2381 /// <summary> 2382 /// Remove the item at a specific position of the list. 2383 /// <exception cref="IndexOutOfRangeException"/> if i is negative or 2384 /// >= the size of the collection. 2385 /// </summary> 2386 /// <param name="i">The index of the item to remove.</param> 2387 /// <returns>The removed item.</returns> 2388 [Tested] RemoveAt(int i)2389 public virtual T RemoveAt(int i) 2390 { 2391 updatecheck(); 2392 T retval = remove(get(i), i); 2393 #if HASHINDEX 2394 dict.Remove(retval); 2395 #endif 2396 if (ActiveEvents != EventTypeEnum.None) 2397 (underlying ?? this).raiseForRemoveAt(Offset + i, retval); 2398 return retval; 2399 } 2400 2401 /// <summary> 2402 /// Remove all items in an index interval. 2403 /// <exception cref="IndexOutOfRangeException"/>???. 2404 /// </summary> 2405 /// <param name="start">The index of the first item to remove.</param> 2406 /// <param name="count">The number of items to remove.</param> 2407 [Tested] RemoveInterval(int start, int count)2408 public virtual void RemoveInterval(int start, int count) 2409 { 2410 #if HASHINDEX 2411 updatecheck(); 2412 checkRange(start, count); 2413 if (count == 0) 2414 return; 2415 2416 View(start, count).Clear(); 2417 #else 2418 //Note: this is really almost equaivalent to Clear on a view 2419 updatecheck(); 2420 checkRange(start, count); 2421 if (count == 0) 2422 return; 2423 2424 //for small count: optimize 2425 //use an optimal get(int i, int j, ref Node ni, ref Node nj)? 2426 Node a = get(start), b = get(start + count - 1); 2427 fixViewsBeforeRemove(start, count, a, b); 2428 a.prev.next = b.next; 2429 b.next.prev = a.prev; 2430 if (underlying != null) 2431 underlying.size -= count; 2432 2433 size -= count; 2434 if (ActiveEvents != EventTypeEnum.None) 2435 (underlying ?? this).raiseForRemoveInterval(start + Offset, count); 2436 #endif 2437 } 2438 raiseForRemoveInterval(int start, int count)2439 void raiseForRemoveInterval(int start, int count) 2440 { 2441 if (ActiveEvents != 0) 2442 { 2443 raiseCollectionCleared(size == 0, count, start); 2444 raiseCollectionChanged(); 2445 } 2446 } 2447 #endregion 2448 2449 #region ISequenced<T> Members 2450 2451 /// <summary> 2452 /// 2453 /// </summary> 2454 /// <returns></returns> 2455 [Tested] GetSequencedHashCode()2456 public override int GetSequencedHashCode() { validitycheck(); return base.GetSequencedHashCode(); } 2457 2458 /// <summary> 2459 /// 2460 /// </summary> 2461 /// <param name="that"></param> 2462 /// <returns></returns> 2463 [Tested] SequencedEquals(ISequenced<T> that)2464 public override bool SequencedEquals(ISequenced<T> that) { validitycheck(); return base.SequencedEquals(that); } 2465 2466 #endregion 2467 2468 #region IDirectedCollection<T> Members 2469 2470 /// <summary> 2471 /// Create a collection containing the same items as this collection, but 2472 /// whose enumerator will enumerate the items backwards. The new collection 2473 /// will become invalid if the original is modified. Method typicaly used as in 2474 /// <code>foreach (T x in coll.Backwards()) {...}</code> 2475 /// </summary> 2476 /// <returns>The backwards collection.</returns> 2477 [Tested] Backwards()2478 public override IDirectedCollectionValue<T> Backwards() 2479 { return this[0, size].Backwards(); } 2480 2481 #endregion 2482 2483 #region IDirectedEnumerable<T> Members 2484 2485 [Tested] Backwards()2486 IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); } 2487 2488 #endregion 2489 2490 #region IEditableCollection<T> Members 2491 2492 /// <summary> 2493 /// The value is symbolic indicating the type of asymptotic complexity 2494 /// in terms of the size of this collection (worst-case or amortized as 2495 /// relevant). 2496 /// </summary> 2497 /// <value>Speed.Linear</value> 2498 [Tested] 2499 public virtual Speed ContainsSpeed 2500 { 2501 [Tested] 2502 get 2503 { 2504 #if HASHINDEX 2505 return Speed.Constant; 2506 #else 2507 return Speed.Linear; 2508 #endif 2509 } 2510 } 2511 2512 /// <summary> 2513 /// Performs a check for view validity before calling base.GetUnsequencedHashCode() 2514 /// </summary> 2515 /// <returns></returns> 2516 [Tested] GetUnsequencedHashCode()2517 public override int GetUnsequencedHashCode() 2518 { validitycheck(); return base.GetUnsequencedHashCode(); } 2519 2520 /// <summary> 2521 /// 2522 /// </summary> 2523 /// <param name="that"></param> 2524 /// <returns></returns> 2525 [Tested] UnsequencedEquals(ICollection<T> that)2526 public override bool UnsequencedEquals(ICollection<T> that) 2527 { validitycheck(); return base.UnsequencedEquals(that); } 2528 2529 /// <summary> 2530 /// Check if this collection contains (an item equivalent to according to the 2531 /// itemequalityComparer) a particular value. 2532 /// </summary> 2533 /// <param name="item">The value to check for.</param> 2534 /// <returns>True if the items is in this collection.</returns> 2535 [Tested] Contains(T item)2536 public virtual bool Contains(T item) 2537 { 2538 validitycheck(); 2539 Node node; 2540 return contains(item, out node); 2541 } 2542 2543 /// <summary> 2544 /// Check if this collection contains an item equivalent according to the 2545 /// itemequalityComparer to a particular value. If so, return in the ref argument (a 2546 /// binary copy of) the actual value found. 2547 /// </summary> 2548 /// <param name="item">The value to look for.</param> 2549 /// <returns>True if the items is in this collection.</returns> 2550 [Tested] Find(ref T item)2551 public virtual bool Find(ref T item) 2552 { 2553 validitycheck(); 2554 Node node; 2555 if (contains(item, out node)) { item = node.item; return true; } 2556 return false; 2557 } 2558 2559 /// <summary> 2560 /// Check if this collection contains an item equivalent according to the 2561 /// itemequalityComparer to a particular value. If so, update the item in the collection 2562 /// to with a binary copy of the supplied value. Will update a single item. 2563 /// </summary> 2564 /// <param name="item">Value to update.</param> 2565 /// <returns>True if the item was found and hence updated.</returns> 2566 [Tested] Update(T item)2567 public virtual bool Update(T item) { T olditem; return Update(item, out olditem); } 2568 2569 /// <summary> 2570 /// 2571 /// </summary> 2572 /// <param name="item"></param> 2573 /// <param name="olditem"></param> 2574 /// <returns></returns> Update(T item, out T olditem)2575 public virtual bool Update(T item, out T olditem) 2576 { 2577 updatecheck(); 2578 Node node; 2579 2580 if (contains(item, out node)) 2581 { 2582 olditem = node.item; 2583 node.item = item; 2584 #if HASHINDEX 2585 //Avoid clinging onto a reference to olditem via dict! 2586 dict.Update(item, node); 2587 #endif 2588 (underlying ?? this).raiseForUpdate(item, olditem); 2589 return true; 2590 } 2591 2592 olditem = default(T); 2593 return false; 2594 } 2595 2596 /// <summary> 2597 /// Check if this collection contains an item equivalent according to the 2598 /// itemequalityComparer to a particular value. If so, return in the ref argument (a 2599 /// binary copy of) the actual value found. Else, add the item to the collection. 2600 /// </summary> 2601 /// <param name="item">The value to look for.</param> 2602 /// <returns>True if the item was found (hence not added).</returns> 2603 [Tested] FindOrAdd(ref T item)2604 public virtual bool FindOrAdd(ref T item) 2605 { 2606 updatecheck(); 2607 #if HASHINDEX 2608 //This is an extended myinsert: 2609 Node node = new Node(item); 2610 if (!dict.FindOrAdd(item, ref node)) 2611 { 2612 insertNode(true, endsentinel, node); 2613 (underlying ?? this).raiseForAdd(item); 2614 return false; 2615 } 2616 if (!insideview(node)) 2617 throw new ArgumentException("Item alredy in indexed list but outside view"); 2618 item = node.item; 2619 return true; 2620 #else 2621 if (Find(ref item)) 2622 return true; 2623 2624 Add(item); 2625 return false; 2626 #endif 2627 } 2628 2629 /// <summary> 2630 /// Check if this collection contains an item equivalent according to the 2631 /// itemequalityComparer to a particular value. If so, update the item in the collection 2632 /// to with a binary copy of the supplied value; else add the value to the collection. 2633 /// </summary> 2634 /// <param name="item">Value to add or update.</param> 2635 /// <returns>True if the item was found and updated (hence not added).</returns> 2636 [Tested] UpdateOrAdd(T item)2637 public virtual bool UpdateOrAdd(T item) { T olditem; return UpdateOrAdd(item, out olditem); } 2638 2639 /// <summary> 2640 /// 2641 /// </summary> 2642 /// <param name="item"></param> 2643 /// <param name="olditem"></param> 2644 /// <returns></returns> UpdateOrAdd(T item, out T olditem)2645 public virtual bool UpdateOrAdd(T item, out T olditem) 2646 { 2647 updatecheck(); 2648 #if HASHINDEX 2649 Node node = new Node(item); 2650 //NOTE: it is hard to do this without double access to the dictionary 2651 //in the update case 2652 if (dict.FindOrAdd(item, ref node)) 2653 { 2654 if (!insideview(node)) 2655 throw new ArgumentException("Item in indexed list but outside view"); 2656 olditem = node.item; 2657 //Avoid clinging onto a reference to olditem via dict! 2658 dict.Update(item, node); 2659 node.item = item; 2660 (underlying ?? this).raiseForUpdate(item, olditem); 2661 return true; 2662 } 2663 insertNode(true, endsentinel, node); 2664 (underlying ?? this).raiseForAdd(item); 2665 #else 2666 if (Update(item, out olditem)) 2667 return true; 2668 Add(item); 2669 #endif 2670 olditem = default(T); 2671 return false; 2672 } 2673 2674 /// <summary> 2675 /// Remove a particular item from this collection. Since the collection has bag 2676 /// semantics only one copy equivalent to the supplied item is removed. 2677 /// </summary> 2678 /// <param name="item">The value to remove.</param> 2679 /// <returns>True if the item was found (and removed).</returns> 2680 [Tested] Remove(T item)2681 public virtual bool Remove(T item) 2682 { 2683 updatecheck(); 2684 int i = 0; 2685 Node node; 2686 #if HASHINDEX 2687 if (!dictremove(item, out node)) 2688 #else 2689 node = fIFO ? startsentinel.next : endsentinel.prev; 2690 if (!(fIFO ? find(item, ref node, ref i) : dnif(item, ref node, ref i))) 2691 #endif 2692 return false; 2693 T removeditem = remove(node, i); 2694 (underlying ?? this).raiseForRemove(removeditem); 2695 return true; 2696 } 2697 2698 /// <summary> 2699 /// Remove a particular item from this collection if found (only one copy). 2700 /// If an item was removed, report a binary copy of the actual item removed in 2701 /// the argument. 2702 /// </summary> 2703 /// <param name="item">The value to remove on input.</param> 2704 /// <param name="removeditem">The value removed.</param> 2705 /// <returns>True if the item was found (and removed).</returns> 2706 [Tested] Remove(T item, out T removeditem)2707 public virtual bool Remove(T item, out T removeditem) 2708 { 2709 updatecheck(); 2710 int i = 0; 2711 Node node; 2712 #if HASHINDEX 2713 if (!dictremove(item, out node)) 2714 #else 2715 node = fIFO ? startsentinel.next : endsentinel.prev; 2716 if (!(fIFO ? find(item, ref node, ref i) : dnif(item, ref node, ref i))) 2717 #endif 2718 { 2719 removeditem = default(T); 2720 return false; 2721 } 2722 removeditem = node.item; 2723 remove(node, i); 2724 (underlying ?? this).raiseForRemove(removeditem); 2725 return true; 2726 } 2727 2728 /// <summary> 2729 /// Remove all items in another collection from this one, taking multiplicities into account. 2730 /// <para>Always removes from the front of the list. 2731 /// </para> 2732 /// <para>The asymptotic running time complexity of this method is <code>O(n+m+v*log(v))</code>, 2733 /// where <code>n</code> is the size of this list, <code>m</code> is the size of the 2734 /// <code>items</code> collection and <code>v</code> is the number of views. 2735 /// The method will temporarily allocate memory of size <code>O(m+v)</code>. 2736 /// </para> 2737 /// </summary> 2738 /// <typeparam name="U"></typeparam> 2739 /// <param name="items">The items to remove.</param> 2740 [Tested] 2741 public virtual void RemoveAll<U>(SCG.IEnumerable<U> items) where U : T 2742 { 2743 updatecheck(); 2744 if (size == 0) 2745 return; 2746 RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(underlying ?? this); 2747 bool mustFire = raiseHandler.MustFire; 2748 #if HASHINDEX 2749 Node node; 2750 foreach (T item in items) 2751 if (dictremove(item, out node)) 2752 { 2753 if (mustFire) 2754 raiseHandler.Remove(node.item); 2755 remove(node, 118); 2756 } 2757 #else 2758 HashBag<T> toremove = new HashBag<T>(itemequalityComparer); 2759 toremove.AddAll(items); 2760 ViewHandler viewHandler = new ViewHandler(this); 2761 int index = 0, removed = 0, myoffset = Offset; 2762 Node node = startsentinel.next; 2763 while (node != endsentinel) 2764 { 2765 //pass by a stretch of nodes 2766 while (node != endsentinel && !toremove.Contains(node.item)) 2767 { 2768 node = node.next; 2769 index++; 2770 } 2771 viewHandler.skipEndpoints(removed, myoffset + index); 2772 //Remove a stretch of nodes 2773 Node localend = node.prev; //Latest node not to be removed 2774 while (node != endsentinel && toremove.Remove(node.item)) 2775 { 2776 if (mustFire) 2777 raiseHandler.Remove(node.item); 2778 removed++; 2779 node = node.next; 2780 index++; 2781 viewHandler.updateViewSizesAndCounts(removed, myoffset + index); 2782 } 2783 viewHandler.updateSentinels(myoffset + index, localend, node); 2784 localend.next = node; 2785 node.prev = localend; 2786 } 2787 index = underlying != null ? underlying.size + 1 - myoffset : size + 1 - myoffset; 2788 viewHandler.updateViewSizesAndCounts(removed, myoffset + index); 2789 size -= removed; 2790 if (underlying != null) 2791 underlying.size -= removed; 2792 #endif 2793 raiseHandler.Raise(); 2794 } 2795 2796 /// <summary> 2797 /// 2798 /// </summary> 2799 /// <param name="predicate"></param> RemoveAll(Fun<T, bool> predicate)2800 void RemoveAll(Fun<T, bool> predicate) 2801 { 2802 updatecheck(); 2803 if (size == 0) 2804 return; 2805 RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(underlying ?? this); 2806 bool mustFire = raiseHandler.MustFire; 2807 #if HASHINDEX 2808 { 2809 Node n = startsentinel.next; 2810 2811 while (n != endsentinel) 2812 { 2813 bool removeIt = predicate(n.item); 2814 updatecheck(); 2815 if (removeIt) 2816 { 2817 dict.Remove(n.item); 2818 remove(n, 119); 2819 if (mustFire) 2820 raiseHandler.Remove(n.item); 2821 } 2822 2823 n = n.next; 2824 } 2825 } 2826 #else 2827 ViewHandler viewHandler = new ViewHandler(this); 2828 int index = 0, removed = 0, myoffset = Offset; 2829 Node node = startsentinel.next; 2830 while (node != endsentinel) 2831 { 2832 //pass by a stretch of nodes 2833 while (node != endsentinel && !predicate(node.item)) 2834 { 2835 updatecheck(); 2836 node = node.next; 2837 index++; 2838 } 2839 updatecheck(); 2840 viewHandler.skipEndpoints(removed, myoffset + index); 2841 //Remove a stretch of nodes 2842 Node localend = node.prev; //Latest node not to be removed 2843 while (node != endsentinel && predicate(node.item)) 2844 { 2845 updatecheck(); 2846 if (mustFire) 2847 raiseHandler.Remove(node.item); 2848 removed++; 2849 node = node.next; 2850 index++; 2851 viewHandler.updateViewSizesAndCounts(removed, myoffset + index); 2852 } 2853 updatecheck(); 2854 viewHandler.updateSentinels(myoffset + index, localend, node); 2855 localend.next = node; 2856 node.prev = localend; 2857 } 2858 index = underlying != null ? underlying.size + 1 - myoffset : size + 1 - myoffset; 2859 viewHandler.updateViewSizesAndCounts(removed, myoffset + index); 2860 size -= removed; 2861 if (underlying != null) 2862 underlying.size -= removed; 2863 #endif 2864 raiseHandler.Raise(); 2865 } 2866 2867 /// <summary> 2868 /// Remove all items from this collection. 2869 /// </summary> 2870 [Tested] Clear()2871 public virtual void Clear() 2872 { 2873 updatecheck(); 2874 if (size == 0) 2875 return; 2876 int oldsize = size; 2877 #if HASHINDEX 2878 if (underlying == null) 2879 dict.Clear(); 2880 else 2881 foreach (T item in this) 2882 dict.Remove(item); 2883 #endif 2884 clear(); 2885 (underlying ?? this).raiseForRemoveInterval(Offset, oldsize); 2886 } 2887 clear()2888 void clear() 2889 { 2890 if (size == 0) 2891 return; 2892 #if HASHINDEX 2893 //TODO: mix with tag maintenance to only run through list once? 2894 ViewHandler viewHandler = new ViewHandler(this); 2895 if (viewHandler.viewCount > 0) 2896 { 2897 int removed = 0; 2898 Node n = startsentinel.next; 2899 viewHandler.skipEndpoints(0, n); 2900 while (n != endsentinel) 2901 { 2902 removed++; 2903 n = n.next; 2904 viewHandler.updateViewSizesAndCounts(removed, n); 2905 } 2906 viewHandler.updateSentinels(endsentinel, startsentinel, endsentinel); 2907 if (underlying != null) 2908 viewHandler.updateViewSizesAndCounts(removed, underlying.endsentinel); 2909 } 2910 #else 2911 fixViewsBeforeRemove(Offset, size, startsentinel.next, endsentinel.prev); 2912 #endif 2913 #if HASHINDEX 2914 if (underlying != null) 2915 { 2916 Node n = startsentinel.next; 2917 2918 while (n != endsentinel) 2919 { 2920 n.next.prev = startsentinel; 2921 startsentinel.next = n.next; 2922 removefromtaggroup(n); 2923 n = n.next; 2924 } 2925 } 2926 else 2927 taggroups = 0; 2928 #endif 2929 endsentinel.prev = startsentinel; 2930 startsentinel.next = endsentinel; 2931 if (underlying != null) 2932 underlying.size -= size; 2933 size = 0; 2934 } 2935 2936 /// <summary> 2937 /// Remove all items not in some other collection from this one, taking multiplicities into account. 2938 /// <para>The asymptotic running time complexity of this method is <code>O(n+m+v*log(v))</code>, 2939 /// where <code>n</code> is the size of this collection, <code>m</code> is the size of the 2940 /// <code>items</code> collection and <code>v</code> is the number of views. 2941 /// The method will temporarily allocate memory of size <code>O(m+v)</code>. The stated complexitiy 2942 /// holds under the assumption that the itemequalityComparer of this list is well-behaved. 2943 /// </para> 2944 /// </summary> 2945 /// <typeparam name="U"></typeparam> 2946 /// <param name="items">The items to retain.</param> 2947 [Tested] 2948 public virtual void RetainAll<U>(SCG.IEnumerable<U> items) where U : T 2949 { 2950 updatecheck(); 2951 if (size == 0) 2952 return; 2953 RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(underlying ?? this); 2954 bool mustFire = raiseHandler.MustFire; 2955 #if HASHINDEX 2956 /*if (underlying == null) 2957 { 2958 HashDictionary<T, Node> newdict = new HashDictionary<T, Node>(itemequalityComparer); 2959 foreach (T item in items) 2960 { 2961 Node node; 2962 2963 if (dict.Remove(item, out node)) 2964 newdict.Add(item, node); 2965 } 2966 foreach (KeyValuePair<T, Node> pair in dict) 2967 { 2968 Node n = pair.Value; 2969 fixViewsBeforeSingleRemove(n, 117); 2970 Node p = n.prev, s = n.next; s.prev = p; p.next = s; 2971 removefromtaggroup(n); 2972 } 2973 dict = newdict; 2974 size = dict.Count; 2975 //For a small number of items to retain it might be faster to 2976 //iterate through the list and splice out the chunks not needed 2977 } 2978 else*/ 2979 { 2980 HashSet<T> toremove = new HashSet<T>(itemequalityComparer); 2981 2982 foreach (T item in this) 2983 toremove.Add(item); 2984 2985 foreach (T item in items) 2986 toremove.Remove(item); 2987 2988 Node n = startsentinel.next; 2989 2990 while (n != endsentinel && toremove.Count > 0) 2991 { 2992 if (toremove.Contains(n.item)) 2993 { 2994 dict.Remove(n.item); 2995 remove(n, 119); 2996 if (mustFire) 2997 raiseHandler.Remove(n.item); 2998 } 2999 3000 n = n.next; 3001 } 3002 } 3003 #else 3004 HashBag<T> toretain = new HashBag<T>(itemequalityComparer); 3005 toretain.AddAll(items); 3006 ViewHandler viewHandler = new ViewHandler(this); 3007 int index = 0, removed = 0, myoffset = Offset; 3008 Node node = startsentinel.next; 3009 while (node != endsentinel) 3010 { 3011 //Skip a stretch of nodes 3012 while (node != endsentinel && toretain.Remove(node.item)) 3013 { 3014 node = node.next; 3015 index++; 3016 } 3017 viewHandler.skipEndpoints(removed, myoffset + index); 3018 //Remove a stretch of nodes 3019 Node localend = node.prev; //Latest node not to be removed 3020 while (node != endsentinel && !toretain.Contains(node.item)) 3021 { 3022 if (mustFire) 3023 raiseHandler.Remove(node.item); 3024 removed++; 3025 node = node.next; 3026 index++; 3027 viewHandler.updateViewSizesAndCounts(removed, myoffset + index); 3028 } 3029 viewHandler.updateSentinels(myoffset + index, localend, node); 3030 localend.next = node; 3031 node.prev = localend; 3032 } 3033 index = underlying != null ? underlying.size + 1 - myoffset : size + 1 - myoffset; 3034 viewHandler.updateViewSizesAndCounts(removed, myoffset + index); 3035 size -= removed; 3036 if (underlying != null) 3037 underlying.size -= removed; 3038 #endif 3039 raiseHandler.Raise(); 3040 } 3041 3042 /// <summary> 3043 /// 3044 /// </summary> 3045 /// <param name="predicate"></param> RetainAll(Fun<T, bool> predicate)3046 void RetainAll(Fun<T, bool> predicate) 3047 { 3048 updatecheck(); 3049 if (size == 0) 3050 return; 3051 RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(underlying ?? this); 3052 bool mustFire = raiseHandler.MustFire; 3053 #if HASHINDEX 3054 { 3055 Node n = startsentinel.next; 3056 3057 while (n != endsentinel) 3058 { 3059 bool removeIt = !predicate(n.item); 3060 updatecheck(); 3061 if (removeIt) 3062 { 3063 dict.Remove(n.item); 3064 remove(n, 119); 3065 if (mustFire) 3066 raiseHandler.Remove(n.item); 3067 } 3068 3069 n = n.next; 3070 } 3071 } 3072 #else 3073 ViewHandler viewHandler = new ViewHandler(this); 3074 int index = 0, removed = 0, myoffset = Offset; 3075 Node node = startsentinel.next; 3076 while (node != endsentinel) 3077 { 3078 //Skip a stretch of nodes 3079 while (node != endsentinel && predicate(node.item)) 3080 { 3081 updatecheck(); 3082 node = node.next; 3083 index++; 3084 } 3085 updatecheck(); 3086 viewHandler.skipEndpoints(removed, myoffset + index); 3087 //Remove a stretch of nodes 3088 Node localend = node.prev; //Latest node not to be removed 3089 while (node != endsentinel && !predicate(node.item)) 3090 { 3091 updatecheck(); 3092 if (mustFire) 3093 raiseHandler.Remove(node.item); 3094 removed++; 3095 node = node.next; 3096 index++; 3097 viewHandler.updateViewSizesAndCounts(removed, myoffset + index); 3098 } 3099 updatecheck(); 3100 viewHandler.updateSentinels(myoffset + index, localend, node); 3101 localend.next = node; 3102 node.prev = localend; 3103 } 3104 index = underlying != null ? underlying.size + 1 - myoffset : size + 1 - myoffset; 3105 viewHandler.updateViewSizesAndCounts(removed, myoffset + index); 3106 size -= removed; 3107 if (underlying != null) 3108 underlying.size -= removed; 3109 #endif 3110 raiseHandler.Raise(); 3111 } 3112 3113 /// <summary> 3114 /// Check if this collection contains all the values in another collection 3115 /// with respect to multiplicities. 3116 /// </summary> 3117 /// <param name="items">The </param> 3118 /// <typeparam name="U"></typeparam> 3119 /// <returns>True if all values in <code>items</code>is in this collection.</returns> 3120 [Tested] 3121 public virtual bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T 3122 { 3123 validitycheck(); 3124 #if HASHINDEX 3125 Node node; 3126 foreach (T item in items) 3127 if (!contains(item, out node)) 3128 return false; 3129 return true; 3130 #else 3131 HashBag<T> tocheck = new HashBag<T>(itemequalityComparer); 3132 tocheck.AddAll(items); 3133 if (tocheck.Count > size) 3134 return false; 3135 Node node = startsentinel.next; 3136 while (node != endsentinel) 3137 { 3138 tocheck.Remove(node.item); 3139 node = node.next; 3140 } 3141 return tocheck.IsEmpty; 3142 #endif 3143 } 3144 3145 3146 /// <summary> 3147 /// Create a new list consisting of the items of this list satisfying a 3148 /// certain predicate. 3149 /// </summary> 3150 /// <param name="filter">The filter delegate defining the predicate.</param> 3151 /// <returns>The new list.</returns> 3152 [Tested] FindAll(Fun<T, bool> filter)3153 public IList<T> FindAll(Fun<T, bool> filter) 3154 { 3155 validitycheck(); 3156 int stamp = this.stamp; 3157 LinkedList<T> retval = new LinkedList<T>(); 3158 Node cursor = startsentinel.next; 3159 Node mcursor = retval.startsentinel; 3160 #if HASHINDEX 3161 double tagdelta = int.MaxValue / (size + 1.0); 3162 int count = 1; 3163 TagGroup taggroup = new TagGroup(); 3164 retval.taggroups = 1; 3165 #endif 3166 while (cursor != endsentinel) 3167 { 3168 bool found = filter(cursor.item); 3169 modifycheck(stamp); 3170 if (found) 3171 { 3172 mcursor.next = new Node(cursor.item, mcursor, null); 3173 mcursor = mcursor.next; 3174 retval.size++; 3175 #if HASHINDEX 3176 retval.dict.Add(cursor.item, mcursor); 3177 mcursor.taggroup = taggroup; 3178 mcursor.tag = (int)(tagdelta * count++); 3179 #endif 3180 } 3181 cursor = cursor.next; 3182 } 3183 #if HASHINDEX 3184 if (retval.size > 0) 3185 { 3186 taggroup.count = retval.size; 3187 taggroup.first = retval.startsentinel.next; 3188 taggroup.last = mcursor; 3189 } 3190 #endif 3191 retval.endsentinel.prev = mcursor; 3192 mcursor.next = retval.endsentinel; 3193 return retval; 3194 } 3195 3196 3197 /// <summary> 3198 /// Count the number of items of the collection equal to a particular value. 3199 /// Returns 0 if and only if the value is not in the collection. 3200 /// </summary> 3201 /// <param name="item">The value to count.</param> 3202 /// <returns>The number of copies found.</returns> 3203 [Tested] ContainsCount(T item)3204 public virtual int ContainsCount(T item) 3205 { 3206 #if HASHINDEX 3207 return Contains(item) ? 1 : 0; 3208 #else 3209 validitycheck(); 3210 int retval = 0; 3211 Node node = startsentinel.next; 3212 while (node != endsentinel) 3213 { 3214 if (itemequalityComparer.Equals(node.item, item)) 3215 retval++; 3216 node = node.next; 3217 } 3218 return retval; 3219 #endif 3220 } 3221 3222 /// <summary> 3223 /// 3224 /// </summary> 3225 /// <returns></returns> UniqueItems()3226 public virtual ICollectionValue<T> UniqueItems() 3227 { 3228 #if HASHINDEX 3229 return this; 3230 #else 3231 HashBag<T> hashbag = new HashBag<T>(itemequalityComparer); 3232 hashbag.AddAll(this); 3233 return hashbag.UniqueItems(); 3234 #endif 3235 } 3236 3237 /// <summary> 3238 /// 3239 /// </summary> 3240 /// <returns></returns> ItemMultiplicities()3241 public virtual ICollectionValue<KeyValuePair<T, int>> ItemMultiplicities() 3242 { 3243 #if HASHINDEX 3244 return new MultiplicityOne<T>(this); 3245 #else 3246 HashBag<T> hashbag = new HashBag<T>(itemequalityComparer); 3247 hashbag.AddAll(this); 3248 return hashbag.ItemMultiplicities(); 3249 #endif 3250 } 3251 3252 /// <summary> 3253 /// Remove all items equivalent to a given value. 3254 /// <para>The asymptotic complexity of this method is <code>O(n+v*log(v))</code>, 3255 /// where <code>n</code> is the size of the collection and <code>v</code> 3256 /// is the number of views. 3257 /// </para> 3258 /// </summary> 3259 /// <param name="item">The value to remove.</param> 3260 [Tested] RemoveAllCopies(T item)3261 public virtual void RemoveAllCopies(T item) 3262 { 3263 #if HASHINDEX 3264 Remove(item); 3265 #else 3266 updatecheck(); 3267 if (size == 0) 3268 return; 3269 RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(underlying ?? this); 3270 bool mustFire = raiseHandler.MustFire; 3271 ViewHandler viewHandler = new ViewHandler(this); 3272 int index = 0, removed = 0, myoffset = Offset; 3273 // 3274 Node node = startsentinel.next; 3275 while (node != endsentinel) 3276 { 3277 //pass by a stretch of nodes 3278 while (node != endsentinel && !itemequalityComparer.Equals(node.item, item)) 3279 { 3280 node = node.next; 3281 index++; 3282 } 3283 viewHandler.skipEndpoints(removed, myoffset + index); 3284 //Remove a stretch of nodes 3285 Node localend = node.prev; //Latest node not to be removed 3286 while (node != endsentinel && itemequalityComparer.Equals(node.item, item)) 3287 { 3288 if (mustFire) 3289 raiseHandler.Remove(node.item); 3290 removed++; 3291 node = node.next; 3292 index++; 3293 viewHandler.updateViewSizesAndCounts(removed, myoffset + index); 3294 } 3295 viewHandler.updateSentinels(myoffset + index, localend, node); 3296 localend.next = node; 3297 node.prev = localend; 3298 } 3299 index = underlying != null ? underlying.size + 1 - myoffset : size + 1 - myoffset; 3300 viewHandler.updateViewSizesAndCounts(removed, myoffset + index); 3301 size -= removed; 3302 if (underlying != null) 3303 underlying.size -= removed; 3304 raiseHandler.Raise(); 3305 #endif 3306 } 3307 3308 #endregion 3309 3310 #region ICollectionValue<T> Members 3311 3312 /// <summary> 3313 /// 3314 /// </summary> 3315 /// <value>The number of items in this collection</value> 3316 [Tested] 3317 public override int Count { [Tested]get { validitycheck(); return size; } } 3318 3319 /// <summary> 3320 /// Choose some item of this collection. 3321 /// </summary> 3322 /// <exception cref="NoSuchItemException">if collection is empty.</exception> 3323 /// <returns></returns> 3324 [Tested] Choose()3325 public override T Choose() { return First; } 3326 3327 /// <summary> 3328 /// Create an enumerable, enumerating the items of this collection that satisfies 3329 /// a certain condition. 3330 /// </summary> 3331 /// <param name="filter">The T->bool filter delegate defining the condition</param> 3332 /// <returns>The filtered enumerable</returns> Filter(Fun<T, bool> filter)3333 public override SCG.IEnumerable<T> Filter(Fun<T, bool> filter) { validitycheck(); return base.Filter(filter); } 3334 3335 #endregion 3336 3337 #region IEnumerable<T> Members 3338 /// <summary> 3339 /// Create an enumerator for the collection 3340 /// </summary> 3341 /// <returns>The enumerator</returns> 3342 [Tested] GetEnumerator()3343 public override SCG.IEnumerator<T> GetEnumerator() 3344 { 3345 validitycheck(); 3346 Node cursor = startsentinel.next; 3347 int enumeratorstamp = underlying != null ? underlying.stamp : this.stamp; 3348 3349 while (cursor != endsentinel) 3350 { 3351 modifycheck(enumeratorstamp); 3352 yield return cursor.item; 3353 cursor = cursor.next; 3354 } 3355 } 3356 3357 #endregion 3358 3359 #region IExtensible<T> Members 3360 /// <summary> 3361 /// Add an item to this collection if possible. 3362 /// </summary> 3363 /// <param name="item">The item to add.</param> 3364 /// <returns>True.</returns> 3365 [Tested] Add(T item)3366 public virtual bool Add(T item) 3367 { 3368 updatecheck(); 3369 #if HASHINDEX 3370 Node node = new Node(item); 3371 if (!dict.FindOrAdd(item, ref node)) 3372 { 3373 insertNode(true, endsentinel, node); 3374 (underlying ?? this).raiseForAdd(item); 3375 return true; 3376 } 3377 return false; 3378 #else 3379 insert(size, endsentinel, item); 3380 (underlying ?? this).raiseForAdd(item); 3381 return true; 3382 #endif 3383 } 3384 3385 /// <summary> 3386 /// 3387 /// </summary> 3388 /// <value>True since this collection has bag semantics.</value> 3389 [Tested] 3390 public virtual bool AllowsDuplicates 3391 { 3392 [Tested] 3393 get 3394 { 3395 #if HASHINDEX 3396 return false; 3397 #else 3398 return true; 3399 #endif 3400 } 3401 } 3402 3403 /// <summary> 3404 /// By convention this is true for any collection with set semantics. 3405 /// </summary> 3406 /// <value>True if only one representative of a group of equal items 3407 /// is kept in the collection together with the total count.</value> 3408 public virtual bool DuplicatesByCounting 3409 { 3410 get 3411 { 3412 #if HASHINDEX 3413 return true; 3414 #else 3415 return false; 3416 #endif 3417 } 3418 } 3419 3420 /// <summary> 3421 /// Add the elements from another collection with a more specialized item type 3422 /// to this collection. 3423 /// </summary> 3424 /// <typeparam name="U">The type of items to add</typeparam> 3425 /// <param name="items">The items to add</param> 3426 [Tested] 3427 public virtual void AddAll<U>(SCG.IEnumerable<U> items) where U : T 3428 { 3429 #if HASHINDEX 3430 updatecheck(); 3431 int added = 0; 3432 Node pred = endsentinel.prev; 3433 foreach (U item in items) 3434 { 3435 Node node = new Node(item); 3436 if (!dict.FindOrAdd(item, ref node)) 3437 { 3438 insertNode(false, endsentinel, node); 3439 added++; 3440 } 3441 } 3442 if (added > 0) 3443 { 3444 fixViewsAfterInsert(endsentinel, pred, added, 0); 3445 raiseForInsertAll(pred, size - added, added, false); 3446 } 3447 #else 3448 insertAll(size, items, false); 3449 #endif 3450 } 3451 3452 #endregion 3453 3454 #if HASHINDEX 3455 #else 3456 #region IStack<T> Members 3457 3458 /// <summary> 3459 /// Push an item to the top of the stack. 3460 /// </summary> 3461 /// <param name="item">The item</param> 3462 [Tested] Push(T item)3463 public void Push(T item) 3464 { 3465 InsertLast(item); 3466 } 3467 3468 /// <summary> 3469 /// Pop the item at the top of the stack from the stack. 3470 /// </summary> 3471 /// <returns>The popped item.</returns> 3472 [Tested] Pop()3473 public T Pop() 3474 { 3475 return RemoveLast(); 3476 } 3477 3478 #endregion 3479 3480 #region IQueue<T> Members 3481 3482 /// <summary> 3483 /// Enqueue an item at the back of the queue. 3484 /// </summary> 3485 /// <param name="item">The item</param> 3486 [Tested] Enqueue(T item)3487 public virtual void Enqueue(T item) 3488 { 3489 InsertLast(item); 3490 } 3491 3492 /// <summary> 3493 /// Dequeue an item from the front of the queue. 3494 /// </summary> 3495 /// <returns>The item</returns> 3496 [Tested] Dequeue()3497 public virtual T Dequeue() 3498 { 3499 return RemoveFirst(); 3500 } 3501 #endregion 3502 #endif 3503 3504 #region Diagnostic 3505 checkViews()3506 private bool checkViews() 3507 { 3508 if (underlying != null) 3509 throw new InternalException(System.Reflection.MethodInfo.GetCurrentMethod() + " called on a view"); 3510 if (views == null) 3511 return true; 3512 bool retval = true; 3513 3514 Node[] nodes = new Node[size + 2]; 3515 int i = 0; 3516 Node n = startsentinel; 3517 while (n != null) 3518 { 3519 nodes[i++] = n; 3520 n = n.next; 3521 } 3522 //Console.WriteLine("###"); 3523 foreach (LinkedList<T> view in views) 3524 { 3525 if (!view.isValid) 3526 { 3527 Console.WriteLine("Invalid view(hash {0}, offset {1}, size {2})", 3528 view.GetHashCode(), view.offset, view.size); 3529 retval = false; 3530 continue; 3531 } 3532 if (view.Offset > size || view.Offset < 0) 3533 { 3534 Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), Offset > underlying.size ({2})", 3535 view.GetHashCode(), view.offset, view.size, size); 3536 retval = false; 3537 } 3538 else if (view.startsentinel != nodes[view.Offset]) 3539 { 3540 Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), startsentinel {3} should be {4}", 3541 view.GetHashCode(), view.offset, view.size, 3542 view.startsentinel + " " + view.startsentinel.GetHashCode(), 3543 nodes[view.Offset] + " " + nodes[view.Offset].GetHashCode()); 3544 retval = false; 3545 } 3546 if (view.Offset + view.size > size || view.Offset + view.size < 0) 3547 { 3548 Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), end index > underlying.size ({3})", 3549 view.GetHashCode(), view.offset, view.size, size); 3550 retval = false; 3551 } 3552 else if (view.endsentinel != nodes[view.Offset + view.size + 1]) 3553 { 3554 Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), endsentinel {3} should be {4}", 3555 view.GetHashCode(), view.offset, view.size, 3556 view.endsentinel + " " + view.endsentinel.GetHashCode(), 3557 nodes[view.Offset + view.size + 1] + " " + nodes[view.Offset + view.size + 1].GetHashCode()); 3558 retval = false; 3559 } 3560 if (view.views != views) 3561 { 3562 Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), wrong views list {3} <> {4}", 3563 view.GetHashCode(), view.offset, view.size, view.views.GetHashCode(), views.GetHashCode()); 3564 retval = false; 3565 } 3566 if (view.underlying != this) 3567 { 3568 Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), wrong underlying {3} <> this {4}", 3569 view.GetHashCode(), view.offset, view.size, view.underlying.GetHashCode(), GetHashCode()); 3570 retval = false; 3571 } 3572 if (view.stamp != stamp) 3573 { 3574 //Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), wrong stamp view:{2} underlying: {3}", view.GetHashCode(),view.offset, view.size, view.stamp, stamp); 3575 //retval = false; 3576 } 3577 } 3578 return retval; 3579 } 3580 zeitem(Node node)3581 string zeitem(Node node) 3582 { 3583 return node == null ? "(null node)" : node.item.ToString(); 3584 } 3585 3586 /// <summary> 3587 /// Check the sanity of this list 3588 /// </summary> 3589 /// <returns>true if sane</returns> 3590 [Tested] Check()3591 public virtual bool Check() 3592 { 3593 bool retval = true; 3594 3595 /*if (underlying != null && underlying.stamp != stamp) 3596 { 3597 Console.WriteLine("underlying != null && underlying.stamp({0}) != stamp({1})", underlying.stamp, stamp); 3598 retval = false; 3599 }*/ 3600 3601 if (underlying != null) 3602 { 3603 //TODO: check that this view is included in viewsEndpoints tree 3604 return underlying.Check(); 3605 } 3606 3607 if (startsentinel == null) 3608 { 3609 Console.WriteLine("startsentinel == null"); 3610 retval = false; 3611 } 3612 3613 if (endsentinel == null) 3614 { 3615 Console.WriteLine("endsentinel == null"); 3616 retval = false; 3617 } 3618 3619 if (size == 0) 3620 { 3621 if (startsentinel != null && startsentinel.next != endsentinel) 3622 { 3623 Console.WriteLine("size == 0 but startsentinel.next != endsentinel"); 3624 retval = false; 3625 } 3626 3627 if (endsentinel != null && endsentinel.prev != startsentinel) 3628 { 3629 Console.WriteLine("size == 0 but endsentinel.prev != startsentinel"); 3630 retval = false; 3631 } 3632 } 3633 3634 if (startsentinel == null) 3635 { 3636 Console.WriteLine("NULL startsentinel"); 3637 return retval; 3638 } 3639 3640 int count = 0; 3641 Node node = startsentinel.next, prev = startsentinel; 3642 #if HASHINDEX 3643 int taggroupsize = 0, oldtaggroupsize = losize + 1, seentaggroups = 0; 3644 TagGroup oldtg = null; 3645 3646 if (underlying == null) 3647 { 3648 TagGroup tg = startsentinel.taggroup; 3649 3650 if (tg.count != 0 || tg.first != null || tg.last != null || tg.tag != int.MinValue) 3651 { 3652 Console.WriteLine("Bad startsentinel tag group: {0}", tg); 3653 retval = false; 3654 } 3655 3656 tg = endsentinel.taggroup; 3657 if (tg.count != 0 || tg.first != null || tg.last != null || tg.tag != int.MaxValue) 3658 { 3659 Console.WriteLine("Bad endsentinel tag group: {0}", tg); 3660 retval = false; 3661 } 3662 } 3663 #endif 3664 while (node != endsentinel) 3665 { 3666 count++; 3667 if (node.prev != prev) 3668 { 3669 Console.WriteLine("Bad backpointer at node {0}", count); 3670 retval = false; 3671 } 3672 #if HASHINDEX 3673 if (underlying == null) 3674 { 3675 if (!node.prev.precedes(node)) 3676 { 3677 Console.WriteLine("node.prev.tag ({0}, {1}) >= node.tag ({2}, {3}) at index={4} item={5} ", node.prev.taggroup.tag, node.prev.tag, node.taggroup.tag, node.tag, count, node.item); 3678 retval = false; 3679 } 3680 3681 if (node.taggroup != oldtg) 3682 { 3683 3684 if (node.taggroup.first != node) 3685 { 3686 string ntfi = zeitem(node.taggroup.first); 3687 Console.WriteLine("Bad first pointer in taggroup: node.taggroup.first.item ({0}), node.item ({1}) at index={2} item={3}", ntfi, node.item, count, node.item); 3688 retval = false; 3689 } 3690 3691 if (oldtg != null) 3692 { 3693 if (oldtg.count != taggroupsize) 3694 { 3695 Console.WriteLine("Bad taggroupsize: oldtg.count ({0}) != taggroupsize ({1}) at index={2} item={3}", oldtg.count, taggroupsize, count, node.item); 3696 retval = false; 3697 } 3698 3699 if (oldtaggroupsize <= losize && taggroupsize <= losize) 3700 { 3701 Console.WriteLine("Two small taggroups in a row: oldtaggroupsize ({0}), taggroupsize ({1}) at index={2} item={3}", oldtaggroupsize, taggroupsize, count, node.item); 3702 retval = false; 3703 } 3704 3705 if (node.taggroup.tag <= oldtg.tag) 3706 { 3707 Console.WriteLine("Taggroup tags not strictly increasing: oldtaggrouptag ({0}), taggrouptag ({1}) at index={2} item={3}", oldtg.tag, node.taggroup.tag, count, node.item); 3708 retval = false; 3709 } 3710 3711 if (oldtg.last != node.prev) 3712 { 3713 Console.WriteLine("Bad last pointer in taggroup: oldtg.last.item ({0}), node.prev.item ({1}) at index={2} item={3}", oldtg.last.item, node.prev.item, count, node.item); 3714 retval = false; 3715 } 3716 3717 oldtaggroupsize = taggroupsize; 3718 } 3719 3720 seentaggroups++; 3721 oldtg = node.taggroup; 3722 taggroupsize = 1; 3723 } 3724 else 3725 { 3726 taggroupsize++; 3727 } 3728 } 3729 3730 #endif 3731 prev = node; 3732 node = node.next; 3733 if (node == null) 3734 { 3735 Console.WriteLine("Null next pointer at node {0}", count); 3736 return false; 3737 } 3738 } 3739 3740 #if HASHINDEX 3741 if (underlying == null && size == 0 && taggroups != 0) 3742 { 3743 Console.WriteLine("Bad taggroups for empty list: size={0} taggroups={1}", size, taggroups); 3744 retval = false; 3745 } 3746 if (underlying == null && size > 0) 3747 { 3748 oldtg = node.prev.taggroup; 3749 if (oldtg != null) 3750 { 3751 if (oldtg.count != taggroupsize) 3752 { 3753 Console.WriteLine("Bad taggroupsize: oldtg.count ({0}) != taggroupsize ({1}) at index={2} item={3}", oldtg.count, taggroupsize, count, node.item); 3754 retval = false; 3755 } 3756 3757 if (oldtaggroupsize <= losize && taggroupsize <= losize) 3758 { 3759 Console.WriteLine("Two small taggroups in a row: oldtaggroupsize ({0}), taggroupsize ({1}) at index={2} item={3}", oldtaggroupsize, taggroupsize, count, node.item); 3760 retval = false; 3761 } 3762 3763 if (node.taggroup.tag <= oldtg.tag) 3764 { 3765 Console.WriteLine("Taggroup tags not strictly increasing: oldtaggrouptag ({0}), taggrouptag ({1}) at index={2} item={3}", oldtg.tag, node.taggroup.tag, count, node.item); 3766 retval = false; 3767 } 3768 3769 if (oldtg.last != node.prev) 3770 { 3771 Console.WriteLine("Bad last pointer in taggroup: oldtg.last.item ({0}), node.prev.item ({1}) at index={2} item={3}", zeitem(oldtg.last), zeitem(node.prev), count, node.item); 3772 retval = false; 3773 } 3774 } 3775 3776 if (seentaggroups != taggroups) 3777 { 3778 Console.WriteLine("seentaggroups ({0}) != taggroups ({1}) (at size {2})", seentaggroups, taggroups, size); 3779 retval = false; 3780 } 3781 } 3782 #endif 3783 if (count != size) 3784 { 3785 Console.WriteLine("size={0} but enumeration gives {1} nodes ", size, count); 3786 retval = false; 3787 } 3788 3789 retval = checkViews() && retval; 3790 3791 #if HASHINDEX 3792 if (!retval) 3793 return false; 3794 if (underlying == null) 3795 { 3796 if (size != dict.Count) 3797 { 3798 Console.WriteLine("list.size ({0}) != dict.Count ({1})", size, dict.Count); 3799 retval = false; 3800 } 3801 Node n = startsentinel.next, n2; 3802 while (n != endsentinel) 3803 { 3804 if (!dict.Find(n.item, out n2)) 3805 { 3806 Console.WriteLine("Item in list but not dict: {0}", n.item); 3807 retval = false; 3808 } 3809 else if (n != n2) 3810 { 3811 Console.WriteLine("Wrong node in dict for item: {0}", n.item); 3812 retval = false; 3813 } 3814 n = n.next; 3815 } 3816 } 3817 #endif 3818 return retval; 3819 } 3820 #endregion 3821 3822 #region ICloneable Members 3823 3824 /// <summary> 3825 /// Make a shallow copy of this LinkedList. 3826 /// </summary> 3827 /// <returns></returns> Clone()3828 public virtual object Clone() 3829 { 3830 LinkedList<T> clone = new LinkedList<T>(itemequalityComparer); 3831 clone.AddAll(this); 3832 return clone; 3833 } 3834 3835 #endregion 3836 3837 #region System.Collections.Generic.IList<T> Members 3838 RemoveAt(int index)3839 void System.Collections.Generic.IList<T>.RemoveAt(int index) 3840 { 3841 RemoveAt(index); 3842 } 3843 Add(T item)3844 void System.Collections.Generic.ICollection<T>.Add(T item) 3845 { 3846 Add(item); 3847 } 3848 3849 #endregion 3850 3851 #region System.Collections.ICollection Members 3852 3853 bool System.Collections.ICollection.IsSynchronized 3854 { 3855 get { return false; } 3856 } 3857 3858 [Obsolete] 3859 Object System.Collections.ICollection.SyncRoot 3860 { 3861 // Presumably safe to use the startsentinel (of type Node, always != null) as SyncRoot 3862 // since the class Node is private. 3863 get { return underlying != null ? ((System.Collections.ICollection)underlying).SyncRoot : startsentinel; } 3864 } 3865 System.Collections.ICollection.CopyTo(Array arr, int index)3866 void System.Collections.ICollection.CopyTo(Array arr, int index) 3867 { 3868 if (index < 0 || index + Count > arr.Length) 3869 throw new ArgumentOutOfRangeException(); 3870 3871 foreach (T item in this) 3872 arr.SetValue(item, index++); 3873 } 3874 3875 #endregion 3876 3877 #region System.Collections.IList Members 3878 3879 Object System.Collections.IList.this[int index] 3880 { 3881 get { return this[index]; } 3882 set { this[index] = (T)value; } 3883 } 3884 System.Collections.IList.Add(Object o)3885 int System.Collections.IList.Add(Object o) 3886 { 3887 bool added = Add((T)o); 3888 // What position to report if item not added? SC.IList.Add doesn't say 3889 return added ? Count-1 : -1; 3890 } 3891 System.Collections.IList.Contains(Object o)3892 bool System.Collections.IList.Contains(Object o) 3893 { 3894 return Contains((T)o); 3895 } 3896 System.Collections.IList.IndexOf(Object o)3897 int System.Collections.IList.IndexOf(Object o) 3898 { 3899 return Math.Max(-1, IndexOf((T)o)); 3900 } 3901 System.Collections.IList.Insert(int index, Object o)3902 void System.Collections.IList.Insert(int index, Object o) 3903 { 3904 Insert(index, (T)o); 3905 } 3906 System.Collections.IList.Remove(Object o)3907 void System.Collections.IList.Remove(Object o) 3908 { 3909 Remove((T)o); 3910 } 3911 System.Collections.IList.RemoveAt(int index)3912 void System.Collections.IList.RemoveAt(int index) 3913 { 3914 RemoveAt(index); 3915 } 3916 3917 #endregion 3918 } 3919 }