/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package edu.slcc.asdv.caleb.projecttrees_calebfontenot;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Queue;
import java.util.Stack;

/**
 *
 * @author caleb
 * @param <T>
 */
public class TreeASDV<T extends Comparable> implements Cloneable {

    private Node<T> root;

    class Node<T> {

        T data;
        Node<T> leftChild;
        Node<T> rightChild;
    }

    @Override
    public Object clone()
    {
        System.out.println("Cloning...");
        TreeASDV<T> clone = new TreeASDV<T>();
        ArrayList<T> oldData = this.getBreadthFirstArray();
        for (int i = 0; i < oldData.size(); ++i) {
            //System.out.println(oldData.get(i));
            clone.insert(oldData.get(i));
        }
        return clone;
    }

    public boolean insert(T t)
    {
        Node<T> newNode = new Node<>();
        newNode.data = t;

        if (root == null) {
            root = newNode;
            return true;
        }

        Node<T> current = root;
        Node<T> parent = null;

        while (current != null) {
            parent = current;
            if (t.compareTo(current.data) >= 0) {
                current = current.rightChild;
            } else {
                current = current.leftChild;
            }
        }

        // At this point, 'parent' is the node where the new node should be inserted as a child
        if (t.compareTo(parent.data) >= 0) {
            parent.rightChild = newNode;
        } else {
            parent.leftChild = newNode;
        }

        return true;
    }

    private void inOrder(Node<T> p)
    {
        if (p == null) {
            return;
        }

        inOrder(p.leftChild);
        System.out.print(p.data + " ");
        inOrder(p.rightChild);
    }

    public Node<T> findNode(T t)
    {
        Node<T> currentNode = root;
        while (currentNode != null) {
            if (t.compareTo(currentNode.data) == 0) {
                return currentNode;
            } else if (t.compareTo(currentNode.data) > 0) {
                currentNode = currentNode.rightChild;
            } else {
                currentNode = currentNode.leftChild;
            }
        }
        return null;
    }
    
public boolean remove(T t) {
    // Initialize parent and current nodes for traversal
    Node<T> parent = null;
    Node<T> current = root;

    // Search for the node to be removed
    while (current != null && !current.data.equals(t)) {
        parent = current;
        if (t.compareTo(current.data) > 0) {
            current = current.rightChild;
        } else {
            current = current.leftChild;
        }
    }

    // If node not found, return false
    if (current == null) {
        return false;
    }

    // Case 1: Node with no children
    if (current.leftChild == null && current.rightChild == null) {
        if (current == root) {
            root = null; // Removing root node
        } else if (parent.leftChild == current) {
            parent.leftChild = null; // Removing a left child
        } else {
            parent.rightChild = null; // Removing a right child
        }
    } // Case 2: Node with one child
    else if (current.leftChild == null || current.rightChild == null) {
        Node<T> child = (current.leftChild != null) ? current.leftChild : current.rightChild;
        if (current == root) {
            root = child; // Replace root with its child
        } else if (parent.leftChild == current) {
            parent.leftChild = child; // Replace parent's left child with the node's child
        } else {
            parent.rightChild = child; // Replace parent's right child with the node's child
        }
    } // Case 3: Node with two children
    else {
        Node<T> successorParent = current;
        Node<T> successor = current.rightChild;
        while (successor.leftChild != null) {
            successorParent = successor;
            successor = successor.leftChild;
        }
        current.data = successor.data; // Replace data with successor's data
        if (successorParent == current) {
            successorParent.rightChild = successor.rightChild;
        } else {
            successorParent.leftChild = successor.rightChild;
        }
    }

    return true;
}


// Helper method to find in-order successor of a node
    private Node<T> getSuccessor(Node<T> node)
    {
        Node<T> current = node.rightChild;
        Node<T> successorParent = node;
        Node<T> successor = node;

        // Find the leftmost node in the right subtree (in-order successor)
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }

        // If the successor is not the right child of the node to be removed,
        // adjust the successor's parent's leftChild reference
        if (successor != node.rightChild) {
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = node.rightChild;
        }

        return successor;
    }

    // Inorder ListIterator
    public Iterator<T> listIterator()
    {
        return new InorderIterator();
    }

    private class InorderIterator implements Iterator<T> {

        private Stack<Node<T>> stack;

        public InorderIterator()
        {
            stack = new Stack<>();
            pushLeft(root);
        }

        private void pushLeft(Node<T> node)
        {
            while (node != null) {
                stack.push(node);
                node = node.leftChild;
            }
        }

        @Override
        public boolean hasNext()
        {
            return !stack.isEmpty();
        }

        @Override
        public T next()
        {
            if (!hasNext()) {
                throw new java.util.NoSuchElementException();
            }
            Node<T> current = stack.pop();
            pushLeft(current.rightChild);
            return current.data;
        }

        @Override
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }
    
     public ArrayList<T> getBreadthFirstArray()
    {
        ArrayList<T> returnArray = new ArrayList<T>();
        if (root == null) {
            return returnArray;
        }
        Queue<Node<T>> queue = new LinkedList<>();
        
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<T> current = queue.poll();
            returnArray.add(current.data);

            if (current.leftChild != null) {
                queue.offer(current.leftChild);
            }
            if (current.rightChild != null) {
                queue.offer(current.rightChild);
            }
        }
        return returnArray;
    }

    public void breadthFirstTraversal()
    {
        if (root == null) {
            return;
        }

        Queue<Node<T>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<T> current = queue.poll();
            System.out.print(current.data + " ");

            if (current.leftChild != null) {
                queue.offer(current.leftChild);
            }
            if (current.rightChild != null) {
                queue.offer(current.rightChild);
            }
        }
    }

       @Override
    public boolean equals(Object obj) {
        return this.getBreadthFirstArray().equals(((TreeASDV) obj).getBreadthFirstArray());
    }
    
    public int height()
    {
        return calculateHeight(root);
    }

    private int calculateHeight(Node<T> node)
    {
        if (node == null) {
            return 0;
        }

        int leftHeight = calculateHeight(node.leftChild);
        int rightHeight = calculateHeight(node.rightChild);

        return 1 + Math.max(leftHeight, rightHeight);
    }

    public boolean isFullBST()
    {
        int height = height();
        int nodeCount = countNodes(root);
        return nodeCount == (1 << height) - 1; // Formula for full binary tree
    }

    private int countNodes(Node<T> node)
    {
        if (node == null) {
            return 0;
        }
        return 1 + countNodes(node.leftChild) + countNodes(node.rightChild);
    }

    public void inOrder()
    {
        if (root == null) {
            return;
        }

        Stack<Node<T>> stack = new Stack<>();
        Node<T> current = root;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.leftChild;
            }
            current = stack.pop();
            System.out.print(current.data + " ");
            current = current.rightChild;
        }
    }

    public static void main(String[] args) throws CloneNotSupportedException
    {
        TreeASDV<Integer> tree = new TreeASDV<>();
        // Insert some elements into the tree
        tree.insert(5);
        tree.insert(3);
        tree.insert(7);
        tree.insert(2);
        tree.insert(4);
        tree.insert(6);
        tree.insert(8);

        // Test breadth-first traversal
        System.out.println("Breadth-First Traversal:");
        tree.breadthFirstTraversal();
        System.out.println();

        // Test height calculation
        System.out.println("Height of the tree: " + tree.height());

        // Test if the tree is a full binary tree
        System.out.println("Is the tree a full binary tree? " + tree.isFullBST());

        // Test inorder traversal without recursion
        System.out.println("Inorder Traversal without Recursion:");
        tree.inOrder();
        System.out.println();
        System.out.println("array list from breadth traversal");
        System.out.println(tree.getBreadthFirstArray());
        System.out.println("Cloned Tree:");
        TreeASDV<Integer> clonedTree = (TreeASDV<Integer>) tree.clone();
        clonedTree.breadthFirstTraversal();
        System.out.println();
        System.out.println("Does the original tree and the clone tree equal? " + (tree.equals(clonedTree) ? "yes" : "no") );
        tree.insert(3000000);
        System.out.println("Does the original tree and the clone tree equal? " + (tree.equals(clonedTree) ? "yes" : "no") );
        tree.remove(5);
        tree.breadthFirstTraversal();
    }
}