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