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

namespace Developpez.Dotnet.Collections
{
    /// <summary>
    /// Représente une collection de type file (premier entré, premier sorti, FIFO),
    /// où chaque élément n'est présent qu'une fois.
    /// </summary>
    /// <typeparam name="T">Type des éléments de la collection</typeparam>
    /// <remarks>Si un élément déjà présent est ajouté à nouveau, il est replacé à la fin de la pile</remarks>
    public class QueueSet<T> : ICollection<T>
    {
        private readonly LinkedList<T> _items;
        private readonly Dictionary<T, LinkedListNode<T>> _nodes;
        private readonly IEqualityComparer<T> _comparer;

        /// <summary>
        /// Crée une nouvelle instance de <c>QueueSet&lt;T&gt;</c> avec le comparateur d'égalité par défaut
        /// </summary>
        public QueueSet()
            : this(null)
        {
        }

        /// <summary>
        /// Crée une nouvelle instance de <c>QueueSet&lt;T&gt;</c> avec le comparateur d'égalité spécifié
        /// </summary>
        /// <param name="comparer">Comparateur à utiliser pour tester l'égalité des éléments</param>
        public QueueSet(IEqualityComparer<T> comparer)
        {
            _comparer = comparer ?? EqualityComparer<T>.Default;
            _items = new LinkedList<T>();
            _nodes = new Dictionary<T, LinkedListNode<T>>(_comparer);
        }

        /// <summary>
        /// Ajoute une élément à la fin de la file. Si l'élément est déjà présent, il est replacé à la fin de la file
        /// </summary>
        /// <param name="item">Élément à ajouter</param>
        /// <returns>true si l'élément a été ajouté, false s'il était déjà présent</returns>
        /// <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 bool Enqueue(T item)
        {
            LinkedListNode<T> node;
            if (_nodes.TryGetValue(item, out node))
            {
                if (node.Next != null) // i.e. not already at the end of the queue
                {
                    _items.Remove(node);
                    node = _items.AddLast(item);
                    _nodes[item] = node;
                }
                return false;
            }
            node = _items.AddLast(item);
            _nodes[item] = node;
            return true;
        }

        /// <summary>
        /// Supprime et retourne l'élément se trouvant en tête de la file
        /// </summary>
        /// <returns>L'élément qui se trouvait en tête de la file</returns>
        /// <remarks>Cette méthode est proche d'une opération en O(1)</remarks>
        public T Dequeue()
        {
            var node = _items.First;
            if (node == null)
                throw new InvalidOperationException("The queue was empty");
            T item = node.Value;
            _items.RemoveFirst();
            _nodes.Remove(item);
            return item;
        }

        /// <summary>
        /// Retourne l'élément se trouvant en tête de la file, sans le supprimer
        /// </summary>
        /// <returns>L'élément se trouvant en tête de la file</returns>
        /// <remarks>Cette méthode est une opération en O(1).</remarks>
        public T Peek()
        {
            var node = _items.First;
            if (node == null)
                throw new InvalidOperationException("The queue was empty");
            return node.Value;
        }

        #region Implementation of IEnumerable<T>

        /// <summary>
        /// Renvoie un énumérateur pour parcourir les éléments de la collection
        /// </summary>
        /// <returns>Un énumérateur pour parcourir les éléments de la collection</returns>
        public IEnumerator<T> GetEnumerator()
        {
            return _items.GetEnumerator();
        }

        /// <summary>
        /// Renvoie un énumérateur pour parcourir les éléments de la collection
        /// </summary>
        /// <returns>Un énumérateur pour parcourir les éléments de la collection</returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region Implementation of ICollection<T>

        /// <summary>
        /// Ajoute un élément à la collection
        /// </summary>
        /// <param name="item">Élément à ajouter</param>
        void ICollection<T>.Add(T item)
        {
            Enqueue(item);
        }

        /// <summary>
        /// Supprime un élément de la collection
        /// </summary>
        /// <param name="item">Élément à supprimer</param>
        /// <returns>true si l'élément a été supprimé, false s'il n'appartenait pas à la collection</returns>
        bool ICollection<T>.Remove(T item)
        {
            LinkedListNode<T> node;
            if (_nodes.TryGetValue(item, out node))
            {
                _items.Remove(node);
                _nodes.Remove(item);
                return true;
            }
            return false;
        }

        /// <summary>
        /// Supprime tous les éléments de la collection
        /// </summary>
        /// <remarks>Cette méthode est une opération en O(n).</remarks>
        public void Clear()
        {
            _items.Clear();
            _nodes.Clear();
        }

        /// <summary>
        /// Indique si l'élément est présent dans la collection
        /// </summary>
        /// <param name="item">Élément recherché</param>
        /// <returns>true si l'élément est présent dans la collection, sinon false</returns>
        /// <remarks>Cette méthode est proche d'une opération en O(1).</remarks>
        public bool Contains(T item)
        {
            return _nodes.ContainsKey(item);
        }

        /// <summary>
        /// Copie les éléments de la collection vers le tableau spécifié
        /// </summary>
        /// <param name="array">Tableau vers lequel les éléments sont copiés</param>
        /// <param name="arrayIndex">Position dans le tableau à laquelle la copie commence</param>
        /// <remarks>Cette méthode est une opération en O(n).</remarks>
        public void CopyTo(T[] array, int arrayIndex)
        {
            _items.CopyTo(array, arrayIndex);
        }

        /// <summary>
        /// Renvoie le nombre d'éléments dans la collection
        /// </summary>
        /// <remarks>Obtenir la valeur de cette propriété est une opération en O(1).</remarks>
        public int Count
        {
            get { return _items.Count; }
        }

        /// <summary>
        /// Indique si la collection est en lecture seule
        /// </summary>
        /// <remarks>Obtenir la valeur de cette propriété est une opération en O(1).</remarks>
        public bool IsReadOnly
        {
            get { return false; }
        }

        #endregion
    }
}