biglist.cs

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

            else {
                if ((uint)Count + (uint)node.count > MAXITEMS)
                    throw new InvalidOperationException(Strings.CollectionTooLarge);

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

        /// <summary>
        /// Adds a collection of items to the front of BigList. The indices of all existing items
        /// in the are increased by the number of items in <paramref name="collection"/>. 
        /// The first item in the added collection becomes the first 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 AddRangeToFront(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();
            }
            else {
                if ((uint)Count + (uint)node.Count > MAXITEMS)
                    throw new InvalidOperationException(Strings.CollectionTooLarge);

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

        /// <summary>
        /// Creates a new BigList that is a copy of this 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>
        /// <returns>A copy of the current list</returns>
        public BigList<T> Clone()
        {
            if (root == null)
                return new BigList<T>();
            else {
                root.MarkShared();
                return new BigList<T>(root);
            }
        }

        /// <summary>
        /// Creates a new BigList that is a copy of this 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>
        /// <returns>A copy of the current list</returns>
        object ICloneable.Clone()
        {
            return Clone();
        }

        /// <summary>
        /// Makes a deep clone of this BigList. A new BigList is created with a clone of
        /// each element of this set, by calling ICloneable.Clone on each element. If T is
        /// a value type, then this method is the same as Clone.
        /// </summary>
        /// <remarks><para>If T is a reference type, it must implement
        /// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
        /// <para>If T is a reference type, cloning the list takes time approximate O(N), where N is the number of items in the list.</para></remarks>
        /// <returns>The cloned set.</returns>
        /// <exception cref="InvalidOperationException">T is a reference type that does not implement ICloneable.</exception>
        public BigList<T> CloneContents()
        {
            if (root == null)
                return new BigList<T>();
            else {
                bool itemIsValueType;
                if (!Util.IsCloneableType(typeof(T), out itemIsValueType))
                    throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, typeof(T).FullName));

                if (itemIsValueType)
                    return Clone();

                // Create a new list by converting each item in this list via cloning.
                return new BigList<T>(Algorithms.Convert<T,T>(this, delegate(T item) {
                    if (item == null)
                        return default(T);    // Really null, because we know T is a reference type
                    else
                        return (T)(((ICloneable)item).Clone());
                }));
            }
        }

        /// <summary>
        /// Adds a BigList of items to the end of BigList. The indices of all existing items
        /// are unchanged. The last item in <paramref name="list"/> becomes the
        /// last item in this list. The added list <paramref name="list"/> is unchanged.
        /// </summary>
        /// <remarks>This method takes, on average, constant time, regardless of the size
        /// of either list. Although conceptually all of the items in <paramref name="list"/> are
        /// copied, storage is shared between the two lists until changes are made to the 
        /// shared sections.</remarks>
        /// <param name="list">The list of items to add.</param>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        public void AddRange(BigList<T> list)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if ((uint)Count + (uint)list.Count > MAXITEMS)
                throw new InvalidOperationException(Strings.CollectionTooLarge);

            if (list.Count == 0)
                return;

            StopEnumerations();

            if (root == null) {
                list.root.MarkShared();
                root = list.root;
            }
            else {
                Node newRoot = root.AppendInPlace(list.root, false);
                if (newRoot != root) {
                    root = newRoot;
                    CheckBalance();
                }
            }
        }

        /// <summary>
        /// Adds a BigList of items to the front of BigList. The indices of all existing items
        /// are increased by the number of items in <paramref name="list"/>. The first item in <paramref name="list"/> 
        /// becomes the first item in this list. The added list <paramref name="list"/> is unchanged.
        /// </summary>
        /// <remarks>This method takes, on average, constant time, regardless of the size
        /// of either list. Although conceptually all of the items in <paramref name="list"/> are
        /// copied, storage is shared between the two lists until changes are made to the 
        /// shared sections.</remarks>
        /// <param name="list">The list of items to add.</param>
        /// <exception cref="ArgumentNullException"><paramref name="list"/> is null.</exception>
        public void AddRangeToFront(BigList<T> list)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if ((uint)Count + (uint)list.Count > MAXITEMS)
                throw new InvalidOperationException(Strings.CollectionTooLarge);

            if (list.Count == 0)
                return;

            StopEnumerations();

            if (root == null) {
                list.root.MarkShared();
                root = list.root;
            }
            else {
                Node newRoot = root.PrependInPlace(list.root, false);
                if (newRoot != root) {
                    root = newRoot;
                    CheckBalance();
                }
            }
        }

        /// <summary>
        /// Concatenates two lists together to create a new list. Both lists being concatenated
        /// are unchanged. The resulting list contains all the items in <paramref name="first"/>, followed
        /// by all the items in <paramref name="second"/>.
        /// </summary>
        /// <remarks>This method takes, on average, constant time, regardless of the size
        /// of either list. Although conceptually all of the items in both lists are
        /// copied, storage is shared until changes are made to the 
        /// shared sections.</remarks>
        /// <param name="first">The first list to concatenate.</param>
        /// <param name="second">The second list to concatenate.</param>
        /// <exception cref="ArgumentNullException"><paramref name="first"/> or <paramref name="second"/> is null.</exception>
        public static BigList<T> operator +(BigList<T> first, BigList<T> second)
        {
            if (first == null)
                throw new ArgumentNullException("first");
            if (second == null)
                throw new ArgumentNullException("second");
            if ((uint)first.Count + (uint)second.Count > MAXITEMS)
                throw new InvalidOperationException(Strings.CollectionTooLarge);

            if (first.Count == 0)
                return second.Clone();
            else if (second.Count == 0)
                return first.Clone();
            else {
                BigList<T> result = new BigList<T>(first.root.Append(second.root, false));
                result.CheckBalance();
                return result;
            }
        }

        /// <summary>
        /// Creates a new list that contains a subrange of elements from this list. The
        /// current list is unchanged.
        /// </summary>
        /// <remarks>This method takes take O(log N), where N is the size of the current list. Although
        /// the sub-range is conceptually copied, storage is shared between the two lists until a change
        /// is made to the shared items.</remarks>
        /// <remarks>If a view of a sub-range is desired, instead of a copy, use the
        /// more efficient <see cref="Range"/> method, which provides a view onto a sub-range of items.</remarks>
        /// <param name="index">The starting index of the sub-range.</param>
        /// <param name="count">The number of items in the sub-range. If this is zero,
        /// the returned list is empty.</param>
        /// <returns>A new list with the <paramref name="count"/> items that start at <paramref name="index"/>.</returns>
        public BigList<T> GetRange(int index, int count)
        {
            if (count == 0)
                return new BigList<T>();

            if (index < 0 || index >= Count)
                throw new ArgumentOutOfRangeException("index");
            if (count < 0 || count > Count - index)
                throw new ArgumentOutOfRangeException("count");

            return new BigList<T>(root.Subrange(index, index + count - 1));
        }

        /// <summary>
        /// Returns a view onto a sub-range of this list. Items are not copied; the
        /// returned IList&lt;T&gt; is simply a different view onto the same underlying items. Changes to this list
        /// are reflected in the view, and vice versa. Insertions and deletions in the view change the size of the 
        /// view, but insertions and deletions in the underlying list do not.
        /// </summary>
        /// <remarks>
        /// <para>If a copy of the sub-range is desired, use the <see cref="GetRange"/> method instead.</para>
        /// <para>This method can be used to apply an algorithm to a portion of a list. For example:</para>
        /// <code>Algorithms.ReverseInPlace(list.Range(3, 6))</code>
        /// will reverse the 6 items beginning at index 3.</remarks>
        /// <param name="index">The starting index of the view.</param>
        /// <param name="count">The number of items in the view.</param>
        /// <returns>A list that is a view onto the given sub-list. </returns>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> or <paramref name="count"/> is negative.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> + <paramref name="count"/> is greater than the
        /// size of this list.</exception>
        public sealed override IList<T> Range(int index, int count)
        {
            if (index < 0 || index > this.Count || (index == this.Count && count != 0))
                throw new ArgumentOutOfRangeException("index");
            if (count < 0 || count > this.Count || count + index > this.Count)
                throw new ArgumentOutOfRangeException("count");

            return new BigListRange(this, index, count);
        }

        /// <summary>
        /// Enumerates a range of the items in the list, in order. The item at <paramref name="start"/>
        /// is enumerated first, then the next item at index 1, and so on. At most <paramref name="maxItems"/>
        /// items are enumerated. 
        /// </summary>
        /// <remarks>Enumerating all of the items in the list take time O(N), where
        /// N is the number of items being enumerated. Using GetEnumerator() or foreach
        /// is much more efficient than accessing all items by index.</remarks>
        /// <param name="start">Index to start enumerating at.</param>
        /// <param name="maxItems">Max number of items to enumerate.</param>
        /// <returns>An IEnumerator&lt;T&gt; that enumerates all the
        /// items in the given range.</returns>
        private IEnumerator<T> GetEnumerator(int start, int maxItems)
        {
            // We could use a recursive enumerator here, but an explicit stack
            // is a lot more efficient, and efficiency matters here.

            int startStamp = changeStamp;       // to detect changes during enumeration.