/*

 * #!

 * 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); }

}