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) throw (Exception::IncompatibleIterators, Exception::InvalidIterator)
void	erase (Iterator f, Iterator l) throw (Exception::IncompatibleIterators)
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.

Member Typedef Documentation

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

template<class Key>

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

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.

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.

References BALL::HashSet< Key >::bucket_.

template<class Key >

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

Copy Constructor.

References BALL::HashSet< Key >::bucket_, BALL::HashSet< Key >::newNode_(), BALL::HashSet< Key >::Node::next, and BALL::HashSet< Key >::Node::value.

template<class Key>

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

Destructor.

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.

References BALL::HashSet< Key >::begin(), BALL::Processor::BREAK, BALL::HashSet< Key >::end(), BALL::UnaryProcessor< T >::finish(), and BALL::UnaryProcessor< T >::start().

template<class Key>

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

template<class Key>

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

Referenced by BALL::HashSet< Key >::apply(), BALL::GraphVertex< Vertex, Edge, Face >::beginEdge(), BALL::GraphVertex< Vertex, Edge, Face >::beginFace(), BALL::GraphVertex< Vertex, Edge, Face >::has(), BALL::HashSet< Key >::operator&(), BALL::HashSet< Key >::operator&=(), BALL::HashSet< Key >::operator-(), BALL::HashSet< Key >::operator-=(), BALL::HashSet< Key >::operator==(), BALL::HashSet< Key >::operator|=(), and BALL::GraphVertex< Vertex, Edge, Face >::substitute().

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.

References BALL::HashSet< Key >::bucket_, BALL::HashSet< Key >::deleteNode_(), BALL::HashSet< Key >::Node::next, and BALL::HashSet< Key >::size_.

Referenced by BALL::HashSet< Key >::destroy(), and BALL::HashSet< Key >::operator-=().

template<class Key >

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

References BALL::HashSet< Key >::bucket_, and BALL::HashSet< Key >::Node::next.

Referenced by BALL::HashSet< Key >::set(), and BALL::HashSet< Triangle * >::~HashSet().

template<class Key>

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

Referenced by BALL::HashSet< Key >::clear(), and BALL::HashSet< Key >::erase().

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;

References BALL::HashSet< Key >::clear().

Referenced by BALL::HashSet< Key >::set(), and BALL::HashSet< Triangle * >::~HashSet().

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.

References BALL_DUMP_DEPTH, BALL_DUMP_STREAM_PREFIX, BALL_DUMP_STREAM_SUFFIX, BALL::HashSet< Key >::bucket_, BALL::HashSet< Key >::getBucketSize(), BALL::HashSet< Key >::getCapacity(), BALL::HashSet< Key >::getSize(), and BALL::HashSet< Key >::size_.

template<class Key>

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

template<class Key>

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

Referenced by BALL::HashSet< Key >::apply(), BALL::GraphVertex< Vertex, Edge, Face >::endEdge(), BALL::GraphVertex< Vertex, Edge, Face >::endFace(), BALL::HashSet< Key >::find(), BALL::HashSet< Key >::has(), BALL::GraphVertex< Vertex, Edge, Face >::has(), BALL::HashSet< Key >::operator&=(), BALL::HashSet< Key >::operator-=(), BALL::HashSet< Key >::operator==(), BALL::HashSet< Key >::operator|=(), and BALL::GraphVertex< Vertex, Edge, Face >::substitute().

template<class Key >

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

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

References BALL::HashSet< Key >::Node::next.

template<class Key >

void BALL::HashSet< Key >::erase ( Iterator pos ) throw (Exception::IncompatibleIterators, Exception::InvalidIterator) [inline]

Erase element at a given position.

Parameters:

pos

an iterator pointing to the element to delete

References BALL::HashSet< Key >::Node::next.

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)

References BALL::HashSet< Key >::bucket_, BALL::HashSet< Key >::deleteNode_(), BALL::HashSet< Key >::hashBucket_(), BALL::HashSet< Key >::Node::next, BALL::HashSet< Key >::size_, and BALL::HashSet< Key >::Node::value.

Referenced by BALL::HashSet< Key >::operator&=(), BALL::HashSet< Key >::operator-=(), and BALL::GraphVertex< Vertex, Edge, Face >::remove().

template<class Key>

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

Find the element whose key is key.

template<class Key>

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

Find the element whose key is key.

References BALL::HashSet< Key >::bucket_, BALL::HashSet< Key >::end(), BALL::BaseIterator< Container, DataType, Position, Traits >::getTraits(), BALL::HashSet< Key >::hashBucket_(), BALL::HashSet< Key >::Node::next, and BALL::HashSet< Key >::Node::value.

Referenced by BALL::HashSet< Key >::has().

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

References BALL::HashSet< Key >::set().

template<class Key >

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

Return the number of buckets.

References BALL::HashSet< Key >::bucket_.

Referenced by BALL::HashSet< Key >::dump().

template<class Key >

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

Return the capcacity of the hash set.

References BALL::HashSet< Key >::capacity_.

Referenced by BALL::HashSet< Key >::dump().

template<class Key >

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

Return the number of elements in the hash set.

References BALL::HashSet< Key >::size_.

Referenced by BALL::HashSet< Key >::dump().

template<class Key>

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

Test whether the set contains the key key.

References BALL::HashSet< Key >::end(), and BALL::HashSet< Key >::find().

Referenced by BALL::HashSet< Key >::operator&(), BALL::HashSet< Key >::operator&=(), BALL::HashSet< Key >::operator-(), BALL::HashSet< Key >::operator-=(), BALL::PersistenceManager::writeObjectPointer(), and BALL::PersistenceManager::writeObjectReference().

template<class Key>

BALL_INLINE HashIndex BALL::HashSet< Key >::hash ( const Key & key ) const [inline, protected, virtual]

References BALL::Hash().

Referenced by BALL::HashSet< Key >::hashBucket_().

template<class Key>

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

References BALL::HashSet< Key >::bucket_, and BALL::HashSet< Key >::hash().

Referenced by BALL::HashSet< Key >::erase(), BALL::HashSet< Key >::find(), and BALL::HashSet< Key >::rehash_().

template<class Key>

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

Host a visitor for all set entries.

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.

References BALL::BaseIterator< Container, DataType, Position, Traits >::getTraits().

Referenced by BALL::GraphVertex< Vertex, Edge, Face >::insert(), BALL::GraphVertex< Vertex, Edge, Face >::join(), BALL::HashSet< Key >::operator&(), BALL::HashSet< Key >::operator-(), BALL::HashSet< Key >::operator|=(), and BALL::PersistenceManager::writeObjectHeader().

template<class Key >

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

Test whether the set is empty.

References BALL::HashSet< Key >::size_.

Referenced by BALL::GraphVertex< Vertex, Edge, Face >::hasEdges(), and BALL::GraphVertex< Vertex, Edge, Face >::hasFaces().

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()).

References BALL::HashSet< Key >::bucket_, BALL::HashSet< Key >::Node::next, BALL::HashSet< Key >::size(), and BALL::HashSet< Key >::size_.

template<class Key >

BALL_INLINE bool BALL::HashSet< Key >::needRehashing_ ( ) const [inline, protected, virtual]

References BALL::HashSet< Key >::capacity_, and BALL::HashSet< Key >::size_.

template<class Key>

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

Referenced by BALL::HashSet< Key >::HashSet(), and BALL::HashSet< Key >::set().

template<class Key >

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

Compare two hash sets.

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.

References BALL::HashSet< Key >::begin(), BALL::HashSet< Key >::has(), and BALL::HashSet< Key >::insert().

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.

References BALL::HashSet< Key >::begin(), BALL::HashSet< Key >::end(), BALL::HashSet< Key >::erase(), and BALL::HashSet< Key >::has().

template<class Key >

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

Union operator.

See also:: operator|

References BALL::HashSet< Key >::operator|().

template<class Key >

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

Union operator.

See also:: operator|=

References BALL::HashSet< Key >::operator|=().

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.

References BALL::HashSet< Key >::begin(), BALL::HashSet< Key >::has(), and BALL::HashSet< Key >::insert().

template<class Key >

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