sclass SortedArrayBasedMap<A, B> extends CompactAbstractMap<A, B> {

  O[] entries; // key, value, ... with keys being sorted

  *() {}

  *(Map<A, B> map) {

    LPair<A, B> l = pairsSortedByA(mapToPairs(map));

    int n = l(l);

    entries = new O[n*2];

    for i to n: {

      Pair<A, B> p = l.get(i);

      entries[i*2] = p.a;

      entries[i*2+1] = p.b;

    }

  }

  public int size() { ret l(entries)/2; }

  public Set<Map.Entry<A, B>> entrySet() {

    ret new AbstractSet<Map.Entry<A, B>>() {

      public int size() { ret SortedArrayBasedMap.this.size(); }

      public Iterator<Map.Entry<A, B>> iterator() {

        ret new Iterator<Map.Entry<A, B>>() {

          int idx;

          public bool hasNext() {

            ret idx < l(entries);

          }

          public Map.Entry<A, B> next() {

            SimpleEntry<A, B> e = new SimpleEntry<A, B>((A) entries[idx], (B) entries[idx+1]);

            idx += 2;

            ret e;

          }

        };

      }

    };

  }

  int find(O key) {

    ret find(0, size(), key);

  }

  int find(int fromIndex, int toIndex, O key) {

    int low = fromIndex;

    int high = toIndex - 1;

    while (low <= high) {

      int mid = (low + high) >>> 1;

      O midVal = entries[mid*2];

      int c = cmp(midVal, key);

      if (c < 0)

        low = mid + 1;

      else if (c > 0)

        high = mid - 1;

      else

        ret mid; // key found

    }

    ret -(low + 1);  // key not found.

  }

  public bool containsKey(O o) {

    ret find(o) >= 0;

  }

  @Override

  public B get(O o) {

    int i = find(o)*2;

    ret i >= 0 ? (B) entries[i+1] : null;

  }

}