Stefan Scholz / ETL

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

flat_set.h@0:b47c2a7920c2, 2018-03-16 (annotated)

Committer:
bobbery
Date:
Fri Mar 16 16:34:18 2018 +0000
Revision:
0:b47c2a7920c2
Works after using gcc_generic undef CAPACITY and replacing nullptr by std::nullptr

Who changed what in which revision?

UserRevisionLine numberNew contents of line
bobbery 0:b47c2a7920c2 1 ///\file
bobbery 0:b47c2a7920c2 2
bobbery 0:b47c2a7920c2 3 /******************************************************************************
bobbery 0:b47c2a7920c2 4 The MIT License(MIT)
bobbery 0:b47c2a7920c2 5
bobbery 0:b47c2a7920c2 6 Embedded Template Library.
bobbery 0:b47c2a7920c2 7 https://github.com/ETLCPP/etl
bobbery 0:b47c2a7920c2 8 http://www.etlcpp.com
bobbery 0:b47c2a7920c2 9
bobbery 0:b47c2a7920c2 10 Copyright(c) 2015 jwellbelove
bobbery 0:b47c2a7920c2 11
bobbery 0:b47c2a7920c2 12 Permission is hereby granted, free of charge, to any person obtaining a copy
bobbery 0:b47c2a7920c2 13 of this software and associated documentation files(the "Software"), to deal
bobbery 0:b47c2a7920c2 14 in the Software without restriction, including without limitation the rights
bobbery 0:b47c2a7920c2 15 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
bobbery 0:b47c2a7920c2 16 copies of the Software, and to permit persons to whom the Software is
bobbery 0:b47c2a7920c2 17 furnished to do so, subject to the following conditions :
bobbery 0:b47c2a7920c2 18
bobbery 0:b47c2a7920c2 19 The above copyright notice and this permission notice shall be included in all
bobbery 0:b47c2a7920c2 20 copies or substantial portions of the Software.
bobbery 0:b47c2a7920c2 21
bobbery 0:b47c2a7920c2 22 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
bobbery 0:b47c2a7920c2 23 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
bobbery 0:b47c2a7920c2 24 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
bobbery 0:b47c2a7920c2 25 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
bobbery 0:b47c2a7920c2 26 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
bobbery 0:b47c2a7920c2 27 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
bobbery 0:b47c2a7920c2 28 SOFTWARE.
bobbery 0:b47c2a7920c2 29 ******************************************************************************/
bobbery 0:b47c2a7920c2 30
bobbery 0:b47c2a7920c2 31 #ifndef __ETL_FLAT_SET__
bobbery 0:b47c2a7920c2 32 #define __ETL_FLAT_SET__
bobbery 0:b47c2a7920c2 33
bobbery 0:b47c2a7920c2 34 #include "platform.h"
bobbery 0:b47c2a7920c2 35 #include "reference_flat_set.h"
bobbery 0:b47c2a7920c2 36 #include "pool.h"
bobbery 0:b47c2a7920c2 37
bobbery 0:b47c2a7920c2 38 #undef ETL_FILE
bobbery 0:b47c2a7920c2 39 #define ETL_FILE "5"
bobbery 0:b47c2a7920c2 40
bobbery 0:b47c2a7920c2 41 //*****************************************************************************
bobbery 0:b47c2a7920c2 42 ///\defgroup flat_set flat_set
bobbery 0:b47c2a7920c2 43 /// A flat_set with the capacity defined at compile time.
bobbery 0:b47c2a7920c2 44 /// Has insertion of O(N) and flat_set of O(logN)
bobbery 0:b47c2a7920c2 45 /// Duplicate entries and not allowed.
bobbery 0:b47c2a7920c2 46 ///\ingroup containers
bobbery 0:b47c2a7920c2 47 //*****************************************************************************
bobbery 0:b47c2a7920c2 48
bobbery 0:b47c2a7920c2 49 namespace etl
bobbery 0:b47c2a7920c2 50 {
bobbery 0:b47c2a7920c2 51 //***************************************************************************
bobbery 0:b47c2a7920c2 52 /// The base class for specifically sized flat_sets.
bobbery 0:b47c2a7920c2 53 /// Can be used as a reference type for all flat_sets containing a specific type.
bobbery 0:b47c2a7920c2 54 ///\ingroup flat_set
bobbery 0:b47c2a7920c2 55 //***************************************************************************
bobbery 0:b47c2a7920c2 56 template <typename T, typename TKeyCompare = std::less<T> >
bobbery 0:b47c2a7920c2 57 class iflat_set : private etl::ireference_flat_set<T, TKeyCompare>
bobbery 0:b47c2a7920c2 58 {
bobbery 0:b47c2a7920c2 59 private:
bobbery 0:b47c2a7920c2 60
bobbery 0:b47c2a7920c2 61 typedef etl::ireference_flat_set<T, TKeyCompare> refset_t;
bobbery 0:b47c2a7920c2 62 typedef typename refset_t::lookup_t lookup_t;
bobbery 0:b47c2a7920c2 63 typedef etl::ipool storage_t;
bobbery 0:b47c2a7920c2 64
bobbery 0:b47c2a7920c2 65 public:
bobbery 0:b47c2a7920c2 66
bobbery 0:b47c2a7920c2 67 typedef T key_type;
bobbery 0:b47c2a7920c2 68 typedef T value_type;
bobbery 0:b47c2a7920c2 69 typedef TKeyCompare key_compare;
bobbery 0:b47c2a7920c2 70 typedef value_type& reference;
bobbery 0:b47c2a7920c2 71 typedef const value_type& const_reference;
bobbery 0:b47c2a7920c2 72 typedef value_type* pointer;
bobbery 0:b47c2a7920c2 73 typedef const value_type* const_pointer;
bobbery 0:b47c2a7920c2 74 typedef size_t size_type;
bobbery 0:b47c2a7920c2 75
bobbery 0:b47c2a7920c2 76 typedef typename refset_t::iterator iterator;
bobbery 0:b47c2a7920c2 77 typedef typename refset_t::const_iterator const_iterator;
bobbery 0:b47c2a7920c2 78
bobbery 0:b47c2a7920c2 79 typedef std::reverse_iterator<iterator> reverse_iterator;
bobbery 0:b47c2a7920c2 80 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
bobbery 0:b47c2a7920c2 81 typedef typename std::iterator_traits<iterator>::difference_type difference_type;
bobbery 0:b47c2a7920c2 82
bobbery 0:b47c2a7920c2 83 protected:
bobbery 0:b47c2a7920c2 84
bobbery 0:b47c2a7920c2 85 typedef typename etl::parameter_type<T>::type parameter_t;
bobbery 0:b47c2a7920c2 86
bobbery 0:b47c2a7920c2 87 public:
bobbery 0:b47c2a7920c2 88
bobbery 0:b47c2a7920c2 89 //*********************************************************************
bobbery 0:b47c2a7920c2 90 /// Returns an iterator to the beginning of the flat_set.
bobbery 0:b47c2a7920c2 91 ///\return An iterator to the beginning of the flat_set.
bobbery 0:b47c2a7920c2 92 //*********************************************************************
bobbery 0:b47c2a7920c2 93 iterator begin()
bobbery 0:b47c2a7920c2 94 {
bobbery 0:b47c2a7920c2 95 return refset_t::begin();
bobbery 0:b47c2a7920c2 96 }
bobbery 0:b47c2a7920c2 97
bobbery 0:b47c2a7920c2 98 //*********************************************************************
bobbery 0:b47c2a7920c2 99 /// Returns a const_iterator to the beginning of the flat_set.
bobbery 0:b47c2a7920c2 100 ///\return A const iterator to the beginning of the flat_set.
bobbery 0:b47c2a7920c2 101 //*********************************************************************
bobbery 0:b47c2a7920c2 102 const_iterator begin() const
bobbery 0:b47c2a7920c2 103 {
bobbery 0:b47c2a7920c2 104 return refset_t::begin();
bobbery 0:b47c2a7920c2 105 }
bobbery 0:b47c2a7920c2 106
bobbery 0:b47c2a7920c2 107 //*********************************************************************
bobbery 0:b47c2a7920c2 108 /// Returns an iterator to the end of the flat_set.
bobbery 0:b47c2a7920c2 109 ///\return An iterator to the end of the flat_set.
bobbery 0:b47c2a7920c2 110 //*********************************************************************
bobbery 0:b47c2a7920c2 111 iterator end()
bobbery 0:b47c2a7920c2 112 {
bobbery 0:b47c2a7920c2 113 return refset_t::end();
bobbery 0:b47c2a7920c2 114 }
bobbery 0:b47c2a7920c2 115
bobbery 0:b47c2a7920c2 116 //*********************************************************************
bobbery 0:b47c2a7920c2 117 /// Returns a const_iterator to the end of the flat_set.
bobbery 0:b47c2a7920c2 118 ///\return A const iterator to the end of the flat_set.
bobbery 0:b47c2a7920c2 119 //*********************************************************************
bobbery 0:b47c2a7920c2 120 const_iterator end() const
bobbery 0:b47c2a7920c2 121 {
bobbery 0:b47c2a7920c2 122 return refset_t::end();
bobbery 0:b47c2a7920c2 123 }
bobbery 0:b47c2a7920c2 124
bobbery 0:b47c2a7920c2 125 //*********************************************************************
bobbery 0:b47c2a7920c2 126 /// Returns a const_iterator to the beginning of the flat_set.
bobbery 0:b47c2a7920c2 127 ///\return A const iterator to the beginning of the flat_set.
bobbery 0:b47c2a7920c2 128 //*********************************************************************
bobbery 0:b47c2a7920c2 129 const_iterator cbegin() const
bobbery 0:b47c2a7920c2 130 {
bobbery 0:b47c2a7920c2 131 return refset_t::cbegin();
bobbery 0:b47c2a7920c2 132 }
bobbery 0:b47c2a7920c2 133
bobbery 0:b47c2a7920c2 134 //*********************************************************************
bobbery 0:b47c2a7920c2 135 /// Returns a const_iterator to the end of the flat_set.
bobbery 0:b47c2a7920c2 136 ///\return A const iterator to the end of the flat_set.
bobbery 0:b47c2a7920c2 137 //*********************************************************************
bobbery 0:b47c2a7920c2 138 const_iterator cend() const
bobbery 0:b47c2a7920c2 139 {
bobbery 0:b47c2a7920c2 140 return refset_t::cend();
bobbery 0:b47c2a7920c2 141 }
bobbery 0:b47c2a7920c2 142
bobbery 0:b47c2a7920c2 143 //*********************************************************************
bobbery 0:b47c2a7920c2 144 /// Returns an reverse iterator to the reverse beginning of the flat_set.
bobbery 0:b47c2a7920c2 145 ///\return Iterator to the reverse beginning of the flat_set.
bobbery 0:b47c2a7920c2 146 //*********************************************************************
bobbery 0:b47c2a7920c2 147 reverse_iterator rbegin()
bobbery 0:b47c2a7920c2 148 {
bobbery 0:b47c2a7920c2 149 return refset_t::rbegin();
bobbery 0:b47c2a7920c2 150 }
bobbery 0:b47c2a7920c2 151
bobbery 0:b47c2a7920c2 152 //*********************************************************************
bobbery 0:b47c2a7920c2 153 /// Returns a const reverse iterator to the reverse beginning of the flat_set.
bobbery 0:b47c2a7920c2 154 ///\return Const iterator to the reverse beginning of the flat_set.
bobbery 0:b47c2a7920c2 155 //*********************************************************************
bobbery 0:b47c2a7920c2 156 const_reverse_iterator rbegin() const
bobbery 0:b47c2a7920c2 157 {
bobbery 0:b47c2a7920c2 158 return refset_t::rbegin();
bobbery 0:b47c2a7920c2 159 }
bobbery 0:b47c2a7920c2 160
bobbery 0:b47c2a7920c2 161 //*********************************************************************
bobbery 0:b47c2a7920c2 162 /// Returns a reverse iterator to the end + 1 of the flat_set.
bobbery 0:b47c2a7920c2 163 ///\return Reverse iterator to the end + 1 of the flat_set.
bobbery 0:b47c2a7920c2 164 //*********************************************************************
bobbery 0:b47c2a7920c2 165 reverse_iterator rend()
bobbery 0:b47c2a7920c2 166 {
bobbery 0:b47c2a7920c2 167 return refset_t::rend();
bobbery 0:b47c2a7920c2 168 }
bobbery 0:b47c2a7920c2 169
bobbery 0:b47c2a7920c2 170 //*********************************************************************
bobbery 0:b47c2a7920c2 171 /// Returns a const reverse iterator to the end + 1 of the flat_set.
bobbery 0:b47c2a7920c2 172 ///\return Const reverse iterator to the end + 1 of the flat_set.
bobbery 0:b47c2a7920c2 173 //*********************************************************************
bobbery 0:b47c2a7920c2 174 const_reverse_iterator rend() const
bobbery 0:b47c2a7920c2 175 {
bobbery 0:b47c2a7920c2 176 return refset_t::rend();
bobbery 0:b47c2a7920c2 177 }
bobbery 0:b47c2a7920c2 178
bobbery 0:b47c2a7920c2 179 //*********************************************************************
bobbery 0:b47c2a7920c2 180 /// Returns a const reverse iterator to the reverse beginning of the flat_set.
bobbery 0:b47c2a7920c2 181 ///\return Const reverse iterator to the reverse beginning of the flat_set.
bobbery 0:b47c2a7920c2 182 //*********************************************************************
bobbery 0:b47c2a7920c2 183 const_reverse_iterator crbegin() const
bobbery 0:b47c2a7920c2 184 {
bobbery 0:b47c2a7920c2 185 return refset_t::crbegin();
bobbery 0:b47c2a7920c2 186 }
bobbery 0:b47c2a7920c2 187
bobbery 0:b47c2a7920c2 188 //*********************************************************************
bobbery 0:b47c2a7920c2 189 /// Returns a const reverse iterator to the end + 1 of the flat_set.
bobbery 0:b47c2a7920c2 190 ///\return Const reverse iterator to the end + 1 of the flat_set.
bobbery 0:b47c2a7920c2 191 //*********************************************************************
bobbery 0:b47c2a7920c2 192 const_reverse_iterator crend() const
bobbery 0:b47c2a7920c2 193 {
bobbery 0:b47c2a7920c2 194 return refset_t::crend();
bobbery 0:b47c2a7920c2 195 }
bobbery 0:b47c2a7920c2 196
bobbery 0:b47c2a7920c2 197 //*********************************************************************
bobbery 0:b47c2a7920c2 198 /// Assigns values to the flat_set.
bobbery 0:b47c2a7920c2 199 /// If asserts or exceptions are enabled, emits flat_set_full if the flat_set does not have enough free space.
bobbery 0:b47c2a7920c2 200 /// If asserts or exceptions are enabled, emits flat_set_iterator if the iterators are reversed.
bobbery 0:b47c2a7920c2 201 ///\param first The iterator to the first element.
bobbery 0:b47c2a7920c2 202 ///\param last The iterator to the last element + 1.
bobbery 0:b47c2a7920c2 203 //*********************************************************************
bobbery 0:b47c2a7920c2 204 template <typename TIterator>
bobbery 0:b47c2a7920c2 205 void assign(TIterator first, TIterator last)
bobbery 0:b47c2a7920c2 206 {
bobbery 0:b47c2a7920c2 207 #if defined(ETL_DEBUG)
bobbery 0:b47c2a7920c2 208 difference_type d = std::distance(first, last);
bobbery 0:b47c2a7920c2 209 ETL_ASSERT(d <= difference_type(capacity()), ETL_ERROR(flat_set_full));
bobbery 0:b47c2a7920c2 210 #endif
bobbery 0:b47c2a7920c2 211
bobbery 0:b47c2a7920c2 212 clear();
bobbery 0:b47c2a7920c2 213
bobbery 0:b47c2a7920c2 214 while (first != last)
bobbery 0:b47c2a7920c2 215 {
bobbery 0:b47c2a7920c2 216 insert(*first++);
bobbery 0:b47c2a7920c2 217 }
bobbery 0:b47c2a7920c2 218 }
bobbery 0:b47c2a7920c2 219
bobbery 0:b47c2a7920c2 220 //*********************************************************************
bobbery 0:b47c2a7920c2 221 /// Inserts a value to the flat_set.
bobbery 0:b47c2a7920c2 222 /// If asserts or exceptions are enabled, emits flat_set_full if the flat_set is already full.
bobbery 0:b47c2a7920c2 223 ///\param value The value to insert.
bobbery 0:b47c2a7920c2 224 //*********************************************************************
bobbery 0:b47c2a7920c2 225 std::pair<iterator, bool> insert(parameter_t value)
bobbery 0:b47c2a7920c2 226 {
bobbery 0:b47c2a7920c2 227 iterator i_element = lower_bound(value);
bobbery 0:b47c2a7920c2 228
bobbery 0:b47c2a7920c2 229 std::pair<iterator, bool> result(i_element, false);
bobbery 0:b47c2a7920c2 230
bobbery 0:b47c2a7920c2 231 // Doesn't already exist?
bobbery 0:b47c2a7920c2 232 if ((i_element == end() || (*i_element != value)))
bobbery 0:b47c2a7920c2 233 {
bobbery 0:b47c2a7920c2 234 ETL_ASSERT(!refset_t::full(), ETL_ERROR(flat_set_full));
bobbery 0:b47c2a7920c2 235
bobbery 0:b47c2a7920c2 236 value_type* pvalue = storage.allocate<value_type>();
bobbery 0:b47c2a7920c2 237 ::new (pvalue) value_type(value);
bobbery 0:b47c2a7920c2 238 ++construct_count;
bobbery 0:b47c2a7920c2 239 result = refset_t::insert_at(i_element, *pvalue);
bobbery 0:b47c2a7920c2 240 }
bobbery 0:b47c2a7920c2 241
bobbery 0:b47c2a7920c2 242 return result;
bobbery 0:b47c2a7920c2 243 }
bobbery 0:b47c2a7920c2 244
bobbery 0:b47c2a7920c2 245 //*********************************************************************
bobbery 0:b47c2a7920c2 246 /// Inserts a value to the flat_set.
bobbery 0:b47c2a7920c2 247 /// If asserts or exceptions are enabled, emits flat_set_full if the flat_set is already full.
bobbery 0:b47c2a7920c2 248 ///\param position The position to insert at.
bobbery 0:b47c2a7920c2 249 ///\param value The value to insert.
bobbery 0:b47c2a7920c2 250 //*********************************************************************
bobbery 0:b47c2a7920c2 251 iterator insert(iterator position, parameter_t value)
bobbery 0:b47c2a7920c2 252 {
bobbery 0:b47c2a7920c2 253 return insert(value).first;
bobbery 0:b47c2a7920c2 254 }
bobbery 0:b47c2a7920c2 255
bobbery 0:b47c2a7920c2 256 //*********************************************************************
bobbery 0:b47c2a7920c2 257 /// Inserts a range of values to the flat_set.
bobbery 0:b47c2a7920c2 258 /// If asserts or exceptions are enabled, emits flat_set_full if the flat_set does not have enough free space.
bobbery 0:b47c2a7920c2 259 ///\param position The position to insert at.
bobbery 0:b47c2a7920c2 260 ///\param first The first element to add.
bobbery 0:b47c2a7920c2 261 ///\param last The last + 1 element to add.
bobbery 0:b47c2a7920c2 262 //*********************************************************************
bobbery 0:b47c2a7920c2 263 template <class TIterator>
bobbery 0:b47c2a7920c2 264 void insert(TIterator first, TIterator last)
bobbery 0:b47c2a7920c2 265 {
bobbery 0:b47c2a7920c2 266 while (first != last)
bobbery 0:b47c2a7920c2 267 {
bobbery 0:b47c2a7920c2 268 insert(*first++);
bobbery 0:b47c2a7920c2 269 }
bobbery 0:b47c2a7920c2 270 }
bobbery 0:b47c2a7920c2 271
bobbery 0:b47c2a7920c2 272 //*********************************************************************
bobbery 0:b47c2a7920c2 273 /// Erases an element.
bobbery 0:b47c2a7920c2 274 ///\param key The key to erase.
bobbery 0:b47c2a7920c2 275 ///\return The number of elements erased. 0 or 1.
bobbery 0:b47c2a7920c2 276 //*********************************************************************
bobbery 0:b47c2a7920c2 277 size_t erase(parameter_t key)
bobbery 0:b47c2a7920c2 278 {
bobbery 0:b47c2a7920c2 279 iterator i_element = find(key);
bobbery 0:b47c2a7920c2 280
bobbery 0:b47c2a7920c2 281 if (i_element == end())
bobbery 0:b47c2a7920c2 282 {
bobbery 0:b47c2a7920c2 283 return 0;
bobbery 0:b47c2a7920c2 284 }
bobbery 0:b47c2a7920c2 285 else
bobbery 0:b47c2a7920c2 286 {
bobbery 0:b47c2a7920c2 287 i_element->~value_type();
bobbery 0:b47c2a7920c2 288 storage.release(etl::addressof(*i_element));
bobbery 0:b47c2a7920c2 289 refset_t::erase(i_element);
bobbery 0:b47c2a7920c2 290 --construct_count;
bobbery 0:b47c2a7920c2 291 return 1;
bobbery 0:b47c2a7920c2 292 }
bobbery 0:b47c2a7920c2 293 }
bobbery 0:b47c2a7920c2 294
bobbery 0:b47c2a7920c2 295 //*********************************************************************
bobbery 0:b47c2a7920c2 296 /// Erases an element.
bobbery 0:b47c2a7920c2 297 ///\param i_element Iterator to the element.
bobbery 0:b47c2a7920c2 298 //*********************************************************************
bobbery 0:b47c2a7920c2 299 void erase(iterator i_element)
bobbery 0:b47c2a7920c2 300 {
bobbery 0:b47c2a7920c2 301 i_element->~value_type();
bobbery 0:b47c2a7920c2 302 storage.release(etl::addressof(*i_element));
bobbery 0:b47c2a7920c2 303 refset_t::erase(i_element);
bobbery 0:b47c2a7920c2 304 --construct_count;
bobbery 0:b47c2a7920c2 305 }
bobbery 0:b47c2a7920c2 306
bobbery 0:b47c2a7920c2 307 //*********************************************************************
bobbery 0:b47c2a7920c2 308 /// Erases a range of elements.
bobbery 0:b47c2a7920c2 309 /// The range includes all the elements between first and last, including the
bobbery 0:b47c2a7920c2 310 /// element pointed by first, but not the one pointed by last.
bobbery 0:b47c2a7920c2 311 ///\param first Iterator to the first element.
bobbery 0:b47c2a7920c2 312 ///\param last Iterator to the last element.
bobbery 0:b47c2a7920c2 313 //*********************************************************************
bobbery 0:b47c2a7920c2 314 void erase(iterator first, iterator last)
bobbery 0:b47c2a7920c2 315 {
bobbery 0:b47c2a7920c2 316 iterator itr = first;
bobbery 0:b47c2a7920c2 317
bobbery 0:b47c2a7920c2 318 while (itr != last)
bobbery 0:b47c2a7920c2 319 {
bobbery 0:b47c2a7920c2 320 itr->~value_type();
bobbery 0:b47c2a7920c2 321 storage.release(etl::addressof(*itr));
bobbery 0:b47c2a7920c2 322 ++itr;
bobbery 0:b47c2a7920c2 323 --construct_count;
bobbery 0:b47c2a7920c2 324 }
bobbery 0:b47c2a7920c2 325
bobbery 0:b47c2a7920c2 326 refset_t::erase(first, last);
bobbery 0:b47c2a7920c2 327 }
bobbery 0:b47c2a7920c2 328
bobbery 0:b47c2a7920c2 329 //*************************************************************************
bobbery 0:b47c2a7920c2 330 /// Clears the flat_set.
bobbery 0:b47c2a7920c2 331 //*************************************************************************
bobbery 0:b47c2a7920c2 332 void clear()
bobbery 0:b47c2a7920c2 333 {
bobbery 0:b47c2a7920c2 334 erase(begin(), end());
bobbery 0:b47c2a7920c2 335 }
bobbery 0:b47c2a7920c2 336
bobbery 0:b47c2a7920c2 337 //*********************************************************************
bobbery 0:b47c2a7920c2 338 /// Finds an element.
bobbery 0:b47c2a7920c2 339 ///\param key The key to search for.
bobbery 0:b47c2a7920c2 340 ///\return An iterator pointing to the element or end() if not found.
bobbery 0:b47c2a7920c2 341 //*********************************************************************
bobbery 0:b47c2a7920c2 342 iterator find(parameter_t key)
bobbery 0:b47c2a7920c2 343 {
bobbery 0:b47c2a7920c2 344 return refset_t::find(key);
bobbery 0:b47c2a7920c2 345 }
bobbery 0:b47c2a7920c2 346
bobbery 0:b47c2a7920c2 347 //*********************************************************************
bobbery 0:b47c2a7920c2 348 /// Finds an element.
bobbery 0:b47c2a7920c2 349 ///\param key The key to search for.
bobbery 0:b47c2a7920c2 350 ///\return An iterator pointing to the element or end() if not found.
bobbery 0:b47c2a7920c2 351 //*********************************************************************
bobbery 0:b47c2a7920c2 352 const_iterator find(parameter_t key) const
bobbery 0:b47c2a7920c2 353 {
bobbery 0:b47c2a7920c2 354 return refset_t::find(key);
bobbery 0:b47c2a7920c2 355 }
bobbery 0:b47c2a7920c2 356
bobbery 0:b47c2a7920c2 357 //*********************************************************************
bobbery 0:b47c2a7920c2 358 /// Counts an element.
bobbery 0:b47c2a7920c2 359 ///\param key The key to search for.
bobbery 0:b47c2a7920c2 360 ///\return 1 if the key exists, otherwise 0.
bobbery 0:b47c2a7920c2 361 //*********************************************************************
bobbery 0:b47c2a7920c2 362 size_t count(parameter_t key) const
bobbery 0:b47c2a7920c2 363 {
bobbery 0:b47c2a7920c2 364 return refset_t::count(key);
bobbery 0:b47c2a7920c2 365 }
bobbery 0:b47c2a7920c2 366
bobbery 0:b47c2a7920c2 367 //*********************************************************************
bobbery 0:b47c2a7920c2 368 /// Finds the lower bound of a key
bobbery 0:b47c2a7920c2 369 ///\param key The key to search for.
bobbery 0:b47c2a7920c2 370 ///\return An iterator.
bobbery 0:b47c2a7920c2 371 //*********************************************************************
bobbery 0:b47c2a7920c2 372 iterator lower_bound(parameter_t key)
bobbery 0:b47c2a7920c2 373 {
bobbery 0:b47c2a7920c2 374 return refset_t::lower_bound(key);
bobbery 0:b47c2a7920c2 375 }
bobbery 0:b47c2a7920c2 376
bobbery 0:b47c2a7920c2 377 //*********************************************************************
bobbery 0:b47c2a7920c2 378 /// Finds the lower bound of a key
bobbery 0:b47c2a7920c2 379 ///\param key The key to search for.
bobbery 0:b47c2a7920c2 380 ///\return An iterator.
bobbery 0:b47c2a7920c2 381 //*********************************************************************
bobbery 0:b47c2a7920c2 382 const_iterator lower_bound(parameter_t key) const
bobbery 0:b47c2a7920c2 383 {
bobbery 0:b47c2a7920c2 384 return refset_t::lower_bound(key);
bobbery 0:b47c2a7920c2 385 }
bobbery 0:b47c2a7920c2 386
bobbery 0:b47c2a7920c2 387 //*********************************************************************
bobbery 0:b47c2a7920c2 388 /// Finds the upper bound of a key
bobbery 0:b47c2a7920c2 389 ///\param key The key to search for.
bobbery 0:b47c2a7920c2 390 ///\return An iterator.
bobbery 0:b47c2a7920c2 391 //*********************************************************************
bobbery 0:b47c2a7920c2 392 iterator upper_bound(parameter_t key)
bobbery 0:b47c2a7920c2 393 {
bobbery 0:b47c2a7920c2 394 return refset_t::upper_bound(key);
bobbery 0:b47c2a7920c2 395 }
bobbery 0:b47c2a7920c2 396
bobbery 0:b47c2a7920c2 397 //*********************************************************************
bobbery 0:b47c2a7920c2 398 /// Finds the upper bound of a key
bobbery 0:b47c2a7920c2 399 ///\param key The key to search for.
bobbery 0:b47c2a7920c2 400 ///\return An iterator.
bobbery 0:b47c2a7920c2 401 //*********************************************************************
bobbery 0:b47c2a7920c2 402 const_iterator upper_bound(parameter_t key) const
bobbery 0:b47c2a7920c2 403 {
bobbery 0:b47c2a7920c2 404 return refset_t::upper_bound(key);
bobbery 0:b47c2a7920c2 405 }
bobbery 0:b47c2a7920c2 406
bobbery 0:b47c2a7920c2 407 //*********************************************************************
bobbery 0:b47c2a7920c2 408 /// Finds the range of equal elements of a key
bobbery 0:b47c2a7920c2 409 ///\param key The key to search for.
bobbery 0:b47c2a7920c2 410 ///\return An iterator pair.
bobbery 0:b47c2a7920c2 411 //*********************************************************************
bobbery 0:b47c2a7920c2 412 std::pair<iterator, iterator> equal_range(parameter_t key)
bobbery 0:b47c2a7920c2 413 {
bobbery 0:b47c2a7920c2 414 return refset_t::equal_range(key);
bobbery 0:b47c2a7920c2 415 }
bobbery 0:b47c2a7920c2 416
bobbery 0:b47c2a7920c2 417 //*********************************************************************
bobbery 0:b47c2a7920c2 418 /// Finds the range of equal elements of a key
bobbery 0:b47c2a7920c2 419 ///\param key The key to search for.
bobbery 0:b47c2a7920c2 420 ///\return An iterator pair.
bobbery 0:b47c2a7920c2 421 //*********************************************************************
bobbery 0:b47c2a7920c2 422 std::pair<const_iterator, const_iterator> equal_range(parameter_t key) const
bobbery 0:b47c2a7920c2 423 {
bobbery 0:b47c2a7920c2 424 return refset_t::upper_bound(key);
bobbery 0:b47c2a7920c2 425 }
bobbery 0:b47c2a7920c2 426
bobbery 0:b47c2a7920c2 427 //*************************************************************************
bobbery 0:b47c2a7920c2 428 /// Assignment operator.
bobbery 0:b47c2a7920c2 429 //*************************************************************************
bobbery 0:b47c2a7920c2 430 iflat_set& operator = (const iflat_set& rhs)
bobbery 0:b47c2a7920c2 431 {
bobbery 0:b47c2a7920c2 432 if (&rhs != this)
bobbery 0:b47c2a7920c2 433 {
bobbery 0:b47c2a7920c2 434 assign(rhs.cbegin(), rhs.cend());
bobbery 0:b47c2a7920c2 435 }
bobbery 0:b47c2a7920c2 436
bobbery 0:b47c2a7920c2 437 return *this;
bobbery 0:b47c2a7920c2 438 }
bobbery 0:b47c2a7920c2 439
bobbery 0:b47c2a7920c2 440 //*************************************************************************
bobbery 0:b47c2a7920c2 441 /// Gets the current size of the flat_set.
bobbery 0:b47c2a7920c2 442 ///\return The current size of the flat_set.
bobbery 0:b47c2a7920c2 443 //*************************************************************************
bobbery 0:b47c2a7920c2 444 size_type size() const
bobbery 0:b47c2a7920c2 445 {
bobbery 0:b47c2a7920c2 446 return refset_t::size();
bobbery 0:b47c2a7920c2 447 }
bobbery 0:b47c2a7920c2 448
bobbery 0:b47c2a7920c2 449 //*************************************************************************
bobbery 0:b47c2a7920c2 450 /// Checks the 'empty' state of the flat_set.
bobbery 0:b47c2a7920c2 451 ///\return <b>true</b> if empty.
bobbery 0:b47c2a7920c2 452 //*************************************************************************
bobbery 0:b47c2a7920c2 453 bool empty() const
bobbery 0:b47c2a7920c2 454 {
bobbery 0:b47c2a7920c2 455 return refset_t::empty();
bobbery 0:b47c2a7920c2 456 }
bobbery 0:b47c2a7920c2 457
bobbery 0:b47c2a7920c2 458 //*************************************************************************
bobbery 0:b47c2a7920c2 459 /// Checks the 'full' state of the flat_set.
bobbery 0:b47c2a7920c2 460 ///\return <b>true</b> if full.
bobbery 0:b47c2a7920c2 461 //*************************************************************************
bobbery 0:b47c2a7920c2 462 bool full() const
bobbery 0:b47c2a7920c2 463 {
bobbery 0:b47c2a7920c2 464 return refset_t::full();
bobbery 0:b47c2a7920c2 465 }
bobbery 0:b47c2a7920c2 466
bobbery 0:b47c2a7920c2 467 //*************************************************************************
bobbery 0:b47c2a7920c2 468 /// Returns the capacity of the flat_set.
bobbery 0:b47c2a7920c2 469 ///\return The capacity of the flat_set.
bobbery 0:b47c2a7920c2 470 //*************************************************************************
bobbery 0:b47c2a7920c2 471 size_type capacity() const
bobbery 0:b47c2a7920c2 472 {
bobbery 0:b47c2a7920c2 473 return refset_t::capacity();
bobbery 0:b47c2a7920c2 474 }
bobbery 0:b47c2a7920c2 475
bobbery 0:b47c2a7920c2 476 //*************************************************************************
bobbery 0:b47c2a7920c2 477 /// Returns the maximum possible size of the flat_set.
bobbery 0:b47c2a7920c2 478 ///\return The maximum size of the flat_set.
bobbery 0:b47c2a7920c2 479 //*************************************************************************
bobbery 0:b47c2a7920c2 480 size_type max_size() const
bobbery 0:b47c2a7920c2 481 {
bobbery 0:b47c2a7920c2 482 return refset_t::max_size();
bobbery 0:b47c2a7920c2 483 }
bobbery 0:b47c2a7920c2 484
bobbery 0:b47c2a7920c2 485 //*************************************************************************
bobbery 0:b47c2a7920c2 486 /// Returns the remaining capacity.
bobbery 0:b47c2a7920c2 487 ///\return The remaining capacity.
bobbery 0:b47c2a7920c2 488 //*************************************************************************
bobbery 0:b47c2a7920c2 489 size_t available() const
bobbery 0:b47c2a7920c2 490 {
bobbery 0:b47c2a7920c2 491 return refset_t::available();
bobbery 0:b47c2a7920c2 492 }
bobbery 0:b47c2a7920c2 493
bobbery 0:b47c2a7920c2 494 protected:
bobbery 0:b47c2a7920c2 495
bobbery 0:b47c2a7920c2 496 //*********************************************************************
bobbery 0:b47c2a7920c2 497 /// Constructor.
bobbery 0:b47c2a7920c2 498 //*********************************************************************
bobbery 0:b47c2a7920c2 499 iflat_set(lookup_t& lookup_, storage_t& storage_)
bobbery 0:b47c2a7920c2 500 : refset_t(lookup_),
bobbery 0:b47c2a7920c2 501 storage(storage_)
bobbery 0:b47c2a7920c2 502 {
bobbery 0:b47c2a7920c2 503 }
bobbery 0:b47c2a7920c2 504
bobbery 0:b47c2a7920c2 505 private:
bobbery 0:b47c2a7920c2 506
bobbery 0:b47c2a7920c2 507 // Disable copy construction.
bobbery 0:b47c2a7920c2 508 iflat_set(const iflat_set&);
bobbery 0:b47c2a7920c2 509
bobbery 0:b47c2a7920c2 510 storage_t& storage;
bobbery 0:b47c2a7920c2 511
bobbery 0:b47c2a7920c2 512 /// Internal debugging.
bobbery 0:b47c2a7920c2 513 etl::debug_count construct_count;
bobbery 0:b47c2a7920c2 514 };
bobbery 0:b47c2a7920c2 515
bobbery 0:b47c2a7920c2 516 //***************************************************************************
bobbery 0:b47c2a7920c2 517 /// Equal operator.
bobbery 0:b47c2a7920c2 518 ///\param lhs Reference to the first flat_set.
bobbery 0:b47c2a7920c2 519 ///\param rhs Reference to the second flat_set.
bobbery 0:b47c2a7920c2 520 ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b>
bobbery 0:b47c2a7920c2 521 ///\ingroup flat_set
bobbery 0:b47c2a7920c2 522 //***************************************************************************
bobbery 0:b47c2a7920c2 523 template <typename T, typename TKeyCompare>
bobbery 0:b47c2a7920c2 524 bool operator ==(const etl::iflat_set<T, TKeyCompare>& lhs, const etl::iflat_set<T, TKeyCompare>& rhs)
bobbery 0:b47c2a7920c2 525 {
bobbery 0:b47c2a7920c2 526 return (lhs.size() == rhs.size()) && std::equal(lhs.begin(), lhs.end(), rhs.begin());
bobbery 0:b47c2a7920c2 527 }
bobbery 0:b47c2a7920c2 528
bobbery 0:b47c2a7920c2 529 //***************************************************************************
bobbery 0:b47c2a7920c2 530 /// Not equal operator.
bobbery 0:b47c2a7920c2 531 ///\param lhs Reference to the first flat_set.
bobbery 0:b47c2a7920c2 532 ///\param rhs Reference to the second flat_set.
bobbery 0:b47c2a7920c2 533 ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b>
bobbery 0:b47c2a7920c2 534 ///\ingroup flat_set
bobbery 0:b47c2a7920c2 535 //***************************************************************************
bobbery 0:b47c2a7920c2 536 template <typename T, typename TKeyCompare>
bobbery 0:b47c2a7920c2 537 bool operator !=(const etl::iflat_set<T, TKeyCompare>& lhs, const etl::iflat_set<T, TKeyCompare>& rhs)
bobbery 0:b47c2a7920c2 538 {
bobbery 0:b47c2a7920c2 539 return !(lhs == rhs);
bobbery 0:b47c2a7920c2 540 }
bobbery 0:b47c2a7920c2 541
bobbery 0:b47c2a7920c2 542 //***************************************************************************
bobbery 0:b47c2a7920c2 543 /// A flat_set implementation that uses a fixed size buffer.
bobbery 0:b47c2a7920c2 544 ///\tparam T The value type.
bobbery 0:b47c2a7920c2 545 ///\tparam TCompare The type to compare keys. Default = std::less<T>
bobbery 0:b47c2a7920c2 546 ///\tparam MAX_SIZE_ The maximum number of elements that can be stored.
bobbery 0:b47c2a7920c2 547 ///\ingroup flat_set
bobbery 0:b47c2a7920c2 548 //***************************************************************************
bobbery 0:b47c2a7920c2 549 template <typename T, const size_t MAX_SIZE_, typename TCompare = std::less<T> >
bobbery 0:b47c2a7920c2 550 class flat_set : public etl::iflat_set<T, TCompare>
bobbery 0:b47c2a7920c2 551 {
bobbery 0:b47c2a7920c2 552 public:
bobbery 0:b47c2a7920c2 553
bobbery 0:b47c2a7920c2 554 static const size_t MAX_SIZE = MAX_SIZE_;
bobbery 0:b47c2a7920c2 555
bobbery 0:b47c2a7920c2 556 //*************************************************************************
bobbery 0:b47c2a7920c2 557 /// Constructor.
bobbery 0:b47c2a7920c2 558 //*************************************************************************
bobbery 0:b47c2a7920c2 559 flat_set()
bobbery 0:b47c2a7920c2 560 : etl::iflat_set<T, TCompare>(lookup, storage)
bobbery 0:b47c2a7920c2 561 {
bobbery 0:b47c2a7920c2 562 }
bobbery 0:b47c2a7920c2 563
bobbery 0:b47c2a7920c2 564 //*************************************************************************
bobbery 0:b47c2a7920c2 565 /// Copy constructor.
bobbery 0:b47c2a7920c2 566 //*************************************************************************
bobbery 0:b47c2a7920c2 567 flat_set(const flat_set& other)
bobbery 0:b47c2a7920c2 568 : etl::iflat_set<T, TCompare>(lookup, storage)
bobbery 0:b47c2a7920c2 569 {
bobbery 0:b47c2a7920c2 570 etl::iflat_set<T, TCompare>::assign(other.cbegin(), other.cend());
bobbery 0:b47c2a7920c2 571 }
bobbery 0:b47c2a7920c2 572
bobbery 0:b47c2a7920c2 573 //*************************************************************************
bobbery 0:b47c2a7920c2 574 /// Constructor, from an iterator range.
bobbery 0:b47c2a7920c2 575 ///\tparam TIterator The iterator type.
bobbery 0:b47c2a7920c2 576 ///\param first The iterator to the first element.
bobbery 0:b47c2a7920c2 577 ///\param last The iterator to the last element + 1.
bobbery 0:b47c2a7920c2 578 //*************************************************************************
bobbery 0:b47c2a7920c2 579 template <typename TIterator>
bobbery 0:b47c2a7920c2 580 flat_set(TIterator first, TIterator last)
bobbery 0:b47c2a7920c2 581 : etl::iflat_set<T, TCompare>(lookup, storage)
bobbery 0:b47c2a7920c2 582 {
bobbery 0:b47c2a7920c2 583 etl::iflat_set<T, TCompare>::assign(first, last);
bobbery 0:b47c2a7920c2 584 }
bobbery 0:b47c2a7920c2 585
bobbery 0:b47c2a7920c2 586 //*************************************************************************
bobbery 0:b47c2a7920c2 587 /// Destructor.
bobbery 0:b47c2a7920c2 588 //*************************************************************************
bobbery 0:b47c2a7920c2 589 ~flat_set()
bobbery 0:b47c2a7920c2 590 {
bobbery 0:b47c2a7920c2 591 etl::iflat_set<T, TCompare>::clear();
bobbery 0:b47c2a7920c2 592 }
bobbery 0:b47c2a7920c2 593
bobbery 0:b47c2a7920c2 594 //*************************************************************************
bobbery 0:b47c2a7920c2 595 /// Assignment operator.
bobbery 0:b47c2a7920c2 596 //*************************************************************************
bobbery 0:b47c2a7920c2 597 flat_set& operator = (const flat_set& rhs)
bobbery 0:b47c2a7920c2 598 {
bobbery 0:b47c2a7920c2 599 if (&rhs != this)
bobbery 0:b47c2a7920c2 600 {
bobbery 0:b47c2a7920c2 601 etl::iflat_set<T, TCompare>::assign(rhs.cbegin(), rhs.cend());
bobbery 0:b47c2a7920c2 602 }
bobbery 0:b47c2a7920c2 603
bobbery 0:b47c2a7920c2 604 return *this;
bobbery 0:b47c2a7920c2 605 }
bobbery 0:b47c2a7920c2 606
bobbery 0:b47c2a7920c2 607 private:
bobbery 0:b47c2a7920c2 608
bobbery 0:b47c2a7920c2 609 typedef typename etl::iflat_set<T, TCompare>::value_type node_t;
bobbery 0:b47c2a7920c2 610
bobbery 0:b47c2a7920c2 611 // The pool of nodes.
bobbery 0:b47c2a7920c2 612 etl::pool<node_t, MAX_SIZE> storage;
bobbery 0:b47c2a7920c2 613
bobbery 0:b47c2a7920c2 614 // The vector that stores pointers to the nodes.
bobbery 0:b47c2a7920c2 615 etl::vector<node_t*, MAX_SIZE> lookup;
bobbery 0:b47c2a7920c2 616 };
bobbery 0:b47c2a7920c2 617 }
bobbery 0:b47c2a7920c2 618
bobbery 0:b47c2a7920c2 619 #undef ETL_FILE
bobbery 0:b47c2a7920c2 620
bobbery 0:b47c2a7920c2 621 #endif
bobbery 0:b47c2a7920c2 622