FastLED 3.9.15
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
map.h
Go to the documentation of this file.
1#pragma once
2
3#include <stddef.h>
4#include <stdint.h>
5
6#include "fl/assert.h"
7#include "fl/insert_result.h"
8#include "fl/namespace.h"
9#include "fl/pair.h"
10#include "fl/template_magic.h"
11#include "fl/vector.h"
12
13namespace fl {
14
15template <typename T> struct DefaultLess {
16 bool operator()(const T &a, const T &b) const { return a < b; }
17};
18
19// A simple unordered map implementation with a fixed size.
20// The user is responsible for making sure that the inserts
21// do not exceed the capacity of the set, otherwise they will
22// fail. Because of this limitation, this set is not a drop in
23// replacement for std::map.
24template <typename Key, typename Value, size_t N> class FixedMap {
25 public:
27
31
32 // Constructor
33 constexpr FixedMap() = default;
34
35 iterator begin() { return data.begin(); }
36 iterator end() { return data.end(); }
37 const_iterator begin() const { return data.begin(); }
38 const_iterator end() const { return data.end(); }
39
40 iterator find(const Key &key) {
41 for (auto it = begin(); it != end(); ++it) {
42 if (it->first == key) {
43 return it;
44 }
45 }
46 return end();
47 }
48
49 const_iterator find(const Key &key) const {
50 for (auto it = begin(); it != end(); ++it) {
51 if (it->first == key) {
52 return it;
53 }
54 }
55 return end();
56 }
57
58 template <typename Less> iterator lowest(Less less_than = Less()) {
60 for (iterator it = begin(); it != end(); ++it) {
61 if (lowest == end() || less_than(it->first, lowest->first)) {
62 lowest = it;
63 }
64 }
65 return lowest;
66 }
67
68 template <typename Less>
69 const_iterator lowest(Less less_than = Less()) const {
71 for (const_iterator it = begin(); it != end(); ++it) {
72 if (lowest == end() || less_than(it->first, lowest->first)) {
73 lowest = it;
74 }
75 }
76 return lowest;
77 }
78
79 template <typename Less> iterator highest(Less less_than = Less()) {
81 for (iterator it = begin(); it != end(); ++it) {
82 if (highest == end() || less_than(highest->first, it->first)) {
83 highest = it;
84 }
85 }
86 return highest;
87 }
88
89 template <typename Less>
90 const_iterator highest(Less less_than = Less()) const {
92 for (const_iterator it = begin(); it != end(); ++it) {
93 if (highest == end() || less_than(highest->first, it->first)) {
94 highest = it;
95 }
96 }
97 return highest;
98 }
99
100 // We differ from the std standard here so that we don't allow
101 // dereferencing the end iterator.
102 bool get(const Key &key, Value *value) const {
103 const_iterator it = find(key);
104 if (it != end()) {
105 *value = it->second;
106 return true;
107 }
108 return false;
109 }
110
111 Value get(const Key &key, bool *has = nullptr) const {
112 const_iterator it = find(key);
113 if (it != end()) {
114 if (has) {
115 *has = true;
116 }
117 return it->second;
118 }
119 if (has) {
120 *has = false;
121 }
122 return Value();
123 }
124
125 Pair<bool, iterator> insert(const Key &key, const Value &value,
126 InsertResult *result = nullptr) {
127 iterator it = find(key);
128 if (it != end()) {
129 if (result) {
130 *result = InsertResult::kExists;
131 }
132 // return false;
133 return {false, it};
134 }
135 if (data.size() < N) {
136 data.push_back(PairKV(key, value));
137 if (result) {
138 *result = InsertResult::kInserted;
139 }
140 // return true;
141 return {true, data.end() - 1};
142 }
143 if (result) {
144 *result = InsertResult::kMaxSize;
145 }
146 // return false;
147 return {false, end()};
148 }
149
150 bool update(const Key &key, const Value &value,
151 bool insert_if_missing = true) {
152 iterator it = find(key);
153 if (it != end()) {
154 it->second = value;
155 return true;
156 } else if (insert_if_missing) {
157 return insert(key, value).first;
158 }
159 return false;
160 }
161
162 Value &operator[](const Key &key) {
163 iterator it = find(key);
164 if (it != end()) {
165 return it->second;
166 }
167 data.push_back(PairKV(key, Value()));
168 return data.back().second;
169 }
170
171 const Value &operator[](const Key &key) const {
172 const_iterator it = find(key);
173 if (it != end()) {
174 return it->second;
175 }
176 static Value default_value;
177 return default_value;
178 }
179
180 bool next(const Key &key, Key *next_key,
181 bool allow_rollover = false) const {
182 const_iterator it = find(key);
183 if (it != end()) {
184 ++it;
185 if (it != end()) {
186 *next_key = it->first;
187 return true;
188 } else if (allow_rollover && !empty()) {
189 *next_key = begin()->first;
190 return true;
191 }
192 }
193 return false;
194 }
195
196 bool prev(const Key &key, Key *prev_key,
197 bool allow_rollover = false) const {
198 const_iterator it = find(key);
199 if (it != end()) {
200 if (it != begin()) {
201 --it;
202 *prev_key = it->first;
203 return true;
204 } else if (allow_rollover && !empty()) {
205 *prev_key = data[data.size() - 1].first;
206 return true;
207 }
208 }
209 return false;
210 }
211
212 // Get the current size of the vector
213 constexpr size_t size() const { return data.size(); }
214
215 constexpr bool empty() const { return data.empty(); }
216
217 // Get the capacity of the vector
218 constexpr size_t capacity() const { return N; }
219
220 // Clear the vector
221 void clear() { data.clear(); }
222
223 bool has(const Key &it) const { return find(it) != end(); }
224
225 bool contains(const Key &key) const { return has(key); }
226
227 private:
229};
230
231// Closest data structure to an std::map. Always sorted.
232// O(n + log(n)) for insertions, O(log(n)) for searches, O(n) for iteration.
233template <typename Key, typename Value, typename Less = fl::DefaultLess<Key>>
235 private:
236 struct Pair {
238 Value second;
239
240 Pair(const Key &k = Key(), const Value &v = Value())
241 : first(k), second(v) {}
242 };
243
244 struct PairLess {
245 Less less;
246 bool operator()(const Pair &a, const Pair &b) const {
247 return less(a.first, b.first);
248 }
249 };
250
252
253 public:
258
259 SortedHeapMap(Less less = Less()) : data(PairLess{less}) {}
260
261 void setMaxSize(size_t n) { data.setMaxSize(n); }
262
263 void reserve(size_t n) { data.reserve(n); }
264
265 bool insert(const Key &key, const Value &value,
266 InsertResult *result = nullptr) {
267 return data.insert(Pair(key, value), result);
268 }
269
270 void update(const Key &key, const Value &value) {
271 if (!insert(key, value)) {
272 iterator it = find(key);
273 it->second = value;
274 }
275 }
276
277 void swap(SortedHeapMap &other) { data.swap(other.data); }
278
279 Value &at(const Key &key) {
280 iterator it = find(key);
281 return it->second;
282 }
283
284 // Matches FixedMap<>::get(...).
285 bool get(const Key &key, Value *value) const {
286 const_iterator it = find(key);
287 if (it != end()) {
288 *value = it->second;
289 return true;
290 }
291 return false;
292 }
293
294 bool has(const Key &key) const { return data.has(Pair(key)); }
295
296 bool contains(const Key &key) const { return has(key); }
297
298 bool operator==(const SortedHeapMap &other) const {
299 if (size() != other.size()) {
300 return false;
301 }
302 for (const_iterator it = begin(), other_it = other.begin(); it != end();
303 ++it, ++other_it) {
304 if (it->first != other_it->first ||
305 it->second != other_it->second) {
306 return false;
307 }
308 }
309 return true;
310 }
311
312 bool operator!=(const SortedHeapMap &other) const {
313 return !(*this == other);
314 }
315
316 size_t size() const { return data.size(); }
317 bool empty() const { return data.empty(); }
318 bool full() const { return data.full(); }
319 size_t capacity() const { return data.capacity(); }
320 void clear() { data.clear(); }
321
322 // begin, dend
323 iterator begin() { return data.begin(); }
324 iterator end() { return data.end(); }
325 const_iterator begin() const { return data.begin(); }
326 const_iterator end() const { return data.end(); }
327
328 iterator find(const Key &key) { return data.find(Pair(key)); }
329 const_iterator find(const Key &key) const { return data.find(Pair(key)); }
330
331 bool erase(const Key &key) { return data.erase(Pair(key)); }
332 bool erase(iterator it) { return data.erase(it); }
333
334 iterator lower_bound(const Key &key) { return data.lower_bound(Pair(key)); }
335
336 const_iterator lower_bound(const Key &key) const {
337 return data.lower_bound(Pair(key));
338 }
339
341 iterator it = lower_bound(key);
342 if (it != end() && it->first == key) {
343 ++it;
344 }
345 return it;
346 }
347
348 const_iterator upper_bound(const Key &key) const {
349 const_iterator it = lower_bound(key);
350 if (it != end() && it->first == key) {
351 ++it;
352 }
353 return it;
354 }
355
356 Pair &front() { return data.front(); }
357 const Pair &front() const { return data.front(); }
358 Pair &back() { return data.back(); }
359 const Pair &back() const { return data.back(); }
360
361 Value &operator[](const Key &key) {
362 iterator it = find(key);
363 if (it != end()) {
364 return it->second;
365 }
366 Pair pair(key, Value());
367 bool ok = data.insert(pair);
368 FASTLED_ASSERT(ok, "Failed to insert into SortedHeapMap");
369 return data.find(pair)->second; // TODO: optimize.
370 }
371};
372
373} // namespace fl
bool contains(const Key &key) const
Definition map.h:225
Pair< bool, iterator > insert(const Key &key, const Value &value, InsertResult *result=nullptr)
Definition map.h:125
VectorType::iterator iterator
Definition map.h:29
iterator end()
Definition map.h:36
const_iterator begin() const
Definition map.h:37
bool prev(const Key &key, Key *prev_key, bool allow_rollover=false) const
Definition map.h:196
iterator lowest(Less less_than=Less())
Definition map.h:58
iterator begin()
Definition map.h:35
Value & operator[](const Key &key)
Definition map.h:162
constexpr size_t size() const
Definition map.h:213
const_iterator lowest(Less less_than=Less()) const
Definition map.h:69
const_iterator highest(Less less_than=Less()) const
Definition map.h:90
constexpr size_t capacity() const
Definition map.h:218
iterator find(const Key &key)
Definition map.h:40
bool next(const Key &key, Key *next_key, bool allow_rollover=false) const
Definition map.h:180
const_iterator find(const Key &key) const
Definition map.h:49
iterator highest(Less less_than=Less())
Definition map.h:79
bool update(const Key &key, const Value &value, bool insert_if_missing=true)
Definition map.h:150
const Value & operator[](const Key &key) const
Definition map.h:171
constexpr bool empty() const
Definition map.h:215
Value get(const Key &key, bool *has=nullptr) const
Definition map.h:111
FixedVector< PairKV, N > VectorType
Definition map.h:28
VectorType::const_iterator const_iterator
Definition map.h:30
void clear()
Definition map.h:221
constexpr FixedMap()=default
bool get(const Key &key, Value *value) const
Definition map.h:102
fl::Pair< Key, Value > PairKV
Definition map.h:26
const_iterator end() const
Definition map.h:38
const PairKV * const_iterator
Definition vector.h:80
iterator upper_bound(const Key &key)
Definition map.h:340
bool full() const
Definition map.h:318
const_iterator begin() const
Definition map.h:325
const_iterator end() const
Definition map.h:326
void update(const Key &key, const Value &value)
Definition map.h:270
bool has(const Key &key) const
Definition map.h:294
bool erase(iterator it)
Definition map.h:332
iterator begin()
Definition map.h:323
const Pair & back() const
Definition map.h:359
bool erase(const Key &key)
Definition map.h:331
void swap(SortedHeapMap &other)
Definition map.h:277
iterator end()
Definition map.h:324
const_iterator lower_bound(const Key &key) const
Definition map.h:336
SortedHeapMap(Less less=Less())
Definition map.h:259
SortedHeapVector< Pair, PairLess >::iterator iterator
Definition map.h:254
bool contains(const Key &key) const
Definition map.h:296
iterator lower_bound(const Key &key)
Definition map.h:334
bool operator!=(const SortedHeapMap &other) const
Definition map.h:312
Pair value_type
Definition map.h:257
size_t capacity() const
Definition map.h:319
bool get(const Key &key, Value *value) const
Definition map.h:285
const_iterator upper_bound(const Key &key) const
Definition map.h:348
size_t size() const
Definition map.h:316
bool insert(const Key &key, const Value &value, InsertResult *result=nullptr)
Definition map.h:265
Value & operator[](const Key &key)
Definition map.h:361
const_iterator find(const Key &key) const
Definition map.h:329
Pair & front()
Definition map.h:356
iterator find(const Key &key)
Definition map.h:328
SortedHeapVector< Pair, PairLess > data
Definition map.h:251
Value & at(const Key &key)
Definition map.h:279
void reserve(size_t n)
Definition map.h:263
SortedHeapVector< Pair, PairLess >::const_iterator const_iterator
Definition map.h:256
Pair & back()
Definition map.h:358
const Pair & front() const
Definition map.h:357
void clear()
Definition map.h:320
bool empty() const
Definition map.h:317
bool operator==(const SortedHeapMap &other) const
Definition map.h:298
void setMaxSize(size_t n)
Definition map.h:261
HeapVector< T >::const_iterator const_iterator
Definition vector.h:675
HeapVector< T >::iterator iterator
Definition vector.h:674
Implements the FastLED namespace macros.
Pair< Key, Value > pair
Definition pair.h:13
InsertResult
@ kMaxSize
@ kExists
@ kInserted
Implements a simple red square effect for 2D LED grids.
Definition crgb.h:16
Definition Keyboard.h:22
bool operator()(const T &a, const T &b) const
Definition map.h:16
Key first
Definition pair.h:6
Value second
Definition pair.h:7
Definition pair.h:5
Pair(const Key &k=Key(), const Value &v=Value())
Definition map.h:240
bool operator()(const Pair &a, const Pair &b) const
Definition map.h:246
Binary function object that returns whether the first argument is less than the second.
Definition functional.h:15