bag.cs

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

        public sealed override void Clear()
        {
            hash.StopEnumerations();  // Invalidate any enumerations.

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

        #endregion Removing elements

        #region Set operations

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

            if (!object.Equals(equalityComparer, otherBag.equalityComparer))
                throw new InvalidOperationException(Strings.InconsistentComparisons);
        }

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

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

            // Check each item to make sure it is in this set the same number of times.
            foreach (T item in otherBag.DistinctItems()) {
                if (this.NumberOfCopies(item) != otherBag.NumberOfCopies(item))
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Determines if this bag is a superset of another bag. Neither bag is modified.
        /// This bag is a superset of <paramref name="otherBag"/> if every element in
        /// <paramref name="otherBag"/> is also in this bag, at least the same number of
        /// times.
        /// </summary>
        /// <remarks>IsSupersetOf is computed in time O(M), where M is the number of unique items in 
        /// <paramref name="otherBag"/>.</remarks>
        /// <param name="otherBag">Bag to compare to.</param>
        /// <returns>True if this is a superset of <paramref name="otherBag"/>.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        public bool IsSupersetOf(Bag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            if (otherBag.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 otherBag.DistinctItems()) {
                if (this.NumberOfCopies(item) < otherBag.NumberOfCopies(item))
                    return false;
            }

            return true;
        }

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

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

            return IsSupersetOf(otherBag);
        }

        /// <summary>
        /// Determines if this bag is a subset of another ba11 items in this bag.
        /// </summary>
        /// <param name="otherBag">Bag to compare to.</param>
        /// <returns>True if this is a subset of <paramref name="otherBag"/>.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        public bool IsSubsetOf(Bag<T> otherBag)
        {
            return otherBag.IsSupersetOf(this);
        }

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

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

            foreach (T item in smaller.DistinctItems()) {
                if (larger.Contains(item))
                    return false;
            }

            return true;
        }

        /// <summary>
        /// Computes the union of this bag with another bag. The union of two bags
        /// is all items from both of the bags. If an item appears X times in one bag,
        /// and Y times in the other bag, the union contains the item Maximum(X,Y) times. This bag receives
        /// the union of the two bags, the other bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The union of two bags is computed in time O(M+N), where M and N are the size of the 
        /// two bags.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to union with.</param>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        public void UnionWith(Bag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            if (otherBag == this)
                return;             // Nothing to do

            int copiesInThis, copiesInOther;

            // Enumerate each of the items in the other bag. Add items that need to be
            // added to this bag.
            foreach (T item in otherBag.DistinctItems()) {
                copiesInThis = this.NumberOfCopies(item);
                copiesInOther = otherBag.NumberOfCopies(item);

                if (copiesInOther > copiesInThis)
                    ChangeNumberOfCopies(item, copiesInOther);
            } 
        }

        /// <summary>
        /// Computes the union of this bag with another bag. The union of two bags
        /// is all items from both of the bags.  If an item appears X times in one bag,
        /// and Y times in the other bag, the union contains the item Maximum(X,Y) times. A new bag is 
        /// created with the union of the bags and is returned. This bag and the other bag 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The union of two bags is computed in time O(M+N), where M and N are the size of the two bags.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to union with.</param>
        /// <returns>The union of the two bags.</returns>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        public Bag<T> Union(Bag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            Bag<T> smaller, larger, result;
            if (otherBag.Count > this.Count) {
                smaller = this; larger = otherBag;
            }
            else {
                smaller = otherBag; larger = this;
            }

            result = larger.Clone();
            result.UnionWith(smaller);
            return result; 
        }

        /// <summary>
        /// Computes the sum of this bag with another bag. The sum of two bags
        /// is all items from both of the bags. If an item appears X times in one bag,
        /// and Y times in the other bag, the sum contains the item (X+Y) times. This bag receives
        /// the sum of the two bags, the other bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The sum of two bags is computed in time O(M), where M is the size of the 
        /// other bag..</para>
        /// </remarks>
        /// <param name="otherBag">Bag to sum with.</param>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        public void SumWith(Bag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            if (this == otherBag) {
                // Not very efficient, but an uncommon case.
                AddMany(otherBag);
                return;
            }

            int copiesInThis, copiesInOther;

            // Enumerate each of the items in the other bag. Add items that need to be
            // added to this bag.
            foreach (T item in otherBag.DistinctItems()) {
                copiesInThis = this.NumberOfCopies(item);
                copiesInOther = otherBag.NumberOfCopies(item);

                ChangeNumberOfCopies(item, copiesInThis + copiesInOther);
            }
        }

        /// <summary>