!7

sclass ABTree<A> {
  A[] array;
  
  *() {}
  *(L<A> l) {
    array = (A[]) new O[roundUpToPowerOfTwo(l(l))];
    l = sorted(l);
    fill(l, 0, l(array), 0);
  }
  
  void fill(L<A> l, int lIdx1, int lIdx2, int aIdx) {
    if (lIdx2 <= lIdx1) ret;
    int middle = (lIdx1+lIdx2)/2;
    print("Copying " + middle + " => " + aIdx);
    array[aIdx] = get(l, middle);
    fill(l, lIdx1, middle, aIdx*2+1);
    fill(l, middle+1, lIdx2, aIdx*2+2);
  }
  
  bool contains(A a) {
    int i = 0;
    while (i < l(array)) {
      int x = cmp(a, array[i]);
      if (x == 0) true;
      i = i*2+(x > 0 ? 2 : 1);
    }
    false;
  }
}

p {
  new L<Int> l;
  for (int n = 0; n <= 8; n++) {
    if (n != 0) l.add(n*10);
    print("n=" + n); assertEquals(n, l(l));
    ABTree tree = new ABTree(l);
    printStruct(tree);
    for (int i : l) {
      assertTrue(str(i), tree.contains(i));
      assertFalse(tree.contains(i-1));
      assertFalse(tree.contains(i+1));
    }
  }
  print("OK");
}