package eg.edu.alexu.csd.filestructure.redblacktree;

import javax.management.RuntimeErrorException;
import java.util.ArrayList;
import java.util.List;

public class RedBlackTree<T extends Comparable<T>, V> implements IRedBlackTree<T, V> {
    private INode<T,V>root=new Node<>();
    private INode<T,V> current=root;
    @Override
    public INode<T,V> getRoot() {
        if(root.isNull())
            return null;
        return root;
    }

    @Override
    public boolean isEmpty() {
        return root.isNull();
    }

    @Override
    public void clear() {
        root=new Node<>();
        current =root;
    }

    @Override
    public V search(T key) {
        if(key==null)
            throw new RuntimeErrorException(new Error("null key inserted"));
        if(root.isNull()|| current.isNull())
        {
            current=root;
            return null;
        }
        if(current.getKey().compareTo(key)==0)
        {
            V answer= current.getValue();
            current =root;
            return answer;
        }
        if(current.getKey().compareTo(key)>0)
            current = current.getLeftChild();
        else
            current = current.getRightChild();
        return search(key);
    }

    @Override
    public boolean contains(T key) {
        V value= search(key);
        return value!=null;
    }

    @Override
    public void insert(T key, V value) {
        if(key==null)
            throw new RuntimeErrorException(new Error("null key inserted"));
        if(value==null)
            throw new RuntimeErrorException(new Error("null value inserted"));
        if(root.isNull())
        {
            root.setColor(false);
            root.setKey(key);
            root.setValue(value);
            root.setRightChild(new Node<>());
            root.setLeftChild(new Node<>());
            return;
        }
        if(contains(key))
        {
            Replace(key,value);
            return;
        }
        INode<T,V>parent=root;
        while(true)
        {
            if(current.isNull())
            {
                current =new Node<>();
                current.setColor(true);
                current.setKey(key);
                current.setValue(value);
                current.setParent(parent);
                current.setLeftChild(new Node<>());
                current.setRightChild(new Node<>());
                if(key.compareTo(parent.getKey())>0)
                    parent.setRightChild(current);
                else
                    parent.setLeftChild(current);
                //Balance(current);
                current=root;
                break;
            }
            if(current.getKey().compareTo(key)<0)
            {
                parent=current;
                current= current.getRightChild();
            }
            else
            {
                parent=current;
                current=current.getLeftChild();
            }
        }
    }
    private void Replace(T key,V value)
    {
        if(current.getKey().compareTo(key)==0)
        {
            current.setValue(value);
            current =root;
            return;
        }
        if(current.getKey().compareTo(key)>0)
            current = current.getLeftChild();
        else
            current = current.getRightChild();
        Replace(key,value);
    }
    private void LeftRotate(INode<T,V> x){
        INode<T,V> y=x.getRightChild();
        x.setRightChild(y.getLeftChild());
        if( (!y.getLeftChild().getLeftChild().isNull()) || (!y.getLeftChild().getRightChild().isNull()) ){
            y.getLeftChild().setParent(x);
        }
        y.setParent(x.getParent());
        if( (x.getParent().getLeftChild().isNull()) || (x.getParent().getRightChild().isNull())||x.getParent().isNull() ){
            this.root=y;
        }else if(x==x.getParent().getLeftChild()){
            x.getParent().setLeftChild(y);
        }else{
            x.getParent().setRightChild(y);
        }
        y.setLeftChild(x);
        x.setParent(y);
    }
    private void RightRotate(INode<T,V> y){
        INode<T,V> x;
        x=y.getLeftChild();
        y.setLeftChild(x.getRightChild());
        if( (!x.getRightChild().getLeftChild().isNull()) || (!x.getRightChild().getRightChild().isNull()) ){
            x.getRightChild().setParent(y);
        }
        x.setParent(y.getParent());
        if( (y.getParent().getLeftChild().isNull()) && (y.getParent().getRightChild().isNull()) ){
            this.root=x;
        }else if(y==y.getParent().getRightChild()){
            y.getParent().setRightChild(x);
        }else{
            y.getParent().setLeftChild(x);
        }
        x.setRightChild(y);
        y.setParent(x);
    }
    private void Balance(INode<T,V> node) {
        while(node.getParent().getColor()){
            if(node.getParent()==node.getParent().getParent().getLeftChild()){
                INode<T,V> y=node.getParent().getParent().getRightChild();
                if(y.getColor()){
                    node.getParent().setColor(false);
                    y.setColor(false);
                    node.getParent().getParent().setColor(true);
                    node=node.getParent().getParent();
                }else if(node==node.getParent().getRightChild()){
                    node=node.getParent();
                    LeftRotate(node);
                    node.getParent().setColor(false);
                    node.getParent().getParent().setColor(true);
                    RightRotate(node.getParent().getParent());
                }
            }else if(node.getParent()==node.getParent().getParent().getRightChild()){
                node=node.getParent();
                RightRotate(node);
                node.getParent().setColor(false);
                node.getParent().getParent().setColor(true);
                LeftRotate(node);
            }
        }
        this.root.setColor(false);
    }

    @Override
    public boolean delete(T key) {
        if(key==null)
            throw new RuntimeErrorException(new Error("null key inserted"));
        if(root.isNull()||!contains(key))
            return false;
        else
        {
            List<INode<T,V>> nodes=BSTDeletion(key);
            if(nodes.get(0).getColor()!=nodes.get(1).getColor())
            {
                INode<T,V>u=nodes.get(0);
                INode<T,V>v=nodes.get(1);
                v.setColor(false);
                v.setKey(u.getKey());
                v.setValue(u.getValue());
                v.setLeftChild(new Node<>());
                v.setRightChild(new Node<>());
            }
            else
            {
                Node<T,V>u= (Node<T, V>) nodes.get(0);
                Node<T,V>v= (Node<T, V>) nodes.get(1);
                u.setDoubleBlack(true);
                if (u.IsDoubleBlack()&&u!=root)
                {
                    INode<T,V>s;
                    if(RightChild(u))
                    {
                        s=u.getParent().getLeftChild();
                    }
                    else
                    {
                        s=u.getParent().getRightChild();
                        if(!s.getColor())
                        {
                            INode<T,V>r;
                            //s has a red child
                            if(s.getRightChild().getColor())
                            {
                                r=s.getRightChild();
                                v.setKey(u.getKey());
                                v.setValue(u.getValue());
                                u=new Node<>();
                            }
                        }
                    }
                    /*if(!s.getColor())
                    {
                        INode<T,V>r;
                        if(s.getLeftChild().getColor())
                            r=s.getLeftChild();
                        else
                            r=s.getRightChild();

                    }*/
                }
            }
        }
        return true;
    }
    //first element is leaf,second element is to be deleted
    private List<INode<T,V>> BSTDeletion(T key)
    {
        List<INode<T,V>> container=new ArrayList<>();
        while(current.getKey().compareTo(key)!=0)
        {
            if(current.getKey().compareTo(key)>0)
                current=current.getLeftChild();
            else
                current=current.getRightChild();
        }//No children
        if(current.getLeftChild().isNull()&&current.getRightChild().isNull())
        {
            container.add(current.getRightChild());
            container.add(current);
        }//One child Only
        else if(current.getLeftChild().isNull())
        {
            INode<T,V> tempNode=current.getRightChild();
            container.add(tempNode);
            container.add(current);
        }
        else if(current.getRightChild().isNull())
        {
            INode<T,V>tempNode=current.getLeftChild();
            container.add(tempNode);
            container.add(current);
        }//Both children
        else
        {
            INode<T,V>tempNode=current.getRightChild();
            while(!tempNode.getLeftChild().isNull())
                tempNode=tempNode.getLeftChild();
            container.add(tempNode);
            container.add(current);
        }
        return container;
    }
    private boolean RightChild(INode<T,V>node)
    {
        //right = true ...... left = false
        return node.getParent().getRightChild() == node;
    }
}