?//******************************
// 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;
using System.Diagnostics;

namespace Wintellect.PowerCollections
{
    /// <summary>
    /// MultiDictionaryBase is a base class that can be used to more easily implement a class
    /// that associates multiple values to a single key. The class implements the generic
    /// IDictionary&lt;TKey, ICollection&lt;TValue&gt;&gt; interface.
    /// </summary>
    /// <remarks>
    /// <para>To use MultiDictionaryBase as a base class, the derived class must override
    /// Count, Clear, Add, Remove(TKey), Remove(TKey,TValue), Contains(TKey,TValue), 
    /// EnumerateKeys, and TryEnumerateValuesForKey. </para>
    /// <para>It may wish consider overriding CountValues, CountAllValues, ContainsKey,
    /// and EqualValues, but these are not required.
    /// </para>
    /// </remarks>
    /// <typeparam name="TKey">The key type of the dictionary.</typeparam>
    /// <typeparam name="TValue">The value type of the dictionary.</typeparam>
    [Serializable]
    [DebuggerDisplay("{DebuggerDisplayString()}")]
    public abstract class MultiDictionaryBase<TKey, TValue> : CollectionBase<KeyValuePair<TKey, ICollection<TValue>>>,
                                                                                               IDictionary<TKey, ICollection<TValue>>
    {
        /// <summary>
        /// Creates a new MultiDictionaryBase. 
        /// </summary>
        protected MultiDictionaryBase()
        {
        }

        /// <summary>
        /// Clears the dictionary. This method must be overridden in the derived class.
        /// </summary>
        public abstract override void Clear();

        /// <summary>
        /// Gets the number of keys in the dictionary. This property must be overridden
        /// in the derived class.
        /// </summary>
        public abstract override int Count
        {
            get;
        }

        /// <summary>
        /// Enumerate all the keys in the dictionary. This method must be overridden by a derived
        /// class.
        /// </summary>
        /// <returns>An IEnumerator&lt;TKey&gt; that enumerates all of the keys in the collection that
        /// have at least one value associated with them.</returns>
        protected abstract IEnumerator<TKey> EnumerateKeys();

        /// <summary>
        /// Enumerate all of the values associated with a given key. This method must be overridden
        /// by the derived class. If the key exists and has values associated with it, an enumerator for those
        /// values is returned throught <paramref name="values"/>. If the key does not exist, false is returned.
        /// </summary>
        /// <param name="key">The key to get values for.</param>
        /// <param name="values">If true is returned, this parameter receives an enumerators that
        /// enumerates the values associated with that key.</param>
        /// <returns>True if the key exists and has values associated with it. False otherwise.</returns>
        protected abstract bool TryEnumerateValuesForKey(TKey key, out IEnumerator<TValue> values);

        /// <summary>
        /// Adds a key-value pair to the collection. The value part of the pair must be a collection
        /// of values to associate with the key. If values are already associated with the given
        /// key, the new values are added to the ones associated with that key.
        /// </summary>
        /// <param name="item">A KeyValuePair contains the Key and Value collection to add.</param>
        public override void Add(KeyValuePair<TKey, ICollection<TValue>> item)
        {
            this.AddMany(item.Key, item.Value);
        }

        /// <summary>
        /// Implements IDictionary&lt;TKey, IEnumerable&lt;TValue&gt;&gt;.Add. If the 
        /// key is already present, and ArgumentException is thrown. Otherwise, a
        /// new key is added, and new values are associated with that key.
        /// </summary>
        /// <param name="key">Key to add.</param>
        /// <param name="values">Values to associate with that key.</param>
        /// <exception cref="ArgumentException">The key is already present in the dictionary.</exception>
        void IDictionary<TKey, ICollection<TValue>>.Add(TKey key, ICollection<TValue> values)
        {
            if (ContainsKey(key)) {
                throw new ArgumentException(Strings.KeyAlreadyPresent, "key");
            }
            else {
                AddMany(key, values);
            }
        }

        /// <summary>
        /// <para>Adds new values to be associated with a key. If duplicate values are permitted, this
        /// method always adds new key-value pairs to the dictionary.</para>
        /// <para>If duplicate values are not permitted, and <paramref name="key"/> already has a value
        /// equal to one of <paramref name="values"/> associated with it, then that value is replaced,
        /// and the number of values associate with <paramref name="key"/> is unchanged.</para>
        /// </summary>
        /// <param name="key">The key to associate with.</param>
        /// <param name="values">A collection of values to associate with <paramref name="key"/>.</param>
        public virtual void AddMany(TKey key, IEnumerable<TValue> values)
        {
            foreach (TValue value in values)
                Add(key, value);
        }

        /// <summary>
        /// Adds a new key-value pair to the dictionary.  This method must be overridden in the derived class.
        /// </summary>
        /// <param name="key">Key to add.</param>
        /// <param name="value">Value to associated with the key.</param>
        /// <exception cref="ArgumentException">key is already present in the dictionary</exception>
        public abstract void Add(TKey key, TValue value);

        /// <summary>
        /// Removes a key from the dictionary. This method must be overridden in the derived class.
        /// </summary>
        /// <param name="key">Key to remove from the dictionary.</param>
        /// <returns>True if the key was found, false otherwise.</returns>
        public abstract bool Remove(TKey key);

        /// <summary>
        /// Removes a key-value pair from the dictionary. This method must be overridden in the derived class.
        /// </summary>
        /// <param name="key">Key to remove from the dictionary.</param>
        /// <param name="value">Associated value to remove from the dictionary.</param>
        /// <returns>True if the key-value pair was found, false otherwise.</returns>
        public abstract bool Remove(TKey key, TValue value);

        /// <summary>
        /// Removes a set of values from a given key. If all values associated with a key are
        /// removed, then the key is removed also.
        /// </summary>
        /// <param name="pair">A KeyValuePair contains a key and a set of values to remove from that key.</param>
        /// <returns>True if at least one values was found and removed.</returns>
        public override bool Remove(KeyValuePair<TKey,ICollection<TValue>> pair)
        {
 	        return RemoveMany(pair.Key, pair.Value) > 0;  
        }

        /// <summary>
        /// Removes a collection of values from the values associated with a key. If the
        /// last value is removed from a key, the key is removed also.
        /// </summary>
        /// <param name="key">A key to remove values from.</param>
        /// <param name="values">A collection of values to remove.</param>
        /// <returns>The number of values that were present and removed. </returns>
        public virtual int RemoveMany(TKey key, IEnumerable<TValue> values)
        {
            int countRemoved = 0;

            foreach (TValue val in values) {
                if (Remove(key, val))
                    ++countRemoved;
            }

            return countRemoved;
        }

        /// <summary>
        /// Remove all of the keys (and any associated values) in a collection
        /// of keys. If a key is not present in the dictionary, nothing happens.
        /// </summary>
        /// <param name="keyCollection">A collection of key values to remove.</param>
        /// <returns>The number of keys from the collection that were present and removed.</returns>
        public int RemoveMany(IEnumerable<TKey> keyCollection)
        {
            int count = 0;
            foreach (TKey key in keyCollection) {
                if (Remove(key))
                    ++count;
            }

            return count;
        }


        /// <summary>
        /// Determines if this dictionary contains a key equal to <paramref name="key"/>. If so, all the values
        /// associated with that key are returned through the values parameter. This method must be
        /// overridden by the derived class.
        /// </summary>
        /// <param name="key">The key to search for.</param>
        /// <param name="values">Returns all values associated with key, if true was returned.</param>
        /// <returns>True if the dictionary contains key. False if the dictionary does not contain key.</returns>
        bool IDictionary<TKey,ICollection<TValue>>.TryGetValue(TKey key, out ICollection<TValue> values)
        {
            if (ContainsKey(key)) {
                values = this[key];
                return true;
            }
            else {
                values = null;
                return false;
            }
        }

        /// <summary>
        /// Determines whether a given key is found in the dictionary.
        /// </summary>
        /// <remarks>The default implementation simply calls TryEnumerateValuesForKey.
        /// It may be appropriate to override this method to 
        /// provide a more efficient implementation.</remarks>
        /// <param name="key">Key to look for in the dictionary.</param>
        /// <returns>True if the key is present in the dictionary.</returns>
        public virtual bool ContainsKey(TKey key)
        {
            IEnumerator<TValue> values;
            return TryEnumerateValuesForKey(key, out values);
        }

        /// <summary>
        /// Determines if this dictionary contains a key-value pair equal to <paramref name="key"/> and 
        /// <paramref name="value"/>. The dictionary is not changed. This method must be overridden in the derived class.
        /// </summary>
        /// <param name="key">The key to search for.</param>
        /// <param name="value">The value to search for.</param>
        /// <returns>True if the dictionary has associated <paramref name="value"/> with <paramref name="key"/>.</returns>
        public abstract bool Contains(TKey key, TValue value);

        /// <summary>
        /// Determines if this dictionary contains the given key and all of the values associated with that key..
        /// </summary>
        /// <param name="pair">A key and collection of values to search for.</param>
        /// <returns>True if the dictionary has associated all of the values in <paramref name="pair"/>.Value with <paramref name="pair"/>.Key.</returns>
        public override bool Contains(KeyValuePair<TKey,ICollection<TValue>> pair)
        {
            foreach (TValue val in pair.Value) {
                if (! Contains(pair.Key, val))
                    return false;
            }

            return true;
        }

        // Cache the equality comparer after we get it the first time.
        private volatile IEqualityComparer<TValue> valueEqualityComparer;

        /// <summary>
        /// If the derived class does not use the default comparison for values, this
        /// methods should be overridden to compare two values for equality. This is
        /// used for the correct implementation of ICollection.Contains on the Values
        /// and KeyValuePairs collections.
        /// </summary>
        /// <param name="value1">First value to compare.</param>
        /// <param name="value2">Second value to compare.</param>
        /// <returns>True if the values are equal.</returns>
        protected virtual bool EqualValues(TValue value1, TValue value2)
        {
            if (valueEqualityComparer == null)
                valueEqualityComparer = EqualityComparer<TValue>.Default;
            return valueEqualityComparer.Equals(value1, value2);
        }

        /// <summary>
        /// Gets a count of the number of values associated with a key. The
        /// default implementation is slow; it enumerators all of the values
        /// (using TryEnumerateValuesForKey) to count them. A derived class
        /// may be able to supply a more efficient implementation.
        /// </summary>
        /// <param name="key">The key to count values for.</param>
        /// <returns>The number of values associated with <paramref name="key"/>.</returns>
        protected virtual int CountValues(TKey key)
        {