orderedset.cs

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

        /// <code>
        /// OrderedSet&lt;string&gt; set = new OrderedSet&lt;string&gt;(StringComparer.CurrentCultureIgnoreCase);
        /// set.Add("HELLO");
        /// string s;
        /// bool b = set.TryGetItem("Hello", out s);   // b receives true, s receives "HELLO".
        /// </code>
        /// </example>
        /// <param name="item">The item to search for.</param>
        /// <param name="foundItem">Returns the item from the set that was equal to <paramref name="item"/>.</param>
        /// <returns>True if the set contains <paramref name="item"/>. False if the set does not contain <paramref name="item"/>.</returns>
        public bool TryGetItem(T item, out T foundItem)
        {
            return tree.Find(item, true, false, out foundItem);
        }

        #endregion

        #region Index by sorted order

        /// <summary>
        /// Get the item by its index in the sorted order. The smallest item has index 0,
        /// the next smallest item has index 1, and the largest item has index Count-1. 
        /// </summary>
        /// <remarks>The indexer takes time O(log N), which N is the number of items in 
        /// the set.</remarks>
        /// <param name="index">The index to get the item by.</param>
        /// <returns>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 T this[int index]
        {
            get {
                if (index < 0 || index >= Count)
                    throw new ArgumentOutOfRangeException("index");

                return tree.GetItemByIndex(index);
            }
        }

        /// <summary>
        /// Get the index of the given item in the sorted order. The smallest item has index 0,
        /// the next smallest item has index 1, and the largest item has index Count-1. 
        /// </summary>
        /// <remarks>Finding the index takes time O(log N), which N is the number of items in 
        /// the set.</remarks>
        /// <param name="item">The item to get the index of.</param>
        /// <returns>The index of the item in the sorted set, or -1 if the item is not present
        /// in the set.</returns>
        public int IndexOf(T item)
        {
            return tree.FindIndex(item, true);
        }

        #endregion

        #region Adding elements

        /// <summary>
        /// Adds a new item to the set. If the set already contains an item equal to
        /// <paramref name="item"/>, that item is replaced with <paramref name="item"/>.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparison instance or delegate used
        /// to create the set.</para>
        /// <para>Adding an item takes time O(log N), where N is the number of items in the set.</para></remarks>
        /// <param name="item">The item to add to the set.</param>
        /// <returns>True if the set already contained an item equal to <paramref name="item"/> (which was replaced), false 
        /// otherwise.</returns>
        public new bool Add(T item)
        {
            T dummy;
            return ! tree.Insert(item, DuplicatePolicy.ReplaceFirst, out dummy);
        }

        /// <summary>
        /// Adds a new item to the set. If the set already contains an item equal to
        /// <paramref name="item"/>, that item is replaces with <paramref name="item"/>.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparison instance or delegate used
        /// to create the set.</para>
        /// <para>Adding an item takes time O(log N), where N is the number of items in the set.</para></remarks>
        /// <param name="item">The item to add to the set.</param>
        void ICollection<T>.Add(T item)
        {
            Add(item);
        }

        /// <summary>
        /// Adds all the items in <paramref name="collection"/> to the set. If the set already contains an item equal to
        /// one of the items in <paramref name="collection"/>, that item will be replaced.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparison instance or delegate used
        /// to create the set.</para>
        /// <para>Adding the collection takes time O(M log N), where N is the number of items in the set, and M is the 
        /// number of items in <paramref name="collection"/>.</para></remarks>
        /// <param name="collection">A collection of items to add to the set.</param>
        public void AddMany(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            // If we're adding ourselves, then there is nothing to do.
            if (object.ReferenceEquals(collection, this))
                return;

            foreach (T item in collection)
                Add(item);
        }

        #endregion Adding elements

        #region Removing elements

        /// <summary>
        /// Searches the set for an item equal to <paramref name="item"/>, and if found,
        /// removes it from the set. If not found, the set is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparison instance or delegate used
        /// to create the set.</para>
        /// <para>Removing an item from the set takes time O(log N), where N is the number of items in the set.</para></remarks>
        /// <param name="item">The item to remove.</param>
        /// <returns>True if <paramref name="item"/> was found and removed. False if <paramref name="item"/> was not in the set.</returns>
        public sealed override bool Remove(T item)
        {
            T dummy;
            return tree.Delete(item, true, out dummy);
        }

        /// <summary>
        /// Removes all the items in <paramref name="collection"/> from the set. Items
        /// not present in the set are ignored.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparison instance or delegate used
        /// to create the set.</para>
        /// <para>Removing the collection takes time O(M log N), where N is the number of items in the set, and M is the 
        /// number of items in <paramref name="collection"/>.</para></remarks>
        /// <param name="collection">A collection of items to remove from the set.</param>
        /// <returns>The number of items removed from the set.</returns>
        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
        public int RemoveMany(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            int count = 0;

            if (collection == this) {
                count = Count;
                Clear();            // special case, otherwise we will throw.
            }
            else {
                foreach (T item in collection) {
                    if (Remove(item))
                        ++count;
                }
            }

            return count;
        }

        /// <summary>
        /// Removes all items from the set.
        /// </summary>
        /// <remarks>Clearing the sets takes a constant amount of time, regardless of the number of items in it.</remarks>
        public sealed override void Clear()
        {
            tree.StopEnumerations();  // Invalidate any enumerations.

            // The simplest and fastest way is simply to throw away the old tree and create a new one.
            tree = new RedBlackTree<T>(comparer);
        }

        #endregion Removing elements

        #region First/last items

        /// <summary>
        /// If the collection is empty, throw an invalid operation exception.
        /// </summary>
        /// <exception cref="InvalidOperationException">The set is empty.</exception>
        private void CheckEmpty()
        {
            if (Count == 0)
                throw new InvalidOperationException(Strings.CollectionIsEmpty);
        }

        /// <summary>
        /// Returns the first item in the set: the item
        /// that would appear first if the set was enumerated. This is also
        /// the smallest item in the set.
        /// </summary>
        /// <remarks>GetFirst() takes time O(log N), where N is the number of items in the set.</remarks>
        /// <returns>The first item in the set. </returns>
        /// <exception cref="InvalidOperationException">The set is empty.</exception>
        public T GetFirst()
        {
            T item;
            CheckEmpty();
            tree.FirstItemInRange(tree.EntireRangeTester, out item);
            return item;
        }

        /// <summary>
        /// Returns the lastl item in the set: the item
        /// that would appear last if the set was enumerated. This is also the
        /// largest item in the set.
        /// </summary>
        /// <remarks>GetLast() takes time O(log N), where N is the number of items in the set.</remarks>
        /// <returns>The lastl item in the set. </returns>
        /// <exception cref="InvalidOperationException">The set is empty.</exception>
        public T GetLast()
        {
            T item;
            CheckEmpty();
            tree.LastItemInRange(tree.EntireRangeTester, out item);
            return item;
        }

        /// <summary>
        /// Removes the first item in the set. This is also the smallest item in the set.
        /// </summary>
        /// <remarks>RemoveFirst() takes time O(log N), where N is the number of items in the set.</remarks>
        /// <returns>The item that was removed, which was the smallest item in the set. </returns>
        /// <exception cref="InvalidOperationException">The set is empty.</exception>
        public T RemoveFirst()
        {
            CheckEmpty();
            T item;
            tree.DeleteItemFromRange(tree.EntireRangeTester, true, out item);
            return item;
        }

        /// <summary>
        /// Removes the last item in the set. This is also the largest item in the set.
        /// </summary>
        /// <remarks>RemoveLast() takes time O(log N), where N is the number of items in the set.</remarks>
        /// <returns>The item that was removed, which was the largest item in the set. </returns>
        /// <exception cref="InvalidOperationException">The set is empty.</exception>
        public T RemoveLast()
        {
            CheckEmpty();
            T item;
            tree.DeleteItemFromRange(tree.EntireRangeTester, false, out item);
            return item;
        }

        #endregion

        #region Set operations

        /// <summary>
        /// Check that this set and another set were created with the same comparison
        /// mechanism. Throws exception if not compatible.
        /// </summary>
        /// <param name="otherSet">Other set to check comparision mechanism.</param>
        /// <exception cref="InvalidOperationException">If otherSet and this set don't use the same method for comparing items.</exception>
        private void CheckConsistentComparison(OrderedSet<T> otherSet) 
        {
            if (otherSet == null)
                throw new ArgumentNullException("otherSet");

            if (!object.Equals(comparer, otherSet.comparer))
                throw new InvalidOperationException(Strings.InconsistentComparisons);
        }

        /// <summary>
        /// Determines if this set is a superset of another set. Neither set is modified.
        /// This set is a superset of <paramref name="otherSet"/> if every element in
        /// <paramref name="otherSet"/> is also in this set.
        /// <remarks>IsSupersetOf is computed in time O(M log N), where M is the size of the 
        /// <paramref name="otherSet"/>, and N is the size of the this set.</remarks>