/*

 * #!

 * 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. 

sclass CompactHashSet<A> extends java.util.AbstractSet<A> {

  protected final static int INITIAL_SIZE = 0;

  protected final static int FIRST_INCREMENT = 3; // 2 or 3 are useful

  public 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;

  ifndef NoModCount

  protected int modCount;

  endifndef

  CompactHashSet() {

    this(INITIAL_SIZE);

  }

  *(int size) {

    objects = (A[]) (size == 0 ? emptyObjectArray() : new O[size]);

    elements = 0;

    freecells = objects.length;

    ifndef NoModCount

      modCount = 0;

    endifndef

  }

  *(Collection<A> c) {

    this(c.size());

    addAll(c);

  }

  @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 (objects.length == 0) null;

    if (o == null) o = nullObject;

    int hash = o.hashCode();

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

    int offset = 1;

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

    while(objects[index] != null &&

          !(objects[index].hashCode() == hash &&

            objects[index].equals(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 (objects.length == 0) rehash(FIRST_INCREMENT);

    if (o == null) o = nullObject;

    int hash = o.hashCode();

    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 &&

          !(objects[index].hashCode() == hash &&

            objects[index].equals(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--;

      ifndef NoModCount

        modCount++;

      endifndef

      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();

      true;

    } else // was there already 

      return false;

  }

  @Override

  synchronized public boolean remove(Object o) {

    if (objects.length == 0) false;

    if (o == null) o = nullObject;

    int hash = o.hashCode();

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

    int offset = 1;

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

    while(objects[index] != null &&

          !(objects[index].hashCode() == hash &&

            objects[index].equals(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;

      ifndef NoModCount

        modCount++;

      endifndef

      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;

    ifndef NoModCount

      modCount++;

    endifndef

  }

  @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 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")

    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 = o.hashCode();

      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;

    ifndef NoModCount

      private int expectedModCount;

    endifndef

    @SuppressWarnings("empty-statement")

    public CompactHashIterator() {

      synchronized(CompactHashSet.this) {

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

                        (objects[index] == null ||

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

          ;

        ifndef NoModCount

          expectedModCount = modCount;

        endifndef

      }

    }

    @Override

    public boolean hasNext() {

      synchronized(CompactHashSet.this) {

        return index < objects.length;

      }

    }

    @SuppressWarnings("empty-statement")

    @Override

    public T next() {

      synchronized(CompactHashSet.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(CompactHashSet.this) {

        ifndef NoModCount

          if (modCount != expectedModCount)

            throw new ConcurrentModificationException();

        endifndef

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

          throw new IllegalStateException();

        // delete object

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

          objects[lastReturned] = (A) deletedObject;

          elements--;

          ifndef NoModCount

            modCount++;

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

          endifndef

        }

      }

    }

  }

  synchronized int capacity() { ret objects.length; }

  // returns true if there was a shrink

  synchronized 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;

  }

}