FastLED 3.9.15
Loading...
Searching...
No Matches
vector.h
Go to the documentation of this file.
1#pragma once
2
3#include <stddef.h>
4#include <stdint.h>
5#include <string.h>
6
7#include "fl/functional.h"
8#include "fl/insert_result.h"
9#include "fl/math_macros.h"
10#include "fl/namespace.h"
11#include "fl/scoped_ptr.h"
12#include "fl/type_traits.h"
13#include "inplacenew.h"
14
15namespace fl {
16
17// Aligned memory block for inlined data structures.
18template <typename T, size_t N> struct InlinedMemoryBlock {
19 // using MemoryType = uinptr_t;
20 typedef uintptr_t MemoryType;
21 enum {
22 kTotalBytes = N * sizeof(T),
23 kAlign = sizeof(MemoryType),
25 (kTotalBytes % kAlign) ? (kAlign - (kTotalBytes % kAlign)) : 0,
27 };
28
30 memset(mMemoryBlock, 0, sizeof(mMemoryBlock));
31#ifdef FASTLED_TESTING
32 __data = memory();
33#endif
34 }
35
36 InlinedMemoryBlock(const InlinedMemoryBlock &other) = default;
38
39 // uint32_t mRaw[N * sizeof(T)/sizeof(MemoryType) + kExtraSize];
40 // align this to the size of MemoryType.
41 // uint32_t mMemoryBlock[kTotalSize] = {0};
43
44 T *memory() {
45 MemoryType *begin = &mMemoryBlock[0];
46 uintptr_t shift_up =
47 reinterpret_cast<uintptr_t>(begin) & (sizeof(MemoryType) - 1);
48 MemoryType *raw = begin + shift_up;
49 return reinterpret_cast<T *>(raw);
50 }
51
52 const T *memory() const {
53 const MemoryType *begin = &mMemoryBlock[0];
54 const uintptr_t shift_up =
55 reinterpret_cast<uintptr_t>(begin) & (sizeof(MemoryType) - 1);
56 const MemoryType *raw = begin + shift_up;
57 return reinterpret_cast<const T *>(raw);
58 }
59
60#ifdef FASTLED_TESTING
61 T *__data = nullptr;
62#endif
63};
64
65// A fixed sized vector. The user is responsible for making sure that the
66// inserts do not exceed the capacity of the vector, otherwise they will fail.
67// Because of this limitation, this vector is not a drop in replacement for
68// std::vector. However it used for vector_inlined<T, N> which allows spill over
69// to a heap vector when size > N.
70template <typename T, size_t N> class FixedVector {
71 private:
73
74 T *memory() { return mMemoryBlock.memory(); }
75
76 const T *memory() const { return mMemoryBlock.memory(); }
77
78 public:
79 typedef T *iterator;
80 typedef const T *const_iterator;
81 // Constructor
82 constexpr FixedVector() : current_size(0) {}
83
84 FixedVector(const T (&values)[N]) : current_size(N) {
85 assign_array(values, N);
86 }
87
89 fl::swap(*this, other);
90 other.clear();
91 }
92
94 assign_array(other.memory(), other.current_size);
95 }
96
97 template <size_t M> FixedVector(const T (&values)[M]) : current_size(M) {
98 static_assert(M <= N, "Too many elements for FixedVector");
99 assign_array(values, M);
100 }
101
103 if (this != &other) {
104 assign_array(other.memory(), other.current_size);
105 }
106 return *this;
107 }
108
109 // Destructor
111
112 // Array subscript operator
113 T &operator[](size_t index) { return memory()[index]; }
114
115 // Const array subscript operator
116 const T &operator[](size_t index) const {
117 if (index >= current_size) {
118 const T *out = nullptr;
119 return *out; // Cause a nullptr dereference
120 }
121 return memory()[index];
122 }
123
124 void resize(size_t n) {
125 while (current_size < n) {
126 push_back(T());
127 }
128 while (current_size > n) {
129 pop_back();
130 }
131 }
132
133 // Get the current size of the vector
134 constexpr size_t size() const { return current_size; }
135
136 constexpr bool empty() const { return current_size == 0; }
137
138 // Get the capacity of the vector
139 constexpr size_t capacity() const { return N; }
140
141 // Add an element to the end of the vector
142 void push_back(const T &value) {
143 if (current_size < N) {
144 void *mem = &memory()[current_size];
145 new (mem) T(value);
146 ++current_size;
147 }
148 }
149
150 void reserve(size_t n) {
151 if (n > N) {
152 // This is a no-op for fixed size vectors
153 return;
154 }
155 }
156
157 void assign_array(const T *values, size_t count) {
158 clear();
159 for (size_t i = 0; i < count; ++i) {
160 push_back(values[i]);
161 }
162 }
163
165 clear();
166 for (const_iterator it = begin; it != end; ++it) {
167 push_back(*it);
168 }
169 }
170
171 // Remove the last element from the vector
172 void pop_back() {
173 if (current_size > 0) {
174 --current_size;
175 memory()[current_size].~T();
176 }
177 }
178
179 // Clear the vector
180 void clear() {
181 while (current_size > 0) {
182 pop_back();
183 }
184 }
185
186 // Erase the element at the given iterator position
188 if (pos != end()) {
189 pos->~T();
190 // shift all elements to the left
191 for (iterator p = pos; p != end() - 1; ++p) {
192 new (p)
193 T(*(p + 1)); // Use copy constructor instead of std::move
194 (p + 1)->~T();
195 }
196 --current_size;
197 }
198 return pos;
199 }
200
201 iterator erase(const T &value) {
202 iterator it = find(value);
203 if (it != end()) {
204 erase(it);
205 }
206 return it;
207 }
208
209 iterator find(const T &value) {
210 for (iterator it = begin(); it != end(); ++it) {
211 if (*it == value) {
212 return it;
213 }
214 }
215 return end();
216 }
217
218 template <typename Predicate> iterator find_if(Predicate pred) {
219 for (iterator it = begin(); it != end(); ++it) {
220 if (pred(*it)) {
221 return it;
222 }
223 }
224 return end();
225 }
226
227 bool insert(iterator pos, const T &value) {
228 if (current_size < N) {
229 // shift all elements to the right
230 // for (iterator p = end(); p != pos; --p) {
231 // new (p) T(*(p - 1)); // Use copy constructor instead of
232 // std::move (p - 1)->~T();
233 // }
234 // new (pos) T(value);
235 // shift all element from pos to end to the right
236 for (iterator p = end(); p != pos; --p) {
237 // LOOKS LIKE THERE ARE BUGS AROUND THIS INSERT FUNCTION.
238 // I'VE TRIED TO UPGRADE THE CODE TO USE TEMPORARIES BUT
239 // IT SEEMS TO NOT WORK. IT COULD POSSIBLY DO WITH ALIGNMENT
240 // OF THE DATA. THIS IMPL HAS ISSUES WITH THE NEW PLACE
241 // OPERATION.
242 T temp = *(p - 1);
243 (p)->~T(); // Destroy the current element
244 // Clear the memory
245 void *vp = static_cast<void *>(p);
246 memset(vp, 0, sizeof(T));
247 new (p) T(temp); // Use copy constructor instead of std::move
248 //(p - 1)->~T();
249 }
250 ++current_size;
251 // now insert the new value
252 new (pos) T(value);
253 return true;
254 }
255 return false;
256 }
257
258 const_iterator find(const T &value) const {
259 for (const_iterator it = begin(); it != end(); ++it) {
260 if (*it == value) {
261 return it;
262 }
263 }
264 return end();
265 }
266
267 iterator data() { return begin(); }
268
269 const_iterator data() const { return begin(); }
270
271 bool has(const T &value) const { return find(value) != end(); }
272
273 // Access to first and last elements
274 T &front() { return memory()[0]; }
275
276 const T &front() const { return memory()[0]; }
277
278 T &back() { return memory()[current_size - 1]; }
279
280 const T &back() const { return memory()[current_size - 1]; }
281
282 // Iterator support
283 iterator begin() { return &memory()[0]; }
284 const_iterator begin() const { return &memory()[0]; }
285 iterator end() { return &memory()[current_size]; }
286 const_iterator end() const { return &memory()[current_size]; }
287
288 void swap(FixedVector<T, N> &other) {
289 if (this != &other) {
290 const int max_size = MAX(current_size, other.current_size);
291 for (int i = 0; i < max_size; ++i) {
292 fl::swap(memory()[i], other.memory()[i]);
293 }
294 // swap the sizes
295 size_t temp_size = current_size;
297 other.current_size = temp_size;
298 }
299 }
300
301 private:
302 size_t current_size = 0;
303};
304
305template <typename T> class HeapVector {
306 private:
308
309 size_t mCapacity = 0;
310 size_t mSize = 0;
311
312 public:
313 typedef T *iterator;
314 typedef const T *const_iterator;
315
319 T &operator*() { return *(it - 1); }
321 --it;
322 return *this;
323 }
324 bool operator!=(const reverse_iterator &other) const {
325 return it != other.it;
326 }
327 };
328
329 // Constructor
330 HeapVector(size_t size = 0, const T &value = T()) : mCapacity(size) {
331 mArray.reset(new T[mCapacity]());
332 for (size_t i = 0; i < size; ++i) {
333 mArray[i] = value;
334 }
335 mSize = size;
336 }
337 HeapVector(const HeapVector<T> &other) {
338 reserve(other.size());
339 assign(other.begin(), other.end());
340 }
342 this->swap(other);
343 other.clear();
344 }
346 const HeapVector<T> &other) { // cppcheck-suppress operatorEqVarError
347 if (this != &other) {
348 assign(other.begin(), other.end());
349 }
350 return *this;
351 }
352
353 template <size_t N> HeapVector(T (&values)[N]) {
354 T *begin = &values[0];
355 T *end = &values[N];
356 assign(begin, end);
357 }
358
359 // Destructor
361
362 void ensure_size(size_t n) {
363 if (n > mCapacity) {
364 size_t new_capacity = (3 * mCapacity) / 2;
365 if (new_capacity < n) {
366 new_capacity = n;
367 }
368 T *ptr = new T[new_capacity]();
369 fl::scoped_array<T> new_array(ptr);
370 for (size_t i = 0; i < mSize; ++i) {
371 new_array[i] = mArray[i];
372 }
373 // mArray = std::move(new_array);
374 mArray.reset();
375 mArray.reset(new_array.release());
376 mCapacity = new_capacity;
377 }
378 }
379
380 void reserve(size_t n) {
381 if (n > mCapacity) {
382 ensure_size(n);
383 }
384 }
385
386 void resize(size_t n) {
387 if (mSize == n) {
388 return;
389 }
390 if (n > mCapacity) {
391 ensure_size(n);
392 }
393 while (mSize < n) {
394 push_back(T());
395 }
396 while (mSize > n) {
397 pop_back();
398 }
399 }
400
401 void resize(size_t n, const T &value) {
402 mArray.reset();
403 mArray.reset(new T[n]());
404 for (size_t i = 0; i < n; ++i) {
405 mArray[i] = value;
406 }
407 mCapacity = n;
408 mSize = n;
409 }
410
411 template <typename InputIt,
413 void assign(InputIt begin, InputIt end) {
414 clear();
415 reserve(end - begin);
416 for (InputIt it = begin; it != end; ++it) {
417 push_back(*it);
418 }
419 }
420
421 void assign(size_t new_cap, const T &value) {
422 clear();
423 reserve(new_cap);
424 while (size() < new_cap) {
425 push_back(value);
426 }
427 }
428
429 // Array access operators
430 T &operator[](size_t index) { return mArray[index]; }
431
432 const T &operator[](size_t index) const { return mArray[index]; }
433
434 // Capacity and size methods
435 size_t size() const { return mSize; }
436
437 bool empty() const { return mSize == 0; }
438
439 size_t capacity() const { return mCapacity; }
440
441 // Element addition/removal
442 void push_back(const T &value) {
443 ensure_size(mSize + 1);
444 if (mSize < mCapacity) {
445 mArray[mSize] = value;
446 ++mSize;
447 }
448 }
449
450 void pop_back() {
451 if (mSize > 0) {
452 --mSize;
453 mArray[mSize] = T();
454 }
455 }
456
457 void clear() {
458 while (mSize > 0) {
459 pop_back();
460 }
461 }
462
463 // Iterator methods
464 iterator begin() { return &mArray[0]; }
465 const_iterator begin() const { return &mArray[0]; }
466 iterator end() { return &mArray[mSize]; }
467 const_iterator end() const { return &mArray[mSize]; }
468
469 reverse_iterator rbegin() { return reverse_iterator(end()); }
470
471 reverse_iterator rend() { return reverse_iterator(begin()); }
472
473 // Element access
474 T &front() { return mArray[0]; }
475
476 const T &front() const { return mArray[0]; }
477
478 T &back() { return mArray[mSize - 1]; }
479
480 const T &back() const { return mArray[mSize - 1]; }
481
482 // Search and modification
483 iterator find(const T &value) {
484 for (iterator it = begin(); it != end(); ++it) {
485 if (*it == value) {
486 return it;
487 }
488 }
489 return end();
490 }
491
492 const_iterator find(const T &value) const {
493 for (const_iterator it = begin(); it != end(); ++it) {
494 if (*it == value) {
495 return it;
496 }
497 }
498 return end();
499 }
500
501 template <typename Predicate> iterator find_if(Predicate pred) {
502 for (iterator it = begin(); it != end(); ++it) {
503 if (pred(*it)) {
504 return it;
505 }
506 }
507 return end();
508 }
509
510 bool has(const T &value) const { return find(value) != end(); }
511
512 bool erase(iterator pos, T *out_value = nullptr) {
513 if (pos == end() || empty()) {
514 return false;
515 }
516 if (out_value) {
517 *out_value = *pos;
518 }
519 while (pos != end() - 1) {
520 *pos = *(pos + 1);
521 ++pos;
522 }
523 back() = T();
524 --mSize;
525 return true;
526 }
527
528 void erase(const T &value) {
529 iterator it = find(value);
530 if (it != end()) {
531 erase(it);
532 }
533 }
534
535 void swap(HeapVector<T> &other) {
536 T *temp = mArray.release();
537 size_t temp_size = mSize;
538 size_t temp_capacity = mCapacity;
539 T *temp2 = other.mArray.release();
540 mArray.reset(temp2);
541 other.mArray.reset(temp);
542 mSize = other.mSize;
543 mCapacity = other.mCapacity;
544 other.mSize = temp_size;
545 other.mCapacity = temp_capacity;
546 }
547
548 void swap(iterator a, iterator b) {
549 T temp = *a;
550 *a = *b;
551 *b = temp;
552 }
553
554 bool full() const { return mSize >= mCapacity; }
555
556 bool insert(iterator pos, const T &value) {
557 // TODO: Introduce mMaxSize (and move it from SortedVector to here)
558 // push back and swap into place.
559 size_t target_idx = pos - begin();
560 push_back(value);
561 auto last = end() - 1;
562 for (size_t curr_idx = last - begin(); curr_idx > target_idx;
563 --curr_idx) {
564 auto first = begin() + curr_idx - 1;
565 auto second = begin() + curr_idx;
566 swap(first, second);
567 }
568 return true;
569 }
570
571 // void assign(const T* values, size_t count) {
572 // clear();
573 // if (!mArray) {
574 // mArray.reset(new T[count]);
575 // }
576 // mCapacity = count;
577 // assign(values, values + count);
578 // }
579
580 // void assign(size_t new_cap, const T &value) {
581 // clear();
582 // reserve(new_cap);
583 // while (size() < new_cap) {
584 // push_back(value);
585 // }
586 // }
587
588 // 2) the iterator‐range overload, only enabled when InputIt is *not*
589 // integral
590 // template <typename InputIt>
591 // void assign(InputIt begin, InputIt end) {
592 // clear();
593 // auto n = static_cast<std::size_t>(end - begin);
594 // reserve(n);
595 // for (InputIt it = begin; it != end; ++it) {
596 // push_back(*it);
597 // }
598 // }
599
600 T *data() { return mArray.get(); }
601
602 const T *data() const { return mArray.get(); }
603
604 bool operator==(const HeapVector<T> &other) const {
605 if (size() != other.size()) {
606 return false;
607 }
608 for (size_t i = 0; i < size(); ++i) {
609 if (mArray[i] != other.mArray[i]) {
610 return false;
611 }
612 }
613 return true;
614 }
615
616 bool operator!=(const HeapVector<T> &other) const {
617 return !(*this == other);
618 }
619};
620
621template <typename T, typename LessThan = fl::less<T>> class SortedHeapVector {
622 private:
624 LessThan mLess;
625 size_t mMaxSize = size_t(-1);
626
627 public:
630
631 SortedHeapVector(LessThan less = LessThan()) : mLess(less) {}
632
633 void setMaxSize(size_t n) {
634 if (mMaxSize == n) {
635 return;
636 }
637 mMaxSize = n;
638 const bool needs_adjustment = mArray.size() > mMaxSize;
639 if (needs_adjustment) {
640 mArray.resize(n);
641 } else {
642 mArray.reserve(n);
643 }
644 }
645
647
648 void reserve(size_t n) { mArray.reserve(n); }
649
650 // Insert while maintaining sort order
651 bool insert(const T &value, InsertResult *result = nullptr) {
652 // Find insertion point using binary search
653 iterator pos = lower_bound(value);
654 if (pos != end() && !mLess(value, *pos) && !mLess(*pos, value)) {
655 // return false; // Already inserted.
656 if (result) {
657 // *result = kExists;
658 *result = InsertResult::kExists;
659 }
660
661 return false;
662 }
663 if (mArray.size() >= mMaxSize) {
664 // return false; // Too full
665 if (result) {
666 *result = InsertResult::kMaxSize;
667 }
668 return false;
669 }
670 mArray.insert(pos, value);
671 if (result) {
672 *result = kInserted;
673 }
674
675 return true;
676 }
677
678 // Find the first position where we should insert value to maintain sort
679 // order
680 iterator lower_bound(const T &value) {
681 iterator first = mArray.begin();
682 iterator last = mArray.end();
683
684 while (first != last) {
685 iterator mid = first + (last - first) / 2;
686
687 if (mLess(*mid, value)) {
688 first = mid + 1;
689 } else {
690 last = mid;
691 }
692 }
693 return first;
694 }
695
696 const_iterator lower_bound(const T &value) const {
697 return const_cast<SortedHeapVector *>(this)->lower_bound(value);
698 }
699
700 // Lookup operations
701 iterator find(const T &value) {
702 iterator pos = lower_bound(value);
703 if (pos != end() && !mLess(value, *pos) && !mLess(*pos, value)) {
704 return pos;
705 }
706 return end();
707 }
708
709 void swap(SortedHeapVector &other) { mArray.swap(other.mArray); }
710
711 const_iterator find(const T &value) const {
712 return const_cast<SortedHeapVector *>(this)->find(value);
713 }
714
715 bool has(const T &value) const { return find(value) != end(); }
716
717 // Removal operations
718 bool erase(const T &value) {
719 iterator it = find(value);
720 if (it != end()) {
721 return mArray.erase(it);
722 }
723 return false;
724 }
725
726 bool erase(iterator pos) { return mArray.erase(pos); }
727
728 // Basic container operations
729 size_t size() const { return mArray.size(); }
730 bool empty() const { return mArray.empty(); }
731 size_t capacity() const { return mArray.capacity(); }
732 void clear() { mArray.clear(); }
733 bool full() const {
734 if (mArray.size() >= mMaxSize) {
735 return true;
736 }
737 return mArray.full();
738 }
739
740 // Element access
741 T &operator[](size_t index) { return mArray[index]; }
742 const T &operator[](size_t index) const { return mArray[index]; }
743
744 T &front() { return mArray.front(); }
745 const T &front() const { return mArray.front(); }
746
747 T &back() { return mArray.back(); }
748 const T &back() const { return mArray.back(); }
749
750 // Iterators
751 iterator begin() { return mArray.begin(); }
752 const_iterator begin() const { return mArray.begin(); }
753 iterator end() { return mArray.end(); }
754 const_iterator end() const { return mArray.end(); }
755
756 // Raw data access
757 T *data() { return mArray.data(); }
758 const T *data() const { return mArray.data(); }
759};
760
761template <typename T, size_t INLINED_SIZE> class InlinedVector {
762 public:
766
767 InlinedVector() = default;
769 if (other.mUsingHeap) {
770 mHeap = other.mHeap;
771 mUsingHeap = true;
772 } else {
773 mFixed = other.mFixed;
774 mUsingHeap = false;
775 }
776 }
778 // swap(*this, other);
779 fl::swap(*this, other);
780 other.clear();
781 }
782 InlinedVector(size_t size) : mUsingHeap(false) {
783 if (size > INLINED_SIZE) {
784 mHeap.resize(size);
785 mUsingHeap = true;
786 } else {
787 mFixed.resize(size);
788 }
789 }
790
792 if (this != &other) {
793 assign(other.begin(), other.end());
794 }
795 return *this;
796 }
797
799 this->clear();
800 if (this != &other) {
801 if (other.mUsingHeap) {
802 mHeap.swap(other.mHeap);
803 mUsingHeap = true;
804 } else {
805 mFixed.swap(other.mFixed);
806 mUsingHeap = false;
807 }
808 other.clear();
809 }
810 return *this;
811 }
812
813 void reserve(size_t size) {
814 if (size > INLINED_SIZE) {
815 if (mUsingHeap) {
816 mHeap.reserve(size);
817 } else {
818 mHeap.reserve(size);
819 for (auto &v : mFixed) {
820 mHeap.push_back(v);
821 }
822 mFixed.clear();
823 mUsingHeap = true;
824 }
825 } else {
826 if (mUsingHeap) {
827 mFixed.reserve(size);
828 for (auto &v : mHeap) {
829 mFixed.push_back(v);
830 }
831 mHeap.clear();
832 mUsingHeap = false;
833 } else {
834 mFixed.reserve(size);
835 }
836 }
837 }
838
839 void resize(size_t size) {
840 if (size > INLINED_SIZE) {
841 if (mUsingHeap) {
842 mHeap.resize(size);
843 } else {
844 mHeap.resize(size);
845 for (auto &v : mFixed) {
846 mHeap.push_back(v);
847 }
848 mFixed.clear();
849 mUsingHeap = true;
850 }
851 } else {
852 if (mUsingHeap) {
853 mFixed.resize(size);
854 for (auto &v : mHeap) {
855 mFixed.push_back(v);
856 }
857 mHeap.clear();
858 mUsingHeap = false;
859 } else {
860 mFixed.resize(size);
861 }
862 }
863 }
864
865 // Get current size
866 size_t size() const { return mUsingHeap ? mHeap.size() : mFixed.size(); }
867 bool empty() const { return size() == 0; }
868 T *data() { return mUsingHeap ? mHeap.data() : mFixed.data(); }
869 const T *data() const { return mUsingHeap ? mHeap.data() : mFixed.data(); }
870
871 void assign(size_t new_cap, const T &value) {
872 clear();
873 if (INLINED_SIZE > new_cap) {
874 // mFixed.assign(value);
875 while (size() < new_cap) {
876 mFixed.push_back(value);
877 }
878 return;
879 }
880 // mHeap.assign(value);
881 mHeap.reserve(new_cap);
882 mUsingHeap = true;
883 while (size() < new_cap) {
884 mHeap.push_back(value);
885 }
886 }
887
888 template <typename InputIt,
890 void assign(InputIt begin, InputIt end) {
891 clear();
892 if (uint32_t(end - begin) <= INLINED_SIZE) {
893 mFixed.assign(begin, end);
894 return;
895 }
896 mHeap.assign(begin, end);
897 mUsingHeap = true;
898 }
899
900 // void assign(const_iterator begin, const_iterator end) {
901 // clear();
902 // if (end - begin <= INLINED_SIZE) {
903 // mFixed.assign(begin, end);
904 // return;
905 // }
906 // mHeap.assign(begin, end);
907 // mUsingHeap = true;
908 // }
909
910 // Element access
911 T &operator[](size_t idx) { return mUsingHeap ? mHeap[idx] : mFixed[idx]; }
912 const T &operator[](size_t idx) const {
913 return mUsingHeap ? mHeap[idx] : mFixed[idx];
914 }
915
916 bool full() const { return INLINED_SIZE == size(); }
917
918 // Add an element
919 void push_back(const T &value) {
920 if (!mUsingHeap) {
921 if (mFixed.size() < INLINED_SIZE) {
922 mFixed.push_back(value);
923 return;
924 }
925 // overflow: move inline data into heap
926 mHeap.reserve(INLINED_SIZE * 2);
927 for (auto &v : mFixed) {
928 mHeap.push_back(v);
929 }
930 mFixed.clear();
931 mUsingHeap = true;
932 }
933 mHeap.push_back(value);
934 }
935
936 // Remove last element
937 void pop_back() {
938 if (mUsingHeap) {
939 mHeap.pop_back();
940 } else {
941 mFixed.pop_back();
942 }
943 }
944
945 // Clear all elements
946 void clear() {
947 if (mUsingHeap) {
948 mHeap.clear();
949 // mUsingHeap = false;
950 } else {
951 mFixed.clear();
952 }
953 }
954
955 template <typename Predicate> iterator find_if(Predicate pred) {
956 for (iterator it = begin(); it != end(); ++it) {
957 if (pred(*it)) {
958 return it;
959 }
960 }
961 return end();
962 }
963
965 if (mUsingHeap) {
966 mHeap.erase(pos);
967 } else {
968 mFixed.erase(pos);
969 }
970 }
971
972 bool insert(iterator pos, const T &value) {
973 if (mUsingHeap) {
974 // return insert(pos, value);
975 return mHeap.insert(pos, value);
976 }
977
978 if (mFixed.size() < INLINED_SIZE) {
979 return mFixed.insert(pos, value);
980 }
981
982 // size_t diff = pos - mFixed.begin();
983 // make safe for data that grows down
984 size_t idx = mFixed.end() - pos;
985
986 // overflow: move inline data into heap
987 mHeap.reserve(INLINED_SIZE * 2);
988 for (auto &v : mFixed) {
989 mHeap.push_back(v);
990 }
991 mFixed.clear();
992 return mHeap.insert(mHeap.begin() + idx, value);
993 }
994
995 // Iterators
996 iterator begin() { return mUsingHeap ? mHeap.begin() : mFixed.begin(); }
997 iterator end() { return mUsingHeap ? mHeap.end() : mFixed.end(); }
999 return mUsingHeap ? mHeap.begin() : mFixed.begin();
1000 }
1002 return mUsingHeap ? mHeap.end() : mFixed.end();
1003 }
1004
1005 // back, front
1006 T &front() { return mUsingHeap ? mHeap.front() : mFixed.front(); }
1007 const T &front() const {
1008 return mUsingHeap ? mHeap.front() : mFixed.front();
1009 }
1010
1011 T &back() { return mUsingHeap ? mHeap.back() : mFixed.back(); }
1012 const T &back() const { return mUsingHeap ? mHeap.back() : mFixed.back(); }
1013
1014 void swap(InlinedVector &other) {
1015 if (this != &other) {
1017 fl::swap(mFixed, other.mFixed);
1018 fl::swap(mHeap, other.mHeap);
1019 }
1020 }
1021
1022 private:
1023 bool mUsingHeap = false;
1026};
1027
1028template <typename T> using vector = HeapVector<T>;
1029
1030template <typename T, size_t INLINED_SIZE>
1032
1033template <typename T, size_t INLINED_SIZE = 64>
1035
1036} // namespace fl
uint8_t pos
Definition Blur.ino:11
const PairKV * const_iterator
Definition vector.h:80
FixedVector(const FixedVector &other)
Definition vector.h:93
constexpr size_t size() const
Definition vector.h:134
iterator find_if(Predicate pred)
Definition vector.h:218
InlinedMemoryBlock< PairKV, N > mMemoryBlock
Definition vector.h:72
const T * memory() const
Definition vector.h:76
void resize(size_t n)
Definition vector.h:124
FixedVector & operator=(const FixedVector &other)
Definition vector.h:102
iterator data()
Definition vector.h:267
constexpr FixedVector()
Definition vector.h:82
FixedVector(FixedVector &&other)
Definition vector.h:88
void clear()
Definition vector.h:180
const T & back() const
Definition vector.h:280
void assign(const_iterator begin, const_iterator end)
Definition vector.h:164
T & operator[](size_t index)
Definition vector.h:113
const_iterator find(const T &value) const
Definition vector.h:258
bool has(const T &value) const
Definition vector.h:271
void pop_back()
Definition vector.h:172
iterator erase(const T &value)
Definition vector.h:201
void swap(FixedVector< T, N > &other)
Definition vector.h:288
const_iterator data() const
Definition vector.h:269
constexpr bool empty() const
Definition vector.h:136
const T & operator[](size_t index) const
Definition vector.h:116
const_iterator end() const
Definition vector.h:286
const_iterator begin() const
Definition vector.h:284
const T & front() const
Definition vector.h:276
void reserve(size_t n)
Definition vector.h:150
FixedVector(const T(&values)[M])
Definition vector.h:97
void push_back(const T &value)
Definition vector.h:142
FixedVector(const T(&values)[N])
Definition vector.h:84
iterator erase(iterator pos)
Definition vector.h:187
constexpr size_t capacity() const
Definition vector.h:139
void assign_array(const T *values, size_t count)
Definition vector.h:157
bool insert(iterator pos, const T &value)
Definition vector.h:227
T * memory()
Definition vector.h:74
iterator find(const T &value)
Definition vector.h:209
size_t capacity() const
Definition vector.h:439
bool operator==(const HeapVector< T > &other) const
Definition vector.h:604
const_iterator end() const
Definition vector.h:467
const_iterator find(const T &value) const
Definition vector.h:492
const T & back() const
Definition vector.h:480
void reserve(size_t n)
Definition vector.h:380
HeapVector(HeapVector< T > &&other)
Definition vector.h:341
const_iterator begin() const
Definition vector.h:465
void resize(size_t n, const T &value)
Definition vector.h:401
void assign(InputIt begin, InputIt end)
Definition vector.h:413
size_t size() const
Definition vector.h:435
HeapVector(T(&values)[N])
Definition vector.h:353
bool insert(iterator pos, const T &value)
Definition vector.h:556
HeapVector(size_t size=0, const T &value=T())
Definition vector.h:330
void assign(size_t new_cap, const T &value)
Definition vector.h:421
T & operator[](size_t index)
Definition vector.h:430
void clear()
Definition vector.h:457
void pop_back()
Definition vector.h:450
void push_back(const T &value)
Definition vector.h:442
HeapVector & operator=(const HeapVector< T > &other)
Definition vector.h:345
bool empty() const
Definition vector.h:437
bool erase(iterator pos, T *out_value=nullptr)
Definition vector.h:512
const T * data() const
Definition vector.h:602
const T & operator[](size_t index) const
Definition vector.h:432
iterator find_if(Predicate pred)
Definition vector.h:501
iterator end()
Definition vector.h:466
void ensure_size(size_t n)
Definition vector.h:362
void swap(iterator a, iterator b)
Definition vector.h:548
bool operator!=(const HeapVector< T > &other) const
Definition vector.h:616
const T & front() const
Definition vector.h:476
void resize(size_t n)
Definition vector.h:386
reverse_iterator rend()
Definition vector.h:471
iterator begin()
Definition vector.h:464
const DrawItem * const_iterator
Definition vector.h:314
iterator find(const T &value)
Definition vector.h:483
void swap(HeapVector< T > &other)
Definition vector.h:535
void erase(const T &value)
Definition vector.h:528
reverse_iterator rbegin()
Definition vector.h:469
fl::scoped_array< DrawItem > mArray
Definition vector.h:307
bool full() const
Definition vector.h:554
bool has(const T &value) const
Definition vector.h:510
HeapVector(const HeapVector< T > &other)
Definition vector.h:337
T & front()
Definition vector.h:474
iterator end()
Definition vector.h:997
const_iterator begin() const
Definition vector.h:998
void pop_back()
Definition vector.h:937
const T & back() const
Definition vector.h:1012
InlinedVector(size_t size)
Definition vector.h:782
void swap(InlinedVector &other)
Definition vector.h:1014
const T * data() const
Definition vector.h:869
void reserve(size_t size)
Definition vector.h:813
const T & front() const
Definition vector.h:1007
InlinedVector()=default
iterator find_if(Predicate pred)
Definition vector.h:955
void push_back(const T &value)
Definition vector.h:919
HeapVector< T > mHeap
Definition vector.h:1025
FixedVector< T, INLINED_SIZE > mFixed
Definition vector.h:1024
const T & operator[](size_t idx) const
Definition vector.h:912
InlinedVector & operator=(const InlinedVector &other)
Definition vector.h:791
iterator begin()
Definition vector.h:996
const_iterator end() const
Definition vector.h:1001
size_t size() const
Definition vector.h:866
InlinedVector(InlinedVector &&other)
Definition vector.h:777
void assign(size_t new_cap, const T &value)
Definition vector.h:871
InlinedVector(const InlinedVector &other)
Definition vector.h:768
bool full() const
Definition vector.h:916
typename FixedVector< T, INLINED_SIZE >::iterator iterator
Definition vector.h:763
bool insert(iterator pos, const T &value)
Definition vector.h:972
bool empty() const
Definition vector.h:867
void resize(size_t size)
Definition vector.h:839
void assign(InputIt begin, InputIt end)
Definition vector.h:890
void erase(iterator pos)
Definition vector.h:964
typename FixedVector< T, INLINED_SIZE >::const_iterator const_iterator
Definition vector.h:764
T & operator[](size_t idx)
Definition vector.h:911
InlinedVector & operator=(InlinedVector &&other)
Definition vector.h:798
size_t mMaxSize
Definition vector.h:625
SortedHeapVector(LessThan less=LessThan())
Definition vector.h:631
bool erase(iterator pos)
Definition vector.h:726
iterator lower_bound(const T &value)
Definition vector.h:680
HeapVector< Pair > mArray
Definition vector.h:623
bool erase(const T &value)
Definition vector.h:718
size_t size() const
Definition vector.h:729
iterator end()
Definition vector.h:753
bool has(const T &value) const
Definition vector.h:715
const T * data() const
Definition vector.h:758
iterator begin()
Definition vector.h:751
void swap(SortedHeapVector &other)
Definition vector.h:709
bool full() const
Definition vector.h:733
const T & back() const
Definition vector.h:748
const_iterator end() const
Definition vector.h:754
void setMaxSize(size_t n)
Definition vector.h:633
size_t capacity() const
Definition vector.h:731
HeapVector< Pair >::const_iterator const_iterator
Definition vector.h:629
const_iterator begin() const
Definition vector.h:752
PairLess mLess
Definition vector.h:624
T & operator[](size_t index)
Definition vector.h:741
bool insert(const T &value, InsertResult *result=nullptr)
Definition vector.h:651
const_iterator lower_bound(const T &value) const
Definition vector.h:696
HeapVector< Pair >::iterator iterator
Definition vector.h:628
bool empty() const
Definition vector.h:730
void reserve(size_t n)
Definition vector.h:648
const T & front() const
Definition vector.h:745
const T & operator[](size_t index) const
Definition vector.h:742
const_iterator find(const T &value) const
Definition vector.h:711
iterator find(const T &value)
Definition vector.h:701
#define MAX(a, b)
Definition math_macros.h:11
Implements the FastLED namespace macros.
void swap(array< T, N > &lhs, array< T, N > &rhs) noexcept(noexcept(lhs.swap(rhs)))
Definition array.h:140
InlinedVector< T, INLINED_SIZE > vector_inlined
Definition vector.h:1034
HeapVector< T > vector
Definition vector.h:1028
InsertResult
@ kMaxSize
@ kExists
@ kInserted
typename enable_if< Condition, T >::type enable_if_t
Definition type_traits.h:29
FixedVector< T, INLINED_SIZE > vector_fixed
Definition vector.h:1031
Implements a simple red square effect for 2D LED grids.
Definition crgb.h:16
static FASTLED_NAMESPACE_BEGIN uint8_t const p[]
Definition noise.cpp:30
bool operator!=(const reverse_iterator &other) const
Definition vector.h:324
reverse_iterator & operator++()
Definition vector.h:320
uintptr_t MemoryType
Definition vector.h:20
InlinedMemoryBlock(InlinedMemoryBlock &&other)=default
InlinedMemoryBlock(const InlinedMemoryBlock &other)=default
const T * memory() const
Definition vector.h:52
MemoryType mMemoryBlock[kBlockSize]
Definition vector.h:42
Binary function object that returns whether the first argument is less than the second.
Definition functional.h:15