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

// modified by Stefan Reich

// a compact unordered set of longs. unsynchronized

sclass CompactLongSet extends java.util.AbstractSet<Long> {
  protected final static int INITIAL_SIZE = 3;
  public final static double LOAD_FACTOR = 0.75;

  protected final static long deletedObject = Long.MIN_VALUE;
  
  bool containsZero, containsDeletedObject; // special handling for sentinels
  protected int elements;
  protected int freecells;
  protected long[] objects;
  
  ifndef NoModCount
  protected int modCount;
  endifndef
  
  *() { this(0); }

  // This applies the load factor so the set should be able to hold
  // expectedElements without growing (haven't tested if this works exactly).
  *(int expectedElements) {
    int size = max(INITIAL_SIZE, iceil(expectedElements/LOAD_FACTOR));
    // NOTE: If array size is 0, we get a
    // "java.lang.ArithmeticException: / by zero" in add(Object).
    objects = new long[size];
    freecells = objects.length;
  }

  *(Collection<long> c) {
    this(c.size());
    addAll(c);
  }

  @Override
  public RenamedLongIterator iterator() {
    return new CompactHashIterator;
  }

  @Override
  public int size() {
    return elements;
  }

  @Override
  public boolean isEmpty() {
    return elements == 0;
  }

  @Override
  public bool contains(O o) {
    ret contains((long) o);
  }
  
  public bool contains(long o) {
    if (o == 0) ret containsZero;
    if (o == deletedObject) ret containsDeletedObject;

    int hash = hash(o);
    int index = (hash & 0x7FFFFFFF) % objects.length;
    int offset = 1;

    // search for the object (continue while !null and !this object)
    while (objects[index] != 0) {
      if (objects[index] == o) true;
      index = ((index + offset) & 0x7FFFFFFF) % objects.length;
      offset = offset*2 + 1;

      if (offset == -1)
        offset = 2;
    }

    false;
  }
  
  @Override
  public boolean add(Long o) {
    ret add((long) o);
  }
  
  public boolean add(long o) {
    if (o == 0) {
      if (containsZero) false;
      set containsZero; elements++; true;
    }
    if (o == deletedObject)  {
      if (containsDeletedObject) false;
      set containsDeletedObject; elements++; true;
    }
    int hash = hash(o);
    int index = (hash & 0x7FFFFFFF) % objects.length;
    int offset = 1;
    int deletedix = -1;
    
    // search for the object (continue while !null and !this object)
    while (objects[index] != 0 && objects[index] != o) {

      // if there's a deleted object here we can put this object here,
      // provided it's not in here somewhere else already
      if (objects[index] == deletedObject)
        deletedix = index;
      
      index = ((index + offset) & 0x7FFFFFFF) % objects.length;
      offset = offset*2 + 1;

      if (offset == -1)
        offset = 2;
    }
    
    if (objects[index] == 0) { // wasn't present already
      if (deletedix != -1) // reusing a deleted cell
        index = deletedix;
      else
        freecells--;

      ifndef NoModCount
        modCount++;
      endifndef
      elements++;

      objects[index] = o;
      
      // do we need to rehash?
      if (1 - (freecells / (double) objects.length) > LOAD_FACTOR)
        rehash();
      return true;
    } else // was there already 
      return false;
  }
  
  @Override
  public boolean remove(Object o) {
    ret remove((long) o);
  }
  
  public boolean remove(long o) {
    if (o == 0) {
      if (!containsZero) false;
      containsZero = false; --elements;
      true;
    }
    
    if (o == deletedObject) {
      if (!containsDeletedObject) false;
      containsDeletedObject = false; --elements;
      true;
    }
    
    int hash = hash(o);
    int index = (hash & 0x7FFFFFFF) % objects.length;
    int offset = 1;
    
    // search for the object (continue while !null and !this object)
    while (objects[index] != 0 && objects[index] != o) {
      index = ((index + offset) & 0x7FFFFFFF) % objects.length;
      offset = offset*2 + 1;

      if (offset == -1)
        offset = 2;
    }

    // we found the right position, now do the removal
    if (objects[index] != 0) {
      // we found the object

      // same problem here as with add
      objects[index] = deletedObject;
      ifndef NoModCount
        modCount++;
      endifndef
      elements--;
      return true;
    } else
      // we did not find the object
      return false;
  }
  
  @Override
  public void clear() {
    elements = 0;
    for (int ix = 0; ix < objects.length; ix++)
      objects[ix] = 0;
    containsZero = containsDeletedObject = false;
    freecells = objects.length;
    ifndef NoModCount
      modCount++;
    endifndef
  }

  protected void rehash() {
    int garbagecells = objects.length - (elements + freecells);
    if (garbagecells / (double) objects.length > 0.05)
      // rehash with same size
      rehash(objects.length);
    else
      // rehash with increased capacity
      rehash(objects.length*2 + 1);
  }
  
  protected void rehash(int newCapacity) {
    int oldCapacity = objects.length;
    @SuppressWarnings("unchecked")
    long[] newObjects = new[newCapacity];

    for ix to oldCapacity: {
      long o = objects[ix];
      if (o == 0 || o == deletedObject)
        continue;
      
      int hash = hash(o);
      int index = (hash & 0x7FFFFFFF) % newCapacity;
      int offset = 1;

      // search for the object
      while(newObjects[index] != 0) { // no need to test for duplicates
        index = ((index + offset) & 0x7FFFFFFF) % newCapacity;
        offset = offset*2 + 1;

        if (offset == -1)
          offset = 2;
      }

      newObjects[index] = o;
    }

    objects = newObjects;
    freecells = objects.length - elements;
  }
  
  private class CompactHashIterator extends RenamedLongIterator {
    private int index;
    private int lastReturned = -1;
    bool sendZero, sendDeletedObject;

    ifndef NoModCount
      private int expectedModCount;
    endifndef

    @SuppressWarnings("empty-statement")
    public CompactHashIterator() {
      // find first non-empty slot
      for (index = 0; index < objects.length &&
                      (objects[index] == 0 ||
                      objects[index] == deletedObject); index++)
        ;
      ifndef NoModCount
        expectedModCount = modCount;
      endifndef
      
      sendZero = containsZero;
      sendDeletedObject = containsDeletedObject;
    }

    @Override
    public bool hasNext() {
      ret index < objects.length || sendZero || sendDeletedObject;
    }

    @Override
    public long nextLong() {
      /*if (modCount != expectedModCount)
        throw new ConcurrentModificationException();*/
      int length = objects.length;
      
      if (index >= length) {
        if (sendZero) { sendZero = false; ret 0L; }
        if (sendDeletedObject) { sendDeletedObject = false; ret deletedObject; }
        throw new NoSuchElementException;
      }

      lastReturned = index;
      for (index += 1; index < length &&
                       (objects[index] == 0 ||
                        objects[index] == deletedObject); index++)
        ;

      ret objects[lastReturned];
    }

    @Override
    public void remove() {
        ifndef NoModCount
          if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        endifndef
        if (lastReturned == -1 || lastReturned == -2)
          throw new IllegalStateException();
        // delete object
        if (objects[lastReturned] != 0 && objects[lastReturned] != deletedObject) {
          objects[lastReturned] = deletedObject;
          elements--;
          ifndef NoModCount
            modCount++;
            expectedModCount = modCount; // this is expected; we made the change
          endifndef
        }
    }
  }
  
  int capacity() { ret objects.length; }
  
  // returns true if there was a shrink
  bool shrinkToFactor(double factor) {
    if (factor > LOAD_FACTOR)
      fail("Shrink factor must be equal to or smaller than load factor: " + factor + " / " + LOAD_FACTOR);
    int newCapacity = max(INITIAL_SIZE, iround(size()/factor);
    if (newCapacity >= capacity()) false;
    rehash(newCapacity);
    true;
  }
  
  int hash(long l) { ret main hashCode(l); }
}