/*
 * #!
 * 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;
    }
  }
}

Began life as a copy of #1029374