biglist.cs

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

//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement 
// contained in the file "License.txt" accompanying this file.
//******************************

using System;
using System.Collections.Generic;
using System.Collections;
using System.Diagnostics;

// CONSIDER: provide more efficient implementation of CopyTo.

namespace Wintellect.PowerCollections
{
    /// <summary>
    /// BigList&lt;T&gt; provides a list of items, in order, with indices of the items ranging from 0 to one less
    /// than the count of items in the collection. BigList&lt;T&gt; is optimized for efficient operations on large (&gt;100 items)
    /// lists, especially for insertions, deletions, copies, and concatinations.
    /// </summary>
    /// <remarks>
    /// <para>BigList&lt;T&gt; class is similar in functionality to the standard List&lt;T&gt; class. Both classes
    /// provide a collection that stores an set of items in order, with indices of the items ranging from 0 to one less
    /// than the count of items in the collection. Both classes provide the ability to add and remove items from any index,
    /// and the get or set the item at any index.</para> 
    /// <para>BigList&lt;T&gt; differs significantly from List&lt;T&gt; in the performance of various operations, 
    /// especially when the lists become large (several hundred items or more). With List&lt;T&gt;, inserting or removing
    /// elements from anywhere in a large list except the end is very inefficient -- every item after the point of inserting
    /// or deletion has to be moved in the list. The BigList&lt;T&gt; class, however, allows for fast insertions
    /// and deletions anywhere in the list. Furthermore, BigList&lt;T&gt; allows copies of a list, sub-parts
    /// of a list, and concatinations of two lists to be very fast. When a copy is made of part or all of a BigList,
    /// two lists shared storage for the parts of the lists that are the same. Only when one of the lists is changed is additional
    /// memory allocated to store the distinct parts of the lists.</para>
    /// <para>Of course, there is a small price to pay for this extra flexibility. Although still quite efficient, using an 
    /// index to get or change one element of a BigList, while still reasonably efficient, is significantly slower than using
    /// a plain List. Because of this, if you want to process every element of a BigList, using a foreach loop is a lot
    /// more efficient than using a for loop and indexing the list.</para>
    /// <para>In general, use a List when the only operations you are using are Add (to the end), foreach,
    /// or indexing, or you are very sure the list will always remain small (less than 100 items). For large (&gt;100 items) lists
    /// that do insertions, removals, copies, concatinations, or sub-ranges, BigList will be more efficient than List. 
    /// In almost all cases, BigList is more efficient and easier to use than LinkedList.</para>
    /// </remarks>
    /// <typeparam name="T">The type of items to store in the BigList.</typeparam>
    [Serializable]
    public class BigList<T>: ListBase<T>, ICloneable
    {
        const uint MAXITEMS = int.MaxValue - 1;    // maximum number of items in a BigList.

#if DEBUG
        const int MAXLEAF = 8;                  // Maximum number of elements in a leaf node -- small for debugging purposes.
#else
        const int MAXLEAF = 120;               // Maximum number of elements in a leaf node. 
#endif
        const int BALANCEFACTOR = 6;      // how far the root must be in depth from fully balanced to invoke the rebalance operation (min 3).

        // The fibonacci numbers. Used in the rebalancing algorithm. Final MaxValue makes sure we don't go off the end.
        static readonly int[] FIBONACCI = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 
            4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 
            1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 
            102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, int.MaxValue};
        const int MAXFIB = 44;  // maximum index in the above, not counting the final MaxValue.



        // If null, the BigList is empty. If non-null, the list has at least one item.
        private Node root;         

        // Holds the change stamp for the collection.
        private int changeStamp;

        /// <summary>
        /// Must be called whenever there is a structural change in the tree. Causes
        /// changeStamp to be changed, which causes any in-progress enumerations
        /// to throw exceptions.
        /// </summary>
        private void StopEnumerations()
        {
            ++changeStamp;
        }

        /// <summary>
        /// Checks the given stamp against the current change stamp. If different, the
        /// collection has changed during enumeration and an InvalidOperationException
        /// must be thrown
        /// </summary>
        /// <param name="startStamp">changeStamp at the start of the enumeration.</param>
        private void CheckEnumerationStamp(int startStamp)
        {
            if (startStamp != changeStamp) {
                throw new InvalidOperationException(Strings.ChangeDuringEnumeration);
            }
        }

        /// <summary>
        /// Creates a new BigList. The BigList is initially empty.
        /// </summary>
        /// <remarks>Creating a empty BigList takes constant time and consumes a very small amount of memory.</remarks>
        public BigList()
        {
            root = null;
        }

        /// <summary>
        /// Creates a new BigList initialized with the items from <paramref name="collection"/>, in order.
        /// </summary>
        /// <remarks>Initializing the tree list with the elements of collection takes time O(N), where N is the number of
        /// items in <paramref name="collection"/>.</remarks>
        /// <param name="collection">The collection used to initialize the BigList. </param>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public BigList(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            root = NodeFromEnumerable(collection);
            CheckBalance();
        }

        /// <summary>
        /// Creates a new BigList initialized with a given number of copies of the items from <paramref name="collection"/>, in order. 
        /// </summary>
        /// <remarks>Initializing the tree list with the elements of collection takes time O(N + log K), where N is the number of
        /// items in <paramref name="collection"/>, and K is the number of copies.</remarks>
        /// <param name="copies">Number of copies of the collection to use.</param>
        /// <param name="collection">The collection used to initialize the BigList. </param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="copies"/> is negative.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public BigList(IEnumerable<T> collection, int copies)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            root = NCopiesOfNode(copies, NodeFromEnumerable(collection));
            CheckBalance();
        }

        /// <summary>
        /// Creates a new BigList that is a copy of <paramref name="list"/>.
        /// </summary>
        /// <remarks>Copying a BigList takes constant time, and little 
        /// additional memory, since the storage for the items of the two lists is shared. However, changing
        /// either list will take additional time and memory. Portions of the list are copied when they are changed.</remarks>
        /// <param name="list">The BigList to copy. </param>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        public BigList(BigList<T> list)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (list.root == null)
                root = null;
            else {
                list.root.MarkShared();
                root = list.root;
            }
        }


        /// <summary>
        /// Creates a new BigList that is several copies of <paramref name="list"/>.
        /// </summary>
        /// <remarks>Creating K copies of a BigList takes time O(log K), and O(log K) 
        /// additional memory, since the storage for the items of the two lists is shared. However, changing
        /// either list will take additional time and memory. Portions of the list are copied when they are changed.</remarks>
        /// <param name="copies">Number of copies of the collection to use.</param>
        /// <param name="list">The BigList to copy. </param>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        public BigList(BigList<T> list, int copies)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (list.root == null)
                root = null;
            else {
                list.root.MarkShared();
                root = NCopiesOfNode(copies, list.root);
            }
        }

        /// <summary>
        /// Creates a new BigList from the indicated Node.
        /// </summary>
        /// <param name="node">Node that becomes the new root. If null, the new BigList is empty.</param>
        private BigList(Node node)
        {
            this.root = node;
            CheckBalance();
        }

        /// <summary>
        /// Gets the number of items stored in the BigList. The indices of the items
        /// range from 0 to Count-1.
        /// </summary>
        /// <remarks>Getting the number of items in the BigList takes constant time.</remarks>
        /// <value>The number of items in the BigList.</value>
        public sealed override int Count
        {
            get
            {
                if (root == null)
                    return 0;
                else
                    return root.Count;
            }
        }

        /// <summary>
        /// Gets or sets an item in the list, by index.
        /// </summary>
        /// <remarks><para> Gettingor setting an item takes time O(log N), where N is the number of items
        /// in the list.</para>
        /// <para>To process each of the items in the list, using GetEnumerator() or a foreach loop is more efficient
        /// that accessing each of the elements by index.</para></remarks>
        /// <param name="index">The index of the item to get or set. The first item in the list
        /// has index 0, the last item has index Count-1.</param>
        /// <returns>The value of the item at the given index.</returns>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is less than zero or 
        /// greater than or equal to Count.</exception>
        public sealed override T this[int index]
        {
            get
            {
                // This could just be a simple call to GetAt on the root.
                // It is recoded as an interative algorithm for performance.

                if (root == null || index < 0 || index >= root.Count)
                    throw new ArgumentOutOfRangeException("index");

                Node current = root;
                ConcatNode curConcat = current as ConcatNode;

                while (curConcat != null) {
                    int leftCount = curConcat.left.Count;
                    if (index < leftCount)
                        current = curConcat.left;
                    else {
                        current = curConcat.right;
                        index -= leftCount;
                    }

                    curConcat = current as ConcatNode;
                }

                LeafNode curLeaf = (LeafNode)current;
                return curLeaf.items[index];
            }

            set
            {
                // This could just be a simple call to SetAtInPlace on the root.
                // It is recoded as an interative algorithm for performance.

                if (root == null || index < 0 || index >= root.Count)
                    throw new ArgumentOutOfRangeException("index");

                // Like List<T>, we stop enumerations after a set operation. This could be made
                // to not happen, but it would be complex, because set operations on a shared node
                // could change the node.
                StopEnumerations();

                if (root.Shared)
                    root = root.SetAt(index, value);

                Node current = root;
                ConcatNode curConcat = current as ConcatNode;

                while (curConcat != null) {
                    int leftCount = curConcat.left.Count;
                    if (index < leftCount) {
                        current = curConcat.left;
                        if (current.Shared) {
                            curConcat.left = current.SetAt(index, value);
                            return;
                        }
                    }
                    else {
                        current = curConcat.right;
                        index -= leftCount;
                        if (current.Shared) {
                            curConcat.right = current.SetAt(index, value);
                            return;
                        }
                    }