redblack.cs

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

                    else
                        return 0;      // item is after or equal to first
                }
                else {
                    if (comparer.Compare(first, item) >= 0)
                        return -1;     // item is before or equal to first.
                    else
                        return 0;      // item is after first
                }
            };
        }


        /// <summary>
        /// Gets a range tester that defines a range by upper bound.
        /// </summary>
        /// <param name="last">The upper bound.</param>
        /// <param name="inclusive">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 UpperBoundedRangeTester(T last, bool inclusive)
        {
            return delegate(T item) {
                if (inclusive) {
                    if (comparer.Compare(last, item) < 0)
                        return 1;      // item is after last.
                    else
                        return 0;      // item is before or equal to last.
                }
                else {
                    if (comparer.Compare(last, item) <= 0)
                        return 1;      // item is after or equal to last
                    else
                        return 0;      // item is before last.
                }
            };
        }

        /// <summary>
        /// Gets a range tester that defines a range by all items equal to an item.
        /// </summary>
        /// <param name="equalTo">The item that is contained in the range.</param>
        /// <returns>A RangeTester delegate that tests for an item equal to <paramref name="equalTo"/>.</returns>
        public RangeTester EqualRangeTester(T equalTo)
        {
            return delegate(T item) {
                return comparer.Compare(item, equalTo);
            };
        }

        /// <summary>
        /// A range tester that defines a range that is the entire tree.
        /// </summary>
        /// <param name="item">Item to test.</param>
        /// <returns>Always returns 0.</returns>
        public int EntireRangeTester(T item)
        {
            return 0;
        }

        /// <summary>
        /// Enumerate the items in a custom range in the tree. The range is determined by 
        /// a RangeTest delegate.
        /// </summary>
        /// <param name="rangeTester">Tests an item against the custom range.</param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates the custom range in order.</returns>
        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
        public IEnumerable<T> EnumerateRange(RangeTester rangeTester)
        {
            return EnumerateRangeInOrder(rangeTester, root);
        }

        /// <summary>
        /// Enumerate all the items in a custom range, under and including node, in-order.
        /// </summary>
        /// <param name="rangeTester">Tests an item against the custom range.</param>
        /// <param name="node">Node to begin enumeration. May be null.</param>
        /// <returns>An enumerable of the items.</returns>
        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
        private IEnumerable<T> EnumerateRangeInOrder(RangeTester rangeTester, Node node)
        {
            int startStamp = changeStamp;

            if (node != null) {
                int compare = rangeTester(node.item);

                if (compare >= 0) {
                    // At least part of the range may lie to the left.
                    foreach (T item in EnumerateRangeInOrder(rangeTester, node.left)) {
                        yield return item;
                        CheckEnumerationStamp(startStamp);
                    }
                }

                if (compare == 0) {
                    // The item is within the range.
                    yield return node.item;
                    CheckEnumerationStamp(startStamp);
                }

                if (compare <= 0) {
                    // At least part of the range lies to the right.
                    foreach (T item in EnumerateRangeInOrder(rangeTester, node.right)) {
                        yield return item;
                        CheckEnumerationStamp(startStamp);
                    }
                }
            }
        }

        /// <summary>
        /// Enumerate the items in a custom range in the tree, in reversed order. The range is determined by 
        /// a RangeTest delegate.
        /// </summary>
        /// <param name="rangeTester">Tests an item against the custom range.</param>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates the custom range in reversed order.</returns>
        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
        public IEnumerable<T> EnumerateRangeReversed(RangeTester rangeTester)
        {
            return EnumerateRangeInReversedOrder(rangeTester, root);
        }

        /// <summary>
        /// Enumerate all the items in a custom range, under and including node, in reversed order.
        /// </summary>
        /// <param name="rangeTester">Tests an item against the custom range.</param>
        /// <param name="node">Node to begin enumeration. May be null.</param>
        /// <returns>An enumerable of the items, in reversed oreder.</returns>
        /// <exception cref="InvalidOperationException">The tree has an item added or deleted during the enumeration.</exception>
        private IEnumerable<T> EnumerateRangeInReversedOrder(RangeTester rangeTester, Node node)
        {
            int startStamp = changeStamp;

            if (node != null) {
                int compare = rangeTester(node.item);

                if (compare <= 0) {
                    // At least part of the range lies to the right.
                    foreach (T item in EnumerateRangeInReversedOrder(rangeTester, node.right)) {
                        yield return item;
                        CheckEnumerationStamp(startStamp);
                    }
                }

                if (compare == 0) {
                    // The item is within the range.
                    yield return node.item;
                    CheckEnumerationStamp(startStamp);
                }

                if (compare >= 0) {
                    // At least part of the range may lie to the left.
                    foreach (T item in EnumerateRangeInReversedOrder(rangeTester, node.left)) {
                        yield return item;
                        CheckEnumerationStamp(startStamp);
                    }
                }
            }
        }


        /// <summary>
        /// Deletes either the first or last item from a range, as identified by a RangeTester
        /// delegate. If the range is empty, 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="rangeTester">Range to delete from.</param>
        /// <param name="deleteFirst">If true, delete the first item from the range, else the last.</param>
        /// <param name="item">Returns the item that was deleted, if true returned.</param>
        /// <returns>True if an element was deleted, false if the range is empty.</returns>
        public bool DeleteItemFromRange(RangeTester rangeTester, bool deleteFirst, out T item)
        {
            Node node;			// The current node.
            Node parent;		// Parent of the current node.
            Node gparent;		// Grandparent of the current node.
            Node sib;			// Sibling of the current node.
            Node keyNode;		// Node with the key that is being removed.

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

            if (root == null) {
                // Nothing in the tree. Go home now.
                item = default(T);
                return false;
            }

            // We decrement counts on the way down the tree. If we end up not finding an item to delete
            // we need a stack to adjust the counts back. 
            Node[] nodeStack = GetNodeStack();
            int nodeStackPtr = 0;  // first free item on the stack.

            // Start at the root.
            node = root;
            sib = parent = gparent = null;
            keyNode = null;

            // Proceed down the tree, making the current node red so it can be removed.
            for (; ; ) {
                Debug.Assert(parent == null || parent.IsRed);
                Debug.Assert(sib == null || !sib.IsRed);
                Debug.Assert(!node.IsRed);

                if ((node.left == null || !node.left.IsRed) && (node.right == null || !node.right.IsRed)) {
                    // node has two black children (null children are considered black).
                    if (parent == null) {
                        // Special case for the root.
                        Debug.Assert(node == root);
                        node.IsRed = true;
                    }
                    else if ((sib.left == null || !sib.left.IsRed) && (sib.right == null || !sib.right.IsRed)) {
                        // sib has two black children.
                        node.IsRed = true;
                        sib.IsRed = true;
                        parent.IsRed = false;
                    }
                    else {
                        if (parent.left == node && (sib.right == null || !sib.right.IsRed)) {
                            // sib has a black child on the opposite side as node.
                            Node tleft = sib.left;
                            Rotate(parent, sib, tleft);
                            sib = tleft;
                        }
                        else if (parent.right == node && (sib.left == null || !sib.left.IsRed)) {
                            // sib has a black child on the opposite side as node.
                            Node tright = sib.right;
                            Rotate(parent, sib, tright);
                            sib = tright;
                        }

                        // sib has a red child.
                        Rotate(gparent, parent, sib);
                        node.IsRed = true;
                        sib.IsRed = true;
                        sib.left.IsRed = false;
                        sib.right.IsRed = false;

                        sib.DecrementCount();
                        nodeStack[nodeStackPtr - 1] = sib;
                        parent.DecrementCount();
                        nodeStack[nodeStackPtr++] = parent;
                    }
                }

                // Compare the key and move down the tree to the correct child.
                do {
                    Node nextNode, nextSib;		// Node we've moving to, and it's sibling.

                    node.DecrementCount();
                    nodeStack[nodeStackPtr++] = node;

                    // Determine which way to move in the tree by comparing the 
                    // current item to what we're looking for.
                    int compare = rangeTester(node.item);

                    if (compare == 0) {
                        // We've found the node to remove. Remember it, then keep traversing the
                        // tree to either find the first/last of equal keys, and if needed, the predecessor
                        // or successor (the actual node to be removed).
                        keyNode = node;
                        if (deleteFirst) {
                            nextNode = node.left; nextSib = node.right;
                        }
                        else {
                            nextNode = node.right; nextSib = node.left;
                        }
                    }
                    else if (compare > 0) {
                        nextNode = node.left; nextSib = node.right;
                    }
                    else {
                        nextNode = node.right; nextSib = node.left;
                    }

                    // Have we reached the end of our tree walk?
                    if (nextNode == null)
                        goto FINISHED;

                    // Move down the tree.
                    gparent = parent;
                    parent = node;
                    node = nextNode;
                    sib = nextSib;
                } while (!parent.IsRed && node.IsRed);

                if (!parent.IsRed) {
                    Debug.Assert(!node.IsRed);
                    // moved to a black child.
                    Rotate(gparent, parent, sib);

                    sib.DecrementCount();
                    nodeStack[nodeStackPtr - 1] = sib;
                    parent.DecrementCount();
                    nodeStack[nodeStackPtr++] = parent;

                    sib.IsRed = false;
                    parent.IsRed = true;
                    gparent = sib;
                    sib = (parent.left == node) ? parent.right : parent.left;
                }
            }

        FINISHED:
            if (keyNode == null) {
                // We never found a node to delete.

                // Return counts back to their previous value.
                for (int i = 0; i < nodeStackPtr; ++i)
                    nodeStack[i].IncrementCount();

                // Color the root black, in case it was colored red above.