namespace Tree
{
    using System;
    using System.Collections.Generic;

    public class Tree<T> : IAbstractTree<T>
    {
        private readonly List<Tree<T>> _children;

        public Tree(T value)
        {
            this.Value = value;
            this.Parent = null;
            this._children = new List<Tree<T>>();
        }
        public bool IsRootDeleted { get; private set; }
        public Tree(T value, params Tree<T>[] children)
            : this(value)
        {
            foreach (var child in children)
            {
                this.Parent = this;
                this._children.Add(child);
            }
        }

        public T Value { get; private set; }
        public Tree<T> Parent { get; private set; }
        public IReadOnlyCollection<Tree<T>> Children => this._children.AsReadOnly();

        public ICollection<T> OrderBfs()
        {
            var result = new List<T>();
            var queue = new Queue<Tree<T>>();
            if (this.IsRootDeleted)
            {
                return result;
            }
            queue.Enqueue(this);
            while (queue.Count > 0)
            {
                var currentEl = queue.Dequeue();
                result.Add(currentEl.Value);

                foreach (var child in currentEl.Children)
                {
                    queue.Enqueue(child);
                }

            }
            return result;
        }

        public ICollection<T> OrderDfs()
        {
            var result = new List<T>();
            if (this.IsRootDeleted)
            {
                return result;
            }
            this.Dfs(this, result);
            return result;
        }


        public void AddChild(T parentKey, Tree<T> child)
        {
            var searchedNode = this.FindBFs(parentKey);
            this.CheckEmptyNode(searchedNode);
            searchedNode._children.Add(child);
        }


        public void RemoveNode(T nodeKey)
        {
            var currentNode = this.FindBFs(nodeKey);
            this.CheckEmptyNode(currentNode);

            foreach (var child in currentNode.Children)
            {
                child.Parent = null;
            }
            currentNode._children.Clear();
            var parent = currentNode.Parent;
            if (parent is null)
            {
                this.IsRootDeleted = true;
            }
            else
            {
                parent._children.Remove(currentNode);
            }
            currentNode.Value = default(T);
        }

        public void Swap(T firstKey, T secondKey)
        {
            throw new NotImplementedException();
        }

        private Tree<T> FindBFs(T value)
        {

            var queue = new Queue<Tree<T>>();
            queue.Enqueue(this);
            while (queue.Count > 0)
            {
                var subtree = queue.Dequeue();
                if (subtree.Value.Equals(value))
                {
                    return subtree;
                }
                foreach (var child in subtree.Children)
                {
                    queue.Enqueue(child);
                }
            }
            return null;
        }
        private void Dfs(Tree<T> subTree, List<T> result)
        {

            foreach (var child in subTree.Children)
            {
                this.Dfs(child, result);
            }
            result.Add(subTree.Value);
        }
        private void CheckEmptyNode(Tree<T> searchedNode)
        {
            if (searchedNode is null)
            {
                throw new ArgumentNullException("Node not found!");
            }
        }
    }
}