BALL
1.4.1
|
00001 // -*- Mode: C++; tab-width: 2; -*- 00002 // vi: set ts=2: 00003 // 00004 00005 #ifndef BALL_DATATYPE_HASHSET_H 00006 #define BALL_DATATYPE_HASHSET_H 00007 00008 #ifndef BALL_COMMON_H 00009 # include <BALL/common.h> 00010 #endif 00011 00012 #ifndef BALL_COMMON_HASH_H 00013 # include <BALL/COMMON/hash.h> 00014 #endif 00015 00016 #ifndef BALL_CONCEPT_FORWARDITERATOR_H 00017 # include <BALL/CONCEPT/forwardIterator.h> 00018 #endif 00019 00020 #ifndef BALL_CONCEPT_VISITOR_H 00021 # include <BALL/CONCEPT/visitor.h> 00022 #endif 00023 00024 #ifndef BALL_DATATYPE_FOREACH_H 00025 # include <BALL/DATATYPE/forEach.h> 00026 #endif 00027 00028 #ifndef BALL_CONCEPT_PREDICATE_H 00029 # include <BALL/CONCEPT/predicate.h> 00030 #endif 00031 00032 #ifndef BALL_CONCEPT_PROCESSOR_H 00033 # include <BALL/CONCEPT/processor.h> 00034 #endif 00035 00036 #include <algorithm> 00037 00038 00039 namespace BALL 00040 { 00044 template <class Key> 00045 class HashSet 00046 { 00047 public: 00048 00051 typedef Key ValueType; 00052 00055 typedef Key KeyType; 00056 00059 typedef Key* PointerType; 00060 00061 // --- EXTERNAL ITERATORS 00062 struct Node 00063 { 00064 Node* next; 00065 ValueType value; 00066 00067 Node(const KeyType& my_key, const Node* my_next) 00068 : next(const_cast<Node*>(my_next)), 00069 value(const_cast<ValueType&>(my_key)) 00070 { 00071 } 00072 }; 00073 00074 typedef Node* IteratorPosition; 00075 00076 class IteratorTraits 00077 { 00078 00079 friend class HashSet<Key>; 00080 public: 00081 00082 IteratorTraits() 00083 : bound_(0), 00084 position_(0), 00085 bucket_(0) 00086 { 00087 } 00088 00089 IteratorTraits(const HashSet& hash_set) 00090 : bound_(const_cast<HashSet*>(&hash_set)), 00091 position_(0), 00092 bucket_(0) 00093 { 00094 } 00095 00096 IteratorTraits(const IteratorTraits& traits) 00097 : bound_(traits.bound_), 00098 position_(traits.position_), 00099 bucket_(traits.bucket_) 00100 { 00101 } 00102 00103 IteratorTraits& operator = (const IteratorTraits& traits) 00104 { 00105 bound_ = traits.bound_; 00106 position_ = traits.position_; 00107 bucket_ = traits.bucket_; 00108 00109 return *this; 00110 } 00111 00112 HashSet* getContainer() 00113 { 00114 return bound_; 00115 } 00116 00117 const HashSet* getContainer() const 00118 { 00119 return bound_; 00120 } 00121 00122 bool isSingular() const 00123 { 00124 return (bound_ == 0); 00125 } 00126 00127 IteratorPosition& getPosition() 00128 { 00129 return position_; 00130 } 00131 00132 const IteratorPosition& getPosition() const 00133 { 00134 return position_; 00135 } 00136 00137 bool operator == (const IteratorTraits& traits) const 00138 { 00139 return (position_ == traits.position_); 00140 } 00141 00142 bool operator != (const IteratorTraits& traits) const 00143 { 00144 return (position_ != traits.position_); 00145 } 00146 00147 bool isValid() const 00148 { 00149 return ((bound_ != 0) && (position_ != 0) 00150 && (bucket_ < (Position)bound_->bucket_.size())); 00151 } 00152 00153 void invalidate() 00154 { 00155 bound_ = 0; 00156 position_ = 0; 00157 bucket_ = INVALID_POSITION; 00158 } 00159 00160 void toBegin() 00161 { 00162 for (bucket_ = 0; bucket_ < (Position)bound_->bucket_.size(); ++bucket_) 00163 { 00164 position_ = bound_->bucket_[bucket_]; 00165 00166 if (position_ != 0) 00167 { 00168 return; 00169 } 00170 } 00171 } 00172 00173 bool isBegin() const 00174 { 00175 for (Position bucket = 0; bucket < (Position)bound_->bucket_.size(); ++bucket) 00176 { 00177 if (bound_->bucket_[bucket_] != 0) 00178 { 00179 if (position_ == bound_->bucket_[bucket_]) 00180 { 00181 return true; 00182 } 00183 else 00184 { 00185 return false; 00186 } 00187 } 00188 } 00189 00190 return false; 00191 } 00192 00193 void toEnd() 00194 { 00195 position_ = 0; 00196 } 00197 00198 bool isEnd() const 00199 { 00200 return (position_ == 0); 00201 } 00202 00203 ValueType& getData() 00204 { 00205 return position_->value; 00206 } 00207 00208 const ValueType& getData() const 00209 { 00210 return position_->value; 00211 } 00212 00213 void forward() 00214 { 00215 position_ = position_->next; 00216 00217 if (position_ != 0) 00218 { 00219 return; 00220 } 00221 00222 for (++bucket_; bucket_ < (Position)bound_->bucket_.size(); ++bucket_) 00223 { 00224 position_ = bound_->bucket_[bucket_]; 00225 00226 if (position_ != 0) 00227 { 00228 return; 00229 } 00230 } 00231 } 00232 00233 protected: 00234 00235 HashSet* bound_; 00236 IteratorPosition position_; 00237 Position bucket_; 00238 }; 00239 friend class IteratorTraits; 00240 00244 00245 enum 00246 { 00248 INITIAL_CAPACITY = 4, 00250 INITIAL_NUMBER_OF_BUCKETS = 3 00251 }; 00252 00254 00258 00263 class IllegalKey 00264 : public Exception::GeneralException 00265 { 00266 public: 00267 IllegalKey(const char* file, int line) 00268 : Exception::GeneralException(file, line) 00269 { 00270 } 00271 }; 00272 00274 00278 00280 typedef ForwardIterator<HashSet<Key>, ValueType, PointerType, IteratorTraits> Iterator; 00281 00283 typedef ConstForwardIterator <HashSet<Key>, ValueType, PointerType, IteratorTraits> ConstIterator; 00284 00285 // STL compatibility stuff 00287 typedef Iterator iterator; 00289 typedef ConstIterator const_iterator; 00291 typedef Key value_type; 00293 typedef Key key_type; 00295 typedef Key* pointer; 00297 typedef const Key* const_pointer; 00299 typedef Key& reference; 00301 typedef const Key& const_reference; 00303 typedef Size size_type; 00305 typedef Index difference_type; 00307 00311 00314 HashSet(Size initial_capacity = INITIAL_CAPACITY, Size number_of_buckets = INITIAL_NUMBER_OF_BUCKETS); 00315 00318 HashSet(const HashSet& hash_set); 00319 00322 virtual ~HashSet() 00323 { 00324 destroy(); 00325 deleteBuckets_(); 00326 } 00327 00332 virtual void clear(); 00333 00339 void destroy(); 00340 00342 00346 00350 void set(const HashSet& hash_set); 00351 00355 const HashSet& operator = (const HashSet& rhs); 00356 00360 void get(HashSet& hash_set) const; 00361 00364 void swap(HashSet& hash_set); 00365 00367 00371 00374 Size getBucketSize() const; 00375 00378 Size getCapacity() const; 00379 00382 Size getSize() const; 00383 00386 Size size() const; 00387 00390 Iterator find(const Key& key); 00391 00394 ConstIterator find(const Key& key) const; 00395 00398 std::pair<Iterator, bool> insert(const ValueType& item); 00399 00403 Iterator insert(Iterator pos, const ValueType& item); 00404 00408 Size erase(const KeyType& key); 00409 00415 void erase(Iterator pos); 00416 00421 void erase(Iterator f, Iterator l); 00422 00424 00432 const HashSet& operator &= (const HashSet& rhs); 00433 00438 const HashSet& operator |= (const HashSet& rhs); 00439 00444 HashSet operator & (const HashSet& rhs) const; 00445 00450 HashSet operator | (const HashSet& rhs) const; 00451 00455 HashSet operator + (const HashSet& rhs) const; 00456 00462 HashSet operator - (const HashSet& rhs) const; 00463 00467 const HashSet& operator += (const HashSet& rhs); 00468 00472 const HashSet& operator -= (const HashSet& rhs); 00474 00478 00481 virtual void host(Visitor<HashSet<Key> >& visitor); 00483 00487 00490 bool has(const Key& key) const; 00491 00494 bool isEmpty() const; 00495 00498 bool operator == (const HashSet& hash_set) const; 00499 00502 bool operator != (const HashSet& hash_set) const; 00504 00508 00513 bool isValid() const; 00514 00517 virtual void dump(std::ostream& s = std::cout, Size depth = 0) const; 00518 00520 00521 // --- INTERNAL ITERATORS 00522 00529 bool apply(UnaryProcessor<ValueType>& processor); 00531 00532 00533 00536 Iterator begin() 00537 { 00538 return Iterator::begin(*this); 00539 } 00540 00543 Iterator end() 00544 { 00545 return Iterator::end(*this); 00546 } 00547 00550 ConstIterator begin() const 00551 { 00552 return ConstIterator::begin(*this); 00553 } 00554 00557 ConstIterator end() const 00558 { 00559 return ConstIterator::end(*this); 00560 } 00561 00562 00563 protected: 00564 00565 virtual Node* newNode_(const ValueType& value, Node* next) const; 00566 00567 virtual void deleteNode_(Node* node) const; 00568 00569 virtual HashIndex hash(const Key& key) const; 00570 00571 virtual bool needRehashing_() const; 00572 00573 virtual void rehash(); 00574 00575 private: 00576 00577 void deleteBuckets_(); 00578 00579 Position hashBucket_(const Key& key) const; 00580 00581 void rehash_(); 00582 00583 // --- ATTRIBUTES 00584 00585 /*_ The number of elements in the hash set 00586 */ 00587 Size size_; 00588 00589 /*_ The capacity - usually the number of buckets 00590 */ 00591 Size capacity_; 00592 00593 /*_ Buckets are stored as a vector of linked lists of Nodes 00594 */ 00595 vector<Node*> bucket_; 00596 }; 00597 00598 00599 template <class Key> 00600 HashSet<Key>::HashSet(Size initial_capacity, Size number_of_buckets) 00601 : size_(0), 00602 capacity_(initial_capacity), 00603 bucket_(number_of_buckets) 00604 { 00605 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket) 00606 { 00607 bucket_[bucket] = 0; 00608 } 00609 } 00610 00611 template <class Key> 00612 HashSet<Key>::HashSet(const HashSet& hash_set) 00613 : size_(hash_set.size_), 00614 capacity_(hash_set.capacity_), 00615 bucket_(hash_set.bucket_.size()) 00616 { 00617 Node* item = 0; 00618 00619 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket) 00620 { 00621 bucket_[bucket] = 0; 00622 00623 for (item = hash_set.bucket_[bucket]; item != 0; item = item->next) 00624 { 00625 bucket_[bucket] = newNode_(item->value, bucket_[bucket]); 00626 } 00627 } 00628 } 00629 00630 template <class Key> 00631 void HashSet<Key>::set(const HashSet& hash_set) 00632 { 00633 if (&hash_set == this) 00634 { 00635 return; 00636 } 00637 00638 destroy(); 00639 00640 deleteBuckets_(); 00641 00642 size_ = hash_set.size_; 00643 capacity_ = hash_set.capacity_; 00644 bucket_.resize(hash_set.bucket_.size()); 00645 00646 Node* item = 0; 00647 00648 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket) 00649 { 00650 bucket_[bucket] = 0; 00651 00652 for (item = hash_set.bucket_[bucket]; item != 0; item = item->next) 00653 { 00654 bucket_[bucket] = newNode_(item->value, bucket_[bucket]); 00655 } 00656 } 00657 } 00658 00659 template <class Key> 00660 void HashSet<Key>::clear() 00661 { 00662 Node* node = 0; 00663 Node* next_node = 0; 00664 00665 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket) 00666 { 00667 for (node = bucket_[bucket]; node != 0; node = next_node) 00668 { 00669 next_node = node->next; 00670 deleteNode_(node); 00671 } 00672 00673 bucket_[bucket] = 0; 00674 } 00675 00676 size_ = 0; 00677 } 00678 00679 template <class Key> 00680 BALL_INLINE 00681 void HashSet<Key>::destroy() 00682 { 00683 clear(); 00684 } 00685 00686 template <class Key> 00687 BALL_INLINE 00688 const HashSet<Key>& HashSet<Key>::operator = (const HashSet& hash_set) 00689 { 00690 set(hash_set); 00691 return *this; 00692 } 00693 00694 template <class Key> 00695 BALL_INLINE 00696 void HashSet<Key>::get(HashSet& hash_set) const 00697 00698 { 00699 hash_set.set(*this); 00700 } 00701 00702 template <class Key> 00703 BALL_INLINE 00704 void HashSet<Key>::swap(HashSet& hash_set) 00705 { 00706 std::swap(size_, hash_set.size_); 00707 std::swap(capacity_, hash_set.capacity_); 00708 std::swap(bucket_, hash_set.bucket_); 00709 } 00710 00711 template <class Key> 00712 BALL_INLINE 00713 const HashSet<Key>& HashSet<Key>::operator &= (const HashSet& rhs) 00714 { 00715 // Store all elements that are not part of the intersection 00716 // in a list for subsequent deletion. 00717 std::list<Key> erase_list; 00718 for (Iterator it = begin(); it != end(); ++it) 00719 { 00720 if (!rhs.has(*it)) 00721 { 00722 erase_list.push_back(*it); 00723 } 00724 } 00725 00726 // erase all elements not part of the intersection 00727 typename list<Key>::iterator list_it = erase_list.begin(); 00728 for (; list_it != erase_list.end(); ++list_it) 00729 { 00730 erase(*list_it); 00731 } 00732 00733 return *this; 00734 } 00735 00736 template <class Key> 00737 BALL_INLINE 00738 const HashSet<Key>& HashSet<Key>::operator |= (const HashSet<Key>& rhs) 00739 { 00740 // Compute the union of both sets by inserting every element of the 00741 // rhs set. 00742 for (ConstIterator it = rhs.begin(); it != rhs.end(); ++it) 00743 { 00744 insert(*it); 00745 } 00746 00747 return *this; 00748 } 00749 00750 template <class Key> 00751 BALL_INLINE 00752 const HashSet<Key>& HashSet<Key>::operator += (const HashSet<Key>& rhs) 00753 { 00754 return operator |= (rhs); 00755 } 00756 00757 template <class Key> 00758 BALL_INLINE 00759 HashSet<Key> HashSet<Key>::operator & (const HashSet<Key>& rhs) const 00760 { 00761 // Create an empty hash set... 00762 HashSet<Key> tmp; 00763 ConstIterator it = begin(); 00764 00765 // ...and copy all the elements contained in the rhs hash set. 00766 for (; +it; ++it) 00767 { 00768 if (rhs.has(*it)) 00769 { 00770 tmp.insert(*it); 00771 } 00772 } 00773 00774 return tmp; 00775 } 00776 00777 template <class Key> 00778 BALL_INLINE 00779 HashSet<Key> HashSet<Key>::operator - (const HashSet<Key>& rhs) const 00780 { 00781 // Create an empty hash set... 00782 HashSet<Key> tmp; 00783 ConstIterator it = begin(); 00784 00785 // ...and copy all the elements contained in this set and not in the rhs hash set. 00786 for (; +it; ++it) 00787 { 00788 if (!rhs.has(*it)) 00789 { 00790 tmp.insert(*it); 00791 } 00792 } 00793 00794 return tmp; 00795 } 00796 00797 template <class Key> 00798 BALL_INLINE 00799 const HashSet<Key>& HashSet<Key>::operator -= (const HashSet<Key>& hash_set) 00800 { 00801 // avoid memory corruption caused by iterating over freed space when 00802 // deleting myself 00803 if (this == &hash_set) 00804 { 00805 clear(); 00806 } 00807 else 00808 { 00809 // erase all elements which are contained in this and hash_set 00810 typename HashSet<Key>::ConstIterator it = hash_set.begin(); 00811 for (; it != hash_set.end(); ++it) 00812 { 00813 if (has(*it)) 00814 { 00815 erase(*it); 00816 } 00817 } 00818 } 00819 return *this; 00820 } 00821 00822 template <class Key> 00823 BALL_INLINE 00824 HashSet<Key> HashSet<Key>::operator | (const HashSet<Key>& rhs) const 00825 { 00826 HashSet<Key> tmp(*this); 00827 tmp |= rhs; 00828 00829 return tmp; 00830 } 00831 00832 template <class Key> 00833 BALL_INLINE 00834 HashSet<Key> HashSet<Key>::operator + (const HashSet<Key>& rhs) const 00835 { 00836 return operator | (rhs); 00837 } 00838 00839 template <class Key> 00840 BALL_INLINE 00841 Size HashSet<Key>::getBucketSize() const 00842 { 00843 return (Size)bucket_.size(); 00844 } 00845 00846 template <class Key> 00847 BALL_INLINE 00848 Size HashSet<Key>::getCapacity() const 00849 { 00850 return capacity_; 00851 } 00852 00853 template <class Key> 00854 BALL_INLINE 00855 Size HashSet<Key>::getSize() const 00856 { 00857 return size_; 00858 } 00859 00860 template <class Key> 00861 BALL_INLINE 00862 Size HashSet<Key>::size() const 00863 { 00864 return size_; 00865 } 00866 00867 template <class Key> 00868 typename HashSet<Key>::Iterator HashSet<Key>::find(const Key& key) 00869 { 00870 Iterator it = end(); 00871 Position bucket = hashBucket_(key); 00872 Node* node_ptr = bucket_[bucket]; 00873 while (node_ptr != 0) 00874 { 00875 if (node_ptr->value == key) 00876 { 00877 it.getTraits().position_ = node_ptr; 00878 it.getTraits().bucket_ = bucket; 00879 break; 00880 } 00881 node_ptr = node_ptr->next; 00882 } 00883 00884 return it; 00885 } 00886 00887 template <class Key> 00888 BALL_INLINE 00889 typename HashSet<Key>::ConstIterator HashSet<Key>::find(const Key& key) const 00890 { 00891 return (const_cast<HashSet*>(this))->find(key); 00892 } 00893 00894 template <class Key> 00895 std::pair<typename HashSet<Key>::Iterator, bool> HashSet<Key>::insert 00896 (const ValueType& item) 00897 { 00898 Iterator it = find(item); 00899 if (it == end()) 00900 { 00901 if (needRehashing_() == true) 00902 { 00903 rehash_(); 00904 } 00905 00906 Position bucket = hashBucket_(item); 00907 00908 Node* next = bucket_[bucket]; 00909 bucket_[bucket] = newNode_(item, next); 00910 00911 ++size_; 00912 it.getTraits().position_ = bucket_[bucket]; 00913 it.getTraits().bucket_ = bucket; 00914 } 00915 00916 return std::pair<Iterator, bool>(it, true); 00917 } 00918 00919 template <class Key> 00920 typename HashSet<Key>::Iterator HashSet<Key>::insert 00921 (typename HashSet<Key>::Iterator /* pos */, const ValueType& item) 00922 { 00923 return insert(item).first; 00924 } 00925 00926 template <class Key> 00927 Size HashSet<Key>::erase(const KeyType& key) 00928 { 00929 Position bucket = hashBucket_(key); 00930 Node* previous = 0; 00931 Node* node_ptr = bucket_[bucket]; 00932 00933 while (node_ptr != 0 && node_ptr->value != key) 00934 { 00935 previous = node_ptr; 00936 node_ptr = node_ptr->next; 00937 } 00938 00939 if (node_ptr == 0) 00940 { 00941 return false; 00942 } 00943 00944 if (node_ptr == bucket_[bucket]) 00945 { 00946 bucket_[bucket] = node_ptr->next; 00947 } 00948 else 00949 { 00950 previous->next = node_ptr->next; 00951 } 00952 00953 deleteNode_(node_ptr); 00954 --size_; 00955 00956 return 1; 00957 } 00958 00959 template <class Key> 00960 void HashSet<Key>::erase(Iterator pos) 00961 { 00962 if (pos.getTraits().bound_ != this) 00963 { 00964 throw Exception::IncompatibleIterators(__FILE__, __LINE__); 00965 } 00966 00967 if ((pos == end()) || (size_ == 0)) 00968 { 00969 return; 00970 } 00971 00972 if (pos.getTraits().position_ == bucket_[pos.getTraits().bucket_]) 00973 { 00974 bucket_[pos.getTraits().bucket_] = pos.getTraits().position_->next; 00975 } 00976 else 00977 { 00978 // walk over all nodes in this bucket and identify the predecessor 00979 // of the node refered to by the iterator pos 00980 Node* prev = bucket_[pos.getTraits().bucket_]; 00981 for (; (prev != 0) && (prev->next != pos.getTraits().position_); prev = prev->next) {}; 00982 if (prev != 0) 00983 { 00984 // remove the node and reconnect the list 00985 prev->next = pos.getTraits().position_->next; 00986 } 00987 else 00988 { 00989 throw Exception::InvalidIterator(__FILE__, __LINE__); 00990 } 00991 } 00992 00993 // delete the node and decrement the set size 00994 deleteNode_(pos.getTraits().position_); 00995 --size_; 00996 } 00997 00998 template <class Key> 00999 void HashSet<Key>::erase(Iterator f, Iterator l) 01000 { 01001 if (f.getTraits().bound_ != this || l.getTraits().bound_ != this) 01002 { 01003 throw Exception::IncompatibleIterators(__FILE__, __LINE__); 01004 } 01005 01006 if (f == end()) 01007 { 01008 return; 01009 } 01010 01011 Position last_bucket = l.getTraits().bucket_; 01012 if (l == end()) 01013 { 01014 last_bucket = (Position)(bucket_.size() - 1); 01015 } 01016 01017 if (f.getTraits().bucket_ > last_bucket) 01018 { 01019 // empty range - l < f 01020 return; 01021 } 01022 01023 // count the deleted entries to correct the set size 01024 Size no_deletions = 0; 01025 01026 Position bucket = f.getTraits().bucket_; 01027 for (; bucket <= last_bucket; bucket++) 01028 { 01029 if (bucket_[bucket] == 0) 01030 { 01031 // skip all empty buckets 01032 continue; 01033 } 01034 01035 01036 if ((bucket == f.getTraits().bucket_) && (bucket_[bucket] != f.getTraits().position_)) 01037 { 01038 // find the predecessor of f 01039 Node* n = bucket_[bucket]; 01040 Node* next; 01041 for (; (n->next != f.getTraits().position_) && (n->next != 0); n = n->next) {}; 01042 01043 if (bucket == last_bucket) 01044 { 01045 // delete everything from f to l in this bucket 01046 01047 next = n->next; 01048 n->next = l.getTraits().position_; 01049 for (n = next; (n != 0) && (n != l.getTraits().position_); n = next) 01050 { 01051 next = n->next; 01052 deleteNode_(n); 01053 no_deletions++; 01054 } 01055 } 01056 else 01057 { 01058 // delete everything from f to the end in this bucket 01059 01060 if (n != 0) 01061 { 01062 // mark the end of the list 01063 next = n->next; 01064 n->next = 0; 01065 01066 // delete all remaining nodes 01067 for (n = next; n != 0; n = next) 01068 { 01069 next = n->next; 01070 deleteNode_(n); 01071 no_deletions++; 01072 } 01073 } 01074 } 01075 } 01076 // if the current bucket lies between the first and the last bucket... 01077 else if (bucket < last_bucket) 01078 { 01079 // ...delete the whole bucket 01080 Node* next; 01081 for (Node* n = bucket_[bucket]; n != 0; n = next) 01082 { 01083 next = n->next; 01084 deleteNode_(n); 01085 no_deletions++; 01086 } 01087 bucket_[bucket] = 0; 01088 } 01089 else if (bucket == last_bucket) 01090 { 01091 // we delete everything in this bucket up to the iterator l 01092 01093 // find the predecessor of l 01094 Node* n = bucket_[bucket]; 01095 Node* next; 01096 for (; (n != 0) && (n != l.getTraits().position_); n = next) 01097 { 01098 next = n->next; 01099 deleteNode_(n); 01100 no_deletions++; 01101 } 01102 01103 bucket_[bucket] = l.getTraits().position_; 01104 } 01105 } 01106 01107 // correct the set size 01108 size_ -= no_deletions; 01109 } 01110 01111 template <class Key> 01112 BALL_INLINE 01113 void HashSet<Key>::host(Visitor<HashSet<Key> >& visitor) 01114 { 01115 visitor.visit(*this); 01116 } 01117 01118 template <class Key> 01119 BALL_INLINE 01120 bool HashSet<Key>::has(const Key& key) const 01121 { 01122 return (find(key) != end()); 01123 } 01124 01125 template <class Key> 01126 BALL_INLINE 01127 bool HashSet<Key>::isEmpty() const 01128 { 01129 return (size_ == 0); 01130 } 01131 01132 template <class Key> 01133 bool HashSet<Key>::operator == (const HashSet& hash_set) const 01134 { 01135 if (size_ != hash_set.size_) 01136 { 01137 return false; 01138 } 01139 01140 ConstIterator it1 = begin(); 01141 ConstIterator it2 = hash_set.begin(); 01142 while (it1 != end()) 01143 { 01144 if (*it1 != *it2) 01145 { 01146 return false; 01147 } 01148 it1++; 01149 it2++; 01150 } 01151 return true; 01152 } 01153 01154 template <class Key> 01155 BALL_INLINE 01156 bool HashSet<Key>::operator != (const HashSet& hash_set) const 01157 { 01158 return !(*this == hash_set); 01159 } 01160 01161 template <class Key> 01162 bool HashSet<Key>::isValid() const 01163 { 01164 Size size = 0; 01165 Node* node = 0; 01166 01167 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket) 01168 { 01169 for (node = bucket_[bucket]; node != 0; node = node->next) 01170 { 01171 ++size; 01172 01173 if (node->next == 0) 01174 { 01175 break; 01176 } 01177 } 01178 } 01179 01180 return (size_ == size); 01181 } 01182 01183 template <class Key> 01184 void HashSet<Key>::dump(std::ostream& s, Size depth) const 01185 { 01186 BALL_DUMP_STREAM_PREFIX(s); 01187 01188 BALL_DUMP_DEPTH(s, depth); 01189 01190 BALL_DUMP_DEPTH(s, depth); 01191 s << " size: " << getSize() << std::endl; 01192 01193 BALL_DUMP_DEPTH(s, depth); 01194 s << " # buckets: " << getBucketSize() << std::endl; 01195 01196 BALL_DUMP_DEPTH(s, depth); 01197 s << " capacity: " << getCapacity() << std::endl; 01198 01199 BALL_DUMP_DEPTH(s, depth); 01200 s << " load factor: " << (float)size_ / (float)bucket_.size() << std::endl; 01201 01202 for (Position bucket = 0; bucket < (Position)bucket_.size(); ++bucket) 01203 { 01204 BALL_DUMP_DEPTH(s, depth); 01205 s << " bucket " << bucket << ": "; 01206 for (Node* ptr = bucket_[bucket]; ptr != 0; ptr = ptr->next) 01207 { 01208 s << "(" << (void*)ptr << ") "; 01209 } 01210 s << "(0)" << std::endl; 01211 } 01212 01213 BALL_DUMP_STREAM_SUFFIX(s); 01214 } 01215 01216 template <class Key> 01217 bool HashSet<Key>::apply(UnaryProcessor<ValueType>& processor) 01218 { 01219 if (processor.start() == false) 01220 { 01221 return false; 01222 } 01223 01224 Processor::Result result; 01225 01226 Iterator it = begin(); 01227 while (it != end()) 01228 { 01229 result = processor(*it); 01230 if (result <= Processor::BREAK) 01231 { 01232 return (result == Processor::BREAK); 01233 } 01234 it++; 01235 } 01236 01237 return processor.finish(); 01238 } 01239 01240 template <class Key> 01241 BALL_INLINE 01242 HashIndex HashSet<Key>::hash(const Key& key) const 01243 { 01244 return (HashIndex)Hash(key); 01245 } 01246 01247 template <class Key> 01248 BALL_INLINE 01249 void HashSet<Key>::rehash() 01250 { 01251 capacity_ = (Size)getNextPrime((Size)bucket_.size() << 1); 01252 } 01253 01254 template <class Key> 01255 void HashSet<Key>::deleteBuckets_() 01256 { 01257 Size i = 0; 01258 Node* node = 0; 01259 Node* next_node = 0; 01260 for (i = 0; i < bucket_.size(); i++) 01261 { 01262 node = bucket_[i]; 01263 while (node != 0) 01264 { 01265 next_node = node->next; 01266 delete node; 01267 node = next_node; 01268 } 01269 bucket_[i] = 0; 01270 } 01271 } 01272 01273 template <class Key> 01274 BALL_INLINE 01275 typename HashSet<Key>::Node* HashSet<Key>::newNode_ 01276 (const ValueType& value, typename HashSet<Key>::Node* next) const 01277 { 01278 return new Node(value, next); 01279 } 01280 01281 template <class Key> 01282 BALL_INLINE 01283 void HashSet<Key>::deleteNode_(typename HashSet<Key>::Node* node) const 01284 { 01285 delete node; 01286 } 01287 01288 template <class Key> 01289 BALL_INLINE 01290 bool HashSet<Key>::needRehashing_() const 01291 { 01292 return (size_ >= capacity_); 01293 } 01294 01295 template <class Key> 01296 BALL_INLINE 01297 HashIndex HashSet<Key>::hashBucket_(const Key& key) const 01298 { 01299 return (Position)((HashIndex)hash(key) % (HashIndex)bucket_.size()); 01300 } 01301 01302 template <class Key> 01303 void HashSet<Key>::rehash_() 01304 { 01305 // calculate the new number of buckets (in capacity_) 01306 rehash(); 01307 01308 // save the old contents 01309 vector<Node*> old_buckets(bucket_); 01310 01311 // resize the bucket vector and initialize it with zero 01312 bucket_.clear(); 01313 bucket_.resize(capacity_); 01314 Position i; 01315 for (i = 0; i < capacity_; i++) 01316 { 01317 bucket_[i] = 0; 01318 } 01319 01320 // rehash the old contents into the new buckets 01321 Node* node; 01322 Node* next_node; 01323 for (Position i = 0; i < (Position)old_buckets.size(); ++i) 01324 { 01325 for (node = old_buckets[i]; node != 0; node = next_node) 01326 { 01327 next_node = node->next; 01328 Position new_bucket = hashBucket_(node->value); 01329 node->next = bucket_[new_bucket]; 01330 bucket_[new_bucket] = node; 01331 } 01332 } 01333 } 01334 } // namespace BALL 01335 01336 #endif // BALL_DATATYPE_HASHSET_H