// 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]);

    }

  }

}