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

namespace TreeAndGraphStructures
{
    public class Tree<T>
    {
        private Node<T> root;

        public Tree(T value)
        {
            if (value == null)
            {
                throw new ArgumentNullException(
                    "Cannot have null value root");
            }

            this.root = new Node<T>(value);
        }

        public Tree(T value,params Tree<T>[] children)
            : this(value)
        {
            foreach (Tree<T> child in children)
            {
                root.Children.Add(child.root);
            }
        }

        public Node<T> Root
        {
            get
            {
                return this.root;
            }
        }

        public void TraverseDFS(Node<T> root, string spaces)
        {
            if (root == null)
            {
                return;
            }

            Console.WriteLine(spaces + root.Value);

            foreach (Node<T> child in root.Children)
            {
                TraverseDFS(child, spaces + "   ");
            }
        }

        public void TraverseDFS()
        {
            this.TraverseDFS(this.root, String.Empty);
        }

        public void TraverseBFS()
        {
            Queue<Node<T>> queue = new Queue<Node<T>>();
            queue.Enqueue(root);
            string spaces = String.Empty;
            int lastQueueSize = queue.Count;
            while (queue.Count > 0)
            {
                for (int i = 0; i < lastQueueSize; i++)
                {
                    Node<T> top = queue.Dequeue();
                    Console.WriteLine(spaces + top.Value);
                    for (int j = 0; j < top.ChildrenCount; j++)
                    {
                        queue.Enqueue(top.Children[j]);
                    }

                }
                lastQueueSize = queue.Count;
                spaces = spaces + "  ";
            }

            return;
        }

        public void TraverseDFSWithStack()
        {
            Stack<Node<T>> stack = new Stack<Node<T>>();
            stack.Push(root);
            while (stack.Count > 0)
            {
                Node<T> top = stack.Pop();
                Console.WriteLine(top.Value);
                foreach (Node<T> child in top.Children)
                {
                    stack.Push(child);
                }
            }
        }


        //---------------------testing serialization-----------------------//


        public void DumpBinaryTree()
        {
            const string filePath = @"../../BinaryTree.txt";
            StreamWriter writter = new StreamWriter(filePath);
            using (writter)
            {
                RecursiveWrite(writter);
            }

        }


        public void RecursiveWrite(StreamWriter writter, Node<T> node)
        {
            if (node == null)
            {
                writter.Write("-1 ");
                return;
            }

            string data = node.Value.ToString();
            int charsData = data.Length;
            writter.Write(charsData + " " + data + " ");

            for (int i = 0; i < node.ChildrenCount; i++)
            {
                RecursiveWrite(writter, node.Children[i]);
            }

            for (int i = node.ChildrenCount; i < 2; i++)
            {
                RecursiveWrite(writter, null);
            }
        }


        public void RecursiveWrite(StreamWriter writter)
        {
            RecursiveWrite(writter, this.root);
        }

        public Tree<string> LoadBinaryTree()
        {
            const string filePath = @"../../BinaryTree.txt";
            StreamReader reader = new StreamReader(filePath);
            Tree<string> newTree = null;

            using (reader)
            {
                string line = reader.ReadLine();
                string[] treeParts = line.Split();

                int now = 0;
                newTree = MakeTree(treeParts,ref now);
            }
            return newTree;
        }

        private Tree<string> MakeTree(string[] treeParts,ref int now)
        {
            if (treeParts[now] == "-1")
            {

                return null;
            }

            now++;
            Tree<string> tree = new Tree<string>(treeParts[now]);

            now++;
            Tree<string> leftSubtree = MakeTree(treeParts, ref now);

            now++;
            Tree<string> rightSubtree = MakeTree(treeParts, ref now);

            if (leftSubtree != null)
            {
                tree.root.AddChild(leftSubtree.root);
            }
            if (rightSubtree != null)
            {
                tree.root.AddChild(rightSubtree.root);
            }

            return tree;
        }

    }
}