/**
 * <p>
 *     符號表的基本API
 * </p>
 * @author qzlzzz
 * @version 1.0
 * @since 2021/10/8
 */
public interface RedBlackBST<Key extends Comparable<Key>,Value> {

    /**
     * 根據(jù)Key在符號表中找到Value
     * @param key the key
     * @return the value of key
     */
    Value get(Key key);

    /**
     * 插入key-value，如果符號表中有Key，且Key不為空則將該Key的Value轉為傳入的Value
     * @param key the-key
     * @param value the-value
     */
    void put(Key key,Value value);

    /**
     * 根據(jù)Key去符號表中刪除Key
     * @param key the key
     */
    void delete(Key key);

}

    /**
     * 根據(jù)位置返回鍵，如果沒有返回null
     * @param k the index of key
     * @return the key
     */
    Key select(int k);

    /**
     * 返回紅黑樹中最小的鍵
     * @return the min key in this tree
     */
    Key min();

    /**
     * 返回紅黑樹中最大的鍵
     * @return the max key in this tree
     */
    Key max();

    /**
     * 返回小于該鍵的數(shù)量
     * @param key the key
     * @return amount of key small than the key
     */
    int rank(Key key);

/**
 * <h3>
 *     紅黑樹的實現(xiàn),博客:https://www.cnblogs.com/qzlzzz/p/15395010.html
 * </h3>
 * @author qzlzzz
 * @since 2021/10/12
 * @version 1.0
 */
public class RedBlackBST<Key extends Comparable<Key>,Value> {
    
        
    private Node root;//根節(jié)點

    //<父結點>指向自己<子結點>的鏈接是黑色的
    private static final boolean RED = true;

    //<父結點>指向自己<子結點>的鏈接是黑色的
    private static final boolean BLACK = false;

    /**
     * <p>紅黑樹的結點定義</p>
     * @author qzlzzz
     */
    private class Node{
        
        private boolean color;//指向該結點的鏈接的顏色
        
        private Key key;//鍵
        
        private Value value;//值
        
        private Node left,right;//該結點指向左結點的鏈接和右結點的鏈接
        
        private int n;//該子樹的結點樹

        public Node(Key key,Value value,boolean color,int n){
            this.key = key;
            this.value = value;
            this.color = color;
            this.n = n;
        }
    }
    
}

    /**
     * 計算紅黑樹的結點總數(shù),內部調用了{@link RedBlackBST#size(Node)}
     * @return
     */
    public int size(){
        return size(root);
    }

    //計算某個子樹的結點總數(shù)
    private int size(Node x){
        if (x == null) return 0;
        else return x.n;
    }

    /**
     * 將紅色右鏈接變?yōu)樽箧溄?，總體有序性不變，子樹結點數(shù)量不變
     * @param h
     * @return
     */
    private Node rotateLeft(Node h){
        Node t = h.right;
        h.right = t.left;
        t.left = h;
        t.color = h.color;
        h.color = RED;
        t.n = h.n;//轉換后子樹的結點是不變的，
        h.n = size(h.left) + size(h.right) + 1;
        return t;
    }

    //判斷鏈接是否為紅色，不是返回false
    private boolean isRed(Node x){
        if (x == null) return false;
        return x.color;
    }

    /**
     * <p>若左右兩邊的鏈接皆為紅色，將兩邊鏈接顏色設置為黑色，并使指向自己鏈接的顏色設為紅</p>
     * @param x
     */
    private void changeColor(Node x){
        x.color = true;
        x.left.color = false;
        x.right.color = true;
    }

    /**
     * 通過鍵來查找值，內部調用{@link RedBlackBST#get(Node, Comparable)}
     * @param key
     * @return
     */
    public Value get(Key key){
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        return get(root,key);
    }
    
    private Value get(Node x,Key key){
        for (;;){
            if (x == null) return null;
            int cmp = key.compareTo(x.key);
            if (cmp == 0) return x.value;
            else if (cmp < 0) x = x.left;
            else x = x.right;
        }
    }

    /**
     * 插入鍵值對,內部使用{@link RedBlackBST#put(Node, Comparable, Object)}
     * @param key
     * @param value
     */
    public void put(Key key,Value value){
        if (key == null) throw new IllegalArgumentException("argument to put() is null");
        root = put(root,key,value);
        root.color = false;
    }

    private Node put(Node x,Key key,Value value){
        if (x == null) return new Node(key,value,RED,1);
        int cmp = key.compareTo(x.key);
        if (cmp == 0) {x.value = value;}
        else if (cmp < 0) x.left = put(x.left,key,value);
        else x.right = put(x.right,key,value);
        
        if (isRed(x.right) && !isRed(x.left)) x = rotateLeft(x);
        if (isRed(x.left) && isRed(x.left.left)) x = rotateRight(x);
        if (isRed(x.left) && isRed(x.right)) changeColor(x);
        
        x.n = size(x.left) + size(x.right) + 1;
        return x;
    }

    /**
     * 根據(jù)位置返回鍵,內部調用{@link RedBlackBST#select(Node, int)}
     * @param k
     * @return
     */
    public Key select(int k){
        return select(root,k);
    }

    private Key select(Node x,int k){
        while(x != null){
            int t = x.left.N;
            if (t > k) x = x.left;
            else if (t < k){
                x = x.right;
                k = k - t - 1;
            }
            else return x.key;
        }
        return null;
    }

    /**
     * 根據(jù)鍵，返回該鍵的數(shù)量，內部調用{@link RedBlackBST#rank(Node, Comparable)}
     * @param key
     * @return
     */
    public int rank(Key key){
        return rank(root,key);
    }

    private int rank(Node x,Key key){
        while (x != null){
            int cmp = key.compareTo(x.key);
            int count = x.left.N;
            if (cmp == 0) return (count < root.N ? count : 1 + root.left.N + count);
            else if (cmp < 0) x = x.left;
            else x = x.right;
        }
        return 0;
    }