!7

// A must be comparable

sclass ArrayTreeMap<A, B> {

  O[] array; // key, value, key, value...

  *() {}

  *(Map<A, B> map) {

    array = new O[roundUpToPowerOfTwo(l(map))*2];

    fill(sorted(keys(map)), map, 0, l(array)/2, 0);

  }

  void fill(L<A> l, Map<A, B> map, int lIdx1, int lIdx2, int aIdx) {

    if (lIdx2 <= lIdx1) ret;

    int middle = (lIdx1+lIdx2)/2;

    A key = _get(l, middle);

    array[aIdx*2] = key;

    array[aIdx*2+1] = map.get(key);

    fill(l, map, lIdx1, middle, aIdx*2+1);

    fill(l, map, middle+1, lIdx2, aIdx*2+2);

  }

  B get(A a) {

    int i = 0;

    while (i < l(array)) {

      int x = array[i] == null ? -1 : cmp(a, array[i]);

      if (x == 0) ret (B) array[i+1];

      i = i*2+(x > 0 ? 4 : 2);

    }

    null;

  }

}

p {

  new Map<Int, S> m;

  for (int n = 0; n <= 1024; n++) {

    if (n != 0) m.put(n*10, str(n*10));

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

    ArrayTreeMap<Int, S> map = new ArrayTreeMap(m);

    if (n <= 64)

      printStruct(map);

    for (int i : keys(m)) {

      assertEquals(str(i), map.get(i));

      assertNull(map.get(i-1));

      assertNull(map.get(i+1));

    }

  }

  print("OK");

}