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