biglist.cs

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

            }
        }

        /// <summary>
        /// Part of the rebalancing algorithm. Adds a balanced node to the rebalance array. 
        /// </summary>
        /// <param name="rebalanceArray">Rebalance array to insert into.</param>
        /// <param name="balancedNode">Node to add.</param>
        private void AddBalancedNodeToRebalanceArray(Node[] rebalanceArray, Node balancedNode)
        {
            int slot;
            int count;
            Node accum = null;
            Debug.Assert(balancedNode.IsBalanced());

            count = balancedNode.Count;
            slot = 0;
            while (count >= FIBONACCI[slot + 1]) {
                Node n = rebalanceArray[slot];
                if (n != null) {
                    rebalanceArray[slot] = null;
                    if (accum == null)
                        accum = n;
                    else
                        accum = accum.PrependInPlace(n, !n.Shared);
                }
                ++slot;
            }

            // slot is the location where balancedNode originally ended up, but possibly
            // not the final resting place.
            if (accum != null)
                balancedNode = balancedNode.PrependInPlace(accum, !accum.Shared);
            for (;;) {
                Node n = rebalanceArray[slot];
                if (n != null) {
                    rebalanceArray[slot] = null;
                    balancedNode = balancedNode.PrependInPlace(n, !n.Shared);
                }

                if (balancedNode.Count < FIBONACCI[slot + 1]) {
                    rebalanceArray[slot] = balancedNode;
                    break;
                }
                ++slot;
            }

#if DEBUG
            // The above operations should ensure that everything in the rebalance array is now almost balanced.
            for (int i = 0; i < rebalanceArray.Length; ++i) {
                if (rebalanceArray[i] != null)
                    Debug.Assert(rebalanceArray[i].IsAlmostBalanced());
            }
#endif //DEBUG
        }

        /// <summary>
        /// Convert the list to a new list by applying a delegate to each item in the collection. The resulting list
        /// contains the result of applying <paramref name="converter"/> to each item in the list, in
        /// order. The current list is unchanged.
        /// </summary>
        /// <typeparam name="TDest">The type each item is being converted to.</typeparam>
        /// <param name="converter">A delegate to the method to call, passing each item in <paramref name="sourceCollection"/>.</param>
        /// <returns>The resulting BigList from applying <paramref name="converter"/> to each item in this list.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="converter"/> is null.</exception>
        public new BigList<TDest> ConvertAll<TDest>(Converter<T, TDest> converter)
        {
            return new BigList<TDest>(Algorithms.Convert<T, TDest>(this, converter));
        }

        /// <summary>
        /// Reverses the current list in place.
        /// </summary>
        public void Reverse()
        {
            Algorithms.ReverseInPlace<T>(this);
        }

        /// <summary>
        /// Reverses the items in the range of <paramref name="count"/> items starting from <paramref name="startIndex"/>, in place.
        /// </summary>
        /// <param name="start">The starting index of the range to reverse.</param>
        /// <param name="count">The number of items in range to reverse.</param>
        public void Reverse(int start, int count)
        {
            Algorithms.ReverseInPlace<T>(Range(start, count));
        }

        /// <summary>
        /// Sorts the list in place.
        /// </summary>
        /// <remarks><para>The Quicksort algorithm is used to sort the items. In virtually all cases,
        /// this takes time O(N log N), where N is the number of items in the list.</para>
        /// <para>Values are compared by using the IComparable or IComparable&lt;T&gt;
        /// interface implementation on the type T.</para></remarks>
        /// <exception cref="InvalidOperationException">The type T does not implement either the IComparable or
        /// IComparable&lt;T&gt; interfaces.</exception>
        public void Sort()
        {
            Sort(Comparers.DefaultComparer<T>());
        }
        
        /// <summary>
        /// Sorts the list in place. A supplied IComparer&lt;T&gt; is used
        /// to compare the items in the list. 
        /// </summary>
        /// <remarks>The Quicksort algorithms is used to sort the items. In virtually all cases,
        /// this takes time O(N log N), where N is the number of items in the list.</remarks>
        /// <param name="comparer">The comparer instance used to compare items in the collection. Only
        /// the Compare method is used.</param>
        public void Sort(IComparer<T> comparer)
        {
            Algorithms.SortInPlace(this, comparer);
        }

        /// <summary>
        /// Sorts the list in place. A supplied Comparison&lt;T&gt; delegate is used
        /// to compare the items in the list.
        /// </summary>
        /// <remarks>The Quicksort algorithms is used to sort the items. In virtually all cases,
        /// this takes time O(N log N), where N is the number of items in the list.</remarks>
        /// <param name="comparison">The comparison delegate used to compare items in the collection.</param>
        public void Sort(Comparison<T> comparison)
        {
            Sort(Comparers.ComparerFromComparison<T>(comparison));
        }


        /// <summary>
        /// Searches a sorted list for an item via binary search. The list must be sorted
        /// in the order defined by the default ordering of the item type; otherwise, 
        /// incorrect results will be returned.
        /// </summary>
        /// <param name="item">The item to search for.</param>
        /// <returns>Returns the index of the first occurence of <paramref name="item"/> in the list. If the item does not occur
        /// in the list, the bitwise complement of the first item larger than <paramref name="item"/> in the list is returned. If no item is 
        /// larger than <paramref name="item"/>, the bitwise complement of Count is returned.</returns>
        /// <exception cref="InvalidOperationException">The type T does not implement either the IComparable or
        /// IComparable&lt;T&gt; interfaces.</exception>
        public int BinarySearch(T item)
        {
            return BinarySearch(item, Comparers.DefaultComparer<T>());
        }

        /// <summary>
        /// Searches a sorted list for an item via binary search. The list must be sorted
        /// by the ordering defined by the passed IComparer&lt;T&gt; interface; otherwise, 
        /// incorrect results will be returned.
        /// </summary>
        /// <param name="item">The item to search for.</param>
        /// <param name="comparer">The IComparer&lt;T&gt; interface used to sort the list.</param>
        /// <returns>Returns the index of the first occurence of <paramref name="item"/> in the list. If the item does not occur
        /// in the list, the bitwise complement of the first item larger than <paramref name="item"/> in the list is returned. If no item is 
        /// larger than <paramref name="item"/>, the bitwise complement of Count is returned.</returns>
        public int BinarySearch(T item, IComparer<T> comparer)
        {
            int count, index;

            count = Algorithms.BinarySearch<T>(this, item, comparer, out index);
            if (count == 0)
                return (~index);
            else
                return index;
        }

        /// <summary>
        /// Searches a sorted list for an item via binary search. The list must be sorted
        /// by the ordering defined by the passed Comparison&lt;T&gt; delegate; otherwise, 
        /// incorrect results will be returned.
        /// </summary>
        /// <param name="item">The item to search for.</param>
        /// <param name="comparison">The comparison delegate used to sort the list.</param>
        /// <returns>Returns the index of the first occurence of <paramref name="item"/> in the list. If the item does not occur
        /// in the list, the bitwise complement of the first item larger than <paramref name="item"/> in the list is returned. If no item is 
        /// larger than <paramref name="item"/>, the bitwise complement of Count is returned.</returns>
        public int BinarySearch(T item, Comparison<T> comparison)
        {
            return BinarySearch(item, Comparers.ComparerFromComparison<T>(comparison));
        }

        
#if DEBUG

        /// <summary>
        /// Attempts to validate the internal consistency of the tree.
        /// </summary>
        public void Validate()
        {
            if (root != null) {
                root.Validate();
                Debug.Assert(Count != 0);
            }
            else
                Debug.Assert(Count == 0);
        }

        /// <summary>
        /// Prints out the internal structure of the tree, for debugging purposes.
        /// </summary>
        public void Print()
        {
            Console.WriteLine("SERIES: Count={0}", Count);
            if (Count > 0) {
                Console.Write("ITEMS: ");
                foreach (T item in this) {
                    Console.Write("{0} ", item);
                }
                Console.WriteLine();
                Console.WriteLine("TREE:");
                root.Print("      ", "      ");
            }
            Console.WriteLine();
        }
#endif //DEBUG

        /// <summary>
        /// The base class for the two kinds of nodes in the tree: Concat nodes
        /// and Leaf nodes.
        /// </summary>
        [Serializable]
        private abstract class Node
        {
            // Number of items in this node.
            public int count;

            // If true, indicates that this node is referenced by multiple 
            // concat nodes or multiple BigList. Neither this node nor 
            // nodes below it may be modifed ever again. Never becomes
            // false after being set to true. It's volatile so that accesses
            // from another thread work appropriately -- if shared is set
            // to true, no other thread will attempt to change the node.
            protected volatile bool shared;        

            /// <summary>
            /// The number of items stored in the node (or below it).
            /// </summary>
            /// <value>The number of items in the node or below.</value>
            public int Count
            {
                get { return count; }
            }

            /// <summary>
            /// Is this node shared by more that one list (or within a single)
            /// lists. If true, indicates that this node, and any nodes below it,
            /// may never be modified. Never becomes false after being set to 
            /// true.
            /// </summary>
            /// <value></value>
            public bool Shared
            {
                get { return shared; }
            }

            /// <summary>
            /// Marks this node as shared by setting the shared variable.
            /// </summary>
            public void MarkShared()
            {
                shared = true;
            }

            /// <summary>
            /// Gets the depth of this node. A leaf node has depth 0, 
            /// a concat node with two leaf children has depth 1, etc.
            /// </summary>
            /// <value>The depth of this node.</value>
            public abstract int Depth { get;}
            /// <summary>
            /// Returns the items at the given index in this node.
            /// </summary>
            /// <param name="index">0-based index, relative to this node.</param>
            /// <returns>Item at that index.</returns>
            public abstract T GetAt(int index);

            /// <summary>
            /// Returns a node that has a sub-range of items from this node. The
            /// sub-range may not be empty, but may extend outside the node. 
            /// In other words, first might be less than zero or last might be greater
            /// than count. But, last can't be less than zero and first can't be
            /// greater than count. Also, last must be greater than or equal to last.
            /// </summary>
            /// <param name="first">Inclusive