Hash table and linked list implementation of the Set interface, with predictable iteration order. More...

#include <src/main/decaf/util/LinkedHashSet.h>

Inheritance diagram for decaf::util::LinkedHashSet< E, HASHCODE >:

Public Member Functions

LinkedHashSet ()

Constructs a new, empty set; the backing HashMap instance has default initial capacity (16) and load factor (0.75). More...

LinkedHashSet (int capacity)

Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and default load factor (0.75). More...

LinkedHashSet (int capacity, float loadFactor)

Constructs a new instance of. More...

LinkedHashSet (const Collection< E > &collection)

Constructs a new set containing the elements in the specified collection. More...

virtual ~LinkedHashSet ()

virtual std::string toString () const

Public Member Functions inherited from decaf::util::HashSet< E, HASHCODE >

HashSet ()

Constructs a new, empty set; the backing HashMap instance has default initial capacity (16) and load factor (0.75). More...

HashSet (int capacity)

Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and default load factor (0.75). More...

HashSet (int capacity, float loadFactor)

Constructs a new instance of. More...

HashSet (const Collection< E > &collection)

Constructs a new set containing the elements in the specified collection. More...

HashSet (const HashSet< E > &collection)

Constructs a new set containing the elements in the specified HashSet. More...

virtual ~HashSet ()

HashSet< E > & operator= (const Collection< E > &collection)

virtual bool add (const E &value)

Adds the specified element to this set if it is not already present. More...

virtual void clear ()

Removes all elements from this. More...

virtual bool contains (const E &value) const

Searches this. More...

virtual bool isEmpty () const

Returns true if this. More...

virtual Iterator< E > * iterator ()

Returns an Iterator on the elements of this. More...

virtual Iterator< E > * iterator () const

virtual bool remove (const E &value)

Removes the specified element from this set if it is present. More...

virtual int size () const

Returns the number of elements in this. More...

Public Member Functions inherited from decaf::util::AbstractSet< E >

AbstractSet ()

virtual ~AbstractSet ()

virtual bool removeAll (const Collection< E > &collection)

Removes all this collection's elements that are also contained in the specified collection (optional operation).After this call returns, this collection will contain no elements in common with the specified collection.

Parameters

collection The Collection whose elements are to be removed from this one.

Returns: true if the collection changed as a result of this call.

Exceptions

UnsupportedOperationExceptio	if this is an unmodifiable collection.
NullPointerException	if the Collection is a container of pointers and does not allow NULL values.

This implementation iterates over this collection, checking each element returned by the iterator in turn to see if it's contained in the specified collection. If it's so contained, it's removed from this collection with the iterator's remove method.Note that this implementation will throw an UnsupportedOperationException if the iterator returned by the iterator method does not implement the remove method and this collection contains one or more elements in common with the specified collection. More...

Public Member Functions inherited from decaf::util::Set< E >

virtual ~Set ()

Public Member Functions inherited from decaf::util::Collection< E >

virtual ~Collection ()

Public Member Functions inherited from decaf::lang::Iterable< E >

virtual ~Iterable ()

Public Member Functions inherited from decaf::util::concurrent::Synchronizable

virtual ~Synchronizable ()

Public Member Functions inherited from decaf::util::AbstractCollection< E >

AbstractCollection ()

AbstractCollection (const AbstractCollection &other)

Copy Constructor, copy element from the source collection to this collection after clearing any element stored in this collection. More...

virtual ~AbstractCollection ()

AbstractCollection< E > & operator= (const AbstractCollection< E > &collection)

Assignment Operator, copy element from the source collection to this collection after clearing any element stored in this collection. More...

virtual bool containsAll (const Collection< E > &collection) const

Returns true if this collection contains all of the elements in the specified collection.

Parameters

collection The Collection to compare to this one.

Exceptions

NullPointerException if the Collection contains pointers and the Collection does not allow for NULL elements (optional check).

More...

virtual bool equals (const Collection< E > &collection) const

Answers true if this Collection and the one given are the same size and if each element contained in the Collection given is equal to an element contained in this collection. More...

virtual void copy (const Collection< E > &collection)

Renders this Collection as a Copy of the given Collection. More...

virtual bool add (const E &value DECAF_UNUSED)

virtual bool addAll (const Collection< E > &collection)

Adds all of the elements in the specified collection to this collection.The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified collection is this collection, and this collection is nonempty.)

Parameters

collection The Collection whose elements are added to this one.

Returns: true if this collection changed as a result of the call

Exceptions

UnsupportedOperationExceptio	if this is an unmodifiable collection.
NullPointerException	if the Collection is a container of pointers and does not allow NULL values.
IllegalArgumentException	if some property of an element prevents it from being added to this collection
IllegalStateException	if an element cannot be added at this time due to insertion restrictions.

More...

virtual bool retainAll (const Collection< E > &collection)

Retains only the elements in this collection that are contained in the specified collection (optional operation).In other words, removes from this collection all of its elements that are not contained in the specified collection.

Parameters

collection The Collection whose elements are to be retained.

Returns: true if the collection changed as a result of this call.

Exceptions

UnsupportedOperationExceptio	if this is an unmodifiable collection.
NullPointerException	if the Collection is a container of pointers and does not allow NULL values.

More...

virtual std::vector< E > toArray () const

Answers an STL vector containing copies of all elements contained in this Collection. More...

virtual void lock ()

Locks the object. More...

virtual bool tryLock ()

Attempts to Lock the object, if the lock is already held by another thread than this method returns false. More...

virtual void unlock ()

Unlocks the object. More...

virtual void wait ()

Waits on a signal from this object, which is generated by a call to Notify. More...

virtual void wait (long long millisecs)

Waits on a signal from this object, which is generated by a call to Notify. More...

virtual void wait (long long millisecs, int nanos)

Waits on a signal from this object, which is generated by a call to Notify. More...

virtual void notify ()

Signals a waiter on this object that it can now wake up and continue. More...

virtual void notifyAll ()

Signals the waiters on this object that it can now wake up and continue. More...

Additional Inherited Members
Protected Member Functions inherited from decaf::util::HashSet< E, HASHCODE >
	HashSet (HashMap< E, Set< E > , HASHCODE > backingMap)
	Protected constructor for use by subclasses that wish to use an alternate type of backing Map. More...

Protected Attributes inherited from decaf::util::HashSet< E, HASHCODE >
HashMap< E, Set< E > , HASHCODE >	backingMap

Protected Attributes inherited from decaf::util::AbstractCollection< E >
util::concurrent::Mutex	mutex

Detailed Description

template<typename E, typename HASHCODE = HashCode<E>>
class decaf::util::LinkedHashSet< E, HASHCODE >

Hash table and linked list implementation of the Set interface, with predictable iteration order.

This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set. (An element e is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true immediately prior to the invocation.)

This implementation spares its clients from the unspecified, generally chaotic ordering provided by HashSet, without incurring the increased cost associated with TreeSet. It can be used to produce a copy of a set that has the same order as the original, regardless of the original set's implementation:

void foo(const Set<E& s) { Set<E>* copy = new LinkedHashSet<E>(s); ... }

This technique is particularly useful if a module takes a set on input, copies it, and later returns results whose order is determined by that of the copy. (Clients generally appreciate having things returned in the same order they were presented.)

This class provides all of the optional Set operations, and permits null elements. Like HashSet, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashSet, due to the added expense of maintaining the linked list, with one exception: Iteration over a LinkedHashSet requires time proportional to the size of the set, regardless of its capacity. Iteration over a HashSet is likely to be more expensive, requiring time proportional to its capacity.

A linked hash set has two parameters that affect its performance: initial capacity and load factor. They are defined precisely as for HashSet. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashSet, as iteration times for this class are unaffected by capacity.

Note that this implementation is not synchronized. If multiple threads access a linked hash 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. If no such object exists, the set should be "wrapped" using the Collections.synchronizedSet method. This is best done at creation time, to prevent accidental unsynchronized access to the set:

Set<E>* s = Collections::synchronizedSet(new LinkedHashSet<E>(...));

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 will throw 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.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

Since: 1.0

Constructor & Destructor Documentation

template<typename E , typename HASHCODE = HashCode<E>>

decaf::util::LinkedHashSet< E, HASHCODE >::LinkedHashSet ( )

inline

Constructs a new, empty set; the backing HashMap instance has default initial capacity (16) and load factor (0.75).

template<typename E , typename HASHCODE = HashCode<E>>

decaf::util::LinkedHashSet< E, HASHCODE >::LinkedHashSet ( int capacity )

inline

Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and default load factor (0.75).

Parameters

capacity The initial capacity of this LinkedHashSet.

template<typename E , typename HASHCODE = HashCode<E>>

decaf::util::LinkedHashSet< E, HASHCODE >::LinkedHashSet	(	int	capacity,
		float	loadFactor
	)

inline

Constructs a new instance of.

HashSet

with the specified capacity and load factor.

Parameters

capacity	The initial capacity for this LinkedHashSet.
loadFactor	The initial load factor for this LinkedHashSet.

template<typename E , typename HASHCODE = HashCode<E>>

decaf::util::LinkedHashSet< E, HASHCODE >::LinkedHashSet ( const Collection< E > & collection )

inline

Constructs a new set containing the elements in the specified collection.

The HashMap is created with default load factor (0.75) and an initial capacity sufficient to contain the elements in the specified collection.

Parameters

collection The collection of elements to add to this LinkedHashSet.

References decaf::util::HashSet< E, HASHCODE >::add(), and decaf::lang::Iterable< E >::iterator().

template<typename E , typename HASHCODE = HashCode<E>>

virtual decaf::util::LinkedHashSet< E, HASHCODE >::~LinkedHashSet ( )

inlinevirtual

Member Function Documentation

template<typename E , typename HASHCODE = HashCode<E>>

virtual std::string decaf::util::LinkedHashSet< E, HASHCODE >::toString ( ) const

inlinevirtual

Reimplemented from decaf::util::HashSet< E, HASHCODE >.

The documentation for this class was generated from the following file:

src/main/decaf/util/LinkedHashSet.h

Public Member Functions

Additional Inherited Members

Detailed Description

template<typename E, typename HASHCODE = HashCode<E>> class decaf::util::LinkedHashSet< E, HASHCODE >

Constructor & Destructor Documentation

Member Function Documentation

template<typename E, typename HASHCODE = HashCode<E>>
class decaf::util::LinkedHashSet< E, HASHCODE >