package weiss.util;
import java.io.Serializable;
/**
* HashSet implementation.
* Matches are based on equals; and hashCode must be consistently defined.
*/
public class HashSet<AnyType> extends AbstractCollection<AnyType> implements Set<AnyType>
{
/**
* Construct an empty HashSet.
*/
public HashSet( )
{
allocateArray( DEFAULT_TABLE_SIZE );
clear( );
}
/**
* Construct a HashSet from any collection.
*/
public HashSet( Collection<? extends AnyType> other )
{
allocateArray( nextPrime( other.size( ) * 2 ) );
clear( );
for( AnyType val : other )
add( val );
}
/**
* Returns the number of items in this collection.
* @return the number of items in this collection.
*/
public int size( )
{
return currentSize;
}
/**
* This method is not part of standard Java.
* Like contains, it checks if x is in the set.
* If it is, it returns the reference to the matching
* object; otherwise it returns null.
* @param x the object to search for.
* @return if contains(x) is false, the return value is null;
* otherwise, the return value is the object that causes
* contains(x) to return true.
*/
public AnyType getMatch( AnyType x )
{
int currentPos = findPos( x );
if( isActive( array, currentPos ) )
return (AnyType) array[ currentPos ].element;
return null;
}
/**
* Tests if some item is in this collection.
* @param x any object.
* @return true if this collection contains an item equal to x.
*/
public boolean contains( Object x )
{
return isActive( array, findPos( x ) );
}
/**
* Tests if item in pos is active.
* @param pos a position in the hash table.
* @param arr the HashEntry array (can be oldArray during rehash).
* @return true if this position is active.
*/
private static boolean isActive( HashEntry [ ] arr, int pos )
{
return arr[ pos ] != null && arr[ pos ].isActive;
}
/**
* Adds an item to this collection.
* @param x any object.
* @return true if this item was added to the collection.
*/
public boolean add( AnyType x )
{
int currentPos = findPos( x );
if( isActive( array, currentPos ) )
return false;
if( array[ currentPos ] == null )
occupied++;
array[ currentPos ] = new HashEntry( x, true );
currentSize++;
modCount++;
if( occupied > array.length / 2 )
rehash( );
return true;
}
/**
* Private routine to perform rehashing.
* Can be called by both add and remove.
*/
private void rehash( )
{
HashEntry [ ] oldArray = array;
// Create a new, empty table
allocateArray( nextPrime( 4 * size( ) ) );
currentSize = 0;
occupied = 0;
// Copy table over
for( int i = 0; i < oldArray.length; i++ )
if( isActive( oldArray, i ) )
add( (AnyType) oldArray[ i ].element );
}
/**
* Removes an item from this collection.
* @param x any object.
* @return true if this item was removed from the collection.
*/
public boolean remove( Object x )
{
int currentPos = findPos( x );
if( !isActive( array, currentPos ) )
return false;
array[ currentPos ].isActive = false;
currentSize--;
modCount++;
if( currentSize < array.length / 8 )
rehash( );
return true;
}
/**
* Change the size of this collection to zero.
*/
public void clear( )
{
currentSize = occupied = 0;
modCount++;
for( int i = 0; i < array.length; i++ )
array[ i ] = null;
}
/**
* Obtains an Iterator object used to traverse the collection.
* @return an iterator positioned prior to the first element.
*/
public Iterator<AnyType> iterator( )
{
return new HashSetIterator( );
}
/**
* This is the implementation of the HashSetIterator.
* It maintains a notion of a current position and of
* course the implicit reference to the HashSet.
*/
private class HashSetIterator implements Iterator<AnyType>
{
private int expectedModCount = modCount;
private int currentPos = -1;
private int visited = 0;
public boolean hasNext( )
{
if( expectedModCount != modCount )
throw new ConcurrentModificationException( );
return visited != size( );
}
public AnyType next( )
{
if( !hasNext( ) )
throw new NoSuchElementException( );
do
{
currentPos++;
} while( currentPos < array.length && !isActive( array, currentPos ) );
visited++;
return (AnyType) array[ currentPos ].element;
}
public void remove( )
{
if( expectedModCount != modCount )
throw new ConcurrentModificationException( );
if( currentPos == -1 || !isActive( array, currentPos ) )
throw new IllegalStateException( );
array[ currentPos ].isActive = false;
currentSize--;
visited--;
modCount++;
expectedModCount++;
}
}
private static class HashEntry implements Serializable
{
public Object element; // the element
public boolean isActive; // false if marked deleted
public HashEntry( Object e )
{
this( e, true );
}
public HashEntry( Object e, boolean i )
{
element = e;
isActive = i;
}
}
/**
* Method that performs quadratic probing resolution.
* @param x the item to search for.
* @return the position where the search terminates.
*/
private int findPos( Object x )
{
int offset = 1;
int currentPos = ( x == null ) ? 0 : Math.abs( x.hashCode( ) % array.length );
while( array[ currentPos ] != null )
{
if( x == null )
{
if( array[ currentPos ].element == null )
break;
}
else if( x.equals( array[ currentPos ].element ) )
break;
currentPos += offset; // Compute ith probe
offset += 2;
if( currentPos >= array.length ) // Implement the mod
currentPos -= array.length;
}
return currentPos;
}
/**
* Internal method to allocate array.
* @param arraySize the size of the array.
*/
private void allocateArray( int arraySize )
{
array = new HashEntry[ nextPrime( arraySize ) ];
}
/**
* Internal method to find a prime number at least as large as n.
* @param n the starting number (must be positive).
* @return a prime number larger than or equal to n.
*/
private static int nextPrime( int n )
{
if( n % 2 == 0 )
n++;
for( ; !isPrime( n ); n += 2 )
;
return n;
}
/**
* Internal method to test if a number is prime.
* Not an efficient algorithm.
* @param n the number to test.
* @return the result of the test.
*/
private static boolean isPrime( int n )
{
if( n == 2 || n == 3 )
return true;
if( n == 1 || n % 2 == 0 )
return false;
for( int i = 3; i * i <= n; i += 2 )
if( n % i == 0 )
return false;
return true;
}
private static final int DEFAULT_TABLE_SIZE = 101;
private int currentSize = 0;
private int occupied = 0;
private int modCount = 0;
private HashEntry [ ] array;
}