#include <BALL/DATATYPE/hashSet.h>

Classes
class	IllegalKey

class	IteratorTraits

struct	Node

Public Types
typedef Key	ValueType

typedef Key	KeyType

typedef Key *	PointerType

typedef Node *	IteratorPosition

Enums
enum	{ INITIAL_CAPACITY = 4, INITIAL_NUMBER_OF_BUCKETS = 3 }

Type definitions
typedef ForwardIterator < HashSet< Key >, ValueType, PointerType, IteratorTraits >	Iterator

typedef ConstForwardIterator < HashSet< Key >, ValueType, PointerType, IteratorTraits >	ConstIterator

typedef Iterator	iterator

typedef ConstIterator	const_iterator

typedef Key	value_type

typedef Key	key_type

typedef Key *	pointer

typedef const Key *	const_pointer

typedef Key &	reference

typedef const Key &	const_reference

typedef Size	size_type

typedef Index	difference_type

Public Member Functions
Iterator	begin ()

Iterator	end ()

ConstIterator	begin () const

ConstIterator	end () const

Constructors and Destructors
	HashSet (Size initial_capacity=INITIAL_CAPACITY, Size number_of_buckets=INITIAL_NUMBER_OF_BUCKETS)

	HashSet (const HashSet &hash_set)

virtual	~HashSet ()

virtual void	clear ()

void	destroy ()

Assignment
void	set (const HashSet &hash_set)

const HashSet &	operator= (const HashSet &rhs)

void	get (HashSet &hash_set) const

void	swap (HashSet &hash_set)

Accessors
Size	getBucketSize () const

Size	getCapacity () const

Size	getSize () const

Size	size () const

Iterator	find (const Key &key)

ConstIterator	find (const Key &key) const

std::pair< Iterator, bool >	insert (const ValueType &item)

Iterator	insert (Iterator pos, const ValueType &item)

Size	erase (const KeyType &key)

void	erase (Iterator pos)

void	erase (Iterator f, Iterator l)

Operators
const HashSet &	operator&= (const HashSet &rhs)

const HashSet &	operator\|= (const HashSet &rhs)

HashSet	operator& (const HashSet &rhs) const

HashSet	operator\| (const HashSet &rhs) const

HashSet	operator+ (const HashSet &rhs) const

HashSet	operator- (const HashSet &rhs) const

const HashSet &	operator+= (const HashSet &rhs)

const HashSet &	operator-= (const HashSet &rhs)

Miscellaneous
virtual void	host (Visitor< HashSet< Key > > &visitor)

Predicates
bool	has (const Key &key) const

bool	isEmpty () const

bool	operator== (const HashSet &hash_set) const

bool	operator!= (const HashSet &hash_set) const

Debugging and Diagnostics
bool	isValid () const

virtual void	dump (std::ostream &s=std::cout, Size depth=0) const

Iteration
bool	apply (UnaryProcessor< ValueType > &processor)

Protected Member Functions
virtual Node *	newNode_ (const ValueType &value, Node *next) const

virtual void	deleteNode_ (Node *node) const

virtual HashIndex	hash (const Key &key) const

virtual bool	needRehashing_ () const

virtual void	rehash ()

Private Member Functions
void	deleteBuckets_ ()

Position	hashBucket_ (const Key &key) const

void	rehash_ ()

Private Attributes
Size	size_

Size	capacity_

vector< Node * >	bucket_

Friends
class	IteratorTraits

Detailed Description

template<class Key>
class BALL::HashSet< Key >

Generic Hash Set Class.

Definition at line 45 of file hashSet.h.

Member Typedef Documentation

template<class Key>

typedef ConstIterator BALL::HashSet< Key >::const_iterator

Definition at line 289 of file hashSet.h.

template<class Key>

typedef const Key* BALL::HashSet< Key >::const_pointer

Definition at line 297 of file hashSet.h.

template<class Key>

typedef const Key& BALL::HashSet< Key >::const_reference

Definition at line 301 of file hashSet.h.

template<class Key>

typedef ConstForwardIterator<HashSet<Key>, ValueType, PointerType, IteratorTraits> BALL::HashSet< Key >::ConstIterator

Definition at line 283 of file hashSet.h.

template<class Key>

typedef Index BALL::HashSet< Key >::difference_type

Definition at line 305 of file hashSet.h.

template<class Key>

typedef ForwardIterator<HashSet<Key>, ValueType, PointerType, IteratorTraits> BALL::HashSet< Key >::Iterator

Definition at line 280 of file hashSet.h.

template<class Key>

typedef Iterator BALL::HashSet< Key >::iterator

Definition at line 287 of file hashSet.h.

template<class Key>

typedef Node* BALL::HashSet< Key >::IteratorPosition

Definition at line 74 of file hashSet.h.

template<class Key>

typedef Key BALL::HashSet< Key >::key_type

Definition at line 293 of file hashSet.h.

template<class Key>

typedef Key BALL::HashSet< Key >::KeyType

Definition at line 55 of file hashSet.h.

template<class Key>

typedef Key* BALL::HashSet< Key >::pointer

Definition at line 295 of file hashSet.h.

template<class Key>

typedef Key* BALL::HashSet< Key >::PointerType

Definition at line 59 of file hashSet.h.

template<class Key>

typedef Key& BALL::HashSet< Key >::reference

Definition at line 299 of file hashSet.h.

template<class Key>

typedef Size BALL::HashSet< Key >::size_type

Definition at line 303 of file hashSet.h.

template<class Key>

typedef Key BALL::HashSet< Key >::value_type

Definition at line 291 of file hashSet.h.

template<class Key>

typedef Key BALL::HashSet< Key >::ValueType

Definition at line 51 of file hashSet.h.

Member Enumeration Documentation

template<class Key>

anonymous enum

Enumerator
INITIAL_CAPACITY	Initial capacity of the hash set.
INITIAL_NUMBER_OF_BUCKETS	Initial number of buckets.

Definition at line 245 of file hashSet.h.

Constructor & Destructor Documentation

template<class Key >

BALL::HashSet< Key >::HashSet	(	Size	initial_capacity = `INITIAL_CAPACITY`,
		Size	number_of_buckets = `INITIAL_NUMBER_OF_BUCKETS`
	)

Default Constructor.

Definition at line 600 of file hashSet.h.

template<class Key >

BALL::HashSet< Key >::HashSet ( const HashSet< Key > & hash_set )

Copy Constructor.

Definition at line 612 of file hashSet.h.

template<class Key>

virtual BALL::HashSet< Key >::~HashSet ( )

inlinevirtual

Destructor.

Definition at line 322 of file hashSet.h.

Member Function Documentation

template<class Key >

bool BALL::HashSet< Key >::apply ( UnaryProcessor< ValueType > & processor )

Apply a processor to all keys in this instance.

Returns: true if the processor could be applied.

Definition at line 1217 of file hashSet.h.

template<class Key>

Iterator BALL::HashSet< Key >::begin ( )

inline

Definition at line 536 of file hashSet.h.

template<class Key>

ConstIterator BALL::HashSet< Key >::begin ( ) const

inline

Definition at line 550 of file hashSet.h.

template<class Key >

void BALL::HashSet< Key >::clear ( )

virtual

Clear the hash set. Remove all nodes from all buckets. The capacity and the number of buckets remain unchanged.

Definition at line 660 of file hashSet.h.

template<class Key >

void BALL::HashSet< Key >::deleteBuckets_ ( )

private

Definition at line 1255 of file hashSet.h.

template<class Key>

BALL_INLINE void BALL::HashSet< Key >::deleteNode_ ( Node * node ) const

protectedvirtual

Definition at line 1283 of file hashSet.h.

template<class Key >

BALL_INLINE void BALL::HashSet< Key >::destroy ( )

Clear the hash set. Remove all nodes from all buckets. The capacity and the number of buckets remain unchanged. Simply calls clear;

Definition at line 681 of file hashSet.h.

template<class Key >

void BALL::HashSet< Key >::dump	(	std::ostream &	s = `std::cout`,
		Size	depth = `0`
	)		const

virtual

Dump the constent of this instance to an ostream.

Definition at line 1184 of file hashSet.h.

template<class Key>

Iterator BALL::HashSet< Key >::end ( )

inline

Definition at line 543 of file hashSet.h.

template<class Key>

ConstIterator BALL::HashSet< Key >::end ( ) const

inline

Definition at line 557 of file hashSet.h.

template<class Key >

Size BALL::HashSet< Key >::erase ( const KeyType & key )

Erase element with key key.

Returns: Size the number of elements erased (0 or 1)

Definition at line 927 of file hashSet.h.

template<class Key >

void BALL::HashSet< Key >::erase ( Iterator pos )

Erase element at a given position.

Parameters

pos	an iterator pointing to the element to delete

Exceptions

Exception::IncompatibleIterators	does not point into this HashSet
Exception::InvalidIterator	if pos is invalid

Definition at line 960 of file hashSet.h.

template<class Key >

void BALL::HashSet< Key >::erase	(	Iterator	f,
		Iterator	l
	)

Erase a range of elements. Erase all elements in the range f - l.

Exceptions

Exception::IncompatibleIterators if one of the arguments does not point into this HashSet

Definition at line 999 of file hashSet.h.

template<class Key>

HashSet< Key >::Iterator BALL::HashSet< Key >::find ( const Key & key )

Find the element whose key is key.

Definition at line 868 of file hashSet.h.

template<class Key>

BALL_INLINE HashSet< Key >::ConstIterator BALL::HashSet< Key >::find ( const Key & key ) const

Find the element whose key is key.

Definition at line 889 of file hashSet.h.

template<class Key >

BALL_INLINE void BALL::HashSet< Key >::get ( HashSet< Key > & hash_set ) const

Assign another HashSet with the contents of this HashSet

Parameters

hash_set the HashSet to assign to

Definition at line 696 of file hashSet.h.

template<class Key >

BALL_INLINE Size BALL::HashSet< Key >::getBucketSize ( ) const

Return the number of buckets.

Definition at line 841 of file hashSet.h.

template<class Key >

BALL_INLINE Size BALL::HashSet< Key >::getCapacity ( ) const

Return the capcacity of the hash set.

Definition at line 848 of file hashSet.h.

template<class Key >

BALL_INLINE Size BALL::HashSet< Key >::getSize ( ) const

Return the number of elements in the hash set.

Definition at line 855 of file hashSet.h.

template<class Key>

BALL_INLINE bool BALL::HashSet< Key >::has ( const Key & key ) const

Test whether the set contains the key key.

Definition at line 1120 of file hashSet.h.

template<class Key>

BALL_INLINE HashIndex BALL::HashSet< Key >::hash ( const Key & key ) const

protectedvirtual

Definition at line 1242 of file hashSet.h.

template<class Key>

BALL_INLINE HashIndex BALL::HashSet< Key >::hashBucket_ ( const Key & key ) const

private

Definition at line 1297 of file hashSet.h.

template<class Key>

BALL_INLINE void BALL::HashSet< Key >::host ( Visitor< HashSet< Key > > & visitor )

virtual

Host a visitor for all set entries.

Definition at line 1113 of file hashSet.h.

template<class Key >

std::pair< typename HashSet< Key >::Iterator, bool > BALL::HashSet< Key >::insert ( const ValueType & item )

Insert a new entry into the hash set.

Definition at line 896 of file hashSet.h.

template<class Key>

Iterator BALL::HashSet< Key >::insert	(	Iterator	pos,
		const ValueType &	item
	)

Insert a new entry into the hash set. For STL compatibility. The value of pos is ignored.

template<class Key >

BALL_INLINE bool BALL::HashSet< Key >::isEmpty ( ) const

Test whether the set is empty.

Definition at line 1127 of file hashSet.h.

template<class Key >

bool BALL::HashSet< Key >::isValid ( ) const

Return true if the hash set is consistent. Condition: the number of entries in all buckets has to be equal the stored number of entries (getSize()).

Definition at line 1162 of file hashSet.h.

template<class Key >

BALL_INLINE bool BALL::HashSet< Key >::needRehashing_ ( ) const

protectedvirtual

Definition at line 1290 of file hashSet.h.

template<class Key>

BALL_INLINE HashSet< Key >::Node * BALL::HashSet< Key >::newNode_	(	const ValueType &	value,
		Node *	next
	)		const

protectedvirtual

Definition at line 1276 of file hashSet.h.

template<class Key >

BALL_INLINE bool BALL::HashSet< Key >::operator!= ( const HashSet< Key > & hash_set ) const

Compare two hash sets.

Definition at line 1156 of file hashSet.h.

template<class Key >

BALL_INLINE HashSet< Key > BALL::HashSet< Key >::operator& ( const HashSet< Key > & rhs ) const

Intersection operator. Compute the intersection of the two hash sets. The left-hand set is not modified.

Definition at line 759 of file hashSet.h.

template<class Key >

BALL_INLINE const HashSet< Key > & BALL::HashSet< Key >::operator&= ( const HashSet< Key > & rhs )

Intersection operator. Replace the contents of the current hash set by its intersection with rhs.

Definition at line 713 of file hashSet.h.

template<class Key >

BALL_INLINE HashSet< Key > BALL::HashSet< Key >::operator+ ( const HashSet< Key > & rhs ) const

Union operator.

See Also: operator|

Definition at line 834 of file hashSet.h.

template<class Key >

BALL_INLINE const HashSet< Key > & BALL::HashSet< Key >::operator+= ( const HashSet< Key > & rhs )

Union operator.

See Also: operator|=

Definition at line 752 of file hashSet.h.

template<class Key >

BALL_INLINE HashSet< Key > BALL::HashSet< Key >::operator- ( const HashSet< Key > & rhs ) const

Difference operator. Computes the difference of the two sets, i.e. constructs a set containing the the elements of this set that are not contained in rhs.

Definition at line 779 of file hashSet.h.

template<class Key >

BALL_INLINE const HashSet< Key > & BALL::HashSet< Key >::operator-= ( const HashSet< Key > & rhs )

Difference operator. Remove all elements contained in rhs from the set.

Definition at line 799 of file hashSet.h.

template<class Key >

BALL_INLINE const HashSet< Key > & BALL::HashSet< Key >::operator= ( const HashSet< Key > & rhs )

Assign this HashSet with the contents of another HashSet

Parameters

rhs	the HashSet to assign from

Definition at line 688 of file hashSet.h.

template<class Key >

bool BALL::HashSet< Key >::operator== ( const HashSet< Key > & hash_set ) const

Compare two hash sets.

Definition at line 1133 of file hashSet.h.

template<class Key >

BALL_INLINE HashSet< Key > BALL::HashSet< Key >::operator| ( const HashSet< Key > & rhs ) const

Union operator. Compute the union of the two hash sets. The left-hand set is not modified.

Definition at line 824 of file hashSet.h.

template<class Key >

BALL_INLINE const HashSet< Key > & BALL::HashSet< Key >::operator|= ( const HashSet< Key > & rhs )

Union operator. Replace the contents of the current hash set by its union with rhs.

Definition at line 738 of file hashSet.h.

template<class Key >

BALL_INLINE void BALL::HashSet< Key >::rehash ( )

protectedvirtual

Definition at line 1249 of file hashSet.h.

template<class Key >

void BALL::HashSet< Key >::rehash_ ( )

private

Definition at line 1303 of file hashSet.h.

template<class Key >

void BALL::HashSet< Key >::set ( const HashSet< Key > & hash_set )

Assign this HashSet with the contents of another HashSet

Parameters

hash_set the HashSet to assign from

Definition at line 631 of file hashSet.h.

template<class Key >

BALL_INLINE Size BALL::HashSet< Key >::size ( ) const

Return the number of elements in the hash set.

Definition at line 862 of file hashSet.h.

template<class Key >

BALL_INLINE void BALL::HashSet< Key >::swap ( HashSet< Key > & hash_set )

Swap the contents of two hash sets.

Definition at line 704 of file hashSet.h.

Friends And Related Function Documentation

template<class Key>

friend class IteratorTraits

friend

Definition at line 239 of file hashSet.h.

Member Data Documentation

template<class Key>

vector<Node*> BALL::HashSet< Key >::bucket_

private

Definition at line 595 of file hashSet.h.

template<class Key>

Size BALL::HashSet< Key >::capacity_

private

Definition at line 591 of file hashSet.h.

template<class Key>

Size BALL::HashSet< Key >::size_

private

Definition at line 587 of file hashSet.h.

Classes

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

template<class Key> class BALL::HashSet< Key >

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class Key>
class BALL::HashSet< Key >