using MyCollections.Generic;
using MyCollections.Generic.Stacks;
using System;
using UnityEngine;

using Gen = System.Collections.Generic;

namespace MyCollections.Generic.Trees
{
    public class Tree<T>
    {

        private TreeNode<T> root;

        public TreeNode<T> Root
        {
            get => root;
            set => root = value;
        }

        public Tree(T rootData)
        {
            //initialize tree with a root node
            root = new TreeNode<T>(rootData);
        }

        //Add a child
        public void AddChild(TreeNode<T> parent, T childData)
        {
            if (parent == null)
            {
                throw new ArgumentNullException(nameof(parent), "Parent node cannot be null");
            }

            TreeNode<T> childNode = new TreeNode<T>(childData);
            parent.Children.InsertAtEnd(childNode); //Add a child to the parents children LinkedList
        }

        // Perform traversal Depth-First Traversal
        public void RecursiveDFTraverse(TreeNode<T> node)
        {
            if (node == null)
                return;
            
            ListNode<TreeNode<T>> current = node.Children.Head;
            while (current != null)
            {
                RecursiveDFTraverse(current.Data);
                current = current.Next;
            }
        }

        // DFS using stack (iterative)
        public Gen.IEnumerator<TreeNode<T>> DFS_Iterative()
        {
            if (root == null)
                yield break;

            Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
            stack.Push(root);

            while (stack.Count > 0)
            {
                TreeNode<T> current = stack.Pop().Data;
                yield return current;

                // Push the children onto the stack
                foreach (TreeNode<T> child in current.Children)
                {
                    stack.Push(child);
                }
            }
        }

        //public TreeNode<T> DFS_Search(T target)
        //{
        //    if (root == null)
        //        return null;

        //    if (target == null)
        //        throw new ArgumentNullException(nameof(target));

        //    // Create a stack and push the root node onto it
        //    Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
        //    stack.Push(root);

        //    // Loop while there are still nodes to process
        //    while (stack.Count > 0)
        //    {
        //        // Retrieve the TreeNode<T> from the StackNode<T>
        //        TreeNode<T> current = stack.Pop().Data; // Access the Data property here

        //        // Check if the current node matches the target
        //        if (current.Data.CompareTo(target) == 0)
        //        {
        //            return current;  // Found the target node
        //        }

        //        // Push all the children of the current node onto the stack
        //        foreach (TreeNode<T> child in current.Children)
        //        {
        //            stack.Push(child);
        //        }
        //    }

        //    return null;  // Target not found

        //}

        // Search for a node with the given data (DFS)
        //public TreeNode<T> RecursiveDFS_Search(TreeNode<T> node, T searchData)
        //{
        //    if (node == null)
        //        return null;

        //    if (searchData == null) 
        //        throw new ArgumentNullException(nameof(searchData));


        //    if (node.Data.CompareTo(searchData) == 0)
        //        return node;

        //    Node<TreeNode<T>> current = node.Children.head;

        //    while (current != null)
        //    {
        //        TreeNode<T> foundNode = RecursiveDFS_Search(current.Data, searchData);

        //        if(foundNode != null)
        //            return foundNode;

        //        current = current.Next;
        //    }

        //    return null;
        //}
    }
}