BALL::HashSet< Key > Class Template Reference
[Generic Hash Associative Containers]

#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 Iterator BALL::HashSet< Key >::iterator

Definition at line 287 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 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`
	)			`[inline]`

Default Constructor.

Definition at line 600 of file hashSet.h.

template<class Key >

BALL::HashSet< Key >::HashSet ( const HashSet< Key > & hash_set ) [inline]

Copy Constructor.

Definition at line 612 of file hashSet.h.

template<class Key>

virtual BALL::HashSet< Key >::~HashSet ( ) [inline, virtual]

Destructor.

Definition at line 322 of file hashSet.h.

Member Function Documentation

template<class Key >

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

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>

ConstIterator BALL::HashSet< Key >::begin ( ) const [inline]

Definition at line 550 of file hashSet.h.

template<class Key>

Iterator BALL::HashSet< Key >::begin ( ) [inline]

Definition at line 536 of file hashSet.h.

template<class Key >

void BALL::HashSet< Key >::clear ( ) [inline, 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_ ( ) [inline, private]

Definition at line 1255 of file hashSet.h.

template<class Key>

virtual void BALL::HashSet< Key >::deleteNode_ ( Node * node ) const [protected, virtual]

template<class Key >

BALL_INLINE void BALL::HashSet< Key >::destroy ( ) [inline]

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 `[inline, virtual]`

Dump the constent of this instance to an ostream.

Definition at line 1184 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>

Iterator BALL::HashSet< Key >::end ( ) [inline]

Definition at line 543 of file hashSet.h.

template<class Key >

void BALL::HashSet< Key >::erase	(	Iterator	f,
		Iterator	l
	)			`[inline]`

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 >

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

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 >

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

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>

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

Find the element whose key is key.

Definition at line 889 of file hashSet.h.

template<class Key>

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

Find the element whose key is key.

Definition at line 868 of file hashSet.h.

template<class Key >

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

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 [inline]

Return the number of buckets.

Definition at line 841 of file hashSet.h.

template<class Key >

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

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 [inline]

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 [inline]

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 [inline, protected, virtual]

Definition at line 1242 of file hashSet.h.

template<class Key>

BALL_INLINE HashIndex BALL::HashSet< Key >::hashBucket_ ( const Key & key ) const [inline, private]

Definition at line 1297 of file hashSet.h.

template<class Key>

BALL_INLINE void BALL::HashSet< Key >::host ( Visitor< HashSet< Key > > & visitor ) [inline, virtual]

Host a visitor for all set entries.

Definition at line 1113 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 >

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

Insert a new entry into the hash set.

Definition at line 896 of file hashSet.h.

template<class Key >

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

Test whether the set is empty.

Definition at line 1127 of file hashSet.h.

template<class Key >

bool BALL::HashSet< Key >::isValid ( ) const [inline]

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 [inline, protected, virtual]

Definition at line 1290 of file hashSet.h.

template<class Key>

virtual Node* BALL::HashSet< Key >::newNode_	(	const ValueType &	value,
		Node *	next
	)			const `[protected, virtual]`

template<class Key >

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

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 [inline]

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 ) [inline]

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 [inline]

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 ) [inline]

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 [inline]

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 ) [inline]

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 ) [inline]

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 [inline]

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 [inline]

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 ) [inline]

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 ( ) [inline, protected, virtual]

Definition at line 1249 of file hashSet.h.

template<class Key >

void BALL::HashSet< Key >::rehash_ ( ) [inline, private]

Definition at line 1303 of file hashSet.h.

template<class Key >

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

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 [inline]

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 ) [inline]

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.

BALL::HashSet< Key > Class Template Reference [Generic Hash Associative Containers]

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

BALL::HashSet< Key > Class Template Reference
[Generic Hash Associative Containers]

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