set.cs

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

        /// <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 approximately constant time, regardless of 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 !hash.Insert(item, true, 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 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 approximately constant time, regardless of 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>
        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), where 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 approximately constant time, regardless of the size of 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 hash.Delete(item, out dummy);
        }

        /// <summary>
        /// Removes all the items in <paramref name="collection"/> from the set. 
        /// </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), where 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 set takes a constant amount of time, regardless of the number of items in it.</remarks>
        public sealed override void Clear()
        {
            hash.StopEnumerations();  // Invalidate any enumerations.

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

        #endregion Removing elements

        #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(Set<T> otherSet)
        {
            if (otherSet == null)
                throw new ArgumentNullException("otherSet");

            if (!object.Equals(equalityComparer, otherSet.equalityComparer))
                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), where M is the size of the 
        /// <paramref name="otherSet"/>.</remarks>
        /// </summary>
        /// <param name="otherSet">Set to compare to.</param>
        /// <returns>True if this is a superset of <paramref name="otherSet"/>.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsSupersetOf(Set<T> otherSet)
        {
            CheckConsistentComparison(otherSet);

            if (otherSet.Count > this.Count)
                return false;     // Can't be a superset of a bigger set

            // Check each item in the other set to make sure it is in this set.
            foreach (T item in otherSet) {
                if (!this.Contains(item))
                    return false;
            }

            return true; 
        }

        /// <summary>
        /// Determines if this set is a proper superset of another set. Neither set is modified.
        /// This set is a proper superset of <paramref name="otherSet"/> if every element in
        /// <paramref name="otherSet"/> is also in this set.
        /// Additionally, this set must have strictly more items than <paramref name="otherSet"/>.
        /// </summary>
        /// <remarks>IsProperSubsetOf is computed in time O(M), where M is the size of
        /// <paramref name="otherSet"/>.</remarks>
        /// <param name="otherSet">Set to compare to.</param>
        /// <returns>True if this is a proper superset of <paramref name="otherSet"/>.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsProperSupersetOf(Set<T> otherSet)
        {
            CheckConsistentComparison(otherSet);

            if (otherSet.Count >= this.Count)
                return false;     // Can't be a proper superset of a bigger or equal set

            return IsSupersetOf(otherSet);
        }

        /// <summary>
        /// Determines if this set is a subset of another set. Neither set is modified.
        /// This set is a subset of <paramref name="otherSet"/> if every element in this set
        /// is also in <paramref name="otherSet"/>.
        /// </summary>
        /// <remarks>IsSubsetOf is computed in time O(N), where N is the size of the this set.</remarks>
        /// <param name="otherSet">Set to compare to.</param>
        /// <returns>True if this is a subset of <paramref name="otherSet"/>.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsSubsetOf(Set<T> otherSet)
        {
            return otherSet.IsSupersetOf(this);
        }

        /// <summary>
        /// Determines if this set is a proper subset of another set. Neither set is modified.
        /// This set is a subset of <paramref name="otherSet"/> if every element in this set
        /// is also in <paramref name="otherSet"/>. Additionally, this set must have strictly 
        /// fewer items than <paramref name="otherSet"/>.
        /// </summary>
        /// <remarks>IsProperSubsetOf is computed in time O(N), where N is the size of the this set.</remarks>
        /// <param name="otherSet">Set to compare to.</param>
        /// <returns>True if this is a proper subset of <paramref name="otherSet"/>.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsProperSubsetOf(Set<T> otherSet)
        {
            return otherSet.IsProperSupersetOf(this);
        }

        /// <summary>
        /// Determines if this set is equal to another set. This set is equal to
        /// <paramref name="otherSet"/> if they contain the same items.
        /// </summary>
        /// <remarks>IsEqualTo is computed in time O(N), where N is the number of items in 
        /// this set.</remarks>
        /// <param name="otherSet">Set to compare to</param>
        /// <returns>True if this set is equal to <paramref name="otherSet"/>, false otherwise.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsEqualTo(Set<T> otherSet)
        {
            CheckConsistentComparison(otherSet);

            // Must be the same size.
            if (otherSet.Count != this.Count)
                return false;

            // Check each item in the other set to make sure it is in this set.
            foreach (T item in otherSet) {
                if (!this.Contains(item))
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Determines if this set is disjoint from another set. Two sets are disjoint
        /// if no item from one set is equal to any item in the other set.
        /// </summary>
        /// <remarks>
        /// <para>The answer is computed in time O(N), where N is the size of the smaller set.</para>
        /// </remarks>
        /// <param name="otherSet">Set to check disjointness with.</param>
        /// <returns>True if the two sets are disjoint, false otherwise.</returns>
        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
        public bool IsDisjointFrom(Set<T> otherSet)
        {
            CheckConsistentComparison(otherSet);
            Set<T> smaller, larger;
            if (otherSet.Count > this.Count) {
                smaller = this; larger = otherSet;
            }
            else {
                smaller = otherSet; larger = this;