bag.cs

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

        /// Computes the sum of this bag with another bag. he 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. A new bag is 
        /// created with the sum of the bags and is returned. This bag and the other bag 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The sum of two bags is computed in time O(M + N log M), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to sum with.</param>
        /// <returns>The sum 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> Sum(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.SumWith(smaller);
            return result;
        }

        /// <summary>
        /// Computes the intersection of this bag with another bag. The intersection of two bags
        /// is all items that appear in 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 Minimum(X,Y) times. This bag receives
        /// the intersection of the two bags, the other bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both bags, the intersection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>The intersection of two bags is computed in time O(N), where N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to intersection with.</param>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        public void IntersectionWith(Bag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            hash.StopEnumerations();

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

            KeyValuePair<T,int> dummy;
            Hash<KeyValuePair<T, int>> newHash = new Hash<KeyValuePair<T, int>>(equalityComparer);
            int newCount = 0;
            int copiesInSmaller, copiesInLarger, copies;

            // Enumerate each of the items in the smaller bag. Add items that need to be
            // added to the intersection.
            foreach (T item in smaller.DistinctItems()) {
                copiesInLarger = larger.NumberOfCopies(item);
                copiesInSmaller = smaller.NumberOfCopies(item);
                copies = Math.Min(copiesInLarger, copiesInSmaller);
                if (copies > 0) {
                    newHash.Insert(NewPair(item, copies), true, out dummy);
                    newCount += copies;
                }
            }

            hash = newHash;
            count = newCount;
        }

        /// <summary>
        /// Computes the intersection of this bag with another bag. The intersection of two bags
        /// is all items that appear in both of the bags. If an item appears X times in one bag,
        /// and Y times in the other bag, the intersection contains the item Minimum(X,Y) times. A new bag is 
        /// created with the intersection of the bags and is returned. This bag and the other bag 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>When equal items appear in both bags, the intersection will include an arbitrary choice of one of the
        /// two equal items.</para>
        /// <para>The intersection of two bags is computed in time O(N), where N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to intersection with.</param>
        /// <returns>The intersection 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> Intersection(Bag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

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

            int copiesInSmaller, copiesInLarger, copies;

            // Enumerate each of the items in the smaller bag. Add items that need to be
            // added to the intersection.
            result = new Bag<T>(keyEqualityComparer);
            foreach (T item in smaller.DistinctItems()) {
                copiesInLarger = larger.NumberOfCopies(item);
                copiesInSmaller = smaller.NumberOfCopies(item);
                copies = Math.Min(copiesInLarger, copiesInSmaller);
                if (copies > 0) 
                    result.ChangeNumberOfCopies(item, copies);
            }

            return result; 
        }

        /// <summary>
        /// Computes the difference of this bag with another bag. The difference of these two bags
        /// is all items that appear in this bag, but not in <paramref name="otherBag"/>. If an item appears X times in this bag,
        /// and Y times in the other bag, the difference contains the item X - Y times (zero times if Y >= X). This bag receives
        /// the difference of the two bags; the other bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The difference 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 difference with.</param>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        public void DifferenceWith(Bag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            if (this == otherBag) {
                Clear();
                return;
            }

            int copiesInThis, copiesInOther, copies;

            // Enumerate each of the items in the other bag. Remove items that need to be
            // removed from this bag.
            foreach (T item in otherBag.DistinctItems()) {
                copiesInThis = this.NumberOfCopies(item);
                copiesInOther = otherBag.NumberOfCopies(item);
                copies = copiesInThis - copiesInOther;
                if (copies < 0)
                    copies = 0;

                ChangeNumberOfCopies(item, copies);
            }
        }

        /// <summary>
        /// Computes the difference of this bag with another bag. The difference of these two bags
        /// is all items that appear in this bag, but not in <paramref name="otherBag"/>. If an item appears X times in this bag,
        /// and Y times in the other bag, the difference contains the item X - Y times (zero times if Y >= X).  A new bag is 
        /// created with the difference of the bags and is returned. This bag and the other bag 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The difference 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 difference with.</param>
        /// <returns>The difference 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> Difference(Bag<T> otherBag)
        {
            Bag<T> result;

            CheckConsistentComparison(otherBag);

            result = this.Clone();
            result.DifferenceWith(otherBag);
            return result; 
        }

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

            if (this == otherBag) {
                Clear();
                return;
            }

            int copiesInThis, copiesInOther, copies;

            // 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);
                copies = Math.Abs(copiesInThis - copiesInOther);

                if (copies != copiesInThis)
                    ChangeNumberOfCopies(item, copies);
            }
        }

        /// <summary>
        /// Computes the symmetric difference of this bag with another bag. The symmetric difference of two bags
        /// is all items that appear in either of the bags, but not both. If an item appears X times in one bag,
        /// and Y times in the other bag, the symmetric difference contains the item AbsoluteValue(X - Y) times. A new bag is 
        /// created with the symmetric difference of the bags and is returned. This bag and the other bag 
        /// are unchanged.
        /// </summary>
        /// <remarks>
        /// <para>The symmetric difference of two bags is computed in time O(M + N), where M is the size of the 
        /// larger bag, and N is the size of the smaller bag.</para>
        /// </remarks>
        /// <param name="otherBag">Bag to symmetric difference with.</param>
        /// <returns>The symmetric difference 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> SymmetricDifference(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.SymmetricDifferenceWith(smaller);
            return result;
        }

        #endregion Set operations
    }
}