class ArraySortedMap extends ImmutableSortedMap<K, V> {

  @Override
  public ImmutableSortedMap<K, V> insert(K key, V value) {
    int pos = findKey(key);
    if (pos != -1) {
      if (this.keys[pos] == key && this.values[pos] == value) {
        return this;
      } else {
        // The key and/or value might have changed, even though the comparison might still yield 0
        K[] newKeys = replaceInArray(this.keys, pos, key);
        V[] newValues = replaceInArray(this.values, pos, value);
        return new ArraySortedMap<K, V>(this.comparator, newKeys, newValues);
      }
    } else {
      if (this.keys.length > Builder.ARRAY_TO_RB_TREE_SIZE_THRESHOLD) {
        @SuppressWarnings("unchecked")
        Map<K, V> map = new HashMap<K, V>(this.keys.length + 1);
        for (int i = 0; i < this.keys.length; i++) {
          map.put(this.keys[i], this.values[i]);
        }
        map.put(key, value);
        return RBTreeSortedMap.fromMap(map, this.comparator);
      } else {
        int newPos = findKeyOrInsertPosition(key);
        K[] keys = addToArray(this.keys, newPos, key);
        V[] values = addToArray(this.values, newPos, value);
        return new ArraySortedMap<K, V>(this.comparator, keys, values);
      }
    }
  }

  @SuppressWarnings("unchecked") public  ArraySortedMap(Comparator<K> comparator);
  @SuppressWarnings("unchecked") private  ArraySortedMap(Comparator<K> comparator, K[] keys, V[] values);

}