flat_set.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_SET__
00032 #define __ETL_FLAT_SET__
00033 
00034 #include "platform.h "
00035 #include "reference_flat_set.h "
00036 #include "pool.h "
00037 
00038 #undef ETL_FILE
00039 #define ETL_FILE "5"
00040 
00041 //*****************************************************************************
00042 ///\defgroup flat_set flat_set
00043 /// A flat_set with the capacity defined at compile time.
00044 /// Has insertion of O(N) and flat_set 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_sets.
00053   /// Can be used as a reference type for all flat_sets containing a specific type.
00054   ///\ingroup flat_set
00055   //***************************************************************************
00056   template <typename T, typename TKeyCompare = std::less<T> >
00057   class iflat_set : private etl::ireference_flat_set<T, TKeyCompare>
00058   {
00059   private:
00060 
00061     typedef etl::ireference_flat_set<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_set.
00091     ///\return An iterator to the beginning of the flat_set.
00092     //*********************************************************************
00093     iterator begin()
00094     {
00095       return refset_t::begin();
00096     }
00097 
00098     //*********************************************************************
00099     /// Returns a const_iterator to the beginning of the flat_set.
00100     ///\return A const iterator to the beginning of the flat_set.
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_set.
00109     ///\return An iterator to the end of the flat_set.
00110     //*********************************************************************
00111     iterator end()
00112     {
00113       return refset_t::end();
00114     }
00115 
00116     //*********************************************************************
00117     /// Returns a const_iterator to the end of the flat_set.
00118     ///\return A const iterator to the end of the flat_set.
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_set.
00127     ///\return A const iterator to the beginning of the flat_set.
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_set.
00136     ///\return A const iterator to the end of the flat_set.
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_set.
00145     ///\return Iterator to the reverse beginning of the flat_set.
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_set.
00154     ///\return Const iterator to the reverse beginning of the flat_set.
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_set.
00163     ///\return Reverse iterator to the end + 1 of the flat_set.
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_set.
00172     ///\return Const reverse iterator to the end + 1 of the flat_set.
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_set.
00181     ///\return Const reverse iterator to the reverse beginning of the flat_set.
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_set.
00190     ///\return Const reverse iterator to the end + 1 of the flat_set.
00191     //*********************************************************************
00192     const_reverse_iterator crend() const
00193     {
00194       return refset_t::crend();
00195     }
00196 
00197     //*********************************************************************
00198     /// Assigns values to the flat_set.
00199     /// If asserts or exceptions are enabled, emits flat_set_full if the flat_set does not have enough free space.
00200     /// If asserts or exceptions are enabled, emits flat_set_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_set_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_set.
00222     /// If asserts or exceptions are enabled, emits flat_set_full if the flat_set is already full.
00223     ///\param value    The value to insert.
00224     //*********************************************************************
00225     std::pair<iterator, bool> insert(parameter_t value)
00226     {
00227       iterator i_element = lower_bound(value);
00228 
00229       std::pair<iterator, bool> result(i_element, false);
00230 
00231       // Doesn't already exist?
00232       if ((i_element == end() || (*i_element != value)))
00233       {
00234         ETL_ASSERT(!refset_t::full(), ETL_ERROR(flat_set_full));
00235 
00236         value_type* pvalue = storage.allocate<value_type>();
00237         ::new (pvalue) value_type(value);
00238         ++construct_count;
00239         result = refset_t::insert_at(i_element, *pvalue);
00240       }
00241 
00242       return result;
00243     }
00244 
00245     //*********************************************************************
00246     /// Inserts a value to the flat_set.
00247     /// If asserts or exceptions are enabled, emits flat_set_full if the flat_set is already full.
00248     ///\param position The position to insert at.
00249     ///\param value    The value to insert.
00250     //*********************************************************************
00251     iterator insert(iterator position, parameter_t value)
00252     {
00253       return insert(value).first;
00254     }
00255 
00256     //*********************************************************************
00257     /// Inserts a range of values to the flat_set.
00258     /// If asserts or exceptions are enabled, emits flat_set_full if the flat_set does not have enough free space.
00259     ///\param position The position to insert at.
00260     ///\param first    The first element to add.
00261     ///\param last     The last + 1 element to add.
00262     //*********************************************************************
00263     template <class TIterator>
00264     void insert(TIterator first, TIterator last)
00265     {
00266       while (first != last)
00267       {
00268         insert(*first++);
00269       }
00270     }
00271 
00272     //*********************************************************************
00273     /// Erases an element.
00274     ///\param key The key to erase.
00275     ///\return The number of elements erased. 0 or 1.
00276     //*********************************************************************
00277     size_t erase(parameter_t key)
00278     {
00279       iterator i_element = find(key);
00280 
00281       if (i_element == end())
00282       {
00283         return 0;
00284       }
00285       else
00286       {
00287         i_element->~value_type();
00288         storage.release(etl::addressof(*i_element));
00289         refset_t::erase(i_element);
00290         --construct_count;
00291         return 1;
00292       }
00293     }
00294 
00295     //*********************************************************************
00296     /// Erases an element.
00297     ///\param i_element Iterator to the element.
00298     //*********************************************************************
00299     void erase(iterator i_element)
00300     {
00301       i_element->~value_type();
00302       storage.release(etl::addressof(*i_element));
00303       refset_t::erase(i_element);
00304       --construct_count;
00305     }
00306 
00307     //*********************************************************************
00308     /// Erases a range of elements.
00309     /// The range includes all the elements between first and last, including the
00310     /// element pointed by first, but not the one pointed by last.
00311     ///\param first Iterator to the first element.
00312     ///\param last  Iterator to the last element.
00313     //*********************************************************************
00314     void erase(iterator first, iterator last)
00315     {
00316       iterator itr = first;
00317 
00318       while (itr != last)
00319       {
00320         itr->~value_type();
00321         storage.release(etl::addressof(*itr));
00322         ++itr;
00323         --construct_count;
00324       }
00325 
00326       refset_t::erase(first, last);
00327     }
00328 
00329     //*************************************************************************
00330     /// Clears the flat_set.
00331     //*************************************************************************
00332     void clear()
00333     {
00334       erase(begin(), end());
00335     }
00336 
00337     //*********************************************************************
00338     /// Finds an element.
00339     ///\param key The key to search for.
00340     ///\return An iterator pointing to the element or end() if not found.
00341     //*********************************************************************
00342     iterator find(parameter_t key)
00343     {
00344       return refset_t::find(key);
00345     }
00346 
00347     //*********************************************************************
00348     /// Finds an element.
00349     ///\param key The key to search for.
00350     ///\return An iterator pointing to the element or end() if not found.
00351     //*********************************************************************
00352     const_iterator find(parameter_t key) const
00353     {
00354       return refset_t::find(key);
00355     }
00356 
00357     //*********************************************************************
00358     /// Counts an element.
00359     ///\param key The key to search for.
00360     ///\return 1 if the key exists, otherwise 0.
00361     //*********************************************************************
00362     size_t count(parameter_t key) const
00363     {
00364       return refset_t::count(key);
00365     }
00366 
00367     //*********************************************************************
00368     /// Finds the lower bound of a key
00369     ///\param key The key to search for.
00370     ///\return An iterator.
00371     //*********************************************************************
00372     iterator lower_bound(parameter_t key)
00373     {
00374       return refset_t::lower_bound(key);
00375     }
00376 
00377     //*********************************************************************
00378     /// Finds the lower bound of a key
00379     ///\param key The key to search for.
00380     ///\return An iterator.
00381     //*********************************************************************
00382     const_iterator lower_bound(parameter_t key) const
00383     {
00384       return refset_t::lower_bound(key);
00385     }
00386 
00387     //*********************************************************************
00388     /// Finds the upper bound of a key
00389     ///\param key The key to search for.
00390     ///\return An iterator.
00391     //*********************************************************************
00392     iterator upper_bound(parameter_t key)
00393     {
00394       return refset_t::upper_bound(key);
00395     }
00396 
00397     //*********************************************************************
00398     /// Finds the upper bound of a key
00399     ///\param key The key to search for.
00400     ///\return An iterator.
00401     //*********************************************************************
00402     const_iterator upper_bound(parameter_t key) const
00403     {
00404       return refset_t::upper_bound(key);
00405     }
00406 
00407     //*********************************************************************
00408     /// Finds the range of equal elements of a key
00409     ///\param key The key to search for.
00410     ///\return An iterator pair.
00411     //*********************************************************************
00412     std::pair<iterator, iterator> equal_range(parameter_t key)
00413     {
00414       return refset_t::equal_range(key);
00415     }
00416 
00417     //*********************************************************************
00418     /// Finds the range of equal elements of a key
00419     ///\param key The key to search for.
00420     ///\return An iterator pair.
00421     //*********************************************************************
00422     std::pair<const_iterator, const_iterator> equal_range(parameter_t key) const
00423     {
00424       return refset_t::upper_bound(key);
00425     }
00426 
00427     //*************************************************************************
00428     /// Assignment operator.
00429     //*************************************************************************
00430     iflat_set& operator = (const iflat_set& rhs)
00431     {
00432       if (&rhs != this)
00433       {
00434         assign(rhs.cbegin(), rhs.cend());
00435       }
00436 
00437       return *this;
00438     }
00439 
00440     //*************************************************************************
00441     /// Gets the current size of the flat_set.
00442     ///\return The current size of the flat_set.
00443     //*************************************************************************
00444     size_type size() const
00445     {
00446       return refset_t::size();
00447     }
00448 
00449     //*************************************************************************
00450     /// Checks the 'empty' state of the flat_set.
00451     ///\return <b>true</b> if empty.
00452     //*************************************************************************
00453     bool empty() const
00454     {
00455       return refset_t::empty();
00456     }
00457 
00458     //*************************************************************************
00459     /// Checks the 'full' state of the flat_set.
00460     ///\return <b>true</b> if full.
00461     //*************************************************************************
00462     bool full() const
00463     {
00464       return refset_t::full();
00465     }
00466 
00467     //*************************************************************************
00468     /// Returns the capacity of the flat_set.
00469     ///\return The capacity of the flat_set.
00470     //*************************************************************************
00471     size_type capacity() const
00472     {
00473       return refset_t::capacity();
00474     }
00475 
00476     //*************************************************************************
00477     /// Returns the maximum possible size of the flat_set.
00478     ///\return The maximum size of the flat_set.
00479     //*************************************************************************
00480     size_type max_size() const
00481     {
00482       return refset_t::max_size();
00483     }
00484 
00485     //*************************************************************************
00486     /// Returns the remaining capacity.
00487     ///\return The remaining capacity.
00488     //*************************************************************************
00489     size_t available() const
00490     {
00491       return refset_t::available();
00492     }
00493 
00494   protected:
00495 
00496     //*********************************************************************
00497     /// Constructor.
00498     //*********************************************************************
00499     iflat_set(lookup_t & lookup_, storage_t& storage_)
00500       : refset_t (lookup_),
00501         storage(storage_)
00502     {
00503     }
00504 
00505   private:
00506 
00507     // Disable copy construction.
00508     iflat_set(const iflat_set&);
00509 
00510     storage_t& storage;
00511 
00512     /// Internal debugging.
00513     etl::debug_count construct_count;
00514   };
00515 
00516   //***************************************************************************
00517   /// Equal operator.
00518   ///\param lhs Reference to the first flat_set.
00519   ///\param rhs Reference to the second flat_set.
00520   ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b>
00521   ///\ingroup flat_set
00522   //***************************************************************************
00523   template <typename T, typename TKeyCompare>
00524   bool operator ==(const etl::iflat_set<T, TKeyCompare>& lhs, const etl::iflat_set<T, TKeyCompare>& rhs)
00525   {
00526     return (lhs.size() == rhs.size()) && std::equal(lhs.begin(), lhs.end(), rhs.begin());
00527   }
00528 
00529   //***************************************************************************
00530   /// Not equal operator.
00531   ///\param lhs Reference to the first flat_set.
00532   ///\param rhs Reference to the second flat_set.
00533   ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b>
00534   ///\ingroup flat_set
00535   //***************************************************************************
00536   template <typename T, typename TKeyCompare>
00537   bool operator !=(const etl::iflat_set<T, TKeyCompare>& lhs, const etl::iflat_set<T, TKeyCompare>& rhs)
00538   {
00539     return !(lhs == rhs);
00540   }
00541 
00542   //***************************************************************************
00543   /// A flat_set implementation that uses a fixed size buffer.
00544   ///\tparam T        The value type.
00545   ///\tparam TCompare The type to compare keys. Default = std::less<T>
00546   ///\tparam MAX_SIZE_ The maximum number of elements that can be stored.
00547   ///\ingroup flat_set
00548   //***************************************************************************
00549   template <typename T, const size_t MAX_SIZE_, typename TCompare = std::less<T> >
00550   class flat_set : public etl::iflat_set<T, TCompare>
00551   {
00552   public:
00553 
00554     static const size_t MAX_SIZE = MAX_SIZE_;
00555 
00556     //*************************************************************************
00557     /// Constructor.
00558     //*************************************************************************
00559     flat_set()
00560       : etl::iflat_set<T, TCompare>(lookup, storage)
00561     {
00562     }
00563 
00564     //*************************************************************************
00565     /// Copy constructor.
00566     //*************************************************************************
00567     flat_set(const flat_set& other)
00568       : etl::iflat_set<T, TCompare>(lookup, storage)
00569     {
00570       etl::iflat_set<T, TCompare>::assign(other.cbegin(), other.cend());
00571     }
00572 
00573     //*************************************************************************
00574     /// Constructor, from an iterator range.
00575     ///\tparam TIterator The iterator type.
00576     ///\param first The iterator to the first element.
00577     ///\param last  The iterator to the last element + 1.
00578     //*************************************************************************
00579     template <typename TIterator>
00580     flat_set(TIterator first, TIterator last)
00581       : etl::iflat_set<T, TCompare>(lookup, storage)
00582     {
00583       etl::iflat_set<T, TCompare>::assign(first, last);
00584     }
00585 
00586     //*************************************************************************
00587     /// Destructor.
00588     //*************************************************************************
00589     ~flat_set()
00590     {
00591       etl::iflat_set<T, TCompare>::clear();
00592     }
00593 
00594     //*************************************************************************
00595     /// Assignment operator.
00596     //*************************************************************************
00597     flat_set& operator = (const flat_set& rhs)
00598     {
00599       if (&rhs != this)
00600       {
00601         etl::iflat_set<T, TCompare>::assign(rhs.cbegin(), rhs.cend());
00602       }
00603 
00604       return *this;
00605     }
00606 
00607   private:
00608 
00609     typedef typename etl::iflat_set<T, TCompare>::value_type node_t;
00610 
00611     // The pool of nodes.
00612     etl::pool<node_t, MAX_SIZE>  storage;
00613 
00614     // The vector that stores pointers to the nodes.
00615     etl::vector<node_t*, MAX_SIZE>  lookup;
00616   };
00617 }
00618 
00619 #undef ETL_FILE
00620 
00621 #endif
00622