// A must be comparable
sclass ArrayTreeMap<A, B> extends AbstractMap<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);
  }
  
  public Set<Map.Entry<A, B>> entrySet() {
    throw todo();
  }
  
  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);
  }
  
  int find(O a) {
    int i = 0;
    while (i < l(array)) {
      int x = array[i] == null ? -1 : cmp(a, array[i]);
      if (x == 0) ret i;
      i = i*2+(x > 0 ? 4 : 2);
    }
    ret -1;
  }
  
  public bool containsKey(O o) {
    ret find(a) >= 0;
  }
  
  public B get(O a) {
    int i = find(a);
    ret i >= 0 ? array[i+1] : null;
  }
}