// size:

// 64 bytes for 0 to 1 elements

// 96 bytes for 2 to 4 elements

/*

 * #!

 * Ontopia Engine

 * #-

 * Copyright (C) 2001 - 2013 The Ontopia Project

 * #-

 * Licensed under the Apache License, Version 2.0 (the "License");

 * you may not use this file except in compliance with the License.

 * You may obtain a copy of the License at

 * 

 *      http://www.apache.org/licenses/LICENSE-2.0

 * 

 * Unless required by applicable law or agreed to in writing, software

 * distributed under the License is distributed on an "AS IS" BASIS,

 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

 * See the License for the specific language governing permissions and

 * limitations under the License.

 * !#

 */

sclass CompactHashMap<K, V> extends CompactAbstractMap<K, V> {

  final static int INITIAL_SIZE = 3;

  final static double LOAD_FACTOR = 0.6;

  // This object is used to represent a null KEY (null value are kept as is)

  final static Object nullObject = new Object();

  /**

   * When a key is deleted this object is put into the hashtable in

   * its place, so that other entries with the same key (collisions)

   * further down the hashtable are not lost after we delete an object

   * in the collision chain.

   */

  final static Object deletedObject = new Object();

  int elements;

  int freecells;

  O[] table; // key, value, key, value, ...

  //int modCount;

  *() {

    this(INITIAL_SIZE);

  }

  *(int size) {

    table = new Object[(size==0 ? 1 : size)*2];

    elements = 0;

    freecells = tableSize();

    //modCount = 0;

  }

  // TODO: allocate smarter

  *(Map<K, V> map) {

    this(0);

    if (map != null) putAll(map);

  }

  // ===== MAP IMPLEMENTATION =============================================

  /**

   * Returns the number of key/value mappings in this map.

   */

  public synchronized int size() {

    return elements;

  }

  /**

   * Returns <tt>true</tt> if this map contains no mappings.

   */

  public synchronized boolean isEmpty() {

    return elements == 0;

  }

  /**

   * Removes all key/value mappings in the map.

   */

  public synchronized void clear() {

    elements = 0;

    for (int ix = 0; ix < tableSize(); ix++) {

      key(ix, null);

      value(ix, null);

    }

    freecells = tableSize();

    //modCount++;

  }

  /**

   * Returns <tt>true</tt> if this map contains the specified key.

   */

  public synchronized boolean containsKey(Object k) {

    return key(findKeyIndex(k)) != null;

  }

  /**

   * Returns <tt>true</tt> if this map contains the specified value.

   */

  public synchronized boolean containsValue(Object v) {

    if (v == null)

      v = (V)nullObject;

    for (int ix = 0; ix < tableSize(); ix++)

      if (value(ix) != null && value(ix).equals(v))

        return true;

    return false;

  }

  /**

   * Returns a read-only set view of the map's keys.

   */

  public synchronized Set<Entry<K, V>> entrySet() {

    ret new EntrySet;

  }

  /**

   * Removes the mapping with key k, if there is one, and returns its

   * value, if there is one, and null if there is none.

   */

  public synchronized V remove(Object k) {

    int index = findKeyIndex(k);

    // we found the right position, now do the removal

    if (key(index) != null) {

      // we found the object

      // same problem here as with put

      V v = value(index);

      key(index, deletedObject);

      value(index, deletedObject);

      //modCount++;

      elements--;

      return v;

    } else

      // we did not find the key

      return null;

  }

  /**

   * Adds the specified mapping to this map, returning the old value for

   * the mapping, if there was one.

   */

  public synchronized V put(K k, V v) {

    if (k == null)

      k = (K)nullObject;

    int hash = k.hashCode();

    int index = (hash & 0x7FFFFFFF) % tableSize();

    int offset = 1;

    int deletedix = -1;

    // search for the key (continue while !null and !this key)

    while(key(index) != null &&

          !(key(index).hashCode() == hash &&

            key(index).equals(k))) {

      // if there's a deleted mapping here we can put this mapping here,

      // provided it's not in here somewhere else already

      if (key(index) == deletedObject)

        deletedix = index;

      index = ((index + offset) & 0x7FFFFFFF) % tableSize();

      offset = offset*2 + 1;

      if (offset == -1)

        offset = 2;

    }

    if (key(index) == null) { // wasn't present already

      if (deletedix != -1) // reusing a deleted cell

        index = deletedix;

      else

        freecells--;

      //modCount++;

      elements++;

      key(index, k);

      value(index, v);

      // rehash with increased capacity

      if (1 - (freecells / (double) tableSize()) > LOAD_FACTOR)

        rehash(tableSize()*2 + 1);

      return null;

    } else { // was there already

      //modCount++;

      V oldv = value(index);

      value(index, v);

      return oldv;

    }

  }

  /**

   * INTERNAL: Rehashes the hashmap to a bigger size.

   */

  void rehash(int newCapacity) {

    int oldCapacity = tableSize();

    O[] newTable = new Object[newCapacity*2];

    for (int ix = 0; ix < oldCapacity; ix++) {

      Object k = key(ix);

      if (k == null || k == deletedObject)

        continue;

      int hash = k.hashCode();

      int index = (hash & 0x7FFFFFFF) % newCapacity;

      int offset = 1;

      // search for the key

      while(newTable[index*2] != null) { // no need to test for duplicates

        index = ((index + offset) & 0x7FFFFFFF) % newCapacity;

        offset = offset*2 + 1;

        if (offset == -1)

          offset = 2;

      }

      newTable[index*2] = k;

      newTable[index*2+1] = value(ix);

    }

    table = newTable;

    freecells = tableSize() - elements;

  }

  /**

   * Returns the value for the key k, if there is one, and null if

   * there is none.

   */

  public synchronized V get(Object k) {

    return value(findKeyIndex(k));

  }

  /**

   * Returns a virtual read-only collection containing all the values

   * in the map.

   */

  public synchronized Collection<V> values() {

    return new ValueCollection();

  }

  /**

   * Returns a virtual read-only set of all the keys in the map.

   */

  public synchronized Set<K> keySet() {

    return new KeySet();

  }

  // --- Internal utilities

  final int findKeyIndex(Object k) {

    if (k == null)

      k = nullObject;

    int hash = k.hashCode();

    int index = (hash & 0x7FFFFFFF) % tableSize();

    int offset = 1;

    // search for the key (continue while !null and !this key)

    while(key(index) != null &&

          !(key(index).hashCode() == hash &&

            key(index).equals(k))) {

      index = ((index + offset) & 0x7FFFFFFF) % tableSize();

      offset = offset*2 + 1;

      if (offset == -1)

        offset = 2;

    }

    return index;

  }

  // --- Key set

  class KeySet extends AbstractSet<K> {

    public int size() { synchronized(CompactHashMap.this) {

      return elements;

    }}

    public boolean contains(Object k) { synchronized(CompactHashMap.this) {

      return containsKey(k);

    }}

    public Iterator<K> iterator() { synchronized(CompactHashMap.this) {

      return new KeyIterator();

    }}

  }

  class KeyIterator<K> implements Iterator<K> {

    private int ix;

    private KeyIterator() {

      synchronized(CompactHashMap.this) {

        // walk up to first value, so that hasNext() and next() return

        // correct results

        for (; ix < tableSize(); ix++)

          if (value(ix) != null && key(ix) != deletedObject)

            break;

      }

    }

    public boolean hasNext() { synchronized(CompactHashMap.this) {

      return ix < tableSize();

    }}

    public void remove() {

      throw new UnsupportedOperationException("Collection is read-only");

    }

    public K next() { synchronized(CompactHashMap.this) {

      if (ix >= tableSize())

        throw new NoSuchElementException();

      K key = (K) key(ix++);

      // walk up to next value

      for (; ix < tableSize(); ix++)

        if (key(ix) != null && key(ix) != deletedObject)

          break;

      // ix now either points to next key, or outside array (if no next)

      return key;

    }}

  }

  // --- Entry set

  class EntrySet extends AbstractSet<Map.Entry<K, V>> {

    public int size() { synchronized(CompactHashMap.this) {

      return elements;

    }}

    public boolean contains(O o) { synchronized(CompactHashMap.this) {

      if (o cast Map.Entry) {

        O key = o.getKey();

        if (!containsKey(o)) false;

        ret eq(o.getValue(), get(key));

      }

      false;

    }}

    public Iterator<Map.Entry<K, V>> iterator() {

      return new EntryIterator();

    }

  }

  class EntryIterator implements Iterator<Map.Entry<K, V>> {

    private int ix;

    private EntryIterator() {

      synchronized(CompactHashMap.this) {

        // walk up to first value, so that hasNext() and next() return

        // correct results

        for (; ix < tableSize(); ix++)

          if (value(ix) != null && key(ix) != deletedObject)

            break;

      }

    }

    public boolean hasNext() { synchronized(CompactHashMap.this) {

      return ix < tableSize();

    }}

    public void remove() {

      throw new UnsupportedOperationException("Collection is read-only");

    }

    public Map.Entry<K, V> next() { synchronized(CompactHashMap.this) {

      if (ix >= tableSize())

        throw new NoSuchElementException();

      K key = key(ix);

      V val = value(ix);

      ++ix;

      // walk up to next value

      for (; ix < tableSize(); ix++)

        if (key(ix) != null && key(ix) != deletedObject)

          break;

      // ix now either points to next key, or outside array (if no next)

      return simpleMapEntry(key, val);

    }}

  }

  // --- Value collection

  class ValueCollection<V> extends AbstractCollection<V> {

    public int size() { synchronized(CompactHashMap.this) {

      return elements;

    }}

    public Iterator<V> iterator() {

      return new ValueIterator();

    }

    public boolean contains(Object v) {

      return containsValue(v);

    }

  }

  class ValueIterator<V> implements Iterator<V> {

    private int ix;

    private ValueIterator() {

      synchronized(CompactHashMap.this) {

        // walk up to first value, so that hasNext() and next() return

        // correct results

        for (; ix < table.length/2; ix++)

          if (value(ix) != null && value(ix) != deletedObject)

            break;

      }

    }

    public boolean hasNext() { synchronized(CompactHashMap.this) {

      return ix < tableSize();

    }}

    public void remove() {

      throw new UnsupportedOperationException("Collection is read-only");

    }

    public V next() { synchronized(CompactHashMap.this) {

      if (ix >= tableSize())

        throw new NoSuchElementException();

      V value = (V) value(ix++);

      // walk up to next value

      for (; ix < tableSize(); ix++)

        if (value(ix) != null && value(ix) != deletedObject)

          break;

      // ix now either points to next value, or outside array (if no next)

      return value;

    }}

  }

  K key(int i) { ret (K) table[i*2]; }

  void key(int i, O key) { table[i*2] = key; }

  V value(int i) { ret (V) table[i*2+1]; }

  void value(int i, O value) { table[i*2+1] = value; }

  int tableSize() { ret table.length/2; }

}