Embedded Template Library 1.0
Loading...
Searching...
No Matches
deque.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2014 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_DEQUE_INCLUDED
32#define ETL_DEQUE_INCLUDED
33
34#include "platform.h"
35#include "algorithm.h"
36#include "iterator.h"
37#include "utility.h"
38#include "memory.h"
39#include "exception.h"
40#include "error_handler.h"
41#include "debug_count.h"
42#include "algorithm.h"
43#include "type_traits.h"
44#include "placement_new.h"
45#include "initializer_list.h"
46
47#include <stddef.h>
48#include <stdint.h>
49
50#include "private/minmax_push.h"
51
52//*****************************************************************************
56//*****************************************************************************
57
58namespace etl
59{
60 //***************************************************************************
63 //***************************************************************************
73
74 //***************************************************************************
77 //***************************************************************************
79 {
80 public:
81
83 : etl::deque_exception(ETL_ERROR_TEXT("deque:full", ETL_DEQUE_FILE_ID"A"), file_name_, line_number_)
84 {
85 }
86 };
87
88 //***************************************************************************
91 //***************************************************************************
93 {
94 public:
95
97 : etl::deque_exception(ETL_ERROR_TEXT("deque:empty", ETL_DEQUE_FILE_ID"B"), file_name_, line_number_)
98 {
99 }
100 };
101
102 //***************************************************************************
105 //***************************************************************************
107 {
108 public:
109
111 : etl::deque_exception(ETL_ERROR_TEXT("deque:bounds", ETL_DEQUE_FILE_ID"C"), file_name_, line_number_)
112 {
113 }
114 };
115
116 //***************************************************************************
119 //***************************************************************************
121 {
122 public:
123
125 : deque_exception(ETL_ERROR_TEXT("deque:type", ETL_DEQUE_FILE_ID"D"), file_name_, line_number_)
126 {
127 }
128 };
129
130 //***************************************************************************
133 //***************************************************************************
135 {
136 public:
137
138 typedef size_t size_type;
139
140 //*************************************************************************
143 //*************************************************************************
144 size_type size() const
145 {
146 return current_size;
147 }
148
149 //*************************************************************************
152 //*************************************************************************
153 bool empty() const
154 {
155 return (current_size == 0);
156 }
157
158 //*************************************************************************
161 //*************************************************************************
162 bool full() const
163 {
164 return current_size == CAPACITY;
165 }
166
167 //*************************************************************************
170 //*************************************************************************
171 size_type max_size() const
172 {
173 return CAPACITY;
174 }
175
176 //*************************************************************************
179 //*************************************************************************
180 size_type capacity() const
181 {
182 return CAPACITY;
183 }
184
185 //*************************************************************************
188 //*************************************************************************
189 size_t available() const
190 {
191 return max_size() - size();
192 }
193
194 protected:
195
196 //*************************************************************************
198 //*************************************************************************
200 : current_size(0)
203 {
204 }
205
206 //*************************************************************************
208 //*************************************************************************
210 {
211 }
212
213 size_type current_size;
214 const size_type CAPACITY;
215 const size_type BUFFER_SIZE;
217 };
218
219 //***************************************************************************
223 //***************************************************************************
224 template <typename T>
225 class ideque : public etl::deque_base
226 {
227 public:
228
229 typedef T value_type;
230 typedef size_t size_type;
231 typedef T& reference;
232 typedef const T& const_reference;
233#if ETL_USING_CPP11
234 typedef T&& rvalue_reference;
235#endif
236 typedef T* pointer;
237 typedef const T* const_pointer;
238 typedef typename etl::iterator_traits<pointer>::difference_type difference_type;
239
240 //*************************************************************************
242 //*************************************************************************
243 class iterator : public etl::iterator<ETL_OR_STD::random_access_iterator_tag, T>
244 {
245 public:
246
247 friend class ideque;
248 friend class const_iterator;
249
250 //***************************************************
251 iterator()
252 : index(0)
253 , p_deque(0)
254 , p_buffer(0)
255 {
256 }
257
258 //***************************************************
259 iterator(const iterator& other)
260 : index(other.index)
261 , p_deque(other.p_deque)
262 , p_buffer(other.p_buffer)
263 {
264 }
265
266 //***************************************************
268 {
269 index = other.index;
270 p_deque = other.p_deque;
271 p_buffer = other.p_buffer;
272
273 return *this;
274 }
275
276 //***************************************************
278 {
279 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1;
280
281 return *this;
282 }
283
284 //***************************************************
286 {
287 iterator previous(*this);
288 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1;
289
290 return previous;
291 }
292
293 //***************************************************
294 iterator& operator +=(difference_type offset)
295 {
296 if (offset > 0)
297 {
298 index += offset;
299 index = (static_cast<size_t>(index) > p_deque->BUFFER_SIZE - 1) ? index - p_deque->BUFFER_SIZE : index;
300 }
301 else if (offset < 0)
302 {
303 operator -= (-offset);
304 }
305
306 return *this;
307 }
308
309 //***************************************************
310 iterator& operator -=(difference_type offset)
311 {
312 if (offset > 0)
313 {
314 index -= offset;
315 index = (index < 0) ? index + p_deque->BUFFER_SIZE : index;
316 }
317 else if (offset < 0)
318 {
319 operator += (-offset);
320 }
321
322 return *this;
323 }
324
325 //***************************************************
327 {
328 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1;
329
330 return *this;
331 }
332
333 //***************************************************
335 {
336 iterator previous(*this);
337 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1;
338
339 return previous;
340 }
341
342 //***************************************************
343 reference operator *() const
344 {
345 return p_buffer[index];
346 }
347
348 //***************************************************
349 pointer operator ->() const
350 {
351 return &p_buffer[index];
352 }
353
354 //***************************************************
355 reference operator [](size_t i)
356 {
357 iterator result(*this);
358 result += i;
359
360 return *result;
361 }
362
363 //***************************************************
364 const_reference operator [](size_t i) const
365 {
366 iterator result(*this);
367 result += i;
368
369 return *result;
370 }
371
372 //***************************************************
373 friend iterator operator +(const iterator& lhs, difference_type offset)
374 {
375 iterator result(lhs);
376 result += offset;
377 return result;
378 }
379
380 //***************************************************
381 friend iterator operator +(difference_type offset, const iterator& lhs)
382 {
383 iterator result(lhs);
384 result += offset;
385 return result;
386 }
387
388 //***************************************************
389 friend iterator operator -(const iterator& lhs, difference_type offset)
390 {
391 iterator result(lhs);
392 result -= offset;
393 return result;
394 }
395
396 //***************************************************
397 friend bool operator == (const iterator& lhs, const iterator& rhs)
398 {
399 return lhs.index == rhs.index;
400 }
401
402 //***************************************************
403 friend bool operator != (const iterator& lhs, const iterator& rhs)
404 {
405 return !(lhs == rhs);
406 }
407
408 //***************************************************
409 friend bool operator < (const iterator& lhs, const iterator& rhs)
410 {
411 const difference_type lhs_index = lhs.get_index();
412 const difference_type rhs_index = rhs.get_index();
413 const difference_type reference_index = lhs.container().begin().get_index();
414 const size_t buffer_size = lhs.container().max_size() + 1;
415
416 const difference_type lhs_distance = (lhs_index < reference_index) ? buffer_size + lhs_index - reference_index : lhs_index - reference_index;
417 const difference_type rhs_distance = (rhs_index < reference_index) ? buffer_size + rhs_index - reference_index : rhs_index - reference_index;
418
419 return lhs_distance < rhs_distance;
420 }
421
422 //***************************************************
423 friend bool operator <= (const iterator& lhs, const iterator& rhs)
424 {
425 return !(lhs > rhs);
426 }
427
428 //***************************************************
429 friend bool operator > (const iterator& lhs, const iterator& rhs)
430 {
431 return (rhs < lhs);
432 }
433
434 //***************************************************
435 friend bool operator >= (const iterator& lhs, const iterator& rhs)
436 {
437 return !(lhs < rhs);
438 }
439
440 //***************************************************
441 difference_type get_index() const
442 {
443 return index;
444 }
445
446 //***************************************************
447 ideque& container() const
448 {
449 return *p_deque;
450 }
451
452 //***************************************************
453 pointer get_buffer() const
454 {
455 return p_buffer;
456 }
457
458 //***************************************************
459 void swap(iterator& other)
460 {
461 using ETL_OR_STD::swap; // Allow ADL
462
463 swap(index, other.index);
464 }
465
466 private:
467
468 //***************************************************
469 difference_type distance(difference_type firstIndex, difference_type index_) const
470 {
471 if (index_ < firstIndex)
472 {
473 return p_deque->BUFFER_SIZE + index_ - firstIndex;
474 }
475 else
476 {
477 return index_ - firstIndex;
478 }
479 }
480
481 //***************************************************
482 iterator(difference_type index_, ideque& the_deque, pointer p_buffer_)
483 : index(index_)
484 , p_deque(&the_deque)
485 , p_buffer(p_buffer_)
486 {
487 }
488
489 difference_type index;
490 ideque* p_deque;
491 pointer p_buffer;
492 };
493
494 //*************************************************************************
496 //*************************************************************************
497 class const_iterator : public etl::iterator<ETL_OR_STD::random_access_iterator_tag, const T>
498 {
499 public:
500
501 friend class ideque;
502
503 //***************************************************
505 : index(0)
506 , p_deque(0)
507 , p_buffer(0)
508 {
509 }
510
511 //***************************************************
513 : index(other.index)
514 , p_deque(other.p_deque)
515 , p_buffer(other.p_buffer)
516 {
517 }
518
519 //***************************************************
520 const_iterator(const typename ideque::iterator& other)
521 : index(other.index)
522 , p_deque(other.p_deque)
523 , p_buffer(other.p_buffer)
524 {
525 }
526
527 //***************************************************
529 {
530 index = other.index;
531 p_deque = other.p_deque;
532 p_buffer = other.p_buffer;
533
534 return *this;
535 }
536
538 {
539 index = other.index;
540 p_deque = other.p_deque;
541 p_buffer = other.p_buffer;
542
543 return *this;
544 }
545
546 //***************************************************
548 {
549 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1;
550
551 return *this;
552 }
553
554 //***************************************************
556 {
557 const_iterator previous(*this);
558 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1;
559
560 return previous;
561 }
562
563 //***************************************************
564 const_iterator& operator +=(difference_type offset)
565 {
566 if (offset > 0)
567 {
568 index += offset;
569 index = (static_cast<size_t>(index) > p_deque->BUFFER_SIZE - 1) ? index - p_deque->BUFFER_SIZE : index;
570 }
571 else if (offset < 0)
572 {
573 operator -= (-offset);
574 }
575
576 return *this;
577 }
578
579 //***************************************************
580 const_iterator& operator -=(difference_type offset)
581 {
582 if (offset > 0)
583 {
584 index -= offset;
585 index = (index < 0) ? static_cast<size_t>(index) + p_deque->BUFFER_SIZE : index;
586 }
587 else if (offset < 0)
588 {
589 operator += (-offset);
590 }
591
592 return *this;
593 }
594
595 //***************************************************
597 {
598 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1;
599
600 return *this;
601 }
602
603 //***************************************************
605 {
606 const_iterator previous(*this);
607 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1;
608
609 return previous;
610 }
611
612 //***************************************************
614 {
615 return p_buffer[index];
616 }
617
618 //***************************************************
620 {
621 return &p_buffer[index];
622 }
623
624 //***************************************************
625 reference operator [](size_t i)
626 {
627 iterator result(*this);
628 result += i;
629
630 return *result;
631 }
632
633 //***************************************************
634 friend const_iterator operator +(const const_iterator& lhs, difference_type offset)
635 {
636 const_iterator result(lhs);
637 result += offset;
638 return result;
639 }
640
641 //***************************************************
642 friend const_iterator operator +(difference_type offset, const const_iterator& lhs)
643 {
644 const_iterator result(lhs);
645 result += offset;
646 return result;
647 }
648
649 //***************************************************
650 friend const_iterator operator -(const const_iterator& lhs, difference_type offset)
651 {
652 const_iterator result(lhs);
653 result -= offset;
654 return result;
655 }
656
657 //***************************************************
658 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
659 {
660 return lhs.index == rhs.index;
661 }
662
663 //***************************************************
664 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
665 {
666 return !(lhs == rhs);
667 }
668
669 //***************************************************
670 friend bool operator < (const const_iterator& lhs, const const_iterator& rhs)
671 {
672 const difference_type lhs_index = lhs.get_index();
673 const difference_type rhs_index = rhs.get_index();
674 const difference_type reference_index = lhs.container().begin().get_index();
675 const size_t buffer_size = lhs.container().max_size() + 1UL;
676
677 const difference_type lhs_distance = (lhs_index < reference_index) ? buffer_size + lhs_index - reference_index : lhs_index - reference_index;
678 const difference_type rhs_distance = (rhs_index < reference_index) ? buffer_size + rhs_index - reference_index : rhs_index - reference_index;
679
680 return lhs_distance < rhs_distance;
681 }
682
683 //***************************************************
684 friend bool operator <= (const const_iterator& lhs, const const_iterator& rhs)
685 {
686 return !(lhs > rhs);
687 }
688
689 //***************************************************
690 friend bool operator > (const const_iterator& lhs, const const_iterator& rhs)
691 {
692 return (rhs < lhs);
693 }
694
695 //***************************************************
696 friend bool operator >= (const const_iterator& lhs, const const_iterator& rhs)
697 {
698 return !(lhs < rhs);
699 }
700
701 //***************************************************
702 difference_type get_index() const
703 {
704 return index;
705 }
706
707 //***************************************************
708 ideque& container() const
709 {
710 return *p_deque;
711 }
712
713 //***************************************************
714 pointer get_buffer() const
715 {
716 return p_buffer;
717 }
718
719 //***************************************************
720 void swap(const_iterator& other)
721 {
722 ETL_OR_STD::swap(index, other.index);
723 }
724
725 private:
726
727 //***************************************************
728 difference_type distance(difference_type firstIndex, difference_type index_) const
729 {
730 if (index_ < firstIndex)
731 {
732 return p_deque->BUFFER_SIZE + index_ - firstIndex;
733 }
734 else
735 {
736 return index_ - firstIndex;
737 }
738 }
739
740 //***************************************************
742 : index(index_)
743 , p_deque(&the_deque)
744 , p_buffer(p_buffer_)
745 {
746 }
747
748 difference_type index;
749 ideque* p_deque;
750 pointer p_buffer;
751 };
752
753 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
754 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
755
756 //*************************************************************************
758 //*************************************************************************
759 template<typename TIterator>
762 {
763 initialise();
764
765 while (range_begin != range_end)
766 {
768 ++range_begin;
769 }
770 }
771
772 //*************************************************************************
777 //*************************************************************************
778 void assign(size_type n, const value_type& value)
779 {
780 ETL_ASSERT(n <= CAPACITY, ETL_ERROR(deque_full));
781
782 initialise();
783
784 while (n > 0)
785 {
786 create_element_back(value);
787 --n;
788 }
789 }
790
791 //*************************************************************************
795 //*************************************************************************
796 reference at(size_t index)
797 {
798 ETL_ASSERT(index < current_size, ETL_ERROR(deque_out_of_bounds));
799
800 iterator result(_begin);
801 result += index;
802
803 return *result;
804 }
805
806 //*************************************************************************
810 //*************************************************************************
811 const_reference at(size_t index) const
812 {
813 ETL_ASSERT(index < current_size, ETL_ERROR(deque_out_of_bounds));
814
815 iterator result(_begin);
816 result += index;
817
818 return *result;
819 }
820
821 //*************************************************************************
824 //*************************************************************************
825 reference operator [](size_t index)
826 {
827 iterator result(_begin);
828 result += index;
829
830 return *result;
831 }
832
833 //*************************************************************************
836 //*************************************************************************
837 const_reference operator [](size_t index) const
838 {
839 iterator result(_begin);
840 result += index;
841
842 return *result;
843 }
844
845 //*************************************************************************
848 //*************************************************************************
850 {
851 return *_begin;
852 }
853
854 //*************************************************************************
857 //*************************************************************************
859 {
860 return *_begin;
861 }
862
863 //*************************************************************************
866 //*************************************************************************
868 {
869 return *(_end - 1);
870 }
871
872 //*************************************************************************
875 //*************************************************************************
877 {
878 return *(_end - 1);
879 }
880
881 //*************************************************************************
883 //*************************************************************************
885 {
886 return _begin;
887 }
888
889 //*************************************************************************
891 //*************************************************************************
893 {
894 return _begin;
895 }
896
897 //*************************************************************************
899 //*************************************************************************
901 {
902 return _begin;
903 }
904
905 //*************************************************************************
907 //*************************************************************************
909 {
910 return iterator(_end);
911 }
912
913 //*************************************************************************
915 //*************************************************************************
917 {
918 return iterator(_end);
919 }
920
921 //*************************************************************************
923 //*************************************************************************
925 {
926 return const_iterator(_end);
927 }
928
929 //*************************************************************************
931 //*************************************************************************
932 reverse_iterator rbegin()
933 {
934 return reverse_iterator(end());
935 }
936
937 //*************************************************************************
939 //*************************************************************************
940 const_reverse_iterator rbegin() const
941 {
942 return const_reverse_iterator(end());
943 }
944
945 //*************************************************************************
947 //*************************************************************************
948 const_reverse_iterator crbegin() const
949 {
950 return const_reverse_iterator(cend());
951 }
952
953 //*************************************************************************
955 //*************************************************************************
956 reverse_iterator rend()
957 {
958 return reverse_iterator(begin());
959 }
960
961 //*************************************************************************
963 //*************************************************************************
964 const_reverse_iterator rend() const
965 {
966 return const_reverse_iterator(begin());
967 }
968
969 //*************************************************************************
971 //*************************************************************************
972 const_reverse_iterator crend() const
973 {
974 return const_reverse_iterator(cbegin());
975 }
976
977 //*************************************************************************
979 //*************************************************************************
980 void clear()
981 {
982 initialise();
983 }
984
985 //*************************************************************************
987 //*************************************************************************
988 void fill(const T& value)
989 {
990 etl::fill(begin(), end(), value);
991 }
992
993 //*************************************************************************
998 //*************************************************************************
1000 {
1001 iterator position(to_iterator(insert_position));
1002
1003 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1004
1005 if (insert_position == begin())
1006 {
1007 create_element_front(value);
1008 position = _begin;
1009 }
1010 else if (insert_position == end())
1011 {
1012 create_element_back(value);
1013 position = _end - 1;
1014 }
1015 else
1016 {
1017 // Are we closer to the front?
1018 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1019 {
1020 // Construct the _begin.
1021 create_element_front(*_begin);
1022
1023 // Move the values.
1024 etl::move(_begin + 1, position, _begin);
1025
1026 // Write the new value.
1027 *--position = value;
1028 }
1029 else
1030 {
1031 // Construct the _end.
1032 create_element_back(*(_end - 1));
1033
1034 // Move the values.
1035 etl::move_backward(position, _end - 2, _end - 1);
1036
1037 // Write the new value.
1038 *position = value;
1039 }
1040 }
1041
1042 return position;
1043 }
1044
1045#if ETL_USING_CPP11
1046 //*************************************************************************
1051 //*************************************************************************
1052 iterator insert(const_iterator insert_position, value_type&& value)
1053 {
1054 iterator position(insert_position.index, *this, p_buffer);
1055
1056 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1057
1058 if (insert_position == begin())
1059 {
1060 create_element_front(etl::move(value));
1061 position = _begin;
1062 }
1063 else if (insert_position == end())
1064 {
1065 create_element_back(etl::move(value));
1066 position = _end - 1;
1067 }
1068 else
1069 {
1070 // Are we closer to the front?
1071 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1072 {
1073 // Construct the _begin.
1074 create_element_front(etl::move(*_begin));
1075
1076 // Move the values.
1077 etl::move(_begin + 1, position, _begin);
1078
1079 // Write the new value.
1080 *--position = etl::move(value);
1081 }
1082 else
1083 {
1084 // Construct the _end.
1085 create_element_back(etl::move(*(_end - 1)));
1086
1087 // Move the values.
1088 etl::move_backward(position, _end - 2, _end - 1);
1089
1090 // Write the new value.
1091 *position = etl::move(value);
1092 }
1093 }
1094
1095 return position;
1096 }
1097#endif
1098
1099 //*************************************************************************
1103 //*************************************************************************
1104#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
1105 template <typename ... Args>
1106 iterator emplace(const_iterator insert_position, Args && ... args)
1107 {
1108 iterator position(insert_position.index, *this, p_buffer);
1109
1110 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1111
1112 void* p;
1113
1114 if (insert_position == begin())
1115 {
1116 --_begin;
1117 p = etl::addressof(*_begin);
1118 ++current_size;
1119 ETL_INCREMENT_DEBUG_COUNT;
1120 position = _begin;
1121 }
1122 else if (insert_position == end())
1123 {
1124 p = etl::addressof(*_end);
1125 ++_end;
1126 ++current_size;
1127 ETL_INCREMENT_DEBUG_COUNT;
1128 position = _end - 1;
1129 }
1130 else
1131 {
1132 // Are we closer to the front?
1133 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1134 {
1135 // Construct the _begin.
1136 create_element_front(*_begin);
1137
1138 // Move the values.
1139 etl::move(_begin + 1, position, _begin);
1140
1141 // Write the new value.
1142 --position;
1143 (*position).~T();
1144 p = etl::addressof(*position);
1145 }
1146 else
1147 {
1148 // Construct the _end.
1149 create_element_back(*(_end - 1));
1150
1151 // Move the values.
1152 etl::move_backward(position, _end - 2, _end - 1);
1153
1154 // Write the new value.
1155 (*position).~T();
1156 p = etl::addressof(*position);
1157 }
1158 }
1159
1160 ::new (p) T(etl::forward<Args>(args)...);
1161
1162 return position;
1163 }
1164
1165#else
1166
1167 //*************************************************************************
1171 //*************************************************************************
1172 template <typename T1>
1174 {
1175 iterator position(insert_position.index, *this, p_buffer);
1176
1177 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1178
1179 void* p;
1180
1181 if (insert_position == begin())
1182 {
1183 --_begin;
1184 p = etl::addressof(*_begin);
1185 ++current_size;
1186 ETL_INCREMENT_DEBUG_COUNT;
1187 position = _begin;
1188 }
1189 else if (insert_position == end())
1190 {
1191 p = etl::addressof(*_end);
1192 ++_end;
1193 ++current_size;
1194 ETL_INCREMENT_DEBUG_COUNT;
1195 position = _end - 1;
1196 }
1197 else
1198 {
1199 // Are we closer to the front?
1200 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1201 {
1202 // Construct the _begin.
1203 create_element_front(*_begin);
1204
1205 // Move the values.
1206 etl::move(_begin + 1, position, _begin);
1207
1208 // Write the new value.
1209 --position;
1210 (*position).~T();
1211 p = etl::addressof(*position);
1212 }
1213 else
1214 {
1215 // Construct the _end.
1216 create_element_back(*(_end - 1));
1217
1218 // Move the values.
1219 etl::move_backward(position, _end - 2, _end - 1);
1220
1221 // Write the new value.
1222 (*position).~T();
1223 p = etl::addressof(*position);
1224 }
1225 }
1226
1227 ::new (p) T(value1);
1228
1229 return position;
1230 }
1231
1232 //*************************************************************************
1236 //*************************************************************************
1237 template <typename T1, typename T2>
1238 iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2)
1239 {
1240 iterator position(insert_position.index, *this, p_buffer);
1241
1242 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1243
1244 void* p;
1245
1246 if (insert_position == begin())
1247 {
1248 --_begin;
1249 p = etl::addressof(*_begin);
1250 ++current_size;
1251 ETL_INCREMENT_DEBUG_COUNT;
1252 position = _begin;
1253 }
1254 else if (insert_position == end())
1255 {
1256 p = etl::addressof(*_end);
1257 ++_end;
1258 ++current_size;
1259 ETL_INCREMENT_DEBUG_COUNT;
1260 position = _end - 1;
1261 }
1262 else
1263 {
1264 // Are we closer to the front?
1265 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1266 {
1267 // Construct the _begin.
1268 create_element_front(*_begin);
1269
1270 // Move the values.
1271 etl::move(_begin + 1, position, _begin);
1272
1273 // Write the new value.
1274 --position;
1275 (*position).~T();
1276 p = etl::addressof(*position);
1277 }
1278 else
1279 {
1280 // Construct the _end.
1281 create_element_back(*(_end - 1));
1282
1283 // Move the values.
1284 etl::move_backward(position, _end - 2, _end - 1);
1285
1286 // Write the new value.
1287 (*position).~T();
1288 p = etl::addressof(*position);
1289 }
1290 }
1291
1292 ::new (p) T(value1, value2);
1293
1294 return position;
1295 }
1296
1297 //*************************************************************************
1301 //*************************************************************************
1302 template <typename T1, typename T2, typename T3>
1303 iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2, const T3& value3)
1304 {
1305 iterator position(insert_position.index, *this, p_buffer);
1306
1307 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1308
1309 void* p;
1310
1311 if (insert_position == begin())
1312 {
1313 --_begin;
1314 p = etl::addressof(*_begin);
1315 ++current_size;
1316 ETL_INCREMENT_DEBUG_COUNT;
1317 position = _begin;
1318 }
1319 else if (insert_position == end())
1320 {
1321 p = etl::addressof(*_end);
1322 ++_end;
1323 ++current_size;
1324 ETL_INCREMENT_DEBUG_COUNT;
1325 position = _end - 1;
1326 }
1327 else
1328 {
1329 // Are we closer to the front?
1330 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1331 {
1332 // Construct the _begin.
1333 create_element_front(*_begin);
1334
1335 // Move the values.
1336 etl::move(_begin + 1, position, _begin);
1337
1338 // Write the new value.
1339 --position;
1340 (*position).~T();
1341 p = etl::addressof(*position);
1342 }
1343 else
1344 {
1345 // Construct the _end.
1346 create_element_back(*(_end - 1));
1347
1348 // Move the values.
1349 etl::move_backward(position, _end - 2, _end - 1);
1350
1351 // Write the new value.
1352 (*position).~T();
1353 p = etl::addressof(*position);
1354 }
1355 }
1356
1357 ::new (p) T(value1, value2, value3);
1358
1359 return position;
1360 }
1361
1362 //*************************************************************************
1366 //*************************************************************************
1367 template <typename T1, typename T2, typename T3, typename T4>
1368 iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2, const T3& value3, const T4& value4)
1369 {
1370 iterator position(insert_position.index, *this, p_buffer);
1371
1372 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1373
1374 void* p;
1375
1376 if (insert_position == begin())
1377 {
1378 --_begin;
1379 p = etl::addressof(*_begin);
1380 ++current_size;
1381 ETL_INCREMENT_DEBUG_COUNT;
1382 position = _begin;
1383 }
1384 else if (insert_position == end())
1385 {
1386 p = etl::addressof(*_end);
1387 ++_end;
1388 ++current_size;
1389 ETL_INCREMENT_DEBUG_COUNT;
1390 position = _end - 1;
1391 }
1392 else
1393 {
1394 // Are we closer to the front?
1395 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1396 {
1397 // Construct the _begin.
1398 create_element_front(*_begin);
1399
1400 // Move the values.
1401 etl::move(_begin + 1, position, _begin);
1402
1403 // Write the new value.
1404 --position;
1405 (*position).~T();
1406 p = etl::addressof(*position);
1407 }
1408 else
1409 {
1410 // Construct the _end.
1411 create_element_back(*(_end - 1));
1412
1413 // Move the values.
1414 etl::move_backward(position, _end - 2, _end - 1);
1415
1416 // Write the new value.
1417 (*position).~T();
1418 p = etl::addressof(*position);
1419 }
1420 }
1421
1422 ::new (p) T(value1, value2, value3, value4);
1423
1424 return position;
1425 }
1426#endif
1427
1428 //*************************************************************************
1434 //*************************************************************************
1436 {
1437 iterator position;
1438
1439 ETL_ASSERT((current_size + n) <= CAPACITY, ETL_ERROR(deque_full));
1440
1441 if (insert_position == begin())
1442 {
1443 for (size_t i = 0UL; i < n; ++i)
1444 {
1445 create_element_front(value);
1446 }
1447
1448 position = _begin;
1449 }
1450 else if (insert_position == end())
1451 {
1452 for (size_t i = 0UL; i < n; ++i)
1453 {
1454 create_element_back(value);
1455 }
1456
1457 position = _end - n;
1458 }
1459 else
1460 {
1461 // Non-const insert iterator.
1462 position = iterator(insert_position.index, *this, p_buffer);
1463
1464 // Are we closer to the front?
1465 if (distance(_begin, insert_position) <= difference_type(current_size / 2))
1466 {
1467 size_t n_insert = n;
1468 size_t n_move = etl::distance(begin(), position);
1469 size_t n_create_copy = etl::min(n_insert, n_move);
1472 size_t n_copy_old = n_move - n_create_copy;
1473
1474 // Remember the original start.
1475 iterator from = _begin + n_create_copy - 1;
1476 iterator to;
1477
1478 // Create new.
1479 for (size_t i = 0UL; i < n_create_new; ++i)
1480 {
1481 create_element_front(value);
1482 }
1483
1484 // Create copy.
1485 for (size_t i = 0UL; i < n_create_copy; ++i)
1486 {
1487 create_element_front(*from);
1488 --from;
1489 }
1490
1491 // Move old.
1492 from = position - n_copy_old;
1493 to = _begin + n_create_copy;
1494 etl::move(from, from + n_copy_old, to);
1495
1496 // Copy new.
1497 to = position - n_create_copy;
1498 etl::fill_n(to, n_copy_new, value);
1499
1500 position = _begin + n_move;
1501 }
1502 else
1503 {
1504 size_t n_insert = n;
1505 size_t n_move = etl::distance(position, end());
1506 size_t n_create_copy = etl::min(n_insert, n_move);
1509 size_t n_copy_old = n_move - n_create_copy;
1510
1511 // Create new.
1512 for (size_t i = 0UL; i < n_create_new; ++i)
1513 {
1514 create_element_back(value);
1515 }
1516
1517 // Create copy.
1518 const_iterator from = position + n_copy_old;
1519
1520 for (size_t i = 0UL; i < n_create_copy; ++i)
1521 {
1522 create_element_back(*from);
1523 ++from;
1524 }
1525
1526 // Move old.
1527 etl::move_backward(position, position + n_copy_old, position + n_insert + n_copy_old);
1528
1529 // Copy new.
1530 etl::fill_n(position, n_copy_new, value);
1531 }
1532 }
1533
1534 return position;
1535 }
1536
1537 //*************************************************************************
1543 //*************************************************************************
1544 template<typename TIterator>
1547 {
1548 iterator position;
1549
1550 difference_type n = etl::distance(range_begin, range_end);
1551
1552 ETL_ASSERT((current_size + n) <= CAPACITY, ETL_ERROR(deque_full));
1553
1554 if (insert_position == begin())
1555 {
1556 create_element_front(n, range_begin);
1557
1558 position = _begin;
1559 }
1560 else if (insert_position == end())
1561 {
1562 for (difference_type i = 0; i < n; ++i)
1563 {
1564 create_element_back(*range_begin);
1565 ++range_begin;
1566 }
1567
1568 position = _end - n;
1569 }
1570 else
1571 {
1572 // Non-const insert iterator.
1573 position = iterator(insert_position.index, *this, p_buffer);
1574
1575 // Are we closer to the front?
1576 if (distance(_begin, insert_position) < difference_type(current_size / 2))
1577 {
1578 size_t n_insert = n;
1579 size_t n_move = etl::distance(begin(), position);
1580 size_t n_create_copy = etl::min(n_insert, n_move);
1583 size_t n_copy_old = n_move - n_create_copy;
1584
1585 // Remember the original start.
1586 iterator from;
1587 iterator to;
1588
1589 // Create new.
1590 create_element_front(n_create_new, range_begin);
1591
1592 // Create copy.
1593 create_element_front(n_create_copy, _begin + n_create_new);
1594
1595 // Move old.
1596 from = position - n_copy_old;
1597 to = _begin + n_create_copy;
1598 etl::move(from, from + n_copy_old, to);
1599
1600 // Copy new.
1601 to = position - n_create_copy;
1603 etl::copy(range_begin, range_begin + n_copy_new, to);
1604
1605 position = _begin + n_move;
1606 }
1607 else
1608 {
1609 size_t n_insert = n;
1610 size_t n_move = etl::distance(position, end());
1611 size_t n_create_copy = etl::min(n_insert, n_move);
1614 size_t n_copy_old = n_move - n_create_copy;
1615
1616 // Create new.
1618 for (size_t i = 0UL; i < n_create_new; ++i)
1619 {
1620 create_element_back(*item);
1621 ++item;
1622 }
1623
1624 // Create copy.
1625 const_iterator from = position + n_copy_old;
1626
1627 for (size_t i = 0UL; i < n_create_copy; ++i)
1628 {
1629 create_element_back(*from);
1630 ++from;
1631 }
1632
1633 // Move old.
1634 etl::move_backward(position, position + n_copy_old, position + n_insert + n_copy_old);
1635
1636 // Copy new.
1637 item = range_begin;
1638 etl::copy(item, item + n_copy_new, position);
1639 }
1640 }
1641
1642 return position;
1643 }
1644
1645 //*************************************************************************
1649 //*************************************************************************
1651 {
1652 iterator position(to_iterator(erase_position));
1653 //iterator position(erase_position.index, *this, p_buffer);
1654
1655 ETL_ASSERT(distance(position) <= difference_type(current_size), ETL_ERROR(deque_out_of_bounds));
1656
1657 if (position == _begin)
1658 {
1659 destroy_element_front();
1660 position = begin();
1661 }
1662 else if (position == _end - 1)
1663 {
1664 destroy_element_back();
1665 position = end();
1666 }
1667 else
1668 {
1669 // Are we closer to the front?
1670 if (distance(_begin, position) < difference_type(current_size / 2))
1671 {
1672 etl::move_backward(_begin, position, position + 1);
1673 destroy_element_front();
1674 ++position;
1675 }
1676 else
1677 {
1678 etl::move(position + 1, _end, position);
1679 destroy_element_back();
1680 }
1681 }
1682
1683 return position;
1684 }
1685
1686 //*************************************************************************
1691 //*************************************************************************
1693 {
1694 iterator position(to_iterator(range_begin));
1695
1696 ETL_ASSERT((distance(range_begin) <= difference_type(current_size)) && (distance(range_end) <= difference_type(current_size)), ETL_ERROR(deque_out_of_bounds));
1697
1698 // How many to erase?
1699 size_t length = etl::distance(range_begin, range_end);
1700
1701 // At the beginning?
1702 if (position == _begin)
1703 {
1704 for (size_t i = 0UL; i < length; ++i)
1705 {
1706 destroy_element_front();
1707 }
1708
1709 position = begin();
1710 }
1711 // At the end?
1712 else if (position == _end - length)
1713 {
1714 for (size_t i = 0UL; i < length; ++i)
1715 {
1716 destroy_element_back();
1717 }
1718
1719 position = end();
1720 }
1721 else
1722 {
1723 // Copy the smallest number of items.
1724 // Are we closer to the front?
1725 if (distance(_begin, position) < difference_type(current_size / 2))
1726 {
1727 // Move the items.
1728 etl::move_backward(_begin, position, position + length);
1729
1730 for (size_t i = 0UL; i < length; ++i)
1731 {
1732 destroy_element_front();
1733 }
1734
1735 position += length;
1736 }
1737 else
1738 // Must be closer to the back.
1739 {
1740 // Move the items.
1741 etl::move(position + length, _end, position);
1742
1743 for (size_t i = 0UL; i < length; ++i)
1744 {
1745 destroy_element_back();
1746 }
1747 }
1748 }
1749
1750 return position;
1751 }
1752
1753 //*************************************************************************
1757 //*************************************************************************
1759 {
1760#if defined(ETL_CHECK_PUSH_POP)
1761 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1762#endif
1763 create_element_back(item);
1764 }
1765
1766#if ETL_USING_CPP11
1767 //*************************************************************************
1771 //*************************************************************************
1773 {
1774#if defined(ETL_CHECK_PUSH_POP)
1775 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1776#endif
1777 create_element_back(etl::move(item));
1778 }
1779#endif
1780
1781#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
1782 //*************************************************************************
1785 //*************************************************************************
1786 template <typename ... Args>
1787 reference emplace_back(Args && ... args)
1788 {
1789#if defined(ETL_CHECK_PUSH_POP)
1790 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1791#endif
1792
1793 ::new (&(*_end)) T(etl::forward<Args>(args)...);
1794 ++_end;
1795 ++current_size;
1796 ETL_INCREMENT_DEBUG_COUNT;
1797 return back();
1798 }
1799
1800#else
1801
1802 //*************************************************************************
1805 //*************************************************************************
1807 {
1808#if defined(ETL_CHECK_PUSH_POP)
1809 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1810#endif
1811
1812 ::new (&(*_end)) T();
1813 ++_end;
1814 ++current_size;
1815 ETL_INCREMENT_DEBUG_COUNT;
1816 return back();
1817 }
1818
1819 //*************************************************************************
1822 //*************************************************************************
1823 template <typename T1>
1825 {
1826#if defined(ETL_CHECK_PUSH_POP)
1827 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1828#endif
1829
1830 ::new (&(*_end)) T(value1);
1831 ++_end;
1832 ++current_size;
1833 ETL_INCREMENT_DEBUG_COUNT;
1834 return back();
1835 }
1836
1837 //*************************************************************************
1840 //*************************************************************************
1841 template <typename T1, typename T2>
1842 reference emplace_back(const T1& value1, const T2& value2)
1843 {
1844#if defined(ETL_CHECK_PUSH_POP)
1845 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1846#endif
1847
1848 ::new (&(*_end)) T(value1, value2);
1849 ++_end;
1850 ++current_size;
1851 ETL_INCREMENT_DEBUG_COUNT;
1852 return back();
1853 }
1854
1855 //*************************************************************************
1858 //*************************************************************************
1859 template <typename T1, typename T2, typename T3>
1860 reference emplace_back(const T1& value1, const T2& value2, const T3& value3)
1861 {
1862#if defined(ETL_CHECK_PUSH_POP)
1863 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1864#endif
1865
1866 ::new (&(*_end)) T(value1, value2, value3);
1867 ++_end;
1868 ++current_size;
1869 ETL_INCREMENT_DEBUG_COUNT;
1870 return back();
1871 }
1872
1873 //*************************************************************************
1876 //*************************************************************************
1877 template <typename T1, typename T2, typename T3, typename T4>
1878 reference emplace_back(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
1879 {
1880#if defined(ETL_CHECK_PUSH_POP)
1881 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1882#endif
1883
1884 ::new (&(*_end)) T(value1, value2, value3, value4);
1885 ++_end;
1886 ++current_size;
1887 ETL_INCREMENT_DEBUG_COUNT;
1888 return back();
1889 }
1890#endif
1891
1892 //*************************************************************************
1894 //*************************************************************************
1896 {
1897#if defined(ETL_CHECK_PUSH_POP)
1898 ETL_ASSERT(!empty(), ETL_ERROR(deque_empty));
1899#endif
1900 destroy_element_back();
1901 }
1902
1903 //*************************************************************************
1907 //*************************************************************************
1909 {
1910#if defined(ETL_CHECK_PUSH_POP)
1911 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1912#endif
1913 create_element_front(item);
1914 }
1915
1916#if ETL_USING_CPP11
1917 //*************************************************************************
1921 //*************************************************************************
1923 {
1924#if defined(ETL_CHECK_PUSH_POP)
1925 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1926#endif
1927 create_element_front(etl::move(item));
1928 }
1929#endif
1930
1931#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
1932 //*************************************************************************
1935 //*************************************************************************
1936 template <typename ... Args>
1937 reference emplace_front(Args && ... args)
1938 {
1939#if defined(ETL_CHECK_PUSH_POP)
1940 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1941#endif
1942
1943 --_begin;
1944 ::new (&(*_begin)) T(etl::forward<Args>(args)...);
1945 ++current_size;
1946 ETL_INCREMENT_DEBUG_COUNT;
1947 return front();
1948 }
1949
1950#else
1951
1952 //*************************************************************************
1955 //*************************************************************************
1957 {
1958#if defined(ETL_CHECK_PUSH_POP)
1959 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1960#endif
1961
1962 --_begin;
1963 ::new (&(*_begin)) T();
1964 ++current_size;
1965 ETL_INCREMENT_DEBUG_COUNT;
1966 return front();
1967 }
1968
1969 //*************************************************************************
1972 //*************************************************************************
1973 template <typename T1>
1975 {
1976#if defined(ETL_CHECK_PUSH_POP)
1977 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1978#endif
1979
1980 --_begin;
1981 ::new (&(*_begin)) T(value1);
1982 ++current_size;
1983 ETL_INCREMENT_DEBUG_COUNT;
1984 return front();
1985 }
1986
1987 //*************************************************************************
1990 //*************************************************************************
1991 template <typename T1, typename T2>
1992 reference emplace_front(const T1& value1, const T2& value2)
1993 {
1994#if defined(ETL_CHECK_PUSH_POP)
1995 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1996#endif
1997
1998 --_begin;
1999 ::new (&(*_begin)) T(value1, value2);
2000 ++current_size;
2001 ETL_INCREMENT_DEBUG_COUNT;
2002 return front();
2003 }
2004
2005 //*************************************************************************
2008 //*************************************************************************
2009 template <typename T1, typename T2, typename T3>
2010 reference emplace_front(const T1& value1, const T2& value2, const T3& value3)
2011 {
2012#if defined(ETL_CHECK_PUSH_POP)
2013 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
2014#endif
2015
2016 --_begin;
2017 ::new (&(*_begin)) T(value1, value2, value3);
2018 ++current_size;
2019 ETL_INCREMENT_DEBUG_COUNT;
2020 return front();
2021 }
2022
2023 //*************************************************************************
2026 //*************************************************************************
2027 template <typename T1, typename T2, typename T3, typename T4>
2028 reference emplace_front(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
2029 {
2030#if defined(ETL_CHECK_PUSH_POP)
2031 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
2032#endif
2033
2034 --_begin;
2035 ::new (&(*_begin)) T(value1, value2, value3, value4);
2036 ++current_size;
2037 ETL_INCREMENT_DEBUG_COUNT;
2038 return front();
2039 }
2040#endif
2041
2042 //*************************************************************************
2044 //*************************************************************************
2046 {
2047#if defined(ETL_CHECK_PUSH_POP)
2048 ETL_ASSERT(!empty(), ETL_ERROR(deque_empty));
2049#endif
2050 destroy_element_front();
2051 }
2052
2053 //*************************************************************************
2058 //*************************************************************************
2059 void resize(size_t new_size, const value_type& value = value_type())
2060 {
2061 ETL_ASSERT(new_size <= CAPACITY, ETL_ERROR(deque_full));
2062
2063 // Make it smaller?
2064 if (new_size < current_size)
2065 {
2066 while (current_size > new_size)
2067 {
2068 destroy_element_back();
2069 }
2070 }
2071 // Make it larger?
2072 else if (new_size > current_size)
2073 {
2074 size_t count = new_size - current_size;
2075
2076 for (size_t i = 0UL; i < count; ++i)
2077 {
2078 create_element_back(value);
2079 }
2080 }
2081 }
2082
2083 //*************************************************************************
2085 //*************************************************************************
2086 friend difference_type operator -(const iterator& lhs, const iterator& rhs)
2087 {
2088 return distance(rhs, lhs);
2089 }
2090
2091 //*************************************************************************
2093 //*************************************************************************
2094 friend difference_type operator -(const const_iterator& lhs, const const_iterator& rhs)
2095 {
2096 return distance(rhs, lhs);
2097 }
2098
2099 //*************************************************************************
2101 //*************************************************************************
2103 {
2104 if (&rhs != this)
2105 {
2106 assign(rhs.begin(), rhs.end());
2107 }
2108
2109 return *this;
2110 }
2111
2112#if ETL_USING_CPP11
2113 //*************************************************************************
2115 //*************************************************************************
2117 {
2118 if (&rhs != this)
2119 {
2120 clear();
2121 iterator itr = rhs.begin();
2122 while (itr != rhs.end())
2123 {
2124 push_back(etl::move(*itr));
2125 ++itr;
2126 }
2127
2128 rhs.initialise();
2129 }
2130
2131 return *this;
2132 }
2133#endif
2134
2135#ifdef ETL_IDEQUE_REPAIR_ENABLE
2136 //*************************************************************************
2138 //*************************************************************************
2139 virtual void repair() = 0;
2140#endif
2141
2142 protected:
2143
2144 //*************************************************************************
2146 //*************************************************************************
2152
2153 //*********************************************************************
2155 //*********************************************************************
2157 {
2158 if ETL_IF_CONSTEXPR(etl::is_trivially_destructible<T>::value)
2159 {
2160 current_size = 0;
2161 ETL_RESET_DEBUG_COUNT;
2162 }
2163 else
2164 {
2165 while (current_size > 0)
2166 {
2167 destroy_element_back();
2168 }
2169 }
2170
2171 _begin = iterator(0, *this, p_buffer);
2172 _end = iterator(0, *this, p_buffer);
2173 }
2174
2175 //*************************************************************************
2177 //*************************************************************************
2179 {
2181
2182 _begin = iterator(_begin.index, *this, p_buffer);
2183 _end = iterator(_end.index, *this, p_buffer);
2184 }
2185
2186 iterator _begin;
2189
2190 private:
2191
2192 //*********************************************************************
2194 //*********************************************************************
2195 void create_element_front()
2196 {
2197 --_begin;
2198 ::new (&(*_begin)) T();
2199 ++current_size;
2200 ETL_INCREMENT_DEBUG_COUNT;
2201 }
2202
2203 //*********************************************************************
2205 //*********************************************************************
2206 template <typename TIterator>
2207 void create_element_front(size_t n, TIterator from)
2208 {
2209 if (n == 0)
2210 {
2211 return;
2212 }
2213
2214 _begin -= n;
2215
2216 iterator item = _begin;
2217
2218 do
2219 {
2220 ::new (&(*item)) T(*from);
2221 ++item;
2222 ++from;
2223 ++current_size;
2224 ETL_INCREMENT_DEBUG_COUNT;
2225 } while (--n != 0);
2226 }
2227
2228 //*********************************************************************
2230 //*********************************************************************
2231 void create_element_back()
2232 {
2233 ::new (&(*_end)) T();
2234 ++_end;
2235 ++current_size;
2236 ETL_INCREMENT_DEBUG_COUNT;
2237 }
2238
2239 //*********************************************************************
2241 //*********************************************************************
2242 void create_element_front(const_reference value)
2243 {
2244 --_begin;
2245 ::new (&(*_begin)) T(value);
2246 ++current_size;
2247 ETL_INCREMENT_DEBUG_COUNT;
2248 }
2249
2250 //*********************************************************************
2252 //*********************************************************************
2253 void create_element_back(const_reference value)
2254 {
2255 ::new (&(*_end)) T(value);
2256 ++_end;
2257 ++current_size;
2258 ETL_INCREMENT_DEBUG_COUNT;
2259 }
2260
2261#if ETL_USING_CPP11
2262 //*********************************************************************
2264 //*********************************************************************
2265 void create_element_front(rvalue_reference value)
2266 {
2267 --_begin;
2268 ::new (&(*_begin)) T(etl::move(value));
2269 ++current_size;
2270 ETL_INCREMENT_DEBUG_COUNT;
2271 }
2272
2273 //*********************************************************************
2275 //*********************************************************************
2276 void create_element_back(rvalue_reference value)
2277 {
2278 ::new (&(*_end)) T(etl::move(value));
2279 ++_end;
2280 ++current_size;
2281 ETL_INCREMENT_DEBUG_COUNT;
2282 }
2283#endif
2284
2285 //*********************************************************************
2287 //*********************************************************************
2288 void destroy_element_front()
2289 {
2290 (*_begin).~T();
2291 --current_size;
2292 ETL_DECREMENT_DEBUG_COUNT;
2293 ++_begin;
2294 }
2295
2296 //*********************************************************************
2298 //*********************************************************************
2299 void destroy_element_back()
2300 {
2301 --_end;
2302 (*_end).~T();
2303 --current_size;
2304 ETL_DECREMENT_DEBUG_COUNT;
2305 }
2306
2307 //*************************************************************************
2309 //*************************************************************************
2310 template <typename TIterator1, typename TIterator2>
2311 static difference_type distance(const TIterator1& range_begin, const TIterator2& range_end)
2312 {
2313 difference_type distance1 = distance(range_begin);
2314 difference_type distance2 = distance(range_end);
2315
2316 return distance2 - distance1;
2317 }
2318
2319 //*************************************************************************
2321 //*************************************************************************
2322 template <typename TIterator>
2323 static difference_type distance(const TIterator& other)
2324 {
2325 const difference_type index = other.get_index();
2326 const difference_type reference_index = other.container()._begin.index;
2327 const size_t buffer_size = other.container().BUFFER_SIZE;
2328
2329 if (index < reference_index)
2330 {
2331 return buffer_size + index - reference_index;
2332 }
2333 else
2334 {
2335 return index - reference_index;
2336 }
2337 }
2338
2339 //*************************************************************************
2341 //*************************************************************************
2342 iterator to_iterator(const_iterator itr) const
2343 {
2344 return iterator(itr.index, const_cast<ideque&>(*this), p_buffer);
2345 }
2346
2347 // Disable copy construction.
2348 ideque(const ideque&);
2349
2350 //*************************************************************************
2352 //*************************************************************************
2353#if defined(ETL_POLYMORPHIC_DEQUE) || defined(ETL_POLYMORPHIC_CONTAINERS) || defined(ETL_IDEQUE_REPAIR_ENABLE)
2354 public:
2355 virtual ~ideque()
2356 {
2357 }
2358#else
2359 protected:
2361 {
2362 }
2363#endif
2364 };
2365
2366 //***************************************************************************
2372 //***************************************************************************
2373 template <typename T, const size_t MAX_SIZE_>
2374 class deque : public etl::ideque<T>
2375 {
2376 public:
2377
2378 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
2379
2380 private:
2381
2382 static ETL_CONSTANT size_t BUFFER_SIZE = MAX_SIZE + 1;
2383
2384 public:
2385
2386 typedef T value_type;
2387 typedef T* pointer;
2388 typedef const T* const_pointer;
2389 typedef T& reference;
2390 typedef const T& const_reference;
2391 typedef size_t size_type;
2392 typedef typename etl::iterator_traits<pointer>::difference_type difference_type;
2393
2394 //*************************************************************************
2396 //*************************************************************************
2398 : etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2399 {
2400 this->initialise();
2401 }
2402
2403 //*************************************************************************
2405 //*************************************************************************
2407 {
2408 this->initialise();
2409 }
2410
2411 //*************************************************************************
2413 //*************************************************************************
2415 : etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2416 {
2417 if (this != &other)
2418 {
2419 this->assign(other.begin(), other.end());
2420 }
2421 }
2422
2423#if ETL_USING_CPP11
2424 //*************************************************************************
2426 //*************************************************************************
2427 deque(deque&& other)
2428 : etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2429 {
2430 if (this != &other)
2431 {
2432 this->initialise();
2433
2434 typename etl::ideque<T>::iterator itr = other.begin();
2435 while (itr != other.end())
2436 {
2437 this->push_back(etl::move(*itr));
2438 ++itr;
2439 }
2440 }
2441 }
2442#endif
2443
2444 //*************************************************************************
2446 //*************************************************************************
2447 template <typename TIterator>
2449 : etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2450 {
2451 this->assign(begin_, end_);
2452 }
2453
2454 //*************************************************************************
2456 //*************************************************************************
2457 explicit deque(size_t n, const_reference value = value_type())
2458 : etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2459 {
2460 this->assign(n, value);
2461 }
2462
2463#if ETL_HAS_INITIALIZER_LIST
2464 //*************************************************************************
2466 //*************************************************************************
2467 deque(std::initializer_list<T> init)
2468 : ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2469 {
2470 this->assign(init.begin(), init.end());
2471 }
2472#endif
2473
2474 //*************************************************************************
2476 //*************************************************************************
2478 {
2479 if (&rhs != this)
2480 {
2481 this->assign(rhs.begin(), rhs.end());
2482 }
2483
2484 return *this;
2485 }
2486
2487#if ETL_USING_CPP11
2488 //*************************************************************************
2490 //*************************************************************************
2492 {
2493 if (&rhs != this)
2494 {
2495 this->clear();
2496 typename etl::ideque<T>::iterator itr = rhs.begin();
2497 while (itr != rhs.end())
2498 {
2499 this->push_back(etl::move(*itr));
2500 ++itr;
2501 }
2502 }
2503
2504 return *this;
2505 }
2506#endif
2507
2508 //*************************************************************************
2510 //*************************************************************************
2511#ifdef ETL_IDEQUE_REPAIR_ENABLE
2512 virtual void repair() ETL_OVERRIDE
2513#else
2514 void repair()
2515#endif
2516 {
2517#if ETL_CPP11_TYPE_TRAITS_IS_TRIVIAL_SUPPORTED
2519#endif
2520
2521 etl::ideque<T>::repair_buffer(reinterpret_cast<T*>(buffer.raw));
2522 }
2523
2524 private:
2525
2528 };
2529
2530 template <typename T, const size_t MAX_SIZE_>
2531 ETL_CONSTANT size_t deque<T, MAX_SIZE_>::MAX_SIZE;
2532
2533 //*************************************************************************
2535 //*************************************************************************
2536#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2537 template <typename... T>
2538 deque(T...) -> deque<typename etl::common_type_t<T...>, sizeof...(T)>;
2539#endif
2540
2541 //*************************************************************************
2543 //*************************************************************************
2544#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2545 template <typename T, typename... TValues>
2546 constexpr auto make_deque(TValues&&... values) -> etl::deque<T, sizeof...(TValues)>
2547 {
2548 return { etl::forward<T>(values)... };
2549 }
2550#endif
2551
2552 //***************************************************************************
2558 //***************************************************************************
2559 template <typename T>
2561 {
2562 return (lhs.size() == rhs.size()) && etl::equal(lhs.begin(), lhs.end(), rhs.begin());
2563 }
2564
2565 //***************************************************************************
2571 //***************************************************************************
2572 template <typename T>
2574 {
2575 return !(lhs == rhs);
2576 }
2577
2578 //***************************************************************************
2584 //***************************************************************************
2585 template <typename T>
2587 {
2588 return etl::lexicographical_compare(lhs.begin(),
2589 lhs.end(),
2590 rhs.begin(),
2591 rhs.end());
2592 }
2593
2594 //***************************************************************************
2600 //***************************************************************************
2601 template <typename T>
2603 {
2604 return !(lhs > rhs);
2605 }
2606
2607 //***************************************************************************
2613 //***************************************************************************
2614 template <typename T>
2616 {
2617 return (rhs < lhs);
2618 }
2619
2620 //***************************************************************************
2626 //***************************************************************************
2627 template <typename T>
2629 {
2630 return !(lhs < rhs);
2631 }
2632}
2633
2634#include "private/minmax_pop.h"
2635
2636#endif
Const Iterator.
Definition deque.h:498
Iterator.
Definition deque.h:244
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:966
reference emplace_front(const T1 &value1)
Definition deque.h:1974
reference emplace_back(const T1 &value1, const T2 &value2, const T3 &value3)
Definition deque.h:1860
const_reverse_iterator crbegin() const
Gets a const reverse iterator to the end of the deque.
Definition deque.h:948
void clear()
Clears the deque.
Definition deque.h:980
iterator erase(const_iterator erase_position)
Definition deque.h:1650
const size_type CAPACITY
The maximum number of elements in the deque.
Definition deque.h:214
void pop_back()
Removes the oldest item from the deque.
Definition deque.h:1895
ideque & operator=(const ideque &rhs)
Assignment operator.
Definition deque.h:2102
const size_type BUFFER_SIZE
The number of elements in the buffer.
Definition deque.h:215
const_reverse_iterator rbegin() const
Gets a const reverse iterator to the end of the deque.
Definition deque.h:940
ETL_DECLARE_DEBUG_COUNT
Internal debugging.
Definition deque.h:216
void resize(size_t new_size, const value_type &value=value_type())
Definition deque.h:2059
iterator emplace(const_iterator insert_position, const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition deque.h:1368
iterator begin()
Gets an iterator to the beginning of the deque.
Definition deque.h:884
reference front()
Definition deque.h:849
reference at(size_t index)
Definition deque.h:796
reference emplace_back(const T1 &value1, const T2 &value2)
Definition deque.h:1842
pointer p_buffer
Iterator to the _end item in the deque.
Definition deque.h:2188
friend difference_type operator-(const iterator &lhs, const iterator &rhs)
Definition deque.h:2086
reference emplace_front(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition deque.h:2028
reference emplace_front()
Definition deque.h:1956
etl::enable_if<!etl::is_integral< TIterator >::value, void >::type assign(TIterator range_begin, TIterator range_end)
Assigns a range to the deque.
Definition deque.h:761
void initialise()
Initialise the deque.
Definition deque.h:2156
reference operator[](size_t index)
Definition deque.h:825
~deque_base()
Destructor.
Definition deque.h:209
iterator _end
Iterator to the _begin item in the deque.
Definition deque.h:2187
reference emplace_front(const T1 &value1, const T2 &value2, const T3 &value3)
Definition deque.h:2010
size_type size() const
Definition deque.h:144
const_reference at(size_t index) const
Definition deque.h:811
const_reverse_iterator crend() const
Gets a const reverse iterator to the beginning of the deque.
Definition deque.h:972
iterator end()
Gets an iterator to the end of the deque.
Definition deque.h:908
const_iterator end() const
Gets a const iterator to the end of the deque.
Definition deque.h:916
void push_front(const_reference item)
Definition deque.h:1908
size_type max_size() const
Definition deque.h:171
~ideque()
Destructor.
Definition deque.h:2360
iterator erase(const_iterator range_begin, const_iterator range_end)
Definition deque.h:1692
iterator emplace(const_iterator insert_position, const T1 &value1)
Definition deque.h:1173
deque(const deque &other)
Copy constructor.
Definition deque.h:2414
iterator emplace(const_iterator insert_position, const T1 &value1, const T2 &value2)
Definition deque.h:1238
iterator insert(const_iterator insert_position, size_type n, const value_type &value)
Definition deque.h:1435
enable_if<!etl::is_integral< TIterator >::value, iterator >::type insert(const_iterator insert_position, TIterator range_begin, TIterator range_end)
Definition deque.h:1546
bool full() const
Definition deque.h:162
size_type capacity() const
Definition deque.h:180
const_reference back() const
Definition deque.h:876
bool empty() const
Definition deque.h:153
void repair()
Fix the internal pointers after a low level memory copy.
Definition deque.h:2514
const_reverse_iterator rend() const
Gets a const reverse iterator to the beginning of the deque.
Definition deque.h:964
const_iterator cend() const
Gets a const iterator to the end of the deque.
Definition deque.h:924
reference emplace_back(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition deque.h:1878
reference emplace_back()
Definition deque.h:1806
deque_base(size_t max_size_, size_t buffer_size_)
Constructor.
Definition deque.h:199
reference emplace_front(const T1 &value1, const T2 &value2)
Definition deque.h:1992
void assign(size_type n, const value_type &value)
Definition deque.h:778
deque()
Default constructor.
Definition deque.h:2397
reference back()
Definition deque.h:867
iterator emplace(const_iterator insert_position, const T1 &value1, const T2 &value2, const T3 &value3)
Definition deque.h:1303
reverse_iterator rbegin()
Gets a reverse iterator to the end of the deque.
Definition deque.h:932
void fill(const T &value)
Fills the deque.
Definition deque.h:988
void pop_front()
Removes the oldest item from the deque.
Definition deque.h:2045
reference emplace_back(const T1 &value1)
Definition deque.h:1824
void push_back(const_reference item)
Definition deque.h:1758
const_iterator cbegin() const
Gets a const iterator to the beginning of the deque.
Definition deque.h:900
deque(TIterator begin_, TIterator end_, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Assigns data to the deque.
Definition deque.h:2448
~deque()
Destructor.
Definition deque.h:2406
reverse_iterator rend()
Gets a reverse iterator to the beginning of the deque.
Definition deque.h:956
const_reference front() const
Definition deque.h:858
deque(size_t n, const_reference value=value_type())
Assigns data to the deque.
Definition deque.h:2457
size_t available() const
Definition deque.h:189
deque & operator=(const deque &rhs)
Assignment operator.
Definition deque.h:2477
const_iterator begin() const
Gets a const iterator to the beginning of the deque.
Definition deque.h:892
iterator insert(const_iterator insert_position, const value_type &value)
Definition deque.h:999
void repair_buffer(pointer p_buffer_)
Fix the internal pointers after a low level memory copy.
Definition deque.h:2178
size_type current_size
The current number of elements in the deque.
Definition deque.h:213
ideque(pointer p_buffer_, size_t max_size_, size_t buffer_size_)
Constructor.
Definition deque.h:2147
Definition deque.h:2375
Definition deque.h:135
Definition deque.h:93
Definition deque.h:65
Definition deque.h:79
Definition deque.h:107
Definition deque.h:226
#define ETL_ASSERT(b, e)
Definition error_handler.h:316
Definition exception.h:47
ETL_CONSTEXPR17 etl::enable_if<!etl::is_same< T, etl::nullptr_t >::value, T >::type * addressof(T &t)
Definition addressof.h:52
enable_if
Definition type_traits_generator.h:1191
is_integral
Definition type_traits_generator.h:1001
Definition deque.h:121
bitset_ext
Definition absolute.h:38
bool operator>(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:693
bool operator>=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:705
bool operator!=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:654
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:642
bool operator<(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:666
bool operator<=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:681
Definition type_traits_generator.h:2115
Definition type_traits_generator.h:2101
iterator
Definition iterator.h:399
pair holds two objects of arbitrary type
Definition utility.h:164