!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");
}

Began life as a copy of #1011274