+++ /dev/null
-#if NET_2_0\r
-/*\r
- Copyright (c) 2003-2004 Niels Kokholm <kokholm@itu.dk> and Peter Sestoft <sestoft@dina.kvl.dk>\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 MAINTAIN_SIZE\r
-#define MAINTAIN_RANKnot\r
-#define MAINTAIN_HEIGHTnot\r
-#define BAG\r
-#define NCP\r
-\r
-#define MAINTAIN_EXTREMAnot\r
-#define TRACE_IDnot\r
-\r
-#if BAG\r
-#if !MAINTAIN_SIZE\r
-#error BAG defined without MAINTAIN_SIZE!\r
-#endif\r
-#endif\r
-\r
-\r
-using System;\r
-using MSG = System.Collections.Generic;\r
-using SC = System.Collections;\r
-\r
-// NOTE NOTE NOTE NOTE\r
-// This source file is used to produce both TreeBag<T> and TreeBag<T>\r
-// It should be copied to a file called TreeBag.cs in which all code mentions of \r
-// TreeBag is changed to TreeBag and the preprocessor symbol BAG is defined.\r
-// NOTE: there may be problems with documentation comments.\r
-\r
-namespace C5\r
-{\r
-#if BAG\r
- /// <summary>\r
- /// An implementation of Red-Black trees as an indexed, sorted collection with bag semantics,\r
- /// cf. <a href="litterature.htm#CLRS">CLRS</a>. (<see cref="T:C5.TreeBag!1"/> for an \r
- /// implementation with set semantics).\r
- /// <br/>\r
- /// The comparer (sorting order) may be either natural, because the item type is comparable \r
- /// (generic: <see cref="T:C5.IComparable!1"/> or non-generic: System.IComparable) or it can\r
- /// be external and supplied by the user in the constructor.\r
- /// <br/>\r
- /// Each distinct item is only kept in one place in the tree - together with the number\r
- /// of times it is a member of the bag. Thus, if two items that are equal according\r
- /// </summary>\r
-#else\r
- /// <summary>\r
- /// An implementation of Red-Black trees as an indexed, sorted collection with set semantics,\r
- /// cf. <a href="litterature.htm#CLRS">CLRS</a>. <see cref="T:C5.TreeBag!1"/> for a version \r
- /// with bag semantics. <see cref="T:C5.TreeDictionary!2"/> for a sorted dictionary \r
- /// based on this tree implementation.\r
- /// <p>\r
- /// The comparer (sorting order) may be either natural, because the item type is comparable \r
- /// (generic: <see cref="T:C5.IComparable!1"/> or non-generic: System.IComparable) or it can\r
- /// be external and supplied by the user in the constructor.</p>\r
- ///\r
- /// <p><i>TODO: describe performance here</i></p>\r
- /// <p><i>TODO: discuss persistence and its useful usage modes. Warn about the space\r
- /// leak possible with other usage modes.</i></p>\r
- /// </summary>\r
-#endif\r
- public class TreeBag<T>: SequencedBase<T>, IIndexedSorted<T>, IPersistentSorted<T>\r
- {\r
- #region Feature\r
- /// <summary>\r
- /// A debugging aid for making the selected compilation alternatives \r
- /// available to the user. (To be removed when selection is finally fixed\r
- /// for production version).\r
- /// </summary>\r
- [Flags]\r
- public enum Feature: short\r
- {\r
- /// <summary>\r
- /// Nothing\r
- /// </summary>\r
- Dummy = 0,\r
- /// <summary>\r
- /// Node copy persistence as explained in <a href="litterature.htm#Tarjan1">Tarjan1</a>\r
- /// </summary>\r
- NodeCopyPersistence = 2,\r
- /// <summary>\r
- /// Maintain sub tree sizes\r
- /// </summary>\r
- Sizes = 4,\r
- /// <summary>\r
- /// Maintain precise node heights\r
- /// </summary>\r
- Heights = 8,\r
- /// <summary>\r
- /// Maintain node ranks (~ black height)\r
- /// </summary>\r
- Ranks = 16,\r
- /// <summary>\r
- /// Maintain unique ids on tree nodes.\r
- /// </summary>\r
- Traceid = 32\r
- }\r
-\r
-\r
-\r
- static Feature features = Feature.Dummy\r
-#if NCP\r
- | Feature.NodeCopyPersistence\r
-#endif\r
-#if MAINTAIN_RANK\r
- |Feature.Ranks\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- |Feature.Heights\r
-#endif\r
-#if MAINTAIN_SIZE\r
- | Feature.Sizes\r
-#endif\r
-#if TRACE_ID\r
- | Feature.Traceid\r
-#endif\r
- ;\r
-\r
-\r
- /// <summary>\r
- /// A debugging aid for making the selected compilation alternatives \r
- /// available to the user. (To be removed when selection is finally fixed\r
- /// for production version).\r
- /// </summary>\r
- public static Feature Features { get { return features; } }\r
-\r
- #endregion\r
-\r
- #region Fields\r
-\r
- IComparer<T> comparer;\r
-\r
- Node root;\r
-\r
- int blackdepth = 0;\r
-\r
- //We double these stacks for the iterative add and remove on demand\r
- private int[] dirs = new int[2];\r
-\r
- private Node[] path = new Node[2];\r
-#if NCP\r
- private bool isSnapShot = false;\r
-\r
- private SnapData snapdata;\r
-\r
- private int generation;\r
-\r
- private int maxsnapid = -1;\r
-\r
-#endif\r
-#if MAINTAIN_EXTREMA\r
- T min, max;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- private short depth = 0;\r
-#endif\r
- #endregion\r
-\r
- #region Util\r
-\r
- /// <summary>\r
- /// Fetch the left child of n taking node-copying persistence into\r
- /// account if relevant. \r
- /// </summary>\r
- /// <param name="n"></param>\r
- /// <returns></returns>\r
- private Node left(Node n)\r
- {\r
-#if NCP\r
- if (isSnapShot)\r
- {\r
-#if SEPARATE_EXTRA\r
- Node.Extra e = n.extra;\r
-\r
- if (e != null && e.lastgeneration >= treegen && e.leftnode)\r
- return e.oldref;\r
-#else\r
- if (n.lastgeneration >= generation && n.leftnode)\r
- return n.oldref;\r
-#endif\r
- }\r
-#endif\r
- return n.left;\r
- }\r
-\r
-\r
- private Node right(Node n)\r
- {\r
-#if NCP\r
- if (isSnapShot)\r
- {\r
-#if SEPARATE_EXTRA\r
- Node.Extra e = n.extra;\r
-\r
- if (e != null && e.lastgeneration >= treegen && !e.leftnode)\r
- return e.oldref;\r
-#else\r
- if (n.lastgeneration >= generation && !n.leftnode)\r
- return n.oldref;\r
-#endif\r
- }\r
-#endif\r
- return n.right;\r
- }\r
-\r
-\r
- //This method should be called by methods that use the internal \r
- //traversal stack, unless certain that there is room enough\r
- private void stackcheck()\r
- {\r
- while (dirs.Length < 2 * blackdepth)\r
- {\r
- dirs = new int[2 * dirs.Length];\r
- path = new Node[2 * dirs.Length];\r
- }\r
- }\r
-\r
- #endregion\r
-\r
- #region Node nested class\r
- \r
-\r
- /// <summary>\r
- /// The type of node in a Red-Black binary tree\r
- /// </summary>\r
- class Node\r
- {\r
- public bool red = true;\r
-\r
- public T item;\r
-\r
- public Node left;\r
-\r
- public Node right;\r
-\r
-#if MAINTAIN_SIZE\r
- public int size = 1;\r
-#endif\r
-\r
-#if BAG\r
- public int items = 1;\r
-#endif\r
-\r
-#if MAINTAIN_HEIGHT\r
- public short height; \r
-#endif\r
-\r
-#if MAINTAIN_RANK\r
- public short rank = 1;\r
-#endif\r
-\r
-#if TRACE_ID\r
- public int id = sid++;\r
- public static int sid = 0;\r
-#endif\r
-\r
-#if NCP\r
- public int generation;\r
-#if SEPARATE_EXTRA\r
- internal class Extra\r
- {\r
- public int lastgeneration;\r
-\r
- public Node oldref;\r
-\r
- public bool leftnode;\r
-\r
- //public Node next;\r
- }\r
-\r
- public Extra extra;\r
-\r
-#else\r
- public int lastgeneration = -1;\r
-\r
- public Node oldref;\r
-\r
- public bool leftnode;\r
-#endif\r
-\r
- /// <summary>\r
- /// Update a child pointer\r
- /// </summary>\r
- /// <param name="cursor"></param>\r
- /// <param name="leftnode"></param>\r
- /// <param name="child"></param>\r
- /// <param name="maxsnapid"></param>\r
- /// <param name="generation"></param>\r
- /// <returns>True if node was *copied*</returns>\r
- internal static bool update(ref Node cursor, bool leftnode, Node child, int maxsnapid, int generation)\r
- {\r
- Node oldref = leftnode ? cursor.left : cursor.right;\r
-\r
- if (child == oldref)\r
- return false;\r
-\r
- bool retval = false;\r
-\r
- if (cursor.generation <= maxsnapid)\r
- { \r
-#if SEPARATE_EXTRA\r
- if (cursor.extra == null)\r
- {\r
- Extra extra = cursor.extra = new Extra(); \r
-\r
- extra.leftnode = leftnode;\r
- extra.lastgeneration = maxsnapid;\r
- extra.oldref = oldref;\r
- }\r
- else if (cursor.extra.leftnode != leftnode || cursor.extra.lastgeneration < maxsnapid)\r
-#else\r
- if (cursor.lastgeneration == -1)\r
- {\r
- cursor.leftnode = leftnode;\r
- cursor.lastgeneration = maxsnapid;\r
- cursor.oldref = oldref;\r
- }\r
- else if (cursor.leftnode != leftnode || cursor.lastgeneration < maxsnapid)\r
-#endif\r
- {\r
- CopyNode(ref cursor, maxsnapid, generation);\r
- retval = true;\r
- }\r
- }\r
-\r
- if (leftnode)\r
- cursor.left = child;\r
- else\r
- cursor.right = child;\r
-\r
- return retval;\r
- }\r
-\r
-\r
- //If cursor.extra.lastgeneration==maxsnapid, the extra pointer will \r
- //always be used in the old copy of cursor. Therefore, after \r
- //making the clone, we should update the old copy by restoring\r
- //the child pointer and setting extra to null.\r
- //OTOH then we cannot clean up unused Extra objects unless we link\r
- //them together in a doubly linked list.\r
- public static bool CopyNode(ref Node cursor, int maxsnapid, int generation)\r
- {\r
- if (cursor.generation <= maxsnapid)\r
- {\r
- cursor = (Node)(cursor.MemberwiseClone());\r
- cursor.generation = generation;\r
-#if SEPARATE_EXTRA\r
- cursor.extra = null;\r
-#else\r
- cursor.lastgeneration = -1;\r
-#endif\r
-#if TRACE_ID\r
- cursor.id = sid++;\r
-#endif\r
- return true;\r
- }\r
- else\r
- return false;\r
- }\r
-\r
-#endif\r
- }\r
-\r
- #endregion\r
-\r
- #region Constructors\r
- \r
- /// <summary>\r
- /// Create a red-black tree collection with natural comparer and item hasher.\r
- /// </summary>\r
- public TreeBag()\r
- {\r
- comparer = ComparerBuilder.FromComparable<T>.Examine();\r
- itemhasher = HasherBuilder.ByPrototype<T>.Examine();\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Create a red-black tree collection with an external comparer (and natural item hasher,\r
- /// assumed consistent).\r
- /// </summary>\r
- /// <param name="c">The external comparer</param>\r
- public TreeBag(IComparer<T> c)\r
- {\r
- comparer = c;\r
- itemhasher = HasherBuilder.ByPrototype<T>.Examine();\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Create a red-black tree collection with an external comparer aand an external\r
- /// item hasher, assumed consistent.\r
- /// </summary>\r
- /// <param name="c">The external comparer</param>\r
- /// <param name="h">The external item hasher</param>\r
- public TreeBag(IComparer<T> c, IHasher<T> h)\r
- {\r
- comparer = c;\r
- itemhasher = h;\r
- }\r
-\r
- #endregion\r
-\r
- #region TreeBag.Enumerator nested class\r
-\r
- /// <summary>\r
- /// An enumerator for a red-black tree collection. Based on an explicit stack\r
- /// of subtrees waiting to be enumerated. Currently only used for the tree set \r
- /// enumerators (tree bag enumerators use an iterator block based enumerator).\r
- /// </summary>\r
- public class Enumerator: MSG.IEnumerator<T>\r
- {\r
- #region Private Fields\r
- TreeBag<T> tree;\r
-\r
- bool valid = false;\r
-\r
- int stamp;\r
-\r
- T current;\r
-\r
- Node cursor;\r
-\r
- Node[] path; // stack of nodes\r
-\r
- int level = 0;\r
- #endregion\r
- /// <summary>\r
- /// Create a tree enumerator\r
- /// </summary>\r
- /// <param name="tree">The red-black tree to enumerate</param>\r
- public Enumerator(TreeBag<T> tree)\r
- {\r
- this.tree = tree;\r
- stamp = tree.stamp;\r
- path = new Node[2 * tree.blackdepth];\r
- cursor = new Node();\r
- cursor.right = tree.root;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Undefined if enumerator is not valid (MoveNext hash been called returning true)\r
- /// </summary>\r
- /// <value>The current item of the enumerator.</value>\r
- [Tested]\r
- public T Current\r
- {\r
- [Tested]\r
- get\r
- {\r
- if (valid)\r
- return current;\r
- else\r
- throw new InvalidOperationException();\r
- }\r
- }\r
-\r
-\r
- //Maintain a stack of nodes that are roots of\r
- //subtrees not completely exported yet. Invariant:\r
- //The stack nodes together with their right subtrees\r
- //consists of exactly the items we have not passed\r
- //yet (the top of the stack holds current item).\r
- /// <summary>\r
- /// Move enumerator to next item in tree, or the first item if\r
- /// this is the first call to MoveNext. \r
- /// <exception cref="InvalidOperationException"/> if underlying tree was modified.\r
- /// </summary>\r
- /// <returns>True if enumerator is valid now</returns>\r
- [Tested]\r
- public bool MoveNext()\r
- {\r
- tree.modifycheck(stamp);\r
- if (cursor.right != null)\r
- {\r
- path[level] = cursor = cursor.right;\r
- while (cursor.left != null)\r
- path[++level] = cursor = cursor.left;\r
- }\r
- else if (level == 0)\r
- return valid = false;\r
- else\r
- cursor = path[--level];\r
-\r
- current = cursor.item;\r
- return valid = true;\r
- }\r
-\r
- void SC.IEnumerator.Reset ()\r
- {\r
- throw new NotImplementedException ();\r
- }\r
-\r
- object SC.IEnumerator.Current {\r
- get {\r
- return Current;\r
- }\r
- }\r
-\r
- #region IDisposable Members for Enumerator\r
-\r
- bool disposed;\r
-\r
-\r
- /// <summary>\r
- /// Call Dispose(true) and then suppress finalization of this enumerator.\r
- /// </summary>\r
- [Tested]\r
- public void Dispose()\r
- {\r
- Dispose(true);\r
- GC.SuppressFinalize(this);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove the internal data (notably the stack array).\r
- /// </summary>\r
- /// <param name="disposing">True if called from Dispose(),\r
- /// false if called from the finalizer</param>\r
- protected virtual void Dispose(bool disposing)\r
- {\r
- if (!disposed)\r
- {\r
- if (disposing)\r
- {\r
- }\r
-\r
- current = default(T);\r
- cursor = null;\r
- path = null;\r
- disposed = true;\r
- }\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Finalizer for enumeratir\r
- /// </summary>\r
- ~Enumerator()\r
- {\r
- Dispose(false);\r
- }\r
- #endregion\r
-\r
- }\r
-#if NCP\r
- /// <summary>\r
- /// An enumerator for a snapshot of a node copy persistent red-black tree\r
- /// collection.\r
- /// </summary>\r
- public class SnapEnumerator: MSG.IEnumerator<T>\r
- {\r
- #region Private Fields\r
- TreeBag<T> tree;\r
-\r
- bool valid = false;\r
-\r
- int stamp;\r
-#if BAG\r
- int togo;\r
-#endif\r
-\r
- T current;\r
-\r
- Node cursor;\r
-\r
- Node[] path; // stack of nodes\r
-\r
- int level;\r
- #endregion\r
-\r
- /// <summary>\r
- /// Creta an enumerator for a snapshot of a node copy persistent red-black tree\r
- /// collection\r
- /// </summary>\r
- /// <param name="tree">The snapshot</param>\r
- public SnapEnumerator(TreeBag<T> tree)\r
- {\r
- this.tree = tree;\r
- stamp = tree.stamp;\r
- path = new Node[2 * tree.blackdepth];\r
- cursor = new Node();\r
- cursor.right = tree.root;\r
- }\r
-\r
-\r
- #region MSG.IEnumerator<T> Members\r
-\r
- /// <summary>\r
- /// Move enumerator to next item in tree, or the first item if\r
- /// this is the first call to MoveNext. \r
- /// <exception cref="InvalidOperationException"/> if underlying tree was modified.\r
- /// </summary>\r
- /// <returns>True if enumerator is valid now</returns>\r
- [Tested]\r
- public bool MoveNext()\r
- {\r
- tree.modifycheck(stamp);//???\r
-\r
-#if BAG\r
- if (--togo>0)\r
- return true;\r
-#endif\r
- Node next = tree.right(cursor);\r
-\r
- if (next != null)\r
- {\r
- path[level] = cursor = next;\r
- next = tree.left(cursor);\r
- while (next != null)\r
- {\r
- path[++level] = cursor = next;\r
- next = tree.left(cursor);\r
- }\r
- }\r
- else if (level == 0)\r
- return valid = false;\r
- else\r
- cursor = path[--level];\r
-\r
-#if BAG\r
- togo = cursor.items;\r
-#endif\r
- current = cursor.item;\r
- return valid = true;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Undefined if enumerator is not valid (MoveNext hash been called returning true)\r
- /// </summary>\r
- /// <value>The current value of the enumerator.</value>\r
- [Tested]\r
- public T Current\r
- {\r
- [Tested]\r
- get\r
- {\r
- if (valid)\r
- return current;\r
- else\r
- throw new InvalidOperationException();\r
- }\r
- }\r
-\r
- #endregion\r
-\r
- void SC.IEnumerator.Reset ()\r
- {\r
- throw new NotImplementedException ();\r
- }\r
-\r
- object SC.IEnumerator.Current {\r
- get {\r
- return Current;\r
- }\r
- }\r
-\r
- #region IDisposable Members\r
-\r
- [Tested]\r
- void System.IDisposable.Dispose()\r
- {\r
- tree = null;\r
- valid = false;\r
- current = default(T);\r
- cursor = null;\r
- path = null;\r
- }\r
-\r
- #endregion\r
- }\r
-#endif\r
- #endregion\r
-\r
- #region IEnumerable<T> Members\r
-\r
- private MSG.IEnumerator<T> getEnumerator(Node node, int origstamp)\r
- {\r
- if (node == null)\r
- yield break;\r
-\r
- if (node.left != null)\r
- {\r
- MSG.IEnumerator<T> child = getEnumerator(node.left, origstamp);\r
-\r
- while (child.MoveNext())\r
- {\r
- modifycheck(origstamp);\r
- yield return child.Current;\r
- }\r
- }\r
-#if BAG\r
- int togo = node.items;\r
- while (togo-- > 0)\r
- {\r
- modifycheck(origstamp);\r
- yield return node.item;\r
- }\r
-#else\r
- modifycheck(origstamp);\r
- yield return node.item;\r
-#endif\r
- if (node.right != null)\r
- {\r
- MSG.IEnumerator<T> child = getEnumerator(node.right, origstamp);\r
-\r
- while (child.MoveNext())\r
- {\r
- modifycheck(origstamp);\r
- yield return child.Current;\r
- }\r
- }\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Create an enumerator for this tree\r
- /// </summary>\r
- /// <returns>The enumerator</returns>\r
- [Tested]\r
- public override MSG.IEnumerator<T> GetEnumerator()\r
- {\r
-#if NCP\r
- if (isSnapShot)\r
- return new SnapEnumerator(this);\r
-#endif\r
-#if BAG\r
- return getEnumerator(root,stamp);\r
-#else\r
- return new Enumerator(this);\r
-#endif\r
- }\r
-\r
- #endregion\r
-\r
- #region ISink<T> Members\r
- \r
- /// <summary>\r
- /// Add item to tree. If already there, return the found item in the second argument.\r
- /// </summary>\r
- /// <param name="item">Item to add</param>\r
- /// <param name="founditem">item found</param>\r
- /// <param name="update">whether item in node should be updated</param>\r
- /// <param name="wasfound">true if found in bag, false if not found or tre is a set</param>\r
- /// <returns>True if item was added</returns>\r
- bool addIterative(T item, ref T founditem, bool update, out bool wasfound)\r
- {\r
- wasfound = false;\r
- if (root == null)\r
- {\r
- root = new Node();\r
- root.red = false;\r
- blackdepth = 1;\r
-#if MAINTAIN_EXTREMA\r
- root.item = min = max = item;\r
-#else\r
- root.item = item;\r
-#endif\r
-#if NCP\r
- root.generation = generation;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- depth = 0;\r
-#endif\r
- return true;\r
- }\r
-\r
- stackcheck();\r
-\r
- int level = 0;\r
- Node cursor = root;\r
-\r
- while (true)\r
- {\r
- int comp = comparer.Compare(cursor.item, item);\r
-\r
- if (comp == 0)\r
- {\r
- founditem = cursor.item;\r
-\r
-#if BAG\r
- wasfound = true;\r
-#if NCP\r
- Node.CopyNode(ref cursor, maxsnapid, generation);\r
-#endif\r
- cursor.items++;\r
- cursor.size++;\r
- if (update)\r
- cursor.item = item;\r
-\r
- update = true;\r
-\r
-#else\r
- if (update)\r
- {\r
-#if NCP\r
- Node.CopyNode(ref cursor, maxsnapid, generation);\r
-#endif\r
- cursor.item = item;\r
- }\r
-#endif\r
-\r
- while (level-- > 0)\r
- {\r
- if (update)\r
- {\r
- Node kid = cursor;\r
-\r
- cursor = path[level];\r
-#if NCP\r
- Node.update(ref cursor, dirs[level] > 0, kid, maxsnapid, generation);\r
-#endif\r
-#if BAG\r
- cursor.size++;\r
-#endif\r
- }\r
-\r
- path[level] = null;\r
- }\r
-#if BAG\r
- return true;\r
-#else\r
- if (update)\r
- root = cursor;\r
-\r
- return false;\r
-#endif\r
- }\r
-\r
- //else\r
- Node child = comp > 0 ? cursor.left : cursor.right;\r
-\r
- if (child == null)\r
- {\r
- child = new Node();\r
- child.item = item;\r
-#if NCP\r
- child.generation = generation;\r
- Node.update(ref cursor, comp > 0, child, maxsnapid, generation);\r
-#else\r
- if (comp > 0) { cursor.left = child; }\r
- else { cursor.right = child; }\r
-#endif\r
-#if MAINTAIN_SIZE\r
- cursor.size++;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(cursor);\r
-#endif\r
- dirs[level] = comp;\r
- break;\r
- }\r
- else\r
- {\r
- dirs[level] = comp;\r
- path[level++] = cursor;\r
- cursor = child;\r
- }\r
- }\r
-\r
- //We have just added the red node child to "cursor"\r
- while (cursor.red)\r
- {\r
- //take one step up:\r
- Node child = cursor;\r
-\r
- cursor = path[--level];\r
- path[level] = null;\r
-#if NCP\r
- Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);\r
-#endif\r
-#if MAINTAIN_SIZE\r
- cursor.size++;\r
-#endif\r
- int comp = dirs[level];\r
- Node childsibling = comp > 0 ? cursor.right : cursor.left;\r
-\r
- if (childsibling != null && childsibling.red)\r
- {\r
- //Promote\r
-#if MAINTAIN_RANK\r
- cursor.rank++;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(cursor);\r
-#endif\r
- child.red = false;\r
-#if NCP\r
- Node.update(ref cursor, comp < 0, childsibling, maxsnapid, generation);\r
-#endif\r
- childsibling.red = false;\r
-\r
- //color cursor red & take one step up the tree unless at root\r
- if (level == 0)\r
- {\r
- root = cursor;\r
- blackdepth++;\r
- return true;\r
- }\r
- else\r
- {\r
- cursor.red = true;\r
-#if NCP\r
- child = cursor;\r
- cursor = path[--level];\r
- Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);\r
-#endif\r
- path[level] = null;\r
-#if MAINTAIN_SIZE\r
- cursor.size++;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(cursor);\r
-#endif\r
- }\r
- }\r
- else\r
- {\r
- //ROTATE!!!\r
- int childcomp = dirs[level + 1];\r
-\r
- cursor.red = true;\r
- if (comp > 0)\r
- {\r
- if (childcomp > 0)\r
- {//zagzag\r
-#if NCP\r
- Node.update(ref cursor, true, child.right, maxsnapid, generation);\r
- Node.update(ref child, false, cursor, maxsnapid, generation);\r
-#else\r
- cursor.left = child.right;\r
- child.right = cursor;\r
-#endif\r
- cursor = child;\r
- }\r
- else\r
- {//zagzig\r
- Node badgrandchild = child.right;\r
-#if NCP\r
- Node.update(ref cursor, true, badgrandchild.right, maxsnapid, generation);\r
- Node.update(ref child, false, badgrandchild.left, maxsnapid, generation);\r
- Node.CopyNode(ref badgrandchild, maxsnapid, generation);\r
-#else\r
- cursor.left = badgrandchild.right;\r
- child.right = badgrandchild.left;\r
-#endif\r
- badgrandchild.left = child;\r
- badgrandchild.right = cursor;\r
- cursor = badgrandchild;\r
- }\r
- }\r
- else\r
- {//comp < 0\r
- if (childcomp < 0)\r
- {//zigzig\r
-#if NCP\r
- Node.update(ref cursor, false, child.left, maxsnapid, generation);\r
- Node.update(ref child, true, cursor, maxsnapid, generation);\r
-#else\r
- cursor.right = child.left;\r
- child.left = cursor;\r
-#endif\r
- cursor = child;\r
- }\r
- else\r
- {//zigzag\r
- Node badgrandchild = child.left;\r
-#if NCP\r
- Node.update(ref cursor, false, badgrandchild.left, maxsnapid, generation);\r
- Node.update(ref child, true, badgrandchild.right, maxsnapid, generation);\r
- Node.CopyNode(ref badgrandchild, maxsnapid, generation);\r
-#else\r
- cursor.right = badgrandchild.left;\r
- child.left = badgrandchild.right;\r
-#endif\r
- badgrandchild.right = child;\r
- badgrandchild.left = cursor;\r
- cursor = badgrandchild;\r
- }\r
- }\r
-\r
- cursor.red = false;\r
-\r
-#if MAINTAIN_SIZE\r
- Node n;\r
-\r
-#if BAG\r
- n = cursor.right;\r
- cursor.size = n.size = (n.left == null ? 0 : n.left.size) + (n.right == null ? 0 : n.right.size) + n.items;\r
- n = cursor.left;\r
- n.size = (n.left == null ? 0 : n.left.size) + (n.right == null ? 0 : n.right.size) + n.items;\r
- cursor.size += n.size + cursor.items;\r
-#else\r
- n = cursor.right;\r
- cursor.size = n.size = (n.left == null ? 0 : n.left.size) + (n.right == null ? 0 : n.right.size) + 1;\r
- n = cursor.left;\r
- n.size = (n.left == null ? 0 : n.left.size) + (n.right == null ? 0 : n.right.size) + 1;\r
- cursor.size += n.size + 1;\r
-#endif\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(cursor.right);\r
- fixheight(cursor.left);\r
- fixheight(cursor);\r
-#endif\r
- if (level == 0)\r
- {\r
- root = cursor;\r
- return true;\r
- }\r
- else\r
- {\r
- child = cursor;\r
- cursor = path[--level];\r
- path[level] = null;\r
-#if NCP\r
- Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);\r
-#else\r
- if (dirs[level] > 0)\r
- cursor.left = child;\r
- else\r
- cursor.right = child;\r
-#endif\r
-#if MAINTAIN_SIZE\r
- cursor.size++;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(cursor);\r
-#endif\r
- break;\r
- }\r
- }\r
- }\r
-#if NCP\r
- bool stillmore = true;\r
-#endif\r
- while (level > 0)\r
- {\r
- Node child = cursor;\r
-\r
- cursor = path[--level];\r
- path[level] = null;\r
-#if NCP\r
- if (stillmore)\r
- stillmore = Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);\r
-#endif\r
-#if MAINTAIN_SIZE\r
- cursor.size++;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(cursor);\r
-#endif\r
- }\r
-\r
- root = cursor;\r
- return true;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Add an item to this collection if possible. If this collection has set\r
- /// semantics, the item will be added if not already in the collection. If\r
- /// bag semantics, the item will always be added.\r
- /// </summary>\r
- /// <param name="item">The item to add.</param>\r
- /// <returns>True if item was added.</returns>\r
- [Tested]\r
- public bool Add(T item)\r
- {\r
- updatecheck();\r
-\r
- //Note: blackdepth of the tree is set inside addIterative\r
- T j = default(T);\r
- bool tmp;\r
-\r
- if (addIterative(item, ref j, false, out tmp))\r
- {\r
- size++;\r
-#if MAINTAIN_EXTREMA\r
- if (Compare(item, min) < 0)\r
- min = item;\r
- else if (Compare(item, max) > 0)\r
- max = item;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- depth = root.height;\r
-#endif\r
- return true;\r
- }\r
- else\r
- return false;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Add the elements from another collection to this collection. If this\r
- /// collection has set semantics, only items not already in the collection\r
- /// will be added.\r
- /// </summary>\r
- /// <param name="items">The items to add.</param>\r
- [Tested]\r
- public void AddAll(MSG.IEnumerable<T> items)\r
- {\r
- int c = 0;\r
- T j = default(T);\r
- bool tmp;\r
-\r
- updatecheck();\r
- foreach (T i in items)\r
- if (addIterative(i, ref j, false, out tmp)) c++;\r
-\r
- size += c;\r
- }\r
-\r
- /// <summary>\r
- /// Add the elements from another collection with a more specialized item type \r
- /// to this collection. If this\r
- /// collection has set semantics, only items not already in the collection\r
- /// will be added.\r
- /// </summary>\r
- /// <typeparam name="U">The type of items to add</typeparam>\r
- /// <param name="items">The items to add</param>\r
- public void AddAll<U>(MSG.IEnumerable<U> items) where U : T\r
- {\r
- int c = 0;\r
- T j = default(T);\r
- bool tmp;\r
-\r
- updatecheck();\r
- foreach (T i in items)\r
- if (addIterative(i, ref j, false, out tmp)) c++;\r
-\r
- size += c;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Add all the items from another collection with an enumeration order that \r
- /// is increasing in the items. <para>The idea is that the implementation may use\r
- /// a faster algorithm to merge the two collections.</para>\r
- /// <exception cref="ArgumentException"/> if the enumerated items turns out\r
- /// not to be in increasing order.\r
- /// </summary>\r
- /// <param name="items">The collection to add.</param>\r
- [Tested]\r
- public void AddSorted(MSG.IEnumerable<T> items)\r
- {\r
- if (size > 0)\r
- AddAll(items);\r
- else\r
- {\r
- updatecheck();\r
- addSorted(items, true);\r
- }\r
- }\r
-\r
- #region add-sorted helpers\r
- \r
- //Create a RB tree from x+2^h-1 (x < 2^h, h>=1) nodes taken from a\r
- //singly linked list of red nodes using only the right child refs.\r
- //The x nodes at depth h+1 will be red, the rest black.\r
- //(h is the blackdepth of the resulting tree)\r
- static Node maketreer(ref Node rest, int blackheight, int maxred, int red)\r
- {\r
- if (blackheight == 1)\r
- {\r
- Node top = rest;\r
-\r
- rest = rest.right;\r
- if (red > 0)\r
- {\r
- top.right = null;\r
- rest.left = top;\r
- top = rest;\r
-#if BAG\r
- top.size += top.left.size;\r
-#elif MAINTAIN_SIZE\r
- top.size = 1 + red;\r
-#endif\r
- rest = rest.right;\r
- red--;\r
- }\r
-\r
- if (red > 0)\r
- {\r
-#if BAG\r
- top.size += rest.size;\r
-#endif\r
- top.right = rest;\r
- rest = rest.right;\r
- top.right.right = null;\r
- }\r
- else\r
- top.right = null;\r
-\r
- top.red = false;\r
- return top;\r
- }\r
- else\r
- {\r
- maxred >>=1;\r
-\r
- int lred = red > maxred ? maxred : red;\r
- Node left = maketreer(ref rest, blackheight - 1, maxred, lred);\r
- Node top = rest;\r
-\r
- rest = rest.right;\r
- top.left = left;\r
- top.red = false;\r
-#if MAINTAIN_RANK\r
- top.rank = (short)blackheight;\r
-#endif\r
- top.right = maketreer(ref rest, blackheight - 1, maxred, red - lred);\r
-#if BAG\r
- top.size = top.items + top.left.size + top.right.size;\r
-#elif MAINTAIN_SIZE\r
- top.size = (maxred << 1) - 1 + red;\r
-#endif\r
- return top;\r
- }\r
- }\r
-\r
-\r
- void addSorted(MSG.IEnumerable<T> items, bool safe)\r
- {\r
- MSG.IEnumerator<T> e = items.GetEnumerator();;\r
- if (size > 0)\r
- throw new ApplicationException("This can't happen");\r
-\r
- if (!e.MoveNext())\r
- return;\r
-\r
- //To count theCollect \r
- Node head = new Node(), tail = head;\r
- int z = 1;\r
- T lastitem = tail.item = e.Current;\r
-#if BAG\r
- int ec=0;\r
-#endif\r
-\r
- while (e.MoveNext())\r
- {\r
-#if BAG\r
- T thisitem = e.Current;\r
- int comp = comparer.Compare(lastitem, thisitem);\r
- if (comp>0)\r
- throw new ArgumentException("Argument not sorted");\r
- if (comp == 0)\r
- {\r
- tail.items++;\r
- ec++;\r
- }\r
- else\r
- {\r
- tail.size = tail.items;\r
- z++;\r
- tail.right = new Node();\r
- tail = tail.right;\r
- lastitem = tail.item = thisitem;\r
-#if NCP\r
- tail.generation = generation;\r
-#endif\r
- }\r
-#else\r
- z++;\r
- tail.right = new Node();\r
- tail = tail.right;\r
- tail.item = e.Current;\r
- if (safe)\r
- {\r
- if (comparer.Compare(lastitem, tail.item) >= 0)\r
- throw new ArgumentException("Argument not sorted");\r
-\r
- lastitem = tail.item;\r
- }\r
-#if NCP\r
- tail.generation = generation;\r
-#endif\r
-#endif\r
- }\r
-#if BAG\r
- tail.size = tail.items;\r
-#endif \r
- int blackheight = 0, red = z, maxred = 1;\r
-\r
- while (maxred <= red)\r
- {\r
- red -= maxred;\r
- maxred <<= 1;\r
- blackheight++;\r
- }\r
-\r
- root = TreeBag<T>.maketreer(ref head, blackheight, maxred, red);\r
- blackdepth = blackheight;\r
- size = z;\r
-#if BAG\r
- size += ec;\r
-#endif \r
- return;\r
- }\r
-\r
- #endregion\r
-\r
-#if BAG\r
- /// <summary></summary>\r
- /// <value>True since this collection has bag semantics.</value>\r
- [Tested]\r
- public bool AllowsDuplicates { [Tested]get { return true; } }\r
-#else\r
- /// <summary></summary>\r
- /// <value>False since this tree has set semantics.</value>\r
- [Tested]\r
- public bool AllowsDuplicates { [Tested]get { return false; } }\r
-#endif\r
-\r
- #endregion\r
-\r
- #region IEditableCollection<T> Members\r
- \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.Log</value>\r
- [Tested]\r
- public Speed ContainsSpeed { [Tested]get { return Speed.Log; } }\r
-\r
-\r
- [Tested]\r
- int ICollection<T>.GetHashCode() { return unsequencedhashcode(); }\r
-\r
-\r
- [Tested]\r
- bool ICollection<T>.Equals(ICollection<T> that)\r
- { return unsequencedequals(that); }\r
-\r
-\r
- /// <summary>\r
- /// Check if this collection contains (an item equivalent to according to the\r
- /// itemhasher) 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 bool Contains(T item)\r
- {\r
- Node next; int comp = 0;\r
-\r
- next = root;\r
- while (next != null)\r
- {\r
- comp = comparer.Compare(next.item, item);\r
- if (comp == 0)\r
- return true;\r
-\r
- next = comp < 0 ? right(next) : left(next);\r
- }\r
-\r
- return false;\r
- }\r
-\r
-\r
- //Variant for dictionary use\r
- //Will return the actual matching item in the ref argument.\r
- /// <summary>\r
- /// Check if this collection contains an item equivalent according to the\r
- /// itemhasher 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 bool Find(ref T item)\r
- {\r
- Node next; int comp = 0;\r
-\r
- next = root;\r
- while (next != null)\r
- {\r
- comp = comparer.Compare(next.item, item);\r
- if (comp == 0)\r
- {\r
- item = next.item;\r
- return true;\r
- }\r
-\r
- next = comp < 0 ? right(next) : left(next);\r
- }\r
-\r
- return false;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Find or add the item to the tree. If the tree does not contain\r
- /// an item equivalent to this item add it, else return the exisiting\r
- /// one in the ref argument. \r
- ///\r
- /// </summary>\r
- /// <param name="item"></param>\r
- /// <returns>True if item was found</returns>\r
- [Tested]\r
- public bool FindOrAdd(ref T item)\r
- {\r
- updatecheck();\r
- bool wasfound;\r
-\r
- //Note: blackdepth of the tree is set inside addIterative\r
- if (addIterative(item, ref item, false, out wasfound))\r
- {\r
- size++;\r
-#if MAINTAIN_EXTREMA\r
- if (Compare(item, min) < 0)\r
- min = item;\r
- else if (Compare(item, max) > 0)\r
- max = item;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- depth = root.height;\r
-#endif\r
- return wasfound;\r
- }\r
- else\r
- return true;\r
-\r
- }\r
-\r
-\r
- //For dictionary use. \r
- //If found, the matching entry will be updated with the new item.\r
- /// <summary>\r
- /// Check if this collection contains an item equivalent according to the\r
- /// itemhasher to a particular value. If so, update the item in the collection \r
- /// to with a binary copy of the supplied value. If the collection has bag semantics,\r
- /// this updates all equivalent copies in\r
- /// the collection.\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 bool Update(T item)\r
- {\r
- updatecheck();\r
-#if NCP\r
- stackcheck();\r
-\r
- int level = 0;\r
-#endif\r
- Node cursor = root;\r
- int comp = 0;\r
-\r
- while (cursor != null)\r
- {\r
- comp = comparer.Compare(cursor.item, item);\r
- if (comp == 0)\r
- {\r
-#if NCP\r
- Node.CopyNode(ref cursor, maxsnapid, generation);\r
-#endif\r
- cursor.item = item;\r
-#if NCP\r
- while (level > 0)\r
- {\r
- Node child = cursor;\r
-\r
- cursor = path[--level];\r
- path[level] = null;\r
-#if NCP\r
- Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);\r
-#else\r
- if (Node.CopyNode(maxsnapid, ref cursor, generation))\r
- {\r
- if (dirs[level] > 0)\r
- cursor.left = child;\r
- else\r
- cursor.right = child;\r
- }\r
-#endif\r
- }\r
-\r
- root = cursor;\r
-#endif\r
- return true;\r
- }\r
-#if NCP\r
- dirs[level] = comp;\r
- path[level++] = cursor;\r
-#endif\r
- cursor = comp < 0 ? cursor.right : cursor.left;\r
- }\r
-\r
- return false;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Check if this collection contains an item equivalent according to the\r
- /// itemhasher 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
- ///\r
- /// <p>NOTE: the bag implementation is currently wrong!</p>\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 bool UpdateOrAdd(T item)\r
- {\r
- updatecheck();\r
- bool wasfound;\r
-\r
- //Note: blackdepth of the tree is set inside addIterative\r
- if (addIterative(item, ref item, true, out wasfound))\r
- {\r
- size++;\r
-#if MAINTAIN_EXTREMA\r
- if (Compare(item, min) < 0)\r
- min = item;\r
- else if (Compare(item, max) > 0)\r
- max = item;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- depth = root.height;\r
-#endif\r
- return wasfound;\r
- }\r
- else\r
- return true;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove a particular item from this collection. If 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 bool Remove(T item)\r
- {\r
- updatecheck();\r
- if (root == null)\r
- return false;\r
-\r
- return removeIterative(ref item, false);\r
- }\r
-\r
- /// <summary>\r
- /// Remove a particular item from this collection if found. If the collection\r
- /// has bag semantics only one copy equivalent to the supplied item is removed,\r
- /// which one is implementation dependent. \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
- /// <returns>True if the item was found (and removed).</returns>\r
- [Tested]\r
- public bool RemoveWithReturn(ref T item)\r
- {\r
- updatecheck();\r
- if (root == null)\r
- return false;\r
-\r
- return removeIterative(ref item, false);\r
- }\r
-\r
-\r
- private bool removeIterative(ref T item, bool all)\r
- {\r
- //Stage 1: find item\r
- stackcheck();\r
-\r
- int level = 0, comp;\r
- Node cursor = root;\r
-\r
- while (true)\r
- {\r
- comp = comparer.Compare(cursor.item, item);\r
- if (comp == 0)\r
- {\r
- item = cursor.item;\r
-#if BAG\r
- if (!all && cursor.items > 1)\r
- {\r
-#if NCP\r
- Node.CopyNode(ref cursor, maxsnapid, generation);\r
-#endif\r
- cursor.items--;\r
- cursor.size--;\r
- while (level-- > 0)\r
- {\r
- Node kid = cursor;\r
-\r
- cursor = path[level];\r
-#if NCP\r
- Node.update(ref cursor, dirs[level] > 0, kid,maxsnapid,generation);\r
-#endif\r
- cursor.size--;\r
- path[level] = null;\r
- }\r
- size--;\r
- return true;\r
- }\r
-#endif\r
- break;\r
- }\r
-\r
- Node child = comp > 0 ? cursor.left : cursor.right;\r
-\r
- if (child == null)\r
- return false;\r
-\r
- dirs[level] = comp;\r
- path[level++] = cursor;\r
- cursor = child;\r
- }\r
-\r
- return removeIterativePhase2(cursor, level);\r
- }\r
-\r
-\r
- private bool removeIterativePhase2(Node cursor, int level)\r
- {\r
- if (size == 1)\r
- {\r
- clear();\r
- return true;\r
- }\r
-\r
-#if MAINTAIN_EXTREMA\r
- if (Compare(cursor.item, min) == 0)\r
- min = cursor.right != null ? cursor.right.item : path[level - 1].item;\r
- else if (Compare(cursor.item, max) == 0)\r
- max = cursor.left != null ? cursor.left.item : path[level - 1].item;\r
-#endif\r
-#if BAG\r
- int removedcount = cursor.items;\r
- size -= removedcount;\r
-#else\r
- //We are certain to remove one node:\r
- size--;\r
-#endif\r
- //Stage 2: if item's node has no null child, find predecessor\r
- int level_of_item = level;\r
-\r
- if (cursor.left != null && cursor.right != null)\r
- {\r
- dirs[level] = 1;\r
- path[level++] = cursor;\r
- cursor = cursor.left;\r
- while (cursor.right != null)\r
- {\r
- dirs[level] = -1;\r
- path[level++] = cursor;\r
- cursor = cursor.right;\r
- }\r
-#if NCP\r
- Node.CopyNode(ref path[level_of_item], maxsnapid, generation);\r
-#endif\r
- path[level_of_item].item = cursor.item;\r
-#if BAG\r
- path[level_of_item].items = cursor.items;\r
-#endif\r
- }\r
-\r
- //Stage 3: splice out node to be removed\r
- Node newchild = cursor.right == null ? cursor.left : cursor.right;\r
- bool demote_or_rotate = newchild == null && !cursor.red;\r
-\r
- //assert newchild.red \r
- if (newchild != null)\r
- {\r
- newchild.red = false;\r
- }\r
-\r
- if (level == 0)\r
- {\r
- root = newchild;\r
-#if MAINTAIN_HEIGHT\r
- depth = 0;\r
-#endif\r
- return true;\r
- }\r
-\r
- level--;\r
- cursor = path[level];\r
- path[level] = null;\r
-\r
- int comp = dirs[level];\r
- Node childsibling;\r
-#if NCP\r
- Node.update(ref cursor, comp > 0, newchild, maxsnapid, generation);\r
-#else\r
- if (comp > 0)\r
- cursor.left = newchild;\r
- else\r
- cursor.right = newchild;\r
-#endif\r
- childsibling = comp > 0 ? cursor.right : cursor.left;\r
-#if BAG\r
- cursor.size -= removedcount;\r
-#elif MAINTAIN_SIZE\r
- cursor.size--;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(cursor);\r
-#endif\r
-\r
- //Stage 4: demote till we must rotate\r
- Node farnephew = null, nearnephew = null;\r
-\r
- while (demote_or_rotate)\r
- {\r
- if (childsibling.red)\r
- break; //rotate 2+?\r
-\r
- farnephew = comp > 0 ? childsibling.right : childsibling.left;\r
- if (farnephew != null && farnephew.red)\r
- break; //rotate 1b\r
-\r
- nearnephew = comp > 0 ? childsibling.left : childsibling.right;\r
- if (nearnephew != null && nearnephew.red)\r
- break; //rotate 1c\r
-\r
- //demote cursor\r
- childsibling.red = true;\r
-#if MAINTAIN_RANK\r
- cursor.rank--;\r
-#endif\r
- if (level == 0)\r
- {\r
- cursor.red = false;\r
- blackdepth--;\r
-#if MAINTAIN_HEIGHT\r
- depth = root.height;\r
-#endif\r
-#if NCP\r
- root = cursor;\r
-#endif\r
- return true;\r
- }\r
- else if (cursor.red)\r
- {\r
- cursor.red = false;\r
- demote_or_rotate = false;\r
- break; //No rotation\r
- }\r
- else\r
- {\r
- Node child = cursor;\r
-\r
- cursor = path[--level];\r
- path[level] = null;\r
- comp = dirs[level];\r
- childsibling = comp > 0 ? cursor.right : cursor.left;\r
-#if NCP\r
- Node.update(ref cursor, comp > 0, child, maxsnapid, generation);\r
-#endif\r
-#if BAG\r
- cursor.size -= removedcount;\r
-#elif MAINTAIN_SIZE\r
- cursor.size--;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(cursor);\r
-#endif\r
- }\r
- }\r
-\r
- //Stage 5: rotate \r
- if (demote_or_rotate)\r
- {\r
- //At start:\r
- //parent = cursor (temporary for swapping nodes)\r
- //childsibling is the sibling of the updated child (x)\r
- //cursor is always the top of the subtree\r
- Node parent = cursor;\r
-\r
- if (childsibling.red)\r
- {//Case 2 and perhaps more. \r
- //The y.rank == px.rank >= x.rank+2 >=2 so both nephews are != null \r
- //(and black). The grandnephews are children of nearnephew\r
- Node neargrandnephew, fargrandnephew;\r
-\r
- if (comp > 0)\r
- {\r
- nearnephew = childsibling.left;\r
- farnephew = childsibling.right;\r
- neargrandnephew = nearnephew.left;\r
- fargrandnephew = nearnephew.right;\r
- }\r
- else\r
- {\r
- nearnephew = childsibling.right;\r
- farnephew = childsibling.left;\r
- neargrandnephew = nearnephew.right;\r
- fargrandnephew = nearnephew.left;\r
- }\r
-\r
- if (fargrandnephew != null && fargrandnephew.red)\r
- {//Case 2+1b\r
-#if NCP\r
- Node.CopyNode(ref nearnephew, maxsnapid, generation);\r
-\r
- //The end result of this will always be e copy of parent\r
- Node.update(ref parent, comp < 0, neargrandnephew, maxsnapid, generation);\r
- Node.update(ref childsibling, comp > 0, nearnephew, maxsnapid, generation);\r
-#endif\r
- if (comp > 0)\r
- {\r
- nearnephew.left = parent;\r
- parent.right = neargrandnephew;\r
- }\r
- else\r
- {\r
- nearnephew.right = parent;\r
- parent.left = neargrandnephew;\r
- }\r
-\r
- cursor = childsibling;\r
- childsibling.red = false;\r
- nearnephew.red = true;\r
- fargrandnephew.red = false;\r
-#if MAINTAIN_RANK\r
- nearnephew.rank++;\r
- parent.rank--;\r
-#endif\r
-#if BAG\r
- cursor.size = parent.size;\r
- nearnephew.size = cursor.size - cursor.items - farnephew.size;\r
- parent.size = nearnephew.size - nearnephew.items - fargrandnephew.size;\r
-#elif MAINTAIN_SIZE\r
- cursor.size = parent.size;\r
- nearnephew.size = cursor.size - 1 - farnephew.size;\r
- parent.size = nearnephew.size - 1 - fargrandnephew.size;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(parent);\r
- fixheight(nearnephew);\r
- fixheight(cursor);\r
-#endif\r
- }\r
- else if (neargrandnephew != null && neargrandnephew.red)\r
- {//Case 2+1c\r
-#if NCP\r
- Node.CopyNode(ref neargrandnephew, maxsnapid, generation);\r
-#endif\r
- if (comp > 0)\r
- {\r
-#if NCP\r
- Node.update(ref childsibling, true, neargrandnephew, maxsnapid, generation);\r
- Node.update(ref nearnephew, true, neargrandnephew.right, maxsnapid, generation);\r
- Node.update(ref parent, false, neargrandnephew.left, maxsnapid, generation);\r
-#else\r
- childsibling.left = neargrandnephew;\r
- nearnephew.left = neargrandnephew.right;\r
- parent.right = neargrandnephew.left;\r
-#endif\r
- neargrandnephew.left = parent;\r
- neargrandnephew.right = nearnephew;\r
- }\r
- else\r
- {\r
-#if NCP\r
- Node.update(ref childsibling, false, neargrandnephew, maxsnapid, generation);\r
- Node.update(ref nearnephew, false, neargrandnephew.left, maxsnapid, generation);\r
- Node.update(ref parent, true, neargrandnephew.right, maxsnapid, generation);\r
-#else\r
- childsibling.right = neargrandnephew;\r
- nearnephew.right = neargrandnephew.left;\r
- parent.left = neargrandnephew.right;\r
-#endif\r
- neargrandnephew.right = parent;\r
- neargrandnephew.left = nearnephew;\r
- }\r
-\r
- cursor = childsibling;\r
- childsibling.red = false;\r
-#if MAINTAIN_RANK\r
- neargrandnephew.rank++;\r
- parent.rank--;\r
-#endif\r
-#if BAG\r
- cursor.size = parent.size;\r
- parent.size = parent.items + (parent.left == null ? 0 : parent.left.size) + (parent.right == null ? 0 : parent.right.size);\r
- nearnephew.size = nearnephew.items + (nearnephew.left == null ? 0 : nearnephew.left.size) + (nearnephew.right == null ? 0 : nearnephew.right.size);\r
- neargrandnephew.size = neargrandnephew.items + parent.size + nearnephew.size;\r
-#elif MAINTAIN_SIZE\r
- cursor.size = parent.size;\r
- parent.size = 1 + (parent.left == null ? 0 : parent.left.size) + (parent.right == null ? 0 : parent.right.size);\r
- nearnephew.size = 1 + (nearnephew.left == null ? 0 : nearnephew.left.size) + (nearnephew.right == null ? 0 : nearnephew.right.size);\r
- neargrandnephew.size = 1 + parent.size + nearnephew.size;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(parent);\r
- fixheight(nearnephew);\r
- fixheight(neargrandnephew);\r
- fixheight(cursor);\r
-#endif\r
- }\r
- else\r
- {//Case 2 only\r
-#if NCP\r
- Node.update(ref parent, comp < 0, nearnephew, maxsnapid, generation);\r
- Node.update(ref childsibling, comp > 0, parent, maxsnapid, generation);\r
-#else\r
- if (comp > 0)\r
- {\r
- childsibling.left = parent;\r
- parent.right = nearnephew;\r
- }\r
- else\r
- {\r
- childsibling.right = parent;\r
- parent.left = nearnephew;\r
- }\r
-#endif\r
- cursor = childsibling;\r
- childsibling.red = false;\r
- nearnephew.red = true;\r
-#if MAINTAIN_RANK\r
- parent.rank--;\r
-#endif\r
-#if BAG\r
- cursor.size = parent.size;\r
- parent.size -= farnephew.size + cursor.items;\r
-#elif MAINTAIN_SIZE\r
- cursor.size = parent.size;\r
- parent.size -= farnephew.size + 1;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(parent);\r
- fixheight(cursor);\r
-#endif\r
- }\r
- }\r
- else if (farnephew != null && farnephew.red)\r
- {//Case 1b\r
- nearnephew = comp > 0 ? childsibling.left : childsibling.right; \r
-#if NCP\r
- Node.update(ref parent, comp < 0, nearnephew, maxsnapid, generation);\r
- Node.CopyNode(ref childsibling, maxsnapid, generation);\r
- if (comp > 0)\r
- {\r
- childsibling.left = parent;\r
- childsibling.right = farnephew;\r
- }\r
- else\r
- {\r
- childsibling.right = parent;\r
- childsibling.left = farnephew;\r
- }\r
-#else\r
- if (comp > 0)\r
- {\r
- childsibling.left = parent;\r
- parent.right = nearnephew;\r
- }\r
- else\r
- {\r
- childsibling.right = parent;\r
- parent.left = nearnephew;\r
- }\r
-#endif\r
- cursor = childsibling;\r
- cursor.red = parent.red;\r
- parent.red = false;\r
- farnephew.red = false;\r
-\r
-#if MAINTAIN_RANK\r
- childsibling.rank++;\r
- parent.rank--;\r
-#endif\r
-#if BAG\r
- cursor.size = parent.size;\r
- parent.size -= farnephew.size + cursor.items;\r
-#elif MAINTAIN_SIZE\r
- cursor.size = parent.size;\r
- parent.size -= farnephew.size + 1;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(parent);\r
- fixheight(cursor);\r
-#endif\r
- }\r
- else if (nearnephew != null && nearnephew.red)\r
- {//Case 1c\r
-#if NCP\r
- Node.CopyNode(ref nearnephew, maxsnapid, generation);\r
-#endif\r
- if (comp > 0)\r
- {\r
-#if NCP\r
- Node.update(ref childsibling, true, nearnephew.right, maxsnapid, generation);\r
- Node.update(ref parent, false, nearnephew.left, maxsnapid, generation);\r
-#else\r
- childsibling.left = nearnephew.right;\r
- parent.right = nearnephew.left;\r
-#endif\r
- nearnephew.left = parent;\r
- nearnephew.right = childsibling;\r
- }\r
- else\r
- {\r
-#if NCP\r
- Node.update(ref childsibling, false, nearnephew.left, maxsnapid, generation);\r
- Node.update(ref parent, true, nearnephew.right, maxsnapid, generation);\r
-#else\r
- childsibling.right = nearnephew.left;\r
- parent.left = nearnephew.right;\r
-#endif\r
- nearnephew.right = parent;\r
- nearnephew.left = childsibling;\r
- }\r
-\r
- cursor = nearnephew;\r
- cursor.red = parent.red;\r
- parent.red = false;\r
-#if MAINTAIN_RANK\r
- nearnephew.rank++;\r
- parent.rank--;\r
-#endif\r
-#if BAG\r
- cursor.size = parent.size;\r
- parent.size = parent.items + (parent.left == null ? 0 : parent.left.size) + (parent.right == null ? 0 : parent.right.size);\r
- childsibling.size = childsibling.items + (childsibling.left == null ? 0 : childsibling.left.size) + (childsibling.right == null ? 0 : childsibling.right.size);\r
-#elif MAINTAIN_SIZE\r
- cursor.size = parent.size;\r
- parent.size = 1 + (parent.left == null ? 0 : parent.left.size) + (parent.right == null ? 0 : parent.right.size);\r
- childsibling.size = 1 + (childsibling.left == null ? 0 : childsibling.left.size) + (childsibling.right == null ? 0 : childsibling.right.size);\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(parent);\r
- fixheight(childsibling);\r
- fixheight(cursor);\r
-#endif\r
- }\r
- else\r
- {//Case 1a can't happen\r
- throw new Exception("Case 1a can't happen here");\r
- }\r
-\r
- //Resplice cursor:\r
- if (level == 0)\r
- {\r
- root = cursor;\r
- }\r
- else\r
- {\r
- Node swap = cursor;\r
-\r
- cursor = path[--level];\r
- path[level] = null;\r
-#if NCP\r
- Node.update(ref cursor, dirs[level] > 0, swap, maxsnapid, generation);\r
-#else\r
- \r
- if (dirs[level] > 0)\r
- cursor.left = swap;\r
- else\r
- cursor.right = swap;\r
-#endif\r
-#if BAG\r
- cursor.size -= removedcount;\r
-#elif MAINTAIN_SIZE\r
- cursor.size--;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(cursor);\r
-#endif\r
- }\r
- }\r
-\r
- //Stage 6: fixup to the root\r
- while (level > 0)\r
- {\r
- Node child = cursor;\r
-\r
- cursor = path[--level];\r
- path[level] = null;\r
-#if NCP\r
- if (child != (dirs[level] > 0 ? cursor.left : cursor.right))\r
- Node.update(ref cursor, dirs[level] > 0, child, maxsnapid, generation);\r
-#endif\r
-#if BAG\r
- cursor.size -= removedcount;\r
-#elif MAINTAIN_SIZE\r
- cursor.size--;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- fixheight(cursor);\r
-#endif\r
- }\r
-\r
-#if MAINTAIN_HEIGHT\r
- depth = root.height;\r
-#endif\r
-#if NCP\r
- root = cursor;\r
-#endif\r
- return true;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove all items from this collection.\r
- /// </summary>\r
- [Tested]\r
- public void Clear()\r
- {\r
- updatecheck();\r
- clear();\r
- }\r
-\r
-\r
- private void clear()\r
- {\r
- size = 0;\r
- root = null;\r
- blackdepth = 0;\r
-#if MAINTAIN_HEIGHT\r
- depth = 0;\r
-#endif\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove all items in another collection from this one. If this collection\r
- /// has bag semantics, take multiplicities into account.\r
- /// </summary>\r
- /// <param name="items">The items to remove.</param>\r
- [Tested]\r
- public void RemoveAll(MSG.IEnumerable<T> items)\r
- {\r
- updatecheck();\r
-\r
- T jtem;\r
-\r
- foreach (T item in items)\r
- {\r
- if (root == null)\r
- break;\r
-\r
- jtem = item;\r
- removeIterative(ref jtem, false);\r
- }\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove all items not in some other collection from this one. If this collection\r
- /// has bag semantics, take multiplicities into account.\r
- /// </summary>\r
- /// <param name="items">The items to retain.</param>\r
- [Tested]\r
- public void RetainAll(MSG.IEnumerable<T> items)\r
- {\r
- updatecheck();\r
-\r
- //A much more efficient version is possible if items is sorted like this.\r
- //Well, it is unclear how efficient it would be.\r
- //We could use a marking method!?\r
- TreeBag<T> t = (TreeBag<T>)MemberwiseClone();\r
-\r
- t.Clear();\r
- foreach (T item in items)\r
- if (ContainsCount(item) > t.ContainsCount(item))\r
- t.Add(item);\r
-\r
- root = t.root;\r
- size = t.size;\r
- blackdepth = t.blackdepth;\r
-#if MAINTAIN_HEIGHT\r
- depth = t.depth;\r
-#endif\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Check if this collection contains all the values in another collection.\r
- /// If this collection has bag semantics (<code>NoDuplicates==false</code>)\r
- /// the check is made with respect to multiplicities, else multiplicities\r
- /// are not taken into account.\r
- /// </summary>\r
- /// <param name="items">The </param>\r
- /// <returns>True if all values in <code>items</code>is in this collection.</returns>\r
- [Tested]\r
- public bool ContainsAll(MSG.IEnumerable<T> items)\r
- {\r
- //This is worst-case O(m*logn)\r
- foreach (T item in items)\r
- if (!Contains(item)) return false;\r
-\r
- return true;\r
- }\r
-\r
-\r
- //Higher order:\r
- /// <summary>\r
- /// Create a new indexed sorted collection consisting of the items of this\r
- /// indexed sorted collection satisfying a certain predicate.\r
- /// </summary>\r
- /// <param name="filter">The filter delegate defining the predicate.</param>\r
- /// <returns>The new indexed sorted collection.</returns>\r
- [Tested]\r
- public IIndexedSorted<T> FindAll(Filter<T> filter)\r
- {\r
- TreeBag<T> res = new TreeBag<T>(comparer);\r
- MSG.IEnumerator<T> e = GetEnumerator();\r
- Node head = null, tail = null;\r
- int z = 0;\r
-#if BAG\r
- int ec = 0;\r
-#endif\r
- while (e.MoveNext())\r
- {\r
- T thisitem = e.Current;\r
-#if BAG\r
- //We could document that filter will only be called \r
- //once on each unique item. That might even be good for the user!\r
- if (tail!=null && comparer.Compare(thisitem, tail.item) == 0)\r
- {\r
- tail.items++;\r
- ec++;\r
- continue;\r
- }\r
-#endif\r
- if (filter(thisitem))\r
- {\r
- if (head == null)\r
- {\r
- head = tail = new Node();\r
- }\r
- else\r
- {\r
-#if BAG\r
- tail.size = tail.items;\r
-#endif\r
- tail.right = new Node();\r
- tail = tail.right;\r
- }\r
-\r
- tail.item = thisitem;\r
- z++;\r
- }\r
- }\r
-#if BAG\r
- if (tail!=null)\r
- tail.size = tail.items;\r
-#endif\r
-\r
- if (z == 0)\r
- return res;\r
-\r
- int blackheight = 0, red = z, maxred = 1;\r
-\r
- while (maxred <= red)\r
- {\r
- red -= maxred;\r
- maxred <<= 1;\r
- blackheight++;\r
- }\r
-\r
- res.root = TreeBag<T>.maketreer(ref head, blackheight, maxred, red);\r
- res.blackdepth = blackheight;\r
- res.size = z;\r
-#if BAG\r
- res.size += ec;\r
-#endif\r
- return res;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Create a new indexed sorted collection consisting of the results of\r
- /// mapping all items of this list.\r
- /// <exception cref="ArgumentException"/> if the map is not increasing over \r
- /// the items of this collection (with respect to the two given comparison \r
- /// relations).\r
- /// </summary>\r
- /// <param name="mapper">The delegate definging the map.</param>\r
- /// <param name="c">The comparion relation to use for the result.</param>\r
- /// <returns>The new sorted collection.</returns>\r
- [Tested]\r
- public IIndexedSorted<V> Map<V>(Mapper<T,V> mapper, IComparer<V> c)\r
- {\r
- TreeBag<V> res = new TreeBag<V>(c);\r
-\r
- if (size == 0)\r
- return res;\r
-\r
- MSG.IEnumerator<T> e = GetEnumerator();\r
- TreeBag<V>.Node head = null, tail = null;\r
- V oldv = default(V);\r
- int z = 0;\r
-#if BAG\r
- T lastitem = default(T);\r
-#endif\r
- while (e.MoveNext())\r
- {\r
- T thisitem = e.Current;\r
-#if BAG\r
- //We could document that mapper will only be called \r
- //once on each unique item. That might even be good for the user!\r
- if (tail != null && comparer.Compare(thisitem, lastitem) == 0)\r
- {\r
- tail.items++;\r
- continue;\r
- }\r
-#endif\r
- V newv = mapper(thisitem);\r
-\r
- if (head == null)\r
- {\r
- head = tail = new TreeBag<V>.Node();\r
- z++;\r
- }\r
- else\r
- {\r
- int comp = c.Compare(oldv, newv);\r
-#if BAG\r
- if (comp == 0)\r
- {\r
- tail.items++;\r
- continue;\r
- }\r
- if (comp > 0)\r
-#else\r
- if (comp >= 0)\r
-#endif\r
- throw new ArgumentException("mapper not monotonic");\r
-#if BAG\r
- tail.size = tail.items;\r
-#endif\r
- tail.right = new TreeBag<V>.Node();\r
- tail = tail.right;\r
- z++;\r
- }\r
-#if BAG\r
- lastitem = thisitem;\r
-#endif\r
- tail.item = oldv = newv;\r
- }\r
-\r
-#if BAG\r
- tail.size = tail.items;\r
-#endif\r
-\r
- int blackheight = 0, red = z, maxred = 1;\r
-\r
- while (maxred <= red)\r
- {\r
- red -= maxred;\r
- maxred <<= 1;\r
- blackheight++;\r
- }\r
-\r
- res.root = TreeBag<V>.maketreer(ref head, blackheight, maxred, red);\r
- res.blackdepth = blackheight;\r
- res.size = size;\r
- return res;\r
- }\r
-\r
-\r
- //below is the bag utility stuff\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 int ContainsCount(T item)\r
- {\r
-#if BAG\r
- Node next; int comp = 0;\r
-\r
- next = root;\r
- while (next != null)\r
- {\r
- comp = comparer.Compare(next.item, item);\r
- if (comp == 0)\r
- return next.items;\r
-\r
- next = comp < 0 ? right(next) : left(next);\r
- }\r
-\r
- return 0;\r
-#else\r
- //Since we are strictly NoDuplicates we just do\r
- return Contains(item) ? 1 : 0;\r
-#endif\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove all items equivalent to a given value.\r
- /// </summary>\r
- /// <param name="item">The value to remove.</param>\r
- [Tested]\r
- public void RemoveAllCopies(T item)\r
- {\r
-#if BAG\r
- updatecheck();\r
- removeIterative(ref item, true);\r
-#else\r
- \r
- Remove(item);\r
-#endif\r
- }\r
-\r
-\r
- #endregion\r
-\r
- #region IIndexed<T> Members\r
- \r
- private Node findNode(int i)\r
- {\r
-#if NCP\r
- if (isSnapShot)\r
- throw new NotSupportedException("Indexing not supported for snapshots");\r
-#endif\r
-#if MAINTAIN_SIZE\r
- Node next = root;\r
-\r
- if (i >= 0 && i < size)\r
- while (true)\r
- {\r
- int j = next.left == null ? 0 : next.left.size;\r
-\r
- if (i > j)\r
- {\r
-#if BAG\r
- i -= j + next.items; \r
- if (i<0)\r
- return next;\r
-#else\r
- i -= j + 1;\r
-#endif\r
- next = next.right;\r
- }\r
- else if (i == j)\r
- return next;\r
- else\r
- next = next.left;\r
- }\r
-\r
- throw new IndexOutOfRangeException();\r
-#else\r
- throw new NotSupportedException();\r
-#endif\r
- }\r
-\r
-\r
- /// <summary>\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="i">the index to lookup</param>\r
- [Tested]\r
- public T this[int i] { [Tested] get { return findNode(i).item; } }\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 int IndexOf(T item)\r
- {\r
- int upper;\r
-\r
- return indexOf(item, out upper);\r
- }\r
-\r
-\r
- private int indexOf(T item, out int upper)\r
- {\r
-#if NCP\r
- if (isSnapShot)\r
- throw new NotSupportedException("Indexing not supported for snapshots");\r
-#endif\r
-#if MAINTAIN_SIZE\r
- int ind = 0; Node next = root;\r
-\r
- while (next != null)\r
- {\r
- int comp = comparer.Compare(item, next.item);\r
-\r
- if (comp < 0)\r
- next = next.left;\r
- else\r
- {\r
- int leftcnt = next.left == null ? 0 : next.left.size;\r
-\r
- if (comp == 0)\r
- {\r
-#if BAG\r
- upper = ind + leftcnt + next.items - 1;\r
- return ind + leftcnt;\r
-#else\r
- return upper = ind + leftcnt;\r
-#endif\r
- }\r
- else\r
- {\r
-#if BAG\r
- ind = ind + next.items + leftcnt;\r
-#else\r
- ind = ind + 1 + leftcnt;\r
-#endif\r
- next = next.right;\r
- }\r
- }\r
- }\r
-#endif\r
- upper = -1;\r
- return -1;\r
- }\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 int LastIndexOf(T item)\r
- {\r
-#if BAG\r
- int res;\r
- indexOf(item, out res);\r
- return res;\r
-#else\r
- //We have NoDuplicates==true for the set\r
- return IndexOf(item);\r
-#endif\r
- }\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 T RemoveAt(int i)\r
- {\r
- updatecheck();\r
-#if MAINTAIN_SIZE\r
- if (i < 0 || i >= size)\r
- throw new IndexOutOfRangeException("Index out of range for sequenced collection");\r
-\r
- //We must follow the pattern of removeIterative()\r
- while (dirs.Length < 2 * blackdepth)\r
- {\r
- dirs = new int[2 * dirs.Length];\r
- path = new Node[2 * dirs.Length];\r
- }\r
-\r
- int level = 0;\r
- Node cursor = root;\r
-\r
- while (true)\r
- {\r
- int j = cursor.left == null ? 0 : cursor.left.size;\r
-\r
- if (i > j)\r
- {\r
-#if BAG\r
- i -= j + cursor.items;\r
- if (i<0)\r
- break;\r
-#else\r
- i -= j + 1;\r
-#endif\r
- dirs[level] = -1;\r
- path[level++] = cursor;\r
- cursor = cursor.right;\r
- }\r
- else if (i == j)\r
- break;\r
- else\r
- {\r
- dirs[level] = 1;\r
- path[level++] = cursor;\r
- cursor = cursor.left;\r
- }\r
- }\r
-\r
- T retval = cursor.item;\r
-\r
-#if BAG\r
- if (cursor.items>1)\r
- {\r
- resplicebag(level, cursor);\r
- size--;\r
- return retval;\r
- }\r
-#endif\r
- removeIterativePhase2(cursor, level);\r
- return retval;\r
-#else\r
- throw new NotSupportedException();\r
-#endif\r
- }\r
-\r
-#if BAG\r
- private void resplicebag(int level, Node cursor)\r
- {\r
-#if NCP\r
- Node.CopyNode(ref cursor, maxsnapid, generation);\r
-#endif\r
- cursor.items--;\r
- cursor.size--;\r
- while (level-- > 0)\r
- {\r
- Node kid = cursor;\r
-\r
- cursor = path[level];\r
-#if NCP\r
- Node.update(ref cursor, dirs[level] > 0, kid, maxsnapid, generation);\r
-#endif\r
- cursor.size--;\r
- path[level] = null;\r
- }\r
- }\r
-#endif\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 void RemoveInterval(int start, int count)\r
- {\r
- if (start < 0 || count < 0)\r
- throw new ArgumentOutOfRangeException();\r
-\r
- if (start + count > this.size)\r
- throw new ArgumentException();\r
-\r
- updatecheck();\r
-\r
- //This is terrible for large count. We should split the tree at \r
- //the endpoints of the range and fuse the parts!\r
- //We really need good internal destructive split and catenate functions!\r
- for (int i = 0; i < count; i++)\r
- RemoveAt(start);\r
- }\r
-\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="end">The high index of the interval (exclusive).</param>\r
- [Tested]\r
- public IDirectedCollectionValue<T> this[int start, int end]\r
- {\r
- [Tested]\r
- get\r
- {\r
- checkRange(start, end - start);\r
- return new Interval(this, start, end - start, true);\r
- }\r
- }\r
-\r
- #region Interval nested class\r
- class Interval: CollectionValueBase<T>, IDirectedCollectionValue<T>\r
- {\r
- int start, length, stamp;\r
-\r
- bool forwards;\r
-\r
- TreeBag<T> tree;\r
-\r
-\r
- internal Interval(TreeBag<T> tree, int start, int count, bool forwards)\r
- {\r
-#if NCP\r
- if (tree.isSnapShot)\r
- throw new NotSupportedException("Indexing not supported for snapshots");\r
-#endif\r
- this.start = start; this.length = count;this.forwards = forwards;\r
- this.tree = tree; this.stamp = tree.stamp;\r
- }\r
-\r
-\r
- [Tested]\r
- public override int Count { [Tested]get { return length; } }\r
-\r
-\r
- public override Speed CountSpeed { get { return Speed.Constant; } }\r
- \r
- [Tested]\r
- public override MSG.IEnumerator<T> GetEnumerator()\r
- {\r
-#if MAINTAIN_SIZE\r
- tree.modifycheck(stamp);\r
-#if BAG\r
- int togo;\r
-#endif\r
- Node cursor = tree.root;\r
- Node[] path = new Node[2 * tree.blackdepth];\r
- int level = 0, totaltogo = length;\r
-\r
- if (totaltogo == 0)\r
- yield break;\r
-\r
- if (forwards)\r
- {\r
- int i = start;\r
-\r
- while (true)\r
- {\r
- int j = cursor.left == null ? 0 : cursor.left.size;\r
-\r
- if (i > j)\r
- {\r
-#if BAG\r
- i -= j + cursor.items;\r
- if (i < 0)\r
- {\r
- togo = cursor.items + i;\r
- break;\r
- }\r
-#else\r
- i -= j + 1;\r
-#endif\r
- cursor = cursor.right;\r
- }\r
- else if (i == j)\r
- {\r
-#if BAG\r
- togo = cursor.items;\r
-#endif\r
- break;\r
- }\r
- else\r
- {\r
- path[level++] = cursor;\r
- cursor = cursor.left;\r
- }\r
- }\r
-\r
- T current = cursor.item;\r
-\r
- while (totaltogo-- > 0)\r
- {\r
- yield return current;\r
- tree.modifycheck(stamp);\r
-#if BAG\r
- if (--togo > 0)\r
- continue;\r
-#endif\r
- if (cursor.right != null)\r
- {\r
- path[level] = cursor = cursor.right;\r
- while (cursor.left != null)\r
- path[++level] = cursor = cursor.left;\r
- }\r
- else if (level == 0)\r
- yield break;\r
- else\r
- cursor = path[--level];\r
-\r
- current = cursor.item;\r
-#if BAG\r
- togo = cursor.items;\r
-#endif\r
- }\r
- }\r
- else\r
- {\r
- int i = start + length - 1;\r
-\r
- while (true)\r
- {\r
- int j = cursor.left == null ? 0 : cursor.left.size;\r
-\r
- if (i > j)\r
- {\r
-#if BAG\r
- if (i - j < cursor.items)\r
- {\r
- togo = i - j + 1;\r
- break;\r
- }\r
- i -= j + cursor.items;\r
-#else\r
- i -= j + 1;\r
-#endif\r
- path[level++] = cursor;\r
- cursor = cursor.right;\r
- }\r
- else if (i == j)\r
- {\r
-#if BAG\r
- togo = 1;\r
-#endif\r
- break;\r
- }\r
- else\r
- {\r
- cursor = cursor.left;\r
- }\r
- }\r
-\r
- T current = cursor.item;\r
-\r
- while (totaltogo-- > 0)\r
- {\r
- yield return current;\r
- tree.modifycheck(stamp);\r
-#if BAG\r
- if (--togo > 0)\r
- continue;\r
-#endif\r
- if (cursor.left != null)\r
- {\r
- path[level] = cursor = cursor.left;\r
- while (cursor.right != null)\r
- path[++level] = cursor = cursor.right;\r
- }\r
- else if (level == 0)\r
- yield break;\r
- else\r
- cursor = path[--level];\r
-\r
- current = cursor.item;\r
-#if BAG\r
- togo = cursor.items;\r
-#endif\r
- }\r
- }\r
-\r
-#else\r
- throw new NotSupportedException();\r
-#endif\r
- }\r
-\r
-\r
- [Tested]\r
- public IDirectedCollectionValue<T> Backwards()\r
- { return new Interval(tree, start, length, !forwards); }\r
-\r
-\r
- [Tested]\r
- IDirectedEnumerable<T> C5.IDirectedEnumerable<T>.Backwards()\r
- { return Backwards(); }\r
-\r
-\r
- [Tested]\r
- public EnumerationDirection Direction\r
- {\r
- [Tested]\r
- get\r
- {\r
- return forwards ? EnumerationDirection.Forwards : EnumerationDirection.Backwards;\r
- }\r
- }\r
- }\r
- #endregion\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 IDirectedCollectionValue<T> Backwards() { return RangeAll().Backwards(); }\r
-\r
-\r
- [Tested]\r
- IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); }\r
-\r
- #endregion\r
-\r
- #region ISequenced Members\r
- [Tested]\r
- int ISequenced<T>.GetHashCode() { return sequencedhashcode(); }\r
-\r
-\r
- [Tested]\r
- bool ISequenced<T>.Equals(ISequenced<T> that) { return sequencedequals(that); }\r
- #endregion\r
-\r
- #region PriorityQueue Members\r
-\r
- /// <summary>\r
- /// The comparer object supplied at creation time for this collection\r
- /// </summary>\r
- /// <value>The comparer</value>\r
- public IComparer<T> Comparer { get { return comparer; } }\r
-\r
-\r
- /// <summary>\r
- /// Find the current least item of this priority queue.\r
- /// </summary>\r
- /// <returns>The least item.</returns>\r
- [Tested]\r
- public T FindMin()\r
- {\r
- if (size == 0)\r
- throw new InvalidOperationException("Priority queue is empty");\r
-#if MAINTAIN_EXTREMA\r
- return min;\r
-#else\r
- Node cursor = root, next = left(cursor);\r
-\r
- while (next != null)\r
- {\r
- cursor = next;\r
- next = left(cursor);\r
- }\r
-\r
- return cursor.item;\r
-#endif\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove the least item from this priority queue.\r
- /// </summary>\r
- /// <returns>The removed item.</returns>\r
- [Tested]\r
- public T DeleteMin()\r
- {\r
- updatecheck();\r
-\r
- //persistence guard?\r
- if (size == 0)\r
- throw new InvalidOperationException("Priority queue is empty");\r
-\r
- //We must follow the pattern of removeIterative()\r
- stackcheck();\r
-\r
- int level = 0;\r
- Node cursor = root;\r
-\r
- while (cursor.left != null)\r
- {\r
- dirs[level] = 1;\r
- path[level++] = cursor;\r
- cursor = cursor.left;\r
- }\r
-\r
- T retval = cursor.item;\r
-\r
-#if BAG\r
- if (cursor.items > 1)\r
- {\r
- resplicebag(level, cursor);\r
- size--;\r
- return retval;\r
- }\r
-#endif\r
- removeIterativePhase2(cursor, level);\r
- return retval;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Find the current largest item of this priority queue.\r
- /// </summary>\r
- /// <returns>The largest item.</returns>\r
- [Tested]\r
- public T FindMax()\r
- {\r
- if (size == 0)\r
- throw new InvalidOperationException("Priority queue is empty");\r
-\r
-#if MAINTAIN_EXTREMA\r
- return max;\r
-#else\r
- Node cursor = root, next = right(cursor);\r
-\r
- while (next != null)\r
- {\r
- cursor = next;\r
- next = right(cursor);\r
- }\r
-\r
- return cursor.item;\r
-#endif\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove the largest item from this priority queue.\r
- /// </summary>\r
- /// <returns>The removed item.</returns>\r
- [Tested]\r
- public T DeleteMax()\r
- {\r
- //persistence guard?\r
- updatecheck();\r
- if (size == 0)\r
- throw new InvalidOperationException("Priority queue is empty");\r
-\r
- //We must follow the pattern of removeIterative()\r
- stackcheck();\r
-\r
- int level = 0;\r
- Node cursor = root;\r
-\r
- while (cursor.right != null)\r
- {\r
- dirs[level] = -1;\r
- path[level++] = cursor;\r
- cursor = cursor.right;\r
- }\r
-\r
- T retval = cursor.item;\r
-\r
-#if BAG\r
- if (cursor.items > 1)\r
- {\r
- resplicebag(level, cursor);\r
- size--;\r
- return retval;\r
- }\r
-#endif\r
- removeIterativePhase2(cursor, level);\r
- return retval;\r
- }\r
- #endregion\r
-\r
- #region IPredecesorStructure<T> Members\r
-\r
- /// <summary>\r
- /// Find the strict predecessor in the sorted collection of a particular value,\r
- /// i.e. the largest item in the collection less than the supplied value.\r
- /// <exception cref="InvalidOperationException"/> if no such element exists (the\r
- /// supplied value is less than or equal to the minimum of this collection.)\r
- /// </summary>\r
- /// <param name="item">The item to find the predecessor for.</param>\r
- /// <returns>The predecessor.</returns>\r
- [Tested]\r
- public T Predecessor(T item)\r
- {\r
- Node cursor = root, bestsofar = null;\r
-\r
- while (cursor != null)\r
- {\r
- int comp = comparer.Compare(cursor.item, item);\r
-\r
- if (comp < 0)\r
- {\r
- bestsofar = cursor;\r
- cursor = right(cursor);\r
- }\r
- else if (comp == 0)\r
- {\r
- cursor = left(cursor);\r
- while (cursor != null)\r
- {\r
- bestsofar = cursor;\r
- cursor = right(cursor);\r
- }\r
- }\r
- else\r
- cursor = left(cursor);\r
- }\r
-\r
- if (bestsofar != null)\r
- return bestsofar.item;\r
- else\r
- throw new ArgumentOutOfRangeException("item", item, "Below minimum of set");\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Find the weak predecessor in the sorted collection of a particular value,\r
- /// i.e. the largest item in the collection less than or equal to the supplied value.\r
- /// <exception cref="InvalidOperationException"/> if no such element exists (the\r
- /// supplied value is less than the minimum of this collection.)\r
- /// </summary>\r
- /// <param name="item">The item to find the weak predecessor for.</param>\r
- /// <returns>The weak predecessor.</returns>\r
- [Tested]\r
- public T WeakPredecessor(T item)\r
- {\r
- Node cursor = root, bestsofar = null;\r
-\r
- while (cursor != null)\r
- {\r
- int comp = comparer.Compare(cursor.item, item);\r
-\r
- if (comp < 0)\r
- {\r
- bestsofar = cursor;\r
- cursor = right(cursor);\r
- }\r
- else if (comp == 0)\r
- return cursor.item;\r
- else\r
- cursor = left(cursor);\r
- }\r
-\r
- if (bestsofar != null)\r
- return bestsofar.item;\r
- else\r
- throw new ArgumentOutOfRangeException("item", item, "Below minimum of set");\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Find the strict successor in the sorted collection of a particular value,\r
- /// i.e. the least item in the collection greater than the supplied value.\r
- /// <exception cref="InvalidOperationException"/> if no such element exists (the\r
- /// supplied value is greater than or equal to the maximum of this collection.)\r
- /// </summary>\r
- /// <param name="item">The item to find the successor for.</param>\r
- /// <returns>The successor.</returns>\r
- [Tested]\r
- public T Successor(T item)\r
- {\r
- Node cursor = root, bestsofar = null;\r
-\r
- while (cursor != null)\r
- {\r
- int comp = comparer.Compare(cursor.item, item);\r
-\r
- if (comp > 0)\r
- {\r
- bestsofar = cursor;\r
- cursor = left(cursor);\r
- }\r
- else if (comp == 0)\r
- {\r
- cursor = right(cursor);\r
- while (cursor != null)\r
- {\r
- bestsofar = cursor;\r
- cursor = left(cursor);\r
- }\r
- }\r
- else\r
- cursor = right(cursor);\r
- }\r
-\r
- if (bestsofar != null)\r
- return bestsofar.item;\r
- else\r
- throw new ArgumentOutOfRangeException("item", item, "Above maximum of set");\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Find the weak successor in the sorted collection of a particular value,\r
- /// i.e. the least item in the collection greater than or equal to the supplied value.\r
- /// <exception cref="InvalidOperationException"/> if no such element exists (the\r
- /// supplied value is greater than the maximum of this collection.)\r
- /// </summary>\r
- /// <param name="item">The item to find the weak successor for.</param>\r
- /// <returns>The weak successor.</returns>\r
- [Tested]\r
- public T WeakSuccessor(T item)\r
- {\r
- Node cursor = root, bestsofar = null;\r
-\r
- while (cursor != null)\r
- {\r
- int comp = comparer.Compare(cursor.item, item);\r
-\r
- if (comp == 0)\r
- return cursor.item;\r
- else if (comp > 0)\r
- {\r
- bestsofar = cursor;\r
- cursor = left(cursor);\r
- }\r
- else\r
- cursor = right(cursor);\r
- }\r
-\r
- if (bestsofar != null)\r
- return bestsofar.item;\r
- else\r
- throw new ArgumentOutOfRangeException("item", item, "Above maximum of set");\r
- }\r
-\r
- #endregion\r
- \r
- #region ISorted<T> Members\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items greater than or equal to a supplied value.\r
- /// </summary>\r
- /// <param name="bot">The lower bound (inclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- [Tested]\r
- public IDirectedCollectionValue<T> RangeFrom(T bot)\r
- { return new Range(this, true, bot, false, default(T), EnumerationDirection.Forwards); }\r
-\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items between two supplied values.\r
- /// </summary>\r
- /// <param name="bot">The lower bound (inclusive).</param>\r
- /// <param name="top">The upper bound (exclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- [Tested]\r
- public IDirectedCollectionValue<T> RangeFromTo(T bot, T top)\r
- { return new Range(this, true, bot, true, top, EnumerationDirection.Forwards); }\r
-\r
-\r
- /// <summary>\r
- /// Query this sorted collection for items less than a supplied value.\r
- /// </summary>\r
- /// <param name="top">The upper bound (exclusive).</param>\r
- /// <returns>The result directed collection.</returns>\r
- [Tested]\r
- public IDirectedCollectionValue<T> RangeTo(T top)\r
- { return new Range(this, false, default(T), true, top, EnumerationDirection.Forwards); }\r
-\r
-\r
- /// <summary>\r
- /// Create a directed collection with the same items as this collection.\r
- /// </summary>\r
- /// <returns>The result directed collection.</returns>\r
- [Tested]\r
- public IDirectedCollectionValue<T> RangeAll()\r
- { return new Range(this, false, default(T), false, default(T), EnumerationDirection.Forwards); }\r
-\r
-\r
- [Tested]\r
- IDirectedEnumerable<T> ISorted<T>.RangeFrom(T bot) { return RangeFrom(bot); }\r
-\r
-\r
- [Tested]\r
- IDirectedEnumerable<T> ISorted<T>.RangeFromTo(T bot, T top) { return RangeFromTo(bot, top); }\r
-\r
-\r
- [Tested]\r
- IDirectedEnumerable<T> ISorted<T>.RangeTo(T top) { return RangeTo(top); }\r
-\r
-\r
- //Utility for CountXxxx. Actually always called with strict = true.\r
- private int countTo(T item, bool strict)\r
- {\r
-#if NCP\r
- if (isSnapShot)\r
- throw new NotSupportedException("Indexing not supported for snapshots");\r
-#endif\r
-#if MAINTAIN_SIZE\r
- int ind = 0, comp = 0; Node next = root;\r
-\r
- while (next != null)\r
- {\r
- comp = comparer.Compare(item, next.item);\r
- if (comp < 0)\r
- next = next.left;\r
- else\r
- {\r
- int leftcnt = next.left == null ? 0 : next.left.size;\r
-#if BAG\r
- if (comp == 0)\r
- return strict ? ind + leftcnt : ind + leftcnt + next.items;\r
- else\r
- {\r
- ind = ind + next.items + leftcnt;\r
- next = next.right;\r
- }\r
-#else\r
- if (comp == 0)\r
- return strict ? ind + leftcnt : ind + leftcnt + 1;\r
- else\r
- {\r
- ind = ind + 1 + leftcnt;\r
- next = next.right;\r
- }\r
-#endif\r
- }\r
- }\r
-\r
- //if we get here, we are at the same side of the whole collection:\r
- return ind;\r
-#else\r
- throw new NotSupportedException("Code compiled w/o size!");\r
-#endif\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Perform a search in the sorted collection for the ranges in which a\r
- /// non-decreasing function from the item type to <code>int</code> is\r
- /// negative, zero respectively positive. If the supplied cut function is\r
- /// not non-decreasing, the result of this call is undefined.\r
- /// </summary>\r
- /// <param name="c">The cut function <code>T</code> to <code>int</code>, given\r
- /// as an <code>IComparable<T></code> object, where the cut function is\r
- /// the <code>c.CompareTo(T that)</code> method.</param>\r
- /// <param name="low">Returns the largest item in the collection, where the\r
- /// cut function is negative (if any).</param>\r
- /// <param name="lowIsValid">True if the cut function is negative somewhere\r
- /// on this collection.</param>\r
- /// <param name="high">Returns the least item in the collection, where the\r
- /// cut function is positive (if any).</param>\r
- /// <param name="highIsValid">True if the cut function is positive somewhere\r
- /// on this collection.</param>\r
- /// <returns></returns>\r
- [Tested]\r
- public bool Cut(IComparable<T> c, out T low, out bool lowIsValid, out T high, out bool highIsValid)\r
- {\r
- Node cursor = root, lbest = null, rbest = null;\r
- bool res = false;\r
-\r
- while (cursor != null)\r
- {\r
- int comp = c.CompareTo(cursor.item);\r
-\r
- if (comp > 0)\r
- {\r
- lbest = cursor;\r
- cursor = right(cursor);\r
- }\r
- else if (comp < 0)\r
- {\r
- rbest = cursor;\r
- cursor = left(cursor);\r
- }\r
- else\r
- {\r
- res = true;\r
-\r
- Node tmp = left(cursor);\r
-\r
- while (tmp != null && c.CompareTo(tmp.item) == 0)\r
- tmp = left(tmp);\r
-\r
- if (tmp != null)\r
- {\r
- lbest = tmp;\r
- tmp = right(tmp);\r
- while (tmp != null)\r
- {\r
- if (c.CompareTo(tmp.item) > 0)\r
- {\r
- lbest = tmp;\r
- tmp = right(tmp);\r
- }\r
- else\r
- tmp = left(tmp);\r
- }\r
- }\r
-\r
- tmp = right(cursor);\r
- while (tmp != null && c.CompareTo(tmp.item) == 0)\r
- tmp = right(tmp);\r
-\r
- if (tmp != null)\r
- {\r
- rbest = tmp;\r
- tmp = left(tmp);\r
- while (tmp != null)\r
- {\r
- if (c.CompareTo(tmp.item) < 0)\r
- {\r
- rbest = tmp;\r
- tmp = left(tmp);\r
- }\r
- else\r
- tmp = right(tmp);\r
- }\r
- }\r
-\r
- break;\r
- }\r
- }\r
-\r
- if (highIsValid = (rbest != null))\r
- high = rbest.item;\r
- else\r
- high = default(T);\r
-\r
- if (lowIsValid = (lbest != null))\r
- low = lbest.item;\r
- else\r
- low = default(T);\r
-\r
- return res;\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Determine the number of items at or above a supplied threshold.\r
- /// </summary>\r
- /// <param name="bot">The lower bound (inclusive)</param>\r
- /// <returns>The number of matcing items.</returns>\r
- [Tested]\r
- public int CountFrom(T bot) { return size - countTo(bot, true); }\r
-\r
-\r
- /// <summary>\r
- /// Determine the number of items between two supplied thresholds.\r
- /// </summary>\r
- /// <param name="bot">The lower bound (inclusive)</param>\r
- /// <param name="top">The upper bound (exclusive)</param>\r
- /// <returns>The number of matcing items.</returns>\r
- [Tested]\r
- public int CountFromTo(T bot, T top)\r
- {\r
- if (comparer.Compare(bot, top) >= 0)\r
- return 0;\r
-\r
- return countTo(top, true) - countTo(bot, true);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Determine the number of items below a supplied threshold.\r
- /// </summary>\r
- /// <param name="top">The upper bound (exclusive)</param>\r
- /// <returns>The number of matcing items.</returns>\r
- [Tested]\r
- public int CountTo(T top) { return countTo(top, true); }\r
-\r
-\r
- /// <summary>\r
- /// Remove all items of this collection above or at a supplied threshold.\r
- /// </summary>\r
- /// <param name="low">The lower threshold (inclusive).</param>\r
- [Tested]\r
- public void RemoveRangeFrom(T low)\r
- {\r
- updatecheck();\r
-\r
- int count = CountFrom(low);\r
-\r
- if (count == 0)\r
- return;\r
-\r
- for (int i = 0; i < count; i++)\r
- DeleteMax();\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove all items of this collection between two supplied thresholds.\r
- /// </summary>\r
- /// <param name="low">The lower threshold (inclusive).</param>\r
- /// <param name="hi">The upper threshold (exclusive).</param>\r
- [Tested]\r
- public void RemoveRangeFromTo(T low, T hi)\r
- {\r
- updatecheck();\r
-\r
- int count = CountFromTo(low, hi);\r
-\r
- if (count == 0)\r
- return;\r
-\r
- for (int i = 0; i < count; i++)\r
- Remove(Predecessor(hi));\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Remove all items of this collection below a supplied threshold.\r
- /// </summary>\r
- /// <param name="hi">The upper threshold (exclusive).</param>\r
- [Tested]\r
- public void RemoveRangeTo(T hi)\r
- {\r
- updatecheck();\r
-\r
- int count = CountTo(hi);\r
-\r
- if (count == 0)\r
- return;\r
-\r
- for (int i = 0; i < count; i++)\r
- DeleteMin();\r
- }\r
-\r
- #endregion\r
-\r
- #region IPersistent<T> Members\r
-\r
- private bool disposed;\r
-\r
-\r
-\r
- /// <summary>\r
- /// If this tree is a snapshot, remove registration in base tree\r
- /// </summary>\r
- [Tested]\r
- public void Dispose()\r
- {\r
- Dispose(true);\r
- GC.SuppressFinalize(this);\r
- }\r
-\r
-\r
- private void Dispose(bool disposing)\r
- {\r
- if (!disposed)\r
- {\r
- if (disposing) { }\r
-#if NCP\r
- if (isSnapShot)\r
- {\r
- snapdata.Remove(generation, disposing);\r
- snapdata = null;\r
- root = null;\r
- dirs = null;\r
- path = null;\r
- comparer = null;\r
- disposed = true;\r
- }\r
- else { }\r
-#endif\r
- }\r
- }\r
-\r
-\r
- /// <summary>\r
- /// If this tree is a snapshot, remove registration in base tree\r
- /// </summary>\r
- ~TreeBag()\r
- {\r
- Dispose(false);\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Make a (read-only) snap shot of this collection.\r
- /// </summary>\r
- /// <returns>The snap shot.</returns>\r
- [Tested]\r
- public ISorted<T> Snapshot()\r
- {\r
-#if NCP\r
- if (isSnapShot)\r
- throw new InvalidOperationException("Cannot snapshot a snapshot");\r
-\r
- if (snapdata == null)\r
- {\r
- snapdata = new SnapData(this);\r
- }\r
-\r
- snapdata.Add(generation, this);\r
-\r
- TreeBag<T> res = (TreeBag<T>)MemberwiseClone();\r
-\r
- res.isReadOnly = true; res.isSnapShot = true;\r
- maxsnapid = generation++;\r
- return res;\r
-#endif\r
- }\r
-\r
- #endregion\r
-\r
- #region Snapdata nested class\r
- //In a class by itself: the tree itself and snapshots must have a ref to \r
- //the snapids, but we do not want snapshots to have a (strong) ref to the full\r
- //updatable tree, which should be garbagecollectable even if there are still \r
- //live snapshots!\r
- //\r
- //Access to SnapData should be thread safe since we expect finalisers \r
- //of snapshots to remove a snapid that is garbagecollected without \r
- //having been explicitly Disposed. Therefore we access SnapData through \r
- //synchronized method/properties.\r
-\r
-#if NCP\r
- class SnapData\r
- {\r
- TreeBag<int> snapids = new TreeBag<int>(new IC());\r
-\r
- WeakReference master;\r
-\r
-\r
- internal SnapData(TreeBag<T> tree)\r
- {\r
- master = new WeakReference(tree);\r
- }\r
-\r
-\r
- [Tested]\r
- public bool Add(int i, TreeBag<T> tree)\r
- {\r
- lock (this)\r
- {\r
- bool res = snapids.Add(i);\r
-\r
- //assert the following will be i:\r
- tree.maxsnapid = snapids.Count > 0 ? snapids.FindMax() : -1;\r
- return res;\r
- }\r
- }\r
-\r
-\r
- [Tested]\r
- public bool Remove(int i, bool updmaxsnapid)\r
- {\r
- lock (this)\r
- {\r
- bool res = snapids.Remove(i);\r
-\r
- if (updmaxsnapid)\r
- {\r
- //Is this safe or/and overkill?\r
- object t = master.Target;\r
-\r
- if (t != null && master.IsAlive)\r
- {\r
- ((TreeBag<T>)t).maxsnapid = snapids.Count > 0 ? snapids.FindMax() : -1;\r
- }\r
- }\r
-\r
- return res;\r
- }\r
- }\r
- }\r
-\r
-#endif\r
- #endregion\r
-\r
- #region TreeBag.Range nested class\r
- \r
- internal class Range: CollectionValueBase<T>, IDirectedCollectionValue<T>\r
- {\r
- //We actually need exclusive upper and lower bounds, and flags to \r
- //indicate whether the bound is present (we canot rely on default(T))\r
- private int stamp;\r
-\r
- private TreeBag<T> basis;\r
-\r
- private T lowend, highend;\r
-\r
- private bool haslowend, hashighend;\r
-\r
- EnumerationDirection direction;\r
-\r
-\r
- [Tested]\r
- public Range(TreeBag<T> basis, bool haslowend, T lowend, bool hashighend, T highend, EnumerationDirection direction)\r
- {\r
- this.basis = basis;\r
- stamp = basis.stamp;\r
-\r
- //lowind will be const; should we cache highind?\r
- this.lowend = lowend; //Inclusive\r
- this.highend = highend;//Exclusive\r
- this.haslowend = haslowend;\r
- this.hashighend = hashighend;\r
- this.direction = direction;\r
- }\r
- #region IEnumerable<T> Members\r
-\r
-\r
- #region TreeBag.Range.Enumerator nested class\r
- \r
- public class Enumerator: MSG.IEnumerator<T>\r
- {\r
- #region Private Fields\r
- private bool valid = false, ready = true;\r
-\r
- private IComparer<T> comparer;\r
-\r
- private T current;\r
-#if BAG\r
- int togo;\r
-#endif\r
-\r
- private Node cursor;\r
-\r
- private Node[] path; // stack of nodes\r
-\r
- private int level = 0;\r
-\r
- private Range range;\r
-\r
- private bool forwards;\r
-\r
- #endregion\r
- [Tested]\r
- public Enumerator(Range range)\r
- {\r
- comparer = range.basis.comparer;\r
- path = new Node[2 * range.basis.blackdepth];\r
- this.range = range;\r
- forwards = range.direction == EnumerationDirection.Forwards;\r
- cursor = new Node();\r
- if (forwards)\r
- cursor.right = range.basis.root;\r
- else\r
- cursor.left = range.basis.root;\r
- range.basis.modifycheck(range.stamp);\r
- }\r
-\r
-\r
- int compare(T i1, T i2) { return comparer.Compare(i1, i2); }\r
-\r
-\r
- /// <summary>\r
- /// Undefined if enumerator is not valid (MoveNext hash been called returning true)\r
- /// </summary>\r
- /// <value>The current value of the enumerator.</value>\r
- [Tested]\r
- public T Current\r
- {\r
- [Tested]\r
- get\r
- {\r
- if (valid)\r
- return current;\r
- else\r
- throw new InvalidOperationException();\r
- }\r
- }\r
-\r
-\r
- //Maintain a stack of nodes that are roots of\r
- //subtrees not completely exported yet. Invariant:\r
- //The stack nodes together with their right subtrees\r
- //consists of exactly the items we have not passed\r
- //yet (the top of the stack holds current item).\r
- /// <summary>\r
- /// Move enumerator to next item in tree, or the first item if\r
- /// this is the first call to MoveNext. \r
- /// <exception cref="InvalidOperationException"/> if underlying tree was modified.\r
- /// </summary>\r
- /// <returns>True if enumerator is valid now</returns>\r
- [Tested]\r
- public bool MoveNext()\r
- {\r
- range.basis.modifycheck(range.stamp);\r
- if (!ready)\r
- return false;\r
-#if BAG\r
- if (--togo> 0)\r
- return true;\r
-#endif\r
- if (forwards)\r
- {\r
- if (!valid && range.haslowend)\r
- {\r
- cursor = cursor.right;\r
- while (cursor != null)\r
- {\r
- int comp = compare(cursor.item, range.lowend);\r
-\r
- if (comp > 0)\r
- {\r
- path[level++] = cursor;\r
-#if NCP\r
- cursor = range.basis.left(cursor);\r
-#else\r
- cursor = cursor.left;\r
-#endif\r
- }\r
- else if (comp < 0)\r
- {\r
-#if NCP\r
- cursor = range.basis.right(cursor);\r
-#else\r
- cursor = cursor.right;\r
-#endif\r
- }\r
- else\r
- {\r
- path[level] = cursor;\r
- break;\r
- }\r
- }\r
-\r
- if (cursor == null)\r
- {\r
- if (level == 0)\r
- return valid = ready = false;\r
- else\r
- cursor = path[--level];\r
- }\r
- }\r
-#if NCP\r
- else if (range.basis.right(cursor) != null)\r
- {\r
- path[level] = cursor = range.basis.right(cursor);\r
-\r
- Node next = range.basis.left(cursor);\r
-\r
- while (next != null)\r
- {\r
- path[++level] = cursor = next;\r
- next = range.basis.left(cursor);\r
- }\r
- }\r
-#else\r
- else if (cursor.right != null)\r
- {\r
- path[level] = cursor = cursor.right;\r
- while (cursor.left != null)\r
- path[++level] = cursor = cursor.left;\r
- }\r
-#endif\r
- else if (level == 0)\r
- return valid = ready = false;\r
- else\r
- cursor = path[--level];\r
-\r
- current = cursor.item;\r
- if (range.hashighend && compare(current, range.highend) >= 0)\r
- return valid = ready = false;\r
-\r
-#if BAG\r
- togo = cursor.items;\r
-#endif\r
- return valid = true;\r
- }\r
- else\r
- {\r
- if (!valid && range.hashighend)\r
- {\r
- cursor = cursor.left;\r
- while (cursor != null)\r
- {\r
- int comp = compare(cursor.item, range.highend);\r
-\r
- if (comp < 0)\r
- {\r
- path[level++] = cursor;\r
-#if NCP\r
- cursor = range.basis.right(cursor);\r
-#else\r
- cursor = cursor.right;\r
-#endif\r
- }\r
- else\r
- {\r
-#if NCP\r
- cursor = range.basis.left(cursor);\r
-#else\r
- cursor = cursor.left;\r
-#endif\r
- }\r
- }\r
-\r
- if (cursor == null)\r
- {\r
- if (level == 0)\r
- return valid = ready = false;\r
- else\r
- cursor = path[--level];\r
- }\r
- }\r
-#if NCP\r
- else if (range.basis.left(cursor) != null)\r
- {\r
- path[level] = cursor = range.basis.left(cursor);\r
-\r
- Node next = range.basis.right(cursor);\r
-\r
- while (next != null)\r
- {\r
- path[++level] = cursor = next;\r
- next = range.basis.right(cursor);\r
- }\r
- }\r
-#else\r
- else if (cursor.left != null)\r
- {\r
- path[level] = cursor = cursor.left;\r
- while (cursor.right != null)\r
- path[++level] = cursor = cursor.right;\r
- }\r
-#endif\r
- else if (level == 0)\r
- return valid = ready = false;\r
- else\r
- cursor = path[--level];\r
-\r
- current = cursor.item;\r
- if (range.haslowend && compare(current, range.lowend) < 0)\r
- return valid = ready = false;\r
-\r
-#if BAG\r
- togo = cursor.items;\r
-#endif\r
- return valid = true;\r
- }\r
- }\r
-\r
- void SC.IEnumerator.Reset ()\r
- {\r
- throw new NotImplementedException ();\r
- }\r
-\r
- object SC.IEnumerator.Current {\r
- get {\r
- return Current;\r
- }\r
- }\r
-\r
- [Tested]\r
- public void Dispose()\r
- {\r
- comparer = null;\r
- current = default(T);\r
- cursor = null;\r
- path = null;\r
- range = null;\r
- }\r
- }\r
-\r
- #endregion\r
-\r
- [Tested]\r
- public override MSG.IEnumerator<T> GetEnumerator() { return new Enumerator(this); }\r
-\r
-\r
- [Tested]\r
- public EnumerationDirection Direction { [Tested]get { return direction; } }\r
-\r
-\r
- #endregion\r
-\r
- #region Utility\r
- \r
- bool inside(T item)\r
- {\r
- return (!haslowend || basis.comparer.Compare(item, lowend) >= 0) && (!hashighend || basis.comparer.Compare(item, highend) < 0);\r
- }\r
-\r
-\r
- void checkstamp()\r
- {\r
- if (stamp < basis.stamp)\r
- throw new InvalidOperationException("Base collection was modified behind my back!");\r
- }\r
-\r
-\r
- void syncstamp() { stamp = basis.stamp; }\r
- \r
- #endregion\r
-\r
- [Tested]\r
- public IDirectedCollectionValue<T> Backwards()\r
- {\r
- Range b = (Range)MemberwiseClone();\r
-\r
- b.direction = direction == EnumerationDirection.Forwards ? EnumerationDirection.Backwards : EnumerationDirection.Forwards;\r
- return b;\r
- }\r
-\r
-\r
- [Tested]\r
- IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); }\r
-\r
-\r
- [Tested]\r
- public override int Count\r
- {\r
- [Tested]\r
- get\r
- {\r
- return haslowend ? (hashighend ? basis.CountFromTo(lowend, highend) : basis.CountFrom(lowend)) : (hashighend ? basis.CountTo(highend) : basis.Count);\r
- }\r
- }\r
-\r
- //TODO: check that this is correct\r
- public override Speed CountSpeed { get { return Speed.Log; } }\r
-\r
- }\r
-\r
- #endregion\r
-\r
- #region fixheight utility\r
-\r
-#if MAINTAIN_HEIGHT\r
- public void fixheight(Node n)\r
- {\r
- int lh = n.left == null ? 0 : n.left.height + 1;\r
- int rh = n.right == null ? 0 : n.right.height + 1;\r
-\r
- n.height = (short)(lh > rh ? lh : rh);\r
- }\r
-#endif\r
-\r
- #endregion\r
-\r
- #region Diagnostics\r
- /// <summary>\r
- /// Display this node on the console, and recursively its subnodes.\r
- /// </summary>\r
- /// <param name="n">Node to display</param>\r
- /// <param name="space">Indentation</param>\r
- private void minidump(Node n, string space)\r
- {\r
- if (n == null)\r
- {\r
- // System.Console.WriteLine(space + "null");\r
- }\r
- else\r
- {\r
- minidump(n.right, space + " ");\r
- Console.WriteLine(String.Format("{0} {4} (rank={5}, size={1}, items={8}, h={2}, gen={3}, id={6}){7}", space + n.item, \r
-#if MAINTAIN_SIZE\r
- n.size, \r
-#else\r
- 0,\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- n.height, \r
-#else\r
- 0,\r
-#endif\r
-#if NCP\r
- n.generation, \r
-#endif\r
- n.red ? "RED" : "BLACK", \r
-#if MAINTAIN_RANK\r
- n.rank, \r
-#else\r
- 0,\r
-#endif\r
-#if TRACE_ID\r
- n.id,\r
-#else\r
- 0,\r
-#endif\r
-#if NCP\r
-#if SEPARATE_EXTRA\r
- n.extra == null ? "" : String.Format(" [extra: lg={0}, c={1}, i={2}]", n.extra.lastgeneration, n.extra.leftnode ? "L" : "R", n.extra.oldref == null ? "()" : "" + n.extra.oldref.item),\r
-#else\r
- n.lastgeneration == -1 ? "" : String.Format(" [extra: lg={0}, c={1}, i={2}]", n.lastgeneration, n.leftnode ? "L" : "R", n.oldref == null ? "()" : "" + n.oldref.item),\r
-#endif\r
-#else\r
- "",\r
-#endif\r
-#if BAG\r
- n.items\r
-#else\r
- 1\r
-#endif\r
- ));\r
- minidump(n.left, space + " ");\r
- }\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Print the tree structure to the console stdout.\r
- /// </summary>\r
- [Tested(via = "Sawtooth")]\r
- public void dump() { dump(""); }\r
-\r
-\r
- /// <summary>\r
- /// Print the tree structure to the console stdout.\r
- /// </summary>\r
- [Tested(via = "Sawtooth")]\r
- public void dump(string msg)\r
- {\r
- Console.WriteLine(String.Format(">>>>>>>>>>>>>>>>>>> dump {0} (count={1}, blackdepth={2}, depth={3}, gen={4})", msg, size, blackdepth,\r
-#if MAINTAIN_HEIGHT\r
- depth\r
-#else\r
- 0\r
-#endif\r
- , \r
-#if NCP\r
- generation\r
-#endif\r
- ));\r
- minidump(root, "");\r
- check("", Console.Out); Console.WriteLine("<<<<<<<<<<<<<<<<<<<");\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Display this tree on the console.\r
- /// </summary>\r
- /// <param name="msg">Identifying string of this call to dump</param>\r
- /// <param name="err">Extra (error)message to include</param>\r
- void dump(string msg, string err)\r
- {\r
- Console.WriteLine(String.Format(">>>>>>>>>>>>>>>>>>> dump {0} (count={1}, blackdepth={2}, depth={3}, gen={4})", msg, size, blackdepth,\r
-#if MAINTAIN_HEIGHT\r
- depth\r
-#else\r
- 0\r
-#endif\r
- , \r
-#if NCP\r
- generation \r
-#endif\r
- ));\r
- minidump(root, ""); Console.Write(err);\r
- Console.WriteLine("<<<<<<<<<<<<<<<<<<<");\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Print warning m on o if b is false.\r
- /// </summary>\r
- /// <param name="b">Condition that should hold</param>\r
- /// <param name="n">Place (used for id display)</param>\r
- /// <param name="m">Message</param>\r
- /// <param name="o">Output stream</param>\r
- /// <returns>b</returns>\r
- bool massert(bool b, Node n, string m, System.IO.TextWriter o)\r
- {\r
- if (!b) o.WriteLine("*** Node (item={0}, id={1}): {2}", n.item, \r
-#if TRACE_ID\r
- n.id\r
-#else\r
- 0\r
-#endif\r
- , m);\r
-\r
- return b;\r
- }\r
-\r
-\r
- bool rbminicheck(Node n, bool redp, int prank, System.IO.TextWriter o, out T min, out T max, out int blackheight, int maxgen)\r
- {//Red-Black invariant\r
- bool res = true;\r
-\r
- res = massert(!(n.red && redp), n, "RED parent of RED node", o) && res;\r
- res = massert(n.left == null || n.right != null || n.left.red, n, "Left child black, but right child empty", o) && res;\r
- res = massert(n.right == null || n.left != null || n.right.red, n, "Right child black, but left child empty", o) && res;\r
-#if MAINTAIN_RANK\r
- res = massert(n.red == (n.rank == prank), n, "Bad color", o) && res;\r
- res = massert(prank <= n.rank + 1, n, "Parentrank-rank >= 2", o) && res;\r
- res = massert((n.left != null && n.right != null) || n.rank == 1, n, "Rank>1 but empty child", o) && res;\r
-#endif\r
-#if BAG\r
- bool sb = n.size == (n.left == null ? 0 : n.left.size) + (n.right == null ? 0 : n.right.size) + n.items;\r
-\r
- res = massert(sb, n, "Bad size", o) && res;\r
-#elif MAINTAIN_SIZE\r
- bool sb = n.size == (n.left == null ? 0 : n.left.size) + (n.right == null ? 0 : n.right.size) + 1;\r
-\r
- res = massert(sb, n, "Bad size", o) && res;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- int lh = n.left == null ? 0 : n.left.height + 1;\r
- int rh = n.right == null ? 0 : n.right.height + 1;\r
-\r
- res = massert(n.height == (lh < rh ? rh : lh), n, "Bad height", o) && res;\r
-#endif\r
- int therank =\r
-#if MAINTAIN_RANK\r
- n.rank;\r
-#else\r
- 0;\r
-#endif\r
- min = max = n.item;\r
-\r
- T otherext;\r
- int lbh = 0, rbh = 0;\r
-\r
- if (n.left != null)\r
- {\r
- res = rbminicheck(n.left, n.red, therank, o, out min, out otherext, out lbh, generation) && res;\r
- res = massert(comparer.Compare(n.item, otherext) > 0, n, "Value not > all left children", o) && res;\r
- }\r
-\r
- if (n.right != null)\r
- {\r
- res = rbminicheck(n.right, n.red, therank, o, out otherext, out max, out rbh, generation) && res;\r
- res = massert(comparer.Compare(n.item, otherext) < 0, n, "Value not < all right children", o) && res;\r
- }\r
-\r
- res = massert(rbh == lbh, n, "Different blackheights of children", o) && res;\r
- blackheight = n.red ? rbh : rbh + 1;\r
-#if MAINTAIN_RANK\r
- //The rank is the number of black nodes from this one to\r
- //the leaves, not counting this one, but counting 1 for the empty\r
- //virtual leaf nodes.\r
- res = massert(n.rank == rbh + 1, n, "rank!=blackheight " + blackheight, o) && res;\r
-#endif\r
- return res;\r
- }\r
-\r
-\r
-\r
-\r
-#if NCP\r
-\r
- bool rbminisnapcheck(Node n, System.IO.TextWriter o, out int size, out T min, out T max)\r
- {\r
- bool res = true;\r
-\r
- min = max = n.item;\r
-\r
- int lsz = 0, rsz = 0;\r
- T otherext;\r
-#if SEPARATE_EXTRA\r
- Node.Extra extra = n.extra;\r
- Node child = (extra != null && extra.lastgeneration >= treegen && extra.leftnode) ? extra.oldref : n.left;\r
-#else\r
- Node child = (n.lastgeneration >= generation && n.leftnode) ? n.oldref : n.left;\r
-#endif\r
- if (child != null)\r
- {\r
- res = rbminisnapcheck(child, o, out lsz, out min, out otherext) && res;\r
- res = massert(comparer.Compare(n.item, otherext) > 0, n, "Value not > all left children", o) && res;\r
- }\r
-\r
-#if SEPARATE_EXTRA\r
- child = (extra != null && extra.lastgeneration >= treegen && !extra.leftnode) ? extra.oldref : n.right;\r
-#else\r
- child = (n.lastgeneration >= generation && !n.leftnode) ? n.oldref : n.right;\r
-#endif\r
- if (child != null)\r
- {\r
- res = rbminisnapcheck(child, o, out rsz, out otherext, out max) && res;\r
- res = massert(comparer.Compare(n.item, otherext) < 0, n, "Value not < all right children", o) && res;\r
- }\r
-#if BAG\r
- size = n.items + lsz + rsz;\r
-#else\r
- size = 1 + lsz + rsz;\r
-#endif\r
- return res;\r
- }\r
-#endif\r
-\r
- /// <summary>\r
- /// Checks red-black invariant. Dumps tree to console if bad\r
- /// </summary>\r
- /// <param name="name">Title of dump</param>\r
- /// <returns>false if invariant violation</returns>\r
- [Tested(via = "Sawtooth")]\r
- public bool Check(string name)\r
- {\r
- System.Text.StringBuilder e = new System.Text.StringBuilder();\r
- System.IO.TextWriter o = new System.IO.StringWriter(e);\r
-\r
- if (!check(name, o))\r
- return true;\r
- else\r
- {\r
- dump(name, e.ToString());\r
- return false;\r
- }\r
- }\r
-\r
-\r
- /// <summary>\r
- /// Checks red-black invariant. Dumps tree to console if bad\r
- /// </summary>\r
- /// <returns>false if invariant violation</returns>\r
- [Tested]\r
- public bool Check()\r
- {\r
- //return check("", System.IO.TextWriter.Null);\r
- //Console.WriteLine("bamse");\r
- return Check("-");\r
- }\r
-\r
-\r
- bool check(string msg, System.IO.TextWriter o)\r
- {\r
- if (root != null)\r
- {\r
- T max, min;\r
- int blackheight;\r
-#if NCP\r
- if (isSnapShot)\r
- {\r
- //Console.WriteLine("Im'a snapshot");\r
- int thesize;\r
- bool rv = rbminisnapcheck(root, o, out thesize, out min, out max);\r
-\r
- rv = massert(size == thesize, root, "bad snapshot size", o) && rv;\r
- return !rv;\r
- }\r
-#endif\r
-#if MAINTAIN_RANK\r
- bool res = rbminicheck(root, false, root.rank + 1, o, out min, out max, out blackheight, generation);\r
-\r
- res = massert(root.rank == blackdepth, root, "blackdepth!=root.rank", o) && res;\r
-#else\r
- bool res = rbminicheck(root, false, 0, o, out min, out max, out blackheight, generation);\r
-#endif\r
- res = massert(blackheight == blackdepth, root, "bad blackh/d", o) && res;\r
- res = massert(!root.red, root, "root is red", o) && res;\r
-#if MAINTAIN_SIZE\r
- res = massert(root.size == size, root, "count!=root.size", o) && res;\r
-#endif\r
-#if MAINTAIN_HEIGHT\r
- res = massert(root.height == depth, root, "depth!=root.height", o) && res;\r
-#endif\r
- return !res;\r
- }\r
- else\r
- return false;\r
- }\r
- #endregion \r
- }\r
-}\r
-\r
-#endif\r
projects / mono.git / blobdiff