using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Developpez.Dotnet.Threading;
using System.Collections;
using System.Threading;

namespace Developpez.Dotnet.Collections
{
    /// <summary>
    /// Fournit des méthodes d'extension pour les types enumérables
    /// </summary>
    public static class EnumerableExtensions
    {
        #region Divers

        /// <summary>
        /// Indique si une collection est nulle ou vide
        /// </summary>
        /// <param name="collection">La collection à tester</param>
        /// <returns>true si la collection est nulle ou vide, false sinon</returns>
        public static bool IsNullOrEmpty(this ICollection collection)
        {
            return (collection == null || collection.Count == 0);
        }

        /// <summary>
        /// Obtient une version synchronisée de la liste
        /// </summary>
        /// <typeparam name="T">Type générique de la liste</typeparam>
        /// <param name="list">liste</param>
        /// <returns>liste synchronisée</returns>
        public static IList<T> Synchronized<T>(this IList<T> list)
        {
            return new SyncList<T>(list);
        }

        /// <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>(this IList<T> list, int index1, int index2)
        {
            T tmp = list[index1];
            list[index1] = list[index2];
            list[index2] = tmp;
        }

#if !DOTNET4 // La méthode Zip a été ajoutée dans .NET 4.0 et ne sera donc plus nécessaire

        /// <summary>
        /// Fusionne 2 séquences selon la fonction de projection spécifiée, en faisant correspondre
        /// chaque élément de la première séquence à l'élément de même index dans la deuxième séquence.
        /// </summary>
        /// <typeparam name="TFirst">Type des éléments de la première séquence</typeparam>
        /// <typeparam name="TSecond">Type des éléments de la deuxième séquence</typeparam>
        /// <typeparam name="TResult">Type des éléments de la séquence fusionnée</typeparam>
        /// <param name="first">première séquence</param>
        /// <param name="second">deuxième séquence</param>
        /// <param name="selector">fonction de projection pour fusionner des éléments des 2 séquences</param>
        /// <returns>Une séquence d'éléments fusionnée</returns>
        /// <remarks>Si les 2 séquences ne sont pas de même longueur </remarks>
        public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> selector)
        {
            first.CheckArgumentNull("first");
            second.CheckArgumentNull("second");
            selector.CheckArgumentNull("selector");

            return first.ZipIterator(second, selector);
        }

        private static IEnumerable<TResult> ZipIterator<TFirst, TSecond, TResult>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, Func<TFirst, TSecond, TResult> selector)
        {
            using (var enum1 = first.GetEnumerator())
            using (var enum2 = second.GetEnumerator())
            {
                while (enum1.MoveNext() && enum2.MoveNext())
                {
                    yield return selector(enum1.Current, enum2.Current);
                }
            }
        }

#endif

        #endregion

        #region FormatAll

        /// <summary>
        /// Renvoie une chaine contenant chaque élément de l'énumération formaté avec
        /// le format spécifié
        /// </summary>
        /// <param name="enumerable">L'énumération à formater</param>
        /// <param name="format">Le format à appliquer à chaque élément, par exemple "x2" ou "{0:x2}"</param>
        /// <param name="separator">Le séparateur à insérer entre chaque élément</param>
        /// <returns>La chaine contenant tous les éléments formatés</returns>
        public static string FormatAll(this IEnumerable enumerable, string format, string separator)
        {
            if (format.IsNullOrEmpty())
            {
                format = "{0}";
            }
            else if (!(format.StartsWith("{0") && format.EndsWith("}")))
            {
                format = "{0:" + format + "}";
            }

            separator = separator ?? String.Empty;
            StringBuilder sb = new StringBuilder();

            foreach (var item in enumerable)
            {
                sb.AppendFormat(format, item);
                sb.Append(separator);
            }

            sb.Remove(sb.Length - separator.Length, separator.Length);
            return sb.ToString();
        }

        /// <summary>
        /// Renvoie une chaine contenant chaque élément de l'énumération formaté avec
        /// le delegate spécifié
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="enumerable">L'énumération à formater</param>
        /// <param name="formatter">Le delegate à appliquer à chaque élément pour le convertir en chaine de caractères</param>
        /// <param name="separator">Le séparateur à insérer entre chaque élément</param>
        /// <returns>La chaine contenant tous les éléments formatés</returns>
        public static string FormatAll<T>(this IEnumerable<T> enumerable, Func<T, string> formatter, string separator)
        {
            if (formatter == null)
                return enumerable.FormatAll((string)null, separator);

            separator = separator ?? String.Empty;
            StringBuilder sb = new StringBuilder();

            foreach (var item in enumerable)
            {
                sb.Append(formatter(item));
                sb.Append(separator);
            }

            sb.Remove(sb.Length - separator.Length, separator.Length);
            return sb.ToString();
        }

        #endregion

        #region Append, Prepend

        /// <summary>
        /// Ajoute un élément à la suite de la séquence spécifiée
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'origine</param>
        /// <param name="item">Elément à ajouter</param>
        /// <returns>La séquence d'origine suivie de l'élément spécifiée</returns>
        public static IEnumerable<T> Append<T>(this IEnumerable<T> source, T item)
        {
            return source.Concat(new[] { item });
        }

        /// <summary>
        /// Insère un élément au début de la séquence spécifiée
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'origine</param>
        /// <param name="item">Elément à insérer</param>
        /// <returns>La séquence d'origine précédée de l'élément spécifiée</returns>
        public static IEnumerable<T> Prepend<T>(this IEnumerable<T> source, T item)
        {
            return new[] { item }.Concat(source);
        }

        #endregion

        #region ForEachParallel

        /// <summary>
        /// Exécute la méthode callback de manière parallele sur tous les éléments
        /// de la collection
        /// </summary>
        /// <typeparam name="T">Type de collection</typeparam>
        /// <param name="enumerable">Séquence d'éléments sur laquelle effectuer une action en parallèle</param>
        /// <param name="callback">Méthode à rappeller sur chacun des éléments</param>
        public static void ForEachParallel<T>(this IEnumerable<T> enumerable, ThreadedWorker<T>.CallBackMethod callback)
        {
            enumerable.ForEachParallel(callback, true);
        }

        /// <summary>
        /// Exécute la méthode callback de manière parallele sur tous les éléments
        /// de la collection
        /// </summary>
        /// <typeparam name="T">Type de collection</typeparam>
        /// <param name="enumerable">Séquence d'éléments sur laquelle effectuer une action en parallèle</param>
        /// <param name="callback">Méthode à rappeller sur chacun des éléments</param>
        /// <param name="waitForCompletion">True si l'opération doit être synchrone (attente de la fin de l'opération sur tous les éléments)
        /// ou non (aucune attente, l'exécution se poursuit)</param>
        public static void ForEachParallel<T>(this IEnumerable<T> enumerable, ThreadedWorker<T>.CallBackMethod callback, bool waitForCompletion)
        {
            enumerable.ForEachParallel(callback, waitForCompletion, -1);
        }

        /// <summary>
        /// Exécute la méthode callback de manière parallele sur tous les éléments
        /// de la collection
        /// </summary>
        /// <typeparam name="T">Type de collection</typeparam>
        /// <param name="enumerable">Séquence d'éléments sur laquelle effectuer une action en parallèle</param>
        /// <param name="callback">Méthode à rappeller sur chacun des éléments</param>
        /// <param name="waitForCompletion">True si l'opération doit être synchrone (attente de la fin de l'opération sur tous les éléments)
        /// ou non (aucune attente, l'exécution se poursuit)</param>
        /// <param name="maxWorkerThreads">Nombre maximum de thread de travail dédié à cette tâche. Toute valeure inférieure à 1 est ignorée</param>
        public static void ForEachParallel<T>(this IEnumerable<T> enumerable, ThreadedWorker<T>.CallBackMethod callback, bool waitForCompletion, int maxWorkerThreads)
        {
            callback.CheckArgumentNull("callback");

            using (ThreadedWorker<T> worker = new ThreadedWorker<T>())
            {
                if (maxWorkerThreads > 0)
                    worker.MaxThreadCount = maxWorkerThreads;
                worker.ForEach(enumerable, callback, waitForCompletion);
            }
        }

        /// <summary>
        /// Exécute la méthode callback de manière parallele sur tous les éléments
        /// de la collection
        /// </summary>
        /// <param name="enumerable">Séquence d'éléments sur laquelle effectuer une action en parallèle</param>
        /// <param name="callback">Méthode à rappeller sur chacun des éléments</param>
        public static void ForEachParallel(this IEnumerable enumerable, ThreadedWorker<object>.CallBackMethod callback)
        {
            enumerable.ForEachParallel(callback, true);
        }

        /// <summary>
        /// Exécute la méthode callback de manière parallele sur tous les éléments
        /// de la collection
        /// </summary>
        /// <param name="enumerable">Séquence d'éléments sur laquelle effectuer une action en parallèle</param>
        /// <param name="callback">Méthode à rappeller sur chacun des éléments</param>
        /// <param name="waitForCompletion">True si l'opération doit être synchrone (attente de la fin de l'opération sur tous les éléments)
        /// ou non (aucune attente, l'exécution se poursuit)</param>
        public static void ForEachParallel(this IEnumerable enumerable, ThreadedWorker<object>.CallBackMethod callback, bool waitForCompletion)
        {
            enumerable.ForEachParallel(callback, waitForCompletion, -1);
        }

        /// <summary>
        /// Exécute la méthode callback de manière parallele sur tous les éléments
        /// de la collection
        /// </summary>
        /// <param name="enumerable">Séquence d'éléments sur laquelle effectuer une action en parallèle</param>
        /// <param name="callback">Méthode à rappeller sur chacun des éléments</param>
        /// <param name="waitForCompletion">True si l'opération doit être synchrone (attente de la fin de l'opération sur tous les éléments)
        /// ou non (aucune attente, l'exécution se poursuit)</param>
        /// <param name="maxWorkerThreads">Nombre maximum de thread de travail dédié à cette tâche. Toute valeure inférieure à 1 est ignorée</param>
        public static void ForEachParallel(this IEnumerable enumerable, ThreadedWorker<object>.CallBackMethod callback, bool waitForCompletion, int maxWorkerThreads)
        {
            callback.CheckArgumentNull("callback");

            using (ThreadedWorker<object> worker = new ThreadedWorker<object>())
            {
                if (maxWorkerThreads > 0)
                    worker.MaxThreadCount = maxWorkerThreads;
                worker.ForEach(enumerable.Cast<object>(), callback, waitForCompletion);
            }
        }

        #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>(this IList<T> list)
        {
            Random rnd = new Random();
            for (int i = list.Count - 1; i > 0; i--)
            {
                int swapIndex = rnd.Next(i + 1);
                list.Swap(i, swapIndex);
            }
        }

        #endregion

        #region BinarySearch et variantes

        /// <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>(this IList<T> list, 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>(this IList<T> list, 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>(this IList<T> list, 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>(this IList<T> list, Func<T, TKey> keySelector, TKey key, out T result)
            where TKey : IComparable<TKey>
        {
            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 Conversions de et vers des chaînes CSV

        /// <summary>
        /// Convertit une liste en une chaîne CSV avec le séparateur spécifié
        /// </summary>
        /// <param name="list">Liste à convertir</param>
        /// <param name="separator">Séparateur à utiliser</param>
        /// <returns>Une chaine CSV représentant les éléments de la liste</returns>
        public static string ToCsvString(this IEnumerable list, string separator)
        {
            StringBuilder sb = new StringBuilder();
            foreach (object o in list)
            {
                if (sb.Length > 0)
                    sb.Append(separator);
                sb.Append(o);
            }
            return sb.ToString();
        }

        /// <summary>
        /// Convertit une chaine CSV en une liste d'objets du type spécifié
        /// </summary>
        /// <typeparam name="T">Type des éléments de la liste</typeparam>
        /// <param name="source">Chaîne CSV à convertir</param>
        /// <param name="separator">Séparateur à utiliser</param>
        /// <returns>Une liste contenant les éléments de la chaîne CSV</returns>
        public static IEnumerable<T> ListFromCsv<T>(this string source, string separator)
        {
            List<T> lst = new List<T>();

            string[] sItems = source.Split(new string[] { separator }, StringSplitOptions.None);

            foreach (string sItem in sItems)
            {
                T item;
                if (string.IsNullOrEmpty(sItem))
                {
                    item = default(T);
                }
                else
                {
                    item = (T)Convert.ChangeType(sItem, typeof(T));
                }
                lst.Add(item);
            }
            return lst;
        }

        #endregion

        #region IsOrdered et variantes

        /// <summary>
        /// Vérifie que la liste est triée, en utilisant le comparateur spécifié
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la liste</typeparam>
        /// <param name="list">La liste à vérifier</param>
        /// <param name="comparer">Le comparateur à utiliser</param>
        /// <returns>true si la liste est triée, false sinon</returns>
        public static bool IsOrdered<T>(this IEnumerable<T> list, IComparer<T> comparer)
        {
            return list.IsOrdered(comparer.ToComparison());
        }

        /// <summary>
        /// Vérifie que la liste est triée, en utilisant la comparaison spécifiée
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la liste</typeparam>
        /// <param name="list">La liste à vérifier</param>
        /// <param name="comparison">La comparaison à utiliser</param>
        /// <returns>true si la liste est triée, false sinon</returns>
        public static bool IsOrdered<T>(this IEnumerable<T> list, Comparison<T> comparison)
        {
            bool isFirstPass = true;
            T previous = default(T);
            foreach (T item in list)
            {
                if (!isFirstPass)
                {
                    if (comparison(previous, item) > 0)
                        return false;
                }
                isFirstPass = false;
                previous = item;
            }
            return true;
        }

        /// <summary>
        /// Vérifie que la liste est triée, en utilisant le comparateur par défaut
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la liste</typeparam>
        /// <param name="list">La liste à vérifier</param>
        /// <returns>true si la liste est triée, false sinon</returns>
        public static bool IsOrdered<T>(this IEnumerable<T> list)
        {
            return list.IsOrdered(Comparer<T>.Default);
        }

        /// <summary>
        /// Vérifie que la liste est triée en ordre descendant, en utilisant le comparateur spécifié
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la liste</typeparam>
        /// <param name="list">La liste à vérifier</param>
        /// <param name="comparer">Le comparateur à utiliser</param>
        /// <returns>true si la liste est triée, false sinon</returns>
        public static bool IsOrderedDescending<T>(this IEnumerable<T> list, IComparer<T> comparer)
        {
            return list.IsOrdered(comparer.Reverse());
        }

        /// <summary>
        /// Vérifie que la liste est triée en ordre descendant, en utilisant le comparateur par défaut
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la liste</typeparam>
        /// <param name="list">La liste à vérifier</param>
        /// <returns>true si la liste est triée, false sinon</returns>
        public static bool IsOrderedDescending<T>(this IEnumerable<T> list)
        {
            return list.IsOrdered(Comparer<T>.Default.Reverse());
        }

        /// <summary>
        /// Vérifie que la liste est triée selon la clé de tri spécifiée, en utilisant le comparateur spécifié
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la liste</typeparam>
        /// <typeparam name="TKey">Le type de la clé de tri</typeparam>
        /// <param name="list">La liste à vérifier</param>
        /// <param name="comparer">Le comparateur à utiliser</param>
        /// <param name="keySelector">Une fonction pour extraire la clé de tri de l'élément</param>
        /// <returns>true si la liste est triée selon le critère spécifié, false sinon</returns>
        public static bool IsOrderedBy<T, TKey>(this IEnumerable<T> list, Func<T, TKey> keySelector, IComparer<TKey> comparer)
        {
            return list.Select(keySelector).IsOrdered(comparer);
        }

        /// <summary>
        /// Vérifie que la liste est triée selon la clé de tri spécifiée, en utilisant le comparateur par défaut
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la liste</typeparam>
        /// <typeparam name="TKey">Le type de la clé de tri</typeparam>
        /// <param name="list">La liste à vérifier</param>
        /// <param name="keySelector">Une fonction pour extraire la clé de tri de l'élément</param>
        /// <returns>true si la liste est triée selon le critère spécifié, false sinon</returns>
        public static bool IsOrderedBy<T, TKey>(this IEnumerable<T> list, Func<T, TKey> keySelector)
        {
            return list.IsOrderedBy(keySelector, Comparer<TKey>.Default);
        }

        /// <summary>
        /// Vérifie que la liste est triée en ordre descendant selon la clé de tri spécifiée, en utilisant le comparateur spécifié
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la liste</typeparam>
        /// <typeparam name="TKey">Le type de la clé de tri</typeparam>
        /// <param name="list">La liste à vérifier</param>
        /// <param name="comparer">Le comparateur à utiliser</param>
        /// <param name="keySelector">Une fonction pour extraire la clé de tri de l'élément</param>
        /// <returns>true si la liste est triée selon le critère spécifié, false sinon</returns>
        public static bool IsOrderedByDescending<T, TKey>(this IEnumerable<T> list, Func<T, TKey> keySelector, IComparer<TKey> comparer)
        {
            return list.IsOrderedBy(keySelector, comparer.Reverse());
        }

        /// <summary>
        /// Vérifie que la liste est triée en ordre descendant selon la clé de tri spécifiée, en utilisant le comparateur par défaut
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la liste</typeparam>
        /// <typeparam name="TKey">Le type de la clé de tri</typeparam>
        /// <param name="list">La liste à vérifier</param>
        /// <param name="keySelector">Une fonction pour extraire la clé de tri de l'élément</param>
        /// <returns>true si la liste est triée selon le critère spécifié, false sinon</returns>
        public static bool IsOrderedByDescending<T, TKey>(this IEnumerable<T> list, Func<T, TKey> keySelector)
        {
            return list.IsOrderedBy(keySelector, Comparer<TKey>.Default.Reverse());
        }

        #endregion

        #region SelectAggregate

        /// <summary>
        /// Applique une fonction d'accumulation sur une séquence, en renvoyant le résultat
        /// de chaque étape de l'accumulation.
        /// </summary>
        /// <typeparam name="TSource">Type des éléments de <c>source</c></typeparam>
        /// <typeparam name="TAccumulate">Type de la valeur d'accumulation</typeparam>
        /// <param name="source">Séquence sur laquelle appliquer l'accumulation</param>
        /// <param name="seed">Valeur d'accumulation initiale</param>
        /// <param name="func">Fonction d'accumulation à appeler sur chaque élément</param>
        /// <returns>Séquence des valeurs d'accumulation à chaque étape.</returns>
        /// <remarks>Cette méthode est similaire à Enumerable.Aggregate, mais cette dernière ne renvoie que le résultat
        /// final, alors que SelectAggregate renvoie le résultat de chaque étape.</remarks>
        public static IEnumerable<TAccumulate> SelectAggregate<TSource, TAccumulate>(
            this IEnumerable<TSource> source,
            TAccumulate seed,
            Func<TAccumulate, TSource, TAccumulate> func)
        {
            source.CheckArgumentNull("source");
            func.CheckArgumentNull("func");
            return source.SelectAggregateIterator(seed, func);
        }

        private static IEnumerable<TAccumulate> SelectAggregateIterator<TSource, TAccumulate>(
            this IEnumerable<TSource> source,
            TAccumulate seed,
            Func<TAccumulate, TSource, TAccumulate> func)
        {
            TAccumulate previous = seed;
            foreach (var item in source)
            {
                TAccumulate result = func(previous, item);
                previous = result;
                yield return result;
            }
        }

        /// <summary>
        /// Applique une fonction d'accumulation sur une séquence, en renvoyant le résultat
        /// de chaque étape de l'accumulation.
        /// </summary>
        /// <typeparam name="TSource">Type des éléments de <c>source</c></typeparam>
        /// <typeparam name="TAccumulate">Type de la valeur d'accumulation</typeparam>
        /// <param name="source">Séquence sur laquelle appliquer l'accumulation</param>
        /// <param name="func">Fonction d'accumulation à appeler sur chaque élément</param>
        /// <returns>Séquence des valeurs d'accumulation à chaque étape.</returns>
        /// <remarks>Cette méthode est similaire à Enumerable.Aggregate, mais cette dernière ne renvoie que le résultat
        /// final, alors que SelectAggregate renvoie le résultat de chaque étape.</remarks>
        public static IEnumerable<TAccumulate> SelectAggregate<TSource, TAccumulate>(
            this IEnumerable<TSource> source,
            Func<TAccumulate, TSource, TAccumulate> func)
        {
            return source.SelectAggregate(default(TAccumulate), func);
        }

        /// <summary>
        /// Applique une fonction d'accumulation sur une séquence, en renvoyant le résultat
        /// de chaque étape de l'accumulation. La fonction d'accumulation prend en paramètre
        /// les 2 valeurs d'accumulation précédentes.
        /// </summary>
        /// <typeparam name="TSource">Type des éléments de <c>source</c></typeparam>
        /// <typeparam name="TAccumulate">Type de la valeur d'accumulation</typeparam>
        /// <param name="source">Séquence sur laquelle appliquer l'accumulation</param>
        /// <param name="seed1">Valeur d'accumulation initiale (itération -1)</param>
        /// <param name="seed2">Valeur d'accumulation initiale (itération -2)</param>
        /// <param name="func">Fonction d'accumulation à appeler sur chaque élément</param>
        /// <returns>Séquence des valeurs d'accumulation à chaque étape.</returns>
        public static IEnumerable<TAccumulate> SelectAggregate<TSource, TAccumulate>(
            this IEnumerable<TSource> source,
            TAccumulate seed1,
            TAccumulate seed2,
            Func<TAccumulate, TAccumulate, TSource, TAccumulate> func)
        {
            source.CheckArgumentNull("source");
            func.CheckArgumentNull("func");
            return source.SelectAggregateIterator(seed1, seed2, func);
        }
        
        private static IEnumerable<TAccumulate> SelectAggregateIterator<TSource, TAccumulate>(
            this IEnumerable<TSource> source,
            TAccumulate seed1,
            TAccumulate seed2,
            Func<TAccumulate, TAccumulate, TSource, TAccumulate> func)
        {
            TAccumulate previous1 = seed1;
            TAccumulate previous2 = seed2;
            foreach (var item in source)
            {
                TAccumulate result = func(previous1, previous2, item);
                previous2 = previous1;
                previous1 = result;
                yield return result;
            }
        }

        /// <summary>
        /// Applique une fonction d'accumulation sur une séquence, en renvoyant le résultat
        /// de chaque étape de l'accumulation. La fonction d'accumulation prend en paramètre
        /// les 2 valeurs d'accumulation précédentes.
        /// </summary>
        /// <typeparam name="TSource">Type des éléments de <c>source</c></typeparam>
        /// <typeparam name="TAccumulate">Type de la valeur d'accumulation</typeparam>
        /// <param name="source">Séquence sur laquelle appliquer l'accumulation</param>
        /// <param name="func">Fonction d'accumulation à appeler sur chaque élément</param>
        /// <returns>Séquence des valeurs d'accumulation à chaque étape.</returns>
        public static IEnumerable<TAccumulate> SelectAggregate<TSource, TAccumulate>(
            this IEnumerable<TSource> source,
            Func<TAccumulate, TAccumulate, TSource, TAccumulate> func)
        {
            return source.SelectAggregate(default(TAccumulate), default(TAccumulate), func);
        }

        #endregion

        #region FirstOrDefault, LastOrDefault, ElementAtOrDefault, SingleOrDefault

        /// <summary>
        /// Retourne le premier élément d'une séquence, ou la valeur par défaut spécifiée si la séquence ne contient aucun élément.
        /// </summary>
        /// <typeparam name="T">Type des éléments de source</typeparam>
        /// <param name="source">Séquence à partir de laquelle retourner le premier élément</param>
        /// <param name="defaultValue">La valeur par défaut à renvoyer si la séquence est vide</param>
        /// <returns>Le premier élément de source s'il existe, sinon la valeur par défaut spécifiée</returns>
        public static T FirstOrDefault<T>(this IEnumerable<T> source, T defaultValue)
        {
            return source.DefaultIfEmpty(defaultValue).First();
        }

        /// <summary>
        /// Retourne le premier élément de la séquence à satisfaire à une condition, ou la valeur par défaut spécifiée
        /// si aucun élément correspondant n'est trouvé.
        /// </summary>
        /// <typeparam name="T">Type des éléments de source</typeparam>
        /// <param name="source">Séquence à partir de laquelle retourner un élément</param>
        /// <param name="predicate">Condition à vérifier</param>
        /// <param name="defaultValue">La valeur par défaut à renvoyer si aucun élément ne satisfait la condition</param>
        /// <returns>Le premier élément de source à satisfaire la condition, ou la valeur par défaut spécifiée si aucun
        /// élément ne satisfait la condition</returns>
        public static T FirstOrDefault<T>(this IEnumerable<T> source, Func<T, bool> predicate, T defaultValue)
        {
            return source.Where(predicate).FirstOrDefault(defaultValue);
        }

        /// <summary>
        /// Retourne le dernier élément d'une séquence, ou la valeur par défaut spécifiée si la séquence ne contient aucun élément.
        /// </summary>
        /// <typeparam name="T">Type des éléments de source</typeparam>
        /// <param name="source">Séquence à partir de laquelle retourner le dernier élément</param>
        /// <param name="defaultValue">La valeur par défaut à renvoyer si la séquence est vide</param>
        /// <returns>Le dernier élément de source s'il existe, sinon la valeur par défaut spécifiée</returns>
        public static T LastOrDefault<T>(this IEnumerable<T> source, T defaultValue)
        {
            return source.DefaultIfEmpty(defaultValue).Last();
        }

        /// <summary>
        /// Retourne le dernier élément de la séquence à satisfaire à une condition, ou la valeur par défaut spécifiée
        /// si aucun élément correspondant n'est trouvé.
        /// </summary>
        /// <typeparam name="T">Type des éléments de source</typeparam>
        /// <param name="source">Séquence à partir de laquelle retourner un élément</param>
        /// <param name="predicate">Condition à vérifier</param>
        /// <param name="defaultValue">La valeur par défaut à renvoyer si aucun élément ne satisfait la condition</param>
        /// <returns>Le dernier élément de source à satisfaire la condition, ou la valeur par défaut spécifiée si aucun
        /// élément ne satisfait la condition</returns>
        public static T LastOrDefault<T>(this IEnumerable<T> source, Func<T, bool> predicate, T defaultValue)
        {
            return source.Where(predicate).LastOrDefault(defaultValue);
        }

        /// <summary>
        /// Retourne l'élément situé à un index spécifié dans une séquence, ou la valeur par défaut spécifiée si l'index est hors limites.
        /// </summary>
        /// <typeparam name="T">Type des éléments de source</typeparam>
        /// <param name="source">Séquence à partir de laquelle retourner un élément</param>
        /// <param name="index">Index de l'élément à récupérer</param>
        /// <param name="defaultValue">Valeur par défaut à renvoyer si l'index est hors-limite</param>
        /// <returns>L'élément à l'index spécifié s'il existe ; sinon, la valeur par défaut spécifiée.</returns>
        public static T ElementAtOrDefault<T>(this IEnumerable<T> source, int index, T defaultValue)
        {
            if (index < 0)
                throw new ArgumentOutOfRangeException("index");

            return source.Skip(index).DefaultIfEmpty(defaultValue).First();
        }

        /// <summary>
        /// Retourne l'unique élément d'une séquence, ou la valeur par défaut spécifiée si la séquence n'a aucun élément.
        /// Lève une exception si la séquence contient plus d'un élément
        /// </summary>
        /// <typeparam name="T">Type des éléments de source</typeparam>
        /// <param name="source">Séquence à partir de laquelle retourner un élément</param>
        /// <param name="defaultValue">Valeur par défaut à retourner si la séquence est vide</param>
        /// <returns>L'unique élément de la séquence, ou la valeur par défaut spécifiée si la séquence est vide</returns>
        public static T SingleOrDefault<T>(this IEnumerable<T> source, T defaultValue)
        {
            int i = 0;
            T value = defaultValue;
            foreach (var item in source)
            {
                if (i == 0)
                {
                    value = item;
                }
                else
                {
                    throw new InvalidOperationException(ExceptionMessages.InputSequenceHasMoreThanOneElement);
                }
                i++;
            }
            return value;
        }

        /// <summary>
        /// Retourne l'unique élément d'une séquence qui satisfait une condition, ou la valeur par défaut
        /// spécifiée si aucun élément ne satisfait la condition.
        /// Lève une exception si plusieurs éléments satisfont la condition.
        /// </summary>
        /// <typeparam name="T">Type des éléments de source</typeparam>
        /// <param name="source">Séquence à partir de laquelle retourner un élément</param>
        /// <param name="predicate">La condition à vérifier</param>
        /// <param name="defaultValue">Valeur par défaut à retourner si aucun élément ne satisfait la condition</param>
        /// <returns>L'unique élément de la séquence, ou la valeur par défaut spécifiée si aucun élément ne satisfait la condition</returns>
        public static T SingleOrDefault<T>(this IEnumerable<T> source, Func<T, bool> predicate, T defaultValue)
        {
            return source.Where(predicate).SingleOrDefault(defaultValue);
        }

        #endregion

        #region WithMax, WithMin

        /// <summary>
        /// Renvoie l'élément de la liste ayant la plus grande valeur pour la fonction spécifiée
        /// </summary>
        /// <typeparam name="T">Type des éléments de la liste</typeparam>
        /// <typeparam name="TValue">Type de retour de la fonction à évaluer</typeparam>
        /// <param name="source">Liste d'éléments</param>
        /// <param name="selector">Fonction évaluée pour chaque élément</param>
        /// <returns>L'élément ayant la plus petite valeur pour la fonction spécifiée</returns>
        public static T WithMax<T, TValue>(this IEnumerable<T> source, Func<T, TValue> selector)
        {
            var max = default(TValue);
            var withMax = default(T);
            bool first = true;
            foreach (var item in source)
            {
                var value = selector(item);
                int compare = Comparer<TValue>.Default.Compare(value, max);

                if (compare > 0 || first)
                {
                    max = value;
                    withMax = item;
                }
                first = false;
            }
            return withMax;
        }

        /// <summary>
        /// Renvoie l'élément de la liste ayant la plus petite valeur pour la fonction spécifiée
        /// </summary>
        /// <typeparam name="T">Type des éléments de la liste</typeparam>
        /// <typeparam name="TValue">Type de retour de la fonction à évaluer</typeparam>
        /// <param name="source">Liste d'éléments</param>
        /// <param name="selector">Fonction évaluée pour chaque élément</param>
        /// <returns>L'élément ayant la plus petite valeur pour la fonction spécifiée</returns>
        public static T WithMin<T, TValue>(this IEnumerable<T> source, Func<T, TValue> selector)
        {
            var min = default(TValue);
            var withMin = default(T);
            bool first = true;
            foreach (var item in source)
            {
                var value = selector(item);
                int compare = Comparer<TValue>.Default.Compare(value, min);

                if (compare < 0 || first)
                {
                    min = value;
                    withMin = item;
                }
                first = false;
            }
            return withMin;
        }

        #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>(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>(this IList<T> list, Func<T, TKey> 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>(this IList<T> list, IComparer<T> 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>(this IList<T> list, Comparison<T> comparison)
        {
            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 AsIndexed, Unindex

        /// <summary>
        /// Associe un index à un élément d'une séquence
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        public class IndexedItem<T>
        {
            internal IndexedItem(int index, T value)
            {
                this.Index = index;
                this.Value = value;
            }

            /// <summary>
            /// Index de l'élément
            /// </summary>
            public int Index { get; private set; }

            /// <summary>
            /// Valeur de l'élément
            /// </summary>
            public T Value { get; private set; }
        }

        /// <summary>
        /// Associe à chaque élément de la séquence son index dans la séquence
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'éléments à indexer</param>
        /// <returns>Une séquence projetée où chaque élément est associé à son index</returns>
        public static IEnumerable<IndexedItem<T>> AsIndexed<T>(this IEnumerable<T> source)
        {
            return source.Select((v, i) => new IndexedItem<T>(i, v));
        }

        /// <summary>
        /// Dissocie chaque élément de la séquence de son index. Cette méthode effectue l'opération inverse de AsIndexed.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'éléments à dissocier de leur index</param>
        /// <returns>Une séquence d'éléments sans leur index</returns>
        public static IEnumerable<T> Unindex<T>(this IEnumerable<IndexedItem<T>> source)
        {
            return source.Select(x => x.Value);
        }

        #endregion

        #region TakeEvery, SkipEvery, GroupEvery

        /// <summary>
        /// Extrait un élément sur <c>frequency</c> à partir de la séquence d'entrée, à partir du premier élément.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'entrée</param>
        /// <param name="frequency">Fréquence des éléments à extraire</param>
        /// <returns>Une séquence contenant un élément sur <c>frequency</c> de la séquence d'entrée</returns>
        public static IEnumerable<T> TakeEvery<T>(this IEnumerable<T> source, int frequency)
        {
            return source.TakeEvery(frequency, 0);
        }

        /// <summary>
        /// Extrait un élément sur <c>frequency</c> à partir de la séquence d'entrée, à partir de la position spécifiée.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'entrée</param>
        /// <param name="frequency">Fréquence des éléments à extraire</param>
        /// <param name="start">Position du premier élément à extraire</param>
        /// <returns>Une séquence contenant un élément sur <c>frequency</c> de la séquence d'entrée à partir de la position spécifiée</returns>
        public static IEnumerable<T> TakeEvery<T>(this IEnumerable<T> source, int frequency, int start)
        {
            if (frequency <= 0)
                throw new ArgumentException("frequency");
            if (start < 0)
                throw new ArgumentException("start");

            return source
                .Skip(start)
                .Where((item, index) => index % frequency == 0);
        }

        /// <summary>
        /// Renvoie les éléments de la séquence d'entrée, en sautant un élément sur <c>frequency</c> à partir de la position spécifiée.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'entrée</param>
        /// <param name="frequency">Fréquence des éléments à sauter</param>
        /// <returns>Une séquence les éléments de la séquence d'entrée, en en sautant un sur <c>frequency</c> à partir de la position spécifiée</returns>
        public static IEnumerable<T> SkipEvery<T>(this IEnumerable<T> source, int frequency)
        {
            return source.SkipEvery(frequency, 0);
        }

        /// <summary>
        /// Renvoie les éléments de la séquence d'entrée, en sautant un élément sur <c>frequency</c> à partir du premier élément.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'entrée</param>
        /// <param name="frequency">Fréquence des éléments à sauter</param>
        /// <param name="start">Position du premier élément à sauter</param>
        /// <returns>Une séquence les éléments de la séquence d'entrée, en en sautant un sur <c>frequency</c> à partir du premier.</returns>
        public static IEnumerable<T> SkipEvery<T>(this IEnumerable<T> source, int frequency, int start)
        {
            if (frequency <= 0)
                throw new ArgumentException("frequency");

            return source
                .Where((item, index) => index < start ? true : (index - start) % frequency != 0);
        }

        /// <summary>
        /// Renvoie les éléments de la séquence d'entrée par groupes de <c>groupLength</c> éléments.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'éléments à grouper</param>
        /// <param name="groupLength">Longueur des groupes</param>
        /// <returns>Une séquence de groupes de <c>groupLength</c> éléments</returns>
        /// <remarks>Si le nombre total d'éléments dans la séquence n'est pas un multiple de <c>groupLength</c>, le dernier groupe renvoyé contiendra moins de <c>groupLength</c> éléments.</remarks>
        public static IEnumerable<IEnumerable<T>> GroupEvery<T>(this IEnumerable<T> source, int groupLength)
        {
            if (groupLength <= 0)
                throw new ArgumentOutOfRangeException("groupLength");

            return source
                    .AsIndexed()
                    .GroupBy(x => x.Index / groupLength)
                    .Select(g => g.Unindex());
        }

        #endregion

    }
}