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

import javax.management.RuntimeErrorException;

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() {
        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());
        if(current.isNull()||root.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) {
        current=root;
        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(contains(key))
        {
            Replace(key,value);
            return;
        }
        INode<T,V>NewNode=new Node<>();
        NewNode.setLeftChild(new Node<>());NewNode.setRightChild(new Node<>());
        NewNode.setKey(key);NewNode.setValue(value);
        NewNode.setColor(true);
        if(root.isNull())
        {
            NewNode.setColor(false);
            root=NewNode;
        }
        else
        {
            INode<T,V>temp=BSTSearch(key);
            NewNode.setParent(temp);
            if(key.compareTo(temp.getKey())<0)
                temp.setLeftChild(NewNode);
            else
                temp.setRightChild(NewNode);
            FixRedRed(NewNode);
        }
    }
    private void FixRedRed(INode<T,V>node)
    {
        if(node==root)
        {
            node.setColor(false);
            return;
        }
        INode<T,V>parent=node.getParent(),grandparent=parent.getParent(),uncle;
        if(grandparent==null)
            uncle=null;
        else
        {
            if(RightChild(parent))
                uncle=grandparent.getLeftChild();
            else
                uncle=grandparent.getRightChild();
        }
        if(parent.getColor())
        {
            if(uncle!=null&&uncle.getColor())
            {
                parent.setColor(false);
                uncle.setColor(false);
                grandparent.setColor(true);
                FixRedRed(grandparent);
            }
            else
            {
                if(!RightChild(parent))
                {
                    if(!RightChild(node))
                    {
                        boolean temp=parent.getColor();
                        parent.setColor(grandparent.getColor());
                        grandparent.setColor(temp);
                    }
                    else
                    {
                        LeftRotate(parent);
                        boolean temp=node.getColor();
                        node.setColor(grandparent.getColor());
                        grandparent.setColor(temp);
                    }
                    RightRotate(grandparent);
                }
                else
                {
                    if(!RightChild(node))
                    {
                        RightRotate(parent);
                        boolean temp=node.getColor();
                        node.setColor(grandparent.getColor());
                        grandparent.setColor(temp);
                    }
                    else
                    {
                        boolean temp=parent.getColor();
                        parent.setColor(grandparent.getColor());
                        grandparent.setColor(temp);
                    }
                    LeftRotate(grandparent);
                }
            }
        }
    }
    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();
        if(x==root)
            root=y;
        MoveDown(y,x);
        x.setRightChild(y.getLeftChild());
        if(!y.getLeftChild().isNull())
            y.getLeftChild().setParent(x);
        y.setLeftChild(x);
    }
    private void RightRotate(INode<T,V> x){
        INode<T,V> y=x.getLeftChild();
        if(x==root)
            root=y;
        MoveDown(y,x);
        x.setLeftChild(y.getRightChild());
        if(!y.getRightChild().isNull())
            y.getRightChild().setParent(x);
        y.setRightChild(x);
    }

    private void MoveDown(INode<T,V>y,INode<T,V>x)
    {
        if(x.getParent()!=null)
        {
            if (!RightChild(x))
                x.getParent().setLeftChild(y);
            else
                x.getParent().setRightChild(y);
        }
        y.setParent(x.getParent());
        x.setParent(y);
    }

    @Override
    public boolean delete(T key) {
        if(key==null)
            throw new RuntimeErrorException(new Error("null key inserted"));
        if(root.isNull()||!contains(key))
        {
            System.out.println(key+" & "+current.getKey());
            return false;
        }
        DeleteNode(BSTSearch(key));
        return true;
    }
    private void DeleteNode(INode<T,V>v)
    {
        INode<T,V>u=BSTReplace(v);
        boolean BothBlack=((u.isNull()||!u.getColor())&&!v.getColor());
        INode<T,V>parent=v.getParent();
        if(u.isNull())
        {
            if(v==root)
                root=new Node<>();
            else
            {
                if(BothBlack)
                    FixDoubleBlack(v);
                else
                {
                    if(RightChild(v))
                    {
                        if(!v.getParent().getLeftChild().isNull())
                            v.getParent().getLeftChild().setColor(true);
                    }
                    else
                    {
                        if(!v.getParent().getRightChild().isNull())
                            v.getParent().getRightChild().setColor(true);
                    }
                }
                if(!RightChild(v))
                    parent.setLeftChild(new Node<>());
                else
                    parent.setRightChild(new Node<>());
            }
            v.setColor(false);
            v.setKey(null);
            v.setValue(null);
            v.setRightChild(new Node<>());
            v.setLeftChild(new Node<>());
            v.setParent(null);//TODO check
            current=root;
            return;
        }
        if(v.getRightChild().isNull()||v.getLeftChild().isNull())
        {
            if(v==root)
            {
                v.setValue(u.getValue());
                v.setKey(u.getKey());
                v.setLeftChild(new Node<>());
                v.setRightChild(new Node<>());
                u.setColor(false);
                u.setKey(null);
                u.setValue(null);
                u.setRightChild(new Node<>());
                u.setLeftChild(new Node<>());
                u.setParent(null);//TODO check
            }
            else
            {
                if(!RightChild(v))
                    parent.setLeftChild(u);
                else
                    parent.setRightChild(u);
                v.setColor(false);
                v.setKey(null);
                v.setValue(null);
                v.setRightChild(new Node<>());
                v.setLeftChild(new Node<>());
                v.setParent(null);//TODO check
                u.setParent(parent);
                if(BothBlack)
                    FixDoubleBlack(u);
                else
                    u.setColor(false);
            }
            current=root;
            return;
        }
        T TempKey=u.getKey();V TempValue=u.getValue();
        u.setValue(v.getValue());u.setKey(v.getKey());
        v.setValue(TempValue);v.setKey(TempKey);
        current=root;
        DeleteNode(u);
    }
    private void FixDoubleBlack(INode<T,V>node)
    {
        if(node==root)
            return;
        INode<T,V>sibling,parent=node.getParent();
        if(RightChild(node))
            sibling=node.getParent().getLeftChild();
        else
            sibling=node.getParent().getRightChild();
        if(sibling.isNull())
            FixDoubleBlack(parent);
        else
        {
            if (sibling.getColor()) {
                parent.setColor(true);
                sibling.setColor(false);
                if (!RightChild(sibling))
                    RightRotate(parent);
                else
                    LeftRotate(parent);
                FixDoubleBlack(node);
            }
            else
            {
                if(!sibling.getLeftChild().isNull()&&sibling.getLeftChild().getColor()||!sibling.getRightChild().isNull()&&sibling.getRightChild().getColor())
                {
                    if(!sibling.getLeftChild().isNull()&&sibling.getLeftChild().getColor())
                    {
                        if(!RightChild(sibling))
                        {
                            sibling.getLeftChild().setColor(sibling.getColor());
                            sibling.setColor(parent.getColor());
                            RightRotate(parent);
                        }
                        else
                        {
                            sibling.getLeftChild().setColor(parent.getColor());
                            RightRotate(sibling);
                            LeftRotate(parent);
                        }
                    }
                    else
                    {
                        if(!RightChild(sibling))
                        {
                            sibling.getRightChild().setColor(parent.getColor());
                            LeftRotate(sibling);
                            RightRotate(parent);
                        }
                        else
                        {
                            sibling.getRightChild().setColor(sibling.getColor());
                            sibling.setColor(parent.getColor());
                            LeftRotate(parent);
                        }
                    }
                    parent.setColor(false);
                }
                else
                {
                    sibling.setColor(true);
                    if(!parent.getColor())
                        FixDoubleBlack(parent);
                    else
                        parent.setColor(false);
                }
            }
        }
    }
    private INode<T,V> BSTSearch(T key)
    {
        INode<T,V>temp=root;
        while (!temp.isNull())
        {
            if(key.compareTo(temp.getKey())<0)
            {
                if(temp.getLeftChild().isNull())
                    break;
                else
                    temp=temp.getLeftChild();
            }else if (key.compareTo(temp.getKey())==0)
                break;
            else
            {
                if(temp.getRightChild().isNull())
                    break;
                else
                    temp=temp.getRightChild();
            }
        }
        return temp;
    }
    private INode<T,V>BSTReplace(INode<T,V> node)
    {
        if(!node.getLeftChild().isNull()&&!node.getRightChild().isNull())
        {
            INode<T,V>temp=node.getRightChild();
            while (!temp.getLeftChild().isNull())
                temp=temp.getLeftChild();
            return temp;
        }
        if(node.getLeftChild().isNull()&&node.getRightChild().isNull())
            return node.getRightChild();
        if(!node.getLeftChild().isNull())
            return node.getLeftChild();
        return node.getRightChild();
    }
    private boolean RightChild(INode<T,V>node)
    {
        return node.getParent().getRightChild() == node;
    }
}