/*
Marcel Hanser

I create a class, My Comparator, where i make my compare method
I make a Constructor of my Heap with my Comparator
For my Enqueue I merge my _root with my new Node
If one of the is null, i can just return the other
I use my Comparator to check if my _root or my new Node has a higher Priority
If my new Node has a higher Priority, I swap the 2
I recursively call my merge and use the right of my higher priority
to merge with the other until i get to a null. If i get there I return the other


 */


import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

public class BHeap<T> implements Comparator<T> {
    Comparator _comparetor;
    Node _root;


    public BHeap(Comparator<T> comparator) {
        _comparetor = comparator;
    }

    public void Enqueue(T value) {
        _root = merge(_root, new Node(value));
    }

    private Node merge(Node r1, Node r2) {
        if (r1 == null) {
            return r2;
        }
        if (r2 == null) {
            return r1;
        }
        if (_comparetor.compare(r1.get_value(), r2.get_value()) > 0) {
            Node temp = r1;
            r1 = r2;
            r2 = temp;
        }

        r1.set_right(merge(r1.get_right(),r2));

        if (r1.get_left() == null) {
            r1.set_left(r1.get_right());
            r1.set_right(null);
        } else {
            if (r1.get_left().get_s() < r1.get_right().get_s()) {
                Node temp = r1.get_left();
                r1.set_left(r1.get_right());
                r1.set_right(temp);
            }
            r1.set_s(r1.get_right().get_s() + 1);
        }
        return r1;
    }

    public boolean isEmpty() {
        return (_root == null);
    }

    public T Dequeue() {
        if (isEmpty()) {
            return null;
        }
        T value = (T) _root.get_value();
        _root = merge(_root.get_left(),_root.get_right());
        return value;
    }

    @Override
    public int compare(T o1, T o2) {
        return _comparetor.compare(o1,o2);
    }

    public void debugPrint() {
        level(_root);
    }

    private void level(Node root) {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        Node n = new Node();
        while (!q.isEmpty()) {
            n = q.remove();
            System.out.println(n.get_value());
            if (n.get_left() != null) {
                System.out.println("Left Child: " + n.get_left().get_value());
            }
            if (n.get_right() != null) {
                System.out.println("Right Child: " + n.get_right().get_value());
            }
            System.out.println();
            if (n.get_left() != null) {
                q.add(n.get_left());
            }
            if (n.get_right() != null) {
                q.add(n.get_right());
            }
        }
    }


}




import java.util.Comparator;

public class MyComparator<T extends Comparable> implements Comparator<T>
{
    public int compare(T value1, T value2)
    {
        return value1.compareTo(value2);
    }
}



public class Node<T> {
    T _value;
    private Node _left;

    public int get_s() {
        return _s;
    }

    public void set_s(int _s) {
        this._s = _s;
    }

    private int _s;

    public T get_value() {
        return _value;
    }

    public void set_value(T _value) {
        this._value = _value;
    }

    public Node get_left() {
        return _left;
    }

    public void set_left(Node _left) {
        this._left = _left;
    }

    public Node get_right() {
        return _right;
    }

    public void set_right(Node _right) {
        this._right = _right;
    }

    private Node _right;

    public Node() {
        _s = 0;
    }

    public  Node(T value) {
        _value = value;
        _s = 0;
    }
}







/*
Marcel Hanser
Uebung 5-1
RB Tree
Insert
I insert every RBNode as red and then i Rebalance
There I have 3 Cases
Case 1: I'm at the root, I just color it black
Case 2: Parent is Red and Uncle is Red,
        also easy, I color Grandparent, Parent and Uncle Black and if
        Grandparent is the root
Case 3: Uncle is Black or null
        I have to rotate, to the left or right, depending where the uncle is
        if Uncle is on the other side as the child (e.g. uncle is left, child is a right child)
        I rotate the parent to the other side and recolor uncle and parent
        if they're on the same side, i rotate the grandparent and Rebalance again at the
        node that is now the child of my inserted node to make the RBTree right again

If i rotate the _root, i also have to set the root to the new _root

 */

import java.util.LinkedList;
import java.util.Queue;

public class RBTree<T extends Comparable> {

    private RBNode _root;
    private RBNode _insertedNode;

    public void rBinsert(T x) {
        _root = insert(_root, x, null);
        Rebalance();
    }


    private RBNode insert(RBNode root, T insKey, RBNode parent) {
        if (root == null) {
            _insertedNode = new RBNode(insKey, true, parent);
            return _insertedNode;
        }
        if (root.get_key().compareTo(insKey) >= 0) {
            root.set_left(insert(root.get_left(), insKey, root));
        } else {
            root.set_right(insert(root.get_right(), insKey, root));
        }
        return root;
    }


    private void Rebalance() {
        if (_insertedNode == _root) { //Case 1: I'm at the root
            _insertedNode.set_isRed(false);
        } else {
            if (_insertedNode.get_parent().isRed()) { //Case 2
                if (_insertedNode.get_key().compareTo(_insertedNode.get_parent().get_parent().get_key()) >= 0) { // if uncle is to the left
                    if (_insertedNode.get_parent().get_parent().get_left() != null && _insertedNode.get_parent().get_parent().get_left().isRed()) { //case3: if uncle is red
                        _insertedNode.get_parent().get_parent().set_isRed(true);
                        _insertedNode.get_parent().set_isRed(false);
                        _insertedNode.get_parent().get_parent().get_left().set_isRed(false);
                        _insertedNode = _insertedNode.get_parent().get_parent();
                        Rebalance();
                    } else {
                        if (_insertedNode.get_parent().get_key().compareTo(_insertedNode.get_key()) < 0) { //if insertedNode is a right child
                            RBNode grandGrandParent = new RBNode();
                            grandGrandParent = null;
                            if (_insertedNode.get_parent().get_parent().get_parent() != null) {
                                grandGrandParent = _insertedNode.get_parent().get_parent().get_parent();
                            }
                            if (grandGrandParent == null) {
                                rotateLeft(_insertedNode.get_parent().get_parent());
                                _root = _insertedNode.get_parent();
                            }
                            else {
                                if (grandGrandParent.get_right() == _insertedNode.get_parent().get_parent()) {
                                    grandGrandParent.set_right((rotateLeft(_insertedNode.get_parent().get_parent())));
                                }
                                else {
                                    grandGrandParent.set_left((rotateLeft(_insertedNode.get_parent().get_parent())));
                                }
                            }
                            _insertedNode.get_parent().get_left().set_isRed(true);
                            _insertedNode.get_parent().set_isRed(false);
                            _insertedNode = _insertedNode.get_parent();
                        } else {
                            RBNode grandParent = null;
                            if (_insertedNode.get_parent().get_parent() != null) {
                                grandParent = _insertedNode.get_parent().get_parent();
                            }
                            if (grandParent == null) {
                                rotateRight(_insertedNode.get_parent());
                                _root = _insertedNode.get_parent();
                            }
                            else {
                                if (grandParent.get_right() == _insertedNode.get_parent().get_parent()) {
                                    grandParent.set_right((rotateRight(_insertedNode.get_parent())));
                                }
                                else {
                                    grandParent.set_right((rotateRight(_insertedNode.get_parent())));
                                }
                            }
                            if (_insertedNode.get_right() != null) {
                                _insertedNode = _insertedNode.get_right();
                            }
                            Rebalance();
                        }
                    }
                } else { // if uncle is to the right
                    if (_insertedNode.get_parent().get_parent().get_right() != null && _insertedNode.get_parent().get_parent().get_right().isRed()) { //case3: if uncle is red
                        _insertedNode.get_parent().get_parent().set_isRed(true);
                        _insertedNode.get_parent().set_isRed(false);
                        _insertedNode.get_parent().get_parent().get_right().set_isRed(false);
                        _insertedNode = _insertedNode.get_parent().get_parent();
                        Rebalance();
                    } else {
                        if (_insertedNode.get_parent().get_key().compareTo(_insertedNode.get_key()) < 0) { //if insertedNode is a right child
                            RBNode grandParent = null;
                            if (_insertedNode.get_parent().get_parent() != null) {
                                grandParent = _insertedNode.get_parent().get_parent();
                            }
                            if (grandParent == null) {
                                rotateLeft(_insertedNode.get_parent());
                                _root = _insertedNode.get_parent();
                            }
                            else {
                                if (grandParent.get_left() == _insertedNode.get_parent().get_parent()) {
                                    grandParent.set_left((rotateLeft(_insertedNode.get_parent())));
                                }
                                else {
                                    grandParent.set_left((rotateLeft(_insertedNode.get_parent())));
                                }
                            }
                            if (_insertedNode.get_left() != null) {
                                _insertedNode = _insertedNode.get_left();
                            }
                            Rebalance();
                        }
                        else {
                            RBNode grandGrandParent = new RBNode();
                            grandGrandParent = null;
                            if (_insertedNode.get_parent().get_parent().get_parent() != null) {
                                grandGrandParent = _insertedNode.get_parent().get_parent().get_parent();
                            }
                            if (grandGrandParent == null) {
                                rotateRight(_insertedNode.get_parent().get_parent());
                                _root = _insertedNode.get_parent();
                            }
                            else {
                                if (grandGrandParent.get_right() == _insertedNode.get_parent().get_parent()) {
                                    grandGrandParent.set_right((rotateRight(_insertedNode.get_parent().get_parent())));
                                }
                                else {
                                    grandGrandParent.set_left((rotateRight(_insertedNode.get_parent().get_parent())));
                                }
                            }

                            _insertedNode.get_parent().get_right().set_isRed(true);
                            _insertedNode.get_parent().set_isRed(false);
                            _insertedNode = _insertedNode.get_parent();
                        }
                    }
                }
            }
        }
    }

    private RBNode rotateLeft(RBNode root) {
        root.get_right().set_parent(root.get_parent());
        root.set_parent(root.get_right());
        root.set_right(root.get_right().get_left());
        root.get_parent().set_left(root);
        if (root.get_right() != null) {
            root.get_right().set_parent(root);
        }
        root = root.get_parent();
        return root;
    }

    private RBNode rotateRight(RBNode root) {
        root.get_left().set_parent(root.get_parent());
        root.set_parent(root.get_left());
        root.set_left(root.get_left().get_right());
        root.get_parent().set_right(root);
        if (root.get_left() != null) {
            root.get_left().set_parent(root);
        }
        root = root.get_parent();
        return root;
    }

    public int getRBHeight() {
        RBNode root = _root;
        int i = 0;
        while (root != null) {
            if (!root.isRed()) {
                i++;
            }
            root = root.get_left();
        }
        return i;
    }


    public void debugPrint() {
        level(_root);
    }

    private void level(RBNode root) {
        Queue<RBNode> q = new LinkedList<>();
        q.add(root);
        RBNode n = new RBNode();
        while (!q.isEmpty()) {
            n = q.remove();
            System.out.print(n.get_key() + " Color: ");
            if (n.isRed()) {
                System.out.println("Red");
            }
            else {
                System.out.println("Black");
            }
            if (n.get_parent() != null) {
                System.out.println("Parent: " + n.get_parent().get_key());
            }
            if (n.get_left() != null) {
                System.out.println("Left Child: " + n.get_left().get_key());
            }
            if (n.get_right() != null) {
                System.out.println("Right Child: " + n.get_right().get_key());
            }
            System.out.println();
            if (n.get_left() != null) {
                q.add(n.get_left());
            }
            if (n.get_right() != null) {
                q.add(n.get_right());
            }
        }
    }
}





public class RBNode<T extends  Comparable> {
    private RBNode _left;
    private RBNode _right;
    private RBNode _parent;
    private boolean _isRed;//true = red -- falese = black
    private T _key;

    public RBNode() {

    }

    public RBNode(T key) {
        _key = key;
    }

    public RBNode(T key, boolean isRed) {
        _key = key;
        _isRed = isRed;
    }

    public RBNode(T key, boolean isRed, RBNode parent) {
        _key = key;
        _isRed = isRed;
        _parent = parent;
    }

    public RBNode get_left() {
        return _left;
    }

    public void set_left(RBNode left) {
        _left = left;
    }

    public RBNode get_right() {
        return _right;
    }

    public void set_right(RBNode right) {
        _right = right;
    }

    public RBNode get_parent() {
        return _parent;
    }

    public void set_parent(RBNode parent) {
        _parent = parent;
    }

    public boolean isRed() {
        return _isRed;
    }

    public void set_isRed(boolean isRed) {
        _isRed = isRed;
    }

    public T get_key() {
        return _key;
    }

    public void set_Key(T key) {
        _key = key;
    }



}