reference_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) 2017 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_REFERENCE_FLAT_MAP__
00032 #define __ETL_REFERENCE_FLAT_MAP__
00033 
00034 #include <stddef.h>
00035 
00036 #include "platform.h "
00037 #include "vector.h "
00038 #include "error_handler.h "
00039 #include "debug_count.h "
00040 #include "type_traits.h "
00041 #include "parameter_type.h "
00042 #include "exception.h "
00043 #include "static_assert.h"
00044 
00045 #undef ETL_FILE
00046 #define ETL_FILE "30"
00047 
00048 //*****************************************************************************
00049 ///\defgroup reference_flat_map reference_flat_map
00050 /// An reference_flat_map with the capacity defined at compile time.
00051 /// Has insertion of O(N) and search of O(logN)
00052 /// Duplicate entries are not allowed.
00053 ///\ingroup containers
00054 //*****************************************************************************
00055 
00056 namespace etl
00057 {
00058   //***************************************************************************
00059   ///\ingroup reference_flat_map
00060   /// Exception base for reference_flat_maps
00061   //***************************************************************************
00062   class flat_map_exception : public etl::exception
00063   {
00064   public:
00065 
00066     flat_map_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00067       : exception(reason_, file_name_, line_number_)
00068     {
00069     }
00070   };
00071 
00072   //***************************************************************************
00073   ///\ingroup reference_flat_map
00074   /// Vector full exception.
00075   //***************************************************************************
00076   class flat_map_full : public etl::flat_map_exception
00077   {
00078   public:
00079 
00080     flat_map_full(string_type file_name_, numeric_type line_number_)
00081       : flat_map_exception(ETL_ERROR_TEXT("flat_map: full", ETL_FILE"A"), file_name_, line_number_)
00082     {
00083     }
00084   };
00085 
00086   //***************************************************************************
00087   ///\ingroup reference_flat_map
00088   /// Vector out of bounds exception.
00089   //***************************************************************************
00090   class flat_map_out_of_bounds : public etl::flat_map_exception
00091   {
00092   public:
00093 
00094     flat_map_out_of_bounds(string_type file_name_, numeric_type line_number_)
00095       : flat_map_exception(ETL_ERROR_TEXT("flat_map:bounds", ETL_FILE"B"), file_name_, line_number_)
00096     {
00097     }
00098   };
00099 
00100   //***************************************************************************
00101   /// The base class for specifically sized reference_flat_maps.
00102   /// Can be used as a reference type for all reference_flat_maps containing a specific type.
00103   ///\ingroup reference_flat_map
00104   //***************************************************************************
00105   template <typename TKey, typename TMapped, typename TKeyCompare = std::less<TKey> >
00106   class ireference_flat_map
00107   {
00108   public:
00109 
00110     typedef std::pair<const TKey, TMapped> value_type;
00111 
00112   protected:
00113 
00114     typedef etl::ivector<value_type*>  lookup_t ;
00115 
00116   public:
00117 
00118     typedef TKey              key_type;
00119     typedef TMapped           mapped_type;
00120     typedef TKeyCompare       key_compare;
00121     typedef value_type&       reference;
00122     typedef const value_type& const_reference;
00123     typedef value_type*       pointer;
00124     typedef const value_type* const_pointer;
00125     typedef size_t            size_type;
00126 
00127     //*************************************************************************
00128     class iterator : public std::iterator<std::bidirectional_iterator_tag, value_type>
00129     {
00130     public:
00131 
00132       friend class ireference_flat_map;
00133 
00134       iterator()
00135       {
00136       }
00137 
00138       iterator(typename lookup_t::iterator ilookup_)
00139         : ilookup(ilookup_)
00140       {
00141       }
00142 
00143       iterator(const iterator& other)
00144         : ilookup(other.ilookup)
00145       {
00146       }
00147 
00148       iterator& operator =(const iterator& other)
00149       {
00150         ilookup = other.ilookup;
00151         return *this;
00152       }
00153 
00154       iterator& operator ++()
00155       {
00156         ++ilookup;
00157         return *this;
00158       }
00159 
00160       iterator operator ++(int)
00161       {
00162         iterator temp(*this);
00163         ++ilookup;
00164         return temp;
00165       }
00166 
00167       iterator& operator --()
00168       {
00169         --ilookup;
00170         return *this;
00171       }
00172 
00173       iterator operator --(int)
00174       {
00175         iterator temp(*this);
00176         --ilookup;
00177         return temp;
00178       }
00179 
00180       reference operator *()
00181       {
00182         return *(*ilookup);
00183       }
00184 
00185       const_reference operator *() const
00186       {
00187         return *(*ilookup);
00188       }
00189 
00190       pointer operator &()
00191       {
00192         return etl::addressof(*(*ilookup));
00193       }
00194 
00195       const_pointer operator &() const
00196       {
00197         return &(*(*ilookup));
00198       }
00199 
00200       pointer operator ->()
00201       {
00202         return etl::addressof(*(*ilookup));
00203       }
00204 
00205       const_pointer operator ->() const
00206       {
00207         return etl::addressof(*(*ilookup));
00208       }
00209 
00210       friend bool operator == (const iterator& lhs, const iterator& rhs)
00211       {
00212         return lhs.ilookup == rhs.ilookup;
00213       }
00214 
00215       friend bool operator != (const iterator& lhs, const iterator& rhs)
00216       {
00217         return !(lhs == rhs);
00218       }
00219 
00220     private:
00221 
00222       typename lookup_t::iterator ilookup;
00223     };
00224 
00225     //*************************************************************************
00226     class const_iterator : public std::iterator<std::bidirectional_iterator_tag, const value_type>
00227     {
00228     public:
00229 
00230       friend class ireference_flat_map;
00231 
00232       const_iterator()
00233       {
00234       }
00235 
00236       const_iterator(typename lookup_t::const_iterator ilookup_)
00237         : ilookup(ilookup_)
00238       {
00239       }
00240 
00241       const_iterator(const iterator& other)
00242         : ilookup(other.ilookup)
00243       {
00244       }
00245 
00246       const_iterator(const const_iterator& other)
00247         : ilookup(other.ilookup)
00248       {
00249       }
00250 
00251       const_iterator& operator =(const iterator& other)
00252       {
00253         ilookup = other.ilookup;
00254         return *this;
00255       }
00256 
00257       const_iterator& operator =(const const_iterator& other)
00258       {
00259         ilookup = other.ilookup;
00260         return *this;
00261       }
00262 
00263       const_iterator& operator ++()
00264       {
00265         ++ilookup;
00266         return *this;
00267       }
00268 
00269       const_iterator operator ++(int)
00270       {
00271         const_iterator temp(*this);
00272         ++ilookup;
00273         return temp;
00274       }
00275 
00276       const_iterator& operator --()
00277       {
00278         --ilookup;
00279         return *this;
00280       }
00281 
00282       const_iterator operator --(int)
00283       {
00284         const_iterator temp(*this);
00285         --ilookup;
00286         return temp;
00287       }
00288 
00289       const_reference operator *() const
00290       {
00291         return *(*ilookup);
00292       }
00293 
00294       const_pointer operator &() const
00295       {
00296         return etl::addressof(*(*ilookup));
00297       }
00298 
00299       const_pointer operator ->() const
00300       {
00301         return etl::addressof(*(*ilookup));
00302       }
00303 
00304       friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
00305       {
00306         return lhs.ilookup == rhs.ilookup;
00307       }
00308 
00309       friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
00310       {
00311         return !(lhs == rhs);
00312       }
00313 
00314     private:
00315 
00316       typename lookup_t::const_iterator ilookup;
00317     };
00318 
00319     typedef std::reverse_iterator<iterator>       reverse_iterator;
00320     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00321     typedef typename std::iterator_traits<iterator>::difference_type difference_type;
00322 
00323   protected:
00324 
00325     typedef typename etl::parameter_type<TKey>::type key_parameter_t;
00326 
00327   private:
00328 
00329     //*********************************************************************
00330     /// How to compare elements and keys.
00331     //*********************************************************************
00332     class compare
00333     {
00334     public:
00335 
00336       bool operator ()(const value_type& element, key_type key) const
00337       {
00338         return key_compare()(element.first, key);
00339       }
00340 
00341       bool operator ()(key_type key, const value_type& element) const
00342       {
00343         return key_compare()(key, element.first);
00344       }
00345     };
00346 
00347   public:
00348 
00349     //*********************************************************************
00350     /// Returns an iterator to the beginning of the reference_flat_map.
00351     ///\return An iterator to the beginning of the reference_flat_map.
00352     //*********************************************************************
00353     iterator begin()
00354     {
00355       return iterator(lookup.begin());
00356     }
00357 
00358     //*********************************************************************
00359     /// Returns a const_iterator to the beginning of the reference_flat_map.
00360     ///\return A const iterator to the beginning of the reference_flat_map.
00361     //*********************************************************************
00362     const_iterator begin() const
00363     {
00364       return const_iterator(lookup.begin());
00365     }
00366 
00367     //*********************************************************************
00368     /// Returns an iterator to the end of the reference_flat_map.
00369     ///\return An iterator to the end of the reference_flat_map.
00370     //*********************************************************************
00371     iterator end()
00372     {
00373       return iterator(lookup.end());
00374     }
00375 
00376     //*********************************************************************
00377     /// Returns a const_iterator to the end of the reference_flat_map.
00378     ///\return A const iterator to the end of the reference_flat_map.
00379     //*********************************************************************
00380     const_iterator end() const
00381     {
00382       return const_iterator(lookup.end());
00383     }
00384 
00385     //*********************************************************************
00386     /// Returns a const_iterator to the beginning of the reference_flat_map.
00387     ///\return A const iterator to the beginning of the reference_flat_map.
00388     //*********************************************************************
00389     const_iterator cbegin() const
00390     {
00391       return const_iterator(lookup.cbegin());
00392     }
00393 
00394     //*********************************************************************
00395     /// Returns a const_iterator to the end of the reference_flat_map.
00396     ///\return A const iterator to the end of the reference_flat_map.
00397     //*********************************************************************
00398     const_iterator cend() const
00399     {
00400       return const_iterator(lookup.cend());
00401     }
00402 
00403     //*********************************************************************
00404     /// Returns an reverse iterator to the reverse beginning of the reference_flat_map.
00405     ///\return Iterator to the reverse beginning of the reference_flat_map.
00406     //*********************************************************************
00407     reverse_iterator rbegin()
00408     {
00409       return reverse_iterator(lookup.rbegin());
00410     }
00411 
00412     //*********************************************************************
00413     /// Returns a const reverse iterator to the reverse beginning of the reference_flat_map.
00414     ///\return Const iterator to the reverse beginning of the reference_flat_map.
00415     //*********************************************************************
00416     const_reverse_iterator rbegin() const
00417     {
00418       return reverse_iterator(lookup.rbegin());
00419     }
00420 
00421     //*********************************************************************
00422     /// Returns a reverse iterator to the end + 1 of the reference_flat_map.
00423     ///\return Reverse iterator to the end + 1 of the reference_flat_map.
00424     //*********************************************************************
00425     reverse_iterator rend()
00426     {
00427       return reverse_iterator(lookup.rend());
00428     }
00429 
00430     //*********************************************************************
00431     /// Returns a const reverse iterator to the end + 1 of the reference_flat_map.
00432     ///\return Const reverse iterator to the end + 1 of the reference_flat_map.
00433     //*********************************************************************
00434     const_reverse_iterator rend() const
00435     {
00436       return const_reverse_iterator(lookup.rend());
00437     }
00438 
00439     //*********************************************************************
00440     /// Returns a const reverse iterator to the reverse beginning of the reference_flat_map.
00441     ///\return Const reverse iterator to the reverse beginning of the reference_flat_map.
00442     //*********************************************************************
00443     const_reverse_iterator crbegin() const
00444     {
00445       return const_reverse_iterator(lookup.crbegin());
00446     }
00447 
00448     //*********************************************************************
00449     /// Returns a const reverse iterator to the end + 1 of the reference_flat_map.
00450     ///\return Const reverse iterator to the end + 1 of the reference_flat_map.
00451     //*********************************************************************
00452     const_reverse_iterator crend() const
00453     {
00454       return const_reverse_iterator(lookup.crend());
00455     }
00456 
00457     //*********************************************************************
00458     /// Returns a reference to the value at index 'key'
00459     ///\param i The index.
00460     ///\return A reference to the value at index 'key'
00461     //*********************************************************************
00462     mapped_type& operator [](key_parameter_t key)
00463     {
00464       iterator i_element = lower_bound(key);
00465 
00466       ETL_ASSERT(i_element != end(), ETL_ERROR(flat_map_out_of_bounds));
00467 
00468       return i_element->second;
00469     }
00470 
00471     //*********************************************************************
00472     /// Returns a const reference to the value at index 'key'
00473     ///\param i The index.
00474     ///\return A const reference to the value at index 'key'
00475     //*********************************************************************
00476     const mapped_type& operator [](key_parameter_t key) const
00477     {
00478       iterator i_element = lower_bound(key);
00479 
00480       ETL_ASSERT(i_element != end(), ETL_ERROR(flat_map_out_of_bounds));
00481 
00482       return i_element->second;
00483     }
00484 
00485     //*********************************************************************
00486     /// Returns a reference to the value at index 'key'
00487     /// If asserts or exceptions are enabled, emits an etl::flat_map_out_of_bounds if the key is not in the range.
00488     ///\param i The index.
00489     ///\return A reference to the value at index 'key'
00490     //*********************************************************************
00491     mapped_type& at(key_parameter_t key)
00492     {
00493       iterator i_element = lower_bound(key);
00494 
00495       ETL_ASSERT(i_element != end(), ETL_ERROR(flat_map_out_of_bounds));
00496 
00497       return i_element->second;
00498     }
00499 
00500     //*********************************************************************
00501     /// Returns a const reference to the value at index 'key'
00502     /// If asserts or exceptions are enabled, emits an etl::flat_map_out_of_bounds if the key is not in the range.
00503     ///\param i The index.
00504     ///\return A const reference to the value at index 'key'
00505     //*********************************************************************
00506     const mapped_type& at(key_parameter_t key) const
00507     {
00508       const_iterator i_element = lower_bound(key);
00509 
00510       ETL_ASSERT(i_element != end(), ETL_ERROR(flat_map_out_of_bounds));
00511 
00512       return i_element->second;
00513     }
00514 
00515     //*********************************************************************
00516     /// Assigns values to the reference_flat_map.
00517     /// If ETL_THROW_EXCEPTIONS & ETL_DEBUG are defined, emits flat_map_full if the reference_flat_map does not have enough free space.
00518     /// If ETL_THROW_EXCEPTIONS & ETL_DEBUG are defined, emits flat_map_iterator if the iterators are reversed.
00519     ///\param first The iterator to the first element.
00520     ///\param last  The iterator to the last element + 1.
00521     //*********************************************************************
00522     template <typename TIterator>
00523     void assign(TIterator first, TIterator last)
00524     {
00525       STATIC_ASSERT((etl::is_same<value_type, typename std::iterator_traits<TIterator>::value_type>::value), "Incompatible data for assign");
00526 
00527 #if defined(ETL_DEBUG)
00528       difference_type d = std::distance(first, last);
00529       ETL_ASSERT(d <= difference_type(capacity()), ETL_ERROR(flat_map_full));
00530 #endif
00531 
00532       clear();
00533 
00534       while (first != last)
00535       {
00536         insert(*first++);
00537       }
00538     }
00539 
00540     //*********************************************************************
00541     /// Inserts a value to the reference_flat_map.
00542     /// If asserts or exceptions are enabled, emits flat_map_full if the reference_flat_map is already full.
00543     ///\param value    The value to insert.
00544     //*********************************************************************
00545     std::pair<iterator, bool> insert(reference value)
00546     {
00547       iterator i_element = lower_bound(value.first);
00548 
00549       return insert_at(i_element, value);
00550     }
00551 
00552     //*********************************************************************
00553     /// Inserts a value to the reference_flat_map.
00554     /// If asserts or exceptions are enabled, emits flat_map_full if the reference_flat_map is already full.
00555     ///\param position The position to insert at.
00556     ///\param value    The value to insert.
00557     //*********************************************************************
00558     iterator insert(iterator position, reference value)
00559     {
00560       return insert(value).first;
00561     }
00562 
00563     //*********************************************************************
00564     /// Inserts a range of values to the reference_flat_map.
00565     /// If asserts or exceptions are enabled, emits flat_map_full if the reference_flat_map does not have enough free space.
00566     ///\param position The position to insert at.
00567     ///\param first    The first element to add.
00568     ///\param last     The last + 1 element to add.
00569     //*********************************************************************
00570     template <class TIterator>
00571     void insert(TIterator first, TIterator last)
00572     {
00573       while (first != last)
00574       {
00575         insert(*first++);
00576       }
00577     }
00578 
00579     //*********************************************************************
00580     /// Erases an element.
00581     ///\param key The key to erase.
00582     ///\return The number of elements erased. 0 or 1.
00583     //*********************************************************************
00584     size_t erase(key_parameter_t key)
00585     {
00586       iterator i_element = find(key);
00587 
00588       if (i_element == end())
00589       {
00590         return 0;
00591       }
00592       else
00593       {
00594         lookup.erase(i_element.ilookup);
00595         return 1;
00596       }
00597     }
00598 
00599     //*********************************************************************
00600     /// Erases an element.
00601     ///\param i_element Iterator to the element.
00602     //*********************************************************************
00603     void erase(iterator i_element)
00604     {
00605       lookup.erase(i_element.ilookup);
00606     }
00607 
00608     //*********************************************************************
00609     /// Erases a range of elements.
00610     /// The range includes all the elements between first and last, including the
00611     /// element pointed by first, but not the one pointed by last.
00612     ///\param first Iterator to the first element.
00613     ///\param last  Iterator to the last element.
00614     //*********************************************************************
00615     void erase(iterator first, iterator last)
00616     {
00617       lookup.erase(first.ilookup, last.ilookup);
00618     }
00619 
00620     //*************************************************************************
00621     /// Clears the reference_flat_map.
00622     //*************************************************************************
00623     void clear()
00624     {
00625       erase(begin(), end());
00626     }
00627 
00628     //*********************************************************************
00629     /// Finds an element.
00630     ///\param key The key to search for.
00631     ///\return An iterator pointing to the element or end() if not found.
00632     //*********************************************************************
00633     iterator find(key_parameter_t key)
00634     {
00635       iterator itr = lower_bound(key);
00636 
00637       if (itr != end())
00638       {
00639         if (!key_compare()(itr->first, key) && !key_compare()(key, itr->first))
00640         {
00641           return itr;
00642         }
00643         else
00644         {
00645           return end();
00646         }
00647       }
00648 
00649       return end();
00650     }
00651 
00652     //*********************************************************************
00653     /// Finds an element.
00654     ///\param key The key to search for.
00655     ///\return An iterator pointing to the element or end() if not found.
00656     //*********************************************************************
00657     const_iterator find(key_parameter_t key) const
00658     {
00659       const_iterator itr = lower_bound(key);
00660 
00661       if (itr != end())
00662       {
00663         if (!key_compare()(itr->first, key) && !key_compare()(key, itr->first))
00664         {
00665           return itr;
00666         }
00667         else
00668         {
00669           return end();
00670         }
00671       }
00672 
00673       return end();
00674     }
00675 
00676     //*********************************************************************
00677     /// Counts an element.
00678     ///\param key The key to search for.
00679     ///\return 1 if the key exists, otherwise 0.
00680     //*********************************************************************
00681     size_t count(key_parameter_t key) const
00682     {
00683       return (find(key) == end()) ? 0 : 1;
00684     }
00685 
00686     //*********************************************************************
00687     /// Finds the lower bound of a key
00688     ///\param key The key to search for.
00689     ///\return An iterator.
00690     //*********************************************************************
00691     iterator lower_bound(key_parameter_t key)
00692     {
00693       return std::lower_bound(begin(), end(), key, compare());
00694     }
00695 
00696     //*********************************************************************
00697     /// Finds the lower bound of a key
00698     ///\param key The key to search for.
00699     ///\return An iterator.
00700     //*********************************************************************
00701     const_iterator lower_bound(key_parameter_t key) const
00702     {
00703       return std::lower_bound(cbegin(), cend(), key, compare());
00704     }
00705 
00706     //*********************************************************************
00707     /// Finds the upper bound of a key
00708     ///\param key The key to search for.
00709     ///\return An iterator.
00710     //*********************************************************************
00711     iterator upper_bound(key_parameter_t key)
00712     {
00713       return std::upper_bound(begin(), end(), key, compare());
00714     }
00715 
00716     //*********************************************************************
00717     /// Finds the upper bound of a key
00718     ///\param key The key to search for.
00719     ///\return An iterator.
00720     //*********************************************************************
00721     const_iterator upper_bound(key_parameter_t key) const
00722     {
00723       return std::upper_bound(begin(), end(), key, compare());
00724     }
00725 
00726     //*********************************************************************
00727     /// Finds the range of equal elements of a key
00728     ///\param key The key to search for.
00729     ///\return An iterator pair.
00730     //*********************************************************************
00731     std::pair<iterator, iterator> equal_range(key_parameter_t key)
00732     {
00733       iterator i_lower = std::lower_bound(begin(), end(), key, compare());
00734 
00735       return std::make_pair(i_lower, std::upper_bound(i_lower, end(), key, compare()));
00736     }
00737 
00738     //*********************************************************************
00739     /// Finds the range of equal elements of a key
00740     ///\param key The key to search for.
00741     ///\return An iterator pair.
00742     //*********************************************************************
00743     std::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
00744     {
00745       const_iterator i_lower = std::lower_bound(cbegin(), cend(), key, compare());
00746 
00747       return std::make_pair(i_lower, std::upper_bound(i_lower, cend(), key, compare()));
00748     }
00749 
00750     //*************************************************************************
00751     /// Gets the current size of the reference_flat_map.
00752     ///\return The current size of the reference_flat_map.
00753     //*************************************************************************
00754     size_type size() const
00755     {
00756       return lookup.size();
00757     }
00758 
00759     //*************************************************************************
00760     /// Checks the 'empty' state of the reference_flat_map.
00761     ///\return <b>true</b> if empty.
00762     //*************************************************************************
00763     bool empty() const
00764     {
00765       return lookup.empty();
00766     }
00767 
00768     //*************************************************************************
00769     /// Checks the 'full' state of the reference_flat_map.
00770     ///\return <b>true</b> if full.
00771     //*************************************************************************
00772     bool full() const
00773     {
00774       return lookup.full();
00775     }
00776 
00777     //*************************************************************************
00778     /// Returns the capacity of the reference_flat_map.
00779     ///\return The capacity of the reference_flat_map.
00780     //*************************************************************************
00781     size_type capacity() const
00782     {
00783       return lookup.capacity();
00784     }
00785 
00786     //*************************************************************************
00787     /// Returns the maximum possible size of the reference_flat_map.
00788     ///\return The maximum size of the reference_flat_map.
00789     //*************************************************************************
00790     size_type max_size() const
00791     {
00792       return lookup.max_size();
00793     }
00794 
00795     //*************************************************************************
00796     /// Returns the remaining capacity.
00797     ///\return The remaining capacity.
00798     //*************************************************************************
00799     size_t available() const
00800     {
00801       return lookup.available();
00802     }
00803 
00804   protected:
00805 
00806     //*********************************************************************
00807     /// Constructor.
00808     //*********************************************************************
00809     ireference_flat_map(lookup_t & lookup_)
00810       : lookup(lookup_)
00811     {
00812     }
00813 
00814     //*********************************************************************
00815     /// Inserts a value to the reference_flat_map.
00816     ///\param i_element The place to insert.
00817     ///\param value     The value to insert.
00818     //*********************************************************************
00819     std::pair<iterator, bool> insert_at(iterator i_element, value_type& value)
00820     {
00821       std::pair<iterator, bool> result(end(), false);
00822 
00823       if (i_element == end())
00824       {
00825         // At the end.
00826         ETL_ASSERT(!lookup.full(), ETL_ERROR(flat_map_full));
00827 
00828         lookup.push_back(&value);
00829         result.first = --end();
00830         result.second = true;
00831       }
00832       else
00833       {
00834         // Not at the end.
00835         result.first = i_element;
00836 
00837         // Existing element?
00838         if (value.first != i_element->first)
00839         {
00840           // A new one.
00841           ETL_ASSERT(!lookup.full(), ETL_ERROR(flat_map_full));
00842           lookup.insert(i_element.ilookup, &value);
00843           result.second = true;
00844         }
00845       }
00846 
00847       return result;
00848     }
00849 
00850   private:
00851 
00852     // Disable copy construction and assignment.
00853     ireference_flat_map(const ireference_flat_map&);
00854     ireference_flat_map& operator = (const ireference_flat_map&);
00855 
00856     lookup_t& lookup;
00857   };
00858 
00859   //***************************************************************************
00860   /// Equal operator.
00861   ///\param lhs Reference to the first reference_flat_map.
00862   ///\param rhs Reference to the second reference_flat_map.
00863   ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b>
00864   ///\ingroup reference_flat_map
00865   //***************************************************************************
00866   template <typename TKey, typename TMapped, typename TKeyCompare>
00867   bool operator ==(const etl::ireference_flat_map<TKey, TMapped, TKeyCompare>& lhs, const etl::ireference_flat_map<TKey, TMapped, TKeyCompare>& rhs)
00868   {
00869     return (lhs.size() == rhs.size()) && std::equal(lhs.begin(), lhs.end(), rhs.begin());
00870   }
00871 
00872   //***************************************************************************
00873   /// Not equal operator.
00874   ///\param lhs Reference to the first reference_flat_map.
00875   ///\param rhs Reference to the second reference_flat_map.
00876   ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b>
00877   ///\ingroup reference_flat_map
00878   //***************************************************************************
00879   template <typename TKey, typename TMapped, typename TKeyCompare>
00880   bool operator !=(const etl::ireference_flat_map<TKey, TMapped, TKeyCompare>& lhs, const etl::ireference_flat_map<TKey, TMapped, TKeyCompare>& rhs)
00881   {
00882     return !(lhs == rhs);
00883   }
00884 
00885   //***************************************************************************
00886   /// A reference_flat_map implementation that uses a fixed size buffer.
00887   ///\tparam TKey     The key type.
00888   ///\tparam TValue   The value type.
00889   ///\tparam TCompare The type to compare keys. Default = std::less<TKey>
00890   ///\tparam MAX_SIZE_ The maximum number of elements that can be stored.
00891   ///\ingroup reference_flat_map
00892   //***************************************************************************
00893   template <typename TKey, typename TValue, const size_t MAX_SIZE_, typename TCompare = std::less<TKey> >
00894   class reference_flat_map : public ireference_flat_map<TKey, TValue, TCompare>
00895   {
00896   public:
00897 
00898     static const size_t MAX_SIZE = MAX_SIZE_;
00899 
00900     //*************************************************************************
00901     /// Constructor.
00902     //*************************************************************************
00903     reference_flat_map()
00904       : ireference_flat_map<TKey, TValue, TCompare>(lookup)
00905     {
00906     }
00907 
00908     //*************************************************************************
00909     /// Constructor, from an iterator range.
00910     ///\tparam TIterator The iterator type.
00911     ///\param first The iterator to the first element.
00912     ///\param last  The iterator to the last element + 1.
00913     //*************************************************************************
00914     template <typename TIterator>
00915     reference_flat_map(TIterator first, TIterator last)
00916       : ireference_flat_map<TKey, TValue, TCompare>(lookup)
00917     {
00918       ireference_flat_map<TKey, TValue, TCompare>::assign(first, last);
00919     }
00920 
00921     //*************************************************************************
00922     /// Destructor.
00923     //*************************************************************************
00924     ~reference_flat_map()
00925     {
00926       ireference_flat_map<TKey, TValue, TCompare>::clear();
00927     }
00928 
00929     //*************************************************************************
00930     /// Assignment operator.
00931     //*************************************************************************
00932     reference_flat_map& operator = (const reference_flat_map& rhs)
00933     {
00934       if (&rhs != this)
00935       {
00936         ireference_flat_map<TKey, TValue, TCompare>::assign(rhs.cbegin(), rhs.cend());
00937       }
00938 
00939       return *this;
00940     }
00941 
00942   private:
00943 
00944     reference_flat_map(const reference_flat_map&);
00945 
00946     typedef typename ireference_flat_map<TKey, TValue, TCompare>::value_type node_t;
00947 
00948     // The vector that stores pointers to the nodes.
00949     etl::vector<node_t*, MAX_SIZE>  lookup;
00950   };
00951 
00952 }
00953 
00954 #undef ETL_FILE
00955 
00956 #endif
00957