/** Node of a singly linked list of strings. */
class Node
{
    private int data;
    private Node leftNode;
    private Node rightNode;
    private Node nextDataNode;
    private Node prevDataNode;
    private Node parent;

    /** Creates a node with the given element and next node. */
    public Node(int input, Node leftNode, Node rightNode, Node nextDataNode, Node prevDataNode)
    {
        data = input;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
        this.nextDataNode = nextDataNode;
        this.prevDataNode = prevDataNode;
        parent = null;
    }

    protected Node add (int data, Node head, Node smallestDataNode)
    {
        if (this.contains(data))
        {
            System.out.println("Tree already contains " + data + "; not adding it");
            return smallestDataNode;
        }
        //System.out.println("Adding " + data);
        Node currentNode = this;
        Node tempNode = new Node (data, null, null, null, null);
        while (true)
        {
            if (data < currentNode.getData())
            {
                if (currentNode.getLeft() == null)
                {
                    currentNode.setLeft(tempNode);
                    tempNode.setParent(currentNode);
                    break;
                }
                else
                {
                    currentNode = currentNode.getLeft();
                }
            }
            else
            {
                if (currentNode.getRight() == null)
                {
                    currentNode.setRight(tempNode);
                    tempNode.setParent(currentNode);
                    break;
                }
                else
                {
                    currentNode = currentNode.getRight();
                }
            }
        }

        //add it to the double linked list
        currentNode = smallestDataNode;

        if (currentNode.getData() > data)
        {
            //System.out.println("Adding " + data + " between null and " + currentNode.getData());
            currentNode.setPrevDataNode(tempNode);
            tempNode.setNextDataNode(currentNode);
            return tempNode;
        }
        else
        {
            if (currentNode.getNextDataNode() == null)
            {
                //System.out.println("DLL has one element and adding " + data + " at the end of it between " + currentNode.getData() + " and null");
                currentNode.setNextDataNode(tempNode);
                tempNode.setPrevDataNode(currentNode);
            }
            else
            {
                while (currentNode.getNextDataNode() != null && currentNode.getNextDataNode().getData() < data)
                {
                    currentNode = currentNode.getNextDataNode();
                }
                if (currentNode.getNextDataNode() == null)
                {
                    //System.out.println("Adding " + data + " at the end, between " + currentNode.getData() + " and null");
                    currentNode.setNextDataNode(tempNode);
                    tempNode.setPrevDataNode(currentNode);
                }
                else
                {
                    //System.out.println("Adding " + data + " between " + currentNode.getPrevDataNode().getData() + " and " + currentNode.getNextDataNode().getData());
                    tempNode.setNextDataNode(currentNode.getNextDataNode());
                    tempNode.setPrevDataNode(currentNode);
                    currentNode.getNextDataNode().setPrevDataNode(tempNode);
                    currentNode.setNextDataNode(tempNode);
                }
            }
            return smallestDataNode;
        }
    }

    //---------------------------</add>


    protected Node remove(int target, Node currentNode, Node head)
    {
        //System.out.println("Trying to remove " + target + " from node that has data " + currentNode.getData());

        if (currentNode.getParent() == null) //it is the root Node
        {
            //System.out.println("Removing the root");
            if (currentNode.isLeaf())
            {
                return null;
            }
            else if (currentNode.getLeft() == null) //the head node only has a Right branch
            {
                //System.out.println("  The root only has a Right branch");
                Node newHead = currentNode.getRight();
                currentNode.getRight().setParent(null);
                currentNode.setRight(null);
                currentNode.removeNodeLinkedList();
                return newHead;
            }
            else if (currentNode.getRight() == null) //the head node only has a Left branch
            {
                //System.out.println("  The root only has a Left branch");
                Node newHead = currentNode.getLeft();
                currentNode.getLeft().setParent(null);
                currentNode.setLeft(null);
                currentNode.removeNodeLinkedList();
                return newHead;
            }
            else //the head node has two branches
            {
                //System.out.println("  The root has a two branches");
                Node newHead = currentNode.getLeft().getRightmostNode();
                Node oldHead = currentNode;
                if (newHead.getLeft() != null)
                {
                    //System.out.println("    The new root has a left branch");
                    newHead.getLeft().setParent(newHead.getParent());
                    newHead.getParent().setRight(newHead.getLeft());
                    newHead.setLeft(oldHead.getLeft());
                    oldHead.getLeft().setParent(newHead);
                    newHead.setRight(oldHead.getRight());
                    oldHead.getRight().setParent(newHead);
                    newHead.setParent(null);
                    oldHead.setLeft(null);
                    oldHead.setRight(null);
                    oldHead.removeNodeLinkedList();
                    return newHead;
                }
                else
                {
                    //System.out.println("    The new root is a leaf");
                    newHead.getParent().setRight(newHead.getLeft());
                    newHead.setLeft(oldHead.getLeft());
                    oldHead.getLeft().setParent(newHead);
                    oldHead.getRight().setParent(newHead);
                    newHead.setRight(oldHead.getRight());
                    newHead.setParent(null);
                    oldHead.setLeft(null);
                    oldHead.setRight(null);
                    oldHead.removeNodeLinkedList();
                    return newHead;
                }
            }
        }
        else if (currentNode.isLeaf())
        {
            //System.out.println("It is a leaf");
            if (currentNode.getParent().getLeft() == currentNode) //the Node is the left child
            {
                //System.out.println("  It is the left child");
                currentNode.getParent().setLeft(null);
                currentNode.setParent(null);

                currentNode.removeNodeLinkedList();
            }
            else //it is the right child
            {
                //System.out.println("  It is the right child");
                currentNode.getParent().setRight(null);
                currentNode.setParent(null);

                currentNode.removeNodeLinkedList();
            }
        }
        else if (currentNode.getRight() == null || currentNode.getLeft() == null)
        { //the node that we want to delete has only one branch
            //System.out.println("Node only has one branch");
            if (currentNode.getParent().getLeft() == currentNode) //the Node is the left child
            {
                //System.out.println("  It is the left child");
                if (currentNode.getRight() == null) //the node has an empty right side
                {
                    //System.out.println("    It has an empty right side");
                    currentNode.getParent().setLeft(currentNode.getLeft());
                    currentNode.getLeft().setParent(currentNode.getParent());
                    currentNode.setParent(null);

                    currentNode.removeNodeLinkedList();
                }
                else //the node has an empty left side
                {
                    //System.out.println("    It has an empty left side");
                    currentNode.getParent().setLeft(currentNode.getRight());
                    currentNode.getRight().setParent(currentNode.getParent());
                    currentNode.setParent(null);

                    currentNode.removeNodeLinkedList();
                }
            }
            else //it is the right child
            {
                //System.out.println("  It is the right child");
                if (currentNode.getRight() == null) //the node has an empty right side
                {
                    //System.out.println("    It has an empty right side");
                    currentNode.getParent().setRight(currentNode.getLeft());
                    currentNode.getLeft().setParent(currentNode.getParent());
                    currentNode.getLeft().setParent(currentNode.getParent());
                    currentNode.setParent(null);

                    currentNode.removeNodeLinkedList();
                }
                else //the node has an empty left side
                {
                    //System.out.println("    It has an empty left side");
                    currentNode.getParent().setRight(currentNode.getRight());
                    currentNode.getRight().setParent(currentNode.getParent());
                    currentNode.getLeft().setParent(currentNode.getParent());
                    currentNode.setParent(null);

                    currentNode.removeNodeLinkedList();
                }
            }
        }
        else //the node that we want to delete has two branches
        {
            //System.out.println("Node has two branches");
            if (currentNode.getParent().getLeft() == currentNode) //the Node is the left child
            {
                //System.out.println("  It is the left child");
                Node movingNode = currentNode.getLeft().getRightmostNode();
                movingNode.setRight(currentNode.getRight());
                movingNode.getParent().setRight(movingNode.getLeft());
                currentNode.setLeft(null);
                currentNode.removeNodeLinkedList();
                currentNode.getParent().setLeft(movingNode);
                movingNode.setParent(currentNode.getParent());
                currentNode.setParent(null);
            }
            else
            {
                //System.out.println("  It is the right child");
                Node movingNode = currentNode.getLeft().getRightmostNode();
                movingNode.setRight(currentNode.getRight());
                movingNode.getParent().setRight(movingNode.getLeft());
                currentNode.setRight(null);
                currentNode.removeNodeLinkedList();
                currentNode.getParent().setRight(movingNode);
                movingNode.setParent(currentNode.getParent());
                currentNode.setParent(null);
            }
        }
        return head;
    }

    //---------------------------</remove>

    protected void removeNodeLinkedList()
    {
        //System.out.println("Removing " + this.getData() + " from the DLL");
        if (this.getNextDataNode() == null && this.getPrevDataNode() == null)
        {
            //not needed
        }
        else if (this.getNextDataNode() == null) //it is the tail node
        {
            //System.out.println("It is the tail node with previous data " + this.getPrevDataNode().getData());
            this.getPrevDataNode().setNextDataNode(null);
            this.setPrevDataNode(null);
        }
        else if (this.getPrevDataNode() == null) //it is the head node
        {
            //System.out.println("It is the head node with next data " + this.getNextDataNode().getData());
            this.getNextDataNode().setPrevDataNode(null);
            this.setNextDataNode(null);
        }
        else //it is somewhere in the middle of the LinkedList
        {
            //System.out.println("It is in the middle with prev data " + this.getPrevDataNode().getData() + " and next data " + this.getNextDataNode().getData());
            this.getNextDataNode().setPrevDataNode(this.getPrevDataNode());
            this.getPrevDataNode().setNextDataNode(this.getNextDataNode());
            this.setNextDataNode(null);
            this.setPrevDataNode(null);
        }
    }

    protected boolean contains(int data)
    {
        if (this.getData() == data)
            return true;
        else if (this.isLeaf())
            return false;
        else if (this.getData() > data)
        {
            if (this.getLeft() == null)
                return false;
            return this.getLeft().contains(data);
        }
        else
        {
            if (this.getRight() == null)
                return false;
            return this.getRight().contains(data);
        }
    }

    protected Node getNodeThatHasData(int data)
    {
        if (this.getData() == data)
            return this;
        else if (this.isLeaf())
            return null;
        else if (this.getData() > data)
        {
            if (this.getLeft() == null)
                return null;
            return this.getLeft().getNodeThatHasData(data);
        }
        else
        {
            if (this.getRight() == null)
                return null;
            return this.getRight().getNodeThatHasData(data);
        }
    }

    protected void inOrder()
    {
        if (this.getLeft() != null)
            this.getLeft().inOrder();
        System.out.print(data + " ");
        if (this.getRight() != null)
            this.getRight().inOrder();
    }

    protected void preOrder()
    {
        System.out.print(data + " ");
        if (this.getLeft() != null)
            this.getLeft().preOrder();
        if (this.getRight() != null)
            this.getRight().preOrder();
    }

    protected void postOrder()
    {
        if (this.getLeft() != null)
            this.getLeft().postOrder();
        if (this.getRight() != null)
            this.getRight().postOrder();
        System.out.print(data + " ");
    }

    public boolean isLeaf() { return (this.getLeft() == null && this.getRight() == null); }

    public double getRightmostData()
    {
        if (this.getRight() == null)
            return data;
        else
            return this.getRight().getRightmostData();
    }

    public double getLeftmostData()
    {
        if (this.getLeft() == null)
            return data;
        else
            return this.getLeft().getLeftmostData();
    }

    public Node getRightmostNode()
    {
        if (this.getRight() == null)
            return this;
        else
            return this.getRight().getRightmostNode();
    }

    public Node getLeftmostNode()
    {
        if (this.getLeft() == null)
            return this;
        else
            return this.getLeft().getLeftmostNode();
    }

    /** Sets the parent node */
    public void setParent(Node parent) { this.parent = parent; }
    /** Returns the parent node */
    public Node getParent() { return parent; }

    /** Returns the element of this node. */
    public int getData() { return data; }

    /** Returns the left node of this node. */
    public Node getLeft() { return leftNode; }
    /** Returns the right node of this node. */
    public Node getRight() { return rightNode; }

    /** Returns the next highest data node of this node. */
    public Node getNextDataNode() { return nextDataNode; }
    /** Returns the next lower data node of this node. */
    public Node getPrevDataNode() { return prevDataNode; }

    /** Sets the element of this node. */
    public void setElement(int newData ) { data = newData; }

    /** Sets the left node of this node. */
    public void setLeft(Node newLeft) { leftNode = newLeft; }
    /** Sets the right node of this node. */
    public void setRight(Node newRight) { rightNode = newRight; }

    /** Sets the next highest data node of this node. */
    public void setNextDataNode(Node newNext) { nextDataNode = newNext; }
    /** Sets the next lower data node of this node. */
    public void setPrevDataNode(Node newPrev) { prevDataNode = newPrev; }
}