// 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() {
    ret new EntrySet;
  }
  
  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 t) {
    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 int size() {
      ret ArrayTreeMap.this.size();
    }
  }
  
  class EntryIterator implements Iterator<Map.Entry<A, B>> {
    int next = -1, lastReturned = -1;
    
    *(int first) {
      next = first;
    }
    
    public final bool hasNext() {
      ret next >= 0;
    }

    public Map.Entry<A, B> next() {
      int e = next;
      if (e < 0)
        throw new NoSuchElementException;
        
      do {
        next = successor(next);
      } while (next >= 0 && array[next] == null);
      
      lastReturned = e;
      ret new SimpleImmutableEntry((A) array[e], (B) array[e+1]);
    }
  }
}