package project2;

import java.util.Comparator;


public class BinaryTree<E>
{
    Comparator<E> comp;
    Node<E> head = new Node<E>(null);

    private class Node<T>
    {
        T content;
        Node<T> left;
        Node<T> right;

        public Node(T arg)
        {
            content = arg;
        }

        boolean isEmpty()
        {
            return content == null;
        }
    };

    public BinaryTree(Comparator<E> arg)
    {
        comp = arg;
    }
@Deprecated

    public void delete(E arg)
    {

    if (!contains(arg))
            return;
        Node<E> traverser = head;
        Node<E> parentTraverser;
        // search for the node
        if (head.content.equals(arg))
        {
            head = null;

            return;
        } else
        {
            parentTraverser = null;
        }
        while (true)
        {
            while (comp.compare(traverser.content, arg) < 0)
            {
                parentTraverser = traverser;
                traverser = traverser.left;
            }
            while (comp.compare(traverser.content, arg) > 0)
            {
                parentTraverser = traverser;
                traverser = traverser.right;
            }
            if (traverser.content.equals(arg))
            {
                // node to be deleted is found !
                // start searching for the smalles subnode of the right tree
                if (traverser.right == null && traverser.left == null)
                {
                    //traverser has no children the parent left || right should be set to zero
                    if (parentTraverser.left.content.equals(arg))
                    {
                        parentTraverser.left = null;
                        return;
                    }
                    if (parentTraverser.right.content.equals(arg))
                    {
                        parentTraverser.right = null;
                        return;
                    }
                }
                // if there is no right tree the continuation of the tree is in the left part
                if(traverser.right == null)
                {
                    parentTraverser.left = traverser.left;
                    return;
                }
                // normal situation
                // but the right tree's smalles element is the top of the right subtree
                if(traverser.right.left==null)
                {
                    if(parentTraverser.left == traverser)
                    {

                        parentTraverser.left = traverser.right;
                        parentTraverser.left.left = traverser.left;
                        return;
                    }
                    if(parentTraverser.right== traverser)
                    {
                    parentTraverser.right = traverser.right;
                    parentTraverser.right.left = traverser.left;
                    return;
                    }
                    }

                Node<E>traverser2 = traverser.right;
                Node<E> ParentTraverser2= null;// if traverser doesn't have left this should be the parent traverser

                while (traverser2.left != null)
                {
                    ParentTraverser2 = traverser;
                    traverser2 = traverser2.left;
                }
                //traverser2.left is null => smallest element in this subtree
                traverser2.left = traverser.left;
                ParentTraverser2.left = null;
                if (parentTraverser.left.content.equals(arg))
                {
                    parentTraverser.left = traverser2;
                    ParentTraverser2.right.left=traverser2.right;
                    return;
                }
                if (parentTraverser.right.content.equals(arg))
                {
                    parentTraverser.right = traverser2;
                    ParentTraverser2.left=traverser2.right;
                    return;
                }
            }

        }
    }

    void add(E arg)
    {
        if (head.isEmpty())
            head.content = arg;
        else
        {
            Node<E> traverser = head;
            found: while (true)
            {
                while (comp.compare(traverser.content, arg) < 0)
                {
                    if (traverser.left == null)
                    {
                        traverser.left = new Node<E>(arg);
                        break found;
                    } else
                    {
                        traverser = traverser.left;
                    }
                }
                while (comp.compare(traverser.content, arg) >= 0)
                {
                    if (traverser.right == null)
                    {
                        traverser.right = new Node<E>(arg);
                        break found;
                    } else
                    {
                        traverser = traverser.right;
                    }
                }
            }

        }
    }

    boolean contains(E arg)
    {
        Node<E> traverser = head;
        if (head.isEmpty())
            return false;
        while (true)
        {
            while (comp.compare(traverser.content, arg) < 0)
            {
                if (traverser.left == null)
                {
                    return false;
                } else
                {
                    traverser = traverser.left;
                }
            }
            while (comp.compare(traverser.content, arg) > 0)
            {
                if (traverser.right == null)
                {
                    return false;

                } else
                {
                    traverser = traverser.right;
                }
            }
            if (comp.compare(traverser.content, arg) == 0)
                return true;

        }
    }
}