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

Began life as a copy of #1031038