3 Copyright (c) 2003-2004 Niels Kokholm <kokholm@itu.dk> and Peter Sestoft <sestoft@dina.kvl.dk>
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
26 using System
.Diagnostics
;
27 using MSG
=System
.Collections
.Generic
;
32 /// A list collection class based on a doubly linked list data structure.
34 public class LinkedList
<T
>: SequencedBase
<T
>, IList
<T
>
38 /// IExtensible.Add(T) always does AddLast(T), fIFO determines
39 /// if T Remove() does RemoveFirst() or RemoveLast()
43 #if LISTORDER || EXTLISTORDER
45 /// True if we maintain tags for node ordering (false for plain linked list, true for hashed linked list).
47 protected bool maintaintags
= false;
54 //Invariant: startsentinel != null && endsentinel != null
55 //If size==0: startsentinel.next == endsentinel && endsentinel.prev == startsentinel
56 //Else: startsentinel.next == First && endsentinel.prev == Last)
58 /// Node to the left of first node
60 protected Node startsentinel
;
62 /// Node to the right of last node
64 protected Node endsentinel
;
66 /// Offset of this view in underlying list
71 /// underlying list of theis view (or null)
73 protected LinkedList
<T
> underlying
;
79 bool equals(T i1
, T i2
) { return itemhasher.Equals(i1, i2); }
83 /// Check if it is valid to perform updates and increment stamp.
84 /// <exception cref="InvalidOperationException"/> if check fails.
85 /// <br/>This method should be called at the start of any public modifying methods.
87 protected override void updatecheck()
91 if (underlying
!= null)
97 /// Check if we are a view that the underlyinglist has only been updated through us.
98 /// <exception cref="InvalidOperationException"/> if check fails.
100 /// This method should be called from enumerators etc to guard against
101 /// modification of the base collection.
103 protected void modifycheck()
105 if (underlying
!= null && stamp
!= underlying
.stamp
)
106 throw new InvalidOperationException("underlying list was modified");
111 /// Check that the list has not been updated since a particular time.
112 /// <exception cref="InvalidOperationException"/> if check fails.
114 /// <param name="stamp">The stamp indicating the time.</param>
115 protected override void modifycheck(int stamp
)
118 if (this.stamp
!= stamp
)
119 throw new InvalidOperationException("Collection was modified");
123 Node
insert(Node succ
, T item
)
125 Node newnode
= new Node(item
, succ
.prev
, succ
);
127 succ
.prev
.next
= newnode
;
130 if (underlying
!= null)
134 //TODO: replace with Debug.Assert(!maintaintags)
147 /// Insert a Node before another one. Unchecked internal version.
149 /// <param name="succ">The successor to be</param>
150 /// <param name="newnode">Node to insert</param>
151 protected void insertNode(Node succ
, Node newnode
)
154 newnode
.prev
= succ
.prev
;
155 succ
.prev
.next
= newnode
;
158 if (underlying
!= null)
172 /// Remove a node. Unchecked internal version.
174 /// <param name="node">Node to remove</param>
175 /// <returns>The item of the removed node</returns>
176 protected T
remove(Node node
)
178 node
.prev
.next
= node
.next
;
179 node
.next
.prev
= node
.prev
;
181 if (underlying
!= null)
185 removefromtaggroup(node
);
193 //const int MaxTag = int.MaxValue;
195 protected void settag(Node node
)
197 //Note: the (global) sentinels have tag==0 and all other tags are positive.
198 Node pred
= node
.prev
, succ
= node
.next
;
199 if (pred
.tag
< succ
.tag
- 1)
202 //node.tag-pred.tag = (succ.tag-pred.tag) / 2 > 0
203 //succ.tag-node.tag = succ.tag-pred.tag - (succ.tag-pred.tag) / 2 > 0
204 node
.tag
= pred
.tag
+ (succ
.tag
-pred
.tag
) / 2;
208 if (succ
.tag
== 0 && pred
.tag
< int.MaxValue
)
211 //node.tag-pred.tag = 1 + (int.MaxValue-pred.tag) / 2 > 0
212 //node.tag <=int.MaxValue
213 node
.tag
= pred
.tag
+ 1 + (int.MaxValue
- pred
.tag
) / 2;
217 node
.tag
= node
.prev
.tag
;
218 redistributetags(node
);
221 private void redistributetags(Node node
)
223 Node pred
= node
, succ
= node
;
225 //Node start = underlying == null ? startsentinel : underlying.startsentinel;
226 //Node end = underlying == null ? endsentinel : underlying.endsentinel;
227 double limit
= 1, bigt
= Math
.Pow(size
, 1.0/29);//?????
228 int bits
= 1, count
= 1, lowmask
= 0, himask
= 0, target
= 0;
233 lowmask
= (1 << bits
) - 1;
235 target
= node
.tag
& himask
;
236 while (pred
.prev
.tag
> 0 && (pred
.prev
.tag
& himask
) == target
)
237 { count++; pred = pred.prev; }
239 while (succ
.next
.tag
> 0 && (succ
.next
.tag
& himask
) == target
)
240 { count++; succ = succ.next; }
243 } while (count
> limit
);
246 //Console.WriteLine("Redistributing {0} tags at {1} bits around item {2}", count, bits, node.item);
248 int delta
= lowmask
/ (count
+1);
250 for (int i
= 1; i
<= count
; i
++)
252 pred
.tag
= target
+ i
* delta
;
253 //Console.Write("({0} -> {1})", pred.item, pred.tag);
256 //Console.WriteLine("{0}:{1}:{2}/",count,size,Check());
259 const int wordsize
= 32;
261 const int lobits
= 3;
263 const int hibits
= lobits
+ 1;
265 const int losize
= 1 << lobits
;
267 const int hisize
= 1 << hibits
;
269 const int logwordsize
= 5;
275 /// <param name="pred"></param>
276 /// <param name="succ"></param>
277 /// <param name="lowbound"></param>
278 /// <param name="highbound"></param>
279 /// <returns></returns>
280 protected TagGroup
gettaggroup(Node pred
, Node succ
, out int lowbound
, out int highbound
)
282 TagGroup predgroup
= pred
.taggroup
, succgroup
= succ
.taggroup
;
284 if (predgroup
== succgroup
)
286 lowbound
= pred
.tag
+ 1;
287 highbound
= succ
.tag
- 1;
290 else if (predgroup
.first
!= null)
292 lowbound
= pred
.tag
+ 1;
293 highbound
= int.MaxValue
;
296 else if (succgroup
.first
!= null)
298 lowbound
= int.MinValue
;
299 highbound
= succ
.tag
- 1;
304 lowbound
= int.MinValue
;
305 highbound
= int.MaxValue
;
306 return new TagGroup();
312 /// Put a tag on a node (already inserted in the list). Split taggroups and renumber as
315 /// <param name="node">The node to tag</param>
316 protected void settag(Node node
)
318 Node pred
= node
.prev
, succ
= node
.next
;
319 TagGroup predgroup
= pred
.taggroup
, succgroup
= succ
.taggroup
;
321 if (predgroup
== succgroup
)
323 node
.taggroup
= predgroup
;
325 if (pred
.tag
+ 1 == succ
.tag
)
326 splittaggroup(predgroup
);
328 node
.tag
= (pred
.tag
+ 1) / 2 + (succ
.tag
- 1) / 2;
330 else if (predgroup
.first
!= null)
332 node
.taggroup
= predgroup
;
333 predgroup
.last
= node
;
335 if (pred
.tag
== int.MaxValue
)
336 splittaggroup(predgroup
);
338 node
.tag
= pred
.tag
/ 2 + int.MaxValue
/ 2 + 1;
340 else if (succgroup
.first
!= null)
342 node
.taggroup
= succgroup
;
343 succgroup
.first
= node
;
345 if (succ
.tag
== int.MinValue
)
346 splittaggroup(node
.taggroup
);
348 node
.tag
= int.MinValue
/ 2 + (succ
.tag
- 1) / 2;
352 Debug
.Assert(taggroups
== 0);
354 TagGroup newgroup
= new TagGroup();
357 node
.taggroup
= newgroup
;
358 newgroup
.first
= newgroup
.last
= node
;
366 /// Remove a node from its taggroup.
367 /// <br/> When this is called, node must already have been removed from the underlying list
369 /// <param name="node">The node to remove</param>
370 protected void removefromtaggroup(Node node
)
373 TagGroup taggroup
= node
.taggroup
;
375 if (--taggroup
.count
== 0)
381 if (node
== taggroup
.first
)
382 taggroup
.first
= node
.next
;
384 if (node
== taggroup
.last
)
385 taggroup
.last
= node
.prev
;
387 //node.taggroup = null;
388 if (taggroup
.count
!= losize
)
393 if ((otg
= taggroup
.first
.prev
.taggroup
).count
<= losize
)
394 taggroup
.first
= otg
.first
;
395 else if ((otg
= taggroup
.last
.next
.taggroup
).count
<= losize
)
396 taggroup
.last
= otg
.last
;
402 for (int i
= 0, length
= otg
.count
; i
< length
; i
++)
404 n
.taggroup
= taggroup
;
408 taggroup
.count
+= otg
.count
;
412 const int ofs
= wordsize
- hibits
;
414 for (int i
= 0, count
= taggroup
.count
; i
< count
; i
++)
416 n
.tag
= (i
- losize
) << ofs
; //(i-8)<<28
423 /// Split a tag group to make rom for more tags.
425 /// <param name="taggroup">The tag group</param>
426 protected void splittaggroup(TagGroup taggroup
)
428 Node n
= taggroup
.first
;
429 int ptgt
= taggroup
.first
.prev
.taggroup
.tag
;
430 int ntgt
= taggroup
.last
.next
.taggroup
.tag
;
432 Debug
.Assert(ptgt
+ 1 <= ntgt
- 1);
434 int ofs
= wordsize
- hibits
;
435 int newtgs
= taggroup
.count
/ hisize
- 1;
436 int tgtdelta
= (int)((ntgt
+ 0.0 - ptgt
) / (newtgs
+ 2)), tgtag
= ptgt
;
438 tgtdelta
= tgtdelta
== 0 ? 1 : tgtdelta
;
439 for (int j
= 0; j
< newtgs
; j
++)
441 TagGroup newtaggroup
= new TagGroup();
443 newtaggroup
.tag
= (tgtag
= tgtag
>= ntgt
- tgtdelta
? ntgt
: tgtag
+ tgtdelta
);
444 newtaggroup
.first
= n
;
445 newtaggroup
.count
= hisize
;
446 for (int i
= 0; i
< hisize
; i
++)
448 n
.taggroup
= newtaggroup
;
449 n
.tag
= (i
- losize
) << ofs
; //(i-8)<<28
453 newtaggroup
.last
= n
.prev
;
456 int rest
= taggroup
.count
- hisize
* newtgs
;
459 taggroup
.count
= rest
;
460 taggroup
.tag
= (tgtag
= tgtag
>= ntgt
- tgtdelta
? ntgt
: tgtag
+ tgtdelta
); ofs
--;
461 for (int i
= 0; i
< rest
; i
++)
463 n
.tag
= (i
- hisize
) << ofs
; //(i-16)<<27
467 taggroup
.last
= n
.prev
;
470 redistributetaggroups(taggroup
);
474 private void redistributetaggroups(TagGroup taggroup
)
476 TagGroup pred
= taggroup
, succ
= taggroup
, tmp
;
477 double limit
= 1, bigt
= Math
.Pow(taggroups
, 1.0 / 30);//?????
478 int bits
= 1, count
= 1, lowmask
= 0, himask
= 0, target
= 0;
483 lowmask
= (1 << bits
) - 1;
485 target
= taggroup
.tag
& himask
;
486 while ((tmp
= pred
.first
.prev
.taggroup
).first
!= null && (tmp
.tag
& himask
) == target
)
487 { count++; pred = tmp; }
489 while ((tmp
= succ
.last
.next
.taggroup
).last
!= null && (tmp
.tag
& himask
) == target
)
490 { count++; succ = tmp; }
493 } while (count
> limit
);
496 int lob
= pred
.first
.prev
.taggroup
.tag
, upb
= succ
.last
.next
.taggroup
.tag
;
497 int delta
= upb
/ (count
+ 1) - lob
/ (count
+ 1);
499 Debug
.Assert(delta
> 0);
500 for (int i
= 0; i
< count
; i
++)
502 pred
.tag
= lob
+ (i
+ 1) * delta
;
503 pred
= pred
.last
.next
.taggroup
;
512 /// Create a linked list with en external item hasher
514 /// <param name="itemhasher">The external hasher</param>
515 public LinkedList(IHasher
<T
> itemhasher
)
517 this.itemhasher
= itemhasher
;
519 startsentinel
= new Node(default(T
));
520 endsentinel
= new Node(default(T
));
521 startsentinel
.next
= endsentinel
;
522 endsentinel
.prev
= startsentinel
;
524 //It isused that these are different:
525 startsentinel
.taggroup
= new TagGroup();
526 startsentinel
.taggroup
.tag
= int.MinValue
;
527 startsentinel
.taggroup
.count
= 0;
528 endsentinel
.taggroup
= new TagGroup();
529 endsentinel
.taggroup
.tag
= int.MaxValue
;
530 endsentinel
.taggroup
.count
= 0;
532 startsentinel
= endsentinel
= new Node(default(T
));
533 startsentinel
.next
= endsentinel
.prev
= startsentinel
;
540 /// Create a linked list with the nmatural item hasher
542 public LinkedList() : this(HasherBuilder
.ByPrototype
<T
>.Examine()) { }
546 #region Nested classes
549 /// An individual cell in the linked list
554 /// Previous-node reference
559 /// Next-node reference
572 internal TagGroup taggroup
;
575 internal bool precedes(Node that
)
577 //Debug.Assert(taggroup != null, "taggroup field null");
578 //Debug.Assert(that.taggroup != null, "that.taggroup field null");
579 int t1
= taggroup
.tag
;
580 int t2
= that
.taggroup
.tag
;
582 return t1
< t2
? true : t1
> t2
? false : tag
< that
.tag
;
588 /// <param name="item">Item to insert</param>
597 /// Create node, specifying predecessor and successor
599 /// <param name="item"></param>
600 /// <param name="prev"></param>
601 /// <param name="next"></param>
603 public Node(T item
, Node prev
, Node next
)
605 this.item
= item
; this.prev
= prev
; this.next
= next
;
610 /// Pretty print node
612 /// <returns>Formatted node</returns>
613 public override string ToString()
615 #if LISTORDER || EXTLISTORDER
616 return String
.Format("Node: (item={0}, tag={1})", item
, tag
);
618 return String
.Format("Node(item={0})", item
);
625 /// A group of nodes with the same high tag. Purpose is to be
626 /// able to tell the sequence order of two nodes without having to scan through
629 protected class TagGroup
631 internal int tag
, count
;
633 internal Node first
, last
;
637 /// Pretty print a tag group
639 /// <returns>Formatted tag group</returns>
640 public override string ToString()
641 { return String.Format("TagGroup(tag={0}
, cnt
={1}
, fst
={2}
, lst
={3}
)", tag, count, first, last); }
647 #region Range nested class
649 class Range: CollectionValueBase<T>, IDirectedCollectionValue<T>
651 int start, count, stamp;
658 internal Range(LinkedList<T> list, int start, int count, bool forwards)
660 this.list = list;this.stamp = list.stamp;
661 this.start = start;this.count = count;this.forwards = forwards;
666 public override int Count { [Tested]get { list.modifycheck(stamp); return count; } }
669 public override Speed CountSpeed { get { list.modifycheck(stamp); return Speed.Constant; } }
672 public override MSG.IEnumerator<T> GetEnumerator()
676 list.modifycheck(stamp);
680 Node cursor = forwards ? list.get(start) : list.get(start + count - 1);
682 yield return cursor.item;
685 cursor = forwards ? cursor.next : cursor.prev;
686 list.modifycheck(stamp);
687 yield return cursor.item;
693 public IDirectedCollectionValue<T> Backwards()
695 list.modifycheck(stamp);
697 Range b = (Range)MemberwiseClone();
699 b.forwards = !forwards;
705 IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); }
709 public EnumerationDirection Direction
713 { return forwards ? EnumerationDirection.Forwards : EnumerationDirection.Backwards; }
720 #region IList<T> Members
723 /// <exception cref="InvalidOperationException
"/> if this list is empty.
725 /// <value>The first item in this list.</value>
727 public virtual T First
734 throw new InvalidOperationException("List
is empty
");
736 return startsentinel.next.item;
742 /// <exception cref="InvalidOperationException
"/> if this list is empty.
744 /// <value>The last item in this list.</value>
746 public virtual T Last
753 throw new InvalidOperationException("List
is empty
");
755 return endsentinel.prev.item;
761 /// Since <code>Add(T item)</code> always add at the end of the list,
762 /// this describes if list has FIFO or LIFO semantics.
764 /// <value>True if the <code>Remove()</code> operation removes from the
765 /// start of the list, false if it removes from the end.</value>
770 get { modifycheck(); return fIFO; }
772 set { updatecheck(); fIFO = value; }
777 /// On this list, this indexer is read/write.
778 /// <exception cref="IndexOutOfRangeException
"/> if i is negative or
779 /// >= the size of the collection.
781 /// <value>The i'th item of this list.</value>
782 /// <param name="index
">The index of the item to fetch or store.</param>
784 public virtual T this[int index]
787 get { modifycheck(); return get(index).item; }
789 set { updatecheck(); get(index).item = value; }
794 /// Return the node at position n
796 /// <param name="n
"></param>
797 /// <returns></returns>
798 protected Node get(int n)
800 if (n < 0 || n >= size)
801 throw new IndexOutOfRangeException();
802 else if (n < size / 2)
804 Node node = startsentinel;
806 for (int i = 0; i <= n; i++)
813 Node node = endsentinel;
815 for (int i = size; i > n; i--)
824 /// Insert an item at a specific index location in this list.
825 /// <exception cref="IndexOutOfRangeException
"/> if i is negative or
826 /// > the size of the collection.</summary>
827 /// <param name="i
">The index at which to insert.</param>
828 /// <param name="item
">The item to insert.</param>
830 public virtual void Insert(int i, T item)
833 insert(i == size ? endsentinel : get(i), item);
838 /// Insert into this list all items from an enumerable collection starting
839 /// at a particular index.
840 /// <exception cref="IndexOutOfRangeException
"/> if i is negative or
841 /// > the size of the collection.
843 /// <param name="i
">Index to start inserting at</param>
844 /// <param name="items
">Items to insert</param>
846 public virtual void InsertAll(int i, MSG.IEnumerable<T> items)
853 succ = i == size ? endsentinel : get(i);
856 //TODO: replace with Debug.Assert(!maintaintags)
857 int taglimit = i == size ? int.MaxValue : succ.tag - 1, thetag = node.tag;
859 TagGroup taggroup = null;
860 int taglimit = 0, thetag = 0;
863 taggroup = gettaggroup(node, succ, out thetag, out taglimit);
865 foreach (T item in items)
867 Node tmp = new Node(item, node, null);
871 tmp.tag = thetag < taglimit ? ++thetag : thetag;
875 tmp.tag = thetag < taglimit ? ++thetag : thetag;
876 tmp.taggroup = taggroup;
886 taggroup.count += count;
887 taggroup.first = succ.prev;
888 taggroup.last = node;
894 if (underlying != null)
895 underlying.size += count;
898 if (maintaintags && node.tag == node.prev.tag)
903 if (node.tag == node.prev.tag)
904 splittaggroup(taggroup);
911 /// Insert an item right before the first occurrence of some target item.
912 /// <exception cref="ArgumentException
"/> if target is not found
914 /// <param name="item
">The item to insert.</param>
915 /// <param name="target
">The target before which to insert.</param>
917 public virtual void InsertBefore(T item, T target)
921 Node node = startsentinel.next;
924 if (!find(target, ref node, ref i))
925 throw new ArgumentException("Target item not found
");
932 /// Insert an item right after the last(???) occurrence of some target item.
933 /// <exception cref="ArgumentException
"/> if target is not found
935 /// <param name="item
">The item to insert.</param>
936 /// <param name="target
">The target after which to insert.</param>
938 public virtual void InsertAfter(T item, T target)
942 Node node = endsentinel.prev;
945 if (!dnif(target, ref node, ref i))
946 throw new ArgumentException("Target item not found
");
948 insert(node.next, item);
953 /// Insert an item at the front of this list.
955 /// <param name="item
">The item to insert.</param>
957 public virtual void InsertFirst(T item)
960 insert(startsentinel.next, item);
964 /// Insert an item at the back of this list.
966 /// <param name="item
">The item to insert.</param>
968 public virtual void InsertLast(T item)
971 insert(endsentinel, item);
976 /// Create a new list consisting of the results of mapping all items of this
979 /// <param name="mapper
">The delegate definging the map.</param>
980 /// <returns>The new list.</returns>
982 public IList<V> Map<V>(Mapper<T, V> mapper)
986 LinkedList<V> retval = new LinkedList<V>();
987 return map<V>(mapper, retval);
991 /// Create a new list consisting of the results of mapping all items of this
992 /// list. The new list will use a specified hasher for the item type.
994 /// <typeparam name="V
">The type of items of the new list</typeparam>
995 /// <param name="mapper
">The delegate defining the map.</param>
996 /// <param name="hasher
">The hasher to use for the new list</param>
997 /// <returns>The new list.</returns>
998 public IList<V> Map<V>(Mapper<T, V> mapper, IHasher<V> hasher)
1002 LinkedList<V> retval = new LinkedList<V>(hasher);
1003 return map<V>(mapper, retval);
1006 private IList<V> map<V>(Mapper<T, V> mapper, LinkedList<V> retval)
1008 Node cursor = startsentinel.next;
1009 LinkedList<V>.Node mcursor = retval.startsentinel;
1012 //TODO: replace with Debug.Assert(!retval.maintaintags)
1013 double tagdelta = int.MaxValue / (size + 1.0);
1016 double tagdelta = int.MaxValue / (size + 1.0);
1018 LinkedList<V>.TagGroup taggroup = null;
1020 if (retval.maintaintags)
1022 taggroup = new LinkedList<V>.TagGroup();
1023 retval.taggroups = 1;
1024 taggroup.count = size;
1027 while (cursor != endsentinel)
1029 mcursor.next = new LinkedList<V>.Node(mapper(cursor.item), mcursor, null);
1030 cursor = cursor.next;
1031 mcursor = mcursor.next;
1034 if (retval.maintaintags) mcursor.tag = (int)(tagdelta * count++);
1036 if (retval.maintaintags)
1038 mcursor.taggroup = taggroup;
1039 mcursor.tag = (int)(tagdelta * count++);
1044 retval.endsentinel.prev = mcursor;
1045 mcursor.next = retval.endsentinel;
1046 retval.size = size; return retval;
1051 /// Remove one item from the list: from the front if <code>FIFO</code>
1052 /// is true, else from the back.
1053 /// <exception cref="InvalidOperationException
"/> if this list is empty.
1055 /// <returns>The removed item.</returns>
1057 public virtual T Remove()
1059 return fIFO ? RemoveFirst() : RemoveLast();
1064 /// Remove one item from the front of the list.
1065 /// <exception cref="InvalidOperationException
"/> if this list is empty.
1067 /// <returns>The removed item.</returns>
1069 public virtual T RemoveFirst()
1073 throw new InvalidOperationException("List
is empty
");
1075 T item = startsentinel.next.item;
1080 remove(startsentinel.next);
1087 /// Remove one item from the back of the list.
1088 /// <exception cref="InvalidOperationException
"/> if this list is empty.
1090 /// <returns>The removed item.</returns>
1092 public virtual T RemoveLast()
1096 throw new InvalidOperationException("List
is empty
");
1098 Node toremove = endsentinel.prev;
1099 T item = toremove.item;
1111 /// Create a list view on this list.
1112 /// <exception cref="ArgumentOutOfRangeException
"/> if the start or count is negative
1113 /// <exception cref="ArgumentException
"/> if the range does not fit within list.
1115 /// <param name="start
">The index in this list of the start of the view.</param>
1116 /// <param name="count
">The size of the view.</param>
1117 /// <returns>The new list view.</returns>
1119 public virtual IList<T> View(int start, int count)
1122 checkRange(start, count);
1124 LinkedList<T> retval = (LinkedList<T>)MemberwiseClone();
1126 retval.underlying = underlying != null ? underlying : this;
1127 retval.offset = offset + start;
1128 retval.size = count;
1129 retval.startsentinel = start == 0 ? startsentinel : get(start - 1);
1130 retval.endsentinel = start + count == size ? endsentinel : get(start + count);
1139 /// Null if this list is not a view.
1141 /// <value>Underlying list for view.</value>
1143 public IList<T> Underlying { [Tested]get { modifycheck(); return underlying; } }
1148 /// <value>Offset for this list view or 0 for a underlying list.</value>
1150 public int Offset { [Tested]get { modifycheck(); return offset; } }
1154 /// Slide this list view along the underlying list.
1155 /// <exception cref="InvalidOperationException
"/> if this list is not a view.
1156 /// <exception cref="ArgumentOutOfRangeException
"/> if the operation
1157 /// would bring either end of the view outside the underlying list.
1159 /// <param name="offset
">The signed amount to slide: positive to slide
1160 /// towards the end.</param>
1162 public void Slide(int offset)
1165 if (underlying == null)
1166 throw new InvalidOperationException("List not a view
");
1168 if (offset + this.offset < 0 || offset + this.offset + size > underlying.size)
1169 throw new ArgumentOutOfRangeException();
1171 if (offset == 0) return;
1174 for (int i = 0; i < offset; i++)
1176 endsentinel = endsentinel.next;
1177 startsentinel = startsentinel.next;
1180 for (int i = 0; i < -offset; i++)
1182 endsentinel = endsentinel.prev;
1183 startsentinel = startsentinel.prev;
1186 this.offset += offset;
1191 /// Slide this list view along the underlying list, changing its size.
1192 /// <exception cref="InvalidOperationException
"/> if this list is not a view.
1193 /// <exception cref="ArgumentOutOfRangeException
"/> if the operation
1194 /// would bring either end of the view outside the underlying list.
1196 /// <param name="offset
">The signed amount to slide: positive to slide
1197 /// towards the end.</param>
1198 /// <param name="size
">The new size of the view.</param>
1200 public void Slide(int offset, int size)
1203 if (underlying == null)
1204 throw new InvalidOperationException("List not a view
");
1206 if (offset + this.offset < 0 || offset + this.offset + size > underlying.size)
1207 throw new ArgumentOutOfRangeException();
1209 Node node = startsentinel;
1212 for (int i = 0; i < offset; i++)
1215 for (int i = 0; i < -offset; i++)
1218 startsentinel = node;
1220 int enddelta = offset + size - this.size;
1224 for (int i = 0; i < enddelta; i++)
1227 for (int i = 0; i < -enddelta; i++)
1232 this.offset += offset;
1237 /// Reverse the list so the items are in the opposite sequence order.
1240 public void Reverse() { Reverse(0, size); }
1243 //Question: should we swap items or move nodes around?
1244 //The first seems much more efficient unless the items are value types
1245 //with a large memory footprint.
1246 //(Swapping will do count*3/2 T assignments, linking around will do
1247 // 4*count ref assignments; note that ref assignments are more expensive
1248 //than copying non-ref bits)
1250 /// Reverst part of the list so the items are in the opposite sequence order.
1251 /// <exception cref="ArgumentException
"/> if the count is negative.
1252 /// <exception cref="ArgumentOutOfRangeException
"/> if the part does not fit
1255 /// <param name="start
">The index of the start of the part to reverse.</param>
1256 /// <param name="count
">The size of the part to reverse.</param>
1258 public virtual void Reverse(int start, int count)
1261 checkRange(start, count);
1265 Node a = get(start), b = get(start + count - 1);
1267 for (int i = 0; i < count / 2; i++)
1269 T swap = a.item;a.item = b.item;b.item = swap;
1275 a = a.next;b = b.prev;
1281 /// Check if this list is sorted according to a specific sorting order.
1283 /// <param name="c
">The comparer defining the sorting order.</param>
1284 /// <returns>True if the list is sorted, else false.</returns>
1286 public bool IsSorted(IComparer<T> c)
1292 Node node = startsentinel.next;
1293 T prevItem = node.item;
1296 while (node != endsentinel)
1298 if (c.Compare(prevItem, node.item) > 0)
1302 prevItem = node.item;
1311 // Sort the linked list using mergesort
1313 /// Sort the items of the list according to a specific sorting order.
1314 /// The sorting is stable.
1316 /// <param name="c
">The comparer defining the sorting order.</param>
1318 public void Sort(IComparer<T> c)
1322 // Build a linked list of non-empty runs.
1323 // The prev field in first node of a run points to next run's first node
1328 if (maintaintags && underlying != null)
1330 Node cursor = startsentinel.next;
1332 while (cursor != endsentinel)
1334 cursor.taggroup.count--;
1335 cursor = cursor.next;
1339 Node runTail = startsentinel.next;
1340 Node prevNode = startsentinel.next;
1342 endsentinel.prev.next = null;
1343 while (prevNode != null)
1345 Node node = prevNode.next;
1347 while (node != null && c.Compare(prevNode.item, node.item) <= 0)
1350 node = prevNode.next;
1353 // Completed a run; prevNode is the last node of that run
1354 prevNode.next = null; // Finish the run
1355 runTail.prev = node; // Link it into the chain of runs
1357 if (c.Compare(endsentinel.prev.item, prevNode.item) <= 0)
1358 endsentinel.prev = prevNode; // Update last pointer to point to largest
1360 prevNode = node; // Start a new run
1363 // Repeatedly merge runs two and two, until only one run remains
1364 while (startsentinel.next.prev != null)
1366 Node run = startsentinel.next;
1367 Node newRunTail = null;
1369 while (run != null && run.prev != null)
1370 { // At least two runs, merge
1371 Node nextRun = run.prev.prev;
1372 Node newrun = mergeRuns(run, run.prev, c);
1374 if (newRunTail != null)
1375 newRunTail.prev = newrun;
1377 startsentinel.next = newrun;
1379 newRunTail = newrun;
1383 if (run != null) // Add the last run, if any
1384 newRunTail.prev = run;
1387 endsentinel.prev.next = endsentinel;
1388 startsentinel.next.prev = startsentinel;
1390 //assert invariant();
1391 //assert isSorted();
1395 int span = (endsentinel.tag > 0 ? endsentinel.tag - 1 : int.MaxValue) - startsentinel.tag;
1397 Debug.Assert(span >= size);
1399 double tagdelta = span / (size + 0.0);
1401 Node cursor = startsentinel.next;
1403 while (cursor != endsentinel)
1405 cursor.tag = startsentinel.tag + (int)(tagdelta * count++);
1406 cursor = cursor.next;
1412 Node cursor = startsentinel.next, end = endsentinel;
1414 TagGroup t = gettaggroup(startsentinel, endsentinel, out tag, out taglimit);
1415 int tagdelta = taglimit / (size + 1) - tag / (size + 1);
1417 tagdelta = tagdelta == 0 ? 1 : tagdelta;
1418 if (underlying == null)
1421 while (cursor != end)
1423 tag = tag + tagdelta > taglimit ? taglimit : tag + tagdelta;
1426 cursor = cursor.next;
1429 if (tag == taglimit)
1436 private static Node mergeRuns(Node run1, Node run2, IComparer<T> c)
1438 //assert run1 != null && run2 != null;
1440 bool prev1; // is prev from run1?
1442 if (c.Compare(run1.item, run2.item) <= 0)
1457 //assert start != null;
1459 while (run1 != null && run2 != null)
1463 //assert prev.next == run1;
1464 //Comparable run2item = (Comparable)run2.item;
1465 while (run1 != null && c.Compare(run2.item, run1.item) >= 0)
1472 { // prev.item <= run2.item < run1.item; insert run2
1482 //assert prev.next == run2;
1483 //Comparable run1item = (Comparable)run1.item;
1484 while (run2 != null && c.Compare(run1.item, run2.item) > 0)
1491 { // prev.item < run1.item <= run2.item; insert run1
1501 //assert !(run1 != null && prev1) && !(run2 != null && !prev1);
1503 { // last run2 < all of run1; attach run1 at end
1507 else if (run2 != null)
1518 /// Randonmly shuffle the items of this list.
1520 public virtual void Shuffle() { Shuffle(new C5Random()); }
1524 /// Shuffle the items of this list according to a specific random source.
1526 /// <param name="rnd
">The random source.</param>
1527 public virtual void Shuffle(Random rnd)
1531 ArrayList<T> a = new ArrayList<T>();
1536 Node cursor = startsentinel.next;
1539 while (cursor != endsentinel)
1541 cursor.item = a[j++];
1542 cursor = cursor.next;
1548 #region IIndexed<T> Members
1552 /// <exception cref="IndexOutOfRangeException
"/>.
1554 /// <value>The directed collection of items in a specific index interval.</value>
1555 /// <param name="start
">The low index of the interval (inclusive).</param>
1556 /// <param name="count
">The size of the range.</param>
1558 public IDirectedCollectionValue<T> this[int start, int count]
1564 checkRange(start, count);
1565 return new Range(this, start, count, true);
1571 /// Searches for an item in the list going forwrds from the start.
1573 /// <param name="item
">Item to search for.</param>
1574 /// <returns>Index of item from start.</returns>
1576 public virtual int IndexOf(T item)
1580 Node node = startsentinel.next;
1583 if (find(item, ref node, ref index))
1591 /// Searches for an item in the list going backwords from the end.
1593 /// <param name="item
">Item to search for.</param>
1594 /// <returns>Index of of item from the end.</returns>
1596 public virtual int LastIndexOf(T item)
1600 Node node = endsentinel.prev;
1601 int index = size - 1;
1603 if (dnif(item, ref node, ref index))
1610 private bool find(T item, ref Node node, ref int index)
1612 while (node != endsentinel)
1614 //if (item.Equals(node.item))
1615 if (itemhasher.Equals(item, node.item))
1626 private bool dnif(T item, ref Node node, ref int index)
1628 while (node != startsentinel)
1630 //if (item.Equals(node.item))
1631 if (itemhasher.Equals(item, node.item))
1643 /// Remove the item at a specific position of the list.
1644 /// <exception cref="IndexOutOfRangeException
"/> if i is negative or
1645 /// >= the size of the collection.
1647 /// <param name="i
">The index of the item to remove.</param>
1648 /// <returns>The removed item.</returns>
1650 public virtual T RemoveAt(int i)
1653 return remove(get(i));
1658 /// Remove all items in an index interval.
1659 /// <exception cref="IndexOutOfRangeException
"/>???.
1661 /// <param name="start
">The index of the first item to remove.</param>
1662 /// <param name="count
">The number of items to remove.</param>
1664 public virtual void RemoveInterval(int start, int count)
1667 checkRange(start, count);
1671 //for small count: optimize
1672 //make an optimal get(int i, int j, ref Node ni, ref Node nj)?
1673 Node a = get(start), b = get(start + count - 1);
1678 TagGroup t = a.taggroup;
1680 while (c.taggroup == t && c != b.next)
1682 removefromtaggroup(c);
1688 Debug.Assert(b.taggroup != t);
1691 while (c.taggroup == t)
1693 removefromtaggroup(c);
1699 a.prev.next = b.next;
1700 b.next.prev = a.prev;
1701 if (underlying != null)
1702 underlying.size -= count;
1710 #region ISequenced<T> Members
1713 int ISequenced<T>.GetHashCode() { modifycheck(); return sequencedhashcode(); }
1717 bool ISequenced<T>.Equals(ISequenced<T> that)
1718 { modifycheck(); return sequencedequals(that); }
1722 #region IDirectedCollection<T> Members
1725 /// Create a collection containing the same items as this collection, but
1726 /// whose enumerator will enumerate the items backwards. The new collection
1727 /// will become invalid if the original is modified. Method typicaly used as in
1728 /// <code>foreach (T x in coll.Backwards()) {...}</code>
1730 /// <returns>The backwards collection.</returns>
1732 public IDirectedCollectionValue<T> Backwards()
1733 { return this[0, size].Backwards(); }
1737 #region IDirectedEnumerable<T> Members
1740 IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); }
1744 #region IEditableCollection<T> Members
1747 /// The value is symbolic indicating the type of asymptotic complexity
1748 /// in terms of the size of this collection (worst-case or amortized as
1751 /// <value>Speed.Linear</value>
1753 public virtual Speed ContainsSpeed { [Tested]get { return Speed.Linear; } }
1757 int ICollection<T>.GetHashCode()
1758 { modifycheck(); return unsequencedhashcode(); }
1762 bool ICollection<T>.Equals(ICollection<T> that)
1763 { modifycheck(); return unsequencedequals(that); }
1767 /// Check if this collection contains (an item equivalent to according to the
1768 /// itemhasher) a particular value.
1770 /// <param name="item
">The value to check for.</param>
1771 /// <returns>True if the items is in this collection.</returns>
1773 public virtual bool Contains(T item)
1777 Node node = startsentinel.next;
1779 while (node != endsentinel)
1781 if (itemhasher.Equals(item, node.item))
1792 /// Check if this collection contains an item equivalent according to the
1793 /// itemhasher to a particular value. If so, return in the ref argument (a
1794 /// binary copy of) the actual value found.
1796 /// <param name="item
">The value to look for.</param>
1797 /// <returns>True if the items is in this collection.</returns>
1799 public virtual bool Find(ref T item)
1803 Node node = startsentinel.next;
1805 while (node != endsentinel)
1807 if (equals(item, node.item))
1821 /// Check if this collection contains an item equivalent according to the
1822 /// itemhasher to a particular value. If so, update the item in the collection
1823 /// to with a binary copy of the supplied value. Will update a single item.
1825 /// <param name="item
">Value to update.</param>
1826 /// <returns>True if the item was found and hence updated.</returns>
1828 public virtual bool Update(T item)
1832 Node node = startsentinel.next;
1834 while (node != endsentinel)
1836 if (equals(item, node.item))
1850 /// Check if this collection contains an item equivalent according to the
1851 /// itemhasher to a particular value. If so, return in the ref argument (a
1852 /// binary copy of) the actual value found. Else, add the item to the collection.
1854 /// <param name="item
">The value to look for.</param>
1855 /// <returns>True if the item was found (hence not added).</returns>
1857 public virtual bool FindOrAdd(ref T item)
1869 /// Check if this collection contains an item equivalent according to the
1870 /// itemhasher to a particular value. If so, update the item in the collection
1871 /// to with a binary copy of the supplied value; else add the value to the collection.
1873 /// <param name="item
">Value to add or update.</param>
1874 /// <returns>True if the item was updated (hence not added).</returns>
1876 public virtual bool UpdateOrAdd(T item)
1888 /// Remove a particular item from this collection. Since the collection has bag
1889 /// semantics only one copy equivalent to the supplied item is removed.
1891 /// <param name="item
">The value to remove.</param>
1892 /// <returns>True if the item was found (and removed).</returns>
1894 public virtual bool Remove(T item)
1898 Node node = startsentinel.next;
1900 while (node != endsentinel)
1902 if (itemhasher.Equals(item, node.item))
1916 /// Remove a particular item from this collection if found (only one copy).
1917 /// If an item was removed, report a binary copy of the actual item removed in
1920 /// <param name="item
">The value to remove on input.</param>
1921 /// <returns>True if the item was found (and removed).</returns>
1923 public virtual bool RemoveWithReturn(ref T item)
1927 Node node = startsentinel.next;
1929 while (node != endsentinel)
1931 if (itemhasher.Equals(item, node.item))
1946 /// Remove all items in another collection from this one, take multiplicities into account.
1948 /// <param name="items
">The items to remove.</param>
1950 public virtual void RemoveAll(MSG.IEnumerable<T> items)
1952 //Use an auxiliary hashbag should speed from O(n*m) to O(n+m) but use more memory
1957 bool[] paired = new bool[size];
1958 int index, toretain = size;
1961 foreach (T item in items)
1963 node = startsentinel.next;
1965 while (node != endsentinel)
1967 if (itemhasher.Equals(item, node.item) && !paired[index])
1969 if (--toretain == 0)
1975 paired[index] = true;
1987 if (toretain == size)
1990 if (underlying != null)
1991 underlying.size -= size - toretain;
1993 node = startsentinel.next;
1996 while (paired[index])
1999 if (maintaintags) removefromtaggroup(node);
2007 startsentinel.next = node;
2008 node.prev = startsentinel;
2013 while (--toretain > 0 && !paired[++index])
2016 Node localend = node;
2022 while (node != endsentinel)
2024 if (maintaintags) removefromtaggroup(node);
2030 endsentinel.prev = localend;
2031 localend.next = endsentinel;
2036 while (paired[index])
2039 if (maintaintags) removefromtaggroup(node);
2045 localend.next = node;
2046 node.prev = localend;
2052 /// Remove all items from this collection.
2055 public virtual void Clear()
2067 if (underlying != null)
2069 Node n = startsentinel.next;
2071 while (n != endsentinel)
2073 n.next.prev = startsentinel;
2074 startsentinel.next = n.next;
2075 removefromtaggroup(n);
2085 endsentinel.prev = startsentinel;
2086 startsentinel.next = endsentinel;
2087 if (underlying != null)
2088 underlying.size -= size;
2095 /// Remove all items not in some other collection from this one, take multiplicities into account.
2097 /// <param name="items
">The items to retain.</param>
2099 public virtual void RetainAll(MSG.IEnumerable<T> items)
2105 bool[] paired = new bool[size];
2106 int index, pairs = 0;
2109 foreach (T item in items)
2111 node = startsentinel.next;
2113 while (node != endsentinel)
2115 if (itemhasher.Equals(item, node.item) && !paired[index])
2117 if (++pairs == size)
2120 paired[index] = true;
2138 if (underlying != null)
2139 underlying.size -= size - pairs;
2141 node = startsentinel.next;
2144 while (!paired[index])
2147 if (maintaintags) removefromtaggroup(node);
2155 startsentinel.next = node;
2156 node.prev = startsentinel;
2161 while (--pairs > 0 && paired[++index])
2164 Node localend = node;
2170 while (node != endsentinel)
2172 if (maintaintags) removefromtaggroup(node);
2177 endsentinel.prev = localend;
2178 localend.next = endsentinel;
2183 while (!paired[index])
2186 if (maintaintags) removefromtaggroup(node);
2192 localend.next = node;
2193 node.prev = localend;
2199 /// Check if this collection contains all the values in another collection
2200 /// with respect to multiplicities.
2202 /// <param name="items
">The </param>
2203 /// <returns>True if all values in <code>items</code>is in this collection.</returns>
2205 public virtual bool ContainsAll(MSG.IEnumerable<T> items)
2209 bool[] paired = new bool[size];
2211 foreach (T item in items)
2214 Node node = startsentinel.next;
2216 while (node != endsentinel)
2218 if (itemhasher.Equals(item, node.item) && !paired[index])
2220 paired[index] = true;
2238 /// Create a new list consisting of the items of this list satisfying a
2239 /// certain predicate.
2241 /// <param name="filter
">The filter delegate defining the predicate.</param>
2242 /// <returns>The new list.</returns>
2244 public IList<T> FindAll(Filter<T> filter)
2246 LinkedList<T> retval = new LinkedList<T>();
2250 Node cursor = startsentinel.next;
2251 Node mcursor = retval.startsentinel;
2254 double tagdelta = int.MaxValue / (size + 1.0);
2256 double tagdelta = int.MaxValue / (size + 1.0);
2258 TagGroup taggroup = null;
2260 if (retval.maintaintags)
2262 taggroup = new TagGroup();
2263 retval.taggroups = 1;
2266 while (cursor != endsentinel)
2268 if (filter(cursor.item))
2270 mcursor.next = new Node(cursor.item, mcursor, null);
2271 mcursor = mcursor.next;
2274 if (retval.maintaintags)
2275 mcursor.tag = (int)(retval.size * tagdelta);
2277 if (retval.maintaintags)
2279 mcursor.taggroup = taggroup;
2280 mcursor.tag = (int)(tagdelta * count++);
2285 cursor = cursor.next;
2289 if (retval.maintaintags)
2290 taggroup.count = retval.size;
2292 retval.endsentinel.prev = mcursor;
2293 mcursor.next = retval.endsentinel;
2299 /// Count the number of items of the collection equal to a particular value.
2300 /// Returns 0 if and only if the value is not in the collection.
2302 /// <param name="item
">The value to count.</param>
2303 /// <returns>The number of copies found.</returns>
2305 public virtual int ContainsCount(T item)
2311 Node node = startsentinel.next;
2313 while (node != endsentinel)
2315 if (itemhasher.Equals(node.item, item))
2326 /// Remove all items equivalent to a given value.
2328 /// <param name="item
">The value to remove.</param>
2330 public virtual void RemoveAllCopies(T item)
2335 Node node = startsentinel.next;
2337 while (node != endsentinel)
2339 //Here we could loop to collect more matching adjacent nodes in one
2340 //splice, but with some overhead for the general case.
2341 //se retailall for an example
2342 //if (node.item.Equals(item))
2343 if (itemhasher.Equals(node.item, item))
2346 node.prev.next = node.next;
2347 node.next.prev = node.prev;
2350 removefromtaggroup(node);
2360 if (underlying != null)
2361 underlying.size -= removed;
2368 #region ICollection<T> Members
2373 /// <value>The number of items in this collection</value>
2375 public override int Count { [Tested]get { modifycheck(); return size; } }
2379 #region IEnumerable<T> Members
2381 /// Create an enumerator for the collection
2383 /// <returns>The enumerator</returns>
2385 public override MSG.IEnumerator<T> GetEnumerator()
2387 Node cursor = startsentinel.next;
2388 int startstamp = this.stamp;
2390 while (cursor != endsentinel)
2392 modifycheck(startstamp);
2393 yield return cursor.item;
2394 cursor = cursor.next;
2400 #region ISink<T> Members
2402 /// Add an item to this collection if possible.
2404 /// <param name="item
">The item to add.</param>
2405 /// <returns>True.</returns>
2407 public virtual bool Add(T item)
2410 insert(endsentinel, item);
2418 /// <value>True since this collection has bag semantics.</value>
2420 public virtual bool AllowsDuplicates { [Tested]get { return true; } }
2424 /// Add the elements from another collection to this collection.
2426 /// <param name="items
">The items to add.</param>
2428 public virtual void AddAll(MSG.IEnumerable<T> items) { InsertAll(size, items); }
2431 /// Add the elements from another collection with a more specialized item type
2432 /// to this collection.
2434 /// <typeparam name="U
">The type of items to add</typeparam>
2435 /// <param name="items
">The items to add</param>
2436 public virtual void AddAll<U>(MSG.IEnumerable<U> items) where U : T
2444 #region IStack<T> Members
2447 /// Push an item to the top of the stack.
2449 /// <param name="item
">The item</param>
2451 public void Push(T item)
2457 /// Pop the item at the top of the stack from the stack.
2459 /// <returns>The popped item.</returns>
2463 return RemoveLast();
2468 #region IQueue<T> Members
2471 /// Enqueue an item at the back of the queue.
2473 /// <param name="item
">The item</param>
2475 public void EnQueue(T item)
2481 /// Dequeue an item from the front of the queue.
2483 /// <returns>The item</returns>
2487 return RemoveFirst();
2495 /// Check the sanity of this list
2497 /// <returns>true if sane</returns>
2499 public virtual bool Check()
2503 if (underlying != null && underlying.stamp != stamp)
2505 Console.WriteLine("underlying
!= null && underlying
.stamp({0}
) != stamp({1}
)", underlying.stamp, stamp);
2509 if (startsentinel == null)
2511 Console.WriteLine("startsentinel
== null");
2515 if (endsentinel == null)
2517 Console.WriteLine("endsentinel
== null");
2523 if (startsentinel != null && startsentinel.next != endsentinel)
2525 Console.WriteLine("size
== 0 but startsentinel
.next
!= endsentinel
");
2529 if (endsentinel != null && endsentinel.prev != startsentinel)
2531 Console.WriteLine("size
== 0 but endsentinel
.prev
!= startsentinel
");
2536 if (startsentinel == null)
2540 Node node = startsentinel.next, prev = startsentinel;
2542 int taggroupsize = 0, oldtaggroupsize = losize + 1, seentaggroups = 0;
2543 TagGroup oldtg = null;
2545 if (maintaintags && underlying == null)
2547 TagGroup tg = startsentinel.taggroup;
2549 if (tg.count != 0 || tg.first != null || tg.last != null || tg.tag != int.MinValue)
2551 Console.WriteLine("Bad startsentinel tag
group: {0}
", tg);
2555 tg = endsentinel.taggroup;
2556 if (tg.count != 0 || tg.first != null || tg.last != null || tg.tag != int.MaxValue)
2558 Console.WriteLine("Bad endsentinel tag
group: {0}
", tg);
2563 while (node != endsentinel)
2566 if (node.prev != prev)
2568 Console.WriteLine("Bad backpointer at node {0}
", count);
2572 if (maintaintags && node.prev.tag >= node.tag)
2574 Console.WriteLine("node
.prev
.tag ({0}
) >= node
.tag ({1}
) at index
={2} item
={3}
", node.prev.tag, node.tag, count, node.item);
2578 if (maintaintags && underlying == null)
2580 if (!node.prev.precedes(node))
2582 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);
2586 if (node.taggroup != oldtg)
2590 if (oldtg.count != taggroupsize)
2592 Console.WriteLine("Bad taggroupsize
: oldtg
.count ({0}
) != taggroupsize ({1}
) at index
={2} item
={3}
", oldtg.count, taggroupsize, count, node.item);
2596 if (oldtaggroupsize <= losize && taggroupsize <= losize)
2598 Console.WriteLine("Two small taggroups
in a row
: oldtaggroupsize ({0}
), taggroupsize ({1}
) at index
={2} item
={3}
", oldtaggroupsize, taggroupsize, count, node.item);
2602 oldtaggroupsize = taggroupsize;
2606 oldtg = node.taggroup;
2619 Console.WriteLine("Null next pointer at node {0}
", count);
2625 if (maintaintags && underlying == null && size > 0)
2627 oldtg = node.prev.taggroup;
2630 if (oldtg.count != taggroupsize)
2632 Console.WriteLine("Bad taggroupsize
: oldtg
.count ({0}
) != taggroupsize ({1}
) at index
={2} item
={3}
", oldtg.count, taggroupsize, count, node.item);
2636 if (oldtaggroupsize <= losize && taggroupsize <= losize)
2638 Console.WriteLine("Two small taggroups
in a row
: oldtaggroupsize ({0}
), taggroupsize ({1}
) at index
={2} item
={3}
", oldtaggroupsize, taggroupsize, count, node.item);
2643 if (seentaggroups != taggroups)
2645 Console.WriteLine("seentaggroups ({0}
) != taggroups ({1}
) (at size {2}
)", seentaggroups, taggroups, size);
2652 Console.WriteLine("size
={0} but enumeration gives {1} nodes
", size, count);