/*
* Copyright 2005 Ralf Joachim
*
* 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.
*/
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;
/**
* An IdentitySet that uses reference-equality instead of object-equality. According
* to its special function it violates some design contracts of the Set
* interface.
*
* @author Ralf Joachim
* @version $Revision: 7491 $ $Date: 2006-04-13 10:49:49 -0600 (Thu, 13 Apr 2006) $
* @since 0.9.9
*/
public final class IdentitySet implements Set {
//--------------------------------------------------------------------------
/** Default number of buckets. */
private static final int DEFAULT_CAPACITY = 17;
/** Default load factor. */
private static final float DEFAULT_LOAD = 0.75f;
/** Default number of entries. */
private static final int DEFAULT_ENTRIES = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD);
/** Default factor to increment capacity. */
private static final int DEFAULT_INCREMENT = 2;
/** First prime number to check is 3 as we prevent 2 by design. */
private static final int FIRST_PRIME_TO_CHECK = 3;
//--------------------------------------------------------------------------
/** Number of buckets. */
private int _capacity;
/** Maximum number of entries before rehashing. */
private int _maximum;
/** Buckets. */
private Entry[] _buckets;
/** Number of map entries. */
private int _entries = 0;
//--------------------------------------------------------------------------
/**
* Construct a set with default capacity.
*/
public IdentitySet() {
_capacity = DEFAULT_CAPACITY;
_maximum = DEFAULT_ENTRIES;
_buckets = new Entry[DEFAULT_CAPACITY];
}
/**
* Construct a set with given capacity.
*
* @param capacity The capacity of entries this set should be initialized with.
*/
public IdentitySet(final int capacity) {
_capacity = capacity;
_maximum = (int) (capacity * DEFAULT_LOAD);
_buckets = new Entry[capacity];
}
/**
* {@inheritDoc}
* @see java.util.Collection#clear()
*/
public void clear() {
_capacity = DEFAULT_CAPACITY;
_maximum = DEFAULT_ENTRIES;
_buckets = new Entry[DEFAULT_CAPACITY];
_entries = 0;
}
/**
* {@inheritDoc}
* @see java.util.Collection#size()
*/
public int size() { return _entries; }
/**
* {@inheritDoc}
* @see java.util.Collection#isEmpty()
*/
public boolean isEmpty() { return (_entries == 0); }
/**
* {@inheritDoc}
* @see java.util.Collection#add(java.lang.Object)
*/
public boolean add(final Object key) {
int hash = System.identityHashCode(key);
int index = hash % _capacity;
if (index < 0) { index = -index; }
Entry entry = _buckets[index];
Entry prev = null;
while (entry != null) {
if (entry.getKey() == key) {
// There is already a mapping for this key.
return false;
}
prev = entry;
entry = entry.getNext();
}
if (prev == null) {
// There is no previous entry in this bucket.
_buckets[index] = new Entry(key, hash);
} else {
// Next entry is empty so we have no mapping for this key.
prev.setNext(new Entry(key, hash));
}
_entries++;
if (_entries > _maximum) { rehash(); }
return true;
}
/**
* Rehash the map into a new array with increased capacity.
*/
private void rehash() {
long nextCapacity = _capacity * DEFAULT_INCREMENT;
if (nextCapacity > Integer.MAX_VALUE) { return; }
nextCapacity = nextPrime(nextCapacity);
if (nextCapacity > Integer.MAX_VALUE) { return; }
int newCapacity = (int) nextCapacity;
Entry[] newBuckets = new Entry[newCapacity];
Entry entry = null;
Entry temp = null;
Entry next = null;
int newIndex = 0;
for (int index = 0; index < _capacity; index++) {
entry = _buckets[index];
while (entry != null) {
next = entry.getNext();
newIndex = entry.getHash() % newCapacity;
if (newIndex < 0) { newIndex = -newIndex; }
temp = newBuckets[newIndex];
if (temp == null) {
// First entry of the bucket.
entry.setNext(null);
} else {
// Hook entry into beginning of the buckets chain.
entry.setNext(temp);
}
newBuckets[newIndex] = entry;
entry = next;
}
}
_capacity = newCapacity;
_maximum = (int) (newCapacity * DEFAULT_LOAD);
_buckets = newBuckets;
}
/**
* Find next prime number greater than minimum.
*
* @param minimum The minimum (exclusive) value of the next prime number.
* @return The next prime number greater than minimum.
*/
private long nextPrime(final long minimum) {
long candidate = ((minimum + 1) / 2) * 2 + 1;
while (!isPrime(candidate)) { candidate += 2; }
return candidate;
}
/**
* Check for prime number.
*
* @param candidate Number to be checked for being a prime number.
* @return true if the given number is a prime number
* false otherwise.
*/
private boolean isPrime(final long candidate) {
if ((candidate / 2) * 2 == candidate) { return false; }
long stop = candidate / 2;
for (long i = FIRST_PRIME_TO_CHECK; i < stop; i += 2) {
if ((candidate / i) * i == candidate) { return false; }
}
return true;
}
/**
* {@inheritDoc}
* @see java.util.Collection#contains(java.lang.Object)
*/
public boolean contains(final Object key) {
int hash = System.identityHashCode(key);
int index = hash % _capacity;
if (index < 0) { index = -index; }
Entry entry = _buckets[index];
while (entry != null) {
if (entry.getKey() == key) { return true; }
entry = entry.getNext();
}
return false;
}
/**
* {@inheritDoc}
* @see java.util.Collection#remove(java.lang.Object)
*/
public boolean remove(final Object key) {
int hash = System.identityHashCode(key);
int index = hash % _capacity;
if (index < 0) { index = -index; }
Entry entry = _buckets[index];
Entry prev = null;
while (entry != null) {
if (entry.getKey() == key) {
// Found the entry.
if (prev == null) {
// First element in bucket matches.
_buckets[index] = entry.getNext();
} else {
// Remove the entry from the chain.
prev.setNext(entry.getNext());
}
_entries--;
return true;
}
prev = entry;
entry = entry.getNext();
}
return false;
}
/**
* {@inheritDoc}
* @see java.util.Collection#iterator()
*/
public Iterator iterator() {
return new IdentityIterator();
}
/**
* {@inheritDoc}
* @see java.util.Collection#toArray()
*/
public Object[] toArray() {
Object[] result = new Object[_entries];
int j = 0;
for (int i = 0; i < _capacity; i++) {
Entry entry = _buckets[i];
while (entry != null) {
result[j++] = entry.getKey();
entry = entry.getNext();
}
}
return result;
}
/**
* {@inheritDoc}
* @see java.util.Collection#toArray(java.lang.Object[])
*/
public Object[] toArray(final Object[] a) {
Object[] result = a;
if (result.length < _entries) {
result = (Object[]) java.lang.reflect.Array.newInstance(
result.getClass().getComponentType(), _entries);
}
int j = 0;
for (int i = 0; i < _capacity; i++) {
Entry entry = _buckets[i];
while (entry != null) {
result[j++] = entry.getKey();
entry = entry.getNext();
}
}
while (j < result.length) {
result[j++] = null;
}
return result;
}
/**
* In contrast with the design contract of the Set interface this method
* has not been implemented and throws a UnsupportedOperationException.
*
* {@inheritDoc}
* @see java.util.Set#containsAll
*/
public boolean containsAll(final Collection c) {
throw new UnsupportedOperationException();
}
/**
* This optional method has not been implemented for IdentitySet instead
* it throws a UnsupportedOperationException as defined in the
* Set interface.
*
* {@inheritDoc}
* @see java.util.Set#addAll
*/
public boolean addAll(final Collection c) {
throw new UnsupportedOperationException();
}
/**
* This optional method has not been implemented for IdentitySet instead
* it throws a UnsupportedOperationException as defined in the
* Set interface.
*
* {@inheritDoc}
* @see java.util.Set#removeAll
*/
public boolean removeAll(final Collection c) {
throw new UnsupportedOperationException();
}
/**
* This optional method has not been implemented for IdentitySet instead
* it throws a UnsupportedOperationException as defined in the
* Set interface.
*
* {@inheritDoc}
* @see java.util.Set#retainAll
*/
public boolean retainAll(final Collection c) {
throw new UnsupportedOperationException();
}
//--------------------------------------------------------------------------
/**
* An entry of the IdentitySet.
*/
public final class Entry {
/** Key of entry. */
private Object _key;
/** Identity hashcode of key. */
private int _hash;
/** Reference to next entry. */
private Entry _next = null;
/**
* Construct an entry.
*
* @param key Key of entry.
* @param hash Identity hashcode of key.
*/
public Entry(final Object key, final int hash) {
_key = key;
_hash = hash;
}
/**
* Get key of entry.
*
* @return Key of entry.
*/
public Object getKey() { return _key; }
/**
* Get identity hashcode of key.
*
* @return Identity hashcode of key.
*/
public int getHash() { return _hash; }
/**
* Set reference to next entry.
*
* @param next New reference to next entry.
*/
public void setNext(final Entry next) { _next = next; }
/**
* Get reference to next entry.
*
* @return Reference to next entry.
*/
public Entry getNext() { return _next; }
}
//--------------------------------------------------------------------------
/**
* An iterator over all entries of the IdentitySet.
*/
private class IdentityIterator implements Iterator {
/** Index of the current bucket. */
private int _index = 0;
/** The next entry to be returned. null when there is none. */
private Entry _next = _buckets[0];
/**
* Construct a iterator over all entries of the IdentitySet.
*/
public IdentityIterator() {
if (_entries > 0) {
while ((_next == null) && (++_index < _capacity)) {
_next = _buckets[_index];
}
}
}
/**
* {@inheritDoc}
* @see java.util.Iterator#hasNext()
*/
public boolean hasNext() {
return (_next != null);
}
/**
* {@inheritDoc}
* @see java.util.Iterator#next()
*/
public Object next() {
Entry entry = _next;
if (entry == null) { throw new NoSuchElementException(); }
_next = entry.getNext();
while ((_next == null) && (++_index < _capacity)) {
_next = _buckets[_index];
}
return entry.getKey();
}
/**
* This optional method is not implemented for IdentityIterator
* instead it throws a UnsupportedOperationException as defined
* in the Iterator interface.
*
* @see java.util.Iterator#remove()
*/
public void remove() {
throw new UnsupportedOperationException();
}
}
//--------------------------------------------------------------------------
}