unordered_set.h

00001 ///\file
00002 
00003 /******************************************************************************
00004 The MIT License(MIT)
00005 
00006 Embedded Template Library.
00007 https://github.com/ETLCPP/etl
00008 http://www.etlcpp.com
00009 
00010 Copyright(c) 2016 jwellbelove
00011 
00012 Permission is hereby granted, free of charge, to any person obtaining a copy
00013 of this software and associated documentation files(the "Software"), to deal
00014 in the Software without restriction, including without limitation the rights
00015 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
00016 copies of the Software, and to permit persons to whom the Software is
00017 furnished to do so, subject to the following conditions :
00018 
00019 The above copyright notice and this permission notice shall be included in all
00020 copies or substantial portions of the Software.
00021 
00022 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00023 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00024 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
00025 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00026 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00027 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
00028 SOFTWARE.
00029 ******************************************************************************/
00030 
00031 #ifndef __ETL_UNORDERED_SET__
00032 #define __ETL_UNORDERED_SET__
00033 
00034 #include <stddef.h>
00035 #include <iterator>
00036 #include <functional>
00037 #include <algorithm>
00038 #include <functional>
00039 #include <utility>
00040 
00041 #include "platform.h "
00042 #include "container.h "
00043 #include "pool.h "
00044 #include "vector.h "
00045 #include "intrusive_forward_list.h "
00046 #include "hash.h "
00047 #include "type_traits.h "
00048 #include "parameter_type.h "
00049 #include "nullptr.h "
00050 #include "error_handler.h "
00051 #include "exception.h "
00052 #include "error_handler.h "
00053 #include "debug_count.h "
00054 
00055 #undef ETL_FILE
00056 #define ETL_FILE "23"
00057 
00058 //*****************************************************************************
00059 ///\defgroup unordered_set unordered_set
00060 /// A unordered_set with the capacity defined at compile time.
00061 ///\ingroup containers
00062 //*****************************************************************************
00063 
00064 namespace etl
00065 {
00066   //***************************************************************************
00067   /// Exception for the unordered_set.
00068   ///\ingroup unordered_set
00069   //***************************************************************************
00070   class unordered_set_exception : public etl::exception
00071   {
00072   public:
00073 
00074     unordered_set_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00075       : etl::exception(reason_, file_name_, line_number_)
00076     {
00077     }
00078   };
00079 
00080   //***************************************************************************
00081   /// Full exception for the unordered_set.
00082   ///\ingroup unordered_set
00083   //***************************************************************************
00084   class unordered_set_full : public etl::unordered_set_exception
00085   {
00086   public:
00087 
00088     unordered_set_full(string_type file_name_, numeric_type line_number_)
00089       : etl::unordered_set_exception(ETL_ERROR_TEXT("unordered_set:full", ETL_FILE"A"), file_name_, line_number_)
00090     {
00091     }
00092   };
00093 
00094   //***************************************************************************
00095   /// Out of range exception for the unordered_set.
00096   ///\ingroup unordered_set
00097   //***************************************************************************
00098   class unordered_set_out_of_range : public etl::unordered_set_exception
00099   {
00100   public:
00101 
00102     unordered_set_out_of_range(string_type file_name_, numeric_type line_number_)
00103       : etl::unordered_set_exception(ETL_ERROR_TEXT("unordered_set:range", ETL_FILE"B"), file_name_, line_number_)
00104     {}
00105   };
00106 
00107   //***************************************************************************
00108   /// Iterator exception for the unordered_set.
00109   ///\ingroup unordered_set
00110   //***************************************************************************
00111   class unordered_set_iterator : public etl::unordered_set_exception
00112   {
00113   public:
00114 
00115     unordered_set_iterator(string_type file_name_, numeric_type line_number_)
00116       : etl::unordered_set_exception(ETL_ERROR_TEXT("unordered_set:iterator", ETL_FILE"C"), file_name_, line_number_)
00117     {
00118     }
00119   };
00120 
00121   //***************************************************************************
00122   /// The base class for specifically sized unordered_set.
00123   /// Can be used as a reference type for all unordered_set containing a specific type.
00124   ///\ingroup unordered_set
00125   //***************************************************************************
00126   template <typename TKey, typename THash = etl::hash<TKey>, typename TKeyEqual = std::equal_to<TKey> >
00127   class iunordered_set
00128   {
00129   public:
00130 
00131     typedef TKey              value_type;
00132     typedef TKey              key_type;
00133     typedef THash             hasher;
00134     typedef TKeyEqual         key_equal;
00135     typedef value_type&       reference;
00136     typedef const value_type& const_reference;
00137     typedef value_type*       pointer;
00138     typedef const value_type* const_pointer;
00139     typedef size_t            size_type;
00140 
00141     typedef typename etl::parameter_type<TKey>::type key_parameter_t;
00142 
00143     typedef etl::forward_link<0>  link_t ;
00144 
00145     // The nodes that store the elements.
00146     struct node_t : public link_t 
00147     {
00148       node_t(const value_type& key_)
00149         : key(key_)
00150       {
00151       }
00152 
00153       value_type key;
00154     };
00155 
00156   private:
00157 
00158     typedef etl::intrusive_forward_list<node_t, link_t> bucket_t;
00159     typedef etl::ipool pool_t;
00160 
00161   public:
00162 
00163     // Local iterators iterate over one bucket.
00164     typedef typename bucket_t::iterator       local_iterator;
00165     typedef typename bucket_t::const_iterator local_const_iterator;
00166 
00167     //*********************************************************************
00168     class iterator : public std::iterator<std::forward_iterator_tag, TKey>
00169     {
00170     public:
00171 
00172       typedef typename iunordered_set::value_type      value_type;
00173       typedef typename iunordered_set::key_type        key_type;
00174       typedef typename iunordered_set::hasher          hasher;
00175       typedef typename iunordered_set::key_equal       key_equal;
00176       typedef typename iunordered_set::reference       reference;
00177       typedef typename iunordered_set::const_reference const_reference;
00178       typedef typename iunordered_set::pointer         pointer;
00179       typedef typename iunordered_set::const_pointer   const_pointer;
00180       typedef typename iunordered_set::size_type       size_type;
00181 
00182       friend class iunordered_set;
00183 
00184       //*********************************
00185       iterator()
00186       {
00187       }
00188 
00189       //*********************************
00190       iterator(const iterator& other)
00191         : pbuckets_end(other.pbuckets_end),
00192         pbucket(other.pbucket),
00193         inode(other.inode)
00194       {
00195       }
00196 
00197       //*********************************
00198       iterator& operator ++()
00199       {
00200         ++inode;
00201 
00202         // The end of this node list?
00203         if (inode == pbucket->end())
00204         {
00205           // Search for the next non-empty bucket.
00206           ++pbucket;
00207           while ((pbucket != pbuckets_end) && (pbucket->empty()))
00208           {
00209             ++pbucket;
00210           }
00211 
00212           // If not past the end, get the first node in the bucket.
00213           if (pbucket != pbuckets_end)
00214           {
00215             inode = pbucket->begin();
00216           }
00217         }
00218 
00219         return *this;
00220       }
00221 
00222       //*********************************
00223       iterator operator ++(int)
00224       {
00225         iterator temp(*this);
00226         operator++();
00227         return temp;
00228       }
00229 
00230       //*********************************
00231       iterator operator =(const iterator& other)
00232       {
00233         pbuckets_end = other.pbuckets_end;
00234         pbucket = other.pbucket;
00235         inode = other.inode;
00236         return *this;
00237       }
00238 
00239       //*********************************
00240       reference operator *()
00241       {
00242         return inode->key;
00243       }
00244 
00245       //*********************************
00246       const_reference operator *() const
00247       {
00248         return inode->key;
00249       }
00250 
00251       //*********************************
00252       pointer operator &()
00253       {
00254         return &(inode->key);
00255       }
00256 
00257       //*********************************
00258       const_pointer operator &() const
00259       {
00260         return &(inode->key);
00261       }
00262 
00263       //*********************************
00264       pointer operator ->()
00265       {
00266         return &(inode->key);
00267       }
00268 
00269       //*********************************
00270       const_pointer operator ->() const
00271       {
00272         return &(inode->key);
00273       }
00274 
00275       //*********************************
00276       friend bool operator == (const iterator& lhs, const iterator& rhs)
00277       {
00278         return lhs.compare(rhs);
00279       }
00280 
00281       //*********************************
00282       friend bool operator != (const iterator& lhs, const iterator& rhs)
00283       {
00284         return !(lhs == rhs);
00285       }
00286 
00287     private:
00288 
00289       //*********************************
00290       iterator(bucket_t* pbuckets_end_, bucket_t* pbucket_, local_iterator inode_)
00291         : pbuckets_end(pbuckets_end_),
00292           pbucket(pbucket_),
00293           inode(inode_)
00294       {
00295       }
00296 
00297       //*********************************
00298       bool compare(const iterator& rhs) const
00299       {
00300         return rhs.inode == inode;
00301       }
00302 
00303       //*********************************
00304       bucket_t& get_bucket()
00305       {
00306         return *pbucket;
00307       }
00308 
00309       //*********************************
00310       bucket_t*& get_bucket_list_iterator()
00311       {
00312         return pbucket;
00313       }
00314 
00315       //*********************************
00316       local_iterator get_local_iterator()
00317       {
00318         return inode;
00319       }
00320 
00321       bucket_t* pbuckets_end;
00322       bucket_t* pbucket;
00323       local_iterator       inode;
00324     };
00325 
00326     //*********************************************************************
00327     class const_iterator : public std::iterator<std::forward_iterator_tag, const TKey>
00328     {
00329     public:
00330 
00331       typedef typename iunordered_set::value_type      value_type;
00332       typedef typename iunordered_set::key_type        key_type;
00333       typedef typename iunordered_set::hasher          hasher;
00334       typedef typename iunordered_set::key_equal       key_equal;
00335       typedef typename iunordered_set::reference       reference;
00336       typedef typename iunordered_set::const_reference const_reference;
00337       typedef typename iunordered_set::pointer         pointer;
00338       typedef typename iunordered_set::const_pointer   const_pointer;
00339       typedef typename iunordered_set::size_type       size_type;
00340 
00341       friend class iunordered_set;
00342       friend class iterator;
00343 
00344       //*********************************
00345       const_iterator()
00346       {
00347       }
00348 
00349       //*********************************
00350       const_iterator(const typename iunordered_set::iterator& other)
00351         : pbuckets_end(other.pbuckets_end),
00352         pbucket(other.pbucket),
00353         inode(other.inode)
00354       {
00355       }
00356 
00357       //*********************************
00358       const_iterator(const const_iterator& other)
00359         : pbuckets_end(other.pbuckets_end),
00360         pbucket(other.pbucket),
00361         inode(other.inode)
00362       {
00363       }
00364 
00365       //*********************************
00366       const_iterator& operator ++()
00367       {
00368         ++inode;
00369 
00370         // The end of this node list?
00371         if (inode == pbucket->end())
00372         {
00373           // Search for the next non-empty bucket.
00374 
00375           ++pbucket;
00376           while ((pbucket != pbuckets_end) && (pbucket->empty()))
00377           {
00378             ++pbucket;
00379           }
00380 
00381           // If not past the end, get the first node in the bucket.
00382           if (pbucket != pbuckets_end)
00383           {
00384             inode = pbucket->begin();
00385           }
00386         }
00387 
00388         return *this;
00389       }
00390 
00391       //*********************************
00392       const_iterator operator ++(int)
00393       {
00394         const_iterator temp(*this);
00395         operator++();
00396         return temp;
00397       }
00398 
00399       //*********************************
00400       const_iterator operator =(const const_iterator& other)
00401       {
00402         pbuckets_end = other.pbuckets_end;
00403         pbucket = other.pbucket;
00404         inode = other.inode;
00405         return *this;
00406       }
00407 
00408       //*********************************
00409       const_reference operator *() const
00410       {
00411         return inode->key;
00412       }
00413 
00414       //*********************************
00415       const_pointer operator &() const
00416       {
00417         return &(inode->key);
00418       }
00419 
00420       //*********************************
00421       const_pointer operator ->() const
00422       {
00423         return &(inode->key);
00424       }
00425 
00426       //*********************************
00427       friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
00428       {
00429         return lhs.compare(rhs);
00430       }
00431 
00432       //*********************************
00433       friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
00434       {
00435         return !(lhs == rhs);
00436       }
00437 
00438     private:
00439 
00440       //*********************************
00441       const_iterator(bucket_t* pbuckets_end_, bucket_t* pbucket_, local_iterator inode_)
00442         : pbuckets_end(pbuckets_end_),
00443           pbucket(pbucket_),
00444           inode(inode_)
00445       {
00446       }
00447 
00448       //*********************************
00449       bool compare(const const_iterator& rhs) const
00450       {
00451         return rhs.inode == inode;
00452       }
00453 
00454       //*********************************
00455       bucket_t& get_bucket()
00456       {
00457         return *pbucket;
00458       }
00459 
00460       //*********************************
00461       bucket_t*& get_bucket_list_iterator()
00462       {
00463         return pbucket;
00464       }
00465 
00466       //*********************************
00467       local_iterator get_local_iterator()
00468       {
00469         return inode;
00470       }
00471 
00472       bucket_t* pbuckets_end;
00473       bucket_t* pbucket;
00474       local_iterator       inode;
00475     };
00476 
00477     typedef typename std::iterator_traits<iterator>::difference_type difference_type;
00478 
00479     //*********************************************************************
00480     /// Returns an iterator to the beginning of the unordered_set.
00481     ///\return An iterator to the beginning of the unordered_set.
00482     //*********************************************************************
00483     iterator begin()
00484     {
00485       return iterator(pbuckets + number_of_buckets, first, first->begin());
00486     }
00487 
00488     //*********************************************************************
00489     /// Returns a const_iterator to the beginning of the unordered_set.
00490     ///\return A const iterator to the beginning of the unordered_set.
00491     //*********************************************************************
00492     const_iterator begin() const
00493     {
00494       return const_iterator(pbuckets + number_of_buckets, first, first->begin());
00495     }
00496 
00497     //*********************************************************************
00498     /// Returns a const_iterator to the beginning of the unordered_set.
00499     ///\return A const iterator to the beginning of the unordered_set.
00500     //*********************************************************************
00501     const_iterator cbegin() const
00502     {
00503       return const_iterator(pbuckets + number_of_buckets, first, first->begin());
00504     }
00505 
00506     //*********************************************************************
00507     /// Returns an iterator to the beginning of the unordered_set bucket.
00508     ///\return An iterator to the beginning of the unordered_set bucket.
00509     //*********************************************************************
00510     local_iterator begin(size_t i)
00511     {
00512       return pbuckets[i].begin();
00513     }
00514 
00515     //*********************************************************************
00516     /// Returns a const_iterator to the beginning of the unordered_set bucket.
00517     ///\return A const iterator to the beginning of the unordered_set bucket.
00518     //*********************************************************************
00519     local_const_iterator begin(size_t i) const
00520     {
00521       return pbuckets[i].cbegin();
00522     }
00523 
00524     //*********************************************************************
00525     /// Returns a const_iterator to the beginning of the unordered_set bucket.
00526     ///\return A const iterator to the beginning of the unordered_set bucket.
00527     //*********************************************************************
00528     local_const_iterator cbegin(size_t i) const
00529     {
00530       return pbuckets[i].cbegin();
00531     }
00532 
00533     //*********************************************************************
00534     /// Returns an iterator to the end of the unordered_set.
00535     ///\return An iterator to the end of the unordered_set.
00536     //*********************************************************************
00537     iterator end()
00538     {
00539       return iterator(pbuckets + number_of_buckets, last, last->end());
00540     }
00541 
00542     //*********************************************************************
00543     /// Returns a const_iterator to the end of the unordered_set.
00544     ///\return A const iterator to the end of the unordered_set.
00545     //*********************************************************************
00546     const_iterator end() const
00547     {
00548       return const_iterator(pbuckets + number_of_buckets, last, last->end());
00549     }
00550 
00551     //*********************************************************************
00552     /// Returns a const_iterator to the end of the unordered_set.
00553     ///\return A const iterator to the end of the unordered_set.
00554     //*********************************************************************
00555     const_iterator cend() const
00556     {
00557       return const_iterator(pbuckets + number_of_buckets, last, last->end());
00558     }
00559 
00560     //*********************************************************************
00561     /// Returns an iterator to the end of the unordered_set bucket.
00562     ///\return An iterator to the end of the unordered_set bucket.
00563     //*********************************************************************
00564     local_iterator end(size_t i)
00565     {
00566       return pbuckets[i].end();
00567     }
00568 
00569     //*********************************************************************
00570     /// Returns a const_iterator to the end of the unordered_set bucket.
00571     ///\return A const iterator to the end of the unordered_set bucket.
00572     //*********************************************************************
00573     local_const_iterator end(size_t i) const
00574     {
00575       return pbuckets[i].cend();
00576     }
00577 
00578     //*********************************************************************
00579     /// Returns a const_iterator to the end of the unordered_set bucket.
00580     ///\return A const iterator to the end of the unordered_set bucket.
00581     //*********************************************************************
00582     local_const_iterator cend(size_t i) const
00583     {
00584       return pbuckets[i].cend();
00585     }
00586 
00587     //*********************************************************************
00588     /// Returns the bucket index for the key.
00589     ///\return The bucket index for the key.
00590     //*********************************************************************
00591     size_type get_bucket_index(key_parameter_t key) const
00592     {
00593       return key_hash_function(key) % number_of_buckets;
00594     }
00595 
00596     //*********************************************************************
00597     /// Returns the size of the bucket key.
00598     ///\return The bucket size of the bucket key.
00599     //*********************************************************************
00600     size_type bucket_size(key_parameter_t key) const
00601     {
00602       size_t index = bucket(key);
00603 
00604       return std::distance(pbuckets[index].begin(), pbuckets[index].end());
00605     }
00606 
00607     //*********************************************************************
00608     /// Returns the maximum number of the buckets the container can hold.
00609     ///\return The maximum number of the buckets the container can hold.
00610     //*********************************************************************
00611     size_type max_bucket_count() const
00612     {
00613       return number_of_buckets;
00614     }
00615 
00616     //*********************************************************************
00617     /// Returns the number of the buckets the container holds.
00618     ///\return The number of the buckets the container holds.
00619     //*********************************************************************
00620     size_type bucket_count() const
00621     {
00622       return number_of_buckets;
00623     }
00624 
00625     //*********************************************************************
00626     /// Assigns values to the unordered_set.
00627     /// If asserts or exceptions are enabled, emits unordered_set_full if the unordered_set does not have enough free space.
00628     /// If asserts or exceptions are enabled, emits unordered_set_iterator if the iterators are reversed.
00629     ///\param first The iterator to the first element.
00630     ///\param last  The iterator to the last element + 1.
00631     //*********************************************************************
00632     template <typename TIterator>
00633     void assign(TIterator first_, TIterator last_)
00634     {
00635 #if defined(ETL_DEBUG)
00636       difference_type d = std::distance(first_, last_);
00637       ETL_ASSERT(d >= 0, ETL_ERROR(unordered_set_iterator));
00638       ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_set_full));
00639 #endif
00640 
00641       clear();
00642 
00643       while (first_ != last_)
00644       {
00645         insert(*first_++);
00646       }
00647     }
00648 
00649     //*********************************************************************
00650     /// Inserts a value to the unordered_set.
00651     /// If asserts or exceptions are enabled, emits unordered_set_full if the unordered_set is already full.
00652     ///\param value The value to insert.
00653     //*********************************************************************
00654     std::pair<iterator, bool> insert(const value_type& key)
00655     {
00656       std::pair<iterator, bool> result(end(), false);
00657 
00658       ETL_ASSERT(!full(), ETL_ERROR(unordered_set_full));
00659 
00660       // Get the hash index.
00661       size_t index = get_bucket_index(key);
00662 
00663       // Get the bucket & bucket iterator.
00664       bucket_t* pbucket = pbuckets + index;
00665       bucket_t& bucket = *pbucket;
00666 
00667       // The first one in the bucket?
00668       if (bucket.empty())
00669       {
00670         // Get a new node.
00671         node_t& node = *pnodepool->allocate<node_t>();
00672         ::new (&node.key) value_type(key);
00673         ++construct_count;
00674 
00675         // Just add the pointer to the bucket;
00676         bucket.insert_after(bucket.before_begin(), node);
00677 
00678         result.first = iterator(pbuckets + number_of_buckets, pbucket, pbucket->begin());
00679         result.second = true;
00680 
00681         adjust_first_last_markers(pbucket);
00682       }
00683       else
00684       {
00685         // Step though the bucket looking for a place to insert.
00686         local_iterator inode_previous = bucket.before_begin();
00687         local_iterator inode = bucket.begin();
00688 
00689         while (inode != bucket.end())
00690         {
00691           // Do we already have this key?
00692           if (inode->key == key)
00693           {
00694             break;
00695           }
00696 
00697           ++inode_previous;
00698           ++inode;
00699         }
00700 
00701         // Not already there?
00702         if (inode == bucket.end())
00703         {
00704           // Get a new node.
00705           node_t& node = *pnodepool->allocate<node_t>();
00706           ::new (&node.key) value_type(key);
00707           ++construct_count;
00708 
00709           // Add the node to the end of the bucket;
00710           bucket.insert_after(inode_previous, node);
00711           ++inode_previous;
00712 
00713           result.first = iterator(pbuckets + number_of_buckets, pbucket, inode_previous);
00714           result.second = true;
00715         }
00716       }
00717 
00718       return result;
00719     }
00720 
00721     //*********************************************************************
00722     /// Inserts a value to the unordered_set.
00723     /// If asserts or exceptions are enabled, emits unordered_set_full if the unordered_set is already full.
00724     ///\param position The position to insert at.
00725     ///\param value    The value to insert.
00726     //*********************************************************************
00727     iterator insert(const_iterator position, const value_type& key)
00728     {
00729       return insert(key).first;
00730     }
00731 
00732     //*********************************************************************
00733     /// Inserts a range of values to the unordered_set.
00734     /// If asserts or exceptions are enabled, emits unordered_set_full if the unordered_set does not have enough free space.
00735     ///\param position The position to insert at.
00736     ///\param first    The first element to add.
00737     ///\param last     The last + 1 element to add.
00738     //*********************************************************************
00739     template <class TIterator>
00740     void insert(TIterator first_, TIterator last_)
00741     {
00742       while (first_ != last_)
00743       {
00744         insert(*first_++);
00745       }
00746     }
00747 
00748     //*********************************************************************
00749     /// Erases an element.
00750     ///\param key The key to erase.
00751     ///\return The number of elements erased. 0 or 1.
00752     //*********************************************************************
00753     size_t erase(key_parameter_t key)
00754     {
00755       size_t n = 0;
00756       size_t index = get_bucket_index(key);
00757 
00758       bucket_t& bucket = pbuckets[index];
00759 
00760       local_iterator iprevious = bucket.before_begin();
00761       local_iterator icurrent = bucket.begin();
00762 
00763       // Search for the key, if we have it.
00764       while ((icurrent != bucket.end()) && (icurrent->key != key))
00765       {
00766         ++iprevious;
00767         ++icurrent;
00768       }
00769 
00770       // Did we find it?
00771       if (icurrent != bucket.end())
00772       {
00773         bucket.erase_after(iprevious);  // Unlink from the bucket.
00774         icurrent->key.~value_type();    // Destroy the value.
00775         pnodepool->release(&*icurrent); // Release it back to the pool.
00776         n = 1;
00777         --construct_count;
00778       }
00779 
00780       return n;
00781     }
00782 
00783     //*********************************************************************
00784     /// Erases an element.
00785     ///\param ielement Iterator to the element.
00786     //*********************************************************************
00787     iterator erase(const_iterator ielement)
00788     {
00789       // Make a note of the next one.
00790       iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
00791       ++inext;
00792 
00793       bucket_t&      bucket = ielement.get_bucket();
00794       local_iterator iprevious = bucket.before_begin();
00795       local_iterator icurrent = ielement.get_local_iterator();
00796 
00797       // Find the node previous to the one we're interested in.
00798       while (iprevious->etl_next != &*icurrent)
00799       {
00800         ++iprevious;
00801       }
00802 
00803       bucket.erase_after(iprevious);  // Unlink from the bucket.
00804       icurrent->key.~value_type();    // Destroy the value.
00805       pnodepool->release(&*icurrent); // Release it back to the pool.
00806       --construct_count;
00807 
00808       return inext;
00809     }
00810 
00811     //*********************************************************************
00812     /// Erases a range of elements.
00813     /// The range includes all the elements between first and last, including the
00814     /// element pointed by first, but not the one pointed to by last.
00815     ///\param first Iterator to the first element.
00816     ///\param last  Iterator to the last element.
00817     //*********************************************************************
00818     iterator erase(const_iterator first_, const_iterator last_)
00819     {
00820       // Make a note of the last.
00821       iterator result((pbuckets + number_of_buckets), last_.get_bucket_list_iterator(), last_.get_local_iterator());
00822 
00823       // Get the starting point.
00824       bucket_t*      pbucket   = first_.get_bucket_list_iterator();
00825       local_iterator iprevious = pbucket->before_begin();
00826       local_iterator icurrent  = first_.get_local_iterator();
00827       local_iterator iend      = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
00828 
00829                                                        // Find the node previous to the first one.
00830       while (iprevious->etl_next != &*icurrent)
00831       {
00832         ++iprevious;
00833       }
00834 
00835       while (icurrent != iend)
00836       {
00837 
00838         local_iterator inext = pbucket->erase_after(iprevious); // Unlink from the bucket.
00839         icurrent->key.~value_type();    // Destroy the value.
00840         pnodepool->release(&*icurrent); // Release it back to the pool.
00841         --construct_count;
00842 
00843         icurrent = inext;
00844 
00845         // Are we there yet?
00846         if (icurrent != iend)
00847         {
00848           // At the end of this bucket?
00849           if ((icurrent == pbucket->end()))
00850           {
00851             // Find the next non-empty one.
00852             do
00853             {
00854               ++pbucket;
00855             } while (pbucket->empty());
00856 
00857             iprevious = pbucket->before_begin();
00858             icurrent = pbucket->begin();
00859           }
00860         }
00861       }
00862 
00863       return result;
00864     }
00865 
00866     //*************************************************************************
00867     /// Clears the unordered_set.
00868     //*************************************************************************
00869     void clear()
00870     {
00871       initialise();
00872     }
00873 
00874     //*********************************************************************
00875     /// Counts an element.
00876     ///\param key The key to search for.
00877     ///\return 1 if the key exists, otherwise 0.
00878     //*********************************************************************
00879     size_t count(key_parameter_t key) const
00880     {
00881       return (find(key) == end()) ? 0 : 1;
00882     }
00883 
00884     //*********************************************************************
00885     /// Finds an element.
00886     ///\param key The key to search for.
00887     ///\return An iterator to the element if the key exists, otherwise end().
00888     //*********************************************************************
00889     iterator find(key_parameter_t key)
00890     {
00891       size_t index = get_bucket_index(key);
00892 
00893       bucket_t* pbucket = pbuckets + index;
00894       bucket_t& bucket = *pbucket;
00895 
00896       // Is the bucket not empty?
00897       if (!bucket.empty())
00898       {
00899         // Step though the list until we find the end or an equivalent key.
00900         local_iterator inode = bucket.begin();
00901         local_iterator iend = bucket.end();
00902 
00903         while (inode != iend)
00904         {
00905           // Do we have this one?
00906           if (key_equal_function(key, inode->key))
00907           {
00908             return iterator(pbuckets + number_of_buckets, pbucket, inode);
00909           }
00910 
00911           ++inode;
00912         }
00913       }
00914 
00915       return end();
00916     }
00917 
00918     //*********************************************************************
00919     /// Finds an element.
00920     ///\param key The key to search for.
00921     ///\return An iterator to the element if the key exists, otherwise end().
00922     //*********************************************************************
00923     const_iterator find(key_parameter_t key) const
00924     {
00925       size_t index = get_bucket_index(key);
00926 
00927       bucket_t* pbucket = pbuckets + index;
00928       bucket_t& bucket = *pbucket;
00929 
00930       // Is the bucket not empty?
00931       if (!bucket.empty())
00932       {
00933         // Step though the list until we find the end or an equivalent key.
00934         local_iterator inode = bucket.begin();
00935         local_iterator iend = bucket.end();
00936 
00937         while (inode != iend)
00938         {
00939           // Do we have this one?
00940           if (key_equal_function(key, inode->key))
00941           {
00942             return iterator(pbuckets + number_of_buckets, pbucket, inode);
00943           }
00944 
00945           ++inode;
00946         }
00947       }
00948 
00949       return end();
00950     }
00951 
00952     //*********************************************************************
00953     /// Returns a range containing all elements with key 'key' in the container.
00954     /// The range is defined by two iterators, the first pointing to the first
00955     /// element of the wanted range and the second pointing past the last
00956     /// element of the range.
00957     ///\param key The key to search for.
00958     ///\return An iterator pair to the range of elements if the key exists, otherwise end().
00959     //*********************************************************************
00960     std::pair<iterator, iterator> equal_range(key_parameter_t key)
00961     {
00962       iterator f = find(key);
00963       iterator l = f;
00964 
00965       if (l != end())
00966       {
00967         ++l;
00968       }
00969 
00970       return std::pair<iterator, iterator>(f, l);
00971     }
00972 
00973     //*********************************************************************
00974     /// Returns a range containing all elements with key 'key' in the container.
00975     /// The range is defined by two iterators, the first pointing to the first
00976     /// element of the wanted range and the second pointing past the last
00977     /// element of the range.
00978     ///\param key The key to search for.
00979     ///\return A const iterator pair to the range of elements if the key exists, otherwise end().
00980     //*********************************************************************
00981     std::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
00982     {
00983       const_iterator f = find(key);
00984       const_iterator l = f;
00985 
00986       if (l != end())
00987       {
00988         ++l;
00989       }
00990 
00991       return std::pair<const_iterator, const_iterator>(f, l);
00992     }
00993 
00994     //*************************************************************************
00995     /// Gets the size of the unordered_set.
00996     //*************************************************************************
00997     size_type size() const
00998     {
00999       return pnodepool->size();
01000     }
01001 
01002     //*************************************************************************
01003     /// Gets the maximum possible size of the unordered_set.
01004     //*************************************************************************
01005     size_type max_size() const
01006     {
01007       return pnodepool->max_size();
01008     }
01009 
01010     //*************************************************************************
01011     /// Checks to see if the unordered_set is empty.
01012     //*************************************************************************
01013     bool empty() const
01014     {
01015       return pnodepool->empty();
01016     }
01017 
01018     //*************************************************************************
01019     /// Checks to see if the unordered_set is full.
01020     //*************************************************************************
01021     bool full() const
01022     {
01023       return pnodepool->full();
01024     }
01025 
01026     //*************************************************************************
01027     /// Returns the remaining capacity.
01028     ///\return The remaining capacity.
01029     //*************************************************************************
01030     size_t available() const
01031     {
01032       return pnodepool->available();
01033     }
01034 
01035     //*************************************************************************
01036     /// Returns the load factor = size / bucket_count.
01037     ///\return The load factor = size / bucket_count.
01038     //*************************************************************************
01039     float load_factor() const
01040     {
01041       return static_cast<float>(size()) / static_cast<float>(bucket_count());
01042     }
01043 
01044     //*************************************************************************
01045     /// Returns the function that hashes the keys.
01046     ///\return The function that hashes the keys..
01047     //*************************************************************************
01048     hasher hash_function() const
01049     {
01050       return key_hash_function;
01051     }
01052 
01053     //*************************************************************************
01054     /// Returns the function that compares the keys.
01055     ///\return The function that compares the keys..
01056     //*************************************************************************
01057     key_equal key_eq() const
01058     {
01059       return key_equal_function;
01060     }
01061 
01062     //*************************************************************************
01063     /// Assignment operator.
01064     //*************************************************************************
01065     iunordered_set& operator = (const iunordered_set& rhs)
01066     {
01067       // Skip if doing self assignment
01068       if (this != &rhs)
01069       {
01070         assign(rhs.cbegin(), rhs.cend());
01071       }
01072 
01073       return *this;
01074     }
01075 
01076   protected:
01077 
01078     //*********************************************************************
01079     /// Constructor.
01080     //*********************************************************************
01081     iunordered_set(pool_t& node_pool_, bucket_t* pbuckets_, size_t number_of_buckets_)
01082       : pnodepool(&node_pool_),
01083         pbuckets(pbuckets_),
01084         number_of_buckets(number_of_buckets_)
01085     {
01086     }
01087 
01088     //*********************************************************************
01089     /// Initialise the unordered_set.
01090     //*********************************************************************
01091     void initialise()
01092     {
01093       if (!empty())
01094       {
01095         // For each bucket...
01096         for (size_t i = 0; i < number_of_buckets; ++i)
01097         {
01098           bucket_t& bucket = pbuckets[i];
01099 
01100           if (!bucket.empty())
01101           {
01102             // For each item in the bucket...
01103             local_iterator it = bucket.begin();
01104 
01105             while (it != bucket.end())
01106             {
01107               // Destroy the value contents.
01108               it->key.~value_type();
01109               ++it;
01110               --construct_count;
01111             }
01112 
01113             // Now it's safe to clear the bucket.
01114             bucket.clear();
01115           }
01116         }
01117 
01118         // Now it's safe to clear the entire pool in one go.
01119         pnodepool->release_all();
01120       }
01121 
01122       first = pbuckets;
01123       last = first;
01124     }
01125 
01126   private:
01127 
01128     //*********************************************************************
01129     /// Adjust the first and last markers according to the new entry.
01130     //*********************************************************************
01131     void adjust_first_last_markers(bucket_t* pbucket)
01132     {
01133       if (pbucket < first)
01134       {
01135         first = pbucket;
01136       }
01137       else if (pbucket > last)
01138       {
01139         last = pbucket;
01140       }
01141     }
01142 
01143     // Disable copy construction.
01144     iunordered_set(const iunordered_set&);
01145 
01146     /// The pool of data nodes used in the list.
01147     pool_t* pnodepool;
01148 
01149     /// The bucket list.
01150     bucket_t* pbuckets;
01151 
01152     /// The number of buckets.
01153     const size_t number_of_buckets;
01154 
01155     /// The first and last iterators to buckets with values.
01156     bucket_t* first;
01157     bucket_t* last;
01158 
01159     /// The function that creates the hashes.
01160     hasher key_hash_function;
01161 
01162     /// The function that compares the keys for equality.
01163     key_equal key_equal_function;
01164 
01165     /// For library debugging purposes only.
01166     etl::debug_count construct_count;
01167   };
01168 
01169   //***************************************************************************
01170   /// Equal operator.
01171   ///\param lhs Reference to the first unordered_set.
01172   ///\param rhs Reference to the second unordered_set.
01173   ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b>
01174   ///\ingroup unordered_set
01175   //***************************************************************************
01176   template <typename TKey, typename TMapped, typename TKeyCompare>
01177   bool operator ==(const etl::iunordered_set<TKey, TMapped, TKeyCompare>& lhs, const etl::iunordered_set<TKey, TMapped, TKeyCompare>& rhs)
01178   {
01179     return (lhs.size() == rhs.size()) && std::equal(lhs.begin(), lhs.end(), rhs.begin());
01180   }
01181 
01182   //***************************************************************************
01183   /// Not equal operator.
01184   ///\param lhs Reference to the first unordered_set.
01185   ///\param rhs Reference to the second unordered_set.
01186   ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b>
01187   ///\ingroup unordered_set
01188   //***************************************************************************
01189   template <typename TKey, typename TMapped, typename TKeyCompare>
01190   bool operator !=(const etl::iunordered_set<TKey, TMapped, TKeyCompare>& lhs, const etl::iunordered_set<TKey, TMapped, TKeyCompare>& rhs)
01191   {
01192     return !(lhs == rhs);
01193   }
01194 
01195   //*************************************************************************
01196   /// A templated unordered_set implementation that uses a fixed size buffer.
01197   //*************************************************************************
01198   template <typename TKey, const size_t MAX_SIZE_, size_t MAX_BUCKETS_ = MAX_SIZE_, typename THash = etl::hash<TKey>, typename TKeyEqual = std::equal_to<TKey> >
01199   class unordered_set : public etl::iunordered_set<TKey, THash, TKeyEqual>
01200   {
01201   private:
01202 
01203     typedef etl::iunordered_set<TKey, THash, TKeyEqual> base;
01204 
01205   public:
01206 
01207     static const size_t MAX_SIZE    = MAX_SIZE_;
01208     static const size_t MAX_BUCKETS = MAX_BUCKETS_;
01209 
01210     //*************************************************************************
01211     /// Default constructor.
01212     //*************************************************************************
01213     unordered_set()
01214       : base(node_pool, buckets, MAX_BUCKETS)
01215     {
01216       base::initialise();
01217     }
01218 
01219     //*************************************************************************
01220     /// Copy constructor.
01221     //*************************************************************************
01222     unordered_set(const unordered_set& other)
01223       : base(node_pool, buckets, MAX_BUCKETS)
01224     {
01225       base::assign(other.cbegin(), other.cend());
01226     }
01227 
01228     //*************************************************************************
01229     /// Constructor, from an iterator range.
01230     ///\tparam TIterator The iterator type.
01231     ///\param first The iterator to the first element.
01232     ///\param last  The iterator to the last element + 1.
01233     //*************************************************************************
01234     template <typename TIterator>
01235     unordered_set(TIterator first_, TIterator last_)
01236       : base(node_pool, buckets, MAX_BUCKETS)
01237     {
01238       base::assign(first_, last_);
01239     }
01240 
01241     //*************************************************************************
01242     /// Destructor.
01243     //*************************************************************************
01244     ~unordered_set()
01245     {
01246       base::initialise();
01247     }
01248 
01249     //*************************************************************************
01250     /// Assignment operator.
01251     //*************************************************************************
01252     unordered_set& operator = (const unordered_set& rhs)
01253     {
01254       // Skip if doing self assignment
01255       if (this != &rhs)
01256       {
01257         base::assign(rhs.cbegin(), rhs.cend());
01258       }
01259 
01260       return *this;
01261     }
01262 
01263   private:
01264 
01265     /// The pool of nodes used for the unordered_set.
01266     etl::pool<typename base::node_t, MAX_SIZE>  node_pool;
01267 
01268     /// The buckets of node lists.
01269     etl::intrusive_forward_list<typename base::node_t>  buckets[MAX_BUCKETS_];
01270   };
01271 }
01272 
01273 #undef ETL_FILE
01274 
01275 #endif
01276