/*

 * #!

 * 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

// Implements the Set interface more compactly than

// java.util.HashSet by using a closed hashtable

// & allows custom hasher.

sclass CustomCompactHashSet<A> extends AbstractSet<A> {

  protected final static int INITIAL_SIZE = 3;

  protected final static double LOAD_FACTOR = 0.75;

  protected final static Object nullObject = new Object();

  protected final static Object deletedObject = new Object();

  protected int elements;

  protected int freecells;

  protected A[] objects;

  protected int modCount;

  Hasher<A> hasher; // optional

  *() {

    this(INITIAL_SIZE);

  }

  *(int size) {

    // NOTE: If array size is 0, we get a

    // "java.lang.ArithmeticException: / by zero" in add(Object).

    objects = (A[]) new Object[(size==0 ? 1 : size)];

    elements = 0;

    freecells = objects.length;

    modCount = 0;

  }

  *(Collection<A> c) {

    this(c.size());

    addAll(c);

  }

  *(Hasher<A> hasher) {

    this();

    this.hasher = hasher;

  }

  @Override

  public Iterator<A> iterator() {

    return new CompactHashIterator<A>();

  }

  @Override

  public int size() {

    return elements;

  }

  @Override

  public boolean isEmpty() {

    return elements == 0;

  }

  @Override

  public boolean contains(Object o) {

    ret find(o) != null;

  }

  synchronized A find(O o) {

    if (o == null) o = nullObject;

    int hash = elementHashCode(o);

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

    int offset = 1;

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

    while(objects[index] != null &&

        !(elementHashCode(objects[index]) == hash &&

          elementEquals(objects[index], o))) {

      index = ((index + offset) & 0x7FFFFFFF) % objects.length;

      offset = offset*2 + 1;

      if (offset == -1)

        offset = 2;

    }

    ret objects[index];

  }

  bool removeIfSame(O o) {

    A value = find(o);

    if (value == o) {

      remove(value);

      true;

    }

    false;

  }

  @Override

  synchronized public boolean add(Object o) {

    if (o == null) o = nullObject;

    int hash = elementHashCode(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] != null &&

          !(elementHashCode(objects[index]) == hash &&

            elementEquals(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] == null) { // wasn't present already

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

        index = deletedix;

      else

        freecells--;

      modCount++;

      elements++;

      // here we face a problem regarding generics:

      // add(A o) is not possible because of the null Object. We cant do 'new A()' or '(A) new Object()'

      // so adding an empty object is a problem here

      // If (! o instanceof A) : This will cause a class cast exception

      // If (o instanceof A) : This will work fine

      objects[index] = (A) o;

      // do we need to rehash?

      if (1 - (freecells / (double) objects.length) > LOAD_FACTOR)

        rehash();

      return true;

    } else // was there already 

      return false;

  }

  @Override

  synchronized public boolean remove(Object o) {

    if (o == null) o = nullObject;

    int hash = elementHashCode(o);

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

    int offset = 1;

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

    while(objects[index] != null &&

          !(elementHashCode(objects[index]) == hash &&

            elementEquals(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] != null) {

      // we found the object

      // same problem here as with add

      objects[index] = (A) deletedObject;

      modCount++;

      elements--;

      return true;

    } else

      // we did not find the object

      return false;

  }

  @Override

  synchronized public void clear() {

    elements = 0;

    for (int ix = 0; ix < objects.length; ix++)

      objects[ix] = null;

    freecells = objects.length;

    modCount++;

  }

  @Override

  synchronized public Object[] toArray() {

    Object[] result = new Object[elements];

    Object[] objects = this.objects;

    int pos = 0;

    for (int i = 0; i < objects.length; i++)

      if (objects[i] != null && objects[i] != deletedObject) {

        if (objects[i] == nullObject)

          result[pos++] = null;

        else

          result[pos++] = objects[i];

      }

    // unchecked because it should only contain A

    return result;

  }

  // not sure if this needs to have generics

  @Override

  synchronized public <T> T[] toArray(T[] a) {

    int size = elements;

    if (a.length < size)

      a = (T[])java.lang.reflect.Array.newInstance(

                                 a.getClass().getComponentType(), size);

    A[] objects = this.objects;

    int pos = 0;

    for (int i = 0; i < objects.length; i++)

      if (objects[i] != null && objects[i] != deletedObject) {

        if (objects[i] == nullObject)

          a[pos++] = null;

        else

          a[pos++] = (T) objects[i];

      }

    return a;

  }

  protected void rehash() {

    int gargagecells = objects.length - (elements + freecells);

    if (gargagecells / (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")

    A[] newObjects = (A[]) new Object[newCapacity];

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

      Object o = objects[ix];

      if (o == null || o == deletedObject)

        continue;

      int hash = elementHashCode(o);

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

      int offset = 1;

      // search for the object

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

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

        offset = offset*2 + 1;

        if (offset == -1)

          offset = 2;

      }

      newObjects[index] = (A) o;

    }

    objects = newObjects;

    freecells = objects.length - elements;

  }

  private class CompactHashIterator<T> implements Iterator<T> {

    private int index;

    private int lastReturned = -1;

    private int expectedModCount;

    @SuppressWarnings("empty-statement")

    public CompactHashIterator() {

      synchronized(CustomCompactHashSet.this) {

        for (index = 0; index < objects.length &&

                        (objects[index] == null ||

                        objects[index] == deletedObject); index++)

          ;

        expectedModCount = modCount;

      }

    }

    @Override

    public boolean hasNext() {

      synchronized(CustomCompactHashSet.this) {

        return index < objects.length;

      }

    }

    @SuppressWarnings("empty-statement")

    @Override

    public T next() {

      synchronized(CustomCompactHashSet.this) {

        /*if (modCount != expectedModCount)

          throw new ConcurrentModificationException();*/

        int length = objects.length;

        if (index >= length) {

          lastReturned = -2;

          throw new NoSuchElementException();

        }

        lastReturned = index;

        for (index += 1; index < length &&

                         (objects[index] == null ||

                          objects[index] == deletedObject); index++)

          ;

        if (objects[lastReturned] == nullObject)

          return null;

        else

          return (T) objects[lastReturned];

      }

    }

    @Override

    public void remove() {

      synchronized(CustomCompactHashSet.this) {

        if (modCount != expectedModCount)

          throw new ConcurrentModificationException();

        if (lastReturned == -1 || lastReturned == -2)

          throw new IllegalStateException();

        // delete object

        if (objects[lastReturned] != null && objects[lastReturned] != deletedObject) {

          objects[lastReturned] = (A) deletedObject;

          elements--;

          modCount++;

          expectedModCount = modCount; // this is expected; we made the change

        }

      }

    }

  }

  int elementHashCode(O o) {

    if (hasher == null || o == nullObject || o == deletedObject) ret _hashCode(o);

    ret hasher.hashCode((A) o);

  }

  bool elementEquals(O a, O b) {

    if (hasher == null) ret eq(a, b);

    if (a == nullObject || a == deletedObject

      || b == nullObject || b == deletedObject) ret a == b;

    ret hasher.equals((A) a, (A) b);

  }

}