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