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

namespace Developpez.Dotnet.Collections
{
    public static partial class EnumerableExtensions
    {
        #region ToHierarchy

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

        #endregion

        #region DumpHierarchy

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

        #endregion

        #region Flatten
        
        /// <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é.
        /// Les éléments renvoyés sont créés à partir d'un noeud et de son niveau dans la hiérarchie.
        /// </summary>
        /// <typeparam name="TNode">Type des éléments de la hiérarchie</typeparam>
        /// <typeparam name="TResult">Type des éléments de la séquence de résultat</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>
        /// <param name="resultSelector">Fonction qui permet de renvoyer un résultat à partir d'un noeud et de son niveau dans la hiérarchie.</param>
        /// <returns>Une séquence contenant tous les noeuds de la hiérarchie</returns>
        public static IEnumerable<TResult> Flatten<TNode, TResult>(this IEnumerable<TNode> source, Func<TNode, IEnumerable<TNode>> childrenSelector, TreeTraversalMode traversalMode, Func<TNode, int, TResult> resultSelector)
        {
            source.CheckArgumentNull("source");
            childrenSelector.CheckArgumentNull("childrenSelector");
            switch (traversalMode)
            {
                case TreeTraversalMode.DepthFirst:
                    return source.DepthFirstFlattenIterator(childrenSelector, resultSelector);
                case TreeTraversalMode.BreadthFirst:
                    return source.BreadthFirstFlattenIterator(childrenSelector, resultSelector);
                default:
                    throw new ArgumentOutOfRangeException("traversalMode");
            }
        }

        /// <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="TNode">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<TNode> Flatten<TNode>(this IEnumerable<TNode> source, Func<TNode, IEnumerable<TNode>> childrenSelector, TreeTraversalMode traversalMode)
        {
            return Flatten(source, childrenSelector, traversalMode, (x, _) => x);
        }

        private static IEnumerable<TResult> BreadthFirstFlattenIterator<TNode, TResult>(this IEnumerable<TNode> source, Func<TNode, IEnumerable<TNode>> childrenSelector, Func<TNode, int, TResult> resultSelector)
        {
            var queue = new Queue<NodeWithLevel<TNode>>(source.Select(n => new NodeWithLevel<TNode>(n, 0)));
            while (queue.Count > 0)
            {
                var item = queue.Dequeue();
                yield return resultSelector(item.Node, item.Level);
                foreach (var child in childrenSelector(item.Node))
                {
                    queue.Enqueue(new NodeWithLevel<TNode>(child, item.Level + 1));
                }
            }
        }

        private static IEnumerable<TResult> DepthFirstFlattenIterator<TNode, TResult>(this IEnumerable<TNode> source, Func<TNode, IEnumerable<TNode>> childrenSelector, Func<TNode, int, TResult> resultSelector)
        {
            var list = new LinkedList<NodeWithLevel<TNode>>(source.Select(n => new NodeWithLevel<TNode>(n, 0)));
            while (list.Count > 0)
            {
                var current = list.First.Value;
                list.RemoveFirst();
                yield return resultSelector(current.Node, current.Level);
                var llNode = list.First;
                foreach (var child in childrenSelector(current.Node))
                {
                    var newNode = new NodeWithLevel<TNode>(child, current.Level + 1);
                    if (llNode != null)
                        list.AddBefore(llNode, newNode);
                    else
                        list.AddLast(newNode);
                }
            }
        }

        private class NodeWithLevel<TNode>
        {
            private readonly TNode _node;
            private readonly int _level;

            public NodeWithLevel(TNode node, int level)
            {
                _node = node;
                _level = level;
            }

            // ReSharper disable MemberHidesStaticFromOuterClass
            public TNode Node
            // ReSharper restore MemberHidesStaticFromOuterClass
            {
                get { return _node; }
            }

            public int Level
            {
                get { return _level; }
            }
        }

        #endregion
    }
}