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;
  }
}