/*

 * #!

 * 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_IntMemory 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;

  IIntMemory mem;

  // memory layout:

  // tableSize at 0

  // elements at 1

  // freecells at 2

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

  int tableSize;

  int elements;

  int freecells;

  int modCount;

  // load existing map

  *(IIntMemory *mem) {

    tableSize = mem.get(0);

    elements = mem.get(1);

    freecells = mem.get(2);

  }

  // make new map

  *(IIntMemory *mem, int capacity) {

    int tsize = iceil_safe(capacity/LOAD_FACTOR);

    mem.ensureSize(toInt(3+tsize*3L));

    setTableSize(tsize);

    setElements(0);

    setFreecells(tsize);

    for i to tableSize:

      setKey(i, noKey);

  }

  void setTableSize(int tableSize) {

    mem.set(0, this.tableSize = tableSize);

  }

  void setElements(int elements) {

    mem.set(1, this.elements = elements);

  }

  void setFreecells(int freecells) {

    mem.set(2, this.freecells = freecells);

  }

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

  public synchronized int size() { ret elements; }

  public synchronized boolean isEmpty() { ret elements == 0; }

  public synchronized void clear() {

    setElements(0);

    for ix to tableSize: {

      setKey(ix, noKey);

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

    }

    setFreecells(tableSize);

    modCount++;

  }

  int ptr(int i) { ret 3+i*3; }

  void setKey(int i, long key) {

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

  }

  void setValue(int i, int val) {

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

  }

  long getKey(int i) {

    ret mem.getLong(ptr(i));

  }

  int getValue(int i) {

    ret mem.get(ptr(i)+2);

  }

  public synchronized bool containsKey(Object k) {

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

  }

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

    throw new UnsupportedOperationException();

  }

  public synchronized Int remove(Object k) {

    int index = findKeyIndex((Long) k);

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

    if (getKey(index) != noKey) {

      // we found the object

      // same problem here as with put

      int v = getValue(index);

      setKey(index, deletedKey);

      setValue(index, 0);

      modCount++;

      setElements(elements-1);

      ret v;

    }

    // we did not find the key

    null;

  }

  public synchronized Int put(Long k, Int v) {

    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 (getKey(index) != noKey && getKey(index) != k) {

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

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

      if (getKey(index) == deletedKey)

        deletedix = index;

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

      offset = offset*2 + 1;

      if (offset == -1)

        offset = 2;

    }

    if (getKey(index) == noKey) { // wasn't present already

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

        index = deletedix;

      else

        setFreecells(freecells-1);

      modCount++;

      setElements(elements+1);

      setKey(index, k);

      setValue(index, v);

      // rehash with increased capacity

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

        rehash(tableSize*2 + 1);

      null;

    } else { // was there already

      modCount++;

      int oldv = getValue(index);

      setValue(index, v);

      ret oldv;

    }

  }

  /**

   * INTERNAL: Rehashes the hashmap to a bigger size.

   */

  void rehash(int newCapacity) {

    fail("rehash not implemented");

  }

  public synchronized Int get(Object k) {

    int i = findKeyIndex((Long) k);

    ret getKey(i) == noKey ? null : getValue(i);

  }

  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(long k) {

    int hash = Long.hashCode(k);

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

    int offset = 1;

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

    while (getKey(index) != noKey && getKey(index) != k) {

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

      offset = offset*2 + 1;

      if (offset == -1)

        offset = 2;

    }

    ret index;

  }

  class KeySet 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 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 (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 Long next() {

      if (ix >= tableSize)

        throw new NoSuchElementException();

      long key = getKey(ix++);

      // walk up to next value

      for (; ix < tableSize; ix++)

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

          break;

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

      ret key;

    }

  }

  // --- Value collection

  class ValueCollection 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 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;

    }

  }

}