using System;
using System.Collections.Generic;
using System.Linq;
using Developpez.Dotnet.Properties;
using JetBrains.Annotations;

namespace Developpez.Dotnet.Collections
{
    public static partial class EnumerableExtensions
    {
        #region BinarySearch and related methods

        /// <summary>
        /// Effectue une recherche binaire sur une liste triée pour trouver un élément selon
        /// la valeur d'une de ses propriétés. La liste doit être triée selon cette propriété.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la collection</typeparam>
        /// <typeparam name="TKey">Type de la clé de recherche</typeparam>
        /// <param name="list">Liste dans laquelle rechercher l'élément</param>
        /// <param name="keySelector">Fonction permettant d'obtenir la clé de recherche</param>
        /// <param name="key">Valeur de la clé recherchée</param>
        /// <returns>Le premier élément correspondant, s'il existe. Sinon, lève une InvalidOperationException.</returns>
        public static T BinarySearch<T, TKey>(
            [NotNull] this IList<T> list,
            [NotNull] Func<T, TKey> keySelector,
            TKey key)
            where TKey : IComparable<TKey>
        {
            T result;
            if (list.TryBinarySearch(keySelector, key, out result))
                return result;
            throw new InvalidOperationException(ExceptionMessages.NoMatchingItemInList);
        }

        /// <summary>
        /// Effectue une recherche binaire sur une liste triée pour trouver un élément selon
        /// la valeur d'une de ses propriétés. La liste doit être triée selon cette propriété.
        /// Si aucun élément correspondant n'est trouvé, une valeur par défaut est renvoyée.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la collection</typeparam>
        /// <typeparam name="TKey">Type de la clé de recherche</typeparam>
        /// <param name="list">Liste dans laquelle rechercher l'élément</param>
        /// <param name="keySelector">Fonction permettant d'obtenir la clé de recherche</param>
        /// <param name="key">Valeur de la clé recherchée</param>
        /// <returns>Le premier élément correspondant, s'il existe. Sinon, la valeur par défaut du type T.</returns>
        public static T BinarySearchOrDefault<T, TKey>(
            [NotNull] this IList<T> list,
            [NotNull] Func<T, TKey> keySelector,
            TKey key)
            where TKey : IComparable<TKey>
        {
            return list.BinarySearchOrDefault(keySelector, key, default(T));
        }

        /// <summary>
        /// Effectue une recherche binaire sur une liste triée pour trouver un élément selon
        /// la valeur d'une de ses propriétés. La liste doit être triée selon cette propriété.
        /// Si aucun élément correspondant n'est trouvé, la valeur par défaut spécifiée est renvoyée.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la collection</typeparam>
        /// <typeparam name="TKey">Type de la clé de recherche</typeparam>
        /// <param name="list">Liste dans laquelle rechercher l'élément</param>
        /// <param name="keySelector">Fonction permettant d'obtenir la clé de recherche</param>
        /// <param name="key">Valeur de la clé recherchée</param>
        /// <param name="defaultValue">La valeur par défaut à renvoyer si aucun élément correspondant n'est trouvé</param>
        /// <returns>Le premier élément correspondant, s'il existe. Sinon, la valeur par défaut spécifiée.</returns>
        public static T BinarySearchOrDefault<T, TKey>(
            [NotNull] this IList<T> list,
            [NotNull] Func<T, TKey> keySelector,
            TKey key,
            T defaultValue)
            where TKey : IComparable<TKey>
        {
            T result;
            if (list.TryBinarySearch(keySelector, key, out result))
                return result;
            return defaultValue;
        }

        /// <summary>
        /// Effectue une recherche binaire sur une liste triée pour tenter de trouver un élément
        /// selon la valeur d'une de ses propriétés. La liste doit être triée selon cette propriété.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la collection</typeparam>
        /// <typeparam name="TKey">Type de la clé de recherche</typeparam>
        /// <param name="list">Liste dans laquelle rechercher l'élément</param>
        /// <param name="keySelector">Fonction permettant d'obtenir la clé de recherche</param>
        /// <param name="key">Valeur de la clé recherchée</param>
        /// <param name="result">Paramètre de sortie qui prend la valeur du premier élément trouvé.</param>
        /// <returns>true si un élément correspondant est trouvé. Sinon, false.</returns>
        public static bool TryBinarySearch<T, TKey>(
            [NotNull] this IList<T> list,
            [NotNull] Func<T, TKey> keySelector,
            TKey key,
            out T result)
            where TKey : IComparable<TKey>
        {
            list.CheckArgumentNull("list");
            keySelector.CheckArgumentNull("keySelector");

            result = default(T);
            int min = 0;
            int max = list.Count;
            while (min < max)
            {
                int mid = (max + min) / 2;
                T midItem = list[mid];
                TKey midKey = keySelector(midItem);
                int comp = midKey.CompareTo(key);
                if (comp < 0)
                {
                    min = mid + 1;
                }
                else if (comp > 0)
                {
                    max = mid - 1;
                }
                else
                {
                    result = midItem;
                    return true;
                }
            }
            if (min == max &&
                keySelector(list[min]).CompareTo(key) == 0)
            {
                result = list[min];
                return true;
            }
            return false;
        }

        #endregion

        #region QuickSort

        /// <summary>
        /// Trie la liste en utilisant l'algorithme Quicksort
        /// </summary>
        /// <typeparam name="T">Type des éléments de la liste</typeparam>
        /// <param name="list">Liste à trier</param>
        public static void QuickSort<T>([NotNull] this IList<T> list)
        {
            Comparison<T> comparison = Comparer<T>.Default.ToComparison();
            QuickSort(list, comparison);
        }

        /// <summary>
        /// Trie la liste selon la clé spécifiée en utilisant l'algorithme Quicksort
        /// </summary>
        /// <typeparam name="T">Type des éléments de la liste</typeparam>
        /// <typeparam name="TKey">Type de la clé de tri</typeparam>
        /// <param name="list">Liste à trier</param>
        /// <param name="keySelector">Fonction qui renvoie la clé de tri</param>
        public static void QuickSortBy<T, TKey>(
            [NotNull] this IList<T> list,
            [NotNull] Func<T, TKey> keySelector)
        {
            keySelector.CheckArgumentNull("keySelector");

            Comparison<TKey> keyComparison = Comparer<TKey>.Default.ToComparison();
            Comparison<T> comparison = (a, b) => keyComparison(keySelector(a), keySelector(b));
            QuickSort(list, comparison);
        }

        /// <summary>
        /// Trie la liste en utilisant l'algorithme Quicksort, avec le comparateur spécifié
        /// </summary>
        /// <typeparam name="T">Type des éléments de la liste</typeparam>
        /// <param name="list">Liste à trier</param>
        /// <param name="comparer">Comparateur à utiliser</param>
        public static void QuickSort<T>(
            [NotNull] this IList<T> list,
            [NotNull] IComparer<T> comparer)
        {
            comparer.CheckArgumentNull("comparer");

            QuickSort(list, comparer.ToComparison());
        }

        /// <summary>
        /// Trie la liste en utilisant l'algorithme Quicksort, avec la fonction de comparaison spécifiée
        /// </summary>
        /// <typeparam name="T">Type des éléments de la liste</typeparam>
        /// <param name="list">Liste à trier</param>
        /// <param name="comparison">Fonction de comparaison à utiliser</param>
        public static void QuickSort<T>(
            [NotNull] this IList<T> list,
            [NotNull] Comparison<T> comparison)
        {
            list.CheckArgumentNull("list");
            QuickSort(list, 0, list.Count - 1, comparison);
        }

        private static void QuickSort<T>(IList<T> list, int left, int right, Comparison<T> comparison)
        {
            if (right > left)
            {
                int pivot = left;
                QuickSortPartition(list, left, right, ref pivot, comparison);
                QuickSort(list, left, pivot - 1, comparison);
                QuickSort(list, pivot + 1, right, comparison);
            }
        }

        private static void QuickSortPartition<T>(IList<T> list, int left, int right, ref int pivot, Comparison<T> comparison)
        {
            T pivotValue = list[pivot];
            list.Swap(pivot, right);
            int tmpIndex = left;
            for (int i = left; i < right; i++)
            {
                if (comparison(list[i], pivotValue) <= 0)
                {
                    list.Swap(i, tmpIndex);
                    tmpIndex++;
                }
            }
            list.Swap(tmpIndex, right);
            pivot = tmpIndex;
        }

        #endregion

        #region AddRange

        /// <summary>
        /// Ajoute plusieurs éléments à une collection
        /// </summary>
        /// <typeparam name="T">Type des éléments de la collection</typeparam>
        /// <param name="collection">Collection à laquelle ajouter des éléments</param>
        /// <param name="items">Eléments à ajouter</param>
        public static void AddRange<T>(
            [NotNull] this ICollection<T> collection,
            [NotNull] IEnumerable<T> items)
        {
            collection.CheckArgumentNull("collection");
            items.CheckArgumentNull("items");
            foreach (var item in items)
            {
                collection.Add(item);
            }
        }

        #endregion

        #region RemoveRange

        /// <summary>
        /// Retire d'une liste le nombre d'éléments spécifié à partir de la position spécifiée
        /// </summary>
        /// <typeparam name="T">Type des éléments de la liste</typeparam>
        /// <param name="list">Liste de laquelle on retire des éléments</param>
        /// <param name="index">Position à partir de laquelle on retire des éléments</param>
        /// <param name="count">Nombre d'éléments à retirer</param>
        public static void RemoveRange<T>(
            [NotNull] this IList<T> list,
            int index,
            int count)
        {
            list.CheckArgumentNull("list");
            index.CheckArgumentOutOfRange("index", 0, list.Count - 1);
            count.CheckArgumentOutOfRange("count", 0, list.Count - index);
            for (int i = 0; i < count; i++)
            {
                list.RemoveAt(index);
            }
        }

        #endregion

        #region InsertRange

        /// <summary>
        /// Insère les éléments spécifiés dans une liste à partir de la position spécifiée
        /// </summary>
        /// <typeparam name="T">Type des éléments de la liste</typeparam>
        /// <param name="list">Liste dans laquelle on insère les éléments</param>
        /// <param name="index">Position à partir de laquelle insérer les éléments</param>
        /// <param name="items">Éléments à insérer</param>
        public static void InsertRange<T>(
            [NotNull] this IList<T> list,
            int index,
            [NotNull] IEnumerable<T> items)
        {
            list.CheckArgumentNull("list");
            index.CheckArgumentOutOfRange("index", 0, list.Count);
            items.CheckArgumentNull("items");
            foreach (var item in items)
            {
                list.Insert(index++, item);
            }
        }

        #endregion

        #region RemoveAll

        /// <summary>
        /// Retire d'une collection tous les éléments qui vérifient le prédicat spécifié
        /// </summary>
        /// <typeparam name="T">Type des éléments de la liste</typeparam>
        /// <param name="collection">Collection de laquelle on retire des éléments</param>
        /// <param name="predicate">Prédicat qui indique si un élément doit être retiré</param>
        /// <returns>Le nombre d'éléments retirés</returns>
        public static int RemoveAll<T>(
            [NotNull] this ICollection<T> collection,
            [NotNull] Func<T, bool> predicate)
        {
            collection.CheckArgumentNull("collection");
            predicate.CheckArgumentNull("predicate");
            var toRemove = collection.Where(predicate).ToList();
            foreach (var item in toRemove)
            {
                collection.Remove(item);
            }
            return toRemove.Count;
        }

        #endregion

        #region Shuffle

        /// <summary>
        /// Mélange une liste.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="list">La liste à mélanger</param>
        /// <remarks>Cette méthode utilise l'algorithme de Fisher–Yates (http://en.wikipedia.org/wiki/Fisher-Yates_shuffle)
        /// </remarks>
        public static void Shuffle<T>([NotNull] this IList<T> list)
        {
            list.Shuffle(new Random());
        }

        /// <summary>
        /// Mélange une liste en spécifiant le générateur de nombres aléatoires à utiliser.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="list">La liste à mélanger</param>
        /// <param name="rnd">Le générateur de nombres aléatoires à utiliser</param>
        /// <remarks>Cette méthode utilise l'algorithme de Fisher–Yates (http://en.wikipedia.org/wiki/Fisher-Yates_shuffle)
        /// </remarks>
        public static void Shuffle<T>(
            [NotNull] this IList<T> list,
            [NotNull] Random rnd)
        {
            list.CheckArgumentNull("list");
            rnd.CheckArgumentNull("rnd");
            for (int i = list.Count - 1; i > 0; i--)
            {
                int swapIndex = rnd.Next(i + 1);
                list.Swap(i, swapIndex);
            }
        }

        #endregion

        #region Swap

        /// <summary>
        /// Permute deux éléments d'une liste
        /// </summary>
        /// <typeparam name="T">Type des éléments de la liste</typeparam>
        /// <param name="list">La liste contenant les éléments à permuter</param>
        /// <param name="index1">L'index du premier élément</param>
        /// <param name="index2">L'index du second élément</param>
        public static void Swap<T>(
            [NotNull] this IList<T> list,
            int index1,
            int index2)
        {
            list.CheckArgumentNull("list");
            index1.CheckArgumentOutOfRange("index1", 0, list.Count - 1);
            index1.CheckArgumentOutOfRange("index2", 0, list.Count - 1);

            T tmp = list[index1];
            list[index1] = list[index2];
            list[index2] = tmp;
        }

        #endregion

        #region ToHashSet

        /// <summary>
        /// Crée un <see cref="HashSet{T}"/> à partir d'un <see cref="IEnumerable{T}"/> avec le comparateur par défaut.
        /// </summary>
        /// <typeparam name="TSource">Type des éléments de <c>source</c></typeparam>
        /// <param name="source">Séquence à partir de laquelle créer un <see cref="HashSet{T}"/></param>
        /// <returns>Un <see cref="HashSet{T}"/> qui contient les éléments de la séquence d'entrée.</returns>
        public static HashSet<TSource> ToHashSet<TSource>([NotNull] this IEnumerable<TSource> source)
        {
            source.CheckArgumentNull("source");
            return new HashSet<TSource>(source);
        }

        /// <summary>
        /// Crée un <see cref="HashSet{T}"/> à partir d'un <see cref="IEnumerable{T}"/> avec le comparateur spécifié.
        /// </summary>
        /// <typeparam name="TSource">Type des éléments de <c>source</c></typeparam>
        /// <param name="source">Séquence à partir de laquelle créer un <see cref="HashSet{T}"/></param>
        /// <param name="comparer">Comparateur à utiliser pour comparer les éléments.</param>
        /// <returns>Un <see cref="HashSet{T}"/> qui contient les éléments de la séquence d'entrée.</returns>
        public static HashSet<TSource> ToHashSet<TSource>([NotNull] this IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)
        {
            source.CheckArgumentNull("source");
            return new HashSet<TSource>(source, comparer);
        }

        #endregion

        #region ToStack

        /// <summary>
        /// Crée une <see cref="Stack{T}"/> à partir d'un <see cref="IEnumerable{T}"/>.
        /// </summary>
        /// <typeparam name="TSource">Type des éléments de <c>source</c></typeparam>
        /// <param name="source">Séquence à partir de laquelle créer une <see cref="Stack{T}"/></param>
        /// <returns>Une <see cref="Stack{T}"/> qui contient les éléments de la séquence d'entrée.</returns>
        public static Stack<TSource> ToStack<TSource>([NotNull] this IEnumerable<TSource> source)
        {
            source.CheckArgumentNull("source");
            return new Stack<TSource>(source);
        }

        #endregion

        #region ToQueue

        /// <summary>
        /// Crée une <see cref="Queue{T}"/> à partir d'un <see cref="IEnumerable{T}"/>.
        /// </summary>
        /// <typeparam name="TSource">Type des éléments de <c>source</c></typeparam>
        /// <param name="source">Séquence à partir de laquelle créer une <see cref="Queue{T}"/></param>
        /// <returns>Une <see cref="Queue{T}"/> qui contient les éléments de la séquence d'entrée.</returns>
        public static Queue<TSource> ToQueue<TSource>([NotNull] this IEnumerable<TSource> source)
        {
            source.CheckArgumentNull("source");
            return new Queue<TSource>(source);
        }

        #endregion
    }
}