// based on: https://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html

// TODO: implement NavigableSet

// RAM use in a CompressedOOPS JVM (bytes per element):

//   ~12   when elements are inserted in sorted order

//   ~13.7 when elements are inserted in random order

//

// (Obviously more for very small sets. Size 1 is now optimized 24 bytes.)

sclass HyperCompactTreeSet<A> extends AbstractSet<A> {

  // A symbol table implemented using a left-leaning red-black BST.

  // This is the 2-3 version.

  // Note: We sometimes cast the nullSentinel to A

  // which is technically incorrect but ok because of type erasure.

  // May want to fix just to be clean on the source level too.

  private static final boolean RED   = true;

  private static final boolean BLACK = false;

  // replacement for null elements

  private static final new O nullSentinel;

  // root of the BST (null, Node or sentinelled user object)

  // in the latter case it is assumed to be red

  private O root;

  int size; // size of tree set

  // BST helper node data type

  abstract sclass Node<A> {

    A val;         // associated data

    Node<A> left() { null; } // get left subtree

    abstract Node<A> setLeft(Node<A> left); // set left subtree - return potentially replaced node

    Node<A> right() { null; } // get right subtree

    abstract Node<A> setRight(Node<A> right); // set right subtree - return potentially replaced node

    abstract bool color();

    abstract Node<A> convertToBlack();

    abstract Node<A> convertToRed();

    abstract Node<A> invertColor();

    Node<A> convertToColor(bool color) { ret color == RED ? convertToRed() : convertToBlack(); }

    abstract bool isLeaf();

  }

  // This represents a common case near a red leaf - a black node

  // containing a red leaf in the left slot and null in the right slot.

  // Combined with the direct storage of black leaf children in NonLeaf,

  // this is all we need to get rid of all the leaf overhead. Yay!

  sclass SpecialNode<A> extends Node<A> {

    A leftVal;

    *(A *leftVal, A *val) {}

    bool color() { ret BLACK; }

    Node<A> convertToBlack() { this; }

    Node<A> convertToRed() { ret newNode(RED, val, left(), right()); }

    Node invertColor() { ret convertToRed(); }

    Node<A> left() {

      ret newLeaf(RED, leftVal);

    }

    Node<A> setLeft(Node<A> left) {

      // Can we keep the optimized representation? (Probably this

      // is never going to be true.)

      if (left != null && left.isLeaf() && left.color() == RED)

        ret this with leftVal = left.val;

      else

        ret newNode(BLACK, val, left, right());

    }

    Node<A> right() {

      null;

    }

    Node<A> setRight(Node<A> right) {

      if (right == null) this;

      ret newNode(color(), val, left(), right);

    }

    bool isLeaf() { false; }

  }

  asclass NonLeaf<A> extends Node<A> {

    // either a Node or a (sentinelled) direct user value

    O left, right;

    // color of leaf if left is a user value

    bool defaultLeftLeafColor() { ret BLACK; }

    // color of leaf if right is a user value

    bool defaultRightLeafColor() { ret BLACK; }

    Node<A> left() {

      ret left == null ? null

        : left instanceof Node ? (Node) left

        : newLeaf(defaultLeftLeafColor(), (A) left);

    }

    void setLeft_noMorph(Node<A> left) {

      this.left = left != null && left.isLeaf() && left.color() == defaultLeftLeafColor() ? left.val : left;

    }

    void setRight_noMorph(Node<A> right) {

      this.right = right != null && right.isLeaf() && right.color() == defaultRightLeafColor() ? right.val : right;

    }

    Node<A> setLeft(Node<A> left) {

      ifndef HyperCompactTreeSet_disableSpecialNodes

      if (color() == BLACK && right == null && left != null && left.isLeaf() && left.color() == RED)

        ret new SpecialNode(left.val, val);

      endifndef

      setLeft_noMorph(left);

      if (left == null && right() == null) ret newLeaf(color(), val);

      this;

    }

    Node<A> right() {

      ret right == null ? null

        : right instanceof Node ? (Node) right

        : newLeaf(defaultRightLeafColor(), (A) right);

    }

    Node<A> setRight(Node<A> right) {

      // Setting right to null may produce either a leaf or a

      // special node, so we just go through newNode.

      if (right == null && this.right != null)

        ret newNode(color(), val, left(), null);

      // New right is not null, so we compress (if possible) and store it

      setRight_noMorph(right);

      this;

    }

    bool isLeaf() { false; }

  }

  sclass BlackNode<A> extends NonLeaf<A> {

    *(A *val) {}

    bool color() { ret BLACK; }

    Node<A> convertToBlack() { this; }

    Node<A> convertToRed() { ret newNode(RED, val, left(), right()); }

    Node invertColor() { ret convertToRed(); }

  }

  sclass RedNode<A> extends NonLeaf<A> {

    *(A *val) {}

    bool color() { ret RED; }

    Node<A> convertToBlack() { ret newNode(BLACK, val, left(), right()); }

    Node<A> convertToRed() { this; }

    Node invertColor() { ret convertToBlack(); }

  }

  asclass Leaf<A> extends Node<A> {

    bool isLeaf() { true; }

    Node<A> setLeft(Node<A> left) {

      ret left == null ? this : newNode(color(), val, left, null);

    }

    Node<A> setRight(Node<A> right) {

      ret right == null ? this : newNode(color(), val, null, right);

    }

  }

  sclass BlackLeaf<A> extends Leaf<A> {

    *(A *val) {}

    bool color() { ret BLACK; }

    Node<A> convertToBlack() { this; }

    Node<A> convertToRed() { ret new RedLeaf(val); }

    Node invertColor() { ret convertToRed(); }

  }

  sclass RedLeaf<A> extends Leaf<A> {

    *(A *val) {}

    bool color() { ret RED; }

    Node<A> convertToBlack() { ret new BlackLeaf(val); }

    Node<A> convertToRed() { this; }

    Node invertColor() { ret convertToBlack(); }

  }

  *() {}

  *(Cl<? extends A> cl) { addAll(cl); }

  private static O deSentinel(O o) {

    ret o == nullSentinel ? null : o;

  }

  private static O sentinel(O o) {

    ret o == null ? nullSentinel : o;

  }

  // returns false on null (algorithm needs this)

  static bool <A> isRed(Node<A> x) {

    ret x != null && x.color() == RED;

  }

  static <A> Node<A> newLeaf(bool color, A val) {

    ret color == RED ? new RedLeaf(val) : new BlackLeaf(val);

  }

  static <A> Node<A> newNode(bool color, A val, Node<A> left, Node<A> right) {

    // Make leaf (always a temporary object now)

    if (left == null && right == null)

      ret newLeaf(color, val);

    ifndef HyperCompactTreeSet_disableSpecialNodes

      // Make special node

      if (color == BLACK

        && right == null

        && left != null && left.isLeaf() && left.color() == RED)

        ret new SpecialNode(left.val, val);

    endifndef

    // Make normal non-leaf

    NonLeaf node = color == RED ? new RedNode(val) : new BlackNode(val);

    node.setLeft_noMorph(left);

    node.setRight_noMorph(right);

    ret node;

  }

  public int size() {

    ret size;

  }

  public bool isEmpty() {

    ret root == null;

  }

  Node<A> root() {

    ret root == null ? null

      : root instanceof Node ? (Node) root

      : newLeaf(RED, (A) root);

  }

  void setRoot(Node<A> root) {

    if (root == null) this.root = null;

    else if (root.isLeaf()) this.root = root.val;

    else this.root = root;

  }

  public bool add(A val) {

    val = (A) sentinel(val);

    int oldSize = size;

    setRoot(put(root(), val).convertToBlack());

    ifdef CompactTreeSet_debug assertTrue(check()); endifdef

    ret size > oldSize;

  }

  // insert the value in the subtree rooted at h

  private Node<A> put(Node<A> h, A val) { 

    if (h == null) { ++size; ret new RedLeaf(val); }

    int cmp = compare_deSentinel(val, h.val);

    if      (cmp < 0) h = h.setLeft(put(h.left(),  val)); 

    else if (cmp > 0) h = h.setRight(put(h.right(), val)) ;

    else              { /*h.val = val;*/ } // no overwriting

    // fix-up any right-leaning links

    if (isRed(h.right()) && !isRed(h.left()))      h = rotateLeft(h);

    if (isRed(h.left())  &&  isRed(h.left().left())) h = rotateRight(h);

    if (isRed(h.left())  &&  isRed(h.right()))     h = flipColors(h);

    ret h;

  }

  final int compare_deSentinel(A a, A b) {

    ret compare((A) deSentinel(a), (A) deSentinel(b));

  }

  // override me if you wish

  int compare(A a, A b) {

    ret cmp(a, b);

  }

  public bool remove(O key) { 

    if (root == null || !contains(key)) false;

    key = sentinel(key);

    // if both children of root are black, set root to red

    Node root = root();

    if (!isRed(root.left()) && !isRed(root.right()))

      root = root.convertToRed();

    root = delete(root, (A) key);

    if (root != null) root = root.convertToBlack();

    setRoot(root);

    // assert check();

    true;

  }

  // delete the key-value pair with the given key rooted at h

  private Node delete(Node<A> h, A key) { 

    // assert get(h, key) != null;

    if (compare_deSentinel(key, h.val) < 0)  {

      if (!isRed(h.left()) && !isRed(h.left().left()))

          h = moveRedLeft(h);

      h = h.setLeft(delete(h.left(), key));

    }

    else {

      if (isRed(h.left()))

          h = rotateRight(h);

      if (compare_deSentinel(key, h.val) == 0 && (h.right() == null)) {

          --size; null;

      } if (!isRed(h.right()) && !isRed(h.right().left()))

          h = moveRedRight(h);

      if (compare_deSentinel(key, h.val) == 0) {

          --size;

          Node<A> x = min(h.right());

          h.val = x.val;

          // h.val = get(h.right(), min(h.right()).val);

          // h.val = min(h.right()).val;

          h = h.setRight(deleteMin(h.right()));

      }

      else h = h.setRight(delete(h.right(), key));

    }

    return balance(h);

  }

  // make a left-leaning link lean to the right

  private Node<A> rotateRight(Node<A> h) {

      // assert (h != null) && isRed(h.left());

      Node<A> x = h.left();

      h = h.setLeft(x.right());

      x = x.setRight(h);

      x = x.convertToColor(x.right().color());

      x = x.setRight(x.right().convertToRed());

      ret x;

  }

  // make a right-leaning link lean to the left

  private Node<A> rotateLeft(Node<A> h) {

      // assert (h != null) && isRed(h.right());

      Node<A> x = h.right();

      h = h.setRight(x.left());

      x = x.setLeft(h);

      x = x.convertToColor(x.left().color());

      x = x.setLeft(x.left().convertToRed());

      ret x;

  }

  // flip the colors of a node and its two children

  private Node<A> flipColors(Node<A> h) {

      // h must have opposite color of its two children

      // assert (h != null) && (h.left() != null) && (h.right() != null);

      // assert (!isRed(h) &&  isRed(h.left()) &&  isRed(h.right()))

      //    || (isRed(h)  && !isRed(h.left()) && !isRed(h.right()));

      h = h.setLeft(h.left().invertColor());

      h = h.setRight(h.right().invertColor());

      ret h.invertColor();

  }

  // Assuming that h is red and both h.left() and h.left().left()

  // are black, make h.left() or one of its children red.

  private Node<A> moveRedLeft(Node<A> h) {

      // assert (h != null);

      // assert isRed(h) && !isRed(h.left()) && !isRed(h.left().left());

      h = flipColors(h);

      if (isRed(h.right().left())) { 

          h = h.setRight(rotateRight(h.right()));

          h = rotateLeft(h);

          h = flipColors(h);

      }

      ret h;

  }

  // Assuming that h is red and both h.right() and h.right().left()

  // are black, make h.right() or one of its children red.

  private Node<A> moveRedRight(Node<A> h) {

      // assert (h != null);

      // assert isRed(h) && !isRed(h.right()) && !isRed(h.right().left());

      h = flipColors(h);

      if (isRed(h.left().left())) { 

          h = rotateRight(h);

          h = flipColors(h);

      }

      ret h;

  }

  // restore red-black tree invariant

  private Node<A> balance(Node<A> h) {

      // assert (h != null);

      if (isRed(h.right()))                      h = rotateLeft(h);

      if (isRed(h.left()) && isRed(h.left().left())) h = rotateRight(h);

      if (isRed(h.left()) && isRed(h.right()))     h = flipColors(h);

      ret h;

  }

  /**

   * Returns the height of the BST (for debugging).

   * @return the height of the BST (a 1-node tree has height 0)

   */

  public int height() {

      ret height(root());

  }

  private int height(Node<A> x) {

      if (x == null) return -1;

      return 1 + Math.max(height(x.left()), height(x.right()));

  }

  public bool contains(O val) {

    ret find(root(), (A) sentinel(val)) != null;

  }

  public A find(A probeVal) {

    probeVal = (A) sentinel(probeVal);

    Node<A> n = find(root(), probeVal);

    ret n == null ? null : n.val;

  }

  // value associated with the given key in subtree rooted at x; null if no such key

  private A get(Node<A> x, A key) {

    x = find(x, key);

    ret x == null ? null : x.val;

  }

  Node<A> find(Node<A> x, A key) {

    while (x != null) {

      int cmp = compare_deSentinel(key, x.val);

      if      (cmp < 0) x = x.left();

      else if (cmp > 0) x = x.right();

      else              ret x;

    }

    null;

  }

  private boolean check() {

      if (!is23())             println("Not a 2-3 tree");

      if (!isBalanced())       println("Not balanced");

      return is23() && isBalanced();

  }

  // Does the tree have no red right links, and at most one (left)

  // red links in a row on any path?

  private boolean is23() { return is23(root()); }

  private boolean is23(Node<A> x) {

      if (x == null) true;

      if (isRed(x.right())) false;

      if (x != root && isRed(x) && isRed(x.left())) false;

      ret is23(x.left()) && is23(x.right());

  } 

  // do all paths from root to leaf have same number of black edges?

  private bool isBalanced() { 

      int black = 0;     // number of black links on path from root to min

      Node<A> x = root();

      while (x != null) {

          if (!isRed(x)) black++;

          x = x.left();

      }

      ret isBalanced(root(), black);

  }

  // does every path from the root to a leaf have the given number of black links?

  private boolean isBalanced(Node<A> x, int black) {

      if (x == null) return black == 0;

      if (!isRed(x)) black--;

      return isBalanced(x.left(), black) && isBalanced(x.right(), black);

  }

  public void clear() { root = null; size = 0; }

  // the smallest key in subtree rooted at x; null if no such key

  private Node<A> min(Node<A> x) { 

    // assert x != null;

    while (x.left() != null) x = x.left();

    ret x;

  }

  private Node<A> deleteMin(Node<A> h) { 

    if (h.left() == null)

      return null;

    if (!isRed(h.left()) && !isRed(h.left().left()))

      h = moveRedLeft(h);

    h = h.setLeft(deleteMin(h.left()));

    ret balance(h);

  }

  public Iterator<A> iterator() {

    ret new MyIterator;

  }

  class MyIterator extends ItIt<A> {

    new L<Node<A>> path;

    *() {

      fetch(root());

    }

    void fetch(Node<A> node) {

      while (node != null) {

        path.add(node);

        node = node.left();

      }

    }

    public bool hasNext() { ret !path.isEmpty(); }

    public A next() {

      if (path.isEmpty()) fail("no more elements");

      Node<A> node = popLast(path);

      // last node is always a leaf, so left is null

      // so proceed to fetch right branch

      fetch(node.right());

      ret (A) deSentinel(node.val);

    }

  }

  // Returns the smallest key in the symbol table greater than or equal to {@code key}.

  public A ceiling(A key) {

    key = (A) sentinel(key);

    Node<A> x = ceiling(root(), key);

    ret x == null ? null : x.val;

  }

  // the smallest key in the subtree rooted at x greater than or equal to the given key

  Node<A> ceiling(Node<A> x, A key) {  

    if (x == null) null;

    int cmp = compare_deSentinel(key, x.val);

    if (cmp == 0) ret x;

    if (cmp > 0)  ret ceiling(x.right(), key);

    Node<A> t = ceiling(x.left(), key);

    if (t != null) ret t; 

    else           ret x;

  }

  public A floor(A key) {

    key = (A) sentinel(key);

    Node<A> x = floor(root(), key);

    ret x == null ? null : x.val;

  }    

  // the largest key in the subtree rooted at x less than or equal to the given key

  Node<A> floor(Node<A> x, A key) {

    if (x == null) null;

    int cmp = compare_deSentinel(key, x.val);

    if (cmp == 0) ret x;

    if (cmp < 0)  ret floor(x.left(), key);

    Node<A> t = floor(x.right(), key);

    if (t != null) ret t; 

    else           ret x;

  }

  void testInternalStructure() {

    ifndef HyperCompactTreeSet_disableSpecialNodes

      // one leaf object (root) is allowed - could even optimize that

      assertTrue(countLeafObjects() <= 1);

    endifndef

  }

  // count leaf objects we didn't optimize away

  int countLeafObjects(Node node default root()) {

    if (node instanceof Leaf) ret 1;

    if (node cast NonLeaf)

      ret countLeafObjects(optCast Node(node.left))

        + countLeafObjects(optCast Node(node.right));

    ret 0;

  }

  Cl<NonLeaf> unoptimizedNodes() {

    new L<NonLeaf> out;

    findUnoptimizedNodes(out);

    ret out;

  }

  void findUnoptimizedNodes(Node node default root(), L<NonLeaf> out) {

    if (node == null) ret;

    if (node cast NonLeaf) {

      if (isUnoptimizedNode(node)) out.add(node);

      findUnoptimizedNodes(optCast Node(node.left), out);

      findUnoptimizedNodes(optCast Node(node.right), out);

    }

  }

  bool isUnoptimizedNode(Node node) {

    if (node cast NonLeaf)

      ret node.left instanceof Leaf

        || node.right instanceof Leaf;

    false;

  }

  // Compact me (minimize space use). Returns a compacted copy.

  // This only has an effect when elements were inserted in non-sorted

  // or and/or elements were removed.

  selfType compact() {

    ret new HyperCompactTreeSet(this);

  }

}