flat_multimap.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) 2015 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_FLAT_MULTMAP__
00032 #define __ETL_FLAT_MULTMAP__
00033 
00034 #include "platform.h "
00035 #include "reference_flat_multimap.h "
00036 #include "pool.h "
00037 
00038 #undef ETL_FILE
00039 #define ETL_FILE "3"
00040 
00041 //*****************************************************************************
00042 ///\defgroup flat_multimap flat_multimap
00043 /// A flat_multimapmap with the capacity defined at compile time.
00044 /// Has insertion of O(N) and find of O(logN)
00045 /// Duplicate entries and not allowed.
00046 ///\ingroup containers
00047 //*****************************************************************************
00048 
00049 namespace etl
00050 {
00051   //***************************************************************************
00052   /// The base class for specifically sized flat_multimaps.
00053   /// Can be used as a reference type for all flat_multimaps containing a specific type.
00054   ///\ingroup flat_multimap
00055   //***************************************************************************
00056   template <typename TKey, typename TMapped, typename TKeyCompare = std::less<TKey> >
00057   class iflat_multimap : public etl::ireference_flat_multimap<TKey, TMapped, TKeyCompare>
00058   {
00059   public:
00060 
00061     typedef std::pair<const TKey, TMapped> value_type;
00062 
00063   private:
00064 
00065     typedef etl::ireference_flat_multimap<TKey, TMapped, TKeyCompare> refmap_t;
00066     typedef typename refmap_t::lookup_t  lookup_t ;
00067     typedef etl::ipool         storage_t;
00068 
00069   public:
00070 
00071     typedef TKey              key_type;
00072     typedef TMapped           mapped_type;
00073     typedef TKeyCompare       key_compare;
00074     typedef value_type&       reference;
00075     typedef const value_type& const_reference;
00076     typedef value_type*       pointer;
00077     typedef const value_type* const_pointer;
00078     typedef size_t            size_type;
00079 
00080     typedef typename refmap_t::iterator       iterator;
00081     typedef typename refmap_t::const_iterator const_iterator;
00082 
00083     typedef std::reverse_iterator<iterator>       reverse_iterator;
00084     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00085     typedef typename std::iterator_traits<iterator>::difference_type difference_type;
00086 
00087   protected:
00088 
00089     typedef typename etl::parameter_type<TKey>::type key_parameter_t;
00090 
00091   private:
00092 
00093     //*********************************************************************
00094     /// How to compare elements and keys.
00095     //*********************************************************************
00096     class compare
00097     {
00098     public:
00099 
00100       bool operator ()(const value_type& element, key_type key) const
00101       {
00102         return key_compare()(element.first, key);
00103       }
00104 
00105       bool operator ()(key_type key, const value_type& element) const
00106       {
00107         return key_compare()(key, element.first);
00108       }
00109     };
00110 
00111   public:
00112 
00113     //*********************************************************************
00114     /// Returns an iterator to the beginning of the flat_multimap.
00115     ///\return An iterator to the beginning of the flat_multimap.
00116     //*********************************************************************
00117     iterator begin()
00118     {
00119       return refmap_t::begin();
00120     }
00121 
00122     //*********************************************************************
00123     /// Returns a const_iterator to the beginning of the flat_multimap.
00124     ///\return A const iterator to the beginning of the flat_multimap.
00125     //*********************************************************************
00126     const_iterator begin() const
00127     {
00128       return refmap_t::begin();
00129     }
00130 
00131     //*********************************************************************
00132     /// Returns an iterator to the end of the flat_multimap.
00133     ///\return An iterator to the end of the flat_multimap.
00134     //*********************************************************************
00135     iterator end()
00136     {
00137       return refmap_t::end();
00138     }
00139 
00140     //*********************************************************************
00141     /// Returns a const_iterator to the end of the flat_multimap.
00142     ///\return A const iterator to the end of the flat_multimap.
00143     //*********************************************************************
00144     const_iterator end() const
00145     {
00146       return refmap_t::end();
00147     }
00148 
00149     //*********************************************************************
00150     /// Returns a const_iterator to the beginning of the flat_multimap.
00151     ///\return A const iterator to the beginning of the flat_multimap.
00152     //*********************************************************************
00153     const_iterator cbegin() const
00154     {
00155       return refmap_t::cbegin();
00156     }
00157 
00158     //*********************************************************************
00159     /// Returns a const_iterator to the end of the flat_multimap.
00160     ///\return A const iterator to the end of the flat_multimap.
00161     //*********************************************************************
00162     const_iterator cend() const
00163     {
00164       return refmap_t::cend();
00165     }
00166 
00167     //*********************************************************************
00168     /// Returns an reverse iterator to the reverse beginning of the flat_multimap.
00169     ///\return Iterator to the reverse beginning of the flat_multimap.
00170     //*********************************************************************
00171     reverse_iterator rbegin()
00172     {
00173       return refmap_t::rbegin();
00174     }
00175 
00176     //*********************************************************************
00177     /// Returns a const reverse iterator to the reverse beginning of the flat_multimap.
00178     ///\return Const iterator to the reverse beginning of the flat_multimap.
00179     //*********************************************************************
00180     const_reverse_iterator rbegin() const
00181     {
00182       return refmap_t::rbegin();
00183     }
00184 
00185     //*********************************************************************
00186     /// Returns a reverse iterator to the end + 1 of the flat_multimap.
00187     ///\return Reverse iterator to the end + 1 of the flat_multimap.
00188     //*********************************************************************
00189     reverse_iterator rend()
00190     {
00191       return refmap_t::rend();
00192     }
00193 
00194     //*********************************************************************
00195     /// Returns a const reverse iterator to the end + 1 of the flat_multimap.
00196     ///\return Const reverse iterator to the end + 1 of the flat_multimap.
00197     //*********************************************************************
00198     const_reverse_iterator rend() const
00199     {
00200       refmap_t::rend();
00201     }
00202 
00203     //*********************************************************************
00204     /// Returns a const reverse iterator to the reverse beginning of the flat_multimap.
00205     ///\return Const reverse iterator to the reverse beginning of the flat_multimap.
00206     //*********************************************************************
00207     const_reverse_iterator crbegin() const
00208     {
00209       return refmap_t::crbegin();
00210     }
00211 
00212     //*********************************************************************
00213     /// Returns a const reverse iterator to the end + 1 of the flat_multimap.
00214     ///\return Const reverse iterator to the end + 1 of the flat_multimap.
00215     //*********************************************************************
00216     const_reverse_iterator crend() const
00217     {
00218       return refmap_t::crend();
00219     }
00220 
00221     //*********************************************************************
00222     /// Assigns values to the flat_multimap.
00223     /// If asserts or exceptions are enabled, emits flat_multimap_full if the flat_multimap does not have enough free space.
00224     /// If asserts or exceptions are enabled, emits flat_multimap_iterator if the iterators are reversed.
00225     ///\param first The iterator to the first element.
00226     ///\param last  The iterator to the last element + 1.
00227     //*********************************************************************
00228     template <typename TIterator>
00229     void assign(TIterator first, TIterator last)
00230     {
00231 #if defined(ETL_DEBUG)
00232       difference_type d = std::distance(first, last);
00233       ETL_ASSERT(d <= difference_type(capacity()), ETL_ERROR(flat_multimap_full));
00234 #endif
00235 
00236       clear();
00237 
00238       while (first != last)
00239       {
00240         insert(*first++);
00241       }
00242     }
00243 
00244     //*********************************************************************
00245     /// Inserts a value to the flat_multimap.
00246     /// If asserts or exceptions are enabled, emits flat_multimap_full if the flat_multimap is already full.
00247     ///\param value    The value to insert.
00248     //*********************************************************************
00249     std::pair<iterator, bool> insert(const value_type& value)
00250     {
00251       ETL_ASSERT(!refmap_t::full(), ETL_ERROR(flat_multimap_full));
00252 
00253       std::pair<iterator, bool> result(end(), false);
00254 
00255       iterator i_element = lower_bound(value.first);
00256 
00257       value_type* pvalue = storage.allocate<value_type>();
00258       ::new (pvalue) value_type(value);
00259       ++construct_count;
00260       result = refmap_t::insert_at(i_element, *pvalue);
00261 
00262       return result;
00263     }
00264 
00265     //*********************************************************************
00266     /// Inserts a value to the flast_multi.
00267     /// If asserts or exceptions are enabled, emits flat_map_full if the flat_map is already full.
00268     ///\param position The position to insert at.
00269     ///\param value    The value to insert.
00270     //*********************************************************************
00271     iterator insert(iterator position, const value_type& value)
00272     {
00273       return insert(value).first;
00274     }
00275 
00276     //*********************************************************************
00277     /// Inserts a range of values to the flat_multimap.
00278     /// If asserts or exceptions are enabled, emits flat_multimap_full if the flat_multimap does not have enough free space.
00279     ///\param position The position to insert at.
00280     ///\param first    The first element to add.
00281     ///\param last     The last + 1 element to add.
00282     //*********************************************************************
00283     template <class TIterator>
00284     void insert(TIterator first, TIterator last)
00285     {
00286       while (first != last)
00287       {
00288         insert(*first++);
00289       }
00290     }
00291 
00292     //*********************************************************************
00293     /// Erases an element.
00294     ///\param key The key to erase.
00295     ///\return The number of elements erased. 0 or 1.
00296     //*********************************************************************
00297     size_t erase(key_parameter_t key)
00298     {
00299       std::pair<iterator, iterator> range = equal_range(key);
00300 
00301       if (range.first == end())
00302       {
00303         return 0;
00304       }
00305       else
00306       {
00307         size_t d = std::distance(range.first, range.second);
00308         erase(range.first, range.second);
00309         return d;
00310       }
00311     }
00312 
00313     //*********************************************************************
00314     /// Erases an element.
00315     ///\param i_element Iterator to the element.
00316     //*********************************************************************
00317     void erase(iterator i_element)
00318     {
00319       i_element->~value_type();
00320       storage.release(etl::addressof(*i_element));
00321       refmap_t::erase(i_element);
00322       --construct_count;
00323     }
00324 
00325     //*********************************************************************
00326     /// Erases a range of elements.
00327     /// The range includes all the elements between first and last, including the
00328     /// element pointed by first, but not the one pointed by last.
00329     ///\param first Iterator to the first element.
00330     ///\param last  Iterator to the last element.
00331     //*********************************************************************
00332     void erase(iterator first, iterator last)
00333     {
00334       iterator itr = first;
00335 
00336       while (itr != last)
00337       {
00338         itr->~value_type();
00339         storage.release(etl::addressof(*itr));
00340         ++itr;
00341         --construct_count;
00342       }
00343 
00344       refmap_t::erase(first, last);
00345     }
00346 
00347     //*************************************************************************
00348     /// Clears the flat_multimap.
00349     //*************************************************************************
00350     void clear()
00351     {
00352       erase(begin(), end());
00353     }
00354 
00355     //*********************************************************************
00356     /// Finds an element.
00357     ///\param key The key to search for.
00358     ///\return An iterator pointing to the element or end() if not found.
00359     //*********************************************************************
00360     iterator find(key_parameter_t key)
00361     {
00362       return refmap_t::find(key);
00363     }
00364 
00365     //*********************************************************************
00366     /// Finds an element.
00367     ///\param key The key to search for.
00368     ///\return An iterator pointing to the element or end() if not found.
00369     //*********************************************************************
00370     const_iterator find(key_parameter_t key) const
00371     {
00372       return refmap_t::find(key);
00373     }
00374 
00375     //*********************************************************************
00376     /// Counts an element.
00377     ///\param key The key to search for.
00378     ///\return 1 if the key exists, otherwise 0.
00379     //*********************************************************************
00380     size_t count(key_parameter_t key) const
00381     {
00382       return refmap_t::count(key);;
00383     }
00384 
00385     //*********************************************************************
00386     /// Finds the lower bound of a key
00387     ///\param key The key to search for.
00388     ///\return An iterator.
00389     //*********************************************************************
00390     iterator lower_bound(key_parameter_t key)
00391     {
00392       return refmap_t::lower_bound(key);
00393     }
00394 
00395     //*********************************************************************
00396     /// Finds the lower bound of a key
00397     ///\param key The key to search for.
00398     ///\return An iterator.
00399     //*********************************************************************
00400     const_iterator lower_bound(key_parameter_t key) const
00401     {
00402       return refmap_t::lower_bound(key);
00403     }
00404 
00405     //*********************************************************************
00406     /// Finds the upper bound of a key
00407     ///\param key The key to search for.
00408     ///\return An iterator.
00409     //*********************************************************************
00410     iterator upper_bound(key_parameter_t key)
00411     {
00412       return refmap_t::upper_bound(key);
00413     }
00414 
00415     //*********************************************************************
00416     /// Finds the upper bound of a key
00417     ///\param key The key to search for.
00418     ///\return An iterator.
00419     //*********************************************************************
00420     const_iterator upper_bound(key_parameter_t key) const
00421     {
00422       return refmap_t::upper_bound(key);
00423     }
00424 
00425     //*********************************************************************
00426     /// Finds the range of equal elements of a key
00427     ///\param key The key to search for.
00428     ///\return An iterator pair.
00429     //*********************************************************************
00430     std::pair<iterator, iterator> equal_range(key_parameter_t key)
00431     {
00432       return refmap_t::equal_range(key);
00433     }
00434 
00435     //*********************************************************************
00436     /// Finds the range of equal elements of a key
00437     ///\param key The key to search for.
00438     ///\return An iterator pair.
00439     //*********************************************************************
00440     std::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
00441     {
00442       return refmap_t::equal_range(key);
00443     }
00444 
00445     //*************************************************************************
00446     /// Assignment operator.
00447     //*************************************************************************
00448     iflat_multimap& operator = (const iflat_multimap& rhs)
00449     {
00450       if (&rhs != this)
00451       {
00452         assign(rhs.cbegin(), rhs.cend());
00453       }
00454 
00455       return *this;
00456     }
00457 
00458     //*************************************************************************
00459     /// Gets the current size of the flat_multiset.
00460     ///\return The current size of the flat_multiset.
00461     //*************************************************************************
00462     size_type size() const
00463     {
00464       return refmap_t::size();
00465     }
00466 
00467     //*************************************************************************
00468     /// Checks the 'empty' state of the flat_multiset.
00469     ///\return <b>true</b> if empty.
00470     //*************************************************************************
00471     bool empty() const
00472     {
00473       return refmap_t::empty();
00474     }
00475 
00476     //*************************************************************************
00477     /// Checks the 'full' state of the flat_multiset.
00478     ///\return <b>true</b> if full.
00479     //*************************************************************************
00480     bool full() const
00481     {
00482       return refmap_t::full();
00483     }
00484 
00485     //*************************************************************************
00486     /// Returns the capacity of the flat_multiset.
00487     ///\return The capacity of the flat_multiset.
00488     //*************************************************************************
00489     size_type capacity() const
00490     {
00491       return refmap_t::capacity();
00492     }
00493 
00494     //*************************************************************************
00495     /// Returns the maximum possible size of the flat_multiset.
00496     ///\return The maximum size of the flat_multiset.
00497     //*************************************************************************
00498     size_type max_size() const
00499     {
00500       return refmap_t::max_size();
00501     }
00502 
00503     //*************************************************************************
00504     /// Returns the remaining capacity.
00505     ///\return The remaining capacity.
00506     //*************************************************************************
00507     size_t available() const
00508     {
00509       return refmap_t::available();
00510     }
00511 
00512   protected:
00513 
00514     //*********************************************************************
00515     /// Constructor.
00516     //*********************************************************************
00517     iflat_multimap(lookup_t & lookup_, storage_t& storage_)
00518       : refmap_t (lookup_),
00519         storage(storage_)
00520     {
00521     }
00522 
00523   private:
00524 
00525     // Disable copy construction.
00526     iflat_multimap(const iflat_multimap&);
00527 
00528     storage_t& storage;
00529 
00530     /// Internal debugging.
00531     etl::debug_count construct_count;
00532   };
00533 
00534   //***************************************************************************
00535   /// Equal operator.
00536   ///\param lhs Reference to the first flat_multimap.
00537   ///\param rhs Reference to the second flat_multimap.
00538   ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b>
00539   ///\ingroup flat_multimap
00540   //***************************************************************************
00541   template <typename TKey, typename TMapped, typename TKeyCompare>
00542   bool operator ==(const etl::iflat_multimap<TKey, TMapped, TKeyCompare>& lhs, const etl::iflat_multimap<TKey, TMapped, TKeyCompare>& rhs)
00543   {
00544     return (lhs.size() == rhs.size()) && std::equal(lhs.begin(), lhs.end(), rhs.begin());
00545   }
00546 
00547   //***************************************************************************
00548   /// Not equal operator.
00549   ///\param lhs Reference to the first flat_multimap.
00550   ///\param rhs Reference to the second flat_multimap.
00551   ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b>
00552   ///\ingroup flat_multimap
00553   //***************************************************************************
00554   template <typename TKey, typename TMapped, typename TKeyCompare>
00555   bool operator !=(const etl::iflat_multimap<TKey, TMapped, TKeyCompare>& lhs, const etl::iflat_multimap<TKey, TMapped, TKeyCompare>& rhs)
00556   {
00557     return !(lhs == rhs);
00558   }
00559 
00560   //***************************************************************************
00561   /// A flat_multimap implementation that uses a fixed size buffer.
00562   ///\tparam TKey     The key type.
00563   ///\tparam TValue   The value type.
00564   ///\tparam TCompare The type to compare keys. Default = std::less<TKey>
00565   ///\tparam MAX_SIZE_ The maximum number of elements that can be stored.
00566   ///\ingroup flat_multimap
00567   //***************************************************************************
00568   template <typename TKey, typename TValue, const size_t MAX_SIZE_, typename TCompare = std::less<TKey> >
00569   class flat_multimap : public etl::iflat_multimap<TKey, TValue, TCompare>
00570   {
00571   public:
00572 
00573     static const size_t MAX_SIZE = MAX_SIZE_;
00574 
00575     //*************************************************************************
00576     /// Constructor.
00577     //*************************************************************************
00578     flat_multimap()
00579       : etl::iflat_multimap<TKey, TValue, TCompare>(lookup, storage)
00580     {
00581     }
00582 
00583     //*************************************************************************
00584     /// Copy constructor.
00585     //*************************************************************************
00586     flat_multimap(const flat_multimap& other)
00587       : etl::iflat_multimap<TKey, TValue, TCompare>(lookup, storage)
00588     {
00589       etl::iflat_multimap<TKey, TValue, TCompare>::assign(other.cbegin(), other.cend());
00590     }
00591 
00592     //*************************************************************************
00593     /// Constructor, from an iterator range.
00594     ///\tparam TIterator The iterator type.
00595     ///\param first The iterator to the first element.
00596     ///\param last  The iterator to the last element + 1.
00597     //*************************************************************************
00598     template <typename TIterator>
00599     flat_multimap(TIterator first, TIterator last)
00600       : etl::iflat_multimap<TKey, TValue, TCompare>(lookup, storage)
00601     {
00602       etl::iflat_multimap<TKey, TValue, TCompare>::assign(first, last);
00603     }
00604 
00605     //*************************************************************************
00606     /// Destructor.
00607     //*************************************************************************
00608     ~flat_multimap()
00609     {
00610       etl::iflat_multimap<TKey, TValue, TCompare>::clear();
00611     }
00612 
00613     //*************************************************************************
00614     /// Assignment operator.
00615     //*************************************************************************
00616     flat_multimap& operator = (const flat_multimap& rhs)
00617     {
00618       if (&rhs != this)
00619       {
00620         etl::iflat_multimap<TKey, TValue, TCompare>::assign(rhs.cbegin(), rhs.cend());
00621       }
00622 
00623       return *this;
00624     }
00625 
00626   private:
00627 
00628     typedef typename etl::iflat_multimap<TKey, TValue, TCompare>::value_type node_t;
00629 
00630     // The pool of nodes.
00631     etl::pool<node_t, MAX_SIZE>  storage;
00632 
00633     // The vector that stores pointers to the nodes.
00634     etl::vector<node_t*, MAX_SIZE>  lookup;
00635   };
00636 }
00637 
00638 #undef ETL_FILE
00639 
00640 #endif
00641