5 #ifndef BALL_DATATYPE_HASHSET_H 6 #define BALL_DATATYPE_HASHSET_H 12 #ifndef BALL_COMMON_HASH_H 16 #ifndef BALL_CONCEPT_FORWARDITERATOR_H 20 #ifndef BALL_CONCEPT_VISITOR_H 24 #ifndef BALL_DATATYPE_FOREACH_H 28 #ifndef BALL_CONCEPT_PREDICATE_H 32 #ifndef BALL_CONCEPT_PROCESSOR_H 67 Node(
const KeyType& my_key,
const Node* my_next)
68 : next(const_cast<
Node*>(my_next)),
69 value(const_cast<ValueType&>(my_key))
90 : bound_(const_cast<
HashSet*>(&hash_set)),
97 : bound_(traits.bound_),
98 position_(traits.position_),
99 bucket_(traits.bucket_)
124 return (bound_ == 0);
149 return ((bound_ != 0) && (position_ != 0)
150 && (bucket_ < (
Position)bound_->bucket_.size()));
162 for (bucket_ = 0; bucket_ < (
Position)bound_->bucket_.size(); ++bucket_)
164 position_ = bound_->bucket_[bucket_];
175 for (
Position bucket = 0; bucket < (
Position)bound_->bucket_.size(); ++bucket)
177 if (bound_->bucket_[bucket_] != 0)
179 if (position_ == bound_->bucket_[bucket_])
200 return (position_ == 0);
205 return position_->value;
210 return position_->value;
215 position_ = position_->next;
222 for (++bucket_; bucket_ < (
Position)bound_->bucket_.size(); ++bucket_)
224 position_ = bound_->bucket_[bucket_];
268 : Exception::GeneralException(file, line)
332 virtual void clear();
350 void set(
const HashSet& hash_set);
360 void get(
HashSet& hash_set)
const;
390 Iterator
find(
const Key& key);
394 ConstIterator
find(
const Key& key)
const;
398 std::pair<Iterator, bool>
insert(
const ValueType& item);
403 Iterator
insert(Iterator pos,
const ValueType& item);
415 void erase(Iterator pos);
421 void erase(Iterator f, Iterator l);
490 bool has(
const Key& key)
const;
517 virtual void dump(std::ostream& s = std::cout,
Size depth = 0)
const;
577 void deleteBuckets_();
579 Position hashBucket_(
const Key& key)
const;
595 vector<Node*> bucket_;
602 capacity_(initial_capacity),
603 bucket_(number_of_buckets)
613 : size_(hash_set.size_),
614 capacity_(hash_set.capacity_),
615 bucket_(hash_set.bucket_.size())
623 for (item = hash_set.bucket_[bucket]; item != 0; item = item->next)
625 bucket_[bucket] = newNode_(item->value, bucket_[bucket]);
633 if (&hash_set ==
this)
642 size_ = hash_set.size_;
643 capacity_ = hash_set.capacity_;
644 bucket_.resize(hash_set.bucket_.size());
652 for (item = hash_set.bucket_[bucket]; item != 0; item = item->next)
654 bucket_[bucket] = newNode_(item->value, bucket_[bucket]);
667 for (node = bucket_[bucket]; node != 0; node = next_node)
669 next_node = node->next;
706 std::swap(size_, hash_set.size_);
707 std::swap(capacity_, hash_set.capacity_);
708 std::swap(bucket_, hash_set.bucket_);
717 std::list<Key> erase_list;
718 for (
Iterator it = begin(); it != end(); ++it)
722 erase_list.push_back(*it);
727 typename list<Key>::iterator list_it = erase_list.begin();
728 for (; list_it != erase_list.end(); ++list_it)
754 return operator |= (rhs);
803 if (
this == &hash_set)
811 for (; it != hash_set.
end(); ++it)
836 return operator | (rhs);
872 Node* node_ptr = bucket_[bucket];
873 while (node_ptr != 0)
875 if (node_ptr->value == key)
881 node_ptr = node_ptr->next;
891 return (const_cast<HashSet*>(
this))->
find(key);
901 if (needRehashing_() ==
true)
906 Position bucket = hashBucket_(item);
908 Node* next = bucket_[bucket];
909 bucket_[bucket] = newNode_(item, next);
912 it.
getTraits().position_ = bucket_[bucket];
916 return std::pair<Iterator, bool>(it,
true);
923 return insert(item).first;
931 Node* node_ptr = bucket_[bucket];
933 while (node_ptr != 0 && node_ptr->value != key)
936 node_ptr = node_ptr->next;
944 if (node_ptr == bucket_[bucket])
946 bucket_[bucket] = node_ptr->next;
950 previous->next = node_ptr->next;
953 deleteNode_(node_ptr);
967 if ((pos == end()) || (size_ == 0))
980 Node* prev = bucket_[pos.
getTraits().bucket_];
981 for (; (prev != 0) && (prev->next != pos.
getTraits().position_); prev = prev->next) {};
985 prev->next = pos.
getTraits().position_->next;
1014 last_bucket = (
Position)(bucket_.size() - 1);
1017 if (f.
getTraits().bucket_ > last_bucket)
1024 Size no_deletions = 0;
1027 for (; bucket <= last_bucket; bucket++)
1029 if (bucket_[bucket] == 0)
1036 if ((bucket == f.
getTraits().bucket_) && (bucket_[bucket] != f.
getTraits().position_))
1039 Node* n = bucket_[bucket];
1041 for (; (n->next != f.
getTraits().position_) && (n->next != 0); n = n->next) {};
1043 if (bucket == last_bucket)
1049 for (n = next; (n != 0) && (n != l.
getTraits().position_); n = next)
1067 for (n = next; n != 0; n = next)
1077 else if (bucket < last_bucket)
1081 for (Node* n = bucket_[bucket]; n != 0; n = next)
1087 bucket_[bucket] = 0;
1089 else if (bucket == last_bucket)
1094 Node* n = bucket_[bucket];
1096 for (; (n != 0) && (n != l.
getTraits().position_); n = next)
1103 bucket_[bucket] = l.
getTraits().position_;
1108 size_ -= no_deletions;
1111 template <
class Key>
1115 visitor.visit(*
this);
1118 template <
class Key>
1122 return (find(key) != end());
1125 template <
class Key>
1129 return (size_ == 0);
1132 template <
class Key>
1135 if (size_ != hash_set.size_)
1142 while (it1 != end())
1154 template <
class Key>
1158 return !(*
this == hash_set);
1161 template <
class Key>
1169 for (node = bucket_[bucket]; node != 0; node = node->next)
1173 if (node->next == 0)
1180 return (size_ == size);
1183 template <
class Key>
1191 s <<
" size: " << getSize() << std::endl;
1194 s <<
" # buckets: " << getBucketSize() << std::endl;
1197 s <<
" capacity: " << getCapacity() << std::endl;
1200 s <<
" load factor: " << (
float)size_ / (
float)bucket_.size() << std::endl;
1205 s <<
" bucket " << bucket <<
": ";
1206 for (Node* ptr = bucket_[bucket]; ptr != 0; ptr = ptr->next)
1208 s <<
"(" << (
void*)ptr <<
") ";
1210 s <<
"(0)" << std::endl;
1216 template <
class Key>
1219 if (processor.
start() ==
false)
1229 result = processor(*it);
1230 if (result <= Processor::BREAK)
1232 return (result == Processor::BREAK);
1237 return processor.
finish();
1240 template <
class Key>
1247 template <
class Key>
1254 template <
class Key>
1259 Node* next_node = 0;
1260 for (i = 0; i < bucket_.size(); i++)
1265 next_node = node->next;
1273 template <
class Key>
1278 return new Node(value, next);
1281 template <
class Key>
1288 template <
class Key>
1292 return (size_ >= capacity_);
1295 template <
class Key>
1302 template <
class Key>
1309 vector<Node*> old_buckets(bucket_);
1313 bucket_.resize(capacity_);
1315 for (i = 0; i < capacity_; i++)
1325 for (node = old_buckets[i]; node != 0; node = next_node)
1327 next_node = node->next;
1328 Position new_bucket = hashBucket_(node->value);
1329 node->next = bucket_[new_bucket];
1330 bucket_[new_bucket] = node;
1336 #endif // BALL_DATATYPE_HASHSET_H
Size getBucketSize() const
HashIndex Hash(const T &key)
bool operator!=(const HashSet &hash_set) const
ConstIterator const_iterator
std::pair< Iterator, bool > insert(const ValueType &item)
const HashSet * getContainer() const
HashSet operator|(const HashSet &rhs) const
IteratorPosition position_
Iterator find(const Key &key)
BALL_INLINE const Traits & getTraits() const
Get a constant reference to the traits of this iterator.
friend class IteratorTraits
bool apply(UnaryProcessor< ValueType > &processor)
ConstForwardIterator< HashSet< Key >, ValueType, PointerType, IteratorTraits > ConstIterator
virtual HashIndex hash(const Key &key) const
static ConstForwardIterator end(const Container &container)
ForwardIterator< HashSet< Key >, ValueType, PointerType, IteratorTraits > Iterator
ConstIterator end() const
Initial number of buckets.
const IteratorPosition & getPosition() const
HashSet operator-(const HashSet &rhs) const
const HashSet & operator-=(const HashSet &rhs)
const Key * const_pointer
virtual void deleteNode_(Node *node) const
Size erase(const KeyType &key)
const HashSet & operator&=(const HashSet &rhs)
virtual bool needRehashing_() const
BALL_EXPORT bool operator!=(const String &s1, const String &s2)
IteratorPosition & getPosition()
HashSet(Size initial_capacity=INITIAL_CAPACITY, Size number_of_buckets=INITIAL_NUMBER_OF_BUCKETS)
static const Position INVALID_POSITION
void swap(HashSet &hash_set)
IteratorTraits(const IteratorTraits &traits)
const HashSet & operator+=(const HashSet &rhs)
BALL_EXPORT bool operator==(const String &s1, const String &s2)
virtual Node * newNode_(const ValueType &value, Node *next) const
void set(const HashSet &hash_set)
static ForwardIterator end(const Container &container)
HashSet operator+(const HashSet &rhs) const
const ValueType & getData() const
const Key & const_reference
const HashSet & operator=(const HashSet &rhs)
-*- Mode: C++; tab-width: 2; -*-
HashSet operator&(const HashSet &rhs) const
IllegalKey(const char *file, int line)
#define BALL_DUMP_STREAM_PREFIX(os)
ConstRandomAccessIterator< Container, DataType, Position, Traits > operator+(Distance distance, const ConstRandomAccessIterator< Container, DataType, Position, Traits > &iterator)
BALL_EXPORT HashIndex getNextPrime(HashIndex l)
virtual void dump(std::ostream &s=std::cout, Size depth=0) const
static ConstForwardIterator begin(const Container &container)
ConstIterator begin() const
#define BALL_DUMP_STREAM_SUFFIX(os)
#define BALL_DUMP_DEPTH(os, depth)
BALL_INLINE TAngle< T > operator-(const T &val, const TAngle< T > &angle)
static ForwardIterator begin(const Container &container)
bool operator==(const HashSet &hash_set) const
const HashSet & operator|=(const HashSet &rhs)
bool has(const Key &key) const
Node(const KeyType &my_key, const Node *my_next)
Initial capacity of the hash set.
virtual void host(Visitor< HashSet< Key > > &visitor)
IteratorTraits(const HashSet &hash_set)