BALL 1.5.0
hashSet.h
Go to the documentation of this file.
1// -*- Mode: C++; tab-width: 2; -*-
2// vi: set ts=2:
3//
4
5#ifndef BALL_DATATYPE_HASHSET_H
6#define BALL_DATATYPE_HASHSET_H
7
8#ifndef BALL_COMMON_H
9# include <BALL/common.h>
10#endif
11
12#ifndef BALL_COMMON_HASH_H
13# include <BALL/COMMON/hash.h>
14#endif
15
16#ifndef BALL_CONCEPT_FORWARDITERATOR_H
18#endif
19
20#ifndef BALL_CONCEPT_VISITOR_H
21# include <BALL/CONCEPT/visitor.h>
22#endif
23
24#ifndef BALL_DATATYPE_FOREACH_H
26#endif
27
28#ifndef BALL_CONCEPT_PREDICATE_H
30#endif
31
32#ifndef BALL_CONCEPT_PROCESSOR_H
34#endif
35
36#include <algorithm>
37
38
39namespace BALL
40{
44 template <class Key>
45 class HashSet
46 {
47 public:
48
51 typedef Key ValueType;
52
55 typedef Key KeyType;
56
59 typedef Key* PointerType;
60
61 // --- EXTERNAL ITERATORS
62 struct Node
63 {
66
67 Node(const KeyType& my_key, const Node* my_next)
68 : next(const_cast<Node*>(my_next)),
69 value(const_cast<ValueType&>(my_key))
70 {
71 }
72 };
73
75
77 {
78
79 friend class HashSet<Key>;
80 public:
81
83 : bound_(0),
84 position_(0),
85 bucket_(0)
86 {
87 }
88
89 IteratorTraits(const HashSet& hash_set)
90 : bound_(const_cast<HashSet*>(&hash_set)),
91 position_(0),
92 bucket_(0)
93 {
94 }
95
97 : bound_(traits.bound_),
98 position_(traits.position_),
99 bucket_(traits.bucket_)
100 {
101 }
102
104 {
105 bound_ = traits.bound_;
106 position_ = traits.position_;
107 bucket_ = traits.bucket_;
108
109 return *this;
110 }
111
113 {
114 return bound_;
115 }
116
117 const HashSet* getContainer() const
118 {
119 return bound_;
120 }
121
122 bool isSingular() const
123 {
124 return (bound_ == 0);
125 }
126
128 {
129 return position_;
130 }
131
133 {
134 return position_;
135 }
136
137 bool operator == (const IteratorTraits& traits) const
138 {
139 return (position_ == traits.position_);
140 }
141
142 bool operator != (const IteratorTraits& traits) const
143 {
144 return (position_ != traits.position_);
145 }
146
147 bool isValid() const
148 {
149 return ((bound_ != 0) && (position_ != 0)
150 && (bucket_ < (Position)bound_->bucket_.size()));
151 }
152
154 {
155 bound_ = 0;
156 position_ = 0;
158 }
159
160 void toBegin()
161 {
162 for (bucket_ = 0; bucket_ < (Position)bound_->bucket_.size(); ++bucket_)
163 {
164 position_ = bound_->bucket_[bucket_];
165
166 if (position_ != 0)
167 {
168 return;
169 }
170 }
171 }
172
173 bool isBegin() const
174 {
175 for (Position bucket = 0; bucket < (Position)bound_->bucket_.size(); ++bucket)
176 {
177 if (bound_->bucket_[bucket_] != 0)
178 {
179 if (position_ == bound_->bucket_[bucket_])
180 {
181 return true;
182 }
183 else
184 {
185 return false;
186 }
187 }
188 }
189
190 return false;
191 }
192
193 void toEnd()
194 {
195 position_ = 0;
196 }
197
198 bool isEnd() const
199 {
200 return (position_ == 0);
201 }
202
204 {
205 return position_->value;
206 }
207
208 const ValueType& getData() const
209 {
210 return position_->value;
211 }
212
213 void forward()
214 {
216
217 if (position_ != 0)
218 {
219 return;
220 }
221
222 for (++bucket_; bucket_ < (Position)bound_->bucket_.size(); ++bucket_)
223 {
224 position_ = bound_->bucket_[bucket_];
225
226 if (position_ != 0)
227 {
228 return;
229 }
230 }
231 }
232
233 protected:
234
238 };
239 friend class IteratorTraits;
240
244
245 enum
246 {
251 };
252
254
258
265 {
266 public:
267 IllegalKey(const char* file, int line)
268 : Exception::GeneralException(file, line)
269 {
270 }
271 };
272
274
278
281
284
285 // STL compatibility stuff
291 typedef Key value_type;
293 typedef Key key_type;
295 typedef Key* pointer;
297 typedef const Key* const_pointer;
299 typedef Key& reference;
301 typedef const Key& const_reference;
307
311
314 HashSet(Size initial_capacity = INITIAL_CAPACITY, Size number_of_buckets = INITIAL_NUMBER_OF_BUCKETS);
315
318 HashSet(const HashSet& hash_set);
319
322 virtual ~HashSet()
323 {
324 destroy();
325 deleteBuckets_();
326 }
327
332 virtual void clear();
333
339 void destroy();
340
342
346
350 void set(const HashSet& hash_set);
351
355 const HashSet& operator = (const HashSet& rhs);
356
360 void get(HashSet& hash_set) const;
361
364 void swap(HashSet& hash_set);
365
367
371
375
379
382 Size getSize() const;
383
386 Size size() const;
387
390 Iterator find(const Key& key);
391
394 ConstIterator find(const Key& key) const;
395
398 std::pair<Iterator, bool> insert(const ValueType& item);
399
404
408 Size erase(const KeyType& key);
409
415 void erase(Iterator pos);
416
422
424
432 const HashSet& operator &= (const HashSet& rhs);
433
438 const HashSet& operator |= (const HashSet& rhs);
439
444 HashSet operator & (const HashSet& rhs) const;
445
450 HashSet operator | (const HashSet& rhs) const;
451
455 HashSet operator + (const HashSet& rhs) const;
456
462 HashSet operator - (const HashSet& rhs) const;
463
467 const HashSet& operator += (const HashSet& rhs);
468
472 const HashSet& operator -= (const HashSet& rhs);
474
478
481 virtual void host(Visitor<HashSet<Key> >& visitor);
483
487
490 bool has(const Key& key) const;
491
494 bool isEmpty() const;
495
498 bool operator == (const HashSet& hash_set) const;
499
502 bool operator != (const HashSet& hash_set) const;
504
508
513 bool isValid() const;
514
517 virtual void dump(std::ostream& s = std::cout, Size depth = 0) const;
518
520
521 // --- INTERNAL ITERATORS
522
531
532
533
537 {
538 return Iterator::begin(*this);
539 }
540
544 {
545 return Iterator::end(*this);
546 }
547
551 {
552 return ConstIterator::begin(*this);
553 }
554
558 {
559 return ConstIterator::end(*this);
560 }
561
562
563 protected:
564
565 virtual Node* newNode_(const ValueType& value, Node* next) const;
566
567 virtual void deleteNode_(Node* node) const;
568
569 virtual HashIndex hash(const Key& key) const;
570
571 virtual bool needRehashing_() const;
572
573 virtual void rehash();
574
575 private:
576
577 void deleteBuckets_();
578
579 Position hashBucket_(const Key& key) const;
580
581 void rehash_();
582
583 // --- ATTRIBUTES
584
585 /*_ The number of elements in the hash set
586 */
587 Size size_;
588
589 /*_ The capacity - usually the number of buckets
590 */
591 Size capacity_;
592
593 /*_ Buckets are stored as a vector of linked lists of Nodes
594 */
595 vector<Node*> bucket_;
596 };
597
598
599 template <class Key>
600 HashSet<Key>::HashSet(Size initial_capacity, Size number_of_buckets)
601 : size_(0),
602 capacity_(initial_capacity),
603 bucket_(number_of_buckets)
604 {
605 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
606 {
607 bucket_[bucket] = 0;
608 }
609 }
610
611 template <class Key>
613 : size_(hash_set.size_),
614 capacity_(hash_set.capacity_),
615 bucket_(hash_set.bucket_.size())
616 {
617 Node* item = 0;
618
619 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
620 {
621 bucket_[bucket] = 0;
622
623 for (item = hash_set.bucket_[bucket]; item != 0; item = item->next)
624 {
625 bucket_[bucket] = newNode_(item->value, bucket_[bucket]);
626 }
627 }
628 }
629
630 template <class Key>
631 void HashSet<Key>::set(const HashSet& hash_set)
632 {
633 if (&hash_set == this)
634 {
635 return;
636 }
637
638 destroy();
639
640 deleteBuckets_();
641
642 size_ = hash_set.size_;
643 capacity_ = hash_set.capacity_;
644 bucket_.resize(hash_set.bucket_.size());
645
646 Node* item = 0;
647
648 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
649 {
650 bucket_[bucket] = 0;
651
652 for (item = hash_set.bucket_[bucket]; item != 0; item = item->next)
653 {
654 bucket_[bucket] = newNode_(item->value, bucket_[bucket]);
655 }
656 }
657 }
658
659 template <class Key>
661 {
662 Node* node = 0;
663 Node* next_node = 0;
664
665 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
666 {
667 for (node = bucket_[bucket]; node != 0; node = next_node)
668 {
669 next_node = node->next;
670 deleteNode_(node);
671 }
672
673 bucket_[bucket] = 0;
674 }
675
676 size_ = 0;
677 }
678
679 template <class Key>
682 {
683 clear();
684 }
685
686 template <class Key>
689 {
690 set(hash_set);
691 return *this;
692 }
693
694 template <class Key>
696 void HashSet<Key>::get(HashSet& hash_set) const
697
698 {
699 hash_set.set(*this);
700 }
701
702 template <class Key>
705 {
706 std::swap(size_, hash_set.size_);
707 std::swap(capacity_, hash_set.capacity_);
708 std::swap(bucket_, hash_set.bucket_);
709 }
710
711 template <class Key>
714 {
715 // Store all elements that are not part of the intersection
716 // in a list for subsequent deletion.
717 std::list<Key> erase_list;
718 for (Iterator it = begin(); it != end(); ++it)
719 {
720 if (!rhs.has(*it))
721 {
722 erase_list.push_back(*it);
723 }
724 }
725
726 // erase all elements not part of the intersection
727 typename list<Key>::iterator list_it = erase_list.begin();
728 for (; list_it != erase_list.end(); ++list_it)
729 {
730 erase(*list_it);
731 }
732
733 return *this;
734 }
735
736 template <class Key>
739 {
740 // Compute the union of both sets by inserting every element of the
741 // rhs set.
742 for (ConstIterator it = rhs.begin(); it != rhs.end(); ++it)
743 {
744 insert(*it);
745 }
746
747 return *this;
748 }
749
750 template <class Key>
753 {
754 return operator |= (rhs);
755 }
756
757 template <class Key>
760 {
761 // Create an empty hash set...
762 HashSet<Key> tmp;
763 ConstIterator it = begin();
764
765 // ...and copy all the elements contained in the rhs hash set.
766 for (; +it; ++it)
767 {
768 if (rhs.has(*it))
769 {
770 tmp.insert(*it);
771 }
772 }
773
774 return tmp;
775 }
776
777 template <class Key>
780 {
781 // Create an empty hash set...
782 HashSet<Key> tmp;
783 ConstIterator it = begin();
784
785 // ...and copy all the elements contained in this set and not in the rhs hash set.
786 for (; +it; ++it)
787 {
788 if (!rhs.has(*it))
789 {
790 tmp.insert(*it);
791 }
792 }
793
794 return tmp;
795 }
796
797 template <class Key>
800 {
801 // avoid memory corruption caused by iterating over freed space when
802 // deleting myself
803 if (this == &hash_set)
804 {
805 clear();
806 }
807 else
808 {
809 // erase all elements which are contained in this and hash_set
810 typename HashSet<Key>::ConstIterator it = hash_set.begin();
811 for (; it != hash_set.end(); ++it)
812 {
813 if (has(*it))
814 {
815 erase(*it);
816 }
817 }
818 }
819 return *this;
820 }
821
822 template <class Key>
825 {
826 HashSet<Key> tmp(*this);
827 tmp |= rhs;
828
829 return tmp;
830 }
831
832 template <class Key>
835 {
836 return operator | (rhs);
837 }
838
839 template <class Key>
842 {
843 return (Size)bucket_.size();
844 }
845
846 template <class Key>
849 {
850 return capacity_;
851 }
852
853 template <class Key>
856 {
857 return size_;
858 }
859
860 template <class Key>
863 {
864 return size_;
865 }
866
867 template <class Key>
869 {
870 Iterator it = end();
871 Position bucket = hashBucket_(key);
872 Node* node_ptr = bucket_[bucket];
873 while (node_ptr != 0)
874 {
875 if (node_ptr->value == key)
876 {
877 it.getTraits().position_ = node_ptr;
878 it.getTraits().bucket_ = bucket;
879 break;
880 }
881 node_ptr = node_ptr->next;
882 }
883
884 return it;
885 }
886
887 template <class Key>
889 typename HashSet<Key>::ConstIterator HashSet<Key>::find(const Key& key) const
890 {
891 return (const_cast<HashSet*>(this))->find(key);
892 }
893
894 template <class Key>
895 std::pair<typename HashSet<Key>::Iterator, bool> HashSet<Key>::insert
896 (const ValueType& item)
897 {
898 Iterator it = find(item);
899 if (it == end())
900 {
901 if (needRehashing_() == true)
902 {
903 rehash_();
904 }
905
906 Position bucket = hashBucket_(item);
907
908 Node* next = bucket_[bucket];
909 bucket_[bucket] = newNode_(item, next);
910
911 ++size_;
912 it.getTraits().position_ = bucket_[bucket];
913 it.getTraits().bucket_ = bucket;
914 }
915
916 return std::pair<Iterator, bool>(it, true);
917 }
918
919 template <class Key>
921 (typename HashSet<Key>::Iterator /* pos */, const ValueType& item)
922 {
923 return insert(item).first;
924 }
925
926 template <class Key>
928 {
929 Position bucket = hashBucket_(key);
930 Node* previous = 0;
931 Node* node_ptr = bucket_[bucket];
932
933 while (node_ptr != 0 && node_ptr->value != key)
934 {
935 previous = node_ptr;
936 node_ptr = node_ptr->next;
937 }
938
939 if (node_ptr == 0)
940 {
941 return false;
942 }
943
944 if (node_ptr == bucket_[bucket])
945 {
946 bucket_[bucket] = node_ptr->next;
947 }
948 else
949 {
950 previous->next = node_ptr->next;
951 }
952
953 deleteNode_(node_ptr);
954 --size_;
955
956 return 1;
957 }
958
959 template <class Key>
961 {
962 if (pos.getTraits().bound_ != this)
963 {
964 throw Exception::IncompatibleIterators(__FILE__, __LINE__);
965 }
966
967 if ((pos == end()) || (size_ == 0))
968 {
969 return;
970 }
971
972 if (pos.getTraits().position_ == bucket_[pos.getTraits().bucket_])
973 {
974 bucket_[pos.getTraits().bucket_] = pos.getTraits().position_->next;
975 }
976 else
977 {
978 // walk over all nodes in this bucket and identify the predecessor
979 // of the node refered to by the iterator pos
980 Node* prev = bucket_[pos.getTraits().bucket_];
981 for (; (prev != 0) && (prev->next != pos.getTraits().position_); prev = prev->next) {};
982 if (prev != 0)
983 {
984 // remove the node and reconnect the list
985 prev->next = pos.getTraits().position_->next;
986 }
987 else
988 {
989 throw Exception::InvalidIterator(__FILE__, __LINE__);
990 }
991 }
992
993 // delete the node and decrement the set size
994 deleteNode_(pos.getTraits().position_);
995 --size_;
996 }
997
998 template <class Key>
1000 {
1001 if (f.getTraits().bound_ != this || l.getTraits().bound_ != this)
1002 {
1003 throw Exception::IncompatibleIterators(__FILE__, __LINE__);
1004 }
1005
1006 if (f == end())
1007 {
1008 return;
1009 }
1010
1011 Position last_bucket = l.getTraits().bucket_;
1012 if (l == end())
1013 {
1014 last_bucket = (Position)(bucket_.size() - 1);
1015 }
1016
1017 if (f.getTraits().bucket_ > last_bucket)
1018 {
1019 // empty range - l < f
1020 return;
1021 }
1022
1023 // count the deleted entries to correct the set size
1024 Size no_deletions = 0;
1025
1026 Position bucket = f.getTraits().bucket_;
1027 for (; bucket <= last_bucket; bucket++)
1028 {
1029 if (bucket_[bucket] == 0)
1030 {
1031 // skip all empty buckets
1032 continue;
1033 }
1034
1035
1036 if ((bucket == f.getTraits().bucket_) && (bucket_[bucket] != f.getTraits().position_))
1037 {
1038 // find the predecessor of f
1039 Node* n = bucket_[bucket];
1040 Node* next;
1041 for (; (n->next != f.getTraits().position_) && (n->next != 0); n = n->next) {};
1042
1043 if (bucket == last_bucket)
1044 {
1045 // delete everything from f to l in this bucket
1046
1047 next = n->next;
1048 n->next = l.getTraits().position_;
1049 for (n = next; (n != 0) && (n != l.getTraits().position_); n = next)
1050 {
1051 next = n->next;
1052 deleteNode_(n);
1053 no_deletions++;
1054 }
1055 }
1056 else
1057 {
1058 // delete everything from f to the end in this bucket
1059
1060 if (n != 0)
1061 {
1062 // mark the end of the list
1063 next = n->next;
1064 n->next = 0;
1065
1066 // delete all remaining nodes
1067 for (n = next; n != 0; n = next)
1068 {
1069 next = n->next;
1070 deleteNode_(n);
1071 no_deletions++;
1072 }
1073 }
1074 }
1075 }
1076 // if the current bucket lies between the first and the last bucket...
1077 else if (bucket < last_bucket)
1078 {
1079 // ...delete the whole bucket
1080 Node* next;
1081 for (Node* n = bucket_[bucket]; n != 0; n = next)
1082 {
1083 next = n->next;
1084 deleteNode_(n);
1085 no_deletions++;
1086 }
1087 bucket_[bucket] = 0;
1088 }
1089 else if (bucket == last_bucket)
1090 {
1091 // we delete everything in this bucket up to the iterator l
1092
1093 // find the predecessor of l
1094 Node* n = bucket_[bucket];
1095 Node* next;
1096 for (; (n != 0) && (n != l.getTraits().position_); n = next)
1097 {
1098 next = n->next;
1099 deleteNode_(n);
1100 no_deletions++;
1101 }
1102
1103 bucket_[bucket] = l.getTraits().position_;
1104 }
1105 }
1106
1107 // correct the set size
1108 size_ -= no_deletions;
1109 }
1110
1111 template <class Key>
1114 {
1115 visitor.visit(*this);
1116 }
1117
1118 template <class Key>
1120 bool HashSet<Key>::has(const Key& key) const
1121 {
1122 return (find(key) != end());
1123 }
1124
1125 template <class Key>
1128 {
1129 return (size_ == 0);
1130 }
1131
1132 template <class Key>
1133 bool HashSet<Key>::operator == (const HashSet& hash_set) const
1134 {
1135 if (size_ != hash_set.size_)
1136 {
1137 return false;
1138 }
1139
1140 ConstIterator it1 = begin();
1141 ConstIterator it2 = hash_set.begin();
1142 while (it1 != end())
1143 {
1144 if (*it1 != *it2)
1145 {
1146 return false;
1147 }
1148 it1++;
1149 it2++;
1150 }
1151 return true;
1152 }
1153
1154 template <class Key>
1156 bool HashSet<Key>::operator != (const HashSet& hash_set) const
1157 {
1158 return !(*this == hash_set);
1159 }
1160
1161 template <class Key>
1163 {
1164 Size size = 0;
1165 Node* node = 0;
1166
1167 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
1168 {
1169 for (node = bucket_[bucket]; node != 0; node = node->next)
1170 {
1171 ++size;
1172
1173 if (node->next == 0)
1174 {
1175 break;
1176 }
1177 }
1178 }
1179
1180 return (size_ == size);
1181 }
1182
1183 template <class Key>
1184 void HashSet<Key>::dump(std::ostream& s, Size depth) const
1185 {
1187
1188 BALL_DUMP_DEPTH(s, depth);
1189
1190 BALL_DUMP_DEPTH(s, depth);
1191 s << " size: " << getSize() << std::endl;
1192
1193 BALL_DUMP_DEPTH(s, depth);
1194 s << " # buckets: " << getBucketSize() << std::endl;
1195
1196 BALL_DUMP_DEPTH(s, depth);
1197 s << " capacity: " << getCapacity() << std::endl;
1198
1199 BALL_DUMP_DEPTH(s, depth);
1200 s << " load factor: " << (float)size_ / (float)bucket_.size() << std::endl;
1201
1202 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket)
1203 {
1204 BALL_DUMP_DEPTH(s, depth);
1205 s << " bucket " << bucket << ": ";
1206 for (Node* ptr = bucket_[bucket]; ptr != 0; ptr = ptr->next)
1207 {
1208 s << "(" << (void*)ptr << ") ";
1209 }
1210 s << "(0)" << std::endl;
1211 }
1212
1214 }
1215
1216 template <class Key>
1218 {
1219 if (processor.start() == false)
1220 {
1221 return false;
1222 }
1223
1224 Processor::Result result;
1225
1226 Iterator it = begin();
1227 while (it != end())
1228 {
1229 result = processor(*it);
1230 if (result <= Processor::BREAK)
1231 {
1232 return (result == Processor::BREAK);
1233 }
1234 it++;
1235 }
1236
1237 return processor.finish();
1238 }
1239
1240 template <class Key>
1242 HashIndex HashSet<Key>::hash(const Key& key) const
1243 {
1244 return (HashIndex)Hash(key);
1245 }
1246
1247 template <class Key>
1250 {
1251 capacity_ = (Size)getNextPrime((Size)bucket_.size() << 1);
1252 }
1253
1254 template <class Key>
1256 {
1257 Size i = 0;
1258 Node* node = 0;
1259 Node* next_node = 0;
1260 for (i = 0; i < bucket_.size(); i++)
1261 {
1262 node = bucket_[i];
1263 while (node != 0)
1264 {
1265 next_node = node->next;
1266 delete node;
1267 node = next_node;
1268 }
1269 bucket_[i] = 0;
1270 }
1271 }
1272
1273 template <class Key>
1276 (const ValueType& value, typename HashSet<Key>::Node* next) const
1277 {
1278 return new Node(value, next);
1279 }
1280
1281 template <class Key>
1284 {
1285 delete node;
1286 }
1287
1288 template <class Key>
1291 {
1292 return (size_ >= capacity_);
1293 }
1294
1295 template <class Key>
1297 HashIndex HashSet<Key>::hashBucket_(const Key& key) const
1298 {
1299 return (Position)((HashIndex)hash(key) % (HashIndex)bucket_.size());
1300 }
1301
1302 template <class Key>
1303 void HashSet<Key>::rehash_()
1304 {
1305 // calculate the new number of buckets (in capacity_)
1306 rehash();
1307
1308 // save the old contents
1309 vector<Node*> old_buckets(bucket_);
1310
1311 // resize the bucket vector and initialize it with zero
1312 bucket_.clear();
1313 bucket_.resize(capacity_);
1314 Position i;
1315 for (i = 0; i < capacity_; i++)
1316 {
1317 bucket_[i] = 0;
1318 }
1319
1320 // rehash the old contents into the new buckets
1321 Node* node;
1322 Node* next_node;
1323 for (Position i = 0; i < (Position)old_buckets.size(); ++i)
1324 {
1325 for (node = old_buckets[i]; node != 0; node = next_node)
1326 {
1327 next_node = node->next;
1328 Position new_bucket = hashBucket_(node->value);
1329 node->next = bucket_[new_bucket];
1330 bucket_[new_bucket] = node;
1331 }
1332 }
1333 }
1334} // namespace BALL
1335
1336#endif // BALL_DATATYPE_HASHSET_H
#define BALL_DUMP_STREAM_PREFIX(os)
Definition: macros.h:391
#define BALL_DUMP_STREAM_SUFFIX(os)
Definition: macros.h:395
#define BALL_DUMP_DEPTH(os, depth)
Definition: macros.h:390
#define BALL_INLINE
Definition: debug.h:15
Definition: constants.h:13
BALL_SIZE_TYPE HashIndex
static const Position INVALID_Position
BALL_SIZE_TYPE Size
HashIndex Hash(const T &key)
Definition: hash.h:47
BALL_SIZE_TYPE Position
BALL_EXPORT HashIndex getNextPrime(HashIndex l)
GeneralException()
Default constructor.
BALL_INLINE const Traits & getTraits() const
Get a constant reference to the traits of this iterator.
Definition: baseIterator.h:130
static ConstForwardIterator begin(const Container &container)
static ConstForwardIterator end(const Container &container)
static ForwardIterator begin(const Container &container)
static ForwardIterator end(const Container &container)
virtual bool start()
Definition: processor.h:92
virtual bool finish()
Definition: processor.h:99
ForwardIterator< HashSet< Key >, ValueType, PointerType, IteratorTraits > Iterator
Definition: hashSet.h:280
virtual HashIndex hash(const Key &key) const
Definition: hashSet.h:1242
Size size() const
Definition: hashSet.h:862
void erase(Iterator f, Iterator l)
Definition: hashSet.h:999
Key * pointer
Definition: hashSet.h:295
const Key & const_reference
Definition: hashSet.h:301
Size size_type
Definition: hashSet.h:303
void set(const HashSet &hash_set)
Definition: hashSet.h:631
ConstIterator find(const Key &key) const
Definition: hashSet.h:889
bool isValid() const
Definition: hashSet.h:1162
bool isEmpty() const
Definition: hashSet.h:1127
const HashSet & operator&=(const HashSet &rhs)
Definition: hashSet.h:713
bool operator!=(const HashSet &hash_set) const
Definition: hashSet.h:1156
void get(HashSet &hash_set) const
Definition: hashSet.h:696
virtual Node * newNode_(const ValueType &value, Node *next) const
Definition: hashSet.h:1276
ConstIterator const_iterator
Definition: hashSet.h:289
HashSet operator-(const HashSet &rhs) const
Definition: hashSet.h:779
HashSet(const HashSet &hash_set)
Definition: hashSet.h:612
ConstIterator end() const
Definition: hashSet.h:557
Iterator begin()
Definition: hashSet.h:536
std::pair< Iterator, bool > insert(const ValueType &item)
Definition: hashSet.h:896
HashSet operator+(const HashSet &rhs) const
Definition: hashSet.h:834
ConstIterator begin() const
Definition: hashSet.h:550
HashSet(Size initial_capacity=INITIAL_CAPACITY, Size number_of_buckets=INITIAL_NUMBER_OF_BUCKETS)
Definition: hashSet.h:600
const HashSet & operator+=(const HashSet &rhs)
Definition: hashSet.h:752
bool has(const Key &key) const
Definition: hashSet.h:1120
Iterator insert(Iterator pos, const ValueType &item)
Key & reference
Definition: hashSet.h:299
virtual void deleteNode_(Node *node) const
Definition: hashSet.h:1283
virtual void dump(std::ostream &s=std::cout, Size depth=0) const
Definition: hashSet.h:1184
Node * IteratorPosition
Definition: hashSet.h:74
virtual void rehash()
Definition: hashSet.h:1249
const HashSet & operator=(const HashSet &rhs)
Definition: hashSet.h:688
Size getSize() const
Definition: hashSet.h:855
Key value_type
Definition: hashSet.h:291
Key ValueType
Definition: hashSet.h:51
virtual ~HashSet()
Definition: hashSet.h:322
HashSet operator|(const HashSet &rhs) const
Definition: hashSet.h:824
Iterator end()
Definition: hashSet.h:543
const HashSet & operator|=(const HashSet &rhs)
Definition: hashSet.h:738
const HashSet & operator-=(const HashSet &rhs)
Definition: hashSet.h:799
HashSet operator&(const HashSet &rhs) const
Definition: hashSet.h:759
void destroy()
Definition: hashSet.h:681
bool operator==(const HashSet &hash_set) const
Definition: hashSet.h:1133
Size getBucketSize() const
Definition: hashSet.h:841
virtual void host(Visitor< HashSet< Key > > &visitor)
Definition: hashSet.h:1113
@ INITIAL_NUMBER_OF_BUCKETS
Initial number of buckets.
Definition: hashSet.h:250
@ INITIAL_CAPACITY
Initial capacity of the hash set.
Definition: hashSet.h:248
Index difference_type
Definition: hashSet.h:305
Key key_type
Definition: hashSet.h:293
bool apply(UnaryProcessor< ValueType > &processor)
Definition: hashSet.h:1217
Iterator iterator
Definition: hashSet.h:287
virtual void clear()
Definition: hashSet.h:660
Key KeyType
Definition: hashSet.h:55
ConstForwardIterator< HashSet< Key >, ValueType, PointerType, IteratorTraits > ConstIterator
Definition: hashSet.h:283
Size erase(const KeyType &key)
Definition: hashSet.h:927
void swap(HashSet &hash_set)
Definition: hashSet.h:704
void erase(Iterator pos)
Definition: hashSet.h:960
Key * PointerType
Definition: hashSet.h:59
Size getCapacity() const
Definition: hashSet.h:848
const Key * const_pointer
Definition: hashSet.h:297
virtual bool needRehashing_() const
Definition: hashSet.h:1290
Iterator find(const Key &key)
Definition: hashSet.h:868
ValueType value
Definition: hashSet.h:65
Node(const KeyType &my_key, const Node *my_next)
Definition: hashSet.h:67
const HashSet * getContainer() const
Definition: hashSet.h:117
const ValueType & getData() const
Definition: hashSet.h:208
IteratorTraits & operator=(const IteratorTraits &traits)
Definition: hashSet.h:103
IteratorPosition position_
Definition: hashSet.h:236
IteratorTraits(const IteratorTraits &traits)
Definition: hashSet.h:96
bool operator==(const IteratorTraits &traits) const
Definition: hashSet.h:137
IteratorPosition & getPosition()
Definition: hashSet.h:127
bool operator!=(const IteratorTraits &traits) const
Definition: hashSet.h:142
IteratorTraits(const HashSet &hash_set)
Definition: hashSet.h:89
const IteratorPosition & getPosition() const
Definition: hashSet.h:132
IllegalKey(const char *file, int line)
Definition: hashSet.h:267