orderedbag.cs

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

            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 + 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>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public void SumWith(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);

            AddMany(otherBag);

            // CONSIDER: if otherBag is much larger, maybe better to clone it,
            // add all of the current into it, and replace.
        }

        /// <summary>
        /// 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>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public OrderedBag<T> Sum(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            OrderedBag<T> smaller, larger, result;
            if (otherBag.Count > this.Count) {
                smaller = this; larger = otherBag;
            }
            else {
                smaller = otherBag; larger = this;
            }

            result = larger.Clone();
            result.AddMany(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 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 intersection with.</param>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public void IntersectionWith(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            tree.StopEnumerations();

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

            T dummy;
            RedBlackTree<T> newTree = new RedBlackTree<T>(comparer);

            T previous = default(T);
            bool atBeginning = true;
            int copiesInSmaller = 0, copiesInLarger = 0;

            // Enumerate each of the items in the smaller bag. Add items that need to be
            // added to the intersection.
            foreach (T item in smaller) {
                if (atBeginning || comparer.Compare(item, previous) != 0) {
                    copiesInLarger = larger.NumberOfCopies(item);
                    copiesInSmaller = 1;
                }
                else {
                    ++copiesInSmaller;
                }

                if (copiesInSmaller <= copiesInLarger)
                    newTree.Insert(item, DuplicatePolicy.InsertLast, out dummy);

                previous = item;
                atBeginning = false;
            }

            tree = newTree;
        }

        /// <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. 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 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 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>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public OrderedBag<T> Intersection(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            OrderedBag<T> smaller, larger, result;
            if (otherBag.Count > this.Count) {
                smaller = this; larger = otherBag;
            }
            else {
                smaller = otherBag; larger = this;
            }

            T previous = default(T);
            bool atBeginning = true;
            int copiesInSmaller = 0, copiesInLarger = 0;

            // Enumerate each of the items in the smaller bag. Add items that need to be
            // added to the intersection.
            result = new OrderedBag<T>(comparer);
            foreach (T item in smaller) {
                if (atBeginning || comparer.Compare(item, previous) != 0) {
                    copiesInLarger = larger.NumberOfCopies(item);
                    copiesInSmaller = 1;
                }
                else {
                    ++copiesInSmaller;
                }

                if (copiesInSmaller <= copiesInLarger)
                    result.Add(item);

                previous = item;
                atBeginning = false;
            }

            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 + 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 difference with.</param>
        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public void DifferenceWith(OrderedBag<T> otherBag)
        {
            // Difference with myself is nothing. This check is needed because the
            // main algorithm doesn't work correctly otherwise.
            if (this == otherBag)
                Clear();

            CheckConsistentComparison(otherBag);

            T previous = default(T);
            bool atBeginning = true;
            int copiesInThis = 0, copiesInOther = 0;

            // Enumerate each of the items in the other bag. Remove items that need to be
            // removed from this bag.
            // CONSIDER: should be able to improve this algorithm if otherBag is larger than this bag.
            foreach (T item in otherBag) {
                if (atBeginning || comparer.Compare(item, previous) != 0) {
                    copiesInThis = this.NumberOfCopies(item);
                    copiesInOther = 1;
                }
                else {
                    ++copiesInOther;
                }

                if (copiesInOther <= copiesInThis)
                    this.Remove(item);

                previous = item;
                atBeginning = false;
            }

        }

        /// <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 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 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>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public OrderedBag<T> Difference(OrderedBag<T> otherBag)
        {
            CheckConsistentComparison(otherBag);
            OrderedBag<T> 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>
        /// <exception cref="ArgumentNullException"><paramref name="otherBag"/> is null.</exception>
        public void SymmetricDifferenceWith(OrderedBag<T> otherBag)
        {
            tree = SymmetricDifference(otherBag).tree;
        }

        /// <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>