net.walend.collection
Class AbstractHashSet

java.lang.Object
  |
  +--net.walend.collection.AbstractHashSet
All Implemented Interfaces:
java.lang.Cloneable, Collection, HasState, java.io.Serializable, Set
Direct Known Subclasses:
AbstractHashSetOfFreezables, HashSet, MutableHashSet

public abstract class AbstractHashSet
extends java.lang.Object
implements Set, java.lang.Cloneable, java.io.Serializable

This class implements the net.walend.collection.Set interface, based very heavily on the java.util.HashSet class by Josh Bloch. Any mistakes I'm sure are my own and not his. This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the AbstractHashSet instance's size (the number of elements) plus the "capacity" of the backing MutableHashMap instance (the number of buckets). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

Note that this implementation is not synchronized. If multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set. The iterators returned by this class's iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the Iterator throws a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Since:
200010705
Author:
David Walend

Field Summary
private  MutableHashMap map
           
private static java.lang.Object PRESENT
           
(package private) static long serialVersionUID
           
 
Fields inherited from interface net.walend.collection.Set
EMPTY
 
Constructor Summary
protected AbstractHashSet()
          Constructs a new, empty set; the backing MutableHashMap instance has default capacity and load factor, which is 0.75, and uses the DefaultIdentitor.
protected AbstractHashSet(Collection c)
          Constructs a new set containing the elements in the specified collection.
protected AbstractHashSet(java.util.Collection c)
          Constructs a new set containing the elements in the specified java.util.Collection.
protected AbstractHashSet(Identitor identitor)
          Constructs a new, empty set; the backing MutableHashMap instance has default capacity and load factor, which is 0.75.
protected AbstractHashSet(Identitor identitor, int initialCapacity)
          Constructs a new, empty set; the backing MutableHashMap instance has the specified initial capacity and default load factor, which is 0.75.
protected AbstractHashSet(Identitor identitor, int initialCapacity, float loadFactor)
          Constructs a new, empty set; the backing MutableHashMap instance has the specified initial capacity and the specified load factor.
protected AbstractHashSet(int initialCapacity)
          Constructs a new, empty set; the backing MutableHashMap instance has the specified initial capacity and default load factor, which is 0.75.
protected AbstractHashSet(int initialCapacity, float loadFactor)
          Constructs a new, empty set; the backing MutableHashMap instance has the specified initial capacity and the specified load factor.
 
Method Summary
protected  boolean add(java.lang.Object o)
          Adds the specified element to this set if it is not already present.
protected  boolean addAll(Collection c)
          Adds all the Objects in c to this MutableCollection by using the add() method.
protected  void clear()
          Removes all of the elements from this set.
 java.lang.Object clone()
          Returns a shallow copy of this AbstractHashSet instance: the elements themselves are not cloned.
 boolean contains(java.lang.Object o)
          Returns true if this set contains the specified element.
 boolean containsAll(Collection c)
          Returns true if this collection contains all of the Objects in the specified collection.
 Identitor getIdentitor()
          Returns the Identitor for this Collection.
 java.util.Collection getJavaCollection()
          Return a java.util.Collection of these Objects.
 java.util.Set getJavaSet()
          Return a java.util.Collection of these Objects.
 java.lang.Class getPrincipleInterface()
          Returns the class's principle interface for state comparisons.
 boolean isEmpty()
          Returns true if this set contains no elements.
 java.util.Iterator iterator()
          Returns an iterator over the elements in this set.
private  void readObject(java.io.ObjectInputStream s)
          Reconstitute the AbstractHashSet instance from a stream (that is, deserialize it).
protected  boolean remove(java.lang.Object o)
          Removes the given element from this set if it is present.
protected  boolean removeAll(Collection c)
          Removes all the Objects in c from this MutableCollection by using the remove() method.
protected  boolean retainAll(Collection c)
          Retains only the Objects in this collection that are contained in c by using the contains() and remove() methods.
 boolean sameContentsAs(Collection c)
          Returns true if this Collection's contents are equal to c's.
 boolean sameStateAs(HasState victem)
          If two HasStates have the same internal state, return true.
 int size()
          Returns the number of elements in this set (its cardinality).
 java.lang.String toString()
           
private  void writeObject(java.io.ObjectOutputStream s)
          Save the state of this AbstractHashSet instance to a stream (that is, serialize this set).
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

serialVersionUID

static final long serialVersionUID

map

private transient MutableHashMap map

PRESENT

private static final java.lang.Object PRESENT
Constructor Detail

AbstractHashSet

protected AbstractHashSet()
Constructs a new, empty set; the backing MutableHashMap instance has default capacity and load factor, which is 0.75, and uses the DefaultIdentitor.


AbstractHashSet

protected AbstractHashSet(Collection c)
Constructs a new set containing the elements in the specified collection. The capacity of the backing MutableHashMap instance is twice the size of the specified collection or eleven (whichever is greater), the default load factor (which is 0.75) is used. It uses the same Identitor as c.

Parameters:
c - the collection whose elements are to be placed into this set.

AbstractHashSet

protected AbstractHashSet(java.util.Collection c)
Constructs a new set containing the elements in the specified java.util.Collection. The capacity of the backing MutableHashMap instance is twice the size of the specified collection or eleven (whichever is greater), and the default load factor (which is 0.75) is used. It uses the DefaultIdentitor.

Parameters:
c - the collection whose elements are to be placed into this set.

AbstractHashSet

protected AbstractHashSet(int initialCapacity,
                          float loadFactor)
Constructs a new, empty set; the backing MutableHashMap instance has the specified initial capacity and the specified load factor. It uses the DefaultIdentitor.

Parameters:
initialCapacity - the initial capacity of the hash map.
loadFactor - the load factor of the hash map.
Throws:
java.lang.IllegalArgumentException - if the initial capacity is less than zero, or if the load factor is nonpositive.

AbstractHashSet

protected AbstractHashSet(int initialCapacity)
Constructs a new, empty set; the backing MutableHashMap instance has the specified initial capacity and default load factor, which is 0.75. It uses the DefaultIdentitor.

Parameters:
initialCapacity - the initial capacity of the hash table.
Throws:
java.lang.IllegalArgumentException - if the initial capacity is less than zero.

AbstractHashSet

protected AbstractHashSet(Identitor identitor)
Constructs a new, empty set; the backing MutableHashMap instance has default capacity and load factor, which is 0.75. It uses the specified identitor.


AbstractHashSet

protected AbstractHashSet(Identitor identitor,
                          int initialCapacity,
                          float loadFactor)
Constructs a new, empty set; the backing MutableHashMap instance has the specified initial capacity and the specified load factor. It uses the specified identitor.

Parameters:
identitor -
initialCapacity - the initial capacity of the hash map.
loadFactor - the load factor of the hash map.
Throws:
java.lang.IllegalArgumentException - if the initial capacity is less than zero, or if the load factor is nonpositive.

AbstractHashSet

protected AbstractHashSet(Identitor identitor,
                          int initialCapacity)
Constructs a new, empty set; the backing MutableHashMap instance has the specified initial capacity and default load factor, which is 0.75. It uses the specified identitor.

Parameters:
identitor -
initialCapacity - the initial capacity of the hash table.
Throws:
java.lang.IllegalArgumentException - if the initial capacity is less than zero.
Method Detail

getIdentitor

public Identitor getIdentitor()
Returns the Identitor for this Collection.

Specified by:
getIdentitor in interface Collection

size

public int size()
Returns the number of elements in this set (its cardinality).

Specified by:
size in interface Collection
Returns:
the number of elements in this set (its cardinality).

isEmpty

public boolean isEmpty()
Returns true if this set contains no elements.

Specified by:
isEmpty in interface Collection
Returns:
true if this set contains no elements.

contains

public boolean contains(java.lang.Object o)
Returns true if this set contains the specified element.

Specified by:
contains in interface Collection
Parameters:
o - element whose presence in this set is to be tested.
Returns:
true if this set contains the specified element.

iterator

public java.util.Iterator iterator()
Returns an iterator over the elements in this set. The elements are returned in no particular order.

Specified by:
iterator in interface Collection
Returns:
an Iterator over the elements in this set.
See Also:
ConcurrentModificationException

containsAll

public boolean containsAll(Collection c)
Returns true if this collection contains all of the Objects in the specified collection. This method uses the contains() method.

Specified by:
containsAll in interface Collection

sameContentsAs

public boolean sameContentsAs(Collection c)
Returns true if this Collection's contents are equal to c's.

Specified by:
sameContentsAs in interface Collection

getJavaCollection

public java.util.Collection getJavaCollection()
Description copied from interface: Collection
Return a java.util.Collection of these Objects.

Specified by:
getJavaCollection in interface Collection

getJavaSet

public java.util.Set getJavaSet()
Description copied from interface: Set
Return a java.util.Collection of these Objects.

Specified by:
getJavaSet in interface Set

add

protected boolean add(java.lang.Object o)
Adds the specified element to this set if it is not already present.

Parameters:
o - element to be added to this set.
Returns:
true if the set did not already contain the specified element.

remove

protected boolean remove(java.lang.Object o)
Removes the given element from this set if it is present.

Parameters:
o - object to be removed from this set, if present.
Returns:
true if the set contained the specified element.

addAll

protected boolean addAll(Collection c)
Adds all the Objects in c to this MutableCollection by using the add() method. Returns true if this MutableCollection changes.

Throws:
java.lang.UnsupportedOperationException - if this collection does not support the addAll method.
java.lang.ClassCastException - if the class of an element of the specified collection prevents it from being added to this collection.
java.lang.IllegalArgumentException - some aspect of an element of the specified collection prevents it from being added to this collection.

removeAll

protected boolean removeAll(Collection c)
Removes all the Objects in c from this MutableCollection by using the remove() method. Returns true if this Colleciton changes.

Throws:
java.lang.UnsupportedOperationException - if the removeAll method is not supported by this collection.

retainAll

protected boolean retainAll(Collection c)
Retains only the Objects in this collection that are contained in c by using the contains() and remove() methods. Returns true if this Colleciton changes.

Throws:
java.lang.UnsupportedOperationException - if the retainAll method is not supported by this collection.

clear

protected void clear()
Removes all of the elements from this set.


getPrincipleInterface

public java.lang.Class getPrincipleInterface()
Description copied from interface: HasState
Returns the class's principle interface for state comparisons. If two objects have different principle interfaces, they never have the same state.

Specified by:
getPrincipleInterface in interface HasState

sameStateAs

public boolean sameStateAs(HasState victem)
Description copied from interface: HasState
If two HasStates have the same internal state, return true.

For objects with subobjects, Generally this method should only return true if the internal objects are equal. Implement a contentsHaveSameState() method to determine if the contents have the same state.

Specified by:
sameStateAs in interface HasState

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

clone

public java.lang.Object clone()
Returns a shallow copy of this AbstractHashSet instance: the elements themselves are not cloned.

Overrides:
clone in class java.lang.Object
Returns:
a shallow copy of this set.

writeObject

private void writeObject(java.io.ObjectOutputStream s)
                  throws java.io.IOException
Save the state of this AbstractHashSet instance to a stream (that is, serialize this set).

Throws:
java.io.IOException

readObject

private void readObject(java.io.ObjectInputStream s)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException
Reconstitute the AbstractHashSet instance from a stream (that is, deserialize it).

Throws:
java.io.IOException
java.lang.ClassNotFoundException


Copyright (c) 2000, 2001, David Walend