Loading...
Searching...
No Matches
hashSet.h
Go to the documentation of this file.
// -*- Mode: C++; tab-width: 2; -*-
// vi: set ts=2:
//
#ifndef BALL_DATATYPE_HASHSET_H
#define BALL_DATATYPE_HASHSET_H
#ifndef BALL_COMMON_H
# include <BALL/common.h>
#endif
#ifndef BALL_COMMON_HASH_H
# include <BALL/COMMON/hash.h>
#endif
#ifndef BALL_CONCEPT_FORWARDITERATOR_H
# include <BALL/CONCEPT/forwardIterator.h>
#endif
#ifndef BALL_CONCEPT_VISITOR_H
# include <BALL/CONCEPT/visitor.h>
#endif
#ifndef BALL_DATATYPE_FOREACH_H
# include <BALL/DATATYPE/forEach.h>
#endif
#ifndef BALL_CONCEPT_PREDICATE_H
# include <BALL/CONCEPT/predicate.h>
#endif
#ifndef BALL_CONCEPT_PROCESSOR_H
# include <BALL/CONCEPT/processor.h>
#endif
#include <algorithm>
namespace BALL
{
template <class Key>
class HashSet
{
public:
typedef Key ValueType;
typedef Key KeyType;
typedef Key* PointerType;
// --- EXTERNAL ITERATORS
struct Node
{
Node* next;
ValueType value;
Node(const KeyType& my_key, const Node* my_next)
: next(const_cast<Node*>(my_next)),
value(const_cast<ValueType&>(my_key))
{
}
};
typedef Node* IteratorPosition;
class IteratorTraits
{
friend class HashSet<Key>;
public:
IteratorTraits()
: bound_(0),
position_(0),
bucket_(0)
{
}
IteratorTraits(const HashSet& hash_set)
: bound_(const_cast<HashSet*>(&hash_set)),
position_(0),
bucket_(0)
{
}
IteratorTraits(const IteratorTraits& traits)
: bound_(traits.bound_),
position_(traits.position_),
bucket_(traits.bucket_)
{
}
IteratorTraits& operator = (const IteratorTraits& traits)
{
bound_ = traits.bound_;
position_ = traits.position_;
bucket_ = traits.bucket_;
return *this;
}
HashSet* getContainer()
{
return bound_;
}
const HashSet* getContainer() const
{
return bound_;
}
bool isSingular() const
{
return (bound_ == 0);
}
IteratorPosition& getPosition()
{
return position_;
}
const IteratorPosition& getPosition() const
{
return position_;
}
bool operator == (const IteratorTraits& traits) const
{
return (position_ == traits.position_);
}
bool operator != (const IteratorTraits& traits) const
{
return (position_ != traits.position_);
}
bool isValid() const
{
return ((bound_ != 0) && (position_ != 0)
&& (bucket_ < (Position)bound_->bucket_.size()));
}
void invalidate()
{
bound_ = 0;
position_ = 0;
bucket_ = INVALID_Position;
}
void toBegin()
{
for (bucket_ = 0; bucket_ < (Position)bound_->bucket_.size(); ++bucket_)
{
position_ = bound_->bucket_[bucket_];
if (position_ != 0)
{
return;
}
}
}
bool isBegin() const
{
for (Position bucket = 0; bucket < (Position)bound_->bucket_.size(); ++bucket)
{
if (bound_->bucket_[bucket_] != 0)
{
if (position_ == bound_->bucket_[bucket_])
{
return true;
}
else
{
return false;
}
}
}
return false;
}
void toEnd()
{
position_ = 0;
}
bool isEnd() const
{
return (position_ == 0);
}
ValueType& getData()
{
return position_->value;
}
const ValueType& getData() const
{
return position_->value;
}
void forward()
{
position_ = position_->next;
if (position_ != 0)
{
return;
}
for (++bucket_; bucket_ < (Position)bound_->bucket_.size(); ++bucket_)
{
position_ = bound_->bucket_[bucket_];
if (position_ != 0)
{
return;
}
}
}
protected:
HashSet* bound_;
IteratorPosition position_;
Position bucket_;
};
friend class IteratorTraits;
enum
{
INITIAL_CAPACITY = 4,
INITIAL_NUMBER_OF_BUCKETS = 3
};
class IllegalKey
: public Exception::GeneralException
{
public:
IllegalKey(const char* file, int line)
: Exception::GeneralException(file, line)
{
}
};
typedef ForwardIterator<HashSet<Key>, ValueType, PointerType, IteratorTraits> Iterator;
typedef ConstForwardIterator <HashSet<Key>, ValueType, PointerType, IteratorTraits> ConstIterator;
// STL compatibility stuff
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;
HashSet(Size initial_capacity = INITIAL_CAPACITY, Size number_of_buckets = INITIAL_NUMBER_OF_BUCKETS);
HashSet(const HashSet& hash_set);
virtual ~HashSet()
{
destroy();
deleteBuckets_();
}
virtual void clear();
void destroy();
void set(const HashSet& hash_set);
const HashSet& operator = (const HashSet& rhs);
void get(HashSet& hash_set) const;
void swap(HashSet& hash_set);
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);
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);
virtual void host(Visitor<HashSet<Key> >& visitor);
bool has(const Key& key) const;
bool isEmpty() const;
bool operator == (const HashSet& hash_set) const;
bool operator != (const HashSet& hash_set) const;
bool isValid() const;
virtual void dump(std::ostream& s = std::cout, Size depth = 0) const;
// --- INTERNAL ITERATORS
bool apply(UnaryProcessor<ValueType>& processor);
Iterator begin()
{
return Iterator::begin(*this);
}
Iterator end()
{
return Iterator::end(*this);
}
ConstIterator begin() const
{
return ConstIterator::begin(*this);
}
ConstIterator end() const
{
return ConstIterator::end(*this);
}
protected:
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:
void deleteBuckets_();
Position hashBucket_(const Key& key) const;
void rehash_();
// --- ATTRIBUTES
/*_ The number of elements in the hash set
*/
Size size_;
/*_ The capacity - usually the number of buckets
*/
Size capacity_;
/*_ Buckets are stored as a vector of linked lists of Nodes
*/
vector<Node*> bucket_;
};
template <class Key>
HashSet<Key>::HashSet(Size initial_capacity, Size number_of_buckets)
: size_(0),
capacity_(initial_capacity),
bucket_(number_of_buckets)
{
for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
{
bucket_[bucket] = 0;
}
}
template <class Key>
HashSet<Key>::HashSet(const HashSet& hash_set)
: size_(hash_set.size_),
capacity_(hash_set.capacity_),
bucket_(hash_set.bucket_.size())
{
Node* item = 0;
for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
{
bucket_[bucket] = 0;
for (item = hash_set.bucket_[bucket]; item != 0; item = item->next)
{
bucket_[bucket] = newNode_(item->value, bucket_[bucket]);
}
}
}
template <class Key>
void HashSet<Key>::set(const HashSet& hash_set)
{
if (&hash_set == this)
{
return;
}
destroy();
deleteBuckets_();
size_ = hash_set.size_;
capacity_ = hash_set.capacity_;
bucket_.resize(hash_set.bucket_.size());
Node* item = 0;
for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
{
bucket_[bucket] = 0;
for (item = hash_set.bucket_[bucket]; item != 0; item = item->next)
{
bucket_[bucket] = newNode_(item->value, bucket_[bucket]);
}
}
}
template <class Key>
void HashSet<Key>::clear()
{
Node* node = 0;
Node* next_node = 0;
for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
{
for (node = bucket_[bucket]; node != 0; node = next_node)
{
next_node = node->next;
deleteNode_(node);
}
bucket_[bucket] = 0;
}
size_ = 0;
}
template <class Key>
BALL_INLINE
void HashSet<Key>::destroy()
{
clear();
}
template <class Key>
BALL_INLINE
const HashSet<Key>& HashSet<Key>::operator = (const HashSet& hash_set)
{
set(hash_set);
return *this;
}
template <class Key>
BALL_INLINE
void HashSet<Key>::get(HashSet& hash_set) const
{
hash_set.set(*this);
}
template <class Key>
BALL_INLINE
void HashSet<Key>::swap(HashSet& hash_set)
{
std::swap(size_, hash_set.size_);
std::swap(capacity_, hash_set.capacity_);
std::swap(bucket_, hash_set.bucket_);
}
template <class Key>
BALL_INLINE
const HashSet<Key>& HashSet<Key>::operator &= (const HashSet& rhs)
{
// Store all elements that are not part of the intersection
// in a list for subsequent deletion.
std::list<Key> erase_list;
for (Iterator it = begin(); it != end(); ++it)
{
if (!rhs.has(*it))
{
erase_list.push_back(*it);
}
}
// erase all elements not part of the intersection
typename list<Key>::iterator list_it = erase_list.begin();
for (; list_it != erase_list.end(); ++list_it)
{
erase(*list_it);
}
return *this;
}
template <class Key>
BALL_INLINE
const HashSet<Key>& HashSet<Key>::operator |= (const HashSet<Key>& rhs)
{
// Compute the union of both sets by inserting every element of the
// rhs set.
for (ConstIterator it = rhs.begin(); it != rhs.end(); ++it)
{
insert(*it);
}
return *this;
}
template <class Key>
BALL_INLINE
const HashSet<Key>& HashSet<Key>::operator += (const HashSet<Key>& rhs)
{
return operator |= (rhs);
}
template <class Key>
BALL_INLINE
HashSet<Key> HashSet<Key>::operator & (const HashSet<Key>& rhs) const
{
// Create an empty hash set...
HashSet<Key> tmp;
ConstIterator it = begin();
// ...and copy all the elements contained in the rhs hash set.
for (; +it; ++it)
{
if (rhs.has(*it))
{
tmp.insert(*it);
}
}
return tmp;
}
template <class Key>
BALL_INLINE
HashSet<Key> HashSet<Key>::operator - (const HashSet<Key>& rhs) const
{
// Create an empty hash set...
HashSet<Key> tmp;
ConstIterator it = begin();
// ...and copy all the elements contained in this set and not in the rhs hash set.
for (; +it; ++it)
{
if (!rhs.has(*it))
{
tmp.insert(*it);
}
}
return tmp;
}
template <class Key>
BALL_INLINE
const HashSet<Key>& HashSet<Key>::operator -= (const HashSet<Key>& hash_set)
{
// avoid memory corruption caused by iterating over freed space when
// deleting myself
if (this == &hash_set)
{
clear();
}
else
{
// erase all elements which are contained in this and hash_set
typename HashSet<Key>::ConstIterator it = hash_set.begin();
for (; it != hash_set.end(); ++it)
{
if (has(*it))
{
erase(*it);
}
}
}
return *this;
}
template <class Key>
BALL_INLINE
HashSet<Key> HashSet<Key>::operator | (const HashSet<Key>& rhs) const
{
HashSet<Key> tmp(*this);
tmp |= rhs;
return tmp;
}
template <class Key>
BALL_INLINE
HashSet<Key> HashSet<Key>::operator + (const HashSet<Key>& rhs) const
{
return operator | (rhs);
}
template <class Key>
BALL_INLINE
Size HashSet<Key>::getBucketSize() const
{
return (Size)bucket_.size();
}
template <class Key>
BALL_INLINE
Size HashSet<Key>::getCapacity() const
{
return capacity_;
}
template <class Key>
BALL_INLINE
Size HashSet<Key>::getSize() const
{
return size_;
}
template <class Key>
BALL_INLINE
Size HashSet<Key>::size() const
{
return size_;
}
template <class Key>
typename HashSet<Key>::Iterator HashSet<Key>::find(const Key& key)
{
Iterator it = end();
Position bucket = hashBucket_(key);
Node* node_ptr = bucket_[bucket];
while (node_ptr != 0)
{
if (node_ptr->value == key)
{
it.getTraits().position_ = node_ptr;
it.getTraits().bucket_ = bucket;
break;
}
node_ptr = node_ptr->next;
}
return it;
}
template <class Key>
BALL_INLINE
typename HashSet<Key>::ConstIterator HashSet<Key>::find(const Key& key) const
{
return (const_cast<HashSet*>(this))->find(key);
}
template <class Key>
std::pair<typename HashSet<Key>::Iterator, bool> HashSet<Key>::insert
(const ValueType& item)
{
Iterator it = find(item);
if (it == end())
{
if (needRehashing_() == true)
{
rehash_();
}
Position bucket = hashBucket_(item);
Node* next = bucket_[bucket];
bucket_[bucket] = newNode_(item, next);
++size_;
it.getTraits().position_ = bucket_[bucket];
it.getTraits().bucket_ = bucket;
}
return std::pair<Iterator, bool>(it, true);
}
template <class Key>
typename HashSet<Key>::Iterator HashSet<Key>::insert
(typename HashSet<Key>::Iterator /* pos */, const ValueType& item)
{
return insert(item).first;
}
template <class Key>
Size HashSet<Key>::erase(const KeyType& key)
{
Position bucket = hashBucket_(key);
Node* previous = 0;
Node* node_ptr = bucket_[bucket];
while (node_ptr != 0 && node_ptr->value != key)
{
previous = node_ptr;
node_ptr = node_ptr->next;
}
if (node_ptr == 0)
{
return false;
}
if (node_ptr == bucket_[bucket])
{
bucket_[bucket] = node_ptr->next;
}
else
{
previous->next = node_ptr->next;
}
deleteNode_(node_ptr);
--size_;
return 1;
}
template <class Key>
void HashSet<Key>::erase(Iterator pos)
{
if (pos.getTraits().bound_ != this)
{
throw Exception::IncompatibleIterators(__FILE__, __LINE__);
}
if ((pos == end()) || (size_ == 0))
{
return;
}
if (pos.getTraits().position_ == bucket_[pos.getTraits().bucket_])
{
bucket_[pos.getTraits().bucket_] = pos.getTraits().position_->next;
}
else
{
// walk over all nodes in this bucket and identify the predecessor
// of the node refered to by the iterator pos
Node* prev = bucket_[pos.getTraits().bucket_];
for (; (prev != 0) && (prev->next != pos.getTraits().position_); prev = prev->next) {};
if (prev != 0)
{
// remove the node and reconnect the list
prev->next = pos.getTraits().position_->next;
}
else
{
throw Exception::InvalidIterator(__FILE__, __LINE__);
}
}
// delete the node and decrement the set size
deleteNode_(pos.getTraits().position_);
--size_;
}
template <class Key>
void HashSet<Key>::erase(Iterator f, Iterator l)
{
if (f.getTraits().bound_ != this || l.getTraits().bound_ != this)
{
throw Exception::IncompatibleIterators(__FILE__, __LINE__);
}
if (f == end())
{
return;
}
Position last_bucket = l.getTraits().bucket_;
if (l == end())
{
last_bucket = (Position)(bucket_.size() - 1);
}
if (f.getTraits().bucket_ > last_bucket)
{
// empty range - l < f
return;
}
// count the deleted entries to correct the set size
Size no_deletions = 0;
Position bucket = f.getTraits().bucket_;
for (; bucket <= last_bucket; bucket++)
{
if (bucket_[bucket] == 0)
{
// skip all empty buckets
continue;
}
if ((bucket == f.getTraits().bucket_) && (bucket_[bucket] != f.getTraits().position_))
{
// find the predecessor of f
Node* n = bucket_[bucket];
Node* next;
for (; (n->next != f.getTraits().position_) && (n->next != 0); n = n->next) {};
if (bucket == last_bucket)
{
// delete everything from f to l in this bucket
next = n->next;
n->next = l.getTraits().position_;
for (n = next; (n != 0) && (n != l.getTraits().position_); n = next)
{
next = n->next;
deleteNode_(n);
no_deletions++;
}
}
else
{
// delete everything from f to the end in this bucket
if (n != 0)
{
// mark the end of the list
next = n->next;
n->next = 0;
// delete all remaining nodes
for (n = next; n != 0; n = next)
{
next = n->next;
deleteNode_(n);
no_deletions++;
}
}
}
}
// if the current bucket lies between the first and the last bucket...
else if (bucket < last_bucket)
{
// ...delete the whole bucket
Node* next;
for (Node* n = bucket_[bucket]; n != 0; n = next)
{
next = n->next;
deleteNode_(n);
no_deletions++;
}
bucket_[bucket] = 0;
}
else if (bucket == last_bucket)
{
// we delete everything in this bucket up to the iterator l
// find the predecessor of l
Node* n = bucket_[bucket];
Node* next;
for (; (n != 0) && (n != l.getTraits().position_); n = next)
{
next = n->next;
deleteNode_(n);
no_deletions++;
}
bucket_[bucket] = l.getTraits().position_;
}
}
// correct the set size
size_ -= no_deletions;
}
template <class Key>
BALL_INLINE
void HashSet<Key>::host(Visitor<HashSet<Key> >& visitor)
{
visitor.visit(*this);
}
template <class Key>
BALL_INLINE
bool HashSet<Key>::has(const Key& key) const
{
return (find(key) != end());
}
template <class Key>
BALL_INLINE
bool HashSet<Key>::isEmpty() const
{
return (size_ == 0);
}
template <class Key>
bool HashSet<Key>::operator == (const HashSet& hash_set) const
{
if (size_ != hash_set.size_)
{
return false;
}
ConstIterator it1 = begin();
ConstIterator it2 = hash_set.begin();
while (it1 != end())
{
if (*it1 != *it2)
{
return false;
}
it1++;
it2++;
}
return true;
}
template <class Key>
BALL_INLINE
bool HashSet<Key>::operator != (const HashSet& hash_set) const
{
return !(*this == hash_set);
}
template <class Key>
bool HashSet<Key>::isValid() const
{
Size size = 0;
Node* node = 0;
for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
{
for (node = bucket_[bucket]; node != 0; node = node->next)
{
++size;
if (node->next == 0)
{
break;
}
}
}
return (size_ == size);
}
template <class Key>
void HashSet<Key>::dump(std::ostream& s, Size depth) const
{
BALL_DUMP_STREAM_PREFIX(s);
BALL_DUMP_DEPTH(s, depth);
BALL_DUMP_DEPTH(s, depth);
s << " size: " << getSize() << std::endl;
BALL_DUMP_DEPTH(s, depth);
s << " # buckets: " << getBucketSize() << std::endl;
BALL_DUMP_DEPTH(s, depth);
s << " capacity: " << getCapacity() << std::endl;
BALL_DUMP_DEPTH(s, depth);
s << " load factor: " << (float)size_ / (float)bucket_.size() << std::endl;
for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
{
BALL_DUMP_DEPTH(s, depth);
s << " bucket " << bucket << ": ";
for (Node* ptr = bucket_[bucket]; ptr != 0; ptr = ptr->next)
{
s << "(" << (void*)ptr << ") ";
}
s << "(0)" << std::endl;
}
BALL_DUMP_STREAM_SUFFIX(s);
}
template <class Key>
bool HashSet<Key>::apply(UnaryProcessor<ValueType>& processor)
{
if (processor.start() == false)
{
return false;
}
Processor::Result result;
Iterator it = begin();
while (it != end())
{
result = processor(*it);
if (result <= Processor::BREAK)
{
return (result == Processor::BREAK);
}
it++;
}
return processor.finish();
}
template <class Key>
BALL_INLINE
HashIndex HashSet<Key>::hash(const Key& key) const
{
return (HashIndex)Hash(key);
}
template <class Key>
BALL_INLINE
void HashSet<Key>::rehash()
{
capacity_ = (Size)getNextPrime((Size)bucket_.size() << 1);
}
template <class Key>
void HashSet<Key>::deleteBuckets_()
{
Size i = 0;
Node* node = 0;
Node* next_node = 0;
for (i = 0; i < bucket_.size(); i++)
{
node = bucket_[i];
while (node != 0)
{
next_node = node->next;
delete node;
node = next_node;
}
bucket_[i] = 0;
}
}
template <class Key>
BALL_INLINE
typename HashSet<Key>::Node* HashSet<Key>::newNode_
(const ValueType& value, typename HashSet<Key>::Node* next) const
{
return new Node(value, next);
}
template <class Key>
BALL_INLINE
void HashSet<Key>::deleteNode_(typename HashSet<Key>::Node* node) const
{
delete node;
}
template <class Key>
BALL_INLINE
bool HashSet<Key>::needRehashing_() const
{
return (size_ >= capacity_);
}
template <class Key>
BALL_INLINE
HashIndex HashSet<Key>::hashBucket_(const Key& key) const
{
return (Position)((HashIndex)hash(key) % (HashIndex)bucket_.size());
}
template <class Key>
void HashSet<Key>::rehash_()
{
// calculate the new number of buckets (in capacity_)
rehash();
// save the old contents
vector<Node*> old_buckets(bucket_);
// resize the bucket vector and initialize it with zero
bucket_.clear();
bucket_.resize(capacity_);
Position i;
for (i = 0; i < capacity_; i++)
{
bucket_[i] = 0;
}
// rehash the old contents into the new buckets
Node* node;
Node* next_node;
for (Position i = 0; i < (Position)old_buckets.size(); ++i)
{
for (node = old_buckets[i]; node != 0; node = next_node)
{
next_node = node->next;
Position new_bucket = hashBucket_(node->value);
node->next = bucket_[new_bucket];
bucket_[new_bucket] = node;
}
}
}
} // namespace BALL
#endif // BALL_DATATYPE_HASHSET_H
predicate.h
forEach.h
BALL::BaseIterator::getTraits
BALL_INLINE const Traits & getTraits() const
Get a constant reference to the traits of this iterator.
Definition baseIterator.h:130
BALL::ConstForwardIterator< HashSet< Key >, ValueType, PointerType, IteratorTraits >::begin
static ConstForwardIterator begin(const HashSet< Key > &container)
BALL::ConstForwardIterator< HashSet< Key >, ValueType, PointerType, IteratorTraits >::end
static ConstForwardIterator end(const HashSet< Key > &container)
BALL::Exception::GeneralException
Definition COMMON/exception.h:61
BALL::Exception::GeneralException::GeneralException
GeneralException()
Default constructor.
BALL::Exception::IncompatibleIterators
Definition COMMON/exception.h:281
BALL::Exception::InvalidIterator
Definition COMMON/exception.h:270
BALL::ForwardIterator
Definition forwardIterator.h:199
BALL::ForwardIterator< HashSet< Key >, ValueType, PointerType, IteratorTraits >::begin
static ForwardIterator begin(const HashSet< Key > &container)
BALL::ForwardIterator< HashSet< Key >, ValueType, PointerType, IteratorTraits >::end
static ForwardIterator end(const HashSet< Key > &container)
BALL::ValueType
BALL::HashSet::IllegalKey::IllegalKey
IllegalKey(const char *file, int line)
Definition hashSet.h:267
BALL::HashSet::IteratorTraits::getContainer
const HashSet * getContainer() const
Definition hashSet.h:117
BALL::HashSet::IteratorTraits::getData
const ValueType & getData() const
Definition hashSet.h:208
BALL::HashSet::IteratorTraits::isValid
bool isValid() const
Definition hashSet.h:147
BALL::HashSet::IteratorTraits::operator=
IteratorTraits & operator=(const IteratorTraits &traits)
Definition hashSet.h:103
BALL::HashSet::IteratorTraits::position_
IteratorPosition position_
Definition hashSet.h:236
BALL::HashSet::IteratorTraits::bound_
HashSet * bound_
Definition hashSet.h:235
BALL::HashSet::IteratorTraits::IteratorTraits
IteratorTraits(const IteratorTraits &traits)
Definition hashSet.h:96
BALL::HashSet::IteratorTraits::toBegin
void toBegin()
Definition hashSet.h:160
BALL::HashSet::IteratorTraits::invalidate
void invalidate()
Definition hashSet.h:153
BALL::HashSet::IteratorTraits::operator==
bool operator==(const IteratorTraits &traits) const
Definition hashSet.h:137
BALL::HashSet::IteratorTraits::getData
ValueType & getData()
Definition hashSet.h:203
BALL::HashSet::IteratorTraits::isBegin
bool isBegin() const
Definition hashSet.h:173
BALL::HashSet::IteratorTraits::getPosition
IteratorPosition & getPosition()
Definition hashSet.h:127
BALL::HashSet::IteratorTraits::IteratorTraits
IteratorTraits()
Definition hashSet.h:82
BALL::HashSet::IteratorTraits::operator!=
bool operator!=(const IteratorTraits &traits) const
Definition hashSet.h:142
BALL::HashSet::IteratorTraits::IteratorTraits
IteratorTraits(const HashSet &hash_set)
Definition hashSet.h:89
BALL::HashSet::IteratorTraits::bucket_
Position bucket_
Definition hashSet.h:237
BALL::HashSet::IteratorTraits::getPosition
const IteratorPosition & getPosition() const
Definition hashSet.h:132
BALL::HashSet::IteratorTraits::getContainer
HashSet * getContainer()
Definition hashSet.h:112
BALL::HashSet::IteratorTraits::forward
void forward()
Definition hashSet.h:213
BALL::HashSet::IteratorTraits::toEnd
void toEnd()
Definition hashSet.h:193
BALL::HashSet::IteratorTraits::isSingular
bool isSingular() const
Definition hashSet.h:122
BALL::HashSet::IteratorTraits::isEnd
bool isEnd() const
Definition hashSet.h:198
BALL::HashSet< const PersistentObject * >::Iterator
ForwardIterator< HashSet< const PersistentObject * >, ValueType, PointerType, IteratorTraits > Iterator
Definition hashSet.h:280
BALL::HashSet::hash
virtual HashIndex hash(const Key &key) const
Definition hashSet.h:1242
BALL::HashSet::size
Size size() const
Definition hashSet.h:862
BALL::HashSet::erase
void erase(Iterator f, Iterator l)
Definition hashSet.h:999
BALL::HashSet< const PersistentObject * >::pointer
const PersistentObject ** pointer
Definition hashSet.h:295
BALL::HashSet< const PersistentObject * >::const_reference
const const PersistentObject *& const_reference
Definition hashSet.h:301
BALL::HashSet< const PersistentObject * >::size_type
Size size_type
Definition hashSet.h:303
BALL::HashSet::set
void set(const HashSet &hash_set)
Definition hashSet.h:631
BALL::HashSet::find
ConstIterator find(const Key &key) const
Definition hashSet.h:889
BALL::HashSet::isValid
bool isValid() const
Definition hashSet.h:1162
BALL::HashSet::isEmpty
bool isEmpty() const
Definition hashSet.h:1127
BALL::HashSet::operator&=
const HashSet & operator&=(const HashSet &rhs)
Definition hashSet.h:713
BALL::HashSet::operator!=
bool operator!=(const HashSet &hash_set) const
Definition hashSet.h:1156
BALL::HashSet::get
void get(HashSet &hash_set) const
Definition hashSet.h:696
BALL::HashSet::newNode_
virtual Node * newNode_(const ValueType &value, Node *next) const
Definition hashSet.h:1276
BALL::HashSet< const PersistentObject * >::const_iterator
ConstIterator const_iterator
Definition hashSet.h:289
BALL::HashSet::operator-
HashSet operator-(const HashSet &rhs) const
Definition hashSet.h:779
BALL::HashSet::HashSet
HashSet(const HashSet &hash_set)
Definition hashSet.h:612
BALL::HashSet::end
ConstIterator end() const
Definition hashSet.h:557
BALL::HashSet::begin
Iterator begin()
Definition hashSet.h:536
BALL::HashSet::insert
std::pair< Iterator, bool > insert(const ValueType &item)
Definition hashSet.h:896
BALL::HashSet::operator+
HashSet operator+(const HashSet &rhs) const
Definition hashSet.h:834
BALL::HashSet::begin
ConstIterator begin() const
Definition hashSet.h:550
BALL::HashSet::HashSet
HashSet(Size initial_capacity=INITIAL_CAPACITY, Size number_of_buckets=INITIAL_NUMBER_OF_BUCKETS)
Definition hashSet.h:600
BALL::HashSet::operator+=
const HashSet & operator+=(const HashSet &rhs)
Definition hashSet.h:752
BALL::HashSet::has
bool has(const Key &key) const
Definition hashSet.h:1120
BALL::HashSet::insert
Iterator insert(Iterator pos, const ValueType &item)
BALL::HashSet< const PersistentObject * >::reference
const PersistentObject *& reference
Definition hashSet.h:299
BALL::HashSet::deleteNode_
virtual void deleteNode_(Node *node) const
Definition hashSet.h:1283
BALL::HashSet::dump
virtual void dump(std::ostream &s=std::cout, Size depth=0) const
Definition hashSet.h:1184
BALL::HashSet< const PersistentObject * >::IteratorPosition
Node * IteratorPosition
Definition hashSet.h:74
BALL::HashSet::rehash
virtual void rehash()
Definition hashSet.h:1249
BALL::HashSet::operator=
const HashSet & operator=(const HashSet &rhs)
Definition hashSet.h:688
BALL::HashSet::getSize
Size getSize() const
Definition hashSet.h:855
BALL::HashSet< const PersistentObject * >::value_type
const PersistentObject * value_type
Definition hashSet.h:291
BALL::HashSet< const PersistentObject * >::ValueType
const PersistentObject * ValueType
Definition hashSet.h:51
BALL::HashSet::~HashSet
virtual ~HashSet()
Definition hashSet.h:322
BALL::HashSet::operator|
HashSet operator|(const HashSet &rhs) const
Definition hashSet.h:824
BALL::HashSet::end
Iterator end()
Definition hashSet.h:543
BALL::HashSet::operator|=
const HashSet & operator|=(const HashSet &rhs)
Definition hashSet.h:738
BALL::HashSet::operator-=
const HashSet & operator-=(const HashSet &rhs)
Definition hashSet.h:799
BALL::HashSet::operator&
HashSet operator&(const HashSet &rhs) const
Definition hashSet.h:759
BALL::HashSet::destroy
void destroy()
Definition hashSet.h:681
BALL::HashSet::operator==
bool operator==(const HashSet &hash_set) const
Definition hashSet.h:1133
BALL::HashSet< const PersistentObject * >::INITIAL_NUMBER_OF_BUCKETS
@ INITIAL_NUMBER_OF_BUCKETS
Definition hashSet.h:250
BALL::HashSet< const PersistentObject * >::INITIAL_CAPACITY
@ INITIAL_CAPACITY
Definition hashSet.h:248
BALL::HashSet::getBucketSize
Size getBucketSize() const
Definition hashSet.h:841
BALL::HashSet::host
virtual void host(Visitor< HashSet< Key > > &visitor)
Definition hashSet.h:1113
BALL::HashSet< const PersistentObject * >::difference_type
Index difference_type
Definition hashSet.h:305
BALL::HashSet< const PersistentObject * >::key_type
const PersistentObject * key_type
Definition hashSet.h:293
BALL::HashSet::apply
bool apply(UnaryProcessor< ValueType > &processor)
Definition hashSet.h:1217
BALL::HashSet< const PersistentObject * >::iterator
Iterator iterator
Definition hashSet.h:287
BALL::HashSet::clear
virtual void clear()
Definition hashSet.h:660
BALL::HashSet< const PersistentObject * >::KeyType
const PersistentObject * KeyType
Definition hashSet.h:55
BALL::HashSet< const PersistentObject * >::ConstIterator
ConstForwardIterator< HashSet< const PersistentObject * >, ValueType, PointerType, IteratorTraits > ConstIterator
Definition hashSet.h:283
BALL::HashSet::erase
Size erase(const KeyType &key)
Definition hashSet.h:927
BALL::HashSet::swap
void swap(HashSet &hash_set)
Definition hashSet.h:704
BALL::HashSet::erase
void erase(Iterator pos)
Definition hashSet.h:960
BALL::HashSet< const PersistentObject * >::PointerType
const PersistentObject ** PointerType
Definition hashSet.h:59
BALL::HashSet::getCapacity
Size getCapacity() const
Definition hashSet.h:848
BALL::HashSet< const PersistentObject * >::const_pointer
const const PersistentObject ** const_pointer
Definition hashSet.h:297
BALL::HashSet::needRehashing_
virtual bool needRehashing_() const
Definition hashSet.h:1290
BALL::HashSet::find
Iterator find(const Key &key)
Definition hashSet.h:868
BALL::Processor::BREAK
@ BREAK
Definition processor.h:47
BALL::Processor::Result
int Result
Definition processor.h:36
BALL::UnaryProcessor
Definition processor.h:60
BALL::UnaryProcessor::start
virtual bool start()
Definition processor.h:92
BALL::UnaryProcessor::finish
virtual bool finish()
Definition processor.h:99
BALL::Visitor
Definition visitor.h:23
common.h
BALL_INLINE
#define BALL_INLINE
Definition debug.h:15
forwardIterator.h
hash.h
BALL_DUMP_STREAM_PREFIX
#define BALL_DUMP_STREAM_PREFIX(os)
Definition macros.h:391
BALL_DUMP_STREAM_SUFFIX
#define BALL_DUMP_STREAM_SUFFIX(os)
Definition macros.h:395
BALL_DUMP_DEPTH
#define BALL_DUMP_DEPTH(os, depth)
Definition macros.h:390
BALL::Exception
Definition COMMON/exception.h:33
BALL
Definition constants.h:13
BALL::HashIndex
BALL_SIZE_TYPE HashIndex
Definition COMMON/global.h:131
BALL::INVALID_Position
static const Position INVALID_Position
Definition COMMON/global.h:243
BALL::Size
BALL_SIZE_TYPE Size
Definition COMMON/global.h:114
BALL::Hash
HashIndex Hash(const T &key)
Definition hash.h:47
BALL::Position
BALL_SIZE_TYPE Position
Definition COMMON/global.h:140
BALL::getNextPrime
BALL_EXPORT HashIndex getNextPrime(HashIndex l)
BALL::Index
BALL_INDEX_TYPE Index
Definition COMMON/global.h:105
processor.h
BALL::HashSet::Node
Definition hashSet.h:63
BALL::HashSet::Node::next
Node * next
Definition hashSet.h:64
BALL::HashSet::Node::value
ValueType value
Definition hashSet.h:65
BALL::HashSet::Node::Node
Node(const KeyType &my_key, const Node *my_next)
Definition hashSet.h:67
visitor.h