/*

 * #!

 * loosely based on code from the 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.

 * !#

 */

// Note: Long.MIN_VALUE and Long.MIN_VALUE+1 are not allowed as keys

sclass LongIntHashMap_IntMemory64 extends AbstractMap<Long, Int> {

  final static int INITIAL_SIZE = 3;

  final static double LOAD_FACTOR = 0.6;

  /**

   * 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 long noKey = Long.MIN_VALUE; // null in original code

  final static long deletedKey = Long.MIN_VALUE+1;

  IIntMemory64 mem;

  // memory layout:

  // tableSize at 0

  // elements at 2

  // freecells at 4

  // table starts at 6 (long key, int value, ...)

  long tableSize;

  long elements;

  long freecells;

  int modCount;

  *() {

    this(INITIAL_SIZE);

  }

  *(int size) {

    keys = (Long[]) new Object[(size==0 ? 1 : size)];

    values = (Int[]) new Object[(size==0 ? 1 : size)];

    elements = 0;

    freecells = tableSize;

    modCount = 0;

  }

  // ===== 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 (long ix = 0; ix < tableSize; ix++) {

      setKey(ix, noKey);

      setValue(ix, 0); // just for beauty

    }

    freecells = tableSize;

    modCount++;

  }

  long ptr(long i) { ret 6+i*3; }

  void setKey(long i, long key) {

    mem.setLong(ptr(i), key);

  }

  void setValue(long i, int val) {

    mem.setInt(ptr(i)+2, val);

  }

  /**

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

   */

  public synchronized boolean containsKey(Object k) {

    return getKey(findKeyIndex(k)) != noKey;

  }

  /**

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

   */

  public synchronized boolean containsValue(Object v) {

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

      if (tableSizeix] != null && values[ix].equals(v))

        return true;

    return false;

  }

  /**

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

   */

  public synchronized Set<Entry<Long, Int>> entrySet() {

    throw new UnsupportedOperationException();

  }

  /**

   * 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 Int remove(Object k) {

    int index = findKeyIndex(k);

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

    if (keys[index] != null) {

      // we found the object

      // same problem here as with put

      Int v = values[index];

      keys[index] = (Long) deletedObject;

      values[index] = (Int) 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 Int put(Long k, Int v) {

    int hash = k.hashCode();

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

    int offset = 1;

    int deletedix = -1;

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

    while(keys[index] != null &&

          !(keys[index].hashCode() == hash &&

            keys[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 (keys[index] == deletedObject)

        deletedix = index;

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

      offset = offset*2 + 1;

      if (offset == -1)

        offset = 2;

    }

    if (keys[index] == null) { // wasn't present already

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

        index = deletedix;

      else

        freecells--;

      modCount++;

      elements++;

      keys[index] = (Long) k;

      values[index] = (Int) v;

      // rehash with increased capacity

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

        rehash(tableSize*2 + 1);

      return null;

    } else { // was there already

      modCount++;

      Int oldv = values[index];

      values[index] = (Int) v;

      return oldv;

    }

  }

  /**

   * INTERNAL: Rehashes the hashmap to a bigger size.

   */

  void rehash(int newCapacity) {

    int oldCapacity = tableSize;

    Long[] newKeys = (Long[]) new Object[newCapacity];

    Int[] newValues = (Int[]) new Object[newCapacity];

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

      Object k = keys[ix];

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

        continue;

      int hash = k.hashCode();

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

      int offset = 1;

      // search for the key

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

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

        offset = offset*2 + 1;

        if (offset == -1)

          offset = 2;

      }

      newKeys[index] = (Long) k;

      newValues[index] = values[ix];

    }

    keys = newKeys;

    values = newValues;

    freecells = tableSize - elements;

  }

  /**

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

   * there is none.

   */

  public synchronized Int get(Object k) {

    return values[findKeyIndex(k)];

  }

  /**

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

   * in the map.

   */

  public synchronized Collection<Int> values() {

    return new ValueCollection();

  }

  /**

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

   */

  public synchronized Set<Long> 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(keys[index] != null &&

          !(keys[index].hashCode() == hash &&

            keys[index].equals(k))) {

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

      offset = offset*2 + 1;

      if (offset == -1)

        offset = 2;

    }

    return index;

  }

  // --- Key set

  class KeySet<Long> extends AbstractSet<Long> {

    public synchronized int size() {

      return elements;

    }

    public synchronized boolean contains(Object k) {

      return containsKey(k);

    }

    public synchronized Iterator<Long> iterator() {

      return new KeyIterator();

    }

  }

  class KeyIterator<Long> implements Iterator<Long> {

    private int ix;

    private KeyIterator() {

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

      // correct results

      for (; ix < tableSize; ix++)

        if (values[ix] != null && keys[ix] != deletedObject)

          break;

    }

    public synchronized boolean hasNext() {

      return ix < tableSize;

    }

    public synchronized void remove() {

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

    }

    public synchronized Long next() {

      if (ix >= tableSize)

        throw new NoSuchElementException();

      Long key = (Long) keys[ix++];

      // walk up to next value

      for (; ix < tableSize; ix++)

        if (keys[ix] != null && keys[ix] != deletedObject)

          break;

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

      return key;

    }

  }

  // --- Value collection

  class ValueCollection<Int> extends AbstractCollection<Int> {

    public synchronized int size() {

      return elements;

    }

    public synchronized Iterator<Int> iterator() {

      return new ValueIterator();

    }

    public synchronized boolean contains(Object v) {

      return containsValue(v);

    }

  }

  class ValueIterator<Int> implements Iterator<Int> {

    private int ix;

    private ValueIterator() {

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

      // correct results

      for (; ix < tableSize; ix++)

        if (getKey(ix) != noKey && getKey(ix) != deletedKey)

          break;

    }

    public synchronized boolean hasNext() {

      return ix < tableSize;

    }

    public synchronized void remove() {

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

    }

    public synchronized Int next() {

      if (ix >= tableSize)

        throw new NoSuchElementException();

      int value = getValue(ix++);

      // walk up to next value

      for (; ix < tableSize; ix++)

        if (getKey(ix) != noKey && getKey(ix) != deletedKey)

          break;

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

      return value;

    }

  }

}