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

namespace Developpez.Dotnet.Collections
{
    /// <summary>
    /// Dictionnaire qui maintient ses éléments dans l'ordre où ils ont été ajoutés
    /// </summary>
    /// <typeparam name="TKey">Type de la clé</typeparam>
    /// <typeparam name="TValue">Type de la valeur</typeparam>
    public class OrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>
    {
        private readonly object _syncLock = new object();
        private readonly Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> _nodes;
        private readonly LinkedList<KeyValuePair<TKey, TValue>> _entries;

        /// <summary>
        /// Initialise une nouvelle instance vide de OrderedDictionary, qui utilise
        /// le comparateur spécifié pour tester l'égalité des clés.
        /// </summary>
        /// <param name="comparer">Comparateur utilisé pour tester l'égalité des clés</param>
        public OrderedDictionary(IEqualityComparer<TKey> comparer)
        {
            _nodes = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>(comparer);
            _entries = new LinkedList<KeyValuePair<TKey, TValue>>();
        }

        /// <summary>
        /// Initialise une nouvelle instance vide de OrderedDictionary
        /// </summary>
        public OrderedDictionary()
            : this (default(IEqualityComparer<TKey>))
        {
        }

        /// <summary>
        /// Initialise une nouvelle instance de OrderedDictionary qui contient les
        /// éléments du dictionnaire spécifié et utilise le comparateur spécifié
        /// pour tester l'égalité des clés.
        /// </summary>
        /// <param name="dictionary">Dictionnaire à partir duquel copier les éléments</param>
        /// <param name="comparer">Comparateur utilisé pour tester l'égalité des clés</param>
        public OrderedDictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer)
            : this(comparer)
        {
            foreach (var kvp in dictionary)
            {
                this.Add(kvp.Key, kvp.Value);
            }
        }

        /// <summary>
        /// Initialise une nouvelle instance de OrderedDictionary qui contient les
        /// éléments du dictionnaire spécifié.
        /// </summary>
        /// <param name="dictionary">Dictionnaire à partir duquel copier les éléments</param>
        public OrderedDictionary(IDictionary<TKey, TValue> dictionary)
            : this(dictionary, null)
        {
            
        }

        #region Implementation of IEnumerable

        /// <summary>
        /// Retourne un énumérateur qui parcourt le dictionnaire
        /// </summary>
        /// <returns>Un énumerateur pour parcourir le dictionnaire</returns>
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return _entries.GetEnumerator();
        }

        /// <summary>
        /// Retourne un énumérateur qui parcourt le dictionnaire
        /// </summary>
        /// <returns>Un énumerateur pour parcourir le dictionnaire</returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region Implementation of ICollection<KeyValuePair<TKey,TValue>>

        /// <summary>
        /// Ajoute la paire clé/valeur spécifiée au dictionnaire 
        /// </summary>
        /// <param name="item">Paire clé/valeur à ajouter</param>
        public void Add(KeyValuePair<TKey, TValue> item)
        {
            Add(item.Key, item.Value);
        }

        /// <summary>
        /// Supprime toutes les clés et les valeurs du dictionnaire.
        /// </summary>
        public void Clear()
        {
            lock (_syncLock)
            {
                _entries.Clear();
                _nodes.Clear();
            }
        }

        /// <summary>
        /// Détermine si le dictionnaire contient la paire clé/valeur spécifiée.
        /// </summary>
        /// <param name="item">Paire clé/valeur recherchée</param>
        /// <returns>true si le dictionnaire contient la paire clé/valeur, false sinon</returns>
        public bool Contains(KeyValuePair<TKey, TValue> item)
        {
            lock (_syncLock)
            {
                TValue value;
                if (TryGetValue(item.Key, out value))
                    return EqualityComparer<TValue>.Default.Equals(item.Value, value);
                return false;
            }
        }

        /// <summary>
        /// Copie les éléments du dictionnaire dans un tableau, à partir de la position spécifiée
        /// </summary>
        /// <param name="array">Tableau de destination</param>
        /// <param name="arrayIndex">Index du tableau où commencer la copie</param>
        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            lock (_syncLock)
            {
                this.CopyTo(array, arrayIndex);
            }
        }

        /// <summary>
        /// Supprime du dictionnaire la paire clé/valeur spécifiée.
        /// </summary>
        /// <param name="item">Paire clé/valeur</param>
        /// <returns>true si la recherche et la suppression de l'élément réussissent ; sinon, false.</returns>
        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            lock (_syncLock)
            {
                LinkedListNode<KeyValuePair<TKey, TValue>> node;
                if (_nodes.TryGetValue(item.Key, out node))
                {
                    if (EqualityComparer<TValue>.Default.Equals(item.Value, node.Value.Value))
                        return Remove(item.Key);
                }
                return false;
            }
        }

        /// <summary>
        /// Obtient le nombre de paires clé/valeur contenues dans le dictionnaire.
        /// </summary>
        public int Count
        {
            get { return _nodes.Count; }
        }

        /// <summary>
        /// Obtient une valeur indiquant si le dictionnaire est en lecture seule.
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }

        #endregion

        #region Implementation of IDictionary<TKey,TValue>

        /// <summary>
        /// Détermine si le dictionnaire contient la clé spécifiée. 
        /// </summary>
        /// <param name="key">Clé à rechercher</param>
        /// <returns>true si le dictionnaire contient un élément correspondant à la clé spécifiée ; sinon, false.</returns>
        /// <remarks>Cette méthode est proche d'une opération en O(1).</remarks>
        public bool ContainsKey(TKey key)
        {
            return _nodes.ContainsKey(key);
        }

        /// <summary>
        /// Ajoute la clé et la valeur spécifiées au dictionnaire. 
        /// </summary>
        /// <param name="key">Clé de l'élément à ajouter. </param>
        /// <param name="value">Valeur de l'élément à ajouter. La valeur peut être null pour les types référence.</param>
        /// <remarks>Cette méthode est proche d'une opération en O(1) si la capacité interne est suffisante.
        /// Si la capacité doit être augmentée, cette méthode devient une opération en O(n).</remarks>
        public void Add(TKey key, TValue value)
        {
            lock (_syncLock)
            {
                var entry = new KeyValuePair<TKey, TValue>(key, value);
                var node = new LinkedListNode<KeyValuePair<TKey, TValue>>(entry);
                _nodes.Add(key, node);
                _entries.AddLast(node);
            }
        }

        /// <summary>
        /// Supprime du dictionnaire la valeur ayant la clé spécifiée. 
        /// </summary>
        /// <param name="key">Clé de l'élément à supprimer.</param>
        /// <returns>true si la recherche et la suppression de l'élément réussissent ; sinon, false.</returns>
        /// <remarks>Cette méthode est proche d'une opération en O(1).</remarks>
        public bool Remove(TKey key)
        {
            lock (_syncLock)
            {
                LinkedListNode<KeyValuePair<TKey, TValue>> node;
                if (_nodes.TryGetValue(key, out node))
                {
                    _nodes.Remove(key);
                    _entries.Remove(node);
                    return true;
                }
                return false;
            }
        }

        /// <summary>
        /// Obtient la valeur associée à la clé spécifiée. 
        /// </summary>
        /// <param name="key">Clé de la valeur à obtenir.</param>
        /// <param name="value">Paramètre de sortie auquel est affecté la valeur trouvée</param>
        /// <returns>true si le dictionnaire contient un élément correspondant à la clé spécifiée ; sinon, false.</returns>
        /// <remarks>Cette méthode est proche d'une opération en O(1).</remarks>
        public bool TryGetValue(TKey key, out TValue value)
        {
            LinkedListNode<KeyValuePair<TKey, TValue>> node;
            if (_nodes.TryGetValue(key, out node))
            {
                value = node.Value.Value;
                return true;
            }
            value = default(TValue);
            return false;
        }

        /// <summary>
        /// Obtient ou définit la valeur associée à la clé spécifiée.
        /// </summary>
        /// <param name="key">Clé de l'élément à obtenir ou à définir</param>
        /// <value>Valeur associée à la clé spécifiée. Si la clé spécifiée est introuvable, une opération Get retourne KeyNotFoundException et une opération Set crée un nouvel élément avec la clé spécifiée.</value>
        /// <remarks>Obtenir la valeur de cette propriété est proche d'une opération en O(1). Définir la valeur
        /// de cette propriété est proche d'une opération en O(1) si la capacité interne est suffisante
        /// ou que la clé est déjà présente dans le dictionnaire. Si la clé n'est pas déjà présente et que
        /// la capacité doit être augmentée, définir la valeur devient une opération en O(n).</remarks>
        public TValue this[TKey key]
        {
            get
            {
                lock (_syncLock)
                {
                    TValue value;
                    if (TryGetValue(key, out value))
                        return value;
                    throw new KeyNotFoundException();
                }
            }
            set
            {
                lock (_syncLock)
                {
                    LinkedListNode<KeyValuePair<TKey, TValue>> node;
                    if (_nodes.TryGetValue(key, out node))
                    {
                        node.Value = new KeyValuePair<TKey, TValue>(key, value);
                    }
                    else
                    {
                        Add(key, value);
                    }
                }
            }
        }

        /// <summary>
        /// Obtient une collection contenant les clés du dictionnaire.
        /// </summary>
        /// <remarks>Les clés sont renvoyées dans l'ordre où elles ont été ajoutées.</remarks>
        public ICollection<TKey> Keys
        {
            get
            {
                lock (_syncLock)
                {
                    var keys = _entries.Select(e => e.Key);
                    return keys.ToList().AsReadOnly(); 
                }
            }
        }

        /// <summary>
        /// Obtient une collection contenant les valeurs du dictionnaire.
        /// </summary>
        /// <remarks>Les valeurs sont renvoyées dans l'ordre où elles ont été ajoutées.</remarks>
        public ICollection<TValue> Values
        {
            get
            {
                lock (_syncLock)
                {
                    var values = _entries.Select(e => e.Value);
                    return values.ToList().AsReadOnly();
                }
            }
        }

        #endregion
    }
}