Loading...
Searching...
No Matches
BALL::HashSet< Key > Class Template Reference
Foundation Classes » General datastructures » Generic Hash Associative Containers

`#include <BALL/DATATYPE/hashSet.h>`

## Classes

struct | Node
class | IteratorTraits
class | IllegalKey

## 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

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

## Friends

class | IteratorTraits

## Iteration

bool | apply (UnaryProcessor< ValueType > &processor)
Iterator | begin ()
Iterator | end ()
ConstIterator | begin () const
ConstIterator | end () const
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 ()

## Detailed Description

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

Generic Hash Set Class.

Definition at line 45 of file hashSet.h.

## Member Typedef Documentation

## const_iterator

template<class Key>

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

Definition at line 289 of file hashSet.h.

## const_pointer

template<class Key>

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

Definition at line 297 of file hashSet.h.

## const_reference

template<class Key>

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

Definition at line 301 of file hashSet.h.

## ConstIterator

template<class Key>

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

Definition at line 283 of file hashSet.h.

## difference_type

template<class Key>

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

Definition at line 305 of file hashSet.h.

## Iterator

template<class Key>

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

Definition at line 280 of file hashSet.h.

## iterator

template<class Key>

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

Definition at line 287 of file hashSet.h.

## IteratorPosition

template<class Key>

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

Definition at line 74 of file hashSet.h.

## key_type

template<class Key>

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

Definition at line 293 of file hashSet.h.

## KeyType

template<class Key>

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

Definition at line 55 of file hashSet.h.

## pointer

template<class Key>

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

Definition at line 295 of file hashSet.h.

## PointerType

template<class Key>

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

Definition at line 59 of file hashSet.h.

## reference

template<class Key>

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

Definition at line 299 of file hashSet.h.

## size_type

template<class Key>

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

Definition at line 303 of file hashSet.h.

## value_type

template<class Key>

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

Definition at line 291 of file hashSet.h.

## ValueType

template<class Key>

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

Definition at line 51 of file hashSet.h.

## Member Enumeration Documentation

## anonymous enum

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

## HashSet() [1/2]

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.

## HashSet() [2/2]

template<class Key>

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

Copy Constructor.

Definition at line 612 of file hashSet.h.

## ~HashSet()

template<class Key>

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

inline virtual

Destructor.

Definition at line 322 of file hashSet.h.

## Member Function Documentation

## apply()

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.

## begin() [1/2]

template<class Key>

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

inline

Definition at line 536 of file hashSet.h.

## begin() [2/2]

template<class Key>

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

inline

Definition at line 550 of file hashSet.h.

## clear()

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.

## deleteNode_()

template<class Key>

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

protected virtual

Definition at line 1283 of file hashSet.h.

## destroy()

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.

## dump()

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.

## end() [1/2]

template<class Key>

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

inline

Definition at line 543 of file hashSet.h.

## end() [2/2]

template<class Key>

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

inline

Definition at line 557 of file hashSet.h.

## erase() [1/3]

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.

## erase() [2/3]

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.

## erase() [3/3]

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.

## find() [1/2]

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.

## find() [2/2]

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.

## get()

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.

## getBucketSize()

template<class Key>

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

Return the number of buckets.

Definition at line 841 of file hashSet.h.

## getCapacity()

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.

## getSize()

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.

## has()

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.

## hash()

template<class Key>

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

protected virtual

Definition at line 1242 of file hashSet.h.

## host()

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.

## insert() [1/2]

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 895 of file hashSet.h.

## insert() [2/2]

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.

## isEmpty()

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.

## isValid()

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.

## needRehashing_()

template<class Key>

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

protected virtual

Definition at line 1290 of file hashSet.h.

## newNode_()

template<class Key>

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

protected virtual

Definition at line 1275 of file hashSet.h.

## operator!=()

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.

## operator&()

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.

## operator&=()

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.

## operator+()

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.

## operator+=()

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.

## 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.

Definition at line 779 of file hashSet.h.

## operator-=()

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.

## operator=()

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.

## operator==()

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.

## operator|()

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.

## operator|=()

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.

## rehash()

template<class Key>

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

protected virtual

Definition at line 1249 of file hashSet.h.

## set()

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.

## size()

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.

## swap()

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 Symbol Documentation

## IteratorTraits

template<class Key>

friend class IteratorTraits

friend

Definition at line 239 of file hashSet.h.