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

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

        /// <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;
        }

        #endregion

        #region Zip

// Contournement d'un bug dans Resharper: la directive #if entre le commentaire de doc et la
// méthode provoque ces deux avertissements (mais le comportement du compilateur est correct)
#pragma warning disable 1587
#pragma warning disable 1591
        /// <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>
        /// <para>Si les 2 séquences ne sont pas de même longueur, les éléments surnuméraires de la séquence la plus longue sont ignorés.</para>
        /// <note>Cette méthode est absente de la version compilée pour .NET 4, car elle est déjà définie dans le framework 4.0 (Enumerable.Zip)</note>
        /// </remarks>

// La méthode Zip a été ajoutée dans .NET 4.0 et ne sera donc plus nécessaire
// Par contre elle est utilisée en interne et doit donc rester présente
#if DOTNET4
        internal
#else
        public
#endif
        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);
        }
#pragma warning restore 1591
#pragma warning restore 1587


        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);
                }
            }
        }

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

        #endregion

        #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>(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 Conversion from/to CSV strings

        /// <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[] { 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 and related methods

        /// <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;
            var comparer = Comparer<TValue>.Default;
            foreach (var item in source)
            {
                var value = selector(item);
                int compare = comparer.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)
            {
                Index = index;
                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

        #region SkipFirst, SkipLast, SkipAt

        /// <summary>
        /// Renvoie les éléments de la séquence d'entrée en sautant le premier.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'entrée</param>
        /// <returns>La séquence d'entrée sans le premier élément</returns>
        public static IEnumerable<T> SkipFirst<T>(this IEnumerable<T> source)
        {
            source.CheckArgumentNull("source");
            return source.Skip(1);
        }

        /// <summary>
        /// Renvoie les éléments de la séquence d'entrée en sautant le premier élément qui vérifie le prédicat spécifié.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'entrée</param>
        /// <param name="predicate">Prédicat à évaluer pour déterminer s'il faut sauter l'élément</param>
        /// <returns>La séquence d'entrée sans le premier élément qui vérifie le prédicat</returns>
        public static IEnumerable<T> SkipFirst<T>(this IEnumerable<T> source, Func<T, bool> predicate)
        {
            source.CheckArgumentNull("source");
            predicate.CheckArgumentNull("predicate");
            return source.SkipFirstIterator(predicate);
        }

        private static IEnumerable<T> SkipFirstIterator<T>(this IEnumerable<T> source, Func<T, bool> predicate)
        {
            bool skipped = false;
            foreach (var item in source)
            {
                if (!skipped && predicate(item))
                {
                    skipped = true;
                    continue;
                }
                
                yield return item;
            }
        }

        /// <summary>
        /// Renvoie les éléments de la séquence d'entrée en sautant le dernier élément qui vérifie le prédicat spécifié.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'entrée</param>
        /// <param name="predicate">Prédicat à évaluer pour déterminer s'il faut sauter l'élément</param>
        /// <returns>La séquence d'entrée sans le dernier élément qui vérifie le prédicat</returns>
        public static IEnumerable<T> SkipLast<T>(this IEnumerable<T> source, Func<T, bool> predicate)
        {
            source.CheckArgumentNull("source");
            predicate.CheckArgumentNull("predicate");
            return source.SkipLastIterator(predicate);
        }

        private static IEnumerable<T> SkipLastIterator<T>(this IEnumerable<T> source, Func<T, bool> predicate)
        {
            var queue = new Queue<T>();
            var last = default(T);
            bool any = false;

            foreach (var item in source)
            {
                if (predicate(item))
                {
                    if (any)
                        yield return last; 
                    
                    while (queue.Count > 0)
                        yield return queue.Dequeue();

                    last = item;
                    any = true;
                }
                else
                {
                    if (any)
                        queue.Enqueue(item);
                    else
                        yield return item;
                }
            }

            while (queue.Count > 0)
                yield return queue.Dequeue();
        }

        /// <summary>
        /// Renvoie les éléments de la séquence d'entrée en sautant l'élément qui se trouve à 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="index">Position de l'élément à sauter</param>
        /// <returns>La séquence d'entrée sans l'élément qui se trouvait à la position spécifiée</returns>
        public static IEnumerable<T> SkipAt<T>(this IEnumerable<T> source, int index)
        {
            return source.Where((it, i) => i != index);
        }

        #endregion

        #region TakeLast

        /// <summary>
        /// Renvoie le nombre spécifié d'éléments de la fin d'une séquence
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'entrée</param>
        /// <param name="count">Nombre maximum d'éléments à renvoyer</param>
        /// <returns>Les <c>count</c> derniers éléments de la séquence</returns>
        public static IEnumerable<T> TakeLast<T>(this IEnumerable<T> source, int count)
        {
            source.CheckArgumentNull("source");
            if (count < 0)
                throw new ArgumentOutOfRangeException(
                    "count",
                    string.Format(ExceptionMessages.NumberMustBePositiveOrZero, "count"));
            return source.TakeLastIterator(count);
        }

        private static IEnumerable<T> TakeLastIterator<T>(this IEnumerable<T> source, int count)
        {
            if (count <= 0)
                yield break;

            var queue = new Queue<T>();
            foreach (var item in source)
            {
                if (queue.Count == count)
                    queue.Dequeue();
                queue.Enqueue(item);
            }

            foreach (var item in queue)
                yield return item;
        }

        #endregion

        #region ReplaceAt

        /// <summary>
        /// Remplaçe l'élément à la position spécifiée d'une séquence par un élément spécifié.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'entrée</param>
        /// <param name="index">Position à laquelle effectuer le remplacement</param>
        /// <param name="item">Elément qui remplace l'élément à la position spécifiée</param>
        /// <returns>Séquence dans laquelle un élément a été remplacé</returns>
        public static IEnumerable<T> ReplaceAt<T>(this IEnumerable<T> source, int index, T item)
        {
            return source.Select((it, i) => i == index ? item : it);
        }

        #endregion

        #region InsertAt
        /// <summary>
        /// Insère un élément à la position spécifiée d'une séquence.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'entrée</param>
        /// <param name="index">Position à laquelle insérer l'élément</param>
        /// <param name="item">Elément à insérer</param>
        /// <returns>Séquence dans laquelle un élément a été inséré</returns>
        public static IEnumerable<T> InsertAt<T>(this IEnumerable<T> source, int index, T item)
        {
            source.CheckArgumentNull("source");
            index.CheckArgumentOutOfRange("index", 0, int.MaxValue);
            return source.InsertAtIterator(index, item);
        }

        private static IEnumerable<T> InsertAtIterator<T>(this IEnumerable<T> source, int index, T item)
        {
            int i = 0;
            foreach (var it in source)
            {
                if (i++ == index)
                    yield return item;
                
                yield return it;
            }
        }

        #endregion

        #region None

        /// <summary>
        /// Indique si une séquence ne contient aucun élément
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence à vérifier</param>
        /// <returns>true si <c>source</c> ne contient aucun élément ; sinon, false</returns>
        public static bool None<T>(this IEnumerable<T> source)
        {
            return !source.Any();
        }

        /// <summary>
        /// Indique s'il n'existe dans la séquence aucun élément qui satisfait le prédicat
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence à vérifier</param>
        /// <param name="predicate">Prédicat à évaluer pour chaque élément de la séquence</param>
        /// <returns>true si la séquence ne contient aucun élément qui satisfait le prédicat ; sinon, false</returns>
        public static bool None<T>(this IEnumerable<T> source, Func<T, bool> predicate)
        {
            return !source.Any(predicate);
        }

        #endregion

        #region ContainsAny

        /// <summary>
        /// Indique si une séquence contient au moins un des éléments spécifiés, en utilisant le comparateur par défaut
        /// </summary>
        /// <typeparam name="T">Type des élements de la séquence</typeparam>
        /// <param name="source">Séquence dans laquelle rechercher des éléments</param>
        /// <param name="items">Eléments à rechercher</param>
        /// <returns>true si <c>source</c> contient au moins un des éléments de <c>items</c>, false sinon</returns>
        public static bool ContainsAny<T>(this IEnumerable<T> source, IEnumerable<T> items)
        {
            return ContainsAny(source, items, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Indique si une séquence contient au moins un des éléments spécifiés, en utilisant le comparateur spécifié
        /// </summary>
        /// <typeparam name="T">Type des élements de la séquence</typeparam>
        /// <param name="source">Séquence dans laquelle rechercher des éléments</param>
        /// <param name="items">Eléments à rechercher</param>
        /// <param name="comparer">Comparateur à utiliser</param>
        /// <returns>true si <c>source</c> contient au moins un des éléments de <c>items</c>, false sinon</returns>
        public static bool ContainsAny<T>(this IEnumerable<T> source, IEnumerable<T> items, IEqualityComparer<T> comparer)
        {
            return source.Intersect(items, comparer).Any();
        }

        #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>(this ICollection<T> collection, IEnumerable<T> items)
        {
            items.CheckArgumentNull("items");
            foreach (var item in items)
            {
                collection.Add(item);
            }
        }

        #endregion

        #region ArraySegment related methods

        /// <summary>
        /// Renvoie le segment demandé d'un tableau
        /// </summary>
        /// <typeparam name="T">Type des éléments du tableau</typeparam>
        /// <param name="array">Tableau dont on veut obtenir un segment</param>
        /// <param name="from">Index de début du segment</param>
        /// <param name="count">Nombre d'éléments dans le segment</param>
        /// <returns>Le segment demandé du tableau</returns>
        public static ArraySegment<T> GetSegment<T>(this T[] array, int from, int count)
        {
            return new ArraySegment<T>(array, from, count);
        }

        /// <summary>
        /// Renvoie un segment d'un tableau à partir de la position spécifiée
        /// </summary>
        /// <typeparam name="T">Type des éléments du tableau</typeparam>
        /// <param name="array">Tableau dont on veut obtenir un segment</param>
        /// <param name="from">Index de début du segment</param>
        /// <returns>Le segment de tableau qui commence à la position spécifiée</returns>
        public static ArraySegment<T> GetSegment<T>(this T[] array, int from)
        {
            return GetSegment(array, from, array.Length - from);
        }

        /// <summary>
        /// Renvoie un segment de tableau représentant la totalité du tableau
        /// </summary>
        /// <typeparam name="T">Type des éléments du tableau</typeparam>
        /// <param name="array">Tableau dont on veut obtenir un segment</param>
        /// <returns>Un segment représentant la totalité du tableau</returns>
        public static ArraySegment<T> GetSegment<T>(this T[] array)
        {
            return new ArraySegment<T>(array);
        }

        /// <summary>
        /// Renvoie une séquence qui énumère les éléments d'un segment de tableau
        /// </summary>
        /// <typeparam name="T">Type des éléments du tableau</typeparam>
        /// <param name="arraySegment">Segment de tableau à énumérer</param>
        /// <returns>Une séquence correspondant aux éléments du segment de tableau</returns>
        public static IEnumerable<T> AsEnumerable<T>(this ArraySegment<T> arraySegment)
        {
            return arraySegment.Array.Skip(arraySegment.Offset).Take(arraySegment.Count);
        }

        /// <summary>
        /// Renvoie un nouveau tableau à partir d'un segment de tableau
        /// </summary>
        /// <typeparam name="T">Type des éléments du tableau</typeparam>
        /// <param name="arraySegment">Segment de tableau à partir duquel est créé le nouveau tableau</param>
        /// <returns>Un tableau contenant tous les éléments du segment d'origine</returns>
        public static T[] ToArray<T>(this ArraySegment<T> arraySegment)
        {
            T[] array = new T[arraySegment.Count];
            Array.Copy(arraySegment.Array, arraySegment.Offset, array, 0, arraySegment.Count);
            return array;
        }

        #endregion

        #region IndexOf

        /// <summary>
        /// Renvoie l'index de la première occurence de l'élément spécifié dans la séquence
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la séquence</typeparam>
        /// <param name="source">La séquence dans laquelle chercher l'élément</param>
        /// <param name="item">L'élément à rechercher</param>
        /// <returns>L'index de la première occurence de l'élément dans la séquence, ou -1 si l'élément ne s'y trouve pas.</returns>
        public static int IndexOf<T>(this IEnumerable<T> source, T item)
        {
            return source.AsIndexed()
                        .Where(x => x.Value.SafeEquals(item))
                        .Select(x => x.Index)
                        .FirstOrDefault(-1);
        }

        /// <summary>
        /// Renvoie l'index du premier élément pour lequel le prédicat spécifié est vérifié
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la séquence</typeparam>
        /// <param name="source">La séquence dans laquelle chercher l'élément</param>
        /// <param name="predicate">Le prédicat à évaluer</param>
        /// <returns>L'index du premier élément pour lequel le prédicat est vérifié, ou -1 si aucun élément ne vérifie le prédicat.</returns>
        public static int IndexOf<T>(this IEnumerable<T> source, Func<T, bool> predicate)
        {
            return source.AsIndexed()
                        .Where(x => predicate(x.Value))
                        .Select(x => x.Index)
                        .FirstOrDefault(-1);
        }

        /// <summary>
        /// Renvoie l'index de la dernière occurence de l'élément spécifié dans la séquence
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la séquence</typeparam>
        /// <param name="source">La séquence dans laquelle chercher l'élément</param>
        /// <param name="item">L'élément à rechercher</param>
        /// <returns>L'index de la dernière occurence de l'élément dans la séquence, ou -1 si l'élément ne s'y trouve pas.</returns>
        public static int LastIndexOf<T>(this IEnumerable<T> source, T item)
        {
            return source.AsIndexed()
                        .Where(x => x.Value.SafeEquals(item))
                        .Select(x => x.Index)
                        .LastOrDefault(-1);
        }

        /// <summary>
        /// Renvoie l'index du dernier élément pour lequel le prédicat spécifié est vérifié
        /// </summary>
        /// <typeparam name="T">Le type des éléments de la séquence</typeparam>
        /// <param name="source">La séquence dans laquelle chercher l'élément</param>
        /// <param name="predicate">Le prédicat à évaluer</param>
        /// <returns>L'index du dernier élément pour lequel le prédicat est vérifié, ou -1 si aucun élément ne vérifie le prédicat.</returns>
        public static int LastIndexOf<T>(this IEnumerable<T> source, Func<T, bool> predicate)
        {
            return source.AsIndexed()
                        .Where(x => predicate(x.Value))
                        .Select(x => x.Index)
                        .LastOrDefault(-1);
        }

        #endregion

        #region CopyTo

        /// <summary>
        /// Copie tous les éléments de la séquence vers le tableau spécifié
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence à partir de laquelle copier les éléments</param>
        /// <param name="array">Tableau vers lequel copier les éléments</param>
        /// <param name="arrayIndex">Position dans le tableau à partir de laquelle les éléments sont copiés</param>
        public static void CopyTo<T>(this IEnumerable<T> source, T[] array, int arrayIndex)
        {
            int lowerBound = array.GetLowerBound(0);
            int upperBound = array.GetUpperBound(0);
            if (arrayIndex < lowerBound || arrayIndex > upperBound)
                throw new ArgumentOutOfRangeException("arrayIndex");

            int i = 0;
            foreach (var item in source)
            {
                if (arrayIndex + i > upperBound)
                    throw new ArgumentException(ExceptionMessages.ArrayCapacityInsufficient);
                array[arrayIndex + i] = item;
                i++;
            }
        }

        #endregion

        #region ShiftLeft, ShiftRight

        /// <summary>
        /// Décale les éléments d'un tableau d'une position vers la gauche,
        /// en remplaçant le dernier élément par la valeur par défaut du type
        /// des éléments du tableau. Cette méthode ne modifie pas le tableau d'origine
        /// mais renvoie un nouveau tableau.
        /// </summary>
        /// <typeparam name="T">Type des éléments du tableau</typeparam>
        /// <param name="array">Tableau à décaler</param>
        /// <returns>Une copie décalée du tableau d'origine</returns>
        public static T[] ShiftLeft<T>(this T[] array)
        {
            return array.ShiftLeft(default(T));
        }

        /// <summary>
        /// Décale les éléments d'un tableau d'une position vers la gauche,
        /// en remplaçant le dernier élément par la valeur spécifiée.
        /// Cette méthode ne modifie pas le tableau d'origine mais renvoie un
        /// nouveau tableau.
        /// </summary>
        /// <typeparam name="T">Type des éléments du tableau</typeparam>
        /// <param name="array">Tableau à décaler</param>
        /// <param name="value">Valeur à insérer à la fin du tableau</param>
        /// <returns>Une copie décalée du tableau d'origine</returns>
        public static T[] ShiftLeft<T>(this T[] array, T value)
        {
            T[] newArray = new T[array.Length];
            Array.Copy(array, 1, newArray, 0, array.Length - 1);
            newArray[array.Length - 1] = value;
            return newArray;
        }

        /// <summary>
        /// Décale les éléments d'un tableau d'une position vers la droite,
        /// en remplaçant le premier élément par la valeur par défaut du type
        /// des éléments du tableau. Cette méthode ne modifie pas le tableau d'origine
        /// mais renvoie un nouveau tableau.
        /// </summary>
        /// <typeparam name="T">Type des éléments du tableau</typeparam>
        /// <param name="array">Tableau à décaler</param>
        /// <returns>Une copie décalée du tableau d'origine</returns>
        public static T[] ShiftRight<T>(this T[] array)
        {
            return array.ShiftRight(default(T));
        }

        /// <summary>
        /// Décale les éléments d'un tableau d'une position vers la droite,
        /// en remplaçant le premier élément par la valeur spécifiée.
        /// Cette méthode ne modifie pas le tableau d'origine mais renvoie un
        /// nouveau tableau.
        /// </summary>
        /// <typeparam name="T">Type des éléments du tableau</typeparam>
        /// <param name="array">Tableau à décaler</param>
        /// <param name="value">Valeur à insérer au début du tableau</param>
        /// <returns>Une copie décalée du tableau d'origine</returns>
        public static T[] ShiftRight<T>(this T[] array, T value)
        {
            T[] newArray = new T[array.Length];
            Array.Copy(array, 0, newArray, 1, array.Length - 1);
            newArray[0] = value;
            return newArray;
        }

        #endregion

        #region RotateLeft, RotateRight

        /// <summary>
        /// Effectue une rotation d'un tableau d'une position vers la gauche.
        /// Cette méthode ne modifie pas le tableau d'origine mais renvoie un
        /// nouveau tableau.
        /// </summary>
        /// <typeparam name="T">Type des éléments du tableau</typeparam>
        /// <param name="array">Tableau sur lequel effectuer une rotation</param>
        /// <returns>Une copie du tableau d'origine sur laquelle une rotation a été effectuée</returns>
        public static T[] RotateLeft<T>(this T[] array)
        {
            return array.ShiftLeft(array.First());
        }

        /// <summary>
        /// Effectue une rotation d'un tableau d'une position vers la droite.
        /// Cette méthode ne modifie pas le tableau d'origine mais renvoie un
        /// nouveau tableau.
        /// </summary>
        /// <typeparam name="T">Type des éléments du tableau</typeparam>
        /// <param name="array">Tableau sur lequel effectuer une rotation</param>
        /// <returns>Une copie du tableau d'origine sur laquelle une rotation a été effectuée</returns>
        public static T[] RotateRight<T>(this T[] array)
        {
            return array.ShiftRight(array.Last());
        }

        #endregion

        #region Apply

        /// <summary>
        /// Applique l'action spécifiée "au passage" sur chaque élément de la séquence
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'origine</param>
        /// <param name="action">Action à effectuer sur chaque élément de la séquence</param>
        /// <returns>La séquence d'origine</returns>
        /// <remarks>Cette méthode s'utilise uniquement avec des types référence. Pour les types valeur,
        /// le paramètre de l'action doit être passé par référence.</remarks>
        public static IEnumerable<T> Apply<T>(this IEnumerable<T> source, Action<T> action)
            where T : class
        {
            action.CheckArgumentNull("action");
            return source.ApplyIterator(action);
        }

        private static IEnumerable<T> ApplyIterator<T>(this IEnumerable<T> source, Action<T> action)
            where T : class
        {
            foreach (var item in source)
            {
                action(item);
                yield return item;
            }
        }

        /// <summary>
        /// Représente une action avec un paramètre passé par référence
        /// </summary>
        /// <typeparam name="T">Type du paramètre</typeparam>
        /// <param name="param">Paramètre de l'action</param>
        public delegate void ByRefAction<T>(ref T param);

        /// <summary>
        /// Applique l'action spécifiée "au passage" sur chaque élément de la séquence
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'origine</param>
        /// <param name="action">Action à effectuer sur chaque élément de la séquence</param>
        /// <returns>La séquence d'origine</returns>
        /// <remarks>Cette méthode s'utilise uniquement avec des types valeur. Pour les types référence,
        /// le paramètre de l'action doit être passé par valeur.</remarks>
        public static IEnumerable<T> Apply<T>(this IEnumerable<T> source, ByRefAction<T> action)
            where T : struct
        {
            action.CheckArgumentNull("action");
            return source.ApplyIterator(action);
        }

        private static IEnumerable<T> ApplyIterator<T>(this IEnumerable<T> source, ByRefAction<T> action)
            where T : struct
        {
            foreach (var item in source)
            {
                T it = item;
                action(ref it);
                yield return it;
            }
        }

        #endregion

        #region IndexOfSequence

        /// <summary>
        /// Renvoie la position de début de la première occurence de la sous-séquence spécifiée dans la séquence source,
        /// en utilisant le comparateur par défaut.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence source dans laquelle on recherche une sous-séquence</param>
        /// <param name="sequence">Sous-séquence à rechercher</param>
        /// <returns>La position de la première occurence de <c>sequence</c> dans <c>source</c>, ou -1 si la sous-séquence n'est pas trouvée.</returns>
        public static int IndexOfSequence<T>(this IEnumerable<T> source, IEnumerable<T> sequence)
        {
            return source.IndexOfSequence(sequence, EqualityComparer<T>.Default);
        }

        /// <summary>
        /// Renvoie la position de début de la première occurence de la sous-séquence spécifiée dans la séquence source,
        /// en utilisant le comparateur spécifié.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence source dans laquelle on recherche une sous-séquence</param>
        /// <param name="sequence">Sous-séquence à rechercher</param>
        /// <param name="comparer">Comparateur à utiliser</param>
        /// <returns>La position de la première occurence de <c>sequence</c> dans <c>source</c>, ou -1 si la sous-séquence n'est pas trouvée.</returns>
        public static int IndexOfSequence<T>(this IEnumerable<T> source, IEnumerable<T> sequence, IEqualityComparer<T> comparer)
        {
            var seq = sequence.ToArray();

            int p = 0; // current position in source sequence
            int i = 0; // current position in searched sequence
            var prospects = new List<int>(); // list of prospective matches
            foreach (var item in source)
            {
// ReSharper disable AccessToModifiedClosure
                // Remove bad prospective matches
                prospects.RemoveAll(k => !comparer.Equals(item, seq[p - k]));
// ReSharper restore AccessToModifiedClosure

                // Is it the start of a prospective match ?
                if (comparer.Equals(item, seq[0]))
                {
                    prospects.Add(p);
                }

                // Does current character continues partial match ?
                if (comparer.Equals(item, seq[i]))
                {
                    i++;
                    // Do we have a complete match ?
                    if (i == seq.Length)
                    {
                        // Bingo !
                        return p - seq.Length + 1;
                    }
                }
                else // Mismatch
                {
                    // Do we have prospective matches to fall back to ?
                    if (prospects.Count > 0)
                    {
                        // Yes, use the first one
                        int k = prospects[0];
                        i = p - k + 1;
                    }
                    else
                    {
                        // No, start from beginning of searched sequence
                        i = 0;
                    }
                }
                p++;
            }
            // No match
            return -1;
        }

        #endregion

        #region Hierarchy related methods

        /// <summary>
        /// Représente un noeud dans une hiérarchie d'objets
        /// </summary>
        /// <typeparam name="T">Type des objets de la hiérarchie</typeparam>
        public class Node<T>
        {
            internal Node() { }

            /// <summary>
            /// Objet contenu par ce noeud
            /// </summary>
            public T Item { get; internal set; }

            /// <summary>
            /// Niveau du noeud dans la hiérarchie (0 pour un noeud racine)
            /// </summary>
            public int Level { get; internal set; }

            /// <summary>
            /// Noeud parent dans la hiérarchie (null pour un noeud racine)
            /// </summary>
            public Node<T> Parent { get; internal set; }

            /// <summary>
            /// Noeuds enfants dans la hiérarchie
            /// </summary>
            public IList<Node<T>> Children { get; internal set; }
        }

        /// <summary>
        /// Renvoie une collection de noeuds représentant les objets de la collection source sous forme hiérarchique,
        /// selon la relation spécifiée
        /// </summary>
        /// <typeparam name="T">Type des éléments de la collection source</typeparam>
        /// <param name="source">Collection d'objets à hiérarchiser</param>
        /// <param name="startWith">Prédicat pour identifier les éléments racines</param>
        /// <param name="connectBy">Relation qui lie un objet parent à ses enfants</param>
        /// <returns>Une collection de noeuds représentant les objets de la collection source sous forme hiérarchique</returns>
        public static IEnumerable<Node<T>> ToHierarchy<T>(
            this IEnumerable<T> source,
            Func<T, bool> startWith,
            Func<T, T, bool> connectBy)
        {
            return source.ToHierarchy(startWith, connectBy, null);
        }

        private static IEnumerable<Node<T>> ToHierarchy<T>(
            this IEnumerable<T> source,
            Func<T, bool> startWith,
            Func<T, T, bool> connectBy,
            Node<T> parent)
        {
            int level = (parent == null ? 0 : parent.Level + 1);

            if (source == null)
                throw new ArgumentNullException("source");

            if (startWith == null)
                throw new ArgumentNullException("startWith");

            if (connectBy == null)
                throw new ArgumentNullException("connectBy");

            foreach (T value in from item in source
                                where startWith(item)
                                select item)
            {
                var children = new List<Node<T>>();
                var newNode = new Node<T>
                {
                    Level = level,
                    Parent = parent,
                    Item = value,
                    Children = children.AsReadOnly()
                };

                T tmpValue = value;
                children.AddRange(source.ToHierarchy(possibleSub => connectBy(tmpValue, possibleSub), connectBy, newNode));

                yield return newNode;
            }
        }

        /// <summary>
        /// Ecrit une hiérarchie d'objets dans le TextWriter spécifié
        /// </summary>
        /// <typeparam name="T">Type des objets de la hiérarchie</typeparam>
        /// <param name="nodes">Collection de noeuds à afficher</param>
        /// <param name="writer">TextWriter dans lequel écrire la hiérarchie</param>
        /// <param name="indent">Chaine d'indentation à utiliser</param>
        /// <param name="display">Fonction qui sélectionne le membre à afficher</param>
        public static void DumpHierarchy<T>(this IEnumerable<Node<T>> nodes, TextWriter writer, string indent, Func<T, string> display)
        {
            nodes.DumpHierarchy(writer, indent, display, 0);
        }

        /// <summary>
        /// Ecrit une hiérarchie d'objets dans le TextWriter spécifié
        /// </summary>
        /// <typeparam name="T">Type des objets de la hiérarchie</typeparam>
        /// <param name="nodes">Collection de noeuds à afficher</param>
        /// <param name="writer">TextWriter dans lequel écrire la hiérarchie</param>
        /// <param name="display">Fonction qui sélectionne le membre à afficher</param>
        public static void DumpHierarchy<T>(this IEnumerable<Node<T>> nodes, TextWriter writer, Func<T, string> display)
        {
            nodes.DumpHierarchy(writer, "  ", display, 0);
        }

        /// <summary>
        /// Ecrit une hiérarchie d'objets dans le TextWriter spécifié
        /// </summary>
        /// <typeparam name="T">Type des objets de la hiérarchie</typeparam>
        /// <param name="nodes">Collection de noeuds à afficher</param>
        /// <param name="writer">TextWriter dans lequel écrire la hiérarchie</param>
        /// <param name="indent">Chaine d'indentation à utiliser</param>
        public static void DumpHierarchy<T>(this IEnumerable<Node<T>> nodes, TextWriter writer, string indent)
        {
            nodes.DumpHierarchy(writer, indent, item => item.ToString(), 0);
        }

        /// <summary>
        /// Ecrit une hiérarchie d'objets dans le TextWriter spécifié
        /// </summary>
        /// <typeparam name="T">Type des objets de la hiérarchie</typeparam>
        /// <param name="nodes">Collection de noeuds à afficher</param>
        /// <param name="writer">TextWriter dans lequel écrire la hiérarchie</param>
        public static void DumpHierarchy<T>(this IEnumerable<Node<T>> nodes, TextWriter writer)
        {
            nodes.DumpHierarchy(writer, "  ", item => item.ToString(), 0);
        }


        /// <summary>
        /// Ecrit une hiérarchie d'objets dans la console
        /// </summary>
        /// <typeparam name="T">Type des objets de la hiérarchie</typeparam>
        /// <param name="nodes">Collection de noeuds à afficher</param>
        /// <param name="indent">Chaine d'indentation à utiliser</param>
        /// <param name="display">Fonction qui sélectionne le membre à afficher</param>
        public static void DumpHierarchy<T>(this IEnumerable<Node<T>> nodes, string indent, Func<T, string> display)
        {
            nodes.DumpHierarchy(Console.Out, indent, display, 0);
        }

        /// <summary>
        /// Ecrit une hiérarchie d'objets dans la console
        /// </summary>
        /// <typeparam name="T">Type des objets de la hiérarchie</typeparam>
        /// <param name="nodes">Collection de noeuds à afficher</param>
        /// <param name="display">Fonction qui sélectionne le membre à afficher</param>
        public static void DumpHierarchy<T>(this IEnumerable<Node<T>> nodes, Func<T, string> display)
        {
            nodes.DumpHierarchy(Console.Out, "  ", display, 0);
        }

        /// <summary>
        /// Ecrit une hiérarchie d'objets dans la console
        /// </summary>
        /// <typeparam name="T">Type des objets de la hiérarchie</typeparam>
        /// <param name="nodes">Collection de noeuds à afficher</param>
        /// <param name="indent">Chaine d'indentation à utiliser</param>
        public static void DumpHierarchy<T>(this IEnumerable<Node<T>> nodes, string indent)
        {
            nodes.DumpHierarchy(Console.Out, indent, item => item.ToString(), 0);
        }

        /// <summary>
        /// Ecrit une hiérarchie d'objets dans la console
        /// </summary>
        /// <typeparam name="T">Type des objets de la hiérarchie</typeparam>
        /// <param name="nodes">Collection de noeuds à afficher</param>
        public static void DumpHierarchy<T>(this IEnumerable<Node<T>> nodes)
        {
            nodes.DumpHierarchy(Console.Out, "  ", item => item.ToString(), 0);
        }

        private static void DumpHierarchy<T>(this IEnumerable<Node<T>> nodes, TextWriter writer, string indent, Func<T, string> display, int level)
        {
            foreach (var node in nodes)
            {
                for (int i = 0; i < level; i++) writer.Write(indent);
                writer.WriteLine(display(node.Item));
                if (node.Children != null)
                    node.Children.DumpHierarchy(writer, indent, display, level + 1);
            }
        }

        /// <summary>
        /// Aplanit une hiérarchie d'objets de même type en énumérant tous les noeuds
        /// de la hiérarchie, dans l'ordre de parcours indiqué.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la hiérarchie</typeparam>
        /// <param name="source">Collection des éléments racines de la hiérarchie</param>
        /// <param name="childrenSelector">Fonction qui renvoie les enfants d'un noeud de la hiérarchie</param>
        /// <param name="traversalMode">Mode de parcours de la hiérarchie</param>
        /// <returns>Une séquence contenant tous les noeuds de la hiérarchie</returns>
        public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector, TreeTraversalMode traversalMode)
        {
            source.CheckArgumentNull("source");
            childrenSelector.CheckArgumentNull("childrenSelector");
            switch (traversalMode)
            {
                case TreeTraversalMode.DepthFirst:
                    return source.DepthFirstFlattenIterator(childrenSelector);
                case TreeTraversalMode.BreadthFirst:
                    return source.BreadthFirstFlattenIterator(childrenSelector);
                default:
                    throw new ArgumentOutOfRangeException("traversalMode");
            }
        }

        private static IEnumerable<T> BreadthFirstFlattenIterator<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector)
        {
            var queue = new Queue<T>(source);
            while (queue.Count > 0)
            {
                var item = queue.Dequeue();
                yield return item;
                foreach (var child in childrenSelector(item))
                {
                    queue.Enqueue(child);
                }
            }
        }

        private static IEnumerable<T> DepthFirstFlattenIterator<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector)
        {
            var list = new LinkedList<T>(source);
            while (list.Count > 0)
            {
                var item = list.First.Value;
                list.RemoveFirst();
                yield return item;
                var node = list.First;
                foreach (var child in childrenSelector(item))
                {
                    if (node != null)
                        list.AddBefore(node, child);
                    else
                        list.AddLast(child);
                }
            }
        }

        #endregion

        #region Split

        /// <summary>
        /// Divise une séquence d'éléments en plusieurs parties à chaque fois qu'un séparateur
        /// est rencontré.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <param name="source">Séquence d'éléments à diviser</param>
        /// <param name="isSeparator">Prédicat qui détermine si un élément de la liste est un séparateur</param>
        /// <returns>Une séquence de parties de la séquence d'origine</returns>
        public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> source, Func<T, bool> isSeparator)
        {
            source.CheckArgumentNull("source");
            isSeparator.CheckArgumentNull("isSeparator");
            return source.SplitIterator(isSeparator);
        }

        private static IEnumerable<IEnumerable<T>> SplitIterator<T>(this IEnumerable<T> source, Func<T, bool> isSeparator)
        {
            List<T> list = new List<T>();
            foreach (var item in source)
            {
                if(isSeparator(item))
                {
                    if (list.Count > 0)
                    {
                        yield return list.AsReadOnly();
                        list = new List<T>();
                    }
                }
                else
                {
                    list.Add(item);
                }
            }

            if (list.Count > 0)
                yield return list.AsReadOnly();
        }

        #endregion

        #region DistinctBy

        /// <summary>
        /// Retourne des éléments distincts d'une séquence, en les comparant selon la clé spécifiée,
        /// et en comparant les clés avec le comparateur spécifié.
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <typeparam name="TKey">Type de la clé</typeparam>
        /// <param name="source">Séquence de laquelle supprimer les éléments en double</param>
        /// <param name="keySelector">Fonction qui renvoie la clé à utiliser pour comparer les éléments</param>
        /// <param name="keyComparer">Comparateur à utiliser pour comparer les clés</param>
        /// <returns>Une séquence contenant des éléments distincts de la séquence d'origine</returns>
        public static IEnumerable<T> Distinct<T, TKey>(this IEnumerable<T> source, Func<T, TKey> keySelector, IEqualityComparer<TKey> keyComparer)
        {
            keySelector.CheckArgumentNull("keySelector");
            keyComparer.CheckArgumentNull("keyComparer");
            return source.Distinct(new KeyEqualityComparer<T, TKey>(keySelector, keyComparer));
        }

        /// <summary>
        /// Retourne des éléments distincts d'une séquence, en les comparant selon la clé spécifiée
        /// </summary>
        /// <typeparam name="T">Type des éléments de la séquence</typeparam>
        /// <typeparam name="TKey">Type de la clé</typeparam>
        /// <param name="source">Séquence de laquelle supprimer les éléments en double</param>
        /// <param name="keySelector">Fonction qui renvoie la clé à utiliser pour comparer les éléments</param>
        /// <returns>Une séquence contenant des éléments distincts de la séquence d'origine</returns>
        public static IEnumerable<T> Distinct<T, TKey>(this IEnumerable<T> source, Func<T, TKey> keySelector)
        {
            keySelector.CheckArgumentNull("keySelector");
            return source.Distinct(new KeyEqualityComparer<T, TKey>(keySelector));
        }

        private class KeyEqualityComparer<T, TKey> : IEqualityComparer<T>
        {
            private readonly Func<T, TKey> _keySelector;
            private readonly IEqualityComparer<TKey> _keyComparer;

            public KeyEqualityComparer(Func<T, TKey> keySelector)
                : this(keySelector, EqualityComparer<TKey>.Default)
            {
            }

            public KeyEqualityComparer(Func<T, TKey> keySelector, IEqualityComparer<TKey> keyComparer)
            {
                keySelector.CheckArgumentNull("keySelector");
                keyComparer.CheckArgumentNull("keyComparer");
                _keySelector = keySelector;
                _keyComparer = keyComparer;
            }

            public bool Equals(T x, T y)
            {
                return _keyComparer.Equals(_keySelector(x), _keySelector(y));
            }

            public int GetHashCode(T obj)
            {
                return _keyComparer.GetHashCode(_keySelector(obj));
            }
        }

        #endregion
    }
}