//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement 
// contained in the file "License.txt" accompanying this file.
//******************************

using System;
using System.Collections.Generic; 
using System.Collections;


namespace Wintellect.PowerCollections
{
    /// <summary>
    /// Bag&lt;T&gt; is a collection that contains items of type T. 
    /// Unlike a Set, duplicate items (items that compare equal to each other) are allowed in an Bag. 
    /// </summary>
    /// <remarks>
    /// <p>The items are compared in one of two ways. If T implements IComparable&lt;T&gt; 
    /// then the Equals method of that interface will be used to compare items, otherwise the Equals
    /// method from Object will be used. Alternatively, an instance of IComparer&lt;T&gt; can be passed
    /// to the constructor to use to compare items.</p>
    /// <p>Bag is implemented as a hash table. Inserting, deleting, and looking up an
    /// an element all are done in approximately constant time, regardless of the number of items in the bag.</p>
    /// <p>When multiple equal items are stored in the bag, they are stored as a representative item and a count. 
    /// If equal items can be distinguished, this may be noticable. For example, if a case-insensitive
    /// comparer is used with a Bag&lt;string&gt;, and both "hello", and "HELLO" are added to the bag, then the
    /// bag will appear to contain two copies of "hello" (the representative item).</p>
    /// <p><see cref="OrderedBag&lt;T&gt;"/> is similar, but uses comparison instead of hashing, maintain
    /// the items in sorted order, and stores distinct copies of items that compare equal.</p>
    ///</remarks>
    ///<seealso cref="OrderedBag&lt;T&gt;"/>
    [Serializable]
    public class Bag<T> : CollectionBase<T>, ICloneable
    {
        // The comparer used to compare KeyValuePairs. Equals and GetHashCode are used.
        private IEqualityComparer<KeyValuePair<T,int>> equalityComparer;

        // The comparer used to compare items. Kept just for the Comparer property. 
        private IEqualityComparer<T> keyEqualityComparer;

        // The hash that actually does the work of storing the items. Each item is
        // stored as a representative item, and a count.
        private Hash<KeyValuePair<T, int>> hash;   

        // The total number of items stored in the bag.
        private int count;

        /// <summary>
        /// Helper function to create a new KeyValuePair struct with an item and a count.
        /// </summary>
        /// <param name="item">The item.</param>
        /// <param name="count">The number of appearances.</param>
        /// <returns>A new KeyValuePair.</returns>
        private static KeyValuePair<T, int> NewPair(T item, int count)
        {
            KeyValuePair<T, int> pair = new KeyValuePair<T,int>(item, count);
            return pair;
        }

        /// <summary>
        /// Helper function to create a new KeyValuePair struct with a count of zero.
        /// </summary>
        /// <param name="item">The item.</param>
        /// <returns>A new KeyValuePair.</returns>
        private static KeyValuePair<T, int> NewPair(T item)
        {
            KeyValuePair<T, int> pair = new KeyValuePair<T, int>(item, 0);
            return pair;
        }

        #region Constructors

        /// <summary>
        /// Creates a new Bag. 
        /// </summary>
        ///<remarks>
        /// Items that are null are permitted.
        ///</remarks>
        public Bag(): 
            this(EqualityComparer<T>.Default)
        {
        }

        /// <summary>
        /// Creates a new Bag. The Equals and GetHashCode methods of the passed comparison object
        /// will be used to compare items in this bag for equality.
        /// </summary>
        /// <param name="equalityComparer">An instance of IEqualityComparer&lt;T&gt; that will be used to compare items.</param>
        public Bag(IEqualityComparer<T> equalityComparer)
        {
            if (equalityComparer == null)
                throw new ArgumentNullException("equalityComparer");

            this.keyEqualityComparer = equalityComparer;
            this.equalityComparer = Comparers.EqualityComparerKeyValueFromComparerKey<T, int>(equalityComparer);
            this.hash = new Hash<KeyValuePair<T, int>>(this.equalityComparer);
        }

        /// <summary>
        /// Creates a new Bag. The bag is
        /// initialized with all the items in the given collection.
        /// </summary>
        ///<remarks>
        /// Items that are null are permitted.
        ///</remarks>
        /// <param name="collection">A collection with items to be placed into the Bag.</param>
        public Bag(IEnumerable<T> collection): 
            this(collection, EqualityComparer<T>.Default)
        {
        }

        /// <summary>
        /// Creates a new Bag. The Equals and GetHashCode methods of the passed comparison object
        /// will be used to compare items in this bag. The bag is
        /// initialized with all the items in the given collection.
        /// </summary>
        /// <param name="collection">A collection with items to be placed into the Bag.</param>
        /// <param name="equalityComparer">An instance of IEqualityComparer&lt;T&gt; that will be used to compare items.</param>
        public Bag(IEnumerable<T> collection, IEqualityComparer<T> equalityComparer)
            : this(equalityComparer)
        {
            AddMany(collection);
        }

        /// <summary>
        /// Creates a new Bag given a comparer and a hash that contains the data. Used
        /// internally for Clone.
        /// </summary>
        /// <param name="equalityComparer">IEqualityComparer for the bag.</param>
        /// <param name="keyEqualityComparer">IEqualityComparer for the key.</param>
        /// <param name="hash">Data for the bag.</param>
        /// <param name="count">Size of the bag.</param>
        private Bag(IEqualityComparer<KeyValuePair<T, int>> equalityComparer, IEqualityComparer<T> keyEqualityComparer, Hash<KeyValuePair<T,int>> hash, int count)
        {
            this.equalityComparer = equalityComparer;
            this.keyEqualityComparer = keyEqualityComparer;
            this.hash = hash;
            this.count = count;
        }

        #endregion Constructors

        #region Cloning

        /// <summary>
        /// Makes a shallow clone of this bag; i.e., if items of the
        /// bag are reference types, then they are not cloned. If T is a value type,
        /// then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks>Cloning the bag takes time O(N), where N is the number of items in the bag.</remarks>
        /// <returns>The cloned bag.</returns>
        object ICloneable.Clone()
        {
            return this.Clone();
        }

        /// <summary>
        /// Makes a shallow clone of this bag; i.e., if items of the
        /// bag are reference types, then they are not cloned. If T is a value type,
        /// then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks>Cloning the bag takes time O(N), where N is the number of unquie items in the bag.</remarks>
        /// <returns>The cloned bag.</returns>
        public Bag<T> Clone()
        {
            Bag<T> newBag = new Bag<T>(equalityComparer, keyEqualityComparer, hash.Clone(null), count);
            return newBag;
        }

        /// <summary>
        /// Makes a deep clone of this bag. A new bag is created with a clone of
        /// each element of this bag, by calling ICloneable.Clone on each element. If T is
        /// a value type, then each element is copied as if by simple assignment.
        /// </summary>
        /// <remarks><para>If T is a reference type, it must implement
        /// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
        /// <para>Cloning the bag takes time O(N log N), where N is the number of items in the bag.</para></remarks>
        /// <returns>The cloned bag.</returns>
        /// <exception cref="InvalidOperationException">T is a reference type that does not implement ICloneable.</exception>
        public Bag<T> CloneContents()
        {
            bool itemIsValueType;
            if (!Util.IsCloneableType(typeof(T), out itemIsValueType))
                throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, typeof(T).FullName));

            Hash<KeyValuePair<T,int>> newHash = new Hash<KeyValuePair<T,int>>(equalityComparer);

            // Clone each item, and add it to the new ordered bag.
            foreach (KeyValuePair<T, int> pair in hash) {
                KeyValuePair<T, int> newPair, dummy;
                T newKey;

                if (!itemIsValueType && pair.Key != null)
                    newKey = (T)(((ICloneable)pair.Key).Clone());
                else
                    newKey = pair.Key;

                newPair = NewPair(newKey, pair.Value);

                newHash.Insert(newPair, true, out dummy);
            }

            return new Bag<T>(equalityComparer, keyEqualityComparer, newHash, count); 
        }

        #endregion Cloning

        #region Basic collection containment

        /// <summary>
        /// Returns the IEqualityComparer&lt;T&gt; used to compare items in this bag. 
        /// </summary>
        /// <value>If the bag was created using a comparer, that comparer is returned. Otherwise
        /// the default comparer for T (EqualityComparer&lt;T&gt;.Default) is returned.</value>
        public IEqualityComparer<T> Comparer
        {
            get
            {
                return keyEqualityComparer;
            }
        }

        /// <summary>
        /// Returns the number of items in the bag.
        /// </summary>
        /// <remarks>The size of the bag is returned in constant time.</remarks>
        /// <value>The number of items in the bag.</value>
        public sealed override int Count
        {
            get
            {
                return count;
            }
        }

        /// <summary>
        /// Returns the number of copies of <paramref name="item"/> in the bag. 
        /// </summary>
        /// <remarks>NumberOfCopies() takes approximately constant time, no matter how many items
        /// are stored in the bag.</remarks>
        /// <param name="item">The item to search for in the bag.</param>
        /// <returns>The number of items in the bag that compare equal to <paramref name="item"/>.</returns>
        public int NumberOfCopies(T item)
        {
            KeyValuePair<T, int> foundPair;
            if (hash.Find(NewPair(item), false, out foundPair)) 
                return foundPair.Value;
            else
                return 0;
        }

        /// <summary>
        /// Returns the representative item stored in the bag that is equal to
        /// the provided item. Also returns the number of copies of the item in the bag.
        /// </summary>
        /// <param name="item">Item to find in the bag.</param>
        /// <param name="representative">If one or more items equal to <paramref name="item"/> are present in the
        /// bag, returns the representative item. If no items equal to <paramref name="item"/> are stored in the bag, 
        /// returns <paramref name="item"/>.</param>
        /// <returns>The number of items equal to <paramref name="item"/> stored in the bag.</returns>
        public int GetRepresentativeItem(T item, out T representative)
        {
            KeyValuePair<T, int> foundPair;
            if (hash.Find(NewPair(item), false, out foundPair)) {
                representative = foundPair.Key;
                return foundPair.Value;
            }
            else {
                representative = item;
                return 0;
            }
        }

        /// <summary>
        /// Returns an enumerator that enumerates all the items in the bag. 
        /// If an item is present multiple times in the bag, the representative item is yielded by the
        /// enumerator multiple times. The order of enumeration is haphazard and may change.
        /// </summary>
        /// <remarks>
        /// <p>Typically, this method is not called directly. Instead the "foreach" statement is used
        /// to enumerate the items, which uses this method implicitly.</p>
        /// <p>If an item is added to or deleted from the bag while it is being enumerated, then 
        /// the enumeration will end with an InvalidOperationException.</p>
        /// <p>Enumeration all the items in the bag takes time O(N), where N is the number
        /// of items in the bag.</p>
        /// </remarks>
        /// <returns>An enumerator for enumerating all the items in the Bag.</returns>		
        public sealed override IEnumerator<T> GetEnumerator()
        {
            foreach (KeyValuePair<T, int> pair in hash) {
                for (int i = 0; i < pair.Value; ++i)
                    yield return pair.Key;
            }
        }

        /// <summary>
        /// Determines if this bag contains an item equal to <paramref name="item"/>. The bag
        /// is not changed.
        /// </summary>
        /// <remarks>Searching the bag for an item takes time O(log N), where N is the number of items in the bag.</remarks>
        /// <param name="item">The item to search for.</param>
        /// <returns>True if the bag contains <paramref name="item"/>. False if the bag does not contain <paramref name="item"/>.</returns>
        public sealed override bool Contains(T item)
        {
            KeyValuePair<T, int> dummy;
            return hash.Find(NewPair(item), false, out dummy);
        }

        /// <summary>
        /// Enumerates all the items in the bag, but enumerates equal items
        /// just once, even if they occur multiple times in the bag.
        /// </summary>
        /// <remarks>If the bag is changed while items are being enumerated, the
        /// enumeration will terminate with an InvalidOperationException.</remarks>
        /// <returns>An IEnumerable&lt;T&gt; that enumerates the unique items.</returns>
        public IEnumerable<T> DistinctItems()
        {
            foreach (KeyValuePair<T, int> pair in hash) {
                yield return pair.Key;
            }
        }

        #endregion


        #region Adding elements

        /// <summary>
        /// Adds a new item to the bag. Since bags can contain duplicate items, the item 
        /// is added even if the bag already contains an item equal to <paramref name="item"/>. In
        /// this case, the count of items for the representative item is increased by one, but the existing
        /// represetative item is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>Adding an item takes approximately constant time, regardless of the number of items in the bag.</para></remarks>
        /// <param name="item">The item to add to the bag.</param>
        public sealed override void Add(T item)
        {
            KeyValuePair<T, int> pair = NewPair(item, 1);
            KeyValuePair<T, int> existing, newPair;
            if (! hash.Insert(pair, false, out existing)) {
                // The item already existed, so update the count instead.
                newPair = NewPair(existing.Key, existing.Value + 1);
                hash.Insert(newPair, true, out pair);
            }
            ++count;
        }

        // CONSIDER: add an example to the documentation below.
        /// <summary>
        /// Adds a new item to the bag. Since bags can contain duplicate items, the item 
        /// is added even if the bag already contains an item equal to <paramref name="item"/>. In
        /// this case (unlike Add), the new item becomes the representative item.
        /// </summary>
        /// <remarks>
        /// <para>Adding an item takes approximately constant time, regardless of the number of items in the bag.</para></remarks>
        /// <param name="item">The item to add to the bag.</param>
        public void AddRepresentative(T item)
        {
            KeyValuePair<T, int> pair = NewPair(item, 1);
            KeyValuePair<T, int> existing, newPair;
            if (!hash.Insert(pair, false, out existing)) {
                // The item already existed, so update the count instead.
                newPair = NewPair(pair.Key, existing.Value + 1);
                hash.Insert(newPair, true, out pair);
            }
            ++count;
        }

        /// <summary>
        /// Changes the number of copies of an existing item in the bag, or adds the indicated number
        /// of copies of the item to the bag. 
        /// </summary>
        /// <remarks>
        /// <para>Changing the number of copies takes approximately constant time, regardless of the number of items in the bag.</para></remarks>
        /// <param name="item">The item to change the number of copies of. This may or may not already be present in the bag.</param>
        /// <param name="numCopies">The new number of copies of the item.</param>
        public void ChangeNumberOfCopies(T item, int numCopies)
        {
            if (numCopies == 0)
                RemoveAllCopies(item);
            else {
                KeyValuePair<T, int> dummy, existing, newPair;
                if (hash.Find(NewPair(item), false, out existing)) {
                    count += numCopies - existing.Value;
                    newPair = NewPair(existing.Key, numCopies);
                }
                else {
                    count += numCopies;
                    newPair = NewPair(item, numCopies);
                }
                hash.Insert(newPair, true, out dummy);
            }
        }

        /// <summary>
        /// Adds all the items in <paramref name="collection"/> to the bag. 
        /// </summary>
        /// <remarks>
        /// <para>Adding the collection takes time O(M log N), where N is the number of items in the bag, and M is the 
        /// number of items in <paramref name="collection"/>.</para></remarks>
        /// <param name="collection">A collection of items to add to the bag.</param>
        public void AddMany(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");

            // If we're adding ourselves, we need to copy to a separate array to avoid modification
            // during enumeration.
            if (this == collection)
                collection = this.ToArray();

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

        #endregion Adding elements

        #region Removing elements

        /// <summary>
        /// Searches the bag for one item equal to <paramref name="item"/>, and if found,
        /// removes it from the bag. If not found, the bag is unchanged. 
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparison instance or delegate used
        /// to create the bag.</para>
        /// <para>Removing an item from the bag takes approximated constant time,
        /// regardless of the number of items in the bag.</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 bag.</returns>
        public sealed override bool Remove(T item)
        {
            KeyValuePair<T, int> removed, newPair;
            if (hash.Delete(NewPair(item), out removed)) {
                if (removed.Value > 1) {
                    // Only want to remove one copied, so add back in with a reduced count.
                    KeyValuePair<T, int> dummy;
                    newPair = NewPair(removed.Key, removed.Value - 1);
                    hash.Insert(newPair, true, out dummy);
                }
                --count;
                return true;
            }
            else
                return false;
        }

        /// <summary>
        /// Searches the bag for all items equal to <paramref name="item"/>, and 
        /// removes all of them from the bag. If not found, the bag is unchanged.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparer instance used
        /// to create the bag.</para>
        /// <para>RemoveAllCopies() takes time O(M log N), where N is the total number of items in the bag, and M is
        /// the number of items equal to <paramref name="item"/>.</para></remarks>
        /// <param name="item">The item to remove.</param>
        /// <returns>The number of copies of <paramref name="item"/> that were found and removed. </returns>
        public int RemoveAllCopies(T item)
        {
            KeyValuePair<T, int> removed;
            if (hash.Delete(NewPair(item), out removed)) {
                count -= removed.Value;
                return removed.Value;
            }
            else
                return 0;
        }

        /// <summary>
        /// Removes all the items in <paramref name="collection"/> from the bag. Items that
        /// are not present in the bag are ignored.
        /// </summary>
        /// <remarks>
        /// <para>Equality between items is determined by the comparer instance used
        /// to create the bag.</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 bag.</param>
        /// <returns>The number of items removed from the bag.</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 bag.
        /// </summary>
        /// <remarks>Clearing the bag 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 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>
        /// 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
    }
}