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

// CONSIDER: RemoveIdentical to remove an identical item only. Can this be done with current RedBlack tree implementation? How
// CONSIDER: useful is it?

namespace Wintellect.PowerCollections
{
    /// <summary>
    /// OrderedBag&lt;T&gt; is a collection that contains items of type T. 
    /// The item are maintained in a sorted order. Unlike a OrderedSet, duplicate items (items that
    /// compare equal to each other) are allows in an OrderedBag.
    /// </summary>
    /// <remarks>
    /// <p>The items are compared in one of three ways. If T implements IComparable&lt;TKey&gt; or IComparable,
    /// then the CompareTo method of that interface will be used to compare items. Alternatively, a comparison
    /// function can be passed in either as a delegate, or as an instance of IComparer&lt;TKey&gt;.</p>
    /// <p>OrderedBag is implemented as a balanced binary tree. Inserting, deleting, and looking up an
    /// an element all are done in log(N) + M time, where N is the number of keys in the tree, and M is the current number
    /// of copies of the element being handled.</p>
    /// <p><see cref="Bag&lt;T&gt;"/> is similar, but uses hashing instead of comparison, and does not maintain
    /// the keys in sorted order.</p>
    ///</remarks>
    ///<seealso cref="Bag&lt;T&gt;"/>
    [Serializable]
    public class OrderedBag<T> : CollectionBase<T>, ICloneable
    {
        // The comparer used to compare items. 
        private IComparer<T> comparer;

        // The red-black tree that actually does the work of storing the items.
        private RedBlackTree<T> tree;

        #region Constructors

        /// <summary>
        /// Creates a new OrderedBag. The T must implement IComparable&lt;T&gt;
        /// or IComparable. 
        /// The CompareTo method of this interface will be used to compare items in this bag.
        /// </summary>
        ///<remarks>
        /// Items that are null are permitted, and will be sorted before all other items.
        ///</remarks>
        /// <exception cref="InvalidOperationException">T does not implement IComparable&lt;TKey&gt;.</exception>
        public OrderedBag(): 
            this(Comparers.DefaultComparer<T>())
        {
        }

        /// <summary>
        /// Creates a new OrderedBag. The passed delegate will be used to compare items in this bag.
        /// </summary>
        /// <param name="comparison">A delegate to a method that will be used to compare items.</param>
        public OrderedBag(Comparison<T> comparison) :
            this(Comparers.ComparerFromComparison<T>(comparison))
        {
        }

        /// <summary>
        /// Creates a new OrderedBag. The Compare method of the passed comparison object
        /// will be used to compare items in this bag.
        /// </summary>
        /// <remarks>
        /// The GetHashCode and Equals methods of the provided IComparer&lt;T&gt; will never
        /// be called, and need not be implemented.
        /// </remarks>
        /// <param name="comparer">An instance of IComparer&lt;T&gt; that will be used to compare items.</param>
        public OrderedBag(IComparer<T> comparer)
        {
            if (comparer == null)
                throw new ArgumentNullException("comparer");

            this.comparer = comparer;
            tree = new RedBlackTree<T>(comparer);
        }

        /// <summary>
        /// Creates a new OrderedBag. The T must implement IComparable&lt;T&gt;
        /// or IComparable. 
        /// The CompareTo method of this interface will be used to compare items in this bag. The bag is
        /// initialized with all the items in the given collection.
        /// </summary>
        ///<remarks>
        /// Items that are null are permitted, and will be sorted before all other items.
        ///</remarks>
        /// <param name="collection">A collection with items to be placed into the OrderedBag.</param>
        /// <exception cref="InvalidOperationException">T does not implement IComparable&lt;TKey&gt;.</exception>
        public OrderedBag(IEnumerable<T> collection): 
            this(collection, Comparers.DefaultComparer<T>())
        {
        }

        /// <summary>
        /// Creates a new OrderedBag. The passed delegate 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 OrderedBag.</param>
        /// <param name="comparison">A delegate to a method that will be used to compare items.</param>
        public OrderedBag(IEnumerable<T> collection, Comparison<T> comparison):
            this(collection, Comparers.ComparerFromComparison<T>(comparison))
        {
        }

        /// <summary>
        /// Creates a new OrderedBag. The Compare method 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>
        /// <remarks>
        /// The GetHashCode and Equals methods of the provided IComparer&lt;T&gt; will never
        /// be called, and need not be implemented.
        /// </remarks>
        /// <param name="collection">A collection with items to be placed into the OrderedBag.</param>
        /// <param name="comparer">An instance of IComparer&lt;T&gt; that will be used to compare items.</param>
        public OrderedBag(IEnumerable<T> collection, IComparer<T> comparer):
            this(comparer)
        {
            AddMany(collection);
        }

        /// <summary>
        /// Creates a new OrderedBag given a comparer and a tree that contains the data. Used
        /// internally for Clone.
        /// </summary>
        /// <param name="comparer">Comparer for the bag.</param>
        /// <param name="tree">Data for the bag.</param>
        private OrderedBag(IComparer<T> comparer, RedBlackTree<T> tree) 
        {
            this.comparer = comparer;
            this.tree = tree;
        }

        #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 items in the bag.</remarks>
        /// <returns>The cloned bag.</returns>
        public OrderedBag<T> Clone()
        {
            OrderedBag<T> newBag = new OrderedBag<T>(comparer, tree.Clone());
            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 OrderedBag<T> CloneContents()
        {
            bool itemIsValueType;
            if (!Util.IsCloneableType(typeof(T), out itemIsValueType))
                throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, typeof(T).FullName));

            OrderedBag<T> clone = new OrderedBag<T>(comparer);

            // Clone each item, and add it to the new ordered bag.
            foreach (T item in this) {
                T itemClone;

                if (itemIsValueType)
                    itemClone = item;
                else {
                    if (item == null)
                        itemClone = default(T);    // Really null, because we know T is a reference type
                    else
                        itemClone = (T)(((ICloneable)item).Clone());
                }

                clone.Add(itemClone);
            }

            return clone;
        }

        #endregion Cloning

        #region Basic collection containment

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

        /// <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 tree.ElementCount;
            }
        }

        /// <summary>
        /// Returns the number of copies of <paramref name="item"/> in the bag. More precisely, returns
        /// the number of items in the bag that compare equal to <paramref name="item"/>.
        /// </summary>
        /// <remarks>NumberOfCopies() takes time O(log N + M), where N is the total number of items in the
        /// bag, and M is the number of copies of <paramref name="item"/> 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)
        {
            return tree.CountRange(tree.EqualRangeTester(item));
        }

        /// <summary>
        /// Returns an enumerator that enumerates all the items in the bag. 
        /// The items are enumerated in sorted order.
        /// </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 OrderedBag.</returns>		
        public sealed override IEnumerator<T> GetEnumerator()
        {
            return tree.GetEnumerator();
        }