flat_multiset.h

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