BALL  1.4.1
hashSet.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines