package trees;

import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;

// arbres binaires de recherche (contenant des entiers)

class BST {
  int value;
  BST left, right;

  BST(BST left, int value, BST right) {
    this.left = left;
    this.value = value;
    this.right = right;
  }

  BST(int value) {
    this(null, value, null);
  }

  static int size(BST t) {
    if (t == null)
      return 0;
    return 1 + size(t.left) + size(t.right);
  }

  static int height(BST t) {
    if (t == null)
      return 0;
    return 1 + Math.max(height(t.left), height(t.right));
  }

  static boolean contains(BST b, int x) {
    while (b != null) {
      if (x == b.value)
        return true;
      b = (x < b.value) ? b.left : b.right;
    }
    return false;
  }

  // version récursive
  static boolean containsRec(BST b, int x) {
    if (b == null) return false;
    if (x == b.value) return true;
    return containsRec(x < b.value ? b.left : b.right, x);
  }

  static BST add(BST b, int x) {
    if (b == null)
      return new BST(x);
    if (x < b.value)
      b.left = add(b.left, x);
    else if (x > b.value)
      b.right = add(b.right, x);
    return b;
  }

  // variante itérative
  static BST addIter(BST b, int x) {
    if (b == null) return new BST(x);
    BST t = b;
    while (true) { // invariant t != null
      if (x == t.value) return b;
      if (x < t.value)
        if (t.left != null) t = t.left;
        else { t.left = new BST(x); return b; }
      else
        if (t.right != null) t = t.right;
        else { t.right = new BST(x); return b; }
    }
  }

  // suppose b != null
  static int getMin(BST b) {
    while (b.left != null)
      b = b.left;
    return b.value;
  }

  // suppose b != null
  static BST removeMin(BST b) {
    if (b.left == null)
      return b.right;
    b.left = removeMin(b.left);
    return b;
  }

  static BST remove(BST b, int x) {
    if (b == null)
      return null;
    if (x < b.value)
      b.left = remove(b.left, x);
    else if (x > b.value) 
      b.right = remove(b.right, x);
    else { // x == b.value
      if (b.right == null)
        return b.left;
//      if (b.left == null) // optim
//        return b.right;
      b.value = getMin(b.right);
      b.right = removeMin(b.right);
    }
    return b;
  }

  static int floorrec(BST b, int x) {
    if (b == null) throw new NoSuchElementException();
    if (x < b.value) return floor(b.left, x);
    if (x == b.value) return x;
    try { return floor(b.right, x); }
    catch (NoSuchElementException e) { return b.value; }
  }
  
  static int floor(BST b, int x) {
    Integer c = null;
    while (b != null) {
      if (x == b.value) return x;
      if (x < b.value) b = b.left;
      else { c = b.value; b = b.right; }
    }
    if (c == null) throw new NoSuchElementException();
    return c;
  }
  
  static BST ofList(Queue<Integer> l, int n) {
    if (n == 0) return null;
    else { // n >= 1
      int n1 = (n - 1) / 2;
      BST left = ofList(l, n1);
      int v = l.poll();
      BST right = ofList(l, n - n1 - 1);
      return new BST(left, v, right);
    }
  }
  
  static BST ofList(Queue<Integer> l) {
    return ofList(l, l.size());
  }

  /* same fringe: do two BST contain the same values?
   * the left branch of the tree is built as a list of
   * pairs (value, right sub-tree), of type Enum
   * the list is bottom-up: the head is the leftmost,
   * innermost element of the tree
   */
  private static class Enum {
    final int root;
    final BST right;
    final Enum next;
    public Enum(int root, BST right, Enum next) {
      this.root = root;
      this.right = right;
      this.next = next;
    }
    static Enum build(BST t, Enum acc) {
      while (t != null) {
        acc = new Enum(t.value, t.right, acc);
        t = t.left;
      }
      return acc;
    }
    static boolean equals(Enum x, Enum y) {
      while (x != null || y != null) {
        if (x == null || y == null) return false;
        if (x.root != y.root) return false;
        x = build(x.right, x.next);
        y = build(y.right, y.next);
      }
      return true;
    }
  }
  
  static boolean equals(BST x, BST y) {
    return Enum.equals(Enum.build(x,  null), Enum.build(y, null));
  }
 
  /* subset */
  static boolean subset(BST s1, BST s2) {
    if (s1 == null) return true;
    if (s2 == null) return false;
    if (s1.value == s2.value)
      return subset(s1.left, s2.left) && subset(s1.right, s2.right);
    if (s1.value < s2.value)
      return subset(new BST(s1.left, s1.value, null), s2.left)
          && subset(s1.right, s2);
    else
      return subset(new BST(null, s1.value, s1.right), s2.right)
          && subset(s1.left, s2);
  }
  
  /* split(v,s) returns two trees, containing values
   * from s smaller and greater than s
   */
  static BST[] split(int x, BST s) {
    if (s == null) return new BST[] { null, null };
    if (x == s.value) return new BST [] { s.left, s.right };
    if (x < s.value) {
      BST[] spl = split(x, s.left);
      spl[1] = new BST(spl[1], s.value, s.right);
      return spl;
    } else {
      BST[] spl = split(x, s.right);
      spl[0] = new BST(s.left, s.value, spl[0]);
      return spl;
    }
  }
  
  /* union */
  static BST union(BST s1, BST s2) {
    if (s1 == null) return s2;
    if (s2 == null) return s1;
    BST[] spl = split(s1.value, s2);
    return new BST(union(s1.left, spl[0]), s1.value, union(s1.right, spl[1]));
  }

  static BST diff(BST s1, BST s2) {
    if (s1 == null) return null;
    if (s2 == null) return s1;
    BST[] spl = split(s1.value, s2);
    if (contains(s2, s1.value))
      return merge(diff(s1.left, spl[0]), diff(s1.right, spl[1]));
    else
      return new BST(diff(s1.left, spl[0]), s1.value, diff(s1.right, spl[1]));
  }
  
  /* merge(s1, s2) merges two trees, elements of s1 being
   * smaller than elements of s2 */
  static BST merge(BST s1, BST s2) {
      if (s1 == null) return s2;
      if (s2 == null) return s1;
      return new BST(s1, getMin(s2), removeMin(s2));
  }
  
  public String toString() {
    return "(" + this.left + "+" + this.value + "+" + this.right + ")";
  }
  
  static List<Integer> toList(BST s) {
    List<Integer> l = new LinkedList<Integer>();
    toList(l, s);
    return l;
  }
  
  private static void toList(List<Integer> l, BST s) {
    if (s == null) return;
    toList(l, s.left);
    l.add(s.value);
    toList(l, s.right);
  }
  
}

public class BSTSet implements intf.Set<Integer> {
  private BST root;

  public BSTSet() {
    this.root = null;
  }
  
  private BSTSet(BST s) {
    this.root = s;
  }
  
  public int height() {
    return BST.height(this.root);
  }
  
  public int size() {
    return BST.size(this.root);
  }
  
  public boolean isEmpty() {
    return this.root == null;
  }

  public boolean contains(Integer x) {
    return BST.contains(this.root, x);
  }

  public void add(Integer x) {
    this.root = BST.add(this.root, x);
  }

  public int getMin() {
    return BST.getMin(this.root);
  }

  public void removeMin() {
    this.root = BST.removeMin(this.root);
  }

  public void remove(Integer x) {
    this.root = BST.remove(this.root, x);
  }
  
  public List<Integer> toList() {
    return BST.toList(this.root);
  }

  public void clear() {
    this.root = null;
  }
   
  public boolean subset(BSTSet s) {
    return BST.subset(this.root, s.root);
  }
  
  public BSTSet diff(BSTSet s) {
    return new BSTSet(BST.diff(this.root, s.root));
  }
  
  public boolean equals(BSTSet s) {
    return BST.equals(this.root, s.root);
  }
  
}

class TestBSTSet {
  public static void main(String[] args) {
    BSTSet s = new BSTSet();
    for (int i = 0; i < 10; i++) {
      assert s.size() == i;
      assert !s.contains(i);
      s.add(i);
      assert s.contains(i);
    }
    BSTSet t = new BSTSet();
    for (int i = 9; i >= 0; i--)
      t.add(i);
    assert s.equals(t);
    assert t.equals(s);
    for (int i = 0; i < 10; i++) {
      assert s.contains(i);
      assert s.getMin() == i;
      s.remove(i);
      assert i == 9 || s.getMin() == i+1;
      assert !s.contains(i); 
    }
    s.clear();
    assert !s.equals(t);
    assert s.size() == 0;
    for (int i = 0; i < 100; i++) {
      int x = (int)(Math.random() * 100);
      s.add(x);
      assert s.contains(x);
      assert s.size() <= i+1;
    }
    System.out.println("TestBSTSet OK");
  }
}