--- /dev/null
+/*\r
+ Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\r
+ Permission is hereby granted, free of charge, to any person obtaining a copy\r
+ of this software and associated documentation files (the "Software"), to deal\r
+ in the Software without restriction, including without limitation the rights\r
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
+ copies of the Software, and to permit persons to whom the Software is\r
+ furnished to do so, subject to the following conditions:\r
+ \r
+ The above copyright notice and this permission notice shall be included in\r
+ all copies or substantial portions of the Software.\r
+ \r
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
+ SOFTWARE.\r
+*/\r
+\r
+#define HASHINDEXnot\r
+\r
+using System;\r
+using System.Diagnostics;\r
+using SCG = System.Collections.Generic;\r
+\r
+namespace C5\r
+{\r
+ /// <summary>\r
+ /// A list collection class based on a doubly linked list data structure.\r
+ /// </summary>\r
+ [Serializable]\r
+ public class LinkedList<T> : SequencedBase<T>, IList<T>\r
+#if HASHINDEX\r
+#else\r
+, IStack<T>, IQueue<T>\r
+#endif\r
+ {\r
+ #region Fields\r
+ /// <summary>\r
+ /// IExtensible.Add(T) always does AddLast(T), fIFO determines \r
+ /// if T Remove() does RemoveFirst() or RemoveLast()\r
+ /// </summary>\r
+ bool fIFO = true;\r
+\r
+ #region Events\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <value></value>\r
+ public override EventTypeEnum ListenableEvents { get { return underlying == null ? EventTypeEnum.All : EventTypeEnum.None; } }\r
+\r
+ #endregion\r
+\r
+ //Invariant: startsentinel != null && endsentinel != null\r
+ //If size==0: startsentinel.next == endsentinel && endsentinel.prev == startsentinel\r
+ //Else: startsentinel.next == First && endsentinel.prev == Last)\r
+ /// <summary>\r
+ /// Node to the left of first node \r
+ /// </summary>\r
+ Node startsentinel;\r
+ /// <summary>\r
+ /// Node to the right of last node\r
+ /// </summary>\r
+ Node endsentinel;\r
+ /// <summary>\r
+ /// Offset of this view in underlying list\r
+ /// </summary>\r
+#if HASHINDEX\r
+ int? offset;\r
+#else\r
+ int offset;\r
+#endif\r
+\r
+ /// <summary>\r
+ /// underlying list of this view (or null for the underlying list)\r
+ /// </summary>\r
+ LinkedList<T> underlying;\r
+\r
+ //Note: all views will have the same views list since all view objects are created by MemeberwiseClone()\r
+ WeakViewList<LinkedList<T>> views;\r
+ WeakViewList<LinkedList<T>>.Node myWeakReference;\r
+\r
+ /// <summary>\r
+ /// Has this list or view not been invalidated by some operation (by someone calling Dispose())\r
+ /// </summary>\r
+ bool isValid = true;\r
+\r
+\r
+#if HASHINDEX\r
+ HashDictionary<T, Node> dict;\r
+ /// <summary>\r
+ /// Number of taggroups\r
+ /// </summary>\r
+ int taggroups;\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <value></value>\r
+ int Taggroups\r
+ {\r
+ get { return underlying == null ? taggroups : underlying.taggroups; }\r
+ set { if (underlying == null) taggroups = value; else underlying.taggroups = value; }\r
+ }\r
+#endif\r
+\r
+ #endregion\r
+\r
+ #region Util\r
+\r
+ bool equals(T i1, T i2) { return itemequalityComparer.Equals(i1, i2); }\r
+\r
+ #region Check utilities\r
+ /// <summary>\r
+ /// Check if it is valid to perform updates and increment stamp of \r
+ /// underlying if this is a view.\r
+ /// <para>This method should be called in every public modifying \r
+ /// methods before any modifications are performed.\r
+ /// </para>\r
+ /// </summary>\r
+ /// <exception cref="InvalidOperationException"> if check fails.</exception>\r
+ protected override void updatecheck()\r
+ {\r
+ validitycheck();\r
+ base.updatecheck();\r
+ if (underlying != null)\r
+ underlying.stamp++;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Check if we are a view that the underlyinglist has only been updated through us.\r
+ /// <br/>\r
+ /// This method should be called from enumerators etc to guard against \r
+ /// modification of the base collection.\r
+ /// </summary>\r
+ /// <exception cref="InvalidOperationException"> if check fails.</exception>\r
+ void validitycheck()\r
+ {\r
+ if (!isValid)\r
+ throw new ViewDisposedException();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Check that the list has not been updated since a particular time.\r
+ /// </summary>\r
+ /// <param name="stamp">The stamp indicating the time.</param>\r
+ /// <exception cref="CollectionModifiedException"> if check fails.</exception>\r
+ protected override void modifycheck(int stamp)\r
+ {\r
+ validitycheck();\r
+ if ((underlying != null ? underlying.stamp : this.stamp) != stamp)\r
+ throw new CollectionModifiedException();\r
+ }\r
+ #endregion\r
+\r
+ #region Searching\r
+ bool contains(T item, out Node node)\r
+ {\r
+#if HASHINDEX\r
+ if (dict.Find(item, out node))\r
+ return insideview(node);\r
+#else\r
+ //TODO: search from both ends? Or search from the end selected by FIFO?\r
+ node = startsentinel.next;\r
+ while (node != endsentinel)\r
+ {\r
+ if (equals(item, node.item))\r
+ return true;\r
+ node = node.next;\r
+ }\r
+#endif\r
+ return false;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Search forwards from a node for a node with a particular item.\r
+ /// </summary>\r
+ /// <param name="item">The item to look for</param>\r
+ /// <param name="node">On input, the node to start at. If item was found, the node found on output.</param>\r
+ /// <param name="index">If node was found, the value will be the number of links followed higher than \r
+ /// the value on input. If item was not found, the value on output is undefined.</param>\r
+ /// <returns>True if node was found.</returns>\r
+ bool find(T item, ref Node node, ref int index)\r
+ {\r
+ while (node != endsentinel)\r
+ {\r
+ //if (item.Equals(node.item))\r
+ if (itemequalityComparer.Equals(item, node.item))\r
+ return true;\r
+\r
+ index++;\r
+ node = node.next;\r
+ }\r
+\r
+ return false;\r
+ }\r
+\r
+ bool dnif(T item, ref Node node, ref int index)\r
+ {\r
+ while (node != startsentinel)\r
+ {\r
+ //if (item.Equals(node.item))\r
+ if (itemequalityComparer.Equals(item, node.item))\r
+ return true;\r
+\r
+ index--;\r
+ node = node.prev;\r
+ }\r
+\r
+ return false;\r
+ }\r
+\r
+#if HASHINDEX\r
+ bool insideview(Node node)\r
+ {\r
+ if (underlying == null)\r
+ return true;\r
+ return (startsentinel.precedes(node) && node.precedes(endsentinel));\r
+ }\r
+#endif\r
+\r
+ #endregion\r
+\r
+ #region Indexing\r
+ /// <summary>\r
+ /// Return the node at position pos\r
+ /// </summary>\r
+ /// <param name="pos"></param>\r
+ /// <returns></returns>\r
+ Node get(int pos)\r
+ {\r
+ if (pos < 0 || pos >= size)\r
+ throw new IndexOutOfRangeException();\r
+ else if (pos < size / 2)\r
+ { // Closer to front\r
+ Node node = startsentinel;\r
+\r
+ for (int i = 0; i <= pos; i++)\r
+ node = node.next;\r
+\r
+ return node;\r
+ }\r
+ else\r
+ { // Closer to end\r
+ Node node = endsentinel;\r
+\r
+ for (int i = size; i > pos; i--)\r
+ node = node.prev;\r
+\r
+ return node;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Find the distance from pos to the set given by positions. Return the\r
+ /// signed distance as return value and as an out parameter, the\r
+ /// array index of the nearest position. This is used for up to length 5 of\r
+ /// positions, and we do not assume it is sorted. \r
+ /// </summary>\r
+ /// <param name="pos"></param>\r
+ /// <param name="positions"></param>\r
+ /// <param name="nearest"></param>\r
+ /// <returns></returns>\r
+ int dist(int pos, out int nearest, int[] positions)\r
+ {\r
+ nearest = -1;\r
+ int bestdist = int.MaxValue;\r
+ int signeddist = bestdist;\r
+ for (int i = 0; i < positions.Length; i++)\r
+ {\r
+ int thisdist = positions[i] - pos;\r
+ if (thisdist >= 0 && thisdist < bestdist) { nearest = i; bestdist = thisdist; signeddist = thisdist; }\r
+ if (thisdist < 0 && -thisdist < bestdist) { nearest = i; bestdist = -thisdist; signeddist = thisdist; }\r
+ }\r
+ return signeddist;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Find the node at position pos, given known positions of several nodes.\r
+ /// </summary>\r
+ /// <param name="pos"></param>\r
+ /// <param name="positions"></param>\r
+ /// <param name="nodes"></param>\r
+ /// <returns></returns>\r
+ Node get(int pos, int[] positions, Node[] nodes)\r
+ {\r
+ int nearest;\r
+ int delta = dist(pos, out nearest, positions);\r
+ Node node = nodes[nearest];\r
+ if (delta > 0)\r
+ for (int i = 0; i < delta; i++)\r
+ node = node.prev;\r
+ else\r
+ for (int i = 0; i > delta; i--)\r
+ node = node.next;\r
+ return node;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Get nodes at positions p1 and p2, given nodes at several positions.\r
+ /// </summary>\r
+ /// <param name="p1"></param>\r
+ /// <param name="p2"></param>\r
+ /// <param name="n1"></param>\r
+ /// <param name="n2"></param>\r
+ /// <param name="positions"></param>\r
+ /// <param name="nodes"></param>\r
+ void getPair(int p1, int p2, out Node n1, out Node n2, int[] positions, Node[] nodes)\r
+ {\r
+ int nearest1, nearest2;\r
+ int delta1 = dist(p1, out nearest1, positions), d1 = delta1 < 0 ? -delta1 : delta1;\r
+ int delta2 = dist(p2, out nearest2, positions), d2 = delta2 < 0 ? -delta2 : delta2;\r
+\r
+ if (d1 < d2)\r
+ {\r
+ n1 = get(p1, positions, nodes);\r
+ n2 = get(p2, new int[] { positions[nearest2], p1 }, new Node[] { nodes[nearest2], n1 });\r
+ }\r
+ else\r
+ {\r
+ n2 = get(p2, positions, nodes);\r
+ n1 = get(p1, new int[] { positions[nearest1], p2 }, new Node[] { nodes[nearest1], n2 });\r
+ }\r
+ }\r
+ #endregion\r
+\r
+ #region Insertion\r
+#if HASHINDEX\r
+ void insert(int index, Node succ, T item)\r
+ {\r
+ Node newnode = new Node(item);\r
+ if (dict.FindOrAdd(item, ref newnode))\r
+ throw new DuplicateNotAllowedException("Item already in indexed list");\r
+ insertNode(true, succ, newnode);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Insert a Node before another one. Unchecked version. \r
+ /// </summary>\r
+ /// <param name="succ">The successor to be</param>\r
+ /// <param name="newnode">Node to insert</param>\r
+ /// <param name="updateViews">update overlapping view in this call</param>\r
+ void insertNode(bool updateViews, Node succ, Node newnode)\r
+ {\r
+ newnode.next = succ;\r
+ Node pred = newnode.prev = succ.prev;\r
+ succ.prev.next = newnode;\r
+ succ.prev = newnode;\r
+ size++;\r
+ if (underlying != null)\r
+ underlying.size++;\r
+ settag(newnode);\r
+ if (updateViews)\r
+ fixViewsAfterInsert(succ, pred, 1, 0);\r
+ }\r
+#else\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <param name="index">The index in this view</param>\r
+ /// <param name="succ"></param>\r
+ /// <param name="item"></param>\r
+ /// <returns></returns>\r
+ Node insert(int index, Node succ, T item)\r
+ {\r
+ Node newnode = new Node(item, succ.prev, succ);\r
+ succ.prev.next = newnode;\r
+ succ.prev = newnode;\r
+ size++;\r
+ if (underlying != null)\r
+ underlying.size++;\r
+ fixViewsAfterInsert(succ, newnode.prev, 1, Offset + index);\r
+ return newnode;\r
+ }\r
+#endif\r
+ #endregion\r
+\r
+ #region Removal\r
+ T remove(Node node, int index)\r
+ {\r
+ fixViewsBeforeSingleRemove(node, Offset + index);\r
+ node.prev.next = node.next;\r
+ node.next.prev = node.prev;\r
+ size--;\r
+ if (underlying != null)\r
+ underlying.size--;\r
+#if HASHINDEX\r
+ removefromtaggroup(node);\r
+#endif\r
+ return node.item;\r
+ }\r
+\r
+#if HASHINDEX\r
+ private bool dictremove(T item, out Node node)\r
+ {\r
+ if (underlying == null)\r
+ {\r
+ if (!dict.Remove(item, out node))\r
+ return false;\r
+ }\r
+ else\r
+ {\r
+ //We cannot avoid calling dict twice - have to intersperse the listorder test!\r
+ if (!contains(item, out node))\r
+ return false;\r
+ dict.Remove(item);\r
+ }\r
+ return true;\r
+ }\r
+#endif\r
+ #endregion\r
+\r
+ #region fixView utilities\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <param name="added">The actual number of inserted nodes</param>\r
+ /// <param name="pred">The predecessor of the inserted nodes</param>\r
+ /// <param name="succ">The successor of the added nodes</param>\r
+ /// <param name="realInsertionIndex"></param>\r
+ void fixViewsAfterInsert(Node succ, Node pred, int added, int realInsertionIndex)\r
+ {\r
+ if (views != null)\r
+ foreach (LinkedList<T> view in views)\r
+ {\r
+ if (view != this)\r
+ {\r
+#if HASHINDEX\r
+ if (pred.precedes(view.startsentinel) || (view.startsentinel == pred && view.size > 0))\r
+ view.offset += added;\r
+ if (view.startsentinel.precedes(pred) && succ.precedes(view.endsentinel))\r
+ view.size += added;\r
+ if (view.startsentinel == pred && view.size > 0)\r
+ view.startsentinel = succ.prev;\r
+ if (view.endsentinel == succ)\r
+ view.endsentinel = pred.next;\r
+#else\r
+ if (view.Offset == realInsertionIndex && view.size > 0)\r
+ view.startsentinel = succ.prev;\r
+ if (view.Offset + view.size == realInsertionIndex)\r
+ view.endsentinel = pred.next;\r
+ if (view.Offset < realInsertionIndex && view.Offset + view.size > realInsertionIndex)\r
+ view.size += added;\r
+ if (view.Offset > realInsertionIndex || (view.Offset == realInsertionIndex && view.size > 0))\r
+ view.offset += added;\r
+#endif\r
+ }\r
+ }\r
+ }\r
+\r
+ void fixViewsBeforeSingleRemove(Node node, int realRemovalIndex)\r
+ {\r
+ if (views != null)\r
+ foreach (LinkedList<T> view in views)\r
+ {\r
+ if (view != this)\r
+ {\r
+#if HASHINDEX\r
+ if (view.startsentinel.precedes(node) && node.precedes(view.endsentinel))\r
+ view.size--;\r
+ if (!view.startsentinel.precedes(node))\r
+ view.offset--;\r
+ if (view.startsentinel == node)\r
+ view.startsentinel = node.prev;\r
+ if (view.endsentinel == node)\r
+ view.endsentinel = node.next;\r
+#else\r
+ if (view.offset - 1 == realRemovalIndex)\r
+ view.startsentinel = node.prev;\r
+ if (view.offset + view.size == realRemovalIndex)\r
+ view.endsentinel = node.next;\r
+ if (view.offset <= realRemovalIndex && view.offset + view.size > realRemovalIndex)\r
+ view.size--;\r
+ if (view.offset > realRemovalIndex)\r
+ view.offset--;\r
+#endif\r
+ }\r
+ }\r
+ }\r
+\r
+#if HASHINDEX\r
+#else\r
+ void fixViewsBeforeRemove(int start, int count, Node first, Node last)\r
+ {\r
+ int clearend = start + count - 1;\r
+ if (views != null)\r
+ foreach (LinkedList<T> view in views)\r
+ {\r
+ if (view == this)\r
+ continue;\r
+ int viewoffset = view.Offset, viewend = viewoffset + view.size - 1;\r
+ //sentinels\r
+ if (start < viewoffset && viewoffset - 1 <= clearend)\r
+ view.startsentinel = first.prev;\r
+ if (start <= viewend + 1 && viewend < clearend)\r
+ view.endsentinel = last.next;\r
+ //offsets and sizes\r
+ if (start < viewoffset)\r
+ {\r
+ if (clearend < viewoffset)\r
+ view.offset = viewoffset - count;\r
+ else\r
+ {\r
+ view.offset = start;\r
+ view.size = clearend < viewend ? viewend - clearend : 0;\r
+ }\r
+ }\r
+ else if (start <= viewend)\r
+ view.size = clearend <= viewend ? view.size - count : start - viewoffset;\r
+ }\r
+ }\r
+#endif\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <param name="otherView"></param>\r
+ /// <returns>The position of View(otherOffset, otherSize) wrt. this view</returns>\r
+ MutualViewPosition viewPosition(LinkedList<T> otherView)\r
+ {\r
+#if HASHINDEX\r
+ Node otherstartsentinel = otherView.startsentinel, otherendsentinel = otherView.endsentinel,\r
+ first = startsentinel.next, last = endsentinel.prev,\r
+ otherfirst = otherstartsentinel.next, otherlast = otherendsentinel.prev;\r
+ if (last.precedes(otherfirst) || otherlast.precedes(first))\r
+ return MutualViewPosition.NonOverlapping;\r
+ if (size == 0 || (otherstartsentinel.precedes(first) && last.precedes(otherendsentinel)))\r
+ return MutualViewPosition.Contains;\r
+ if (otherView.size == 0 || (startsentinel.precedes(otherfirst) && otherlast.precedes(endsentinel)))\r
+ return MutualViewPosition.ContainedIn;\r
+ return MutualViewPosition.Overlapping;\r
+#else\r
+ int end = offset + size, otherOffset = otherView.offset, otherSize = otherView.size, otherEnd = otherOffset + otherSize;\r
+ if (otherOffset >= end || otherEnd <= offset)\r
+ return MutualViewPosition.NonOverlapping;\r
+ if (size == 0 || (otherOffset <= offset && end <= otherEnd))\r
+ return MutualViewPosition.Contains;\r
+ if (otherSize == 0 || (offset <= otherOffset && otherEnd <= end))\r
+ return MutualViewPosition.ContainedIn;\r
+ return MutualViewPosition.Overlapping;\r
+#endif\r
+ }\r
+\r
+ void disposeOverlappingViews(bool reverse)\r
+ {\r
+ if (views != null)\r
+ {\r
+ foreach (LinkedList<T> view in views)\r
+ {\r
+ if (view != this)\r
+ {\r
+ switch (viewPosition(view))\r
+ {\r
+ case MutualViewPosition.ContainedIn:\r
+ if (reverse)\r
+ { }\r
+ else\r
+ view.Dispose();\r
+ break;\r
+ case MutualViewPosition.Overlapping:\r
+ view.Dispose();\r
+ break;\r
+ case MutualViewPosition.Contains:\r
+ case MutualViewPosition.NonOverlapping:\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ }\r
+\r
+ #endregion\r
+\r
+ #endregion\r
+\r
+ #region Constructors\r
+\r
+ /// <summary>\r
+ /// Create a linked list with en external item equalityComparer\r
+ /// </summary>\r
+ /// <param name="itemequalityComparer">The external equalityComparer</param>\r
+ public LinkedList(SCG.IEqualityComparer<T> itemequalityComparer)\r
+ : base(itemequalityComparer)\r
+ {\r
+ offset = 0;\r
+ size = stamp = 0;\r
+ startsentinel = new Node(default(T));\r
+ endsentinel = new Node(default(T));\r
+ startsentinel.next = endsentinel;\r
+ endsentinel.prev = startsentinel;\r
+#if HASHINDEX\r
+ //It is important that the sentinels are different:\r
+ startsentinel.taggroup = new TagGroup();\r
+ startsentinel.taggroup.tag = int.MinValue;\r
+ startsentinel.taggroup.count = 0;\r
+ endsentinel.taggroup = new TagGroup();\r
+ endsentinel.taggroup.tag = int.MaxValue;\r
+ endsentinel.taggroup.count = 0;\r
+ dict = new HashDictionary<T, Node>(itemequalityComparer);\r
+#endif\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create a linked list with the natural item equalityComparer\r
+ /// </summary>\r
+ public LinkedList() : this(EqualityComparer<T>.Default) { }\r
+\r
+ #endregion\r
+\r
+ #region Node nested class\r
+\r
+ /// <summary>\r
+ /// An individual cell in the linked list\r
+ /// </summary>\r
+ [Serializable]\r
+ class Node\r
+ {\r
+ public Node prev;\r
+\r
+ public Node next;\r
+\r
+ public T item;\r
+\r
+ #region Tag support\r
+#if HASHINDEX\r
+ internal int tag;\r
+\r
+ internal TagGroup taggroup;\r
+\r
+ internal bool precedes(Node that)\r
+ {\r
+ //Debug.Assert(taggroup != null, "taggroup field null");\r
+ //Debug.Assert(that.taggroup != null, "that.taggroup field null");\r
+ int t1 = taggroup.tag;\r
+ int t2 = that.taggroup.tag;\r
+\r
+ return t1 < t2 ? true : t1 > t2 ? false : tag < that.tag;\r
+ }\r
+#endif\r
+ #endregion\r
+\r
+ [Tested]\r
+ internal Node(T item) { this.item = item; }\r
+\r
+ [Tested]\r
+ internal Node(T item, Node prev, Node next)\r
+ {\r
+ this.item = item; this.prev = prev; this.next = next;\r
+ }\r
+\r
+ public override string ToString()\r
+ {\r
+#if HASHINDEX\r
+ return String.Format("Node: (item={0}, tag={1})", item, tag);\r
+#else\r
+ return String.Format("Node(item={0})", item);\r
+#endif\r
+ }\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region Taggroup nested class and tag maintenance utilities\r
+#if HASHINDEX\r
+ /// <summary>\r
+ /// A group of nodes with the same high tag. Purpose is to be\r
+ /// able to tell the sequence order of two nodes without having to scan through\r
+ /// the list.\r
+ /// </summary>\r
+ [Serializable]\r
+ class TagGroup\r
+ {\r
+ internal int tag, count;\r
+\r
+ internal Node first, last;\r
+\r
+ /// <summary>\r
+ /// Pretty print a tag group\r
+ /// </summary>\r
+ /// <returns>Formatted tag group</returns>\r
+ public override string ToString()\r
+ { return String.Format("TagGroup(tag={0}, cnt={1}, fst={2}, lst={3})", tag, count, first, last); }\r
+ }\r
+\r
+ //Constants for tag maintenance\r
+ const int wordsize = 32;\r
+\r
+ const int lobits = 3;\r
+\r
+ const int hibits = lobits + 1;\r
+\r
+ const int losize = 1 << lobits;\r
+\r
+ const int hisize = 1 << hibits;\r
+\r
+ const int logwordsize = 5;\r
+\r
+ TagGroup gettaggroup(Node pred, Node succ, out int lowbound, out int highbound)\r
+ {\r
+ TagGroup predgroup = pred.taggroup, succgroup = succ.taggroup;\r
+\r
+ if (predgroup == succgroup)\r
+ {\r
+ lowbound = pred.tag + 1;\r
+ highbound = succ.tag - 1;\r
+ return predgroup;\r
+ }\r
+ else if (predgroup.first != null)\r
+ {\r
+ lowbound = pred.tag + 1;\r
+ highbound = int.MaxValue;\r
+ return predgroup;\r
+ }\r
+ else if (succgroup.first != null)\r
+ {\r
+ lowbound = int.MinValue;\r
+ highbound = succ.tag - 1;\r
+ return succgroup;\r
+ }\r
+ else\r
+ {\r
+ lowbound = int.MinValue;\r
+ highbound = int.MaxValue;\r
+ return new TagGroup();\r
+ }\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Put a tag on a node (already inserted in the list). Split taggroups and renumber as \r
+ /// necessary.\r
+ /// </summary>\r
+ /// <param name="node">The node to tag</param>\r
+ void settag(Node node)\r
+ {\r
+ Node pred = node.prev, succ = node.next;\r
+ TagGroup predgroup = pred.taggroup, succgroup = succ.taggroup;\r
+\r
+ if (predgroup == succgroup)\r
+ {\r
+ node.taggroup = predgroup;\r
+ predgroup.count++;\r
+ if (pred.tag + 1 == succ.tag)\r
+ splittaggroup(predgroup);\r
+ else\r
+ node.tag = (pred.tag + 1) / 2 + (succ.tag - 1) / 2;\r
+ }\r
+ else if (predgroup.first != null)\r
+ {\r
+ node.taggroup = predgroup;\r
+ predgroup.last = node;\r
+ predgroup.count++;\r
+ if (pred.tag == int.MaxValue)\r
+ splittaggroup(predgroup);\r
+ else\r
+ node.tag = pred.tag / 2 + int.MaxValue / 2 + 1;\r
+ }\r
+ else if (succgroup.first != null)\r
+ {\r
+ node.taggroup = succgroup;\r
+ succgroup.first = node;\r
+ succgroup.count++;\r
+ if (succ.tag == int.MinValue)\r
+ splittaggroup(node.taggroup);\r
+ else\r
+ node.tag = int.MinValue / 2 + (succ.tag - 1) / 2;\r
+ }\r
+ else\r
+ {\r
+ Debug.Assert(Taggroups == 0);\r
+\r
+ TagGroup newgroup = new TagGroup();\r
+\r
+ Taggroups = 1;\r
+ node.taggroup = newgroup;\r
+ newgroup.first = newgroup.last = node;\r
+ newgroup.count = 1;\r
+ return;\r
+ }\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Remove a node from its taggroup.\r
+ /// <br/> When this is called, node must already have been removed from the underlying list\r
+ /// </summary>\r
+ /// <param name="node">The node to remove</param>\r
+ void removefromtaggroup(Node node)\r
+ {\r
+ //\r
+ TagGroup taggroup = node.taggroup;\r
+\r
+ if (--taggroup.count == 0)\r
+ {\r
+ Taggroups--;\r
+ return;\r
+ }\r
+\r
+ if (node == taggroup.first)\r
+ taggroup.first = node.next;\r
+\r
+ if (node == taggroup.last)\r
+ taggroup.last = node.prev;\r
+\r
+ //node.taggroup = null;\r
+ if (taggroup.count != losize || Taggroups == 1)\r
+ return;\r
+\r
+ TagGroup otg;\r
+\r
+ if ((otg = taggroup.first.prev.taggroup).count <= losize)\r
+ taggroup.first = otg.first;\r
+ else if ((otg = taggroup.last.next.taggroup).count <= losize)\r
+ taggroup.last = otg.last;\r
+ else\r
+ return;\r
+\r
+ Node n = otg.first;\r
+\r
+ for (int i = 0, length = otg.count; i < length; i++)\r
+ {\r
+ n.taggroup = taggroup;\r
+ n = n.next;\r
+ }\r
+\r
+ taggroup.count += otg.count;\r
+ Taggroups--;\r
+ n = taggroup.first;\r
+\r
+ const int ofs = wordsize - hibits;\r
+\r
+ for (int i = 0, count = taggroup.count; i < count; i++)\r
+ {\r
+ n.tag = (i - losize) << ofs; //(i-8)<<28 \r
+ n = n.next;\r
+ }\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Split a tag group to make rom for more tags.\r
+ /// </summary>\r
+ /// <param name="taggroup">The tag group</param>\r
+ void splittaggroup(TagGroup taggroup)\r
+ {\r
+ Node n = taggroup.first;\r
+ int ptgt = taggroup.first.prev.taggroup.tag;\r
+ int ntgt = taggroup.last.next.taggroup.tag;\r
+\r
+ Debug.Assert(ptgt + 1 <= ntgt - 1);\r
+\r
+ int ofs = wordsize - hibits;\r
+#warning hack alert was there a -1 here?\r
+ int newtgs = taggroup.count / hisize;// - 1;\r
+ int tgtdelta = (int)((ntgt + 0.0 - ptgt) / (newtgs + 2)), tgtag = ptgt;\r
+\r
+ tgtdelta = tgtdelta == 0 ? 1 : tgtdelta;\r
+ for (int j = 0; j < newtgs; j++)\r
+ {\r
+ TagGroup newtaggroup = new TagGroup();\r
+\r
+ newtaggroup.tag = (tgtag = tgtag >= ntgt - tgtdelta ? ntgt : tgtag + tgtdelta);\r
+ newtaggroup.first = n;\r
+ newtaggroup.count = hisize;\r
+ for (int i = 0; i < hisize; i++)\r
+ {\r
+ n.taggroup = newtaggroup;\r
+ n.tag = (i - losize) << ofs; //(i-8)<<28 \r
+ n = n.next;\r
+ }\r
+\r
+ newtaggroup.last = n.prev;\r
+ }\r
+\r
+ int rest = taggroup.count - hisize * newtgs;\r
+\r
+ taggroup.first = n;\r
+ taggroup.count = rest;\r
+ taggroup.tag = (tgtag = tgtag >= ntgt - tgtdelta ? ntgt : tgtag + tgtdelta); ofs--;\r
+ for (int i = 0; i < rest; i++)\r
+ {\r
+ n.tag = (i - hisize) << ofs; //(i-16)<<27 \r
+ n = n.next;\r
+ }\r
+\r
+ taggroup.last = n.prev;\r
+ Taggroups += newtgs;\r
+ if (tgtag == ntgt)\r
+ redistributetaggroups(taggroup);\r
+ }\r
+\r
+\r
+ private void redistributetaggroups(TagGroup taggroup)\r
+ {\r
+ TagGroup pred = taggroup, succ = taggroup, tmp;\r
+ double limit = 1, bigt = Math.Pow(Taggroups, 1.0 / 30);//?????\r
+ int bits = 1, count = 1, lowmask = 0, himask = 0, target = 0;\r
+\r
+ do\r
+ {\r
+ bits++;\r
+ lowmask = (1 << bits) - 1;\r
+ himask = ~lowmask;\r
+ target = taggroup.tag & himask;\r
+ while ((tmp = pred.first.prev.taggroup).first != null && (tmp.tag & himask) == target)\r
+ { count++; pred = tmp; }\r
+\r
+ while ((tmp = succ.last.next.taggroup).last != null && (tmp.tag & himask) == target)\r
+ { count++; succ = tmp; }\r
+\r
+ limit *= bigt;\r
+ } while (count > limit);\r
+\r
+ //redistibute tags\r
+ int lob = pred.first.prev.taggroup.tag, upb = succ.last.next.taggroup.tag;\r
+ int delta = upb / (count + 1) - lob / (count + 1);\r
+\r
+ Debug.Assert(delta > 0);\r
+ for (int i = 0; i < count; i++)\r
+ {\r
+ pred.tag = lob + (i + 1) * delta;\r
+ pred = pred.last.next.taggroup;\r
+ }\r
+ }\r
+#endif\r
+\r
+ #endregion\r
+\r
+ #region Position, PositionComparer and ViewHandler nested types\r
+ class PositionComparer : SCG.IComparer<Position>\r
+ {\r
+ static PositionComparer _default;\r
+ PositionComparer() { }\r
+ public static PositionComparer Default { get { return _default ?? (_default = new PositionComparer()); } }\r
+ public int Compare(Position a, Position b)\r
+ {\r
+#if HASHINDEX\r
+ return a.Endpoint == b.Endpoint ? 0 : a.Endpoint.precedes(b.Endpoint) ? -1 : 1;\r
+#else\r
+ return a.Index.CompareTo(b.Index);\r
+#endif\r
+ }\r
+ }\r
+ /// <summary>\r
+ /// During RemoveAll, we need to cache the original endpoint indices of views\r
+ /// </summary>\r
+ struct Position\r
+ {\r
+ public readonly LinkedList<T> View;\r
+ public bool Left;\r
+#if HASHINDEX\r
+ public readonly Node Endpoint;\r
+#else\r
+ public readonly int Index;\r
+#endif\r
+ public Position(LinkedList<T> view, bool left)\r
+ {\r
+ View = view;\r
+ Left = left;\r
+#if HASHINDEX\r
+ Endpoint = left ? view.startsentinel.next : view.endsentinel.prev;\r
+#else\r
+ Index = left ? view.Offset : view.Offset + view.size - 1;\r
+#endif\r
+ }\r
+#if HASHINDEX\r
+ public Position(Node node, int foo) { this.Endpoint = node; View = null; Left = false;}\r
+#else\r
+ public Position(int index) { this.Index = index; View = null; Left = false; }\r
+#endif\r
+ }\r
+\r
+ //TODO: merge the two implementations using Position values as arguments\r
+ /// <summary>\r
+ /// Handle the update of (other) views during a multi-remove operation.\r
+ /// </summary>\r
+ struct ViewHandler\r
+ {\r
+ ArrayList<Position> leftEnds;\r
+ ArrayList<Position> rightEnds;\r
+ int leftEndIndex, rightEndIndex, leftEndIndex2, rightEndIndex2;\r
+ internal readonly int viewCount;\r
+ internal ViewHandler(LinkedList<T> list)\r
+ {\r
+ leftEndIndex = rightEndIndex = leftEndIndex2 = rightEndIndex2 = viewCount = 0;\r
+ leftEnds = rightEnds = null;\r
+ if (list.views != null)\r
+ foreach (LinkedList<T> v in list.views)\r
+ if (v != list)\r
+ {\r
+ if (leftEnds == null)\r
+ {\r
+ leftEnds = new ArrayList<Position>();\r
+ rightEnds = new ArrayList<Position>();\r
+ }\r
+ leftEnds.Add(new Position(v, true));\r
+ rightEnds.Add(new Position(v, false));\r
+ }\r
+ if (leftEnds == null)\r
+ return;\r
+ viewCount = leftEnds.Count;\r
+ leftEnds.Sort(PositionComparer.Default);\r
+ rightEnds.Sort(PositionComparer.Default);\r
+ }\r
+#if HASHINDEX\r
+ internal void skipEndpoints(int removed, Node n)\r
+ {\r
+ if (viewCount > 0)\r
+ {\r
+ Position endpoint;\r
+ while (leftEndIndex < viewCount && ((endpoint = leftEnds[leftEndIndex]).Endpoint.prev.precedes(n)))\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.offset = view.offset - removed;//TODO: extract offset.Value?\r
+ view.size += removed;\r
+ leftEndIndex++;\r
+ }\r
+ while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Endpoint.precedes(n))\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.size -= removed;\r
+ rightEndIndex++;\r
+ }\r
+ }\r
+ if (viewCount > 0)\r
+ {\r
+ Position endpoint;\r
+ while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Endpoint.prev.precedes(n))\r
+ leftEndIndex2++;\r
+ while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Endpoint.next.precedes(n))\r
+ rightEndIndex2++;\r
+ }\r
+ }\r
+ /// <summary>\r
+ /// To be called with n pointing to the right of each node to be removed in a stretch. \r
+ /// And at the endsentinel. \r
+ /// \r
+ /// Update offset of a view whose left endpoint (has not already been handled and) is n or precedes n.\r
+ /// I.e. startsentinel precedes n.\r
+ /// Also update the size as a prelude to handling the right endpoint.\r
+ /// \r
+ /// Update size of a view not already handled and whose right endpoint precedes n.\r
+ /// </summary>\r
+ /// <param name="removed">The number of nodes left of n to be removed</param>\r
+ /// <param name="n"></param>\r
+ internal void updateViewSizesAndCounts(int removed, Node n)\r
+ {\r
+ if (viewCount > 0)\r
+ {\r
+ Position endpoint;\r
+ while (leftEndIndex < viewCount && ((endpoint = leftEnds[leftEndIndex]).Endpoint.prev.precedes(n)))\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.offset = view.offset - removed; //TODO: fix use of offset\r
+ view.size += removed;\r
+ leftEndIndex++;\r
+ }\r
+ while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Endpoint.precedes(n))\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.size -= removed;\r
+ rightEndIndex++;\r
+ }\r
+ }\r
+ }\r
+ /// <summary>\r
+ /// To be called with n being the first not-to-be-removed node after a (stretch of) node(s) to be removed.\r
+ /// \r
+ /// It will update the startsentinel of views (that have not been handled before and) \r
+ /// whose startsentinel precedes n, i.e. is to be deleted.\r
+ /// \r
+ /// It will update the endsentinel of views (...) whose endsentinel precedes n, i.e. is to be deleted.\r
+ /// \r
+ /// PROBLEM: DOESNT WORK AS ORIGINALLY ADVERTISED. WE MUST DO THIS BEFORE WE ACTUALLY REMOVE THE NODES. WHEN THE \r
+ /// NODES HAVE BEEN REMOVED, THE precedes METHOD WILL NOT WORK!\r
+ /// </summary>\r
+ /// <param name="n"></param>\r
+ /// <param name="newstart"></param>\r
+ /// <param name="newend"></param>\r
+ internal void updateSentinels(Node n, Node newstart, Node newend)\r
+ {\r
+ if (viewCount > 0)\r
+ {\r
+ Position endpoint;\r
+ while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Endpoint.prev.precedes(n))\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.startsentinel = newstart;\r
+ leftEndIndex2++;\r
+ }\r
+ while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Endpoint.next.precedes(n))\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.endsentinel = newend;\r
+ rightEndIndex2++;\r
+ }\r
+ }\r
+ }\r
+#else\r
+ /// <summary>\r
+ /// This is to be called with realindex pointing to the first node to be removed after a (stretch of) node that was not removed\r
+ /// </summary>\r
+ /// <param name="removed"></param>\r
+ /// <param name="realindex"></param>\r
+ internal void skipEndpoints(int removed, int realindex)\r
+ {\r
+ if (viewCount > 0)\r
+ {\r
+ Position endpoint;\r
+ while (leftEndIndex < viewCount && (endpoint = leftEnds[leftEndIndex]).Index <= realindex)\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.offset = view.offset - removed;\r
+ view.size += removed;\r
+ leftEndIndex++;\r
+ }\r
+ while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Index < realindex)\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.size -= removed;\r
+ rightEndIndex++;\r
+ }\r
+ }\r
+ if (viewCount > 0)\r
+ {\r
+ Position endpoint;\r
+ while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Index <= realindex)\r
+ leftEndIndex2++;\r
+ while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Index < realindex - 1)\r
+ rightEndIndex2++;\r
+ }\r
+ }\r
+ internal void updateViewSizesAndCounts(int removed, int realindex)\r
+ {\r
+ if (viewCount > 0)\r
+ {\r
+ Position endpoint;\r
+ while (leftEndIndex < viewCount && (endpoint = leftEnds[leftEndIndex]).Index <= realindex)\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.offset = view.Offset - removed;\r
+ view.size += removed;\r
+ leftEndIndex++;\r
+ }\r
+ while (rightEndIndex < viewCount && (endpoint = rightEnds[rightEndIndex]).Index < realindex)\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.size -= removed;\r
+ rightEndIndex++;\r
+ }\r
+ }\r
+ }\r
+ internal void updateSentinels(int realindex, Node newstart, Node newend)\r
+ {\r
+ if (viewCount > 0)\r
+ {\r
+ Position endpoint;\r
+ while (leftEndIndex2 < viewCount && (endpoint = leftEnds[leftEndIndex2]).Index <= realindex)\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.startsentinel = newstart;\r
+ leftEndIndex2++;\r
+ }\r
+ while (rightEndIndex2 < viewCount && (endpoint = rightEnds[rightEndIndex2]).Index < realindex - 1)\r
+ {\r
+ LinkedList<T> view = endpoint.View;\r
+ view.endsentinel = newend;\r
+ rightEndIndex2++;\r
+ }\r
+ }\r
+ }\r
+#endif\r
+ }\r
+ #endregion\r
+\r
+ #region Range nested class\r
+\r
+ class Range : DirectedCollectionValueBase<T>, IDirectedCollectionValue<T>\r
+ {\r
+ int start, count, rangestamp;\r
+ Node startnode, endnode;\r
+\r
+ LinkedList<T> list;\r
+\r
+ bool forwards;\r
+\r
+\r
+ internal Range(LinkedList<T> list, int start, int count, bool forwards)\r
+ {\r
+ this.list = list; this.rangestamp = list.underlying != null ? list.underlying.stamp : list.stamp;\r
+ this.start = start; this.count = count; this.forwards = forwards;\r
+ if (count > 0)\r
+ {\r
+ startnode = list.get(start);\r
+ endnode = list.get(start + count - 1);\r
+ }\r
+ }\r
+\r
+ public override bool IsEmpty { get { list.modifycheck(rangestamp); return count == 0; } }\r
+\r
+ [Tested]\r
+ public override int Count { [Tested]get { list.modifycheck(rangestamp); return count; } }\r
+\r
+\r
+ public override Speed CountSpeed { get { list.modifycheck(rangestamp); return Speed.Constant; } }\r
+\r
+\r
+ public override T Choose()\r
+ {\r
+ list.modifycheck(rangestamp);\r
+ if (count > 0) return startnode.item;\r
+ throw new NoSuchItemException();\r
+ }\r
+\r
+\r
+ [Tested]\r
+ public override SCG.IEnumerator<T> GetEnumerator()\r
+ {\r
+ int togo = count;\r
+\r
+ list.modifycheck(rangestamp);\r
+ if (togo == 0)\r
+ yield break;\r
+\r
+ Node cursor = forwards ? startnode : endnode;\r
+\r
+ yield return cursor.item;\r
+ while (--togo > 0)\r
+ {\r
+ cursor = forwards ? cursor.next : cursor.prev;\r
+ list.modifycheck(rangestamp);\r
+ yield return cursor.item;\r
+ }\r
+ }\r
+\r
+\r
+ [Tested]\r
+ public override IDirectedCollectionValue<T> Backwards()\r
+ {\r
+ list.modifycheck(rangestamp);\r
+\r
+ Range b = (Range)MemberwiseClone();\r
+\r
+ b.forwards = !forwards;\r
+ return b;\r
+ }\r
+\r
+\r
+ [Tested]\r
+ IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); }\r
+\r
+\r
+ [Tested]\r
+ public override EnumerationDirection Direction\r
+ {\r
+ [Tested]\r
+ get\r
+ { return forwards ? EnumerationDirection.Forwards : EnumerationDirection.Backwards; }\r
+ }\r
+ }\r
+\r
+\r
+ #endregion\r
+\r
+ #region IDisposable Members\r
+\r
+ /// <summary>\r
+ /// Invalidate this list. If a view, just invalidate the view. \r
+ /// If not a view, invalidate the list and all views on it.\r
+ /// </summary>\r
+ public virtual void Dispose()\r
+ {\r
+ Dispose(false);\r
+ }\r
+\r
+ void Dispose(bool disposingUnderlying)\r
+ {\r
+ if (isValid)\r
+ {\r
+ if (underlying != null)\r
+ {\r
+ isValid = false;\r
+ if (!disposingUnderlying)\r
+ views.Remove(myWeakReference);\r
+ endsentinel = null;\r
+ startsentinel = null;\r
+ underlying = null;\r
+ views = null;\r
+ myWeakReference = null;\r
+ }\r
+ else\r
+ {\r
+ //isValid = false;\r
+ //endsentinel = null;\r
+ //startsentinel = null;\r
+ foreach (LinkedList<T> view in views)\r
+ view.Dispose(true);\r
+ //views = null;\r
+ Clear();\r
+ }\r
+ }\r
+ }\r
+\r
+ #endregion IDisposable stuff\r
+\r
+ #region IList<T> Members\r
+\r
+ /// <summary>\r
+ /// </summary>\r
+ /// <exception cref="NoSuchItemException"> if this list is empty.</exception>\r
+ /// <value>The first item in this list.</value>\r
+ [Tested]\r
+ public virtual T First\r
+ {\r
+ [Tested]\r
+ get\r
+ {\r
+ validitycheck();\r
+ if (size == 0)\r
+ throw new NoSuchItemException();\r
+ return startsentinel.next.item;\r
+ }\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// </summary>\r
+ /// <exception cref="NoSuchItemException"> if this list is empty.</exception>\r
+ /// <value>The last item in this list.</value>\r
+ [Tested]\r
+ public virtual T Last\r
+ {\r
+ [Tested]\r
+ get\r
+ {\r
+ validitycheck();\r
+ if (size == 0)\r
+ throw new NoSuchItemException();\r
+ return endsentinel.prev.item;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Since <code>Add(T item)</code> always add at the end of the list,\r
+ /// this describes if list has FIFO or LIFO semantics.\r
+ /// </summary>\r
+ /// <value>True if the <code>Remove()</code> operation removes from the\r
+ /// start of the list, false if it removes from the end. THe default for a new linked list is true.</value>\r
+ [Tested]\r
+ public virtual bool FIFO\r
+ {\r
+ [Tested]\r
+ get { validitycheck(); return fIFO; }\r
+ [Tested]\r
+ set { updatecheck(); fIFO = value; }\r
+ }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ public virtual bool IsFixedSize\r
+ {\r
+ get { validitycheck(); return false; }\r
+ }\r
+\r
+ /// <summary>\r
+ /// On this list, this indexer is read/write.\r
+ /// <exception cref="IndexOutOfRangeException"/> if i is negative or\r
+ /// >= the size of the collection.\r
+ /// </summary>\r
+ /// <value>The i'th item of this list.</value>\r
+ /// <param name="index">The index of the item to fetch or store.</param>\r
+ [Tested]\r
+ public virtual T this[int index]\r
+ {\r
+ [Tested]\r
+ get { validitycheck(); return get(index).item; }\r
+ [Tested]\r
+ set\r
+ {\r
+ updatecheck();\r
+ Node n = get(index);\r
+ //\r
+ T item = n.item;\r
+#if HASHINDEX\r
+\r
+ if (itemequalityComparer.Equals(value, item))\r
+ {\r
+ n.item = value;\r
+ dict.Update(value, n);\r
+ }\r
+ else if (!dict.FindOrAdd(value, ref n))\r
+ {\r
+ dict.Remove(item);\r
+ n.item = value;\r
+ }\r
+ else\r
+ throw new ArgumentException("Item already in indexed list");\r
+#else\r
+ n.item = value;\r
+#endif\r
+ (underlying ?? this).raiseForSetThis(index, value, item);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <value></value>\r
+ public virtual Speed IndexingSpeed { get { return Speed.Linear; } }\r
+\r
+ /// <summary>\r
+ /// Insert an item at a specific index location in this list. \r
+ /// <exception cref="IndexOutOfRangeException"/> if i is negative or\r
+ /// > the size of the collection.</summary>\r
+ /// <param name="i">The index at which to insert.</param>\r
+ /// <param name="item">The item to insert.</param>\r
+ [Tested]\r
+ public virtual void Insert(int i, T item)\r
+ {\r
+ updatecheck();\r
+ insert(i, i == size ? endsentinel : get(i), item);\r
+ if (ActiveEvents != EventTypeEnum.None)\r
+ (underlying ?? this).raiseForInsert(i + Offset, item);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Insert an item at the end of a compatible view, used as a pointer.\r
+ /// <para>The <code>pointer</code> must be a view on the same list as\r
+ /// <code>this</code> and the endpoitn of <code>pointer</code> must be\r
+ /// a valid insertion point of <code>this</code></para>\r
+ /// </summary>\r
+ /// <exception cref="IncompatibleViewException">If <code>pointer</code> \r
+ /// is not a view on the same list as <code>this</code></exception>\r
+ /// <exception cref="IndexOutOfRangeException"><b>??????</b> if the endpoint of \r
+ /// <code>pointer</code> is not inside <code>this</code></exception>\r
+ /// <exception cref="DuplicateNotAllowedException"> if the list has\r
+ /// <code>AllowsDuplicates==false</code> and the item is \r
+ /// already in the list.</exception>\r
+ /// <param name="pointer"></param>\r
+ /// <param name="item"></param>\r
+ public void Insert(IList<T> pointer, T item)\r
+ {\r
+ updatecheck();\r
+ if ((pointer == null) || ((pointer.Underlying ?? pointer) != (underlying ?? this)))\r
+ throw new IncompatibleViewException();\r
+#warning INEFFICIENT\r
+ //TODO: make this efficient (the whole point of the method:\r
+ //Do NOT use Insert, but insert the node at pointer.endsentinel, checking\r
+ //via the ordering that this is a valid insertion point\r
+ Insert(pointer.Offset + pointer.Count - Offset, item);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Insert into this list all items from an enumerable collection starting \r
+ /// at a particular index.\r
+ /// <exception cref="IndexOutOfRangeException"/> if i is negative or\r
+ /// > the size of the collection.\r
+ /// </summary>\r
+ /// <param name="i">Index to start inserting at</param>\r
+ /// <param name="items">Items to insert</param>\r
+ /// <typeparam name="U"></typeparam>\r
+ [Tested]\r
+ public virtual void InsertAll<U>(int i, SCG.IEnumerable<U> items) where U : T\r
+ {\r
+ insertAll(i, items, true);\r
+ }\r
+\r
+ void insertAll<U>(int i, SCG.IEnumerable<U> items, bool insertion) where U : T\r
+ {\r
+ updatecheck();\r
+ Node succ, node, pred;\r
+ int count = 0;\r
+ succ = i == size ? endsentinel : get(i);\r
+ pred = node = succ.prev;\r
+#if HASHINDEX\r
+ TagGroup taggroup = null;\r
+ int taglimit = 0, thetag = 0;\r
+ taggroup = gettaggroup(node, succ, out thetag, out taglimit);\r
+ try\r
+ {\r
+ foreach (T item in items)\r
+ {\r
+ Node tmp = new Node(item, node, null);\r
+ if (!dict.FindOrAdd(item, ref tmp))\r
+ {\r
+ tmp.tag = thetag < taglimit ? ++thetag : thetag;\r
+ tmp.taggroup = taggroup;\r
+ node.next = tmp;\r
+ count++;\r
+ node = tmp;\r
+ }\r
+ else\r
+ throw new DuplicateNotAllowedException("Item already in indexed list");\r
+ }\r
+ }\r
+ finally\r
+ {\r
+ taggroup.count += count;\r
+ taggroup.first = succ.prev;\r
+ taggroup.last = node;\r
+ succ.prev = node;\r
+ node.next = succ;\r
+ if (node.tag == node.prev.tag)\r
+ splittaggroup(taggroup);\r
+ size += count;\r
+ if (underlying != null)\r
+ underlying.size += count;\r
+ if (count > 0)\r
+ {\r
+ fixViewsAfterInsert(succ, pred, count, 0);\r
+ raiseForInsertAll(pred, i, count, insertion);\r
+ }\r
+ }\r
+#else\r
+ foreach (T item in items)\r
+ {\r
+ Node tmp = new Node(item, node, null);\r
+ node.next = tmp;\r
+ count++;\r
+ node = tmp;\r
+ }\r
+ if (count == 0)\r
+ return;\r
+ succ.prev = node;\r
+ node.next = succ;\r
+ size += count;\r
+ if (underlying != null)\r
+ underlying.size += count;\r
+ if (count > 0)\r
+ {\r
+ fixViewsAfterInsert(succ, pred, count, offset + i);\r
+ raiseForInsertAll(pred, i, count, insertion);\r
+ }\r
+#endif\r
+ }\r
+\r
+ private void raiseForInsertAll(Node node, int i, int added, bool insertion)\r
+ {\r
+ if (ActiveEvents != 0)\r
+ {\r
+ int index = Offset + i;\r
+ if ((ActiveEvents & (EventTypeEnum.Added | EventTypeEnum.Inserted)) != 0)\r
+ for (int j = index; j < index + added; j++)\r
+ {\r
+#warning must we check stamps here?\r
+ node = node.next;\r
+ T item = node.item;\r
+ if (insertion) raiseItemInserted(item, j);\r
+ raiseItemsAdded(item, 1);\r
+ }\r
+ raiseCollectionChanged();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Insert an item at the front of this list.\r
+ /// </summary>\r
+ /// <param name="item">The item to insert.</param>\r
+ [Tested]\r
+ public virtual void InsertFirst(T item)\r
+ {\r
+ updatecheck();\r
+ insert(0, startsentinel.next, item);\r
+ if (ActiveEvents != EventTypeEnum.None)\r
+ (underlying ?? this).raiseForInsert(0 + Offset, item);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Insert an item at the back of this list.\r
+ /// </summary>\r
+ /// <param name="item">The item to insert.</param>\r
+ [Tested]\r
+ public virtual void InsertLast(T item)\r
+ {\r
+ updatecheck();\r
+ insert(size, endsentinel, item);\r
+ if (ActiveEvents != EventTypeEnum.None)\r
+ (underlying ?? this).raiseForInsert(size - 1 + Offset, item);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create a new list consisting of the results of mapping all items of this\r
+ /// list.\r
+ /// </summary>\r
+ /// <param name="mapper">The delegate definging the map.</param>\r
+ /// <returns>The new list.</returns>\r
+ [Tested]\r
+ public IList<V> Map<V>(Fun<T, V> mapper)\r
+ {\r
+ validitycheck();\r
+\r
+ LinkedList<V> retval = new LinkedList<V>();\r
+ return map<V>(mapper, retval);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create a new list consisting of the results of mapping all items of this\r
+ /// list. The new list will use a specified equalityComparer for the item type.\r
+ /// </summary>\r
+ /// <typeparam name="V">The type of items of the new list</typeparam>\r
+ /// <param name="mapper">The delegate defining the map.</param>\r
+ /// <param name="equalityComparer">The equalityComparer to use for the new list</param>\r
+ /// <returns>The new list.</returns>\r
+ public IList<V> Map<V>(Fun<T, V> mapper, SCG.IEqualityComparer<V> equalityComparer)\r
+ {\r
+ validitycheck();\r
+\r
+ LinkedList<V> retval = new LinkedList<V>(equalityComparer);\r
+ return map<V>(mapper, retval);\r
+ }\r
+\r
+ private IList<V> map<V>(Fun<T, V> mapper, LinkedList<V> retval)\r
+ {\r
+ if (size == 0)\r
+ return retval;\r
+ int stamp = this.stamp;\r
+ Node cursor = startsentinel.next;\r
+ LinkedList<V>.Node mcursor = retval.startsentinel;\r
+\r
+#if HASHINDEX\r
+ double tagdelta = int.MaxValue / (size + 1.0);\r
+ int count = 1;\r
+ LinkedList<V>.TagGroup taggroup = null;\r
+ taggroup = new LinkedList<V>.TagGroup();\r
+ retval.taggroups = 1;\r
+ taggroup.count = size;\r
+#endif\r
+ while (cursor != endsentinel)\r
+ {\r
+ V v = mapper(cursor.item);\r
+ modifycheck(stamp);\r
+ mcursor.next = new LinkedList<V>.Node(v, mcursor, null);\r
+ cursor = cursor.next;\r
+ mcursor = mcursor.next;\r
+#if HASHINDEX\r
+ retval.dict.Add(v, mcursor);\r
+ mcursor.taggroup = taggroup;\r
+ mcursor.tag = (int)(tagdelta * count++);\r
+#endif\r
+ }\r
+\r
+ retval.endsentinel.prev = mcursor;\r
+ mcursor.next = retval.endsentinel;\r
+ retval.size = size;\r
+ return retval;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove one item from the list: from the front if <code>FIFO</code>\r
+ /// is true, else from the back.\r
+ /// <exception cref="NoSuchItemException"/> if this list is empty.\r
+ /// </summary>\r
+ /// <returns>The removed item.</returns>\r
+ [Tested]\r
+ public virtual T Remove()\r
+ {\r
+ updatecheck();\r
+ if (size == 0)\r
+ throw new NoSuchItemException("List is empty");\r
+ T item = fIFO ? remove(startsentinel.next, 0) : remove(endsentinel.prev, size - 1);\r
+#if HASHINDEX\r
+ dict.Remove(item);\r
+#endif\r
+ (underlying ?? this).raiseForRemove(item);\r
+ return item;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove one item from the front of the list.\r
+ /// <exception cref="NoSuchItemException"/> if this list is empty.\r
+ /// </summary>\r
+ /// <returns>The removed item.</returns>\r
+ [Tested]\r
+ public virtual T RemoveFirst()\r
+ {\r
+ updatecheck();\r
+ if (size == 0)\r
+ throw new NoSuchItemException("List is empty");\r
+\r
+ T item = remove(startsentinel.next, 0);\r
+#if HASHINDEX\r
+ dict.Remove(item);\r
+#endif\r
+ if (ActiveEvents != EventTypeEnum.None)\r
+ (underlying ?? this).raiseForRemoveAt(Offset, item);\r
+ return item;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove one item from the back of the list.\r
+ /// <exception cref="NoSuchItemException"/> if this list is empty.\r
+ /// </summary>\r
+ /// <returns>The removed item.</returns>\r
+ [Tested]\r
+ public virtual T RemoveLast()\r
+ {\r
+ updatecheck();\r
+ if (size == 0)\r
+ throw new NoSuchItemException("List is empty");\r
+\r
+ T item = remove(endsentinel.prev, size - 1);\r
+#if HASHINDEX\r
+ dict.Remove(item);\r
+#endif\r
+ if (ActiveEvents != EventTypeEnum.None)\r
+ (underlying ?? this).raiseForRemoveAt(size + Offset, item);\r
+ return item;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create a list view on this list. \r
+ /// </summary>\r
+ /// <exception cref="ArgumentOutOfRangeException"> if the start or count is negative</exception>\r
+ /// <exception cref="ArgumentException"> if the range does not fit within list.</exception>\r
+ /// <param name="start">The index in this list of the start of the view.</param>\r
+ /// <param name="count">The size of the view.</param>\r
+ /// <returns>The new list view.</returns>\r
+ [Tested]\r
+ public virtual IList<T> View(int start, int count)\r
+ {\r
+ checkRange(start, count);\r
+ validitycheck();\r
+ if (views == null)\r
+ views = new WeakViewList<LinkedList<T>>();\r
+ LinkedList<T> retval = (LinkedList<T>)MemberwiseClone();\r
+ retval.underlying = underlying != null ? underlying : this;\r
+ retval.offset = offset + start;\r
+ retval.size = count;\r
+ getPair(start - 1, start + count, out retval.startsentinel, out retval.endsentinel,\r
+ new int[] { -1, size }, new Node[] { startsentinel, endsentinel });\r
+ //retval.startsentinel = start == 0 ? startsentinel : get(start - 1);\r
+ //retval.endsentinel = start + count == size ? endsentinel : get(start + count);\r
+\r
+ //TODO: for the purpose of Dispose, we need to retain a ref to the node\r
+ retval.myWeakReference = views.Add(retval);\r
+ return retval;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create a list view on this list containing the (first) occurrence of a particular item. \r
+ /// </summary>\r
+ /// <exception cref="ArgumentException"> if the item is not in this list.</exception>\r
+ /// <param name="item">The item to find.</param>\r
+ /// <returns>The new list view.</returns>\r
+ public virtual IList<T> ViewOf(T item)\r
+ {\r
+#if HASHINDEX\r
+ Node n;\r
+ validitycheck();\r
+ if (!contains(item, out n))\r
+ return null;\r
+ LinkedList<T> retval = (LinkedList<T>)MemberwiseClone();\r
+ retval.underlying = underlying != null ? underlying : this;\r
+ retval.offset = null;\r
+ retval.startsentinel = n.prev;\r
+ retval.endsentinel = n.next;\r
+ retval.size = 1;\r
+ return retval;\r
+#else\r
+ int index = 0;\r
+ Node n = startsentinel.next;\r
+ if (!find(item, ref n, ref index))\r
+ return null;\r
+ //TODO: optimize with getpair!\r
+ return View(index, 1);\r
+#endif\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create a list view on this list containing the last occurrence of a particular item. \r
+ /// <exception cref="ArgumentException"/> if the item is not in this list.\r
+ /// </summary>\r
+ /// <param name="item">The item to find.</param>\r
+ /// <returns>The new list view.</returns>\r
+ public virtual IList<T> LastViewOf(T item)\r
+ {\r
+#if HASHINDEX\r
+ return ViewOf(item);\r
+#else\r
+ int index = size - 1;\r
+ Node n = endsentinel.prev;\r
+ if (!dnif(item, ref n, ref index))\r
+ return null;\r
+ return View(index, 1);\r
+#endif\r
+ }\r
+\r
+ /// <summary>\r
+ /// Null if this list is not a view.\r
+ /// </summary>\r
+ /// <value>Underlying list for view.</value>\r
+ [Tested]\r
+ public virtual IList<T> Underlying { [Tested]get { validitycheck(); return underlying; } }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <value></value>\r
+ public virtual bool IsValid { get { return isValid; } }\r
+\r
+ /// <summary>\r
+ /// </summary>\r
+ /// <value>Offset for this list view or 0 for a underlying list.</value>\r
+ [Tested]\r
+ public virtual int Offset\r
+ {\r
+ [Tested]\r
+ get\r
+ {\r
+ validitycheck();\r
+#if HASHINDEX\r
+ if (offset == null && underlying != null)\r
+ {\r
+ //TODO: search from both ends simultaneously!\r
+ Node n = underlying.startsentinel;\r
+ int i = 0;\r
+ while (n != startsentinel) { n = n.next; i++; }\r
+ offset = i;\r
+ }\r
+#endif\r
+ return (int)offset;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Slide this list view along the underlying list.\r
+ /// </summary>\r
+ /// <exception cref="NotAViewException"> if this list is not a view.</exception>\r
+ /// <exception cref="ArgumentOutOfRangeException"> if the operation\r
+ /// would bring either end of the view outside the underlying list.</exception>\r
+ /// <param name="offset">The signed amount to slide: positive to slide\r
+ /// towards the end.</param>\r
+ [Tested]\r
+ public IList<T> Slide(int offset)\r
+ {\r
+ if (!TrySlide(offset, size))\r
+ throw new ArgumentOutOfRangeException();\r
+ return this;\r
+ }\r
+\r
+ //TODO: more test cases\r
+ /// <summary>\r
+ /// Slide this list view along the underlying list, perhaps changing its size.\r
+ /// </summary>\r
+ /// <exception cref="NotAViewException"> if this list is not a view.</exception>\r
+ /// <exception cref="ArgumentOutOfRangeException"> if the operation\r
+ /// would bring either end of the view outside the underlying list.</exception>\r
+ /// <param name="offset">The signed amount to slide: positive to slide\r
+ /// towards the end.</param>\r
+ /// <param name="size">The new size of the view.</param>\r
+ public IList<T> Slide(int offset, int size)\r
+ {\r
+ if (!TrySlide(offset, size))\r
+ throw new ArgumentOutOfRangeException();\r
+ return this;\r
+ }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <param name="offset"></param>\r
+ /// <returns></returns>\r
+ public virtual bool TrySlide(int offset) { return TrySlide(offset, size); }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <param name="offset"></param>\r
+ /// <param name="size"></param>\r
+ /// <returns></returns>\r
+ public virtual bool TrySlide(int offset, int size)\r
+ {\r
+ updatecheck();\r
+ if (underlying == null)\r
+ throw new NotAViewException("List not a view");\r
+\r
+#pragma warning disable 472\r
+ if (this.offset == null) //Note: only possible with HASHINDEX\r
+#pragma warning restore 472\r
+ {\r
+#pragma warning disable 162\r
+ try\r
+ {\r
+ getPair(offset - 1, offset + size, out startsentinel, out endsentinel,\r
+ new int[] { -1, this.size }, new Node[] { startsentinel, endsentinel });\r
+ //TODO: maybe-update offset field\r
+ }\r
+ catch (NullReferenceException)\r
+ {\r
+ return false;\r
+ }\r
+#pragma warning restore 162\r
+ }\r
+ else\r
+ {\r
+ if (offset + this.offset < 0 || offset + this.offset + size > underlying.size)\r
+ return false;\r
+ int oldoffset = (int)(this.offset);\r
+ getPair(offset - 1, offset + size, out startsentinel, out endsentinel,\r
+ new int[] { -oldoffset - 1, -1, this.size, underlying.size - oldoffset },\r
+ new Node[] { underlying.startsentinel, startsentinel, endsentinel, underlying.endsentinel });\r
+ }\r
+ this.size = size;\r
+ this.offset += offset;\r
+ return true;\r
+ }\r
+\r
+\r
+ //TODO: improve the complexity of the implementation\r
+ /// <summary>\r
+ /// \r
+ /// <para>Returns null if <code>otherView</code> is strictly to the left of this view</para>\r
+ /// </summary>\r
+ /// <param name="otherView"></param>\r
+ /// <exception cref="IncompatibleViewException">If otherView does not have the same underlying list as this</exception>\r
+ /// <returns></returns>\r
+ public virtual IList<T> Span(IList<T> otherView)\r
+ {\r
+ if ((otherView == null) || ((otherView.Underlying ?? otherView) != (underlying ?? this)))\r
+ throw new IncompatibleViewException();\r
+ if (otherView.Offset + otherView.Count - Offset < 0)\r
+ return null;\r
+ return (underlying ?? this).View(Offset, otherView.Offset + otherView.Count - Offset);\r
+ }\r
+\r
+\r
+ //Question: should we swap items or move nodes around?\r
+ //The first seems much more efficient unless the items are value types \r
+ //with a large memory footprint.\r
+ //(Swapping will do count*3/2 T assignments, linking around will do \r
+ // 4*count ref assignments; note that ref assignments are more expensive \r
+ //than copying non-ref bits)\r
+ /// <summary>\r
+ /// Reverse the list so the items are in the opposite sequence order.\r
+ /// </summary>\r
+ [Tested]\r
+ public virtual void Reverse()\r
+ {\r
+ updatecheck();\r
+ if (size == 0)\r
+ return;\r
+\r
+ Position[] positions = null;\r
+ int poslow = 0, poshigh = 0;\r
+ if (views != null)\r
+ {\r
+ CircularQueue<Position> _positions = null;\r
+ foreach (LinkedList<T> view in views)\r
+ {\r
+ if (view != this)\r
+ {\r
+ switch (viewPosition(view))\r
+ {\r
+ case MutualViewPosition.ContainedIn:\r
+ (_positions ?? (_positions = new CircularQueue<Position>())).Enqueue(new Position(view, true));\r
+ _positions.Enqueue(new Position(view, false));\r
+ break;\r
+ case MutualViewPosition.Overlapping:\r
+ view.Dispose();\r
+ break;\r
+ case MutualViewPosition.Contains:\r
+ case MutualViewPosition.NonOverlapping:\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ if (_positions != null)\r
+ {\r
+ positions = _positions.ToArray();\r
+ Sorting.IntroSort<Position>(positions, 0, positions.Length, PositionComparer.Default);\r
+ poshigh = positions.Length - 1;\r
+ }\r
+ }\r
+\r
+ Node a = get(0), b = get(size - 1);\r
+ for (int i = 0; i < size / 2; i++)\r
+ {\r
+ T swap;\r
+ swap = a.item; a.item = b.item; b.item = swap;\r
+#if HASHINDEX\r
+ dict[a.item] = a; dict[b.item] = b;\r
+#endif\r
+ if (positions != null)\r
+ mirrorViewSentinelsForReverse(positions, ref poslow, ref poshigh, a, b, i);\r
+ a = a.next; b = b.prev;\r
+ }\r
+ if (positions != null && size % 2 != 0)\r
+ mirrorViewSentinelsForReverse(positions, ref poslow, ref poshigh, a, b, size / 2);\r
+ (underlying ?? this).raiseCollectionChanged();\r
+ }\r
+\r
+ private void mirrorViewSentinelsForReverse(Position[] positions, ref int poslow, ref int poshigh, Node a, Node b, int i)\r
+ {\r
+#if HASHINDEX\r
+ int? aindex = offset + i, bindex = offset + size - 1 - i;\r
+#else\r
+ int aindex = offset + i, bindex = offset + size - 1 - i;\r
+#endif\r
+ Position pos;\r
+#if HASHINDEX\r
+ while (poslow <= poshigh && (pos = positions[poslow]).Endpoint == a)\r
+#else\r
+ while (poslow <= poshigh && (pos = positions[poslow]).Index == aindex)\r
+#endif\r
+ {\r
+ //TODO: Note: in the case og hashed linked list, if this.offset == null, but pos.View.offset!=null\r
+ //we may at this point compute this.offset and non-null values of aindex and bindex\r
+ if (pos.Left)\r
+ pos.View.endsentinel = b.next;\r
+ else\r
+ {\r
+ pos.View.startsentinel = b.prev;\r
+ pos.View.offset = bindex;\r
+ }\r
+ poslow++;\r
+ }\r
+#if HASHINDEX\r
+ while (poslow < poshigh && (pos = positions[poshigh]).Endpoint == b)\r
+#else\r
+ while (poslow < poshigh && (pos = positions[poshigh]).Index == bindex)\r
+#endif\r
+ {\r
+ if (pos.Left)\r
+ pos.View.endsentinel = a.next;\r
+ else\r
+ {\r
+ pos.View.startsentinel = a.prev;\r
+ pos.View.offset = aindex;\r
+ }\r
+ poshigh--;\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Check if this list is sorted according to the default sorting order\r
+ /// for the item type T, as defined by the <see cref="T:C5.Comparer`1"/> class \r
+ /// </summary>\r
+ /// <exception cref="NotComparableException">if T is not comparable</exception>\r
+ /// <returns>True if the list is sorted, else false.</returns>\r
+ public bool IsSorted() { return IsSorted(Comparer<T>.Default); }\r
+\r
+ /// <summary>\r
+ /// Check if this list is sorted according to a specific sorting order.\r
+ /// </summary>\r
+ /// <param name="c">The comparer defining the sorting order.</param>\r
+ /// <returns>True if the list is sorted, else false.</returns>\r
+ [Tested]\r
+ public virtual bool IsSorted(SCG.IComparer<T> c)\r
+ {\r
+ validitycheck();\r
+ if (size <= 1)\r
+ return true;\r
+\r
+ Node node = startsentinel.next;\r
+ T prevItem = node.item;\r
+\r
+ node = node.next;\r
+ while (node != endsentinel)\r
+ {\r
+ if (c.Compare(prevItem, node.item) > 0)\r
+ return false;\r
+ else\r
+ {\r
+ prevItem = node.item;\r
+ node = node.next;\r
+ }\r
+ }\r
+\r
+ return true;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Sort the items of the list according to the default sorting order\r
+ /// for the item type T, as defined by the Comparer[T] class. \r
+ /// (<see cref="T:C5.Comparer`1"/>).\r
+ /// The sorting is stable.\r
+ /// </summary>\r
+ /// <exception cref="InvalidOperationException">if T is not comparable</exception>\r
+ public virtual void Sort() { Sort(Comparer<T>.Default); }\r
+\r
+ // Sort the linked list using mergesort\r
+ /// <summary>\r
+ /// Sort the items of the list according to a specific sorting order.\r
+ /// The sorting is stable.\r
+ /// </summary>\r
+ /// <param name="c">The comparer defining the sorting order.</param>\r
+ [Tested]\r
+ public virtual void Sort(SCG.IComparer<T> c)\r
+ {\r
+ updatecheck();\r
+ if (size == 0)\r
+ return;\r
+ disposeOverlappingViews(false);\r
+#if HASHINDEX\r
+ if (underlying != null)\r
+ {\r
+ Node cursor = startsentinel.next;\r
+ while (cursor != endsentinel)\r
+ {\r
+ cursor.taggroup.count--;\r
+ cursor = cursor.next;\r
+ }\r
+ }\r
+#endif\r
+ // Build a linked list of non-empty runs.\r
+ // The prev field in first node of a run points to next run's first node\r
+ Node runTail = startsentinel.next;\r
+ Node prevNode = startsentinel.next;\r
+\r
+ endsentinel.prev.next = null;\r
+ while (prevNode != null)\r
+ {\r
+ Node node = prevNode.next;\r
+\r
+ while (node != null && c.Compare(prevNode.item, node.item) <= 0)\r
+ {\r
+ prevNode = node;\r
+ node = prevNode.next;\r
+ }\r
+\r
+ // Completed a run; prevNode is the last node of that run\r
+ prevNode.next = null; // Finish the run\r
+ runTail.prev = node; // Link it into the chain of runs\r
+ runTail = node;\r
+ if (c.Compare(endsentinel.prev.item, prevNode.item) <= 0)\r
+ endsentinel.prev = prevNode; // Update last pointer to point to largest\r
+\r
+ prevNode = node; // Start a new run\r
+ }\r
+\r
+ // Repeatedly merge runs two and two, until only one run remains\r
+ while (startsentinel.next.prev != null)\r
+ {\r
+ Node run = startsentinel.next;\r
+ Node newRunTail = null;\r
+\r
+ while (run != null && run.prev != null)\r
+ { // At least two runs, merge\r
+ Node nextRun = run.prev.prev;\r
+ Node newrun = mergeRuns(run, run.prev, c);\r
+\r
+ if (newRunTail != null)\r
+ newRunTail.prev = newrun;\r
+ else\r
+ startsentinel.next = newrun;\r
+\r
+ newRunTail = newrun;\r
+ run = nextRun;\r
+ }\r
+\r
+ if (run != null) // Add the last run, if any\r
+ newRunTail.prev = run;\r
+ }\r
+\r
+ endsentinel.prev.next = endsentinel;\r
+ startsentinel.next.prev = startsentinel;\r
+\r
+ //assert invariant();\r
+ //assert isSorted();\r
+#if HASHINDEX\r
+ {\r
+ Node cursor = startsentinel.next, end = endsentinel;\r
+ int tag, taglimit;\r
+ TagGroup t = gettaggroup(startsentinel, endsentinel, out tag, out taglimit);\r
+ int tagdelta = taglimit / (size + 1) - tag / (size + 1);\r
+ tagdelta = tagdelta == 0 ? 1 : tagdelta;\r
+ if (underlying == null)\r
+ taggroups = 1;\r
+ while (cursor != end)\r
+ {\r
+ tag = tag + tagdelta > taglimit ? taglimit : tag + tagdelta;\r
+ cursor.tag = tag;\r
+ t.count++;\r
+ cursor = cursor.next;\r
+ }\r
+ if (tag == taglimit)\r
+ splittaggroup(t);\r
+ }\r
+#endif\r
+ (underlying ?? this).raiseCollectionChanged();\r
+ }\r
+\r
+ private static Node mergeRuns(Node run1, Node run2, SCG.IComparer<T> c)\r
+ {\r
+ //assert run1 != null && run2 != null;\r
+ Node prev;\r
+ bool prev1; // is prev from run1?\r
+\r
+ if (c.Compare(run1.item, run2.item) <= 0)\r
+ {\r
+ prev = run1;\r
+ prev1 = true;\r
+ run1 = run1.next;\r
+ }\r
+ else\r
+ {\r
+ prev = run2;\r
+ prev1 = false;\r
+ run2 = run2.next;\r
+ }\r
+\r
+ Node start = prev;\r
+\r
+ //assert start != null;\r
+ start.prev = null;\r
+ while (run1 != null && run2 != null)\r
+ {\r
+ if (prev1)\r
+ {\r
+ //assert prev.next == run1;\r
+ //Comparable run2item = (Comparable)run2.item;\r
+ while (run1 != null && c.Compare(run2.item, run1.item) >= 0)\r
+ {\r
+ prev = run1;\r
+ run1 = prev.next;\r
+ }\r
+\r
+ if (run1 != null)\r
+ { // prev.item <= run2.item < run1.item; insert run2\r
+ prev.next = run2;\r
+ run2.prev = prev;\r
+ prev = run2;\r
+ run2 = prev.next;\r
+ prev1 = false;\r
+ }\r
+ }\r
+ else\r
+ {\r
+ //assert prev.next == run2;\r
+ //Comparable run1item = (Comparable)run1.item;\r
+ while (run2 != null && c.Compare(run1.item, run2.item) > 0)\r
+ {\r
+ prev = run2;\r
+ run2 = prev.next;\r
+ }\r
+\r
+ if (run2 != null)\r
+ { // prev.item < run1.item <= run2.item; insert run1\r
+ prev.next = run1;\r
+ run1.prev = prev;\r
+ prev = run1;\r
+ run1 = prev.next;\r
+ prev1 = true;\r
+ }\r
+ }\r
+ }\r
+\r
+ //assert !(run1 != null && prev1) && !(run2 != null && !prev1);\r
+ if (run1 != null)\r
+ { // last run2 < all of run1; attach run1 at end\r
+ prev.next = run1;\r
+ run1.prev = prev;\r
+ }\r
+ else if (run2 != null)\r
+ { // last run1 \r
+ prev.next = run2;\r
+ run2.prev = prev;\r
+ }\r
+\r
+ return start;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Randomly shuffle the items of this list. \r
+ /// <para>Will invalidate overlapping views???</para>\r
+ /// </summary>\r
+ public virtual void Shuffle() { Shuffle(new C5Random()); }\r
+\r
+\r
+ /// <summary>\r
+ /// Shuffle the items of this list according to a specific random source.\r
+ /// <para>Will invalidate overlapping views???</para>\r
+ /// </summary>\r
+ /// <param name="rnd">The random source.</param>\r
+ public virtual void Shuffle(Random rnd)\r
+ {\r
+ updatecheck();\r
+ if (size == 0)\r
+ return;\r
+ disposeOverlappingViews(false);\r
+ ArrayList<T> a = new ArrayList<T>();\r
+ a.AddAll(this);\r
+ a.Shuffle(rnd);\r
+ Node cursor = startsentinel.next;\r
+ int j = 0;\r
+ while (cursor != endsentinel)\r
+ {\r
+ cursor.item = a[j++];\r
+#if HASHINDEX\r
+ dict[cursor.item] = cursor;\r
+#endif\r
+ cursor = cursor.next;\r
+ }\r
+ (underlying ?? this).raiseCollectionChanged();\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region IIndexed<T> Members\r
+\r
+ /// <summary>\r
+ /// <exception cref="IndexOutOfRangeException"/>.\r
+ /// </summary>\r
+ /// <value>The directed collection of items in a specific index interval.</value>\r
+ /// <param name="start">The low index of the interval (inclusive).</param>\r
+ /// <param name="count">The size of the range.</param>\r
+ [Tested]\r
+ public IDirectedCollectionValue<T> this[int start, int count]\r
+ {\r
+ [Tested]\r
+ get\r
+ {\r
+ validitycheck();\r
+ checkRange(start, count);\r
+ return new Range(this, start, count, true);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Searches for an item in the list going forwrds from the start.\r
+ /// </summary>\r
+ /// <param name="item">Item to search for.</param>\r
+ /// <returns>Index of item from start.</returns>\r
+ [Tested]\r
+ public virtual int IndexOf(T item)\r
+ {\r
+ validitycheck();\r
+ Node node;\r
+#if HASHINDEX\r
+ if (!dict.Find(item, out node) || !insideview(node))\r
+ return ~size;\r
+#endif\r
+ node = startsentinel.next;\r
+ int index = 0;\r
+ if (find(item, ref node, ref index))\r
+ return index;\r
+ else\r
+ return ~size;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Searches for an item in the list going backwords from the end.\r
+ /// </summary>\r
+ /// <param name="item">Item to search for.</param>\r
+ /// <returns>Index of of item from the end.</returns>\r
+ [Tested]\r
+ public virtual int LastIndexOf(T item)\r
+ {\r
+#if HASHINDEX\r
+ return IndexOf(item);\r
+#else\r
+ validitycheck();\r
+\r
+ Node node = endsentinel.prev;\r
+ int index = size - 1;\r
+\r
+ if (dnif(item, ref node, ref index))\r
+ return index;\r
+ else\r
+ return ~size;\r
+#endif\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove the item at a specific position of the list.\r
+ /// <exception cref="IndexOutOfRangeException"/> if i is negative or\r
+ /// >= the size of the collection.\r
+ /// </summary>\r
+ /// <param name="i">The index of the item to remove.</param>\r
+ /// <returns>The removed item.</returns>\r
+ [Tested]\r
+ public virtual T RemoveAt(int i)\r
+ {\r
+ updatecheck();\r
+ T retval = remove(get(i), i);\r
+#if HASHINDEX\r
+ dict.Remove(retval);\r
+#endif\r
+ if (ActiveEvents != EventTypeEnum.None)\r
+ (underlying ?? this).raiseForRemoveAt(Offset + i, retval);\r
+ return retval;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove all items in an index interval.\r
+ /// <exception cref="IndexOutOfRangeException"/>???. \r
+ /// </summary>\r
+ /// <param name="start">The index of the first item to remove.</param>\r
+ /// <param name="count">The number of items to remove.</param>\r
+ [Tested]\r
+ public virtual void RemoveInterval(int start, int count)\r
+ {\r
+#if HASHINDEX\r
+ updatecheck();\r
+ checkRange(start, count);\r
+ if (count == 0)\r
+ return;\r
+\r
+ View(start, count).Clear();\r
+#else\r
+ //Note: this is really almost equaivalent to Clear on a view\r
+ updatecheck();\r
+ checkRange(start, count);\r
+ if (count == 0)\r
+ return;\r
+\r
+ //for small count: optimize\r
+ //use an optimal get(int i, int j, ref Node ni, ref Node nj)?\r
+ Node a = get(start), b = get(start + count - 1);\r
+ fixViewsBeforeRemove(start, count, a, b);\r
+ a.prev.next = b.next;\r
+ b.next.prev = a.prev;\r
+ if (underlying != null)\r
+ underlying.size -= count;\r
+\r
+ size -= count;\r
+ if (ActiveEvents != EventTypeEnum.None)\r
+ (underlying ?? this).raiseForRemoveInterval(start + Offset, count);\r
+#endif\r
+ }\r
+\r
+ void raiseForRemoveInterval(int start, int count)\r
+ {\r
+ if (ActiveEvents != 0)\r
+ {\r
+ raiseCollectionCleared(size == 0, count, start);\r
+ raiseCollectionChanged();\r
+ }\r
+ }\r
+ #endregion\r
+\r
+ #region ISequenced<T> Members\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <returns></returns>\r
+ [Tested]\r
+ public override int GetSequencedHashCode() { validitycheck(); return base.GetSequencedHashCode(); }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <param name="that"></param>\r
+ /// <returns></returns>\r
+ [Tested]\r
+ public override bool SequencedEquals(ISequenced<T> that) { validitycheck(); return base.SequencedEquals(that); }\r
+\r
+ #endregion\r
+\r
+ #region IDirectedCollection<T> Members\r
+\r
+ /// <summary>\r
+ /// Create a collection containing the same items as this collection, but\r
+ /// whose enumerator will enumerate the items backwards. The new collection\r
+ /// will become invalid if the original is modified. Method typicaly used as in\r
+ /// <code>foreach (T x in coll.Backwards()) {...}</code>\r
+ /// </summary>\r
+ /// <returns>The backwards collection.</returns>\r
+ [Tested]\r
+ public override IDirectedCollectionValue<T> Backwards()\r
+ { return this[0, size].Backwards(); }\r
+\r
+ #endregion\r
+\r
+ #region IDirectedEnumerable<T> Members\r
+\r
+ [Tested]\r
+ IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); }\r
+\r
+ #endregion\r
+\r
+ #region IEditableCollection<T> Members\r
+\r
+ /// <summary>\r
+ /// The value is symbolic indicating the type of asymptotic complexity\r
+ /// in terms of the size of this collection (worst-case or amortized as\r
+ /// relevant).\r
+ /// </summary>\r
+ /// <value>Speed.Linear</value>\r
+ [Tested]\r
+ public virtual Speed ContainsSpeed\r
+ {\r
+ [Tested]\r
+ get\r
+ {\r
+#if HASHINDEX\r
+ return Speed.Constant ;\r
+#else\r
+ return Speed.Linear;\r
+#endif\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Performs a check for view validity before calling base.GetUnsequencedHashCode()\r
+ /// </summary>\r
+ /// <returns></returns>\r
+ [Tested]\r
+ public override int GetUnsequencedHashCode()\r
+ { validitycheck(); return base.GetUnsequencedHashCode(); }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <param name="that"></param>\r
+ /// <returns></returns>\r
+ [Tested]\r
+ public override bool UnsequencedEquals(ICollection<T> that)\r
+ { validitycheck(); return base.UnsequencedEquals(that); }\r
+\r
+ /// <summary>\r
+ /// Check if this collection contains (an item equivalent to according to the\r
+ /// itemequalityComparer) a particular value.\r
+ /// </summary>\r
+ /// <param name="item">The value to check for.</param>\r
+ /// <returns>True if the items is in this collection.</returns>\r
+ [Tested]\r
+ public virtual bool Contains(T item)\r
+ {\r
+ validitycheck();\r
+ Node node;\r
+ return contains(item, out node);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Check if this collection contains an item equivalent according to the\r
+ /// itemequalityComparer to a particular value. If so, return in the ref argument (a\r
+ /// binary copy of) the actual value found.\r
+ /// </summary>\r
+ /// <param name="item">The value to look for.</param>\r
+ /// <returns>True if the items is in this collection.</returns>\r
+ [Tested]\r
+ public virtual bool Find(ref T item)\r
+ {\r
+ validitycheck();\r
+ Node node;\r
+ if (contains(item, out node)) { item = node.item; return true; }\r
+ return false;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Check if this collection contains an item equivalent according to the\r
+ /// itemequalityComparer to a particular value. If so, update the item in the collection \r
+ /// to with a binary copy of the supplied value. Will update a single item.\r
+ /// </summary>\r
+ /// <param name="item">Value to update.</param>\r
+ /// <returns>True if the item was found and hence updated.</returns>\r
+ [Tested]\r
+ public virtual bool Update(T item) { T olditem; return Update(item, out olditem); }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <param name="item"></param>\r
+ /// <param name="olditem"></param>\r
+ /// <returns></returns>\r
+ public virtual bool Update(T item, out T olditem)\r
+ {\r
+ updatecheck();\r
+ Node node;\r
+\r
+ if (contains(item, out node))\r
+ {\r
+ olditem = node.item;\r
+ node.item = item;\r
+#if HASHINDEX\r
+ //Avoid clinging onto a reference to olditem via dict!\r
+ dict.Update(item, node);\r
+#endif\r
+ (underlying ?? this).raiseForUpdate(item, olditem);\r
+ return true;\r
+ }\r
+\r
+ olditem = default(T);\r
+ return false;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Check if this collection contains an item equivalent according to the\r
+ /// itemequalityComparer to a particular value. If so, return in the ref argument (a\r
+ /// binary copy of) the actual value found. Else, add the item to the collection.\r
+ /// </summary>\r
+ /// <param name="item">The value to look for.</param>\r
+ /// <returns>True if the item was found (hence not added).</returns>\r
+ [Tested]\r
+ public virtual bool FindOrAdd(ref T item)\r
+ {\r
+ updatecheck();\r
+#if HASHINDEX\r
+ //This is an extended myinsert:\r
+ Node node = new Node(item);\r
+ if (!dict.FindOrAdd(item, ref node))\r
+ {\r
+ insertNode(true, endsentinel, node);\r
+ (underlying ?? this).raiseForAdd(item);\r
+ return false; \r
+ }\r
+ if (!insideview(node))\r
+ throw new ArgumentException("Item alredy in indexed list but outside view");\r
+ item = node.item;\r
+ return true;\r
+#else\r
+ if (Find(ref item))\r
+ return true;\r
+\r
+ Add(item);\r
+ return false;\r
+#endif\r
+ }\r
+\r
+ /// <summary>\r
+ /// Check if this collection contains an item equivalent according to the\r
+ /// itemequalityComparer to a particular value. If so, update the item in the collection \r
+ /// to with a binary copy of the supplied value; else add the value to the collection. \r
+ /// </summary>\r
+ /// <param name="item">Value to add or update.</param>\r
+ /// <returns>True if the item was found and updated (hence not added).</returns>\r
+ [Tested]\r
+ public virtual bool UpdateOrAdd(T item) { T olditem; return UpdateOrAdd(item, out olditem); }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <param name="item"></param>\r
+ /// <param name="olditem"></param>\r
+ /// <returns></returns>\r
+ public virtual bool UpdateOrAdd(T item, out T olditem)\r
+ {\r
+ updatecheck();\r
+#if HASHINDEX\r
+ Node node = new Node(item);\r
+ //NOTE: it is hard to do this without double access to the dictionary\r
+ //in the update case\r
+ if (dict.FindOrAdd(item, ref node))\r
+ {\r
+ if (!insideview(node))\r
+ throw new ArgumentException("Item in indexed list but outside view");\r
+ olditem = node.item;\r
+ //Avoid clinging onto a reference to olditem via dict!\r
+ dict.Update(item, node);\r
+ node.item = item;\r
+ (underlying ?? this).raiseForUpdate(item, olditem);\r
+ return true;\r
+ }\r
+ insertNode(true, endsentinel, node);\r
+ (underlying ?? this).raiseForAdd(item);\r
+#else\r
+ if (Update(item, out olditem))\r
+ return true;\r
+ Add(item);\r
+#endif\r
+ olditem = default(T);\r
+ return false;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove a particular item from this collection. Since the collection has bag\r
+ /// semantics only one copy equivalent to the supplied item is removed. \r
+ /// </summary>\r
+ /// <param name="item">The value to remove.</param>\r
+ /// <returns>True if the item was found (and removed).</returns>\r
+ [Tested]\r
+ public virtual bool Remove(T item)\r
+ {\r
+ updatecheck();\r
+ int i = 0;\r
+ Node node;\r
+#if HASHINDEX\r
+ if (!dictremove(item, out node))\r
+#else\r
+ node = fIFO ? startsentinel.next : endsentinel.prev;\r
+ if (!(fIFO ? find(item, ref node, ref i) : dnif(item, ref node, ref i)))\r
+#endif\r
+ return false;\r
+ T removeditem = remove(node, i);\r
+ (underlying ?? this).raiseForRemove(removeditem);\r
+ return true;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove a particular item from this collection if found (only one copy). \r
+ /// If an item was removed, report a binary copy of the actual item removed in \r
+ /// the argument.\r
+ /// </summary>\r
+ /// <param name="item">The value to remove on input.</param>\r
+ /// <param name="removeditem">The value removed.</param>\r
+ /// <returns>True if the item was found (and removed).</returns>\r
+ [Tested]\r
+ public virtual bool Remove(T item, out T removeditem)\r
+ {\r
+ updatecheck();\r
+ int i = 0;\r
+ Node node;\r
+#if HASHINDEX\r
+ if (!dictremove(item, out node))\r
+#else\r
+ node = fIFO ? startsentinel.next : endsentinel.prev;\r
+ if (!(fIFO ? find(item, ref node, ref i) : dnif(item, ref node, ref i)))\r
+#endif\r
+ {\r
+ removeditem = default(T);\r
+ return false;\r
+ }\r
+ removeditem = node.item;\r
+ remove(node, i);\r
+ (underlying ?? this).raiseForRemove(removeditem);\r
+ return true;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove all items in another collection from this one, taking multiplicities into account.\r
+ /// <para>Always removes from the front of the list.\r
+ /// </para>\r
+ /// <para>The asymptotic running time complexity of this method is <code>O(n+m+v*log(v))</code>, \r
+ /// where <code>n</code> is the size of this list, <code>m</code> is the size of the\r
+ /// <code>items</code> collection and <code>v</code> is the number of views. \r
+ /// The method will temporarily allocate memory of size <code>O(m+v)</code>.\r
+ /// </para>\r
+ /// </summary>\r
+ /// <typeparam name="U"></typeparam>\r
+ /// <param name="items">The items to remove.</param>\r
+ [Tested]\r
+ public virtual void RemoveAll<U>(SCG.IEnumerable<U> items) where U : T\r
+ {\r
+ updatecheck();\r
+ if (size == 0)\r
+ return;\r
+ RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(underlying ?? this);\r
+ bool mustFire = raiseHandler.MustFire;\r
+#if HASHINDEX\r
+ Node node;\r
+ foreach (T item in items)\r
+ if (dictremove(item, out node))\r
+ {\r
+ if (mustFire)\r
+ raiseHandler.Remove(node.item);\r
+ remove(node, 118);\r
+ }\r
+#else\r
+ HashBag<T> toremove = new HashBag<T>(itemequalityComparer);\r
+ toremove.AddAll(items);\r
+ ViewHandler viewHandler = new ViewHandler(this);\r
+ int index = 0, removed = 0, myoffset = Offset;\r
+ Node node = startsentinel.next;\r
+ while (node != endsentinel)\r
+ {\r
+ //pass by a stretch of nodes\r
+ while (node != endsentinel && !toremove.Contains(node.item))\r
+ {\r
+ node = node.next;\r
+ index++;\r
+ }\r
+ viewHandler.skipEndpoints(removed, myoffset + index);\r
+ //Remove a stretch of nodes\r
+ Node localend = node.prev; //Latest node not to be removed\r
+ while (node != endsentinel && toremove.Remove(node.item))\r
+ {\r
+ if (mustFire)\r
+ raiseHandler.Remove(node.item);\r
+ removed++;\r
+ node = node.next;\r
+ index++;\r
+ viewHandler.updateViewSizesAndCounts(removed, myoffset + index);\r
+ }\r
+ viewHandler.updateSentinels(myoffset + index, localend, node);\r
+ localend.next = node;\r
+ node.prev = localend;\r
+ }\r
+ index = underlying != null ? underlying.size + 1 - myoffset : size + 1 - myoffset;\r
+ viewHandler.updateViewSizesAndCounts(removed, myoffset + index);\r
+ size -= removed;\r
+ if (underlying != null)\r
+ underlying.size -= removed;\r
+#endif\r
+ raiseHandler.Raise();\r
+ }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <param name="predicate"></param>\r
+ void RemoveAll(Fun<T, bool> predicate)\r
+ {\r
+ updatecheck();\r
+ if (size == 0)\r
+ return;\r
+ RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(underlying ?? this);\r
+ bool mustFire = raiseHandler.MustFire;\r
+#if HASHINDEX\r
+ {\r
+ Node n = startsentinel.next;\r
+\r
+ while (n != endsentinel)\r
+ {\r
+ bool removeIt = predicate(n.item);\r
+ updatecheck();\r
+ if (removeIt)\r
+ {\r
+ dict.Remove(n.item);\r
+ remove(n, 119);\r
+ if (mustFire)\r
+ raiseHandler.Remove(n.item);\r
+ }\r
+\r
+ n = n.next;\r
+ }\r
+ }\r
+#else\r
+ ViewHandler viewHandler = new ViewHandler(this);\r
+ int index = 0, removed = 0, myoffset = Offset;\r
+ Node node = startsentinel.next;\r
+ while (node != endsentinel)\r
+ {\r
+ //pass by a stretch of nodes\r
+ while (node != endsentinel && !predicate(node.item))\r
+ {\r
+ updatecheck();\r
+ node = node.next;\r
+ index++;\r
+ }\r
+ updatecheck();\r
+ viewHandler.skipEndpoints(removed, myoffset + index);\r
+ //Remove a stretch of nodes\r
+ Node localend = node.prev; //Latest node not to be removed\r
+ while (node != endsentinel && predicate(node.item))\r
+ {\r
+ updatecheck();\r
+ if (mustFire)\r
+ raiseHandler.Remove(node.item);\r
+ removed++;\r
+ node = node.next;\r
+ index++;\r
+ viewHandler.updateViewSizesAndCounts(removed, myoffset + index);\r
+ }\r
+ updatecheck();\r
+ viewHandler.updateSentinels(myoffset + index, localend, node);\r
+ localend.next = node;\r
+ node.prev = localend;\r
+ }\r
+ index = underlying != null ? underlying.size + 1 - myoffset : size + 1 - myoffset;\r
+ viewHandler.updateViewSizesAndCounts(removed, myoffset + index);\r
+ size -= removed;\r
+ if (underlying != null)\r
+ underlying.size -= removed;\r
+#endif\r
+ raiseHandler.Raise();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove all items from this collection.\r
+ /// </summary>\r
+ [Tested]\r
+ public virtual void Clear()\r
+ {\r
+ updatecheck();\r
+ if (size == 0)\r
+ return;\r
+ int oldsize = size;\r
+#if HASHINDEX\r
+ if (underlying == null)\r
+ dict.Clear();\r
+ else\r
+ foreach (T item in this)\r
+ dict.Remove(item);\r
+#endif\r
+ clear();\r
+ (underlying ?? this).raiseForRemoveInterval(Offset, oldsize);\r
+ }\r
+\r
+ void clear()\r
+ {\r
+ if (size == 0)\r
+ return;\r
+#if HASHINDEX\r
+ //TODO: mix with tag maintenance to only run through list once?\r
+ ViewHandler viewHandler = new ViewHandler(this);\r
+ if (viewHandler.viewCount > 0)\r
+ {\r
+ int removed = 0;\r
+ Node n = startsentinel.next;\r
+ viewHandler.skipEndpoints(0, n);\r
+ while (n != endsentinel)\r
+ {\r
+ removed++;\r
+ n = n.next;\r
+ viewHandler.updateViewSizesAndCounts(removed, n);\r
+ }\r
+ viewHandler.updateSentinels(endsentinel, startsentinel, endsentinel);\r
+ if (underlying != null)\r
+ viewHandler.updateViewSizesAndCounts(removed, underlying.endsentinel);\r
+ }\r
+#else\r
+ fixViewsBeforeRemove(Offset, size, startsentinel.next, endsentinel.prev);\r
+#endif\r
+#if HASHINDEX\r
+ if (underlying != null)\r
+ {\r
+ Node n = startsentinel.next;\r
+\r
+ while (n != endsentinel)\r
+ {\r
+ n.next.prev = startsentinel;\r
+ startsentinel.next = n.next;\r
+ removefromtaggroup(n);\r
+ n = n.next;\r
+ }\r
+ }\r
+ else\r
+ taggroups = 0;\r
+#endif\r
+ endsentinel.prev = startsentinel;\r
+ startsentinel.next = endsentinel;\r
+ if (underlying != null)\r
+ underlying.size -= size;\r
+ size = 0;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove all items not in some other collection from this one, taking multiplicities into account.\r
+ /// <para>The asymptotic running time complexity of this method is <code>O(n+m+v*log(v))</code>, \r
+ /// where <code>n</code> is the size of this collection, <code>m</code> is the size of the\r
+ /// <code>items</code> collection and <code>v</code> is the number of views. \r
+ /// The method will temporarily allocate memory of size <code>O(m+v)</code>. The stated complexitiy \r
+ /// holds under the assumption that the itemequalityComparer of this list is well-behaved.\r
+ /// </para>\r
+ /// </summary>\r
+ /// <typeparam name="U"></typeparam>\r
+ /// <param name="items">The items to retain.</param>\r
+ [Tested]\r
+ public virtual void RetainAll<U>(SCG.IEnumerable<U> items) where U : T\r
+ {\r
+ updatecheck();\r
+ if (size == 0)\r
+ return;\r
+ RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(underlying ?? this);\r
+ bool mustFire = raiseHandler.MustFire;\r
+#if HASHINDEX\r
+ /*if (underlying == null)\r
+ {\r
+ HashDictionary<T, Node> newdict = new HashDictionary<T, Node>(itemequalityComparer);\r
+ foreach (T item in items)\r
+ {\r
+ Node node;\r
+\r
+ if (dict.Remove(item, out node))\r
+ newdict.Add(item, node);\r
+ }\r
+ foreach (KeyValuePair<T, Node> pair in dict)\r
+ {\r
+ Node n = pair.Value;\r
+ fixViewsBeforeSingleRemove(n, 117);\r
+ Node p = n.prev, s = n.next; s.prev = p; p.next = s;\r
+ removefromtaggroup(n);\r
+ }\r
+ dict = newdict;\r
+ size = dict.Count;\r
+ //For a small number of items to retain it might be faster to \r
+ //iterate through the list and splice out the chunks not needed\r
+ }\r
+ else*/\r
+ {\r
+ HashSet<T> toremove = new HashSet<T>(itemequalityComparer);\r
+\r
+ foreach (T item in this)\r
+ toremove.Add(item);\r
+\r
+ foreach (T item in items)\r
+ toremove.Remove(item);\r
+\r
+ Node n = startsentinel.next;\r
+\r
+ while (n != endsentinel && toremove.Count > 0)\r
+ {\r
+ if (toremove.Contains(n.item))\r
+ {\r
+ dict.Remove(n.item);\r
+ remove(n, 119);\r
+ if (mustFire)\r
+ raiseHandler.Remove(n.item);\r
+ }\r
+\r
+ n = n.next;\r
+ }\r
+ }\r
+#else\r
+ HashBag<T> toretain = new HashBag<T>(itemequalityComparer);\r
+ toretain.AddAll(items);\r
+ ViewHandler viewHandler = new ViewHandler(this);\r
+ int index = 0, removed = 0, myoffset = Offset;\r
+ Node node = startsentinel.next;\r
+ while (node != endsentinel)\r
+ {\r
+ //Skip a stretch of nodes\r
+ while (node != endsentinel && toretain.Remove(node.item))\r
+ {\r
+ node = node.next;\r
+ index++;\r
+ }\r
+ viewHandler.skipEndpoints(removed, myoffset + index);\r
+ //Remove a stretch of nodes\r
+ Node localend = node.prev; //Latest node not to be removed\r
+ while (node != endsentinel && !toretain.Contains(node.item))\r
+ {\r
+ if (mustFire)\r
+ raiseHandler.Remove(node.item);\r
+ removed++;\r
+ node = node.next;\r
+ index++;\r
+ viewHandler.updateViewSizesAndCounts(removed, myoffset + index);\r
+ }\r
+ viewHandler.updateSentinels(myoffset + index, localend, node);\r
+ localend.next = node;\r
+ node.prev = localend;\r
+ }\r
+ index = underlying != null ? underlying.size + 1 - myoffset : size + 1 - myoffset;\r
+ viewHandler.updateViewSizesAndCounts(removed, myoffset + index);\r
+ size -= removed;\r
+ if (underlying != null)\r
+ underlying.size -= removed;\r
+#endif\r
+ raiseHandler.Raise();\r
+ }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <param name="predicate"></param>\r
+ void RetainAll(Fun<T,bool> predicate)\r
+ {\r
+ updatecheck();\r
+ if (size == 0)\r
+ return;\r
+ RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(underlying ?? this);\r
+ bool mustFire = raiseHandler.MustFire;\r
+#if HASHINDEX\r
+ {\r
+ Node n = startsentinel.next;\r
+\r
+ while (n != endsentinel)\r
+ {\r
+ bool removeIt = !predicate(n.item);\r
+ updatecheck();\r
+ if (removeIt)\r
+ {\r
+ dict.Remove(n.item);\r
+ remove(n, 119);\r
+ if (mustFire)\r
+ raiseHandler.Remove(n.item);\r
+ }\r
+\r
+ n = n.next;\r
+ }\r
+ }\r
+#else\r
+ ViewHandler viewHandler = new ViewHandler(this);\r
+ int index = 0, removed = 0, myoffset = Offset;\r
+ Node node = startsentinel.next;\r
+ while (node != endsentinel)\r
+ {\r
+ //Skip a stretch of nodes\r
+ while (node != endsentinel && predicate(node.item))\r
+ {\r
+ updatecheck();\r
+ node = node.next;\r
+ index++;\r
+ }\r
+ updatecheck();\r
+ viewHandler.skipEndpoints(removed, myoffset + index);\r
+ //Remove a stretch of nodes\r
+ Node localend = node.prev; //Latest node not to be removed\r
+ while (node != endsentinel && !predicate(node.item))\r
+ {\r
+ updatecheck();\r
+ if (mustFire)\r
+ raiseHandler.Remove(node.item);\r
+ removed++;\r
+ node = node.next;\r
+ index++;\r
+ viewHandler.updateViewSizesAndCounts(removed, myoffset + index);\r
+ }\r
+ updatecheck();\r
+ viewHandler.updateSentinels(myoffset + index, localend, node);\r
+ localend.next = node;\r
+ node.prev = localend;\r
+ }\r
+ index = underlying != null ? underlying.size + 1 - myoffset : size + 1 - myoffset;\r
+ viewHandler.updateViewSizesAndCounts(removed, myoffset + index);\r
+ size -= removed;\r
+ if (underlying != null)\r
+ underlying.size -= removed;\r
+#endif\r
+ raiseHandler.Raise();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Check if this collection contains all the values in another collection\r
+ /// with respect to multiplicities.\r
+ /// </summary>\r
+ /// <param name="items">The </param>\r
+ /// <typeparam name="U"></typeparam>\r
+ /// <returns>True if all values in <code>items</code>is in this collection.</returns>\r
+ [Tested]\r
+ public virtual bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T\r
+ {\r
+ validitycheck();\r
+#if HASHINDEX\r
+ Node node;\r
+ foreach (T item in items)\r
+ if (!contains(item, out node))\r
+ return false;\r
+ return true;\r
+#else\r
+ HashBag<T> tocheck = new HashBag<T>(itemequalityComparer);\r
+ tocheck.AddAll(items);\r
+ if (tocheck.Count > size)\r
+ return false;\r
+ Node node = startsentinel.next;\r
+ while (node != endsentinel)\r
+ {\r
+ tocheck.Remove(node.item);\r
+ node = node.next;\r
+ }\r
+ return tocheck.IsEmpty;\r
+#endif\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Create a new list consisting of the items of this list satisfying a \r
+ /// certain predicate.\r
+ /// </summary>\r
+ /// <param name="filter">The filter delegate defining the predicate.</param>\r
+ /// <returns>The new list.</returns>\r
+ [Tested]\r
+ public IList<T> FindAll(Fun<T, bool> filter)\r
+ {\r
+ validitycheck();\r
+ int stamp = this.stamp;\r
+ LinkedList<T> retval = new LinkedList<T>();\r
+ Node cursor = startsentinel.next;\r
+ Node mcursor = retval.startsentinel;\r
+#if HASHINDEX\r
+ double tagdelta = int.MaxValue / (size + 1.0);\r
+ int count = 1;\r
+ TagGroup taggroup = new TagGroup();\r
+ retval.taggroups = 1;\r
+#endif\r
+ while (cursor != endsentinel)\r
+ {\r
+ bool found = filter(cursor.item);\r
+ modifycheck(stamp);\r
+ if (found)\r
+ {\r
+ mcursor.next = new Node(cursor.item, mcursor, null);\r
+ mcursor = mcursor.next;\r
+ retval.size++;\r
+#if HASHINDEX\r
+ retval.dict.Add(cursor.item, mcursor); \r
+ mcursor.taggroup = taggroup;\r
+ mcursor.tag = (int)(tagdelta * count++);\r
+#endif\r
+ }\r
+ cursor = cursor.next;\r
+ }\r
+#if HASHINDEX\r
+ taggroup.count = retval.size;\r
+#endif\r
+ retval.endsentinel.prev = mcursor;\r
+ mcursor.next = retval.endsentinel;\r
+ return retval;\r
+ }\r
+\r
+\r
+ /// <summary>\r
+ /// Count the number of items of the collection equal to a particular value.\r
+ /// Returns 0 if and only if the value is not in the collection.\r
+ /// </summary>\r
+ /// <param name="item">The value to count.</param>\r
+ /// <returns>The number of copies found.</returns>\r
+ [Tested]\r
+ public virtual int ContainsCount(T item)\r
+ {\r
+#if HASHINDEX\r
+ return Contains(item) ? 1 : 0;\r
+#else\r
+ validitycheck();\r
+ int retval = 0;\r
+ Node node = startsentinel.next;\r
+ while (node != endsentinel)\r
+ {\r
+ if (itemequalityComparer.Equals(node.item, item))\r
+ retval++;\r
+ node = node.next;\r
+ }\r
+ return retval;\r
+#endif\r
+ }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <returns></returns>\r
+ public virtual ICollectionValue<T> UniqueItems()\r
+ {\r
+#if HASHINDEX\r
+ return this;\r
+#else\r
+ HashBag<T> hashbag = new HashBag<T>(itemequalityComparer);\r
+ hashbag.AddAll(this);\r
+ return hashbag.UniqueItems();\r
+#endif\r
+ }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <returns></returns>\r
+ public virtual ICollectionValue<KeyValuePair<T, int>> ItemMultiplicities()\r
+ {\r
+#if HASHINDEX\r
+ return new MultiplicityOne<T>(this);\r
+#else\r
+ HashBag<T> hashbag = new HashBag<T>(itemequalityComparer);\r
+ hashbag.AddAll(this);\r
+ return hashbag.ItemMultiplicities();\r
+#endif\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove all items equivalent to a given value.\r
+ /// <para>The asymptotic complexity of this method is <code>O(n+v*log(v))</code>, \r
+ /// where <code>n</code> is the size of the collection and <code>v</code> \r
+ /// is the number of views.\r
+ /// </para>\r
+ /// </summary>\r
+ /// <param name="item">The value to remove.</param>\r
+ [Tested]\r
+ public virtual void RemoveAllCopies(T item)\r
+ {\r
+#if HASHINDEX\r
+ Remove(item);\r
+#else\r
+ updatecheck();\r
+ if (size == 0)\r
+ return;\r
+ RaiseForRemoveAllHandler raiseHandler = new RaiseForRemoveAllHandler(underlying ?? this);\r
+ bool mustFire = raiseHandler.MustFire;\r
+ ViewHandler viewHandler = new ViewHandler(this);\r
+ int index = 0, removed = 0, myoffset = Offset;\r
+ //\r
+ Node node = startsentinel.next;\r
+ while (node != endsentinel)\r
+ {\r
+ //pass by a stretch of nodes\r
+ while (node != endsentinel && !itemequalityComparer.Equals(node.item, item))\r
+ {\r
+ node = node.next;\r
+ index++;\r
+ }\r
+ viewHandler.skipEndpoints(removed, myoffset + index);\r
+ //Remove a stretch of nodes\r
+ Node localend = node.prev; //Latest node not to be removed\r
+ while (node != endsentinel && itemequalityComparer.Equals(node.item, item))\r
+ {\r
+ if (mustFire)\r
+ raiseHandler.Remove(node.item);\r
+ removed++;\r
+ node = node.next;\r
+ index++;\r
+ viewHandler.updateViewSizesAndCounts(removed, myoffset + index);\r
+ }\r
+ viewHandler.updateSentinels(myoffset + index, localend, node);\r
+ localend.next = node;\r
+ node.prev = localend;\r
+ }\r
+ index = underlying != null ? underlying.size + 1 - myoffset : size + 1 - myoffset;\r
+ viewHandler.updateViewSizesAndCounts(removed, myoffset + index);\r
+ size -= removed;\r
+ if (underlying != null)\r
+ underlying.size -= removed;\r
+ raiseHandler.Raise();\r
+#endif\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region ICollectionValue<T> Members\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <value>The number of items in this collection</value>\r
+ [Tested]\r
+ public override int Count { [Tested]get { validitycheck(); return size; } }\r
+\r
+ /// <summary>\r
+ /// Choose some item of this collection. \r
+ /// </summary>\r
+ /// <exception cref="NoSuchItemException">if collection is empty.</exception>\r
+ /// <returns></returns>\r
+ [Tested]\r
+ public override T Choose() { return First; }\r
+\r
+ /// <summary>\r
+ /// Create an enumerable, enumerating the items of this collection that satisfies \r
+ /// a certain condition.\r
+ /// </summary>\r
+ /// <param name="filter">The T->bool filter delegate defining the condition</param>\r
+ /// <returns>The filtered enumerable</returns>\r
+ public override SCG.IEnumerable<T> Filter(Fun<T, bool> filter) { validitycheck(); return base.Filter(filter); }\r
+\r
+ #endregion\r
+\r
+ #region IEnumerable<T> Members\r
+ /// <summary>\r
+ /// Create an enumerator for the collection\r
+ /// </summary>\r
+ /// <returns>The enumerator</returns>\r
+ [Tested]\r
+ public override SCG.IEnumerator<T> GetEnumerator()\r
+ {\r
+ validitycheck();\r
+ Node cursor = startsentinel.next;\r
+ int enumeratorstamp = underlying != null ? underlying.stamp : this.stamp;\r
+\r
+ while (cursor != endsentinel)\r
+ {\r
+ modifycheck(enumeratorstamp);\r
+ yield return cursor.item;\r
+ cursor = cursor.next;\r
+ }\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region IExtensible<T> Members\r
+ /// <summary>\r
+ /// Add an item to this collection if possible. \r
+ /// </summary>\r
+ /// <param name="item">The item to add.</param>\r
+ /// <returns>True.</returns>\r
+ [Tested]\r
+ public virtual bool Add(T item)\r
+ {\r
+ updatecheck();\r
+#if HASHINDEX\r
+ Node node = new Node(item);\r
+ if (!dict.FindOrAdd(item, ref node))\r
+ {\r
+ insertNode(true, endsentinel, node);\r
+ (underlying ?? this).raiseForAdd(item);\r
+ return true;\r
+ }\r
+ return false;\r
+#else\r
+ insert(size, endsentinel, item);\r
+ (underlying ?? this).raiseForAdd(item);\r
+ return true;\r
+#endif\r
+ }\r
+\r
+ /// <summary>\r
+ /// \r
+ /// </summary>\r
+ /// <value>True since this collection has bag semantics.</value>\r
+ [Tested]\r
+ public virtual bool AllowsDuplicates\r
+ {\r
+ [Tested]\r
+ get\r
+ {\r
+#if HASHINDEX\r
+ return false;\r
+#else\r
+ return true;\r
+#endif\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// By convention this is true for any collection with set semantics.\r
+ /// </summary>\r
+ /// <value>True if only one representative of a group of equal items \r
+ /// is kept in the collection together with the total count.</value>\r
+ public virtual bool DuplicatesByCounting\r
+ {\r
+ get\r
+ {\r
+#if HASHINDEX\r
+ return true;\r
+#else\r
+ return false;\r
+#endif\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Add the elements from another collection with a more specialized item type \r
+ /// to this collection. \r
+ /// </summary>\r
+ /// <typeparam name="U">The type of items to add</typeparam>\r
+ /// <param name="items">The items to add</param>\r
+ [Tested]\r
+ public virtual void AddAll<U>(SCG.IEnumerable<U> items) where U : T\r
+ {\r
+#if HASHINDEX\r
+ updatecheck();\r
+ int added = 0;\r
+ Node pred = endsentinel.prev;\r
+ foreach (U item in items)\r
+ {\r
+ Node node = new Node(item);\r
+ if (!dict.FindOrAdd(item, ref node))\r
+ {\r
+ insertNode(false, endsentinel, node);\r
+ added++;\r
+ }\r
+ }\r
+ if (added > 0)\r
+ {\r
+ fixViewsAfterInsert(endsentinel, pred, added, 0);\r
+ raiseForInsertAll(pred, size - added, added, false);\r
+ }\r
+#else\r
+ insertAll(size, items, false);\r
+#endif\r
+ }\r
+\r
+ #endregion\r
+\r
+#if HASHINDEX\r
+#else\r
+ #region IStack<T> Members\r
+\r
+ /// <summary>\r
+ /// Push an item to the top of the stack.\r
+ /// </summary>\r
+ /// <param name="item">The item</param>\r
+ [Tested]\r
+ public void Push(T item)\r
+ {\r
+ InsertLast(item);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Pop the item at the top of the stack from the stack.\r
+ /// </summary>\r
+ /// <returns>The popped item.</returns>\r
+ [Tested]\r
+ public T Pop()\r
+ {\r
+ return RemoveLast();\r
+ }\r
+\r
+ #endregion\r
+\r
+ #region IQueue<T> Members\r
+\r
+ /// <summary>\r
+ /// Enqueue an item at the back of the queue. \r
+ /// </summary>\r
+ /// <param name="item">The item</param>\r
+ [Tested]\r
+ public virtual void Enqueue(T item)\r
+ {\r
+ InsertLast(item);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Dequeue an item from the front of the queue.\r
+ /// </summary>\r
+ /// <returns>The item</returns>\r
+ [Tested]\r
+ public virtual T Dequeue()\r
+ {\r
+ return RemoveFirst();\r
+ }\r
+ #endregion\r
+#endif\r
+\r
+ #region Diagnostic\r
+\r
+ private bool checkViews()\r
+ {\r
+ if (underlying != null)\r
+ throw new InternalException(System.Reflection.MethodInfo.GetCurrentMethod() + " called on a view");\r
+ if (views == null)\r
+ return true;\r
+ bool retval = true;\r
+\r
+ Node[] nodes = new Node[size + 2];\r
+ int i = 0;\r
+ Node n = startsentinel;\r
+ while (n != null)\r
+ {\r
+ nodes[i++] = n;\r
+ n = n.next;\r
+ }\r
+ //Console.WriteLine("###");\r
+ foreach (LinkedList<T> view in views)\r
+ {\r
+ if (!view.isValid)\r
+ {\r
+ Console.WriteLine("Invalid view(hash {0}, offset {1}, size {2})",\r
+ view.GetHashCode(), view.offset, view.size);\r
+ retval = false;\r
+ continue;\r
+ }\r
+ if (view.Offset > size || view.Offset < 0)\r
+ {\r
+ Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), Offset > underlying.size ({2})",\r
+ view.GetHashCode(), view.offset, view.size, size);\r
+ retval = false;\r
+ }\r
+ else if (view.startsentinel != nodes[view.Offset])\r
+ {\r
+ Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), startsentinel {3} should be {4}",\r
+ view.GetHashCode(), view.offset, view.size,\r
+ view.startsentinel + " " + view.startsentinel.GetHashCode(),\r
+ nodes[view.Offset] + " " + nodes[view.Offset].GetHashCode());\r
+ retval = false;\r
+ }\r
+ if (view.Offset + view.size > size || view.Offset + view.size < 0)\r
+ {\r
+ Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), end index > underlying.size ({3})",\r
+ view.GetHashCode(), view.offset, view.size, size);\r
+ retval = false;\r
+ }\r
+ else if (view.endsentinel != nodes[view.Offset + view.size + 1])\r
+ {\r
+ Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), endsentinel {3} should be {4}",\r
+ view.GetHashCode(), view.offset, view.size,\r
+ view.endsentinel + " " + view.endsentinel.GetHashCode(),\r
+ nodes[view.Offset + view.size + 1] + " " + nodes[view.Offset + view.size + 1].GetHashCode());\r
+ retval = false;\r
+ }\r
+ if (view.views != views)\r
+ {\r
+ Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), wrong views list {3} <> {4}",\r
+ view.GetHashCode(), view.offset, view.size, view.views.GetHashCode(), views.GetHashCode());\r
+ retval = false;\r
+ }\r
+ if (view.underlying != this)\r
+ {\r
+ Console.WriteLine("Bad view(hash {0}, offset {1}, size {2}), wrong underlying {3} <> this {4}",\r
+ view.GetHashCode(), view.offset, view.size, view.underlying.GetHashCode(), GetHashCode());\r
+ retval = false;\r
+ }\r
+ if (view.stamp != stamp)\r
+ {\r
+ //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);\r
+ //retval = false;\r
+ }\r
+ }\r
+ return retval;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Check the sanity of this list\r
+ /// </summary>\r
+ /// <returns>true if sane</returns>\r
+ [Tested]\r
+ public virtual bool Check()\r
+ {\r
+ bool retval = true;\r
+\r
+ /*if (underlying != null && underlying.stamp != stamp)\r
+ {\r
+ Console.WriteLine("underlying != null && underlying.stamp({0}) != stamp({1})", underlying.stamp, stamp);\r
+ retval = false;\r
+ }*/\r
+\r
+ if (underlying != null)\r
+ {\r
+ //TODO: check that this view is included in viewsEndpoints tree\r
+ return underlying.Check();\r
+ }\r
+\r
+ if (startsentinel == null)\r
+ {\r
+ Console.WriteLine("startsentinel == null");\r
+ retval = false;\r
+ }\r
+\r
+ if (endsentinel == null)\r
+ {\r
+ Console.WriteLine("endsentinel == null");\r
+ retval = false;\r
+ }\r
+\r
+ if (size == 0)\r
+ {\r
+ if (startsentinel != null && startsentinel.next != endsentinel)\r
+ {\r
+ Console.WriteLine("size == 0 but startsentinel.next != endsentinel");\r
+ retval = false;\r
+ }\r
+\r
+ if (endsentinel != null && endsentinel.prev != startsentinel)\r
+ {\r
+ Console.WriteLine("size == 0 but endsentinel.prev != startsentinel");\r
+ retval = false;\r
+ }\r
+ }\r
+\r
+ if (startsentinel == null)\r
+ {\r
+ Console.WriteLine("NULL startsentinel");\r
+ return retval;\r
+ }\r
+\r
+ int count = 0;\r
+ Node node = startsentinel.next, prev = startsentinel;\r
+#if HASHINDEX\r
+ int taggroupsize = 0, oldtaggroupsize = losize + 1, seentaggroups = 0;\r
+ TagGroup oldtg = null;\r
+\r
+ if (underlying == null)\r
+ {\r
+ TagGroup tg = startsentinel.taggroup;\r
+\r
+ if (tg.count != 0 || tg.first != null || tg.last != null || tg.tag != int.MinValue)\r
+ {\r
+ Console.WriteLine("Bad startsentinel tag group: {0}", tg);\r
+ retval = false;\r
+ }\r
+\r
+ tg = endsentinel.taggroup;\r
+ if (tg.count != 0 || tg.first != null || tg.last != null || tg.tag != int.MaxValue)\r
+ {\r
+ Console.WriteLine("Bad endsentinel tag group: {0}", tg);\r
+ retval = false;\r
+ }\r
+ }\r
+#endif\r
+ while (node != endsentinel)\r
+ {\r
+ count++;\r
+ if (node.prev != prev)\r
+ {\r
+ Console.WriteLine("Bad backpointer at node {0}", count);\r
+ retval = false;\r
+ }\r
+#if HASHINDEX\r
+ if (underlying == null)\r
+ {\r
+ if (!node.prev.precedes(node))\r
+ {\r
+ 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);\r
+ retval = false;\r
+ }\r
+\r
+ if (node.taggroup != oldtg)\r
+ {\r
+ if (oldtg != null)\r
+ {\r
+ if (oldtg.count != taggroupsize)\r
+ {\r
+ Console.WriteLine("Bad taggroupsize: oldtg.count ({0}) != taggroupsize ({1}) at index={2} item={3}", oldtg.count, taggroupsize, count, node.item);\r
+ retval = false;\r
+ }\r
+\r
+ if (oldtaggroupsize <= losize && taggroupsize <= losize)\r
+ {\r
+ Console.WriteLine("Two small taggroups in a row: oldtaggroupsize ({0}), taggroupsize ({1}) at index={2} item={3}", oldtaggroupsize, taggroupsize, count, node.item);\r
+ retval = false;\r
+ }\r
+\r
+ oldtaggroupsize = taggroupsize;\r
+ }\r
+\r
+ seentaggroups++;\r
+ oldtg = node.taggroup;\r
+ taggroupsize = 1;\r
+ }\r
+ else\r
+ {\r
+ taggroupsize++;\r
+ }\r
+ }\r
+\r
+#endif\r
+ prev = node;\r
+ node = node.next;\r
+ if (node == null)\r
+ {\r
+ Console.WriteLine("Null next pointer at node {0}", count);\r
+ return false;\r
+ }\r
+ }\r
+\r
+#if HASHINDEX\r
+ if (underlying == null && size == 0 && taggroups != 0)\r
+ {\r
+ Console.WriteLine("Bad taggroups for empty list: size={0} taggroups={1}", size, taggroups);\r
+ retval = false;\r
+ }\r
+ if (underlying == null && size > 0)\r
+ {\r
+ oldtg = node.prev.taggroup;\r
+ if (oldtg != null)\r
+ {\r
+ if (oldtg.count != taggroupsize)\r
+ {\r
+ Console.WriteLine("Bad taggroupsize: oldtg.count ({0}) != taggroupsize ({1}) at index={2} item={3}", oldtg.count, taggroupsize, count, node.item);\r
+ retval = false;\r
+ }\r
+\r
+ if (oldtaggroupsize <= losize && taggroupsize <= losize)\r
+ {\r
+ Console.WriteLine("Two small taggroups in a row: oldtaggroupsize ({0}), taggroupsize ({1}) at index={2} item={3}", oldtaggroupsize, taggroupsize, count, node.item);\r
+ retval = false;\r
+ }\r
+ }\r
+\r
+ if (seentaggroups != taggroups)\r
+ {\r
+ Console.WriteLine("seentaggroups ({0}) != taggroups ({1}) (at size {2})", seentaggroups, taggroups, size);\r
+ retval = false;\r
+ }\r
+ }\r
+#endif\r
+ if (count != size)\r
+ {\r
+ Console.WriteLine("size={0} but enumeration gives {1} nodes ", size, count);\r
+ retval = false;\r
+ }\r
+\r
+ retval = checkViews() && retval;\r
+\r
+#if HASHINDEX\r
+ if (!retval)\r
+ return false;\r
+ if (underlying == null)\r
+ {\r
+ if (size != dict.Count)\r
+ {\r
+ Console.WriteLine("list.size ({0}) != dict.Count ({1})", size, dict.Count);\r
+ retval = false;\r
+ }\r
+ Node n = startsentinel.next, n2;\r
+ while (n != endsentinel)\r
+ {\r
+ if (!dict.Find(n.item, out n2))\r
+ {\r
+ Console.WriteLine("Item in list but not dict: {0}", n.item);\r
+ retval = false;\r
+ }\r
+ else if (n != n2)\r
+ {\r
+ Console.WriteLine("Wrong node in dict for item: {0}", n.item);\r
+ retval = false;\r
+ }\r
+ n = n.next;\r
+ }\r
+ }\r
+#endif\r
+ return retval;\r
+ }\r
+ #endregion\r
+\r
+ #region ICloneable Members\r
+\r
+ /// <summary>\r
+ /// Make a shallow copy of this LinkedList.\r
+ /// </summary>\r
+ /// <returns></returns>\r
+ public virtual object Clone()\r
+ {\r
+ LinkedList<T> clone = new LinkedList<T>(itemequalityComparer);\r
+ clone.AddAll(this);\r
+ return clone;\r
+ }\r
+\r
+ #endregion\r
+\r
+ }\r
+}\r
projects / mono.git / blobdiff