//******************************
// 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;
using System.Collections.Generic;

namespace Wintellect.PowerCollections
{
	/// <summary>
	/// OrderedDictionary&lt;TKey, TValue&gt; is a collection that maps keys of type TKey
	/// to values of type TValue. The keys are maintained in a sorted order, and at most one value
	/// is permitted for each key.
	/// </summary>
	/// <remarks>
	/// <p>The keys are compared in one of three ways. If TKey implements IComparable&lt;TKey&gt; or IComparable,
	/// then the CompareTo method of that interface will be used to compare elements. Alternatively, a comparison
	/// function can be passed in either as a delegate, or as an instance of IComparer&lt;TKey&gt;.</p>
	/// <p>OrderedDictionary is implemented as a balanced binary tree. Inserting, deleting, and looking up an
	/// an element all are done in log(N) type, where N is the number of keys in the tree.</p>
	/// <p><see cref="Dictionary&lt;TKey,TValue&gt;"/> is similar, but uses hashing instead of comparison, and does not maintain
	/// the keys in sorted order.</p>
	///</remarks>
	///<seealso cref="Dictionary&lt;TKey,TValue&gt;"/>
    [Serializable]
	public class OrderedDictionary<TKey,TValue>: DictionaryBase<TKey,TValue>, ICloneable
	{
        // The comparer for comparing keys. This is saved to return from the Comparer property,
        // but is otherwise not used.
        private IComparer<TKey> keyComparer;

		// The comparer for comparing key-value pairs.
		private IComparer<KeyValuePair<TKey,TValue>> pairComparer;

		private RedBlackTree<KeyValuePair<TKey,TValue>> tree;

        /// <summary>
        /// Helper function to create a new KeyValuePair struct.
        /// </summary>
        /// <param name="key">The key.</param>
        /// <param name="value">The value.</param>
        /// <returns>A new KeyValuePair.</returns>
        private static KeyValuePair<TKey,TValue> NewPair(TKey key, TValue value) {
            KeyValuePair<TKey, TValue> pair = new KeyValuePair<TKey,TValue>(key,value);
            return pair;
        }

        /// <summary>
        /// Helper function to create a new KeyValuePair struct with a default value.
        /// </summary>
        /// <param name="key">The key.</param>
        /// <returns>A new KeyValuePair.</returns>
        private static KeyValuePair<TKey, TValue> NewPair(TKey key)
        {
            KeyValuePair<TKey, TValue> pair = new KeyValuePair<TKey,TValue>(key, default(TValue));
            return pair;
        }

        /// <summary>
        /// Creates a new OrderedDictionary. The TKey must implemented IComparable&lt;TKey&gt;
		/// or IComparable. 
		/// The CompareTo method of this interface will be used to compare keys in this dictionary.
		/// </summary>
		/// <exception cref="InvalidOperationException">TKey does not implement IComparable&lt;TKey&gt;.</exception>
		public OrderedDictionary() :
            this(Comparers.DefaultComparer<TKey>())
		{
		}

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

        /// <summary>
		/// Creates a new OrderedDictionary. The passed delegate will be used to compare keys in this dictionary.
		/// </summary>
		/// <param name="comparison">A delegate to a method that will be used to compare keys.</param>
		public OrderedDictionary(Comparison<TKey> comparison) :
            this(null, Comparers.ComparerFromComparison<TKey>(comparison), Comparers.ComparerKeyValueFromComparisonKey<TKey, TValue>(comparison))
		{
        }

        /// <summary>
        /// <para>Creates a new OrderedDictionary. The TKey must implemented IComparable&lt;TKey&gt;
        /// or IComparable. 
        /// The CompareTo method of this interface will be used to compare keys in this dictionary.</para>
        /// <para>A collection and keys and values (typically another dictionary) is used to initialized the 
        /// contents of the dictionary.</para>
        /// </summary>
        /// <param name="keysAndValues">A collection of keys and values whose contents are used to initialized the dictionary.</param>
        /// <exception cref="InvalidOperationException">TKey does not implement IComparable&lt;TKey&gt;.</exception>
        public OrderedDictionary(IEnumerable<KeyValuePair<TKey,TValue>> keysAndValues)
            : this(keysAndValues, Comparers.DefaultComparer<TKey>())
        {
        }

        /// <summary>
        /// <para>Creates a new OrderedDictionary. The Compare method of the passed comparison object
        /// will be used to compare keys in this dictionary.</para>
        /// <para>A collection and keys and values (typically another dictionary) is used to initialized the 
        /// contents of the dictionary.</para>
        /// </summary>
        /// <remarks>
        /// The GetHashCode and Equals methods of the provided IComparer&lt;TKey&gt; will never
        /// be called, and need not be implemented.</remarks>
        /// <param name="keysAndValues">A collection of keys and values whose contents are used to initialized the dictionary.</param>
        /// <param name="comparer">An instance of IComparer&lt;TKey&gt; that will be used to compare keys.</param>
        public OrderedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> keysAndValues, IComparer<TKey> comparer)
            : this(keysAndValues, comparer, Comparers.ComparerKeyValueFromComparerKey<TKey, TValue>(comparer))
        {
            if (comparer == null)
                throw new ArgumentNullException("comparer");
        }

        /// <summary>
        /// <para>Creates a new OrderedDictionary. The passed delegate will be used to compare keys in this dictionary.</para>
        /// <para>A collection and keys and values (typically another dictionary) is used to initialized the 
        /// contents of the dictionary.</para>
        /// </summary>
        /// <param name="keysAndValues">A collection of keys and values whose contents are used to initialized the dictionary.</param>
        /// <param name="comparison">A delegate to a method that will be used to compare keys.</param>
        public OrderedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> keysAndValues, Comparison<TKey> comparison)
            : this(keysAndValues, Comparers.ComparerFromComparison<TKey>(comparison), Comparers.ComparerKeyValueFromComparisonKey<TKey, TValue>(comparison))
        {
        }

        /// <summary>
		/// Creates a new OrderedDictionary. The passed comparer 
		/// will be used to compare key-value pairs in this dictionary. Used internally  
		/// from other constructors.
		/// </summary>
        /// <param name="keysAndValues">A collection of keys and values whose contents are used to initialized the dictionary.</param>
        /// <param name="keyComparer">An IComparer that will be used to compare keys.</param>
        /// <param name="pairComparer">An IComparer that will be used to compare key-value pairs.</param>
        private OrderedDictionary(IEnumerable<KeyValuePair<TKey,TValue>> keysAndValues, IComparer<TKey> keyComparer, IComparer<KeyValuePair<TKey,TValue>> pairComparer)
		{
            this.keyComparer = keyComparer;
            this.pairComparer = pairComparer;
            tree = new RedBlackTree<KeyValuePair<TKey,TValue>>(this.pairComparer);

            if (keysAndValues != null)
                AddMany(keysAndValues);
		}

        /// <summary>
        /// Creates a new OrderedDictionary. The passed comparison delegate 
        /// will be used to compare keys in this dictionary, and the given tree is used. Used internally for Clone().
        /// </summary>
        /// <param name="keyComparer">An IComparer that will be used to compare keys.</param>
        /// <param name="pairComparer">A delegate to a method that will be used to compare key-value pairs.</param>
        /// <param name="tree">RedBlackTree that contains the data for the dictionary.</param>
        private OrderedDictionary(IComparer<TKey> keyComparer, IComparer<KeyValuePair<TKey, TValue>> pairComparer, RedBlackTree<KeyValuePair<TKey, TValue>> tree)
        {
            this.keyComparer = keyComparer;
            this.pairComparer = pairComparer;
            this.tree = tree;
        }

        /// <summary>
        /// Makes a shallow clone of this dictionary; i.e., if keys or values of the
		/// dictionary are reference types, then they are not cloned. If TKey or TValue is a value type,
		/// then each element is copied as if by simple assignment.
		/// </summary>
        /// <remarks>Cloning the dictionary takes time O(N), where N is the number of keys in the dictionary.</remarks>
        /// <returns>The cloned dictionary.</returns>
        public OrderedDictionary<TKey,TValue> Clone()
		{
			OrderedDictionary<TKey,TValue> newDict = new OrderedDictionary<TKey,TValue>(keyComparer, pairComparer, tree.Clone());
			return newDict;
		}

        /// <summary>
        /// Throw an InvalidOperationException indicating that this type is not cloneable.
        /// </summary>
        /// <param name="t">Type to test.</param>
        private void NonCloneableType(Type t)
        {
            throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, t.FullName));
        }

        /// <summary>
		/// Makes a deep clone of this dictionary. A new dictionary is created with a clone of
		/// each entry of this dictionary, by calling ICloneable.Clone on each element. If TKey or TValue is
		/// a value type, then each element is copied as if by simple assignment.
		/// </summary>
		/// <remarks><para>If TKey or TValue is a reference type, it must implement
        /// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
        /// <para>Cloning the dictionary takes time O(N log N), where N is the number of keys in the dictionary.</para></remarks>
        /// <returns>The cloned dictionary.</returns>
        /// <exception cref="InvalidOperationException">TKey or TValue is a reference type that does not implement ICloneable.</exception>
		public OrderedDictionary<TKey,TValue> CloneContents()
		{
            bool keyIsValueType, valueIsValueType;

            // Make sure that TKey and TValue can be cloned.
            if (!Util.IsCloneableType(typeof(TKey), out keyIsValueType))
                NonCloneableType(typeof(TKey));

            if (!Util.IsCloneableType(typeof(TValue), out valueIsValueType))
                NonCloneableType(typeof(TValue));

            OrderedDictionary<TKey, TValue> newDict = new OrderedDictionary<TKey, TValue>(null, keyComparer, pairComparer);

            foreach (KeyValuePair<TKey, TValue> pair in tree) {
                // Clone the key and value parts of the pair. Value types can be cloned
                // by just copying them, otherwise, ICloneable is used.
                TKey keyClone;
                TValue valueClone;

                if (keyIsValueType)
                    keyClone = pair.Key;
                else {
                    if (pair.Key == null)
                        keyClone = default(TKey);  // Really null, because we know TKey isn't a value type.
                    else
                        keyClone = (TKey)(((ICloneable)pair.Key).Clone());
                }

                if (valueIsValueType)
                    valueClone = pair.Value;
                else {
                    if (pair.Value == null)
                        valueClone = default(TValue);   // Really null, because we know TKey isn't a value type.
                    else
                        valueClone = (TValue)(((ICloneable)pair.Value).Clone());
                }

                newDict.Add(keyClone, valueClone);
            }

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


        /// <summary>
        /// Returns a View collection that can be used for enumerating the keys and values in the collection in 
        /// reversed order.