biglist.cs

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

            if (root != null && maxItems > 0) {
                ConcatNode[] stack = new ConcatNode[root.Depth];
                bool[] leftStack = new bool[root.Depth];
                int stackPtr = 0, startIndex = 0;
                Node current = root;
                LeafNode currentLeaf;
                ConcatNode currentConcat;

                if (start != 0) {
                    // Set current to the node containing start, and set startIndex to
                    // the index within that node.
                    if (start < 0 || start >= root.Count)
                        throw new ArgumentOutOfRangeException("start");

                    currentConcat = current as ConcatNode;
                    startIndex = start;
                    while (currentConcat != null) {
                        stack[stackPtr] = currentConcat;
                        
                        int leftCount = currentConcat.left.Count;
                        if (startIndex < leftCount) {
                            leftStack[stackPtr] = true;
                            current = currentConcat.left;
                        }
                        else {
                            leftStack[stackPtr] = false;
                            current = currentConcat.right;
                            startIndex -= leftCount;
                        }

                        ++stackPtr;
                        currentConcat = current as ConcatNode;
                    }
                }

                for (; ; ) {
                    // If not already at a leaf, walk to the left to find a leaf node.
                    while ((currentConcat = current as ConcatNode) != null) {
                        stack[stackPtr] = currentConcat;
                        leftStack[stackPtr] = true;
                        ++stackPtr;
                        current = currentConcat.left;
                    }

                    // Iterate the leaf.
                    currentLeaf = (LeafNode)current;

                    int limit = currentLeaf.Count;
                    if (limit > startIndex + maxItems)
                        limit = startIndex + maxItems;

                    for (int i = startIndex; i < limit; ++i) {
                        yield return currentLeaf.items[i];
                        CheckEnumerationStamp(startStamp);
                    }

                    // Update the number of items to interate.
                    maxItems -= limit - startIndex;
                    if (maxItems <= 0)
                        yield break;    // Done!

                    // From now on, start enumerating at 0.
                    startIndex = 0;

                    // Go back up the stack until we find a place to the right
                    // we didn't just come from.
                    for (; ; ) {
                        ConcatNode parent;
                        if (stackPtr == 0)
                            yield break;        // iteration is complete.

                        parent = stack[--stackPtr];
                        if (leftStack[stackPtr]) {
                            leftStack[stackPtr] = false;
                            ++stackPtr;
                            current = parent.right;
                            break;
                        }

                        current = parent;
                        // And keep going up...
                    }

                    // current is now a new node we need to visit. Loop around to get it.
                }
            }
        }

        /// <summary>
        /// Enumerates all of the items in the list, in order. The item at index 0
        /// is enumerated first, then the item at index 1, and so on. Usually, the
        /// foreach statement is used to call this method implicitly.
        /// </summary>
        /// <remarks>Enumerating all of the items in the list take time O(N), where
        /// N is the number of items in the list. Using GetEnumerator() or foreach
        /// is much more efficient than accessing all items by index.</remarks>
        /// <returns>An IEnumerator&lt;T&gt; that enumerates all the
        /// items in the list.</returns>
        public sealed override IEnumerator<T> GetEnumerator()
        {
            return GetEnumerator(0, int.MaxValue);
        }

        /// <summary>
        /// Given an IEnumerable&lt;T&gt;, create a new Node with all of the 
        /// items in the enumerable. Returns null if the enumerable has no items.
        /// </summary>
        /// <param name="collection">The collection to copy.</param>
        /// <returns>Returns a Node, not shared or with any shared children, 
        /// with the items from the collection. If the collection was empty,
        /// null is returned.</returns>
        private Node NodeFromEnumerable(IEnumerable<T> collection)
        {
            Node node = null;
            LeafNode leaf;
            IEnumerator<T> enumerator = collection.GetEnumerator();

            while ((leaf = LeafFromEnumerator(enumerator)) != null) {
                if (node == null)
                    node = leaf;
                else {
                    if ((uint)(node.count) + (uint)(leaf.count) > MAXITEMS)
                        throw new InvalidOperationException(Strings.CollectionTooLarge);

                    node = node.AppendInPlace(leaf, true);
                }
            }

            return node;
        }

        /// <summary>
        /// Consumes up to MAXLEAF items from an Enumerator and places them in a leaf
        /// node. If the enumerator is at the end, null is returned.
        /// </summary>
        /// <param name="enumerator">The enumerator to take items from.</param>
        /// <returns>A LeafNode with items taken from the enumerator. </returns>
        private LeafNode LeafFromEnumerator(IEnumerator<T> enumerator)
        {
            int i = 0;
            T[] items = null;

            while (i < MAXLEAF && enumerator.MoveNext()) {
                if (i == 0)
                    items = new T[MAXLEAF];
                items[i++] = enumerator.Current;
            }

            if (items != null)
                return new LeafNode(i, items);
            else
                return null;
        }

        /// <summary>
        /// Create a node that has N copies of the given node. 
        /// </summary>
        /// <param name="copies">Number of copies. Must be non-negative.</param>
        /// <param name="node">Node to make copies of.</param>
        /// <returns>null if node is null or copies is 0. Otherwise, a node consisting of <paramref name="copies"/> copies
        /// of node.</returns>
        /// <exception cref="ArgumentOutOfRangeException">copies is negative.</exception>
        private Node NCopiesOfNode(int copies, Node node)
        {
            if (copies < 0)
                throw new ArgumentOutOfRangeException("copies", Strings.ArgMustNotBeNegative);

            // Do the simple cases.
            if (copies == 0 || node == null)
                return null;
            if (copies == 1)
                return node;

            if ((long)copies * (long)(node.count) > MAXITEMS)
                throw new InvalidOperationException(Strings.CollectionTooLarge);

            // Build up the copies by powers of two.
            int n = 1;
            Node power = node, builder = null;
            while (copies > 0) {
                power.MarkShared();

                if ((copies & n) != 0) {
                    // This power of two is used in the final result.
                    copies -= n;
                    if (builder == null)
                        builder = power;
                    else
                        builder = builder.Append(power, false);
                }

                n *= 2;
                power = power.Append(power, false);
            }

            return builder;
        }

        /// <summary>
        /// Check the balance of the current tree and rebalance it if it is more than BALANCEFACTOR
        /// levels away from fully balanced. Note that rebalancing a tree may leave it two levels away from 
        /// fully balanced.
        /// </summary>
        private void CheckBalance()
        {
            if (root != null &&
                (root.Depth > BALANCEFACTOR && !(root.Depth - BALANCEFACTOR <= MAXFIB && Count >= FIBONACCI[root.Depth - BALANCEFACTOR]))) 
            {
                Rebalance();
            }
        }

        /// <summary>
        /// Rebalance the current tree. Once rebalanced, the depth of the current tree is no more than
        /// two levels from fully balanced, where fully balanced is defined as having Fibonacci(N+2) or more items
        /// in a tree of depth N.
        /// </summary>
        /// <remarks>The rebalancing algorithm is from "Ropes: an Alternative to Strings", by 
        /// Boehm, Atkinson, and Plass, in SOFTWARE--PRACTICE AND EXPERIENCE, VOL. 25(12), 1315–1330 (DECEMBER 1995).
        /// </remarks>
        internal void Rebalance()
        {
            Node[] rebalanceArray;
            int slots;

            // The basic rebalancing algorithm is add nodes to a rabalance array, where a node at index K in the 
            // rebalance array has Fibonacci(K+1) to Fibonacci(K+2) items, and the entire list has the nodes
            // from largest to smallest concatenated.

            if (root == null)
                return;
            if (root.Depth <= 1 || (root.Depth-2 <= MAXFIB && Count >= FIBONACCI[root.Depth-2]))
                return;      // already sufficiently balanced.

            // How many slots does the rebalance array need?
            for (slots = 0; slots <= MAXFIB; ++slots)
                if (root.Count < FIBONACCI[slots])
                    break;
            rebalanceArray = new Node[slots];

            // Add all the nodes to the rebalance array.
            AddNodeToRebalanceArray(rebalanceArray, root, false);

            // Concatinate all the node in the rebalance array.
            Node result = null;
            for (int slot = 0; slot < slots; ++slot) {
                Node n = rebalanceArray[slot];
                if (n != null) {
                    if (result == null)
                        result = n;
                    else
                        result = result.PrependInPlace(n, !n.Shared);
                }
            }

            // And we're done. Check that it worked!
            root = result;
            Debug.Assert(root.Depth <= 1 || (root.Depth - 2 <= MAXFIB && Count >= FIBONACCI[root.Depth - 2]));
        }

        /// <summary>
        /// Part of the rebalancing algorithm. Adds a node to the rebalance array. If it is already balanced, add it directly, otherwise
        /// add its children.
        /// </summary>
        /// <param name="rebalanceArray">Rebalance array to insert into.</param>
        /// <param name="node">Node to add.</param>
        /// <param name="shared">If true, mark the node as shared before adding, because one
        /// of its parents was shared.</param>
        private void AddNodeToRebalanceArray(Node[] rebalanceArray, Node node, bool shared)
        {
            if (node.Shared)
                shared = true;

            if (node.IsBalanced()) {
                if (shared)
                    node.MarkShared();
                AddBalancedNodeToRebalanceArray(rebalanceArray, node);
            }
            else {
                ConcatNode n = (ConcatNode)node;          // leaf nodes are always balanced.
                AddNodeToRebalanceArray(rebalanceArray, n.left, shared);
                AddNodeToRebalanceArray(rebalanceArray, n.right, shared);