redblack.cs

C#写的类似于STL的集合类,首先是C#编写,可以用于.net变程.

            // The tree may be changed.
            StopEnumerations();

            // We increment counts on the way down the tree. If we end up not inserting an items due
            // to a duplicate, we need a stack to adjust the counts back. We don't need the stack if the duplicate
            // policy means that we will always do an insertion.
            bool needStack = !((dupPolicy == DuplicatePolicy.InsertFirst) || (dupPolicy == DuplicatePolicy.InsertLast));
            Node[] nodeStack = null;
            int nodeStackPtr = 0;  // first free item on the stack.
            if (needStack) 
                nodeStack = GetNodeStack();

            while (node != null) {
                // If we find a node with two red children, split it so it doesn't cause problems
				// when inserting a node.
                if (node.left != null && node.left.IsRed && node.right != null && node.right.IsRed) {
                    node = InsertSplit(ggparent, gparent, parent, node, out rotated);

                    if (needStack && rotated) {
                        nodeStackPtr -= 2;
                        if (nodeStackPtr < 0)
                            nodeStackPtr = 0;
                    }
                }

				// Keep track of parent, grandparent, great-grand parent.
				ggparent = gparent; gparent = parent; parent = node;

				// Compare the key and the node. 
				int compare = comparer.Compare(item, node.item);

				if (compare == 0) {
					// Found a node with the data already. Check duplicate policy.
					if (dupPolicy == DuplicatePolicy.DoNothing) {
                        previous = node.item;

                        // Didn't insert after all. Return counts back to their previous value.
                        for (int i = 0; i < nodeStackPtr; ++i)
                            nodeStack[i].DecrementCount();

                        return false;
					}
					else if (dupPolicy == DuplicatePolicy.InsertFirst || dupPolicy == DuplicatePolicy.ReplaceFirst) {
						// Insert first by treating the key as less than nodes in the tree.
						duplicateFound = node;
						compare = -1;
					}
					else {
						Debug.Assert(dupPolicy == DuplicatePolicy.InsertLast || dupPolicy == DuplicatePolicy.ReplaceLast);
						// Insert last by treating the key as greater than nodes in the tree.
						duplicateFound = node;
						compare = 1;
					}
				}

				Debug.Assert(compare != 0);

                node.IncrementCount();
                if (needStack)
                    nodeStack[nodeStackPtr++] = node;

				// Move to the left or right as needed to find the insertion point.
				if (compare < 0) {
					node = node.left;
					wentLeft = true; wentRight = false;
				}
				else {
					node = node.right;
					wentRight = true; wentLeft = false;
				}
			}

            if (duplicateFound != null) {
                previous = duplicateFound.item;

                // Are we replacing instread of inserting?
                if (duplicateFound != null && (dupPolicy == DuplicatePolicy.ReplaceFirst || dupPolicy == DuplicatePolicy.ReplaceLast)) {
                    duplicateFound.item = item;

                    // Didn't insert after all. Return counts back to their previous value.
                    for (int i = 0; i < nodeStackPtr; ++i)
                        nodeStack[i].DecrementCount();

                    return false;
                }
            }
            else {
                previous = default(T);
            }

            // Create a new node.
			node = new Node();
			node.item = item;
            node.Count = 1;

			// Link the node into the tree.
			if (wentLeft) 
				parent.left = node;
			else if (wentRight)
				parent.right = node;
			else {
				Debug.Assert(root == null);
				root = node;
			}

			// Maintain the red-black policy.
			InsertSplit(ggparent, gparent, parent, node, out rotated);

			// We've added a node to the tree, so update the count.
			count += 1;

            return (duplicateFound == null);
		}

		/// <summary>
		/// Split a node with two red children (a 4-node in the 2-3-4 tree formalism), as
		/// part of an insert operation.
		/// </summary>
		/// <param name="ggparent">great grand-parent of "node", can be null near root</param>
		/// <param name="gparent">grand-parent of "node", can be null near root</param>
		/// <param name="parent">parent of "node", can be null near root</param>
		/// <param name="node">Node to split, can't be null</param>
        /// <param name="rotated">Indicates that rotation(s) occurred in the tree.</param>
		/// <returns>Node to continue searching from.</returns>
		private Node InsertSplit(Node ggparent, Node gparent, Node parent, Node node, out bool rotated) {
			if (node != root)
				node.IsRed = true;
			if (node.left != null)
				node.left.IsRed = false;
			if (node.right != null)
				node.right.IsRed = false;

			if (parent != null && parent.IsRed) {
				// Since parent is red, gparent can't be null (root is always black). ggparent
				// might be null, however.
				Debug.Assert(gparent != null);

				// if links from gparent and parent are opposite (left/right or right/left),
				// then rotate.
				if ((gparent.left == parent) != (parent.left == node)) {
					Rotate(gparent, parent, node);
					parent = node;
				}

				gparent.IsRed = true;

				// Do a rotate to prevent two red links in a row.
				Rotate(ggparent, gparent, parent);

				parent.IsRed = false;
                rotated = true;
				return parent;
			}
			else {
                rotated = false;
				return node;
			}
		}

		/// <summary>
		/// Performs a rotation involving the node, it's child and grandchild. The counts of 
        /// childs and grand-child are set the correct values from their children; this is important
        /// if they have been adjusted on the way down the try as part of an insert/delete.
		/// </summary>
		/// <param name="node">Top node of the rotation. Can be null if child==root.</param>
		/// <param name="child">One child of "node". Not null.</param>
		/// <param name="gchild">One child of "child". Not null.</param>
		private void Rotate(Node node, Node child, Node gchild) {
			if (gchild == child.left) {
				child.left = gchild.right;
				gchild.right = child;
			}
			else {
				Debug.Assert(gchild == child.right);
				child.right = gchild.left;
				gchild.left = child;
			}

            // Restore the counts.
            child.Count = (child.left != null ? child.left.Count : 0) + (child.right != null ? child.right.Count : 0) + 1;
            gchild.Count = (gchild.left != null ? gchild.left.Count : 0) + (gchild.right != null ? gchild.right.Count : 0) + 1;

			if (node == null) {
				Debug.Assert(child == root);
				root = gchild;
			}
			else if (child == node.left) {
				node.left = gchild;
			}
			else {
				Debug.Assert(child == node.right);
				node.right = gchild;
			}
		}

		/// <summary>
		/// Deletes a key from the tree. If multiple elements are equal to key, 
		/// deletes the first or last. If no element is equal to the key, 
		/// returns false.
		/// </summary>
		/// <remarks>Top-down algorithm from Weiss. Basic plan is to move down in the tree, 
		/// rotating and recoloring along the way to always keep the current node red, which 
		/// ensures that the node we delete is red. The details are quite complex, however! </remarks>
		/// <param name="key">Key to delete.</param>
		/// <param name="deleteFirst">Which item to delete if multiple are equal to key. True to delete the first, false to delete last.</param>
		/// <param name="item">Returns the item that was deleted, if true returned.</param>
		/// <returns>True if an element was deleted, false if no element had 
		/// specified key.</returns>
        public bool Delete(T key, bool deleteFirst, out T item)
        {
            return DeleteItemFromRange(EqualRangeTester(key), deleteFirst, out item);
        }

        /// 
		/// <summary>
		/// Enumerate all the items in-order
		/// </summary>
		/// <returns>An enumerator for all the items, in order.</returns>
        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
        public IEnumerator<T> GetEnumerator()
        {
			return EnumerateRange(EntireRangeTester).GetEnumerator();
		}

		/// <summary>
		/// Enumerate all the items in-order
		/// </summary>
		/// <returns>An enumerator for all the items, in order.</returns>
        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #region Ranges

        /// <summary>
        /// A delegate that tests if an item is within a custom range. The range must be a contiguous
        /// range of items with the ordering of this tree. The range test function must test
        /// if an item is before, withing, or after the range.
        /// </summary>
        /// <param name="item">Item to test against the range.</param>
        /// <returns>Returns negative if item is before the range, zero if item is withing the range,
        /// and positive if item is after the range.</returns>
        public delegate int RangeTester(T item);

        /// <summary>
        /// Gets a range tester that defines a range by first and last items.
        /// </summary>
        /// <param name="useFirst">If true, bound the range on the bottom by first.</param>
        /// <param name="first">If useFirst is true, the inclusive lower bound.</param>
        /// <param name="useLast">If true, bound the range on the top by last.</param>
        /// <param name="last">If useLast is true, the exclusive upper bound.</param>
        /// <returns>A RangeTester delegate that tests for an item in the given range.</returns>
        public RangeTester BoundedRangeTester(bool useFirst, T first, bool useLast, T last)
        {
            return delegate(T item) {
                if (useFirst && comparer.Compare(first, item) > 0)
                    return -1;     // item is before first.
                else if (useLast && comparer.Compare(last, item) <= 0)
                    return 1;      // item is after or equal to last.
                else
                    return 0;      // item is greater or equal to first, and less than last.
            };
        }

        /// <summary>
        /// Gets a range tester that defines a range by first and last items.
        /// </summary>
        /// <param name="first">The lower bound.</param>
        /// <param name="firstInclusive">True if the lower bound is inclusive, false if exclusive.</param>
        /// <param name="last">The upper bound.</param>
        /// <param name="lastInclusive">True if the upper bound is inclusive, false if exclusive.</param>
        /// <returns>A RangeTester delegate that tests for an item in the given range.</returns>
        public RangeTester DoubleBoundedRangeTester(T first, bool firstInclusive, T last, bool lastInclusive)
        {
            return delegate(T item) {
                if (firstInclusive) {
                    if (comparer.Compare(first, item) > 0)
                        return -1;     // item is before first.
                }
                else {
                    if (comparer.Compare(first, item) >= 0)
                        return -1;     // item is before or equal to first.
                }

                if (lastInclusive) {
                    if (comparer.Compare(last, item) < 0)
                        return 1;      // item is after last.
                }
                else {
                    if (comparer.Compare(last, item) <= 0)
                        return 1;      // item is after or equal to last
                }

                return 0;      // item is between first and last.
            };
        }


        /// <summary>
        /// Gets a range tester that defines a range by a lower bound.
        /// </summary>
        /// <param name="first">The lower bound.</param>
        /// <param name="inclusive">True if the lower bound is inclusive, false if exclusive.</param>
        /// <returns>A RangeTester delegate that tests for an item in the given range.</returns>
        public RangeTester LowerBoundedRangeTester(T first, bool inclusive)
        {
            return delegate(T item) {
                if (inclusive) {
                    if (comparer.Compare(first, item) > 0)
                        return -1;     // item is before first.