biglist.cs

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

                    curConcat = current as ConcatNode;
                }

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

        /// <summary>
        /// Removes all of the items from the BigList.
        /// </summary>
        /// <remarks>Clearing a BigList takes constant time.</remarks>
        public sealed override void Clear()
        {
            StopEnumerations();
            root = null;
        }

        /// <summary>
        /// Inserts a new item at the given index in the BigList. All items at indexes 
        /// equal to or greater than <paramref name="index"/> move up one index.
        /// </summary>
        /// <remarks>The amount of time to insert an item is O(log N), no matter where
        /// in the list the insertion occurs. Inserting an item at the beginning or end of the 
        /// list is O(N). 
        /// </remarks>
        /// <param name="index">The index to insert the item at. After the
        /// insertion, the inserted item is located at this index. The
        /// first item has index 0.</param>
        /// <param name="item">The item to insert at the given index.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
        /// less than zero or greater than Count.</exception>
        public sealed override void Insert(int index, T item)
        {
            StopEnumerations();

            if ((uint)Count + 1 > MAXITEMS)
                throw new InvalidOperationException(Strings.CollectionTooLarge);

            if (index <= 0 || index >= Count) {
                if (index == 0)
                    AddToFront(item);
                else if (index == Count)
                    Add(item);
                else
                    throw new ArgumentOutOfRangeException("index");
            }
            else {
                if (root == null)
                    root = new LeafNode(item);
                else {
                    Node newRoot = root.InsertInPlace(index, item);
                    if (newRoot != root) {
                        root = newRoot;
                        CheckBalance();
                    }
                }
            }
        }

        /// <summary>
        /// Inserts a collection of items at the given index in the BigList. All items at indexes 
        /// equal to or greater than <paramref name="index"/> increase their indices 
        /// by the number of items inserted.
        /// </summary>
        /// <remarks>The amount of time to insert an arbitrary collection in the BigList is O(M + log N), 
        /// where M is the number of items inserted, and N is the number of items in the list.
        /// </remarks>
        /// <param name="index">The index to insert the collection at. After the
        /// insertion, the first item of the inserted collection is located at this index. The
        /// first item has index 0.</param>
        /// <param name="collection">The collection of items to insert at the given index.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
        /// less than zero or greater than Count.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public void InsertRange(int index, IEnumerable<T> collection)
        {
            StopEnumerations();

            if (collection == null)
                throw new ArgumentNullException("collection");

            if (index <= 0 || index >= Count) {
                if (index == 0)
                    AddRangeToFront(collection);
                else if (index == Count)
                    AddRange(collection);
                else
                    throw new ArgumentOutOfRangeException("index");
            }
            else {
                Node node = NodeFromEnumerable(collection);
                if (node == null)
                    return;
                else if (root == null)
                    root = node;
                else {
                    if ((uint)Count + (uint)node.Count > MAXITEMS)
                        throw new InvalidOperationException(Strings.CollectionTooLarge);

                    Node newRoot = root.InsertInPlace(index, node, true);
                    if (newRoot != root) {
                        root = newRoot;
                        CheckBalance();
                    }
                }
            }
        }

        /// <summary>
        /// Inserts a BigList of items at the given index in the BigList. All items at indexes 
        /// equal to or greater than <paramref name="index"/> increase their indices 
        /// by the number of items inserted.
        /// </summary>
        /// <remarks>The amount of time to insert another BigList is O(log N), 
        /// where N is the number of items in the list, regardless of the number of items in the 
        /// inserted list. Storage is shared between the two lists until one of them is changed.
        /// </remarks>
        /// <param name="index">The index to insert the collection at. After the
        /// insertion, the first item of the inserted collection is located at this index. The
        /// first item has index 0.</param>
        /// <param name="list">The BigList of items to insert at the given index.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
        /// less than zero or greater than Count.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        public void InsertRange(int index, BigList<T> list)
        {
            StopEnumerations();

            if (list == null)
                throw new ArgumentNullException("list");
            if ((uint)Count + (uint)list.Count > MAXITEMS)
                throw new InvalidOperationException(Strings.CollectionTooLarge);

            if (index <= 0 || index >= Count) {
                if (index == 0)
                    AddRangeToFront(list);
                else if (index == Count)
                    AddRange(list);
                else
                    throw new ArgumentOutOfRangeException("index");
            }
            else {
                if (list.Count == 0)
                    return;

                if (root == null) {
                    list.root.MarkShared();
                    root = list.root;
                }
                else {
                    if (list.root == root)
                        root.MarkShared();     // make sure inserting into itself works.

                    Node newRoot = root.InsertInPlace(index, list.root, false);
                    if (newRoot != root) {
                        root = newRoot;
                        CheckBalance();
                    }
                }
            }
        }

        /// <summary>
        /// Removes the item at the given index in the BigList. All items at indexes 
        /// greater than <paramref name="index"/> move down one index.
        /// </summary>
        /// <remarks>The amount of time to delete an item in the BigList is O(log N),
        /// where N is the number of items in the list. 
        /// </remarks>
        /// <param name="index">The index in the list to remove the item at. The
        /// first item in the list has index 0.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
        /// less than zero or greater than or equal to Count.</exception>
        public sealed override void RemoveAt(int index)
        {
            RemoveRange(index, 1);
        }

        /// <summary>
        /// Removes a range of items at the given index in the Deque. All items at indexes 
        /// greater than <paramref name="index"/> move down <paramref name="count"/> indices
        /// in the Deque.
        /// </summary>
        /// <remarks>The amount of time to delete <paramref name="count"/> items in the Deque is proportional
        /// to the distance of index from the closest end of the Deque, plus <paramref name="count"/>: 
        /// O(count + Min(<paramref name="index"/>, Count - 1 - <paramref name="index"/>)).
        /// </remarks>
        /// <param name="index">The index in the list to remove the range at. The
        /// first item in the list has index 0.</param>
        /// <param name="count">The number of items to remove.</param>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
        /// less than zero or greater than or equal to Count, or <paramref name="count"/> is less than zero
        /// or too large.</exception>
        public void RemoveRange(int index, int count)
        {
            if (count == 0)
                return;              // nothing to do.
            if (index < 0 || index >= Count)
                throw new ArgumentOutOfRangeException("index");
            if (count < 0 || count > Count - index)
                throw new ArgumentOutOfRangeException("count");

            StopEnumerations();

            Node newRoot = root.RemoveRangeInPlace(index, index + count - 1);
            if (newRoot != root) {
                root = newRoot;
                CheckBalance();
            }
        }

        /// <summary>
        /// Adds an item to the end of the BigList. The indices of all existing items
        /// in the Deque are unchanged. 
        /// </summary>
        /// <remarks>Adding an item takes, on average, constant time.</remarks>
        /// <param name="item">The item to add.</param>
        public sealed override void Add(T item)
        {
            if ((uint)Count + 1 > MAXITEMS)
                throw new InvalidOperationException(Strings.CollectionTooLarge);

            StopEnumerations();

            if (root == null)
                root = new LeafNode(item);
            else {
                Node newRoot = root.AppendInPlace(item);
                if (newRoot != root) {
                    root = newRoot;
                    CheckBalance();
                }
            }
        }

        /// <summary>
        /// Adds an item to the beginning of the BigList. The indices of all existing items
        /// in the Deque are increased by one, and the new item has index zero. 
        /// </summary>
        /// <remarks>Adding an item takes, on average, constant time.</remarks>
        /// <param name="item">The item to add.</param>
        public void AddToFront(T item)
        {
            if ((uint)Count + 1 > MAXITEMS)
                throw new InvalidOperationException(Strings.CollectionTooLarge);

            StopEnumerations();

            if (root == null)
                root = new LeafNode(item);
            else {
                Node newRoot = root.PrependInPlace(item);
                if (newRoot != root) {
                    root = newRoot;
                    CheckBalance();
                }
            }
        }

        /// <summary>
        /// Adds a collection of items to the end of BigList. The indices of all existing items
        /// are unchanged. The last item in the added collection becomes the
        /// last item in the BigList.
        /// </summary>
        /// <remarks>This method takes time O(M + log N), where M is the number of items in the 
        /// <paramref name="collection"/>, and N is the size of the BigList.</remarks>
        /// <param name="collection">The collection of items to add.</param>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public void AddRange(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            StopEnumerations();

            Node node = NodeFromEnumerable(collection);
            if (node == null)
                return;
            else if (root == null) {
                root = node;
                CheckBalance();
            }