// A must be comparable
sclass ArrayTreeMap<A, B> extends AbstractMap<A, B> {
  O[] array; // key, value, key, value...
  int size;
  
  *() {}
  *(Map<A, B> map) {
    array = new O[roundUpToPowerOfTwo(l(map))*2];
    fill(sorted(keys(map)), map, 0, l(array)/2, 0);
    size = l(map);
  }
  
  public int size() { ret size; }
  
  public Set<Map.Entry<A, B>> entrySet() {
    int i = 0;
    while (i*2+2 < l(array)) i = i*2+2;
    ret new AbstractSet<Map.Entry<A, B>>() {
      
    };
  }
  
  bool inRange(int i) {
    ret i >= 0 && i < l(array);
  }
  
  int check(int i) { ret inRange(i) ? i : -1; }
  
  int parent(int i) { ret check(i == 0 ? -1 : ((i-2)/2) & ~1); }
  int left(int i) { ret check(i*2+2); }
  int right(int i) { ret check(i*2+4); }
  
  int first() {
    if (l(array) == 0) ret -1;
    int p = 0;
    while (left(p) >= 0)
      p = left(p);
    ret p;
  }
  
  int successor(int i) {
    if (!inRange(t)) ret -1;
    if (right(t) >= 0) {
      int p = right(t);
      while (left(p) >= 0)
        p = left(p);
      ret p;
    }
    int p = parent(t);
    int ch = t;
    while (p >= 0 && ch == right(p)) {
      ch = p;
      p = parent(p);
    }
    ret p;
  }
  
  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 a) {
    ret find(a) >= 0;
  }
  
  public B get(O a) {
    int i = find(a);
    ret i >= 0 ? (B) array[i+1] : null;
  }
  
  class EntrySet extends AbstractSet<Map.Entry<A, B>> {
    public Iterator<Map.Entry<A, B>> iterator() {
      ret new EntryIterator(first());
    }
 
    public bool contains(O o) {
      /*if (!(o instanceof Map.Entry))
        false;
      Map.Entry<A, B> entry = (Map.Entry<A, B>) o;
      V value = entry.getValue();
      Entry<K,V> p = getEntry(entry.getKey());
      ret p != null && valEquals(p.getValue(), value);*/
      throw todo();
    }
 
    public int size() {
      ret ArrayTreeMap.this.size();
    }
  }
}