Main Page   Groups   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Concepts

itk_hashtable.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itk_hashtable.h,v $
00005   Language:  C++
00006   Date:      $Date: 2005/04/28 16:02:42 $
00007   Version:   $Revision: 1.18 $
00008 
00009   Copyright (c) Insight Software Consortium. All rights reserved.
00010   See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
00011 
00012      This software is distributed WITHOUT ANY WARRANTY; without even 
00013      the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
00014      PURPOSE.  See the above copyright notices for more information.
00015 
00016 =========================================================================*/
00017 /*
00018  * Copyright (c) 1996
00019  * Silicon Graphics Computer Systems, Inc.
00020  *
00021  * Permission to use, copy, modify, distribute and sell this software
00022  * and its documentation for any purpose is hereby granted without fee,
00023  * provided that the above copyright notice appear in all copies and
00024  * that both that copyright notice and this permission notice appear
00025  * in supporting documentation.  Silicon Graphics makes no
00026  * representations about the suitability of this software for any
00027  * purpose.  It is provided "as is" without express or implied warranty.
00028  *
00029  *
00030  * Copyright (c) 1994
00031  * Hewlett-Packard Company
00032  *
00033  * Permission to use, copy, modify, distribute and sell this software
00034  * and its documentation for any purpose is hereby granted without fee,
00035  * provided that the above copyright notice appear in all copies and
00036  * that both that copyright notice and this permission notice appear
00037  * in supporting documentation.  Hewlett-Packard Company makes no
00038  * representations about the suitability of this software for any
00039  * purpose.  It is provided "as is" without express or implied warranty.
00040  *
00041  * Exception Handling:
00042  * Copyright (c) 1997
00043  * Mark of the Unicorn, Inc.
00044  *
00045  * Permission to use, copy, modify, distribute and sell this software
00046  * and its documentation for any purpose is hereby granted without fee,
00047  * provided that the above copyright notice appear in all copies and
00048  * that both that copyright notice and this permission notice appear
00049  * in supporting documentation.  Mark of the Unicorn makes no
00050  * representations about the suitability of this software for any
00051  * purpose.  It is provided "as is" without express or implied warranty.
00052  *
00053  * Adaptation:
00054  * Copyright (c) 1997
00055  * Moscow Center for SPARC Technology
00056  *
00057  * Permission to use, copy, modify, distribute and sell this software
00058  * and its documentation for any purpose is hereby granted without fee,
00059  * provided that the above copyright notice appear in all copies and
00060  * that both that copyright notice and this permission notice appear
00061  * in supporting documentation.  Moscow Center for SPARC Technology makes no
00062  * representations about the suitability of this software for any
00063  * purpose.  It is provided "as is" without express or implied warranty.
00064  *
00065  */
00066 
00067 
00068 #ifndef itk_emulation_hashtable_h
00069 #define itk_emulation_hashtable_h
00070 
00071 #if !defined(__GNUC__) || !((__GNUC__==3) && (__GNUC_MINOR__>=1) || (__GNUC__>3)) || defined(__INTEL_COMPILER)
00072 
00076 #include "itkMacro.h"
00077 #include <iostream>
00078 #include "itk_alloc.h"
00079 #include <vector>
00080 #include <utility>
00081 #include <memory>
00082 #include "vcl_compiler.h"
00083 #include <functional>
00084 #include <algorithm>
00085 #include <iterator>
00086 
00087 
00088 namespace itk
00089 {
00090 template <class Key> struct hash { };
00091 
00092 inline size_t hash_string(const char* s)
00093 {
00094   unsigned long h = 0; 
00095   for ( ; *s; ++s)
00096     h = 5*h + *s;
00097   
00098   return size_t(h);
00099 }
00100 
00101 template<>
00102 struct hash<char*>
00103 {
00104   size_t operator()(const char* s) const { return hash_string(s); }
00105 };
00106 
00107 template<>
00108 struct hash<const char*>
00109 {
00110   size_t operator()(const char* s) const { return hash_string(s); }
00111 };
00112 
00113 template<>
00114 struct hash<char> {
00115   size_t operator()(char x) const { return x; }
00116 };
00117 
00118 template<>
00119 struct hash<unsigned char> {
00120   size_t operator()(unsigned char x) const { return x; }
00121 };
00122 
00123 template<>
00124 struct hash<signed char> {
00125   size_t operator()(unsigned char x) const { return x; }
00126 };
00127 
00128 template<>
00129 struct hash<short> {
00130   size_t operator()(short x) const { return x; }
00131 };
00132 
00133 template<>
00134 struct hash<unsigned short> {
00135   size_t operator()(unsigned short x) const { return x; }
00136 };
00137 
00138 template<>
00139 struct hash<int> {
00140   size_t operator()(int x) const { return x; }
00141 };
00142 
00143 template<>
00144 struct hash<unsigned int> {
00145   size_t operator()(unsigned int x) const { return x; }
00146 };
00147 
00148 template<>
00149 struct hash<long> {
00150   size_t operator()(long x) const { return x; }
00151 };
00152 
00153 template<>
00154 struct hash<unsigned long> {
00155   size_t operator()(unsigned long x) const { return x; }
00156 };
00157 
00158 template <class Value>
00159 struct hashtable_node
00160 {
00161   typedef hashtable_node<Value> self;
00162   self* next;
00163   Value val;
00164 };  
00165 
00166 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey ,  VCL_DFL_TYPE_PARAM_STLDECL(Alloc,std::allocator<char>)>
00167 class hashtable;
00168 
00169 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00170 struct hashtable_iterator;
00171 
00172 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00173 struct hashtable_const_iterator;
00174 
00175 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00176 struct hashtable_iterator 
00177 {
00178   typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
00179           hash_table;
00180   typedef hashtable_iterator<Value, Key, HashFcn, 
00181                                ExtractKey, EqualKey, Alloc>
00182           iterator;
00183   typedef hashtable_const_iterator<Value, Key, HashFcn, 
00184                                      ExtractKey, EqualKey, Alloc>
00185           const_iterator;
00186   typedef hashtable_node<Value> node;
00187   typedef size_t size_type;
00188   typedef Value& reference;
00189   typedef const Value& const_reference;
00190 
00191   node* cur;
00192   hash_table* ht;
00193 
00194   hashtable_iterator(node* n, hash_table* tab) : cur(n), ht(tab) {}
00195   hashtable_iterator() {}
00196   reference operator*() const { 
00197         return cur->val; 
00198   }
00199   IUEi_STL_INLINE iterator& operator++();
00200   IUEi_STL_INLINE iterator operator++(int);
00201   bool operator==(const iterator& it) const { 
00202       return cur == it.cur; 
00203   }
00204   bool operator!=(const iterator& it) const { 
00205       return cur != it.cur; 
00206   }
00207 };
00208 
00209 
00210 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00211 struct hashtable_const_iterator 
00212 {
00213   typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
00214           hash_table;
00215   typedef hashtable_iterator<Value, Key, HashFcn, 
00216      ExtractKey, EqualKey, Alloc> iterator;
00217   typedef hashtable_const_iterator<Value, Key, HashFcn, 
00218      ExtractKey, EqualKey, Alloc> const_iterator;
00219   typedef hashtable_node<Value> node;
00220   typedef size_t size_type;
00221   typedef Value& reference;
00222   typedef const Value& const_reference;
00223 
00224   const node* cur;
00225   const hash_table* ht;
00226 
00227   hashtable_const_iterator(const node* n, const hash_table* tab) : cur(n), ht(tab) {}
00228   hashtable_const_iterator() {}
00229   hashtable_const_iterator(const iterator& it) : cur(it.cur), ht(it.ht) {}
00230 
00231   const_reference operator*() const { 
00232       return cur->val; 
00233   }
00234   IUEi_STL_INLINE const_iterator& operator++();
00235   IUEi_STL_INLINE const_iterator operator++(int);
00236   bool operator==(const const_iterator& it) const { 
00237       return cur == it.cur; 
00238   }
00239   bool operator!=(const const_iterator& it) const { 
00240       return cur != it.cur; 
00241   }
00242 };
00243 
00244 // Note: assumes long is at least 32 bits.
00245 // fbp: try to avoid intances in every module
00246 enum { num_primes = 28 };
00247 
00248 #if ( __STL_STATIC_TEMPLATE_DATA > 0 ) && ! defined (WIN32)
00249 #  define prime_list prime<false>::list_
00250    template <bool dummy>
00251    struct prime {
00252    public:
00253        static const unsigned long list_[];
00254    };
00255       static const unsigned long prime_list_dummy[num_primes] =
00256 #  else
00257 #  if ( __STL_WEAK_ATTRIBUTE > 0 )
00258       extern const unsigned long prime_list[num_primes] __attribute__((weak)) =
00259 #  else
00260       // give up
00261       static const unsigned long prime_list[num_primes] =
00262 #  endif /* __STL_WEAK_ATTRIBUTE */
00263 #endif /* __STL_STATIC_TEMPLATE_DATA */
00264 {
00265   53,         97,         193,       389,       769,
00266   1543,       3079,       6151,      12289,     24593,
00267   49157,      98317,      196613,    393241,    786433,
00268   1572869,    3145739,    6291469,   12582917,  25165843,
00269   50331653,   100663319,  201326611, 402653189, 805306457, 
00270   1610612741, 3221225473U, 4294967291U
00271 };
00272 
00273 inline unsigned long next_prime(unsigned long n)
00274 {
00275   const unsigned long* first = prime_list;
00276   const unsigned long* last = prime_list;
00277   last += num_primes;
00278   const unsigned long* pos = std::lower_bound(first, last, n);
00279   return pos == last ? *(last - 1) : *pos;
00280 }
00281 
00282 template <class Value, class Alloc>
00283 class hashtable_base 
00284 {
00285 private:
00286     typedef Value value_type;
00287     typedef size_t size_type;
00288     typedef hashtable_node<Value> node;
00289     typedef itk_simple_alloc<node, Alloc> node_allocator;
00290 public: // These are public to get around restriction on protected access
00291     typedef std::vector<VCL_SUNPRO_ALLOCATOR_HACK(node*) > buckets_type ;
00292     buckets_type buckets; // awf killed optional allocator
00293     size_type num_elements;
00294 protected:
00295     IUEi_STL_INLINE void clear();
00296 
00297     node* new_node(const value_type& obj)
00298   {
00299             node* n = node_allocator::allocate();
00300             try {
00301         new (&(n->val)) value_type(obj);
00302             }
00303             catch (...) {
00304         node_allocator::deallocate(n);
00305         throw "";
00306             }
00307             n->next = 0;
00308             return n;
00309   }
00310   
00311     void delete_node(node* n)
00312   {
00313 #define vcli_destroy(T, p)    ((T*)p)->~T()
00314             vcli_destroy(Value, &(n->val));
00315 #undef vcli_destroy
00316             node_allocator::deallocate(n);
00317   }
00318 
00319     IUEi_STL_INLINE void copy_from(const hashtable_base<Value,Alloc>& ht);
00320   
00321 public: // These are public to get around restriction on protected access
00322     hashtable_base() : num_elements(0) { }
00323 //    hashtable_base(size_type n) : num_elements(0) {}
00324     ~hashtable_base() { clear(); }
00325 };
00326 
00327 
00328 // forward declarations
00329 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> class hashtable;
00330 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00331   bool operator== (hashtable<Value,Key,HashFcn,ExtractKey,EqualKey,Alloc>const&,hashtable<Value,Key,HashFcn,ExtractKey,EqualKey,Alloc>const&);
00332 
00333 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00334 class hashtable : protected hashtable_base<Value, Alloc> 
00335 {
00336   typedef hashtable_base<Value, Alloc> super;
00337   typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> self;
00338 public:
00339   typedef Key key_type;
00340   typedef Value value_type;
00341   typedef HashFcn hasher;
00342   typedef EqualKey key_equal;
00343 
00344   typedef size_t            size_type;
00345   typedef ptrdiff_t         difference_type;
00346   typedef value_type*       pointer;
00347   typedef const value_type* const_pointer;
00348   typedef value_type&       reference;
00349   typedef const value_type& const_reference;
00350 
00351   hasher hash_funct() const { return hashfun; }
00352   key_equal key_eq() const { return equals; }
00353 
00354 private:
00355   hasher hashfun;
00356   key_equal equals;
00357   ExtractKey get_key;
00358 
00359   typedef hashtable_node<Value> node;
00360   typedef itk_simple_alloc<node, Alloc> node_allocator;
00361 
00362 public:
00363   typedef hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
00364   typedef hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,Alloc> const_iterator;
00365   friend struct
00366   hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
00367   friend struct
00368   hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
00369 
00370 public:
00371   hashtable(size_type n,
00372             const HashFcn&    hf,
00373             const EqualKey&   eql,
00374             const ExtractKey& ext)
00375       : hashfun(hf), equals(eql), get_key(ext) {
00376         initialize_buckets(n);
00377     }
00378 
00379   hashtable(size_type n,
00380             const HashFcn&    hf,
00381             const EqualKey&   eql)
00382       : hashfun(hf), equals(eql), get_key(ExtractKey()) {
00383         initialize_buckets(n);
00384     }
00385 
00386   hashtable(const self& ht)
00387     : hashfun(ht.hashfun), equals(ht.equals), get_key(ht.get_key) {
00388         copy_from(ht);
00389   }
00390 
00391   self& operator= (const self& ht)
00392   {
00393     if (&ht != this) {
00394       hashfun = ht.hashfun;
00395       equals = ht.equals;
00396       get_key = ht.get_key;
00397       clear();
00398       buckets.clear();
00399       copy_from(ht);
00400     }
00401     return *this;
00402   }
00403 
00404   ~hashtable() {}
00405 
00406   size_type size() const { return num_elements; }
00407   size_type max_size() const { return size_type(-1); }
00408   bool empty() const { return size() == 0; }
00409 
00410   void swap(self& ht)
00411   {
00412     std::swap(hashfun, ht.hashfun);
00413     std::swap(equals, ht.equals);
00414     std::swap(get_key, ht.get_key);
00415     buckets.swap(ht.buckets);
00416     std::swap(num_elements, ht.num_elements);
00417   }
00418 
00419   iterator begin()
00420   { 
00421     for (size_type n = 0; n < buckets.size(); ++n)
00422       if (buckets[n])
00423         return iterator(buckets[n], this);
00424     return end();
00425   }
00426 
00427   iterator end() { return iterator((node*)0, this); }
00428 
00429   const_iterator begin() const
00430   {
00431     for (size_type n = 0; n < buckets.size(); ++n)
00432       if (buckets[n])
00433         return const_iterator(buckets[n], this);
00434     return end();
00435   }
00436 
00437   const_iterator end() const { return const_iterator((node*)0, this); }
00438 
00439   //  friend IUEi_STL_INLINE bool operator== VCL_NULL_TMPL_ARGS (const
00440   //  self&,const self&);
00441   friend bool operator== VCL_NULL_TMPL_ARGS (const self&,const self&);
00442 public:
00443 
00444   size_type bucket_count() const { return buckets.size(); }
00445 
00446   size_type max_bucket_count() const
00447     { return prime_list[num_primes - 1]; } 
00448 
00449   size_type elems_in_bucket(size_type bucket) const
00450   {
00451     size_type result = 0;
00452     for (node* cur = buckets[bucket]; cur; cur = cur->next)
00453       result += 1;
00454     return result;
00455   }
00456 
00457   std::pair<iterator, bool> insert_unique(const value_type& obj)
00458   {
00459     resize(num_elements + 1);
00460     return insert_unique_noresize(obj);
00461   }
00462 
00463   iterator insert_equal(const value_type& obj)
00464   {
00465     resize(num_elements + 1);
00466     return insert_equal_noresize(obj);
00467   }
00468 
00469   IUEi_STL_INLINE std::pair<iterator, bool> insert_unique_noresize(const value_type& obj);
00470   IUEi_STL_INLINE iterator insert_equal_noresize(const value_type& obj);
00471  
00472   void insert_unique(const value_type* f, const value_type* l)
00473   {
00474     size_type n = l - f;
00475     resize(num_elements + n);
00476     for ( ; n > 0; --n)
00477       insert_unique_noresize(*f++);
00478   }
00479 
00480   void insert_equal(const value_type* f, const value_type* l)
00481   {
00482     size_type n = l - f;
00483     resize(num_elements + n);
00484     for ( ; n > 0; --n)
00485       insert_equal_noresize(*f++);
00486   }
00487 
00488  void insert_unique(const_iterator f, const_iterator l)
00489   {
00490     size_type n = 0;
00491     std::distance(f, l, n);
00492     resize(num_elements + n);
00493     for ( ; n > 0; --n)
00494       insert_unique_noresize(*f++);
00495   }
00496 
00497   void insert_equal(const_iterator f, const_iterator l)
00498   {
00499     size_type n = 0;
00500     std::distance(f, l, n);
00501     resize(num_elements + n);
00502     for ( ; n > 0; --n)
00503       insert_equal_noresize(*f++);
00504   }
00505 
00506   IUEi_STL_INLINE reference find_or_insert(const value_type& obj);
00507 
00508   iterator find(const key_type& key) 
00509   {
00510     size_type n = bkt_num_key(key);
00511     node* first;
00512     for ( first = buckets[n];
00513           first && !equals(get_key(first->val), key);
00514           first = first->next)
00515       {}
00516     return iterator(first, this);
00517   } 
00518 
00519   const_iterator find(const key_type& key) const
00520   {
00521     size_type n = bkt_num_key(key);
00522     const node* first;
00523     for ( first = buckets[n];
00524           first && !equals(get_key(first->val), key);
00525           first = first->next)
00526       {}
00527     return const_iterator(first, this);
00528   } 
00529 
00530   size_type count(const key_type& key) const
00531   {
00532     const size_type n = bkt_num_key(key);
00533     size_type result = 0;
00534 
00535     for (const node* cur = buckets[n]; cur; cur = cur->next)
00536       if (equals(get_key(cur->val), key))
00537         ++result;
00538     return result;
00539   }
00540 
00541   IUEi_STL_INLINE std::pair<iterator, iterator> equal_range(const key_type& key);
00542   IUEi_STL_INLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const;
00543 
00544   IUEi_STL_INLINE size_type erase(const key_type& key);
00545   IUEi_STL_INLINE void erase(const iterator& it);
00546   IUEi_STL_INLINE void erase(iterator first, iterator last);
00547 
00548   IUEi_STL_INLINE void erase(const const_iterator& it);
00549   IUEi_STL_INLINE void erase(const_iterator first, const_iterator last);
00550 
00551   IUEi_STL_INLINE void resize(size_type num_elements_hint);
00552   void clear() { super::clear(); }
00553 private:
00554     size_type next_size(size_type n) const { 
00555        return static_cast<size_type>( 
00556           next_prime( static_cast<unsigned long>(n) ) ); }
00557 
00558     void initialize_buckets(size_type n)
00559     {
00560         const size_type n_buckets = next_size(n);
00561         buckets.reserve(n_buckets);
00562         buckets.insert(buckets.end(), n_buckets, (node*) 0);
00563         num_elements = 0;
00564     }
00565     size_type bkt_num_key(const key_type& key) const{
00566         return bkt_num_key(key, buckets.size());
00567     }
00568 
00569     size_type bkt_num(const value_type& obj) const {
00570         return bkt_num_key(get_key(obj));
00571     }
00572 
00573     size_type bkt_num_key(const key_type& key, size_t n) const {
00574         return hashfun(key) % n;
00575     }
00576 
00577     size_type bkt_num(const value_type& obj, size_t n) const {
00578         return bkt_num_key(get_key(obj), n);
00579     }
00580     IUEi_STL_INLINE void erase_bucket(const size_type n, node* first, node* last);
00581     IUEi_STL_INLINE void erase_bucket(const size_type n, node* last);
00582 };
00583 
00584 // fbp: these defines are for outline methods definitions.
00585 // needed to definitions to be portable. Should not be used in method bodies.
00586 
00587 # if defined ( __STL_NESTED_TYPE_PARAM_BUG )
00588 #  define __difference_type__ ptrdiff_t
00589 #  define __size_type__       size_t
00590 #  define __value_type__      Value
00591 #  define __key_type__        Key
00592 #  define __node__            hashtable_node<Value>
00593 #  define __reference__       Value&
00594 # else
00595 #  define __difference_type__  typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::difference_type
00596 #  define __size_type__        typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::size_type
00597 #  define __value_type__       typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::value_type
00598 #  define __key_type__         typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::key_type
00599 #  define __node__             typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::node
00600 #  define __reference__        typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::reference
00601 # endif
00602 
00603 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00604 inline hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&
00605 hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++()
00606 {
00607   const node* old = cur;
00608   cur = cur->next;
00609   if (!cur) {
00610     size_type bucket = ht->bkt_num(old->val);
00611     while (!cur && ++bucket < ht->buckets.size())
00612       cur = ht->buckets[bucket];
00613   }
00614   return *this;
00615 }
00616 
00617 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00618 inline hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
00619 hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++(int)
00620 {
00621   iterator tmp = *this;
00622   ++*this;
00623   return tmp;
00624 }
00625 
00626 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00627 inline hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&
00628 hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++()
00629 {
00630   const node* old = cur;
00631   cur = cur->next;
00632   if (!cur) {
00633     size_type bucket = ht->bkt_num(old->val);
00634     while (!cur && ++bucket < ht->buckets.size())
00635       cur = ht->buckets[bucket];
00636   }
00637   return *this;
00638 }
00639 
00640 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00641 inline hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
00642 hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++(int)
00643 {
00644   const_iterator tmp = *this;
00645   ++*this;
00646   return tmp;
00647 }
00648 
00649 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00650 inline std::forward_iterator_tag
00651 iterator_category (const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00652 {
00653   return std::forward_iterator_tag();
00654 }
00655 
00656 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00657 inline Value* 
00658 value_type(const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00659 {
00660   return (Value*) 0;
00661 }
00662 
00663 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00664 inline ptrdiff_t*
00665 distance_type(const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00666 {
00667   return (ptrdiff_t*) 0;
00668 }
00669 
00670 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00671 inline std::forward_iterator_tag
00672 iterator_category (const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00673 {
00674   return std::forward_iterator_tag();
00675 }
00676 
00677 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00678 inline Value* 
00679 value_type(const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00680 {
00681   return (Value*) 0;
00682 }
00683 
00684 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00685 inline ptrdiff_t*
00686 distance_type(const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00687 {
00688   return (ptrdiff_t*) 0;
00689 }
00690 
00691 
00692 
00693 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00694 IUEi_STL_INLINE 
00695 bool operator==(const hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& ht1,
00696                 const hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& ht2)
00697 {
00698   typedef typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::node node;
00699   if (ht1.buckets.size() != ht2.buckets.size())
00700     return false;
00701   for (int n = 0; n < ht1.buckets.size(); ++n) {
00702     node* cur1 = ht1.buckets[n];
00703     node* cur2 = ht2.buckets[n];
00704     for ( ; cur1 && cur2 && cur1->val == cur2->val;
00705           cur1 = cur1->next, cur2 = cur2->next)
00706       {}
00707     if (cur1 || cur2)
00708       return false;
00709   }
00710   return true;
00711 }  
00712 
00713 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00714 std::pair<hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>, bool> 
00715 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::insert_unique_noresize(const __value_type__& obj)
00716 {
00717   const size_type n = bkt_num(obj);
00718   node* first = buckets[n];
00719 
00720   for (node* cur = first; cur; cur = cur->next) 
00721     if (equals(get_key(cur->val), get_key(obj)))
00722       return std::pair<iterator, bool>(iterator(cur, this), false);
00723 
00724   node* tmp = new_node(obj);
00725   tmp->next = first;
00726   buckets[n] = tmp;
00727   ++num_elements;
00728   return std::pair<iterator, bool>(iterator(tmp, this), true);
00729 }
00730 
00731 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00732 hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> 
00733 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::insert_equal_noresize(const __value_type__& obj)
00734 {
00735   const size_type n = bkt_num(obj);
00736   node* first = buckets[n];
00737 
00738   for (node* cur = first; cur; cur = cur->next) 
00739     if (equals(get_key(cur->val), get_key(obj))) {
00740       node* tmp = new_node(obj);
00741       tmp->next = cur->next;
00742       cur->next = tmp;
00743       ++num_elements;
00744       return iterator(tmp, this);
00745     }
00746 
00747   node* tmp = new_node(obj);
00748   tmp->next = first;
00749   buckets[n] = tmp;
00750   ++num_elements;
00751   return iterator(tmp, this);
00752 }
00753 
00754 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00755 __reference__ 
00756 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::find_or_insert(const __value_type__& obj)
00757 {
00758   resize(num_elements + 1);
00759 
00760   size_type n = bkt_num(obj);
00761   node* first = buckets[n];
00762 
00763   for (node* cur = first; cur; cur = cur->next)
00764     if (equals(get_key(cur->val), get_key(obj)))
00765       return cur->val;
00766 
00767   node* tmp = new_node(obj);
00768   tmp->next = first;
00769   buckets[n] = tmp;
00770   ++num_elements;
00771   return tmp->val;
00772 }
00773 
00774 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00775 std::pair<hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>,
00776      hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> > 
00777 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::equal_range(const __key_type__& key)
00778 {
00779   typedef std::pair<iterator, iterator> pii;
00780   const size_type n = bkt_num_key(key);
00781 
00782   for (node* first = buckets[n]; first; first = first->next) {
00783     if (equals(get_key(first->val), key)) {
00784       for (node* cur = first->next; cur; cur = cur->next)
00785         if (!equals(get_key(cur->val), key))
00786           return pii(iterator(first, this), iterator(cur, this));
00787       for (size_type m = n + 1; m < buckets.size(); ++m)
00788         if (buckets[m])
00789           return pii(iterator(first, this),
00790                      iterator(buckets[m], this));
00791       return pii(iterator(first, this), end());
00792     }
00793   }
00794   return pii(end(), end());
00795 }
00796 
00797 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00798 std::pair<hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>, 
00799      hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> > 
00800 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::equal_range(const __key_type__& key) const
00801 {
00802   typedef std::pair<const_iterator, const_iterator> pii;
00803   const size_type n = bkt_num_key(key);
00804 
00805   for (const node* first = buckets[n] ; first; first = first->next) {
00806     if (equals(get_key(first->val), key)) {
00807       for (const node* cur = first->next; cur; cur = cur->next)
00808         if (!equals(get_key(cur->val), key))
00809           return pii(const_iterator(first, this),
00810                      const_iterator(cur, this));
00811       for (size_type m = n + 1; m < buckets.size(); ++m)
00812         if (buckets[m])
00813           return pii(const_iterator(first, this),
00814                      const_iterator(buckets[m], this));
00815       return pii(const_iterator(first, this), end());
00816     }
00817   }
00818   return pii(end(), end());
00819 }
00820 
00821 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00822 __size_type__ 
00823 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const __key_type__& key)
00824 {
00825   const size_type n = bkt_num_key(key);
00826   node* first = buckets[n];
00827   size_type erased = 0;
00828 
00829   if (first) {
00830     node* cur = first;
00831     node* next = cur->next;
00832     while (next) {
00833       if (equals(get_key(next->val), key)) {
00834         cur->next = next->next;
00835         delete_node(next);
00836         next = cur->next;
00837         ++erased;
00838       }
00839       else {
00840         cur = next;
00841         next = cur->next;
00842       }
00843     }
00844     if (equals(get_key(first->val), key)) {
00845       buckets[n] = first->next;
00846       delete_node(first);
00847       ++erased;
00848     }
00849   }
00850   num_elements -= erased;
00851   return erased;
00852 }
00853 
00854 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00855 void 
00856 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& it)
00857 {
00858   node* const p = it.cur;
00859   if (p) {
00860     const size_type n = bkt_num(p->val);
00861     node* cur = buckets[n];
00862 
00863     if (cur == p) {
00864       buckets[n] = cur->next;
00865       delete_node(cur);
00866       --num_elements;
00867     }
00868     else {
00869       node* next = cur->next;
00870       while (next) {
00871         if (next == p) {
00872           cur->next = next->next;
00873           delete_node(next);
00874           --num_elements;
00875           break;
00876         }
00877         else {
00878           cur = next;
00879           next = cur->next;
00880         }
00881       }
00882     }
00883   }
00884 }
00885 
00886 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00887 void 
00888 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> first, 
00889                                         hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> last)
00890 {
00891   size_type f_bucket = first.cur ? bkt_num(first.cur->val) : buckets.size();
00892   size_type l_bucket = last.cur ? bkt_num(last.cur->val) : buckets.size();
00893   if (first.cur == last.cur)
00894     return;
00895   else if (f_bucket == l_bucket)
00896     erase_bucket(f_bucket, first.cur, last.cur);
00897   else {
00898     erase_bucket(f_bucket, first.cur, 0);
00899     for (size_type n = f_bucket + 1; n < l_bucket; ++n)
00900       erase_bucket(n, 0);
00901     if (l_bucket != buckets.size())
00902       erase_bucket(l_bucket, last.cur);
00903   }
00904 }
00905 
00906 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00907 inline void
00908 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> first, 
00909                                         hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> last)
00910 {
00911   erase(iterator(const_cast<node*>(first.cur),
00912                  const_cast<self*>(first.ht)),
00913         iterator(const_cast<node*>(last.cur),
00914                  const_cast<self*>(last.ht)));
00915 }
00916 
00917 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00918 inline void
00919 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& it)
00920 {
00921   erase(iterator(const_cast<node*>(it.cur),
00922                  const_cast<self*>(it.ht)));
00923 }
00924 
00925 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00926 void 
00927 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::resize(__size_type__ num_elements_hint)
00928 {
00929     const size_type old_n = buckets.size();
00930     if (num_elements_hint > old_n) {
00931         const size_type n = next_size(num_elements_hint);
00932         if (n > old_n) {
00933       hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::buckets_type tmp(n, (node*)0);
00934             for (size_type bucket = 0; bucket < old_n; ++bucket) {
00935                 node* first = buckets[bucket];
00936                 while (first) {
00937                     size_type new_bucket = bkt_num(first->val, n);
00938                     buckets[bucket] = first->next;
00939                     first->next = tmp[new_bucket];
00940                     tmp[new_bucket] = first;
00941                     first = buckets[bucket];          
00942                 }
00943             }
00944             buckets.clear();
00945             buckets.swap(tmp);
00946         }
00947     }
00948 }
00949 
00950 
00951 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00952 void 
00953 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase_bucket(const size_t n, 
00954                                              hashtable_node<Value>* first, 
00955                                              hashtable_node<Value>* last)
00956 {
00957   node* cur = buckets[n];
00958   if (cur == first)
00959     erase_bucket(n, last);
00960   else {
00961     node* next;
00962     for (next = cur->next; next != first; cur = next, next = cur->next)
00963       ;
00964     while (next) {
00965       cur->next = next->next;
00966       delete_node(next);
00967       next = cur->next;
00968       --num_elements;
00969     }
00970   }
00971 }
00972 
00973 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00974 void 
00975 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase_bucket(const size_t n,
00976                                                             hashtable_node<Value>* last)
00977 {
00978   node* cur = buckets[n];
00979   while (cur != last) {
00980     node* next = cur->next;
00981     delete_node(cur);
00982     cur = next;
00983     buckets[n] = cur;
00984     --num_elements;
00985   }
00986 }
00987 
00988 template <class Value, class Alloc>
00989 void hashtable_base<Value, Alloc>::clear()
00990 {
00991   for (size_type i = 0; i < buckets.size(); ++i) {
00992     node* cur = buckets[i];
00993     while (cur != 0) {
00994       node* next = cur->next;
00995       delete_node(cur);
00996       cur = next;
00997     }
00998     buckets[i] = 0;
00999   }
01000   num_elements = 0;
01001 }
01002   
01003   
01004 template <class Value, class Alloc>
01005 void hashtable_base<Value, Alloc>::copy_from(const hashtable_base<Value, Alloc>& ht)
01006 {
01007   buckets.reserve(ht.buckets.size());
01008   buckets.insert(buckets.end(), ht.buckets.size(), (node*) 0);
01009   for (size_type i = 0; i < ht.buckets.size(); ++i) {
01010     const node* cur = ht.buckets[i];
01011     if (cur) {
01012       node* copy = new_node(cur->val);
01013       buckets[i] = copy;
01014       ++num_elements;
01015       
01016       for (node* next = cur->next; next; cur = next, next = cur->next) {
01017         copy->next = new_node(next->val);
01018         ++num_elements;
01019         copy = copy->next;
01020       }
01021     }
01022   }
01023 }
01024 
01025 }// end namespace itk
01026 
01027 
01028 # undef __difference_type__ 
01029 # undef __size_type__       
01030 # undef __value_type__      
01031 # undef __key_type__        
01032 # undef __node__            
01033 
01034 // the following is added for itk compatability:
01035 
01036 // --
01037 
01038 // A few compatability fixes.  Placed here for automatic include in
01039 // both the hash_set and the hash_map sources.
01040 # if defined(VCL_SUNPRO_CC) || defined (_MSC_VER) || defined(__BORLANDC__) || ((defined(__ICC)||defined(__ECC)) && defined(linux))
01041 namespace std 
01042 {
01043 template <class T>
01044 struct identity : public std::unary_function<T, T> {
01045 public:
01046   const T& operator()(const T& x) const { return x; }
01047 };
01048 }
01049 
01050 template <class _Pair>
01051 struct itk_Select1st : public std::unary_function<_Pair, typename _Pair::first_type> {
01052   typename _Pair::first_type const & operator()(_Pair const & __x) const {
01053     return __x.first;
01054   }
01055 };
01056  
01057 template <class _Pair>
01058 struct itk_Select2nd : public std::unary_function<_Pair, typename _Pair::second_type> {
01059   typename _Pair::second_type const & operator()(_Pair const & __x) const {
01060     return __x.second;
01061   }
01062 };
01063 
01064 // Add select* to std.
01065 namespace std {
01066   template <class _Pair>
01067   struct select1st : public itk_Select1st<_Pair> { };
01068   template <class _Pair> struct select2nd : public itk_Select2nd<_Pair> { };
01069 };
01070 
01071 #endif
01072 
01073 #endif
01074 
01075 #endif // itk_emulation_hashtable_h

Generated at Wed May 24 22:44:54 2006 for ITK by doxygen 1.3.5 written by Dimitri van Heesch, © 1997-2000