BALL::HashSet< Key > Class Template Reference

#include <BALL/DATATYPE/hashSet.h>

List of all members.

Classes

class  IllegalKey
class  IteratorTraits
struct  Node

Public Types

typedef Key ValueType
typedef Key KeyType
typedef Key * PointerType
typedef NodeIteratorPosition
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 HashSetoperator= (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, boolinsert (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 HashSetoperator&= (const HashSet &rhs)
const HashSetoperator|= (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 HashSetoperator+= (const HashSet &rhs)
const HashSetoperator-= (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 NodenewNode_ (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 Index BALL::HashSet< Key >::difference_type
template<class Key>
typedef ForwardIterator<HashSet<Key>, ValueType, PointerType, IteratorTraits> BALL::HashSet< Key >::Iterator
template<class Key>
typedef Iterator 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 
)

Default Constructor.

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

template<class Key >
BALL::HashSet< Key >::HashSet ( const HashSet< Key > &  hash_set)
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)

Apply a processor to all keys in this instance.

Returns:
true if the processor could be applied.

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

template<class Key>
ConstIterator BALL::HashSet< Key >::begin ( ) const [inline]
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.

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

template<class Key >
void BALL::HashSet< Key >::deleteBuckets_ ( ) [private]
template<class Key>
virtual void BALL::HashSet< Key >::deleteNode_ ( Node node) const [protected, virtual]
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;

Referenced by BALL::HashSet< Triangle * >::~HashSet().

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.

References BALL_DUMP_DEPTH, BALL_DUMP_STREAM_PREFIX, BALL_DUMP_STREAM_SUFFIX, and BALL::HashSet< Key >::Node::next.

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

Erase element at a given position.

Parameters:
posan iterator pointing to the element to delete

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

template<class Key >
void BALL::HashSet< Key >::erase ( Iterator  f,
Iterator  l 
) throw (Exception::IncompatibleIterators)

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

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

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)

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

Referenced by BALL::GraphVertex< Vertex, Edge, Face >::remove().

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

Find the element whose key is key.

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_setthe HashSet to assign to

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

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

Return the number of buckets.

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

Return the capcacity of the hash set.

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

Return the number of elements in the hash set.

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

Test whether the set contains the key key.

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

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

References BALL::Hash().

template<class Key>
BALL_INLINE HashIndex BALL::HashSet< Key >::hashBucket_ ( const Key &  key) const [private]
template<class Key>
BALL_INLINE void BALL::HashSet< Key >::host ( Visitor< HashSet< Key > > &  visitor) [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 >
BALL_INLINE bool BALL::HashSet< Key >::isEmpty ( ) const
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()).

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

template<class Key >
BALL_INLINE bool BALL::HashSet< Key >::needRehashing_ ( ) const [protected, virtual]
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

Compare two hash sets.

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.

References 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)

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

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

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

Union operator.

See also:
operator|
template<class Key >
BALL_INLINE const HashSet< Key > & BALL::HashSet< Key >::operator+= ( const HashSet< Key > &  rhs)

Union operator.

See also:
operator|=
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.

References 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)

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

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

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:
rhsthe HashSet to assign from
template<class Key >
bool BALL::HashSet< Key >::operator== ( const HashSet< Key > &  hash_set) const

Compare two hash sets.

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

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.

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.

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

template<class Key >
BALL_INLINE void BALL::HashSet< Key >::rehash ( ) [protected, virtual]

References BALL::getNextPrime().

template<class Key >
void BALL::HashSet< Key >::rehash_ ( ) [private]
template<class Key >
void BALL::HashSet< Key >::set ( const HashSet< Key > &  hash_set)
template<class Key >
BALL_INLINE Size BALL::HashSet< Key >::size ( ) const
template<class Key >
BALL_INLINE void BALL::HashSet< Key >::swap ( HashSet< Key > &  hash_set)

Swap the contents of two hash sets.

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


Friends And Related Function Documentation

template<class Key>
friend class IteratorTraits [friend]

Member Data Documentation

template<class Key>
Size BALL::HashSet< Key >::capacity_ [private]