!7

sclass ArrayTreeSet<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;

    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 = array[i] == null ? -1 : 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 <= 64; n++) {

    if (n != 0) l.add(n*10);

    print("n=" + n); assertEquals(n, l(l));

    ArrayTreeSet tree = new ArrayTreeSet(shuffledList(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");

}