/**
 * This work is based on https://deegen1.github.io/wbtree/index.html
 *
 * WBTreeSetBase.py - v1.01
 * Copyright 2022 Alec Dee - MIT license - SPDX: MIT
 * deegen1.github.io - akdee144@gmail.com
 *
 * This class implements reasonable interface for weight balanced tree, but it is not java-opinionated
 * For example, it does not care about Iterators, sub-sets, submaps, spliterators etc
 *
 * We use this structure inside SortedSet and SortedMap classes.
 * WBTreeSet and WBTreeMap implement all java idioms, when core algorithmic stuff is stored here.
 *
 * Such decomposition makes few things somewhat less effective (e.g. map contains double-wrapped entries) but
 * it allows us to synchronize with python original source code.
 */
package net.ranides.assira.collection.sets;

import net.ranides.assira.generic.CompareUtils;

import java.io.Serializable;
import java.util.Comparator;
import java.util.function.Consumer;

class WBTreeSetBase<V> implements Serializable {

    private static final long serialVersionUID = 2L;

    enum FindMode {
        EQ,
        EQG,
        LT,
        LE,
        GT,
        GE
    }

    private final Comparator<? super V> cmp;
    private final boolean unique;
    private Node<V> root;

    public WBTreeSetBase() {
        this(CompareUtils.comparator(), true);
    }

    public WBTreeSetBase(Comparator<? super V> cmp, boolean unique) {
        this.cmp = cmp;
        this.unique = unique;
        this.root = null;
    }

    public void clear() {
        this.root = null;
    }

    public int size() {
        return weight(root);
    }

    public Node<V> at(int i) {
        Node<V> node = root;
        int weight = size();
        if(i<0) {
            i += weight;
        }
        if(i<0 || i>=weight) {
            return null;
        }
        while (true) {
            Node<V> left = node.left;
            int lw = weight(left);
            if(i > lw) {
                i -= lw +1;
                node = node.right;
            }
            else if(i == lw) {
                break;
            } else {
                node = left;
            }
        }
        return node;
    }

    public void forEach(Consumer<V> consumer) {
        forEachNode(node -> consumer.accept(node.value));
    }

    void forEachNode(Consumer<Node<V>> consumer) {
        Node<V> node = first();
        while(node != null) {
            consumer.accept(node);
            node = next(node);
        }
    }

    public Node<V> first() {
        Node<V> node = root;
        Node<V> ret = null;

        while(node != null) {
            ret = node;
            node = node.left;
        }

        return ret;
    }

    public Node<V> last() {
        Node<V> node = root;
        Node<V> ret = null;

        while (node != null) {
            ret = node;
            node = node.right;
        }

        return ret;
    }

    public Node<V> find(V value) {
        return find(value, FindMode.EQ);
    }

    public Node<V> find(V value, FindMode mode) {
        Node<V> node = root;
        Node<V> ret = null;

        boolean lset = mode == FindMode.LT || mode == FindMode.LE;
        boolean rset = mode == FindMode.GT || mode == FindMode.GE;
        boolean eset = mode == FindMode.EQ || mode == FindMode.EQG || mode == FindMode.LE || mode == FindMode.GE;
        boolean eright = mode == FindMode.EQG || mode == FindMode.LE || mode == FindMode.GT;

        while(node != null) {
            int c = cmp.compare(node.value, value);
            if(c < 0) {
                if(lset) {
                    ret = node;
                }
                node = node.right;
            }
            else if(c > 0) {
                if(rset) {
                    ret = node;
                }
                node = node.left;
            }
            else {
                if(eset) {
                    ret = node;
                    if(unique) {
                        break;
                    }
                }
                node = eright ? node.right : node.left;
            }
        }

        return ret;
    }

    public Node<V> add(V value) {
        Node<V> prev = null;
        Node<V> node = root;
        int c = 0;
        while(node != null) {
            c = cmp.compare(node.value, value);
            if(c == 0 && this.unique) {
                node.value = value;
                return node;
            }
            prev = node;
            if(c <= 0) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        node = new Node<>(value);
        node.parent = prev;
        if(prev == null) {
            this.root = node;
        } else {
            if(c <=0) {
                prev.right = node;
            } else {
                prev.left = node;
            }
            rebalance(prev);
        }
        return node;
    }

    public Node<V> remove(V value) {
        Node<V> node = find(value);
        if(node != null) {
            removeNode(node);
        }
        return node;
    }

    public void removeNode(Node<V> node) {
        Node<V> p = node.parent;
        Node<V> l = node.left;
        Node<V> r = node.right;
        Node<V> bal = null;
        Node<V> next = null;

        if(r == null) {
            // case 1
            bal = p;
            next = l;
            l = null;
        }
        else if(r.left != null) {
            // case 3
            next = r;
            while(next.left != null) {
                bal = next;
                next = next.left;
            }
            Node<V> c = next.right;
            bal.left = c;
            if(c != null) {
                c.parent = bal;
            }
        }
        else {
            // case 2
            bal = r;
            next = r;
            r = null;
        }
        // replace node with next
        if(p == null) {
            root = next;
        }
        else if(p.left == node) {
            p.left = next;
        }
        else {
            p.right = next;
        }

        if(next != null) {
            next.parent = p;
            if(l != null) {
                next.left = l;
                l.parent = next;
            }
            if(r != null) {
                next.right = r;
                r.parent = next;
            }
        }

        rebalance(bal);
    }

    void rebalance(Node<V> next) {
        while (next != null) {
            Node<V> node = next;
            Node<V> orig = next;
            next = node.parent;

            Node<V> l = node.left;
            Node<V> r = node.right;
            int lw = weight(l);
            int rw = weight(r);

            if(rw * 5 + 2< lw * 2) {
                if(weight(l.left) * 5 < lw *2) {
                    node.left = rotateLeft(l);
                }
                node = rotateRight(node);
            }
            else if (lw * 5 + 2 < rw * 2) {
                if( weight(r.right) * 5 < rw*2) {
                    node.right = rotateRight(r);
                }
                node = rotateLeft(node);
            }
            else {
                node.weight = lw + rw + 1;
                continue;
            }
            if(next == null) {
                this.root = node;
            }
            else if(next.left == orig) {
                next.left = node;
            }
            else {
                next.right = node;
            }
        }
    }

    public static int weight(Node<?> node) {
        return node != null ? node.weight : 0;
    }

    public static <V> Node<V> next(Node<V> node) {
        Node<V> child = node.right;
        if(child != null) {
            while(child != null) {
                node = child;
                child = child.left;
            }
        } else {
            while(node != null && node.right == child) {
                child = node;
                node = node.parent;
            }
        }
        return node;
    }

    public static <V> Node<V> prev(Node<V> node) {
        Node<V> child = node.left;
        if(child != null) {
            while(child != null) {
                node = child;
                child = child.right;
            }
        } else {
            while(node != null && node.left == child) {
                child = node;
                node = node.parent;
            }
        }
        return node;
    }

    public static <V> Node<V> rotateLeft(Node<V> a) {
        Node<V> b=a.right;
        Node<V> r=b.left;
        b.parent=a.parent;
        b.left=a;
        a.parent=b;
        a.right=r;
        if (r != null) {
            r.parent = a;
        }
        recomputeWeight(a);
        recomputeWeight(b);
        return b;
    }

    public static <V> Node<V> rotateRight(Node<V> a) {
        Node<V> b = a.left;
        Node<V> l = b.right;
        b.parent = a.parent;
        b.right = a;
        a.parent = b;
        a.left = l;
        if (l != null) {
            l.parent = a;
        }
        recomputeWeight(a);
        recomputeWeight(b);
        return b;
    }

    public static void recomputeWeight(Node<?> node) {
        node.weight = 1 + weight(node.left) + weight(node.right);
    }

    public static int indexOf(Node<?> node) {
        if(node == null) {
            return -1;
        }
        int i = -1;
        Node<?> prev = node.right;
        while (node != null) {
            if (node.right == prev) {
                i += weight(node.left) + 1;
            }
            prev = node;
            node = node.parent;
        }
        return i;
    }

    public static class Node<V> implements Serializable {

        private static final long serialVersionUID = 2L;

        public int weight;
        public Node<V> parent;
        public Node<V> left;
        public Node<V> right;
        public V value;

        public Node(V value) {
            this.weight = 1;
            this.parent = null;
            this.left = null;
            this.right = null;
            this.value = value;
        }
    }




}
