Embedded Template Library 1.0
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 "iterator.h"
45#include "placement_new.h"
46#include "initializer_list.h"
47
48#include <stddef.h>
49#include <stdint.h>
50
51#include "private/minmax_push.h"
52
53//*****************************************************************************
57//*****************************************************************************
58
59namespace etl
60{
61 //***************************************************************************
64 //***************************************************************************
66 {
67 public:
68
69 deque_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
70 : exception(reason_, file_name_, line_number_)
71 {
72 }
73 };
74
75 //***************************************************************************
78 //***************************************************************************
80 {
81 public:
82
83 deque_full(string_type file_name_, numeric_type line_number_)
84 : etl::deque_exception(ETL_ERROR_TEXT("deque:full", ETL_DEQUE_FILE_ID"A"), file_name_, line_number_)
85 {
86 }
87 };
88
89 //***************************************************************************
92 //***************************************************************************
94 {
95 public:
96
97 deque_empty(string_type file_name_, numeric_type line_number_)
98 : etl::deque_exception(ETL_ERROR_TEXT("deque:empty", ETL_DEQUE_FILE_ID"B"), file_name_, line_number_)
99 {
100 }
101 };
102
103 //***************************************************************************
106 //***************************************************************************
108 {
109 public:
110
111 deque_out_of_bounds(string_type file_name_, numeric_type line_number_)
112 : etl::deque_exception(ETL_ERROR_TEXT("deque:bounds", ETL_DEQUE_FILE_ID"C"), file_name_, line_number_)
113 {
114 }
115 };
116
117 //***************************************************************************
120 //***************************************************************************
122 {
123 public:
124
125 deque_incompatible_type(string_type file_name_, numeric_type line_number_)
126 : deque_exception(ETL_ERROR_TEXT("deque:type", ETL_DEQUE_FILE_ID"D"), file_name_, line_number_)
127 {
128 }
129 };
130
131 //***************************************************************************
134 //***************************************************************************
136 {
137 public:
138
139 typedef size_t size_type;
140
141 //*************************************************************************
144 //*************************************************************************
145 size_type size() const
146 {
147 return current_size;
148 }
149
150 //*************************************************************************
153 //*************************************************************************
154 bool empty() const
155 {
156 return (current_size == 0);
157 }
158
159 //*************************************************************************
162 //*************************************************************************
163 bool full() const
164 {
165 return current_size == CAPACITY;
166 }
167
168 //*************************************************************************
171 //*************************************************************************
172 size_type max_size() const
173 {
174 return CAPACITY;
175 }
176
177 //*************************************************************************
180 //*************************************************************************
181 size_type capacity() const
182 {
183 return CAPACITY;
184 }
185
186 //*************************************************************************
189 //*************************************************************************
190 size_t available() const
191 {
192 return max_size() - size();
193 }
194
195 protected:
196
197 //*************************************************************************
199 //*************************************************************************
200 deque_base(size_t max_size_, size_t buffer_size_)
201 : current_size(0),
202 CAPACITY(max_size_),
203 BUFFER_SIZE(buffer_size_)
204 {
205 }
206
207 //*************************************************************************
209 //*************************************************************************
211 {
212 }
213
214 size_type current_size;
215 const size_type CAPACITY;
216 const size_type BUFFER_SIZE;
217 ETL_DECLARE_DEBUG_COUNT
218 };
219
220 //***************************************************************************
224 //***************************************************************************
225 template <typename T>
226 class ideque : public etl::deque_base
227 {
228 public:
229
230 typedef T value_type;
231 typedef size_t size_type;
232 typedef T& reference;
233 typedef const T& const_reference;
234#if ETL_USING_CPP11
235 typedef T&& rvalue_reference;
236#endif
237 typedef T* pointer;
238 typedef const T* const_pointer;
239 typedef typename etl::iterator_traits<pointer>::difference_type difference_type;
240
241 //*************************************************************************
243 //*************************************************************************
244 class iterator : public etl::iterator<ETL_OR_STD::random_access_iterator_tag, T>
245 {
246 public:
247
248 friend class ideque;
249 friend class const_iterator;
250
251 //***************************************************
252 iterator()
253 : index(0)
254 , p_deque(0)
255 , p_buffer(0)
256 {
257 }
258
259 //***************************************************
260 iterator(const iterator& other)
261 : index(other.index),
262 p_deque(other.p_deque),
263 p_buffer(other.p_buffer)
264 {
265 }
266
267 //***************************************************
268 iterator& operator =(const iterator& other)
269 {
270 index = other.index;
271 p_deque = other.p_deque;
272 p_buffer = other.p_buffer;
273
274 return *this;
275 }
276
277 //***************************************************
278 iterator& operator ++()
279 {
280 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1;
281
282 return *this;
283 }
284
285 //***************************************************
286 iterator operator ++(int)
287 {
288 iterator previous(*this);
289 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1;
290
291 return previous;
292 }
293
294 //***************************************************
295 iterator& operator +=(difference_type offset)
296 {
297 if (offset > 0)
298 {
299 index += offset;
300 index = (static_cast<size_t>(index) > p_deque->BUFFER_SIZE - 1) ? index - p_deque->BUFFER_SIZE : index;
301 }
302 else if (offset < 0)
303 {
304 operator -= (-offset);
305 }
306
307 return *this;
308 }
309
310 //***************************************************
311 iterator& operator -=(difference_type offset)
312 {
313 if (offset > 0)
314 {
315 index -= offset;
316 index = (index < 0) ? index + p_deque->BUFFER_SIZE : index;
317 }
318 else if (offset < 0)
319 {
320 operator += (-offset);
321 }
322
323 return *this;
324 }
325
326 //***************************************************
327 iterator& operator --()
328 {
329 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1;
330
331 return *this;
332 }
333
334 //***************************************************
335 iterator operator --(int)
336 {
337 iterator previous(*this);
338 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1;
339
340 return previous;
341 }
342
343 //***************************************************
344 reference operator *() const
345 {
346 return p_buffer[index];
347 }
348
349 //***************************************************
350 pointer operator ->() const
351 {
352 return &p_buffer[index];
353 }
354
355 //***************************************************
356 friend iterator operator +(const iterator& lhs, difference_type offset)
357 {
358 iterator result(lhs);
359 result += offset;
360 return result;
361 }
362
363 //***************************************************
364 friend iterator operator -(const iterator& lhs, difference_type offset)
365 {
366 iterator result(lhs);
367 result -= offset;
368 return result;
369 }
370
371 //***************************************************
372 friend bool operator == (const iterator& lhs, const iterator& rhs)
373 {
374 return lhs.index == rhs.index;
375 }
376
377 //***************************************************
378 friend bool operator != (const iterator& lhs, const iterator& rhs)
379 {
380 return !(lhs == rhs);
381 }
382
383 //***************************************************
384 friend bool operator < (const iterator& lhs, const iterator& rhs)
385 {
386 const difference_type lhs_index = lhs.get_index();
387 const difference_type rhs_index = rhs.get_index();
388 const difference_type reference_index = lhs.container().begin().get_index();
389 const size_t buffer_size = lhs.container().max_size() + 1;
390
391 const difference_type lhs_distance = (lhs_index < reference_index) ? buffer_size + lhs_index - reference_index : lhs_index - reference_index;
392 const difference_type rhs_distance = (rhs_index < reference_index) ? buffer_size + rhs_index - reference_index : rhs_index - reference_index;
393
394 return lhs_distance < rhs_distance;
395 }
396
397 //***************************************************
398 friend bool operator <= (const iterator& lhs, const iterator& rhs)
399 {
400 return !(lhs > rhs);
401 }
402
403 //***************************************************
404 friend bool operator > (const iterator& lhs, const iterator& rhs)
405 {
406 return (rhs < lhs);
407 }
408
409 //***************************************************
410 friend bool operator >= (const iterator& lhs, const iterator& rhs)
411 {
412 return !(lhs < rhs);
413 }
414
415 //***************************************************
416 difference_type get_index() const
417 {
418 return index;
419 }
420
421 //***************************************************
422 ideque& container() const
423 {
424 return *p_deque;
425 }
426
427 //***************************************************
428 pointer get_buffer() const
429 {
430 return p_buffer;
431 }
432
433 //***************************************************
434 void swap(iterator& other)
435 {
436 using ETL_OR_STD::swap; // Allow ADL
437
438 swap(index, other.index);
439 }
440
441 private:
442
443 //***************************************************
444 difference_type distance(difference_type firstIndex, difference_type index_) const
445 {
446 if (index_ < firstIndex)
447 {
448 return p_deque->BUFFER_SIZE + index_ - firstIndex;
449 }
450 else
451 {
452 return index_ - firstIndex;
453 }
454 }
455
456 //***************************************************
457 iterator(difference_type index_, ideque& the_deque, pointer p_buffer_)
458 : index(index_)
459 , p_deque(&the_deque)
460 , p_buffer(p_buffer_)
461 {
462 }
463
464 difference_type index;
465 ideque* p_deque;
466 pointer p_buffer;
467 };
468
469 //*************************************************************************
471 //*************************************************************************
472 class const_iterator : public etl::iterator<ETL_OR_STD::random_access_iterator_tag, const T>
473 {
474 public:
475
476 friend class ideque;
477
478 //***************************************************
480 : index(0)
481 , p_deque(0)
482 , p_buffer(0)
483 {
484 }
485
486 //***************************************************
487 const_iterator(const const_iterator& other)
488 : index(other.index)
489 , p_deque(other.p_deque)
490 , p_buffer(other.p_buffer)
491 {
492 }
493
494 //***************************************************
495 const_iterator(const typename ideque::iterator& other)
496 : index(other.index)
497 , p_deque(other.p_deque)
498 , p_buffer(other.p_buffer)
499 {
500 }
501
502 //***************************************************
503 const_iterator& operator =(const const_iterator& other)
504 {
505 index = other.index;
506 p_deque = other.p_deque;
507 p_buffer = other.p_buffer;
508
509 return *this;
510 }
511
512 const_iterator& operator =(const typename ideque::iterator& other)
513 {
514 index = other.index;
515 p_deque = other.p_deque;
516 p_buffer = other.p_buffer;
517
518 return *this;
519 }
520
521 //***************************************************
522 const_iterator& operator ++()
523 {
524 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1;
525
526 return *this;
527 }
528
529 //***************************************************
530 const_iterator operator ++(int)
531 {
532 const_iterator previous(*this);
533 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1;
534
535 return previous;
536 }
537
538 //***************************************************
539 const_iterator& operator +=(difference_type offset)
540 {
541 if (offset > 0)
542 {
543 index += offset;
544 index = (static_cast<size_t>(index) > p_deque->BUFFER_SIZE - 1) ? index - p_deque->BUFFER_SIZE : index;
545 }
546 else if (offset < 0)
547 {
548 operator -= (-offset);
549 }
550
551 return *this;
552 }
553
554 //***************************************************
555 const_iterator& operator -=(difference_type offset)
556 {
557 if (offset > 0)
558 {
559 index -= offset;
560 index = (index < 0) ? static_cast<size_t>(index) + p_deque->BUFFER_SIZE : index;
561 }
562 else if (offset < 0)
563 {
564 operator += (-offset);
565 }
566
567 return *this;
568 }
569
570 //***************************************************
571 const_iterator& operator --()
572 {
573 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1;
574
575 return *this;
576 }
577
578 //***************************************************
579 const_iterator operator --(int)
580 {
581 const_iterator previous(*this);
582 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1;
583
584 return previous;
585 }
586
587 //***************************************************
588 const_reference operator *() const
589 {
590 return p_buffer[index];
591 }
592
593 //***************************************************
594 const_pointer operator ->() const
595 {
596 return &p_buffer[index];
597 }
598
599 //***************************************************
600 friend const_iterator operator +(const const_iterator& lhs, difference_type offset)
601 {
602 const_iterator result(lhs);
603 result += offset;
604 return result;
605 }
606
607 //***************************************************
608 friend const_iterator operator -(const const_iterator& lhs, difference_type offset)
609 {
610 const_iterator result(lhs);
611 result -= offset;
612 return result;
613 }
614
615 //***************************************************
616 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
617 {
618 return lhs.index == rhs.index;
619 }
620
621 //***************************************************
622 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
623 {
624 return !(lhs == rhs);
625 }
626
627 //***************************************************
628 friend bool operator < (const const_iterator& lhs, const const_iterator& rhs)
629 {
630 const difference_type lhs_index = lhs.get_index();
631 const difference_type rhs_index = rhs.get_index();
632 const difference_type reference_index = lhs.container().begin().get_index();
633 const size_t buffer_size = lhs.container().max_size() + 1UL;
634
635 const difference_type lhs_distance = (lhs_index < reference_index) ? buffer_size + lhs_index - reference_index : lhs_index - reference_index;
636 const difference_type rhs_distance = (rhs_index < reference_index) ? buffer_size + rhs_index - reference_index : rhs_index - reference_index;
637
638 return lhs_distance < rhs_distance;
639 }
640
641 //***************************************************
642 friend bool operator <= (const const_iterator& lhs, const const_iterator& rhs)
643 {
644 return !(lhs > rhs);
645 }
646
647 //***************************************************
648 friend bool operator > (const const_iterator& lhs, const const_iterator& rhs)
649 {
650 return (rhs < lhs);
651 }
652
653 //***************************************************
654 friend bool operator >= (const const_iterator& lhs, const const_iterator& rhs)
655 {
656 return !(lhs < rhs);
657 }
658
659 //***************************************************
660 difference_type get_index() const
661 {
662 return index;
663 }
664
665 //***************************************************
666 ideque& container() const
667 {
668 return *p_deque;
669 }
670
671 //***************************************************
672 pointer get_buffer() const
673 {
674 return p_buffer;
675 }
676
677 //***************************************************
678 void swap(const_iterator& other)
679 {
680 ETL_OR_STD::swap(index, other.index);
681 }
682
683 private:
684
685 //***************************************************
686 difference_type distance(difference_type firstIndex, difference_type index_) const
687 {
688 if (index_ < firstIndex)
689 {
690 return p_deque->BUFFER_SIZE + index_ - firstIndex;
691 }
692 else
693 {
694 return index_ - firstIndex;
695 }
696 }
697
698 //***************************************************
699 const_iterator(difference_type index_, ideque& the_deque, pointer p_buffer_)
700 : index(index_)
701 , p_deque(&the_deque)
702 , p_buffer(p_buffer_)
703 {
704 }
705
706 difference_type index;
707 ideque* p_deque;
708 pointer p_buffer;
709 };
710
711 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
712 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
713
714 //*************************************************************************
716 //*************************************************************************
717 template<typename TIterator>
719 assign(TIterator range_begin, TIterator range_end)
720 {
721 initialise();
722
723 while (range_begin != range_end)
724 {
725 push_back(*range_begin);
726 ++range_begin;
727 }
728 }
729
730 //*************************************************************************
735 //*************************************************************************
736 void assign(size_type n, const value_type& value)
737 {
738 ETL_ASSERT(n <= CAPACITY, ETL_ERROR(deque_full));
739
740 initialise();
741
742 while (n > 0)
743 {
744 create_element_back(value);
745 --n;
746 }
747 }
748
749 //*************************************************************************
753 //*************************************************************************
754 reference at(size_t index)
755 {
756 ETL_ASSERT(index < current_size, ETL_ERROR(deque_out_of_bounds));
757
758 iterator result(_begin);
759 result += index;
760
761 return *result;
762 }
763
764 //*************************************************************************
768 //*************************************************************************
769 const_reference at(size_t index) const
770 {
771 ETL_ASSERT(index < current_size, ETL_ERROR(deque_out_of_bounds));
772
773 iterator result(_begin);
774 result += index;
775
776 return *result;
777 }
778
779 //*************************************************************************
782 //*************************************************************************
783 reference operator [](size_t index)
784 {
785 iterator result(_begin);
786 result += index;
787
788 return *result;
789 }
790
791 //*************************************************************************
794 //*************************************************************************
795 const_reference operator [](size_t index) const
796 {
797 iterator result(_begin);
798 result += index;
799
800 return *result;
801 }
802
803 //*************************************************************************
806 //*************************************************************************
807 reference front()
808 {
809 return *_begin;
810 }
811
812 //*************************************************************************
815 //*************************************************************************
816 const_reference front() const
817 {
818 return *_begin;
819 }
820
821 //*************************************************************************
824 //*************************************************************************
825 reference back()
826 {
827 return *(_end - 1);
828 }
829
830 //*************************************************************************
833 //*************************************************************************
834 const_reference back() const
835 {
836 return *(_end - 1);
837 }
838
839 //*************************************************************************
841 //*************************************************************************
843 {
844 return _begin;
845 }
846
847 //*************************************************************************
849 //*************************************************************************
851 {
852 return _begin;
853 }
854
855 //*************************************************************************
857 //*************************************************************************
859 {
860 return _begin;
861 }
862
863 //*************************************************************************
865 //*************************************************************************
867 {
868 return iterator(_end);
869 }
870
871 //*************************************************************************
873 //*************************************************************************
875 {
876 return iterator(_end);
877 }
878
879 //*************************************************************************
881 //*************************************************************************
883 {
884 return const_iterator(_end);
885 }
886
887 //*************************************************************************
889 //*************************************************************************
890 reverse_iterator rbegin()
891 {
892 return reverse_iterator(end());
893 }
894
895 //*************************************************************************
897 //*************************************************************************
898 const_reverse_iterator rbegin() const
899 {
900 return const_reverse_iterator(end());
901 }
902
903 //*************************************************************************
905 //*************************************************************************
906 const_reverse_iterator crbegin() const
907 {
908 return const_reverse_iterator(cend());
909 }
910
911 //*************************************************************************
913 //*************************************************************************
914 reverse_iterator rend()
915 {
916 return reverse_iterator(begin());
917 }
918
919 //*************************************************************************
921 //*************************************************************************
922 const_reverse_iterator rend() const
923 {
924 return const_reverse_iterator(begin());
925 }
926
927 //*************************************************************************
929 //*************************************************************************
930 const_reverse_iterator crend() const
931 {
932 return const_reverse_iterator(cbegin());
933 }
934
935 //*************************************************************************
937 //*************************************************************************
938 void clear()
939 {
940 initialise();
941 }
942
943 //*************************************************************************
945 //*************************************************************************
946 void fill(const T& value)
947 {
948 etl::fill(begin(), end(), value);
949 }
950
951 //*************************************************************************
956 //*************************************************************************
957 iterator insert(const_iterator insert_position, const value_type& value)
958 {
959 iterator position(to_iterator(insert_position));
960
961 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
962
963 if (insert_position == begin())
964 {
965 create_element_front(value);
966 position = _begin;
967 }
968 else if (insert_position == end())
969 {
970 create_element_back(value);
971 position = _end - 1;
972 }
973 else
974 {
975 // Are we closer to the front?
976 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
977 {
978 // Construct the _begin.
979 create_element_front(*_begin);
980
981 // Move the values.
982 etl::move(_begin + 1, position, _begin);
983
984 // Write the new value.
985 *--position = value;
986 }
987 else
988 {
989 // Construct the _end.
990 create_element_back(*(_end - 1));
991
992 // Move the values.
993 etl::move_backward(position, _end - 2, _end - 1);
994
995 // Write the new value.
996 *position = value;
997 }
998 }
999
1000 return position;
1001 }
1002
1003#if ETL_USING_CPP11
1004 //*************************************************************************
1009 //*************************************************************************
1010 iterator insert(const_iterator insert_position, value_type&& value)
1011 {
1012 iterator position(insert_position.index, *this, p_buffer);
1013
1014 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1015
1016 if (insert_position == begin())
1017 {
1018 create_element_front(etl::move(value));
1019 position = _begin;
1020 }
1021 else if (insert_position == end())
1022 {
1023 create_element_back(etl::move(value));
1024 position = _end - 1;
1025 }
1026 else
1027 {
1028 // Are we closer to the front?
1029 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1030 {
1031 // Construct the _begin.
1032 create_element_front(etl::move(*_begin));
1033
1034 // Move the values.
1035 etl::move(_begin + 1, position, _begin);
1036
1037 // Write the new value.
1038 *--position = etl::move(value);
1039 }
1040 else
1041 {
1042 // Construct the _end.
1043 create_element_back(etl::move(*(_end - 1)));
1044
1045 // Move the values.
1046 etl::move_backward(position, _end - 2, _end - 1);
1047
1048 // Write the new value.
1049 *position = etl::move(value);
1050 }
1051 }
1052
1053 return position;
1054 }
1055#endif
1056
1057 //*************************************************************************
1061 //*************************************************************************
1062#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
1063 template <typename ... Args>
1064 iterator emplace(const_iterator insert_position, Args && ... args)
1065 {
1066 iterator position(insert_position.index, *this, p_buffer);
1067
1068 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1069
1070 void* p;
1071
1072 if (insert_position == begin())
1073 {
1074 --_begin;
1075 p = etl::addressof(*_begin);
1076 ++current_size;
1077 ETL_INCREMENT_DEBUG_COUNT
1078 position = _begin;
1079 }
1080 else if (insert_position == end())
1081 {
1082 p = etl::addressof(*_end);
1083 ++_end;
1084 ++current_size;
1085 ETL_INCREMENT_DEBUG_COUNT
1086 position = _end - 1;
1087 }
1088 else
1089 {
1090 // Are we closer to the front?
1091 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1092 {
1093 // Construct the _begin.
1094 create_element_front(*_begin);
1095
1096 // Move the values.
1097 etl::move(_begin + 1, position, _begin);
1098
1099 // Write the new value.
1100 --position;
1101 (*position).~T();
1102 p = etl::addressof(*position);
1103 }
1104 else
1105 {
1106 // Construct the _end.
1107 create_element_back(*(_end - 1));
1108
1109 // Move the values.
1110 etl::move_backward(position, _end - 2, _end - 1);
1111
1112 // Write the new value.
1113 (*position).~T();
1114 p = etl::addressof(*position);
1115 }
1116 }
1117
1118 ::new (p) T(etl::forward<Args>(args)...);
1119
1120 return position;
1121 }
1122
1123#else
1124
1125 //*************************************************************************
1129 //*************************************************************************
1130 template <typename T1>
1131 iterator emplace(const_iterator insert_position, const T1& value1)
1132 {
1133 iterator position(insert_position.index, *this, p_buffer);
1134
1135 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1136
1137 void* p;
1138
1139 if (insert_position == begin())
1140 {
1141 --_begin;
1142 p = etl::addressof(*_begin);
1143 ++current_size;
1144 ETL_INCREMENT_DEBUG_COUNT
1145 position = _begin;
1146 }
1147 else if (insert_position == end())
1148 {
1149 p = etl::addressof(*_end);
1150 ++_end;
1151 ++current_size;
1152 ETL_INCREMENT_DEBUG_COUNT
1153 position = _end - 1;
1154 }
1155 else
1156 {
1157 // Are we closer to the front?
1158 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1159 {
1160 // Construct the _begin.
1161 create_element_front(*_begin);
1162
1163 // Move the values.
1164 etl::move(_begin + 1, position, _begin);
1165
1166 // Write the new value.
1167 --position;
1168 (*position).~T();
1169 p = etl::addressof(*position);
1170 }
1171 else
1172 {
1173 // Construct the _end.
1174 create_element_back(*(_end - 1));
1175
1176 // Move the values.
1177 etl::move_backward(position, _end - 2, _end - 1);
1178
1179 // Write the new value.
1180 (*position).~T();
1181 p = etl::addressof(*position);
1182 }
1183 }
1184
1185 ::new (p) T(value1);
1186
1187 return position;
1188 }
1189
1190 //*************************************************************************
1194 //*************************************************************************
1195 template <typename T1, typename T2>
1196 iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2)
1197 {
1198 iterator position(insert_position.index, *this, p_buffer);
1199
1200 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1201
1202 void* p;
1203
1204 if (insert_position == begin())
1205 {
1206 --_begin;
1207 p = etl::addressof(*_begin);
1208 ++current_size;
1209 ETL_INCREMENT_DEBUG_COUNT
1210 position = _begin;
1211 }
1212 else if (insert_position == end())
1213 {
1214 p = etl::addressof(*_end);
1215 ++_end;
1216 ++current_size;
1217 ETL_INCREMENT_DEBUG_COUNT
1218 position = _end - 1;
1219 }
1220 else
1221 {
1222 // Are we closer to the front?
1223 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1224 {
1225 // Construct the _begin.
1226 create_element_front(*_begin);
1227
1228 // Move the values.
1229 etl::move(_begin + 1, position, _begin);
1230
1231 // Write the new value.
1232 --position;
1233 (*position).~T();
1234 p = etl::addressof(*position);
1235 }
1236 else
1237 {
1238 // Construct the _end.
1239 create_element_back(*(_end - 1));
1240
1241 // Move the values.
1242 etl::move_backward(position, _end - 2, _end - 1);
1243
1244 // Write the new value.
1245 (*position).~T();
1246 p = etl::addressof(*position);
1247 }
1248 }
1249
1250 ::new (p) T(value1, value2);
1251
1252 return position;
1253 }
1254
1255 //*************************************************************************
1259 //*************************************************************************
1260 template <typename T1, typename T2, typename T3>
1261 iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2, const T3& value3)
1262 {
1263 iterator position(insert_position.index, *this, p_buffer);
1264
1265 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1266
1267 void* p;
1268
1269 if (insert_position == begin())
1270 {
1271 --_begin;
1272 p = etl::addressof(*_begin);
1273 ++current_size;
1274 ETL_INCREMENT_DEBUG_COUNT
1275 position = _begin;
1276 }
1277 else if (insert_position == end())
1278 {
1279 p = etl::addressof(*_end);
1280 ++_end;
1281 ++current_size;
1282 ETL_INCREMENT_DEBUG_COUNT
1283 position = _end - 1;
1284 }
1285 else
1286 {
1287 // Are we closer to the front?
1288 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1289 {
1290 // Construct the _begin.
1291 create_element_front(*_begin);
1292
1293 // Move the values.
1294 etl::move(_begin + 1, position, _begin);
1295
1296 // Write the new value.
1297 --position;
1298 (*position).~T();
1299 p = etl::addressof(*position);
1300 }
1301 else
1302 {
1303 // Construct the _end.
1304 create_element_back(*(_end - 1));
1305
1306 // Move the values.
1307 etl::move_backward(position, _end - 2, _end - 1);
1308
1309 // Write the new value.
1310 (*position).~T();
1311 p = etl::addressof(*position);
1312 }
1313 }
1314
1315 ::new (p) T(value1, value2, value3);
1316
1317 return position;
1318 }
1319
1320 //*************************************************************************
1324 //*************************************************************************
1325 template <typename T1, typename T2, typename T3, typename T4>
1326 iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2, const T3& value3, const T4& value4)
1327 {
1328 iterator position(insert_position.index, *this, p_buffer);
1329
1330 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1331
1332 void* p;
1333
1334 if (insert_position == begin())
1335 {
1336 --_begin;
1337 p = etl::addressof(*_begin);
1338 ++current_size;
1339 ETL_INCREMENT_DEBUG_COUNT
1340 position = _begin;
1341 }
1342 else if (insert_position == end())
1343 {
1344 p = etl::addressof(*_end);
1345 ++_end;
1346 ++current_size;
1347 ETL_INCREMENT_DEBUG_COUNT
1348 position = _end - 1;
1349 }
1350 else
1351 {
1352 // Are we closer to the front?
1353 if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
1354 {
1355 // Construct the _begin.
1356 create_element_front(*_begin);
1357
1358 // Move the values.
1359 etl::move(_begin + 1, position, _begin);
1360
1361 // Write the new value.
1362 --position;
1363 (*position).~T();
1364 p = etl::addressof(*position);
1365 }
1366 else
1367 {
1368 // Construct the _end.
1369 create_element_back(*(_end - 1));
1370
1371 // Move the values.
1372 etl::move_backward(position, _end - 2, _end - 1);
1373
1374 // Write the new value.
1375 (*position).~T();
1376 p = etl::addressof(*position);
1377 }
1378 }
1379
1380 ::new (p) T(value1, value2, value3, value4);
1381
1382 return position;
1383 }
1384#endif
1385
1386 //*************************************************************************
1392 //*************************************************************************
1393 iterator insert(const_iterator insert_position, size_type n, const value_type& value)
1394 {
1395 iterator position;
1396
1397 ETL_ASSERT((current_size + n) <= CAPACITY, ETL_ERROR(deque_full));
1398
1399 if (insert_position == begin())
1400 {
1401 for (size_t i = 0UL; i < n; ++i)
1402 {
1403 create_element_front(value);
1404 }
1405
1406 position = _begin;
1407 }
1408 else if (insert_position == end())
1409 {
1410 for (size_t i = 0UL; i < n; ++i)
1411 {
1412 create_element_back(value);
1413 }
1414
1415 position = _end - n;
1416 }
1417 else
1418 {
1419 // Non-const insert iterator.
1420 position = iterator(insert_position.index, *this, p_buffer);
1421
1422 // Are we closer to the front?
1423 if (distance(_begin, insert_position) <= difference_type(current_size / 2))
1424 {
1425 size_t n_insert = n;
1426 size_t n_move = etl::distance(begin(), position);
1427 size_t n_create_copy = etl::min(n_insert, n_move);
1428 size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0;
1429 size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0;
1430 size_t n_copy_old = n_move - n_create_copy;
1431
1432 // Remember the original start.
1433 iterator from = _begin + n_create_copy - 1;
1434 iterator to;
1435
1436 // Create new.
1437 for (size_t i = 0UL; i < n_create_new; ++i)
1438 {
1439 create_element_front(value);
1440 }
1441
1442 // Create copy.
1443 for (size_t i = 0UL; i < n_create_copy; ++i)
1444 {
1445 create_element_front(*from);
1446 --from;
1447 }
1448
1449 // Move old.
1450 from = position - n_copy_old;
1451 to = _begin + n_create_copy;
1452 etl::move(from, from + n_copy_old, to);
1453
1454 // Copy new.
1455 to = position - n_create_copy;
1456 etl::fill_n(to, n_copy_new, value);
1457
1458 position = _begin + n_move;
1459 }
1460 else
1461 {
1462 size_t n_insert = n;
1463 size_t n_move = etl::distance(position, end());
1464 size_t n_create_copy = etl::min(n_insert, n_move);
1465 size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0;
1466 size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0;
1467 size_t n_copy_old = n_move - n_create_copy;
1468
1469 // Create new.
1470 for (size_t i = 0UL; i < n_create_new; ++i)
1471 {
1472 create_element_back(value);
1473 }
1474
1475 // Create copy.
1476 const_iterator from = position + n_copy_old;
1477
1478 for (size_t i = 0UL; i < n_create_copy; ++i)
1479 {
1480 create_element_back(*from);
1481 ++from;
1482 }
1483
1484 // Move old.
1485 etl::move_backward(position, position + n_copy_old, position + n_insert + n_copy_old);
1486
1487 // Copy new.
1488 etl::fill_n(position, n_copy_new, value);
1489 }
1490 }
1491
1492 return position;
1493 }
1494
1495 //*************************************************************************
1501 //*************************************************************************
1502 template<typename TIterator>
1504 insert(const_iterator insert_position, TIterator range_begin, TIterator range_end)
1505 {
1506 iterator position;
1507
1508 difference_type n = etl::distance(range_begin, range_end);
1509
1510 ETL_ASSERT((current_size + n) <= CAPACITY, ETL_ERROR(deque_full));
1511
1512 if (insert_position == begin())
1513 {
1514 create_element_front(n, range_begin);
1515
1516 position = _begin;
1517 }
1518 else if (insert_position == end())
1519 {
1520 for (difference_type i = 0; i < n; ++i)
1521 {
1522 create_element_back(*range_begin);
1523 ++range_begin;
1524 }
1525
1526 position = _end - n;
1527 }
1528 else
1529 {
1530 // Non-const insert iterator.
1531 position = iterator(insert_position.index, *this, p_buffer);
1532
1533 // Are we closer to the front?
1534 if (distance(_begin, insert_position) < difference_type(current_size / 2))
1535 {
1536 size_t n_insert = n;
1537 size_t n_move = etl::distance(begin(), position);
1538 size_t n_create_copy = etl::min(n_insert, n_move);
1539 size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0;
1540 size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0;
1541 size_t n_copy_old = n_move - n_create_copy;
1542
1543 // Remember the original start.
1544 iterator from;
1545 iterator to;
1546
1547 // Create new.
1548 create_element_front(n_create_new, range_begin);
1549
1550 // Create copy.
1551 create_element_front(n_create_copy, _begin + n_create_new);
1552
1553 // Move old.
1554 from = position - n_copy_old;
1555 to = _begin + n_create_copy;
1556 etl::move(from, from + n_copy_old, to);
1557
1558 // Copy new.
1559 to = position - n_create_copy;
1560 range_begin += n_create_new;
1561 etl::copy(range_begin, range_begin + n_copy_new, to);
1562
1563 position = _begin + n_move;
1564 }
1565 else
1566 {
1567 size_t n_insert = n;
1568 size_t n_move = etl::distance(position, end());
1569 size_t n_create_copy = etl::min(n_insert, n_move);
1570 size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0;
1571 size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0;
1572 size_t n_copy_old = n_move - n_create_copy;
1573
1574 // Create new.
1575 TIterator item = range_begin + (n - n_create_new);
1576 for (size_t i = 0UL; i < n_create_new; ++i)
1577 {
1578 create_element_back(*item);
1579 ++item;
1580 }
1581
1582 // Create copy.
1583 const_iterator from = position + n_copy_old;
1584
1585 for (size_t i = 0UL; i < n_create_copy; ++i)
1586 {
1587 create_element_back(*from);
1588 ++from;
1589 }
1590
1591 // Move old.
1592 etl::move_backward(position, position + n_copy_old, position + n_insert + n_copy_old);
1593
1594 // Copy new.
1595 item = range_begin;
1596 etl::copy(item, item + n_copy_new, position);
1597 }
1598 }
1599
1600 return position;
1601 }
1602
1603 //*************************************************************************
1607 //*************************************************************************
1609 {
1610 iterator position(to_iterator(erase_position));
1611 //iterator position(erase_position.index, *this, p_buffer);
1612
1613 ETL_ASSERT(distance(position) <= difference_type(current_size), ETL_ERROR(deque_out_of_bounds));
1614
1615 if (position == _begin)
1616 {
1617 destroy_element_front();
1618 position = begin();
1619 }
1620 else if (position == _end - 1)
1621 {
1622 destroy_element_back();
1623 position = end();
1624 }
1625 else
1626 {
1627 // Are we closer to the front?
1628 if (distance(_begin, position) < difference_type(current_size / 2))
1629 {
1630 etl::move_backward(_begin, position, position + 1);
1631 destroy_element_front();
1632 ++position;
1633 }
1634 else
1635 {
1636 etl::move(position + 1, _end, position);
1637 destroy_element_back();
1638 }
1639 }
1640
1641 return position;
1642 }
1643
1644 //*************************************************************************
1649 //*************************************************************************
1651 {
1652 iterator position(to_iterator(range_begin));
1653
1654 ETL_ASSERT((distance(range_begin) <= difference_type(current_size)) && (distance(range_end) <= difference_type(current_size)), ETL_ERROR(deque_out_of_bounds));
1655
1656 // How many to erase?
1657 size_t length = etl::distance(range_begin, range_end);
1658
1659 // At the beginning?
1660 if (position == _begin)
1661 {
1662 for (size_t i = 0UL; i < length; ++i)
1663 {
1664 destroy_element_front();
1665 }
1666
1667 position = begin();
1668 }
1669 // At the end?
1670 else if (position == _end - length)
1671 {
1672 for (size_t i = 0UL; i < length; ++i)
1673 {
1674 destroy_element_back();
1675 }
1676
1677 position = end();
1678 }
1679 else
1680 {
1681 // Copy the smallest number of items.
1682 // Are we closer to the front?
1683 if (distance(_begin, position) < difference_type(current_size / 2))
1684 {
1685 // Move the items.
1686 etl::move_backward(_begin, position, position + length);
1687
1688 for (size_t i = 0UL; i < length; ++i)
1689 {
1690 destroy_element_front();
1691 }
1692
1693 position += length;
1694 }
1695 else
1696 // Must be closer to the back.
1697 {
1698 // Move the items.
1699 etl::move(position + length, _end, position);
1700
1701 for (size_t i = 0UL; i < length; ++i)
1702 {
1703 destroy_element_back();
1704 }
1705 }
1706 }
1707
1708 return position;
1709 }
1710
1711 //*************************************************************************
1715 //*************************************************************************
1716 void push_back(const_reference item)
1717 {
1718#if defined(ETL_CHECK_PUSH_POP)
1719 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1720#endif
1721 create_element_back(item);
1722 }
1723
1724#if ETL_USING_CPP11
1725 //*************************************************************************
1729 //*************************************************************************
1730 void push_back(rvalue_reference item)
1731 {
1732#if defined(ETL_CHECK_PUSH_POP)
1733 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1734#endif
1735 create_element_back(etl::move(item));
1736 }
1737#endif
1738
1739#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
1740 //*************************************************************************
1743 //*************************************************************************
1744 template <typename ... Args>
1745 reference emplace_back(Args && ... args)
1746 {
1747#if defined(ETL_CHECK_PUSH_POP)
1748 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1749#endif
1750
1751 ::new (&(*_end)) T(etl::forward<Args>(args)...);
1752 ++_end;
1753 ++current_size;
1754 ETL_INCREMENT_DEBUG_COUNT
1755 return back();
1756 }
1757
1758#else
1759
1760 //*************************************************************************
1763 //*************************************************************************
1764 template <typename T1>
1765 reference emplace_back(const T1& value1)
1766 {
1767#if defined(ETL_CHECK_PUSH_POP)
1768 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1769#endif
1770
1771 ::new (&(*_end)) T(value1);
1772 ++_end;
1773 ++current_size;
1774 ETL_INCREMENT_DEBUG_COUNT
1775 return back();
1776 }
1777
1778 //*************************************************************************
1781 //*************************************************************************
1782 template <typename T1, typename T2>
1783 reference emplace_back(const T1& value1, const T2& value2)
1784 {
1785#if defined(ETL_CHECK_PUSH_POP)
1786 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1787#endif
1788
1789 ::new (&(*_end)) T(value1, value2);
1790 ++_end;
1791 ++current_size;
1792 ETL_INCREMENT_DEBUG_COUNT
1793 return back();
1794 }
1795
1796 //*************************************************************************
1799 //*************************************************************************
1800 template <typename T1, typename T2, typename T3>
1801 reference emplace_back(const T1& value1, const T2& value2, const T3& value3)
1802 {
1803#if defined(ETL_CHECK_PUSH_POP)
1804 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1805#endif
1806
1807 ::new (&(*_end)) T(value1, value2, value3);
1808 ++_end;
1809 ++current_size;
1810 ETL_INCREMENT_DEBUG_COUNT
1811 return back();
1812 }
1813
1814 //*************************************************************************
1817 //*************************************************************************
1818 template <typename T1, typename T2, typename T3, typename T4>
1819 reference emplace_back(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
1820 {
1821#if defined(ETL_CHECK_PUSH_POP)
1822 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1823#endif
1824
1825 ::new (&(*_end)) T(value1, value2, value3, value4);
1826 ++_end;
1827 ++current_size;
1828 ETL_INCREMENT_DEBUG_COUNT
1829 return back();
1830 }
1831#endif
1832
1833 //*************************************************************************
1835 //*************************************************************************
1837 {
1838#if defined(ETL_CHECK_PUSH_POP)
1839 ETL_ASSERT(!empty(), ETL_ERROR(deque_empty));
1840#endif
1841 destroy_element_back();
1842 }
1843
1844 //*************************************************************************
1848 //*************************************************************************
1849 void push_front(const_reference item)
1850 {
1851#if defined(ETL_CHECK_PUSH_POP)
1852 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1853#endif
1854 create_element_front(item);
1855 }
1856
1857#if ETL_USING_CPP11
1858 //*************************************************************************
1862 //*************************************************************************
1863 void push_front(rvalue_reference item)
1864 {
1865#if defined(ETL_CHECK_PUSH_POP)
1866 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1867#endif
1868 create_element_front(etl::move(item));
1869 }
1870#endif
1871
1872#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
1873 //*************************************************************************
1876 //*************************************************************************
1877 template <typename ... Args>
1878 reference emplace_front(Args && ... args)
1879 {
1880#if defined(ETL_CHECK_PUSH_POP)
1881 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1882#endif
1883
1884 --_begin;
1885 ::new (&(*_begin)) T(etl::forward<Args>(args)...);
1886 ++current_size;
1887 ETL_INCREMENT_DEBUG_COUNT
1888 return front();
1889 }
1890
1891#else
1892
1893 //*************************************************************************
1896 //*************************************************************************
1897 template <typename T1>
1898 reference emplace_front(const T1& value1)
1899 {
1900#if defined(ETL_CHECK_PUSH_POP)
1901 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1902#endif
1903
1904 --_begin;
1905 ::new (&(*_begin)) T(value1);
1906 ++current_size;
1907 ETL_INCREMENT_DEBUG_COUNT
1908 return front();
1909 }
1910
1911 //*************************************************************************
1914 //*************************************************************************
1915 template <typename T1, typename T2>
1916 reference emplace_front(const T1& value1, const T2& value2)
1917 {
1918#if defined(ETL_CHECK_PUSH_POP)
1919 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1920#endif
1921
1922 --_begin;
1923 ::new (&(*_begin)) T(value1, value2);
1924 ++current_size;
1925 ETL_INCREMENT_DEBUG_COUNT
1926 return front();
1927 }
1928
1929 //*************************************************************************
1932 //*************************************************************************
1933 template <typename T1, typename T2, typename T3>
1934 reference emplace_front(const T1& value1, const T2& value2, const T3& value3)
1935 {
1936#if defined(ETL_CHECK_PUSH_POP)
1937 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1938#endif
1939
1940 --_begin;
1941 ::new (&(*_begin)) T(value1, value2, value3);
1942 ++current_size;
1943 ETL_INCREMENT_DEBUG_COUNT
1944 return front();
1945 }
1946
1947 //*************************************************************************
1950 //*************************************************************************
1951 template <typename T1, typename T2, typename T3, typename T4>
1952 reference emplace_front(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
1953 {
1954#if defined(ETL_CHECK_PUSH_POP)
1955 ETL_ASSERT(!full(), ETL_ERROR(deque_full));
1956#endif
1957
1958 --_begin;
1959 ::new (&(*_begin)) T(value1, value2, value3, value4);
1960 ++current_size;
1961 ETL_INCREMENT_DEBUG_COUNT
1962 return front();
1963 }
1964#endif
1965
1966 //*************************************************************************
1968 //*************************************************************************
1970 {
1971#if defined(ETL_CHECK_PUSH_POP)
1972 ETL_ASSERT(!empty(), ETL_ERROR(deque_empty));
1973#endif
1974 destroy_element_front();
1975 }
1976
1977 //*************************************************************************
1982 //*************************************************************************
1983 void resize(size_t new_size, const value_type& value = value_type())
1984 {
1985 ETL_ASSERT(new_size <= CAPACITY, ETL_ERROR(deque_full));
1986
1987 // Make it smaller?
1988 if (new_size < current_size)
1989 {
1990 while (current_size > new_size)
1991 {
1992 destroy_element_back();
1993 }
1994 }
1995 // Make it larger?
1996 else if (new_size > current_size)
1997 {
1998 size_t count = new_size - current_size;
1999
2000 for (size_t i = 0UL; i < count; ++i)
2001 {
2002 create_element_back(value);
2003 }
2004 }
2005 }
2006
2007 //*************************************************************************
2009 //*************************************************************************
2010 friend difference_type operator -(const iterator& lhs, const iterator& rhs)
2011 {
2012 return distance(rhs, lhs);
2013 }
2014
2015 //*************************************************************************
2017 //*************************************************************************
2018 friend difference_type operator -(const const_iterator& lhs, const const_iterator& rhs)
2019 {
2020 return distance(rhs, lhs);
2021 }
2022
2023 //*************************************************************************
2025 //*************************************************************************
2026 friend difference_type operator -(const reverse_iterator& lhs, const reverse_iterator& rhs)
2027 {
2028 return distance(lhs.base(), rhs.base());
2029 }
2030
2031 //*************************************************************************
2033 //*************************************************************************
2034 friend difference_type operator -(const const_reverse_iterator& lhs, const const_reverse_iterator& rhs)
2035 {
2036 return distance(lhs.base(), rhs.base());
2037 }
2038
2039 //*************************************************************************
2041 //*************************************************************************
2043 {
2044 if (&rhs != this)
2045 {
2046 assign(rhs.begin(), rhs.end());
2047 }
2048
2049 return *this;
2050 }
2051
2052#if ETL_USING_CPP11
2053 //*************************************************************************
2055 //*************************************************************************
2056 ideque& operator =(ideque&& rhs)
2057 {
2058 if (&rhs != this)
2059 {
2060 clear();
2061 iterator itr = rhs.begin();
2062 while (itr != rhs.end())
2063 {
2064 push_back(etl::move(*itr));
2065 ++itr;
2066 }
2067
2068 rhs.initialise();
2069 }
2070
2071 return *this;
2072 }
2073#endif
2074
2075#ifdef ETL_IDEQUE_REPAIR_ENABLE
2076 //*************************************************************************
2078 //*************************************************************************
2079 virtual void repair() = 0;
2080#endif
2081
2082 protected:
2083
2084 //*************************************************************************
2086 //*************************************************************************
2087 ideque(pointer p_buffer_, size_t max_size_, size_t buffer_size_)
2088 : deque_base(max_size_, buffer_size_),
2089 p_buffer(p_buffer_)
2090 {
2091 }
2092
2093 //*********************************************************************
2095 //*********************************************************************
2097 {
2098 if ETL_IF_CONSTEXPR(etl::is_trivially_destructible<T>::value)
2099 {
2100 current_size = 0;
2101 ETL_RESET_DEBUG_COUNT
2102 }
2103 else
2104 {
2105 while (current_size > 0)
2106 {
2107 destroy_element_back();
2108 }
2109 }
2110
2111 _begin = iterator(0, *this, p_buffer);
2112 _end = iterator(0, *this, p_buffer);
2113 }
2114
2115 //*************************************************************************
2117 //*************************************************************************
2118 void repair_buffer(pointer p_buffer_)
2119 {
2120 p_buffer = p_buffer_;
2121
2122 _begin = iterator(_begin.index, *this, p_buffer);
2123 _end = iterator(_end.index, *this, p_buffer);
2124 }
2125
2126 iterator _begin;
2128 pointer p_buffer;
2129
2130 private:
2131
2132 //*********************************************************************
2134 //*********************************************************************
2135 void create_element_front()
2136 {
2137 --_begin;
2138 ::new (&(*_begin)) T();
2139 ++current_size;
2140 ETL_INCREMENT_DEBUG_COUNT
2141 }
2142
2143 //*********************************************************************
2145 //*********************************************************************
2146 template <typename TIterator>
2147 void create_element_front(size_t n, TIterator from)
2148 {
2149 if (n == 0)
2150 {
2151 return;
2152 }
2153
2154 _begin -= n;
2155
2156 iterator item = _begin;
2157
2158 do
2159 {
2160 ::new (&(*item)) T(*from);
2161 ++item;
2162 ++from;
2163 ++current_size;
2164 ETL_INCREMENT_DEBUG_COUNT
2165 } while (--n != 0);
2166 }
2167
2168 //*********************************************************************
2170 //*********************************************************************
2171 void create_element_back()
2172 {
2173 ::new (&(*_end)) T();
2174 ++_end;
2175 ++current_size;
2176 ETL_INCREMENT_DEBUG_COUNT
2177 }
2178
2179 //*********************************************************************
2181 //*********************************************************************
2182 void create_element_front(const_reference value)
2183 {
2184 --_begin;
2185 ::new (&(*_begin)) T(value);
2186 ++current_size;
2187 ETL_INCREMENT_DEBUG_COUNT
2188 }
2189
2190 //*********************************************************************
2192 //*********************************************************************
2193 void create_element_back(const_reference value)
2194 {
2195 ::new (&(*_end)) T(value);
2196 ++_end;
2197 ++current_size;
2198 ETL_INCREMENT_DEBUG_COUNT
2199 }
2200
2201#if ETL_USING_CPP11
2202 //*********************************************************************
2204 //*********************************************************************
2205 void create_element_front(rvalue_reference value)
2206 {
2207 --_begin;
2208 ::new (&(*_begin)) T(etl::move(value));
2209 ++current_size;
2210 ETL_INCREMENT_DEBUG_COUNT
2211 }
2212
2213 //*********************************************************************
2215 //*********************************************************************
2216 void create_element_back(rvalue_reference value)
2217 {
2218 ::new (&(*_end)) T(etl::move(value));
2219 ++_end;
2220 ++current_size;
2221 ETL_INCREMENT_DEBUG_COUNT
2222 }
2223#endif
2224
2225 //*********************************************************************
2227 //*********************************************************************
2228 void destroy_element_front()
2229 {
2230 (*_begin).~T();
2231 --current_size;
2232 ETL_DECREMENT_DEBUG_COUNT
2233 ++_begin;
2234 }
2235
2236 //*********************************************************************
2238 //*********************************************************************
2239 void destroy_element_back()
2240 {
2241 --_end;
2242 (*_end).~T();
2243 --current_size;
2244 ETL_DECREMENT_DEBUG_COUNT
2245 }
2246
2247 //*************************************************************************
2249 //*************************************************************************
2250 template <typename TIterator1, typename TIterator2>
2251 static difference_type distance(const TIterator1& range_begin, const TIterator2& range_end)
2252 {
2253 difference_type distance1 = distance(range_begin);
2254 difference_type distance2 = distance(range_end);
2255
2256 return distance2 - distance1;
2257 }
2258
2259 //*************************************************************************
2261 //*************************************************************************
2262 template <typename TIterator>
2263 static difference_type distance(const TIterator& other)
2264 {
2265 const difference_type index = other.get_index();
2266 const difference_type reference_index = other.container()._begin.index;
2267 const size_t buffer_size = other.container().BUFFER_SIZE;
2268
2269 if (index < reference_index)
2270 {
2271 return buffer_size + index - reference_index;
2272 }
2273 else
2274 {
2275 return index - reference_index;
2276 }
2277 }
2278
2279 //*************************************************************************
2281 //*************************************************************************
2282 iterator to_iterator(const_iterator itr) const
2283 {
2284 return iterator(itr.index, const_cast<ideque&>(*this), p_buffer);
2285 }
2286
2287 // Disable copy construction.
2288 ideque(const ideque&);
2289
2290 //*************************************************************************
2292 //*************************************************************************
2293#if defined(ETL_POLYMORPHIC_DEQUE) || defined(ETL_POLYMORPHIC_CONTAINERS) || defined(ETL_IDEQUE_REPAIR_ENABLE)
2294 public:
2295 virtual ~ideque()
2296 {
2297 }
2298#else
2299 protected:
2301 {
2302 }
2303#endif
2304 };
2305
2306 //***************************************************************************
2312 //***************************************************************************
2313 template <typename T, const size_t MAX_SIZE_>
2314 class deque : public etl::ideque<T>
2315 {
2316 public:
2317
2318 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
2319
2320 private:
2321
2322 static ETL_CONSTANT size_t BUFFER_SIZE = MAX_SIZE + 1;
2323
2324 public:
2325
2326 typedef T value_type;
2327 typedef T* pointer;
2328 typedef const T* const_pointer;
2329 typedef T& reference;
2330 typedef const T& const_reference;
2331 typedef size_t size_type;
2332 typedef typename etl::iterator_traits<pointer>::difference_type difference_type;
2333
2334 //*************************************************************************
2336 //*************************************************************************
2338 : etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2339 {
2340 this->initialise();
2341 }
2342
2343 //*************************************************************************
2345 //*************************************************************************
2347 {
2348 this->initialise();
2349 }
2350
2351 //*************************************************************************
2353 //*************************************************************************
2354 deque(const deque& other)
2355 : etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2356 {
2357 if (this != &other)
2358 {
2359 this->assign(other.begin(), other.end());
2360 }
2361 }
2362
2363#if ETL_USING_CPP11
2364 //*************************************************************************
2366 //*************************************************************************
2367 deque(deque&& other)
2368 : etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2369 {
2370 if (this != &other)
2371 {
2372 this->initialise();
2373
2374 typename etl::ideque<T>::iterator itr = other.begin();
2375 while (itr != other.end())
2376 {
2377 this->push_back(etl::move(*itr));
2378 ++itr;
2379 }
2380 }
2381 }
2382#endif
2383
2384 //*************************************************************************
2386 //*************************************************************************
2387 template <typename TIterator>
2388 deque(TIterator begin_, TIterator end_, typename etl::enable_if<!etl::is_integral<TIterator>::value, int>::type = 0)
2389 : etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2390 {
2391 this->assign(begin_, end_);
2392 }
2393
2394 //*************************************************************************
2396 //*************************************************************************
2397 explicit deque(size_t n, const_reference value = value_type())
2398 : etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2399 {
2400 this->assign(n, value);
2401 }
2402
2403#if ETL_HAS_INITIALIZER_LIST
2404 //*************************************************************************
2406 //*************************************************************************
2407 deque(std::initializer_list<T> init)
2408 : ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, BUFFER_SIZE)
2409 {
2410 this->assign(init.begin(), init.end());
2411 }
2412#endif
2413
2414 //*************************************************************************
2416 //*************************************************************************
2418 {
2419 if (&rhs != this)
2420 {
2421 this->assign(rhs.begin(), rhs.end());
2422 }
2423
2424 return *this;
2425 }
2426
2427#if ETL_USING_CPP11
2428 //*************************************************************************
2430 //*************************************************************************
2431 deque& operator =(deque&& rhs)
2432 {
2433 if (&rhs != this)
2434 {
2435 this->clear();
2436 typename etl::ideque<T>::iterator itr = rhs.begin();
2437 while (itr != rhs.end())
2438 {
2439 this->push_back(etl::move(*itr));
2440 ++itr;
2441 }
2442 }
2443
2444 return *this;
2445 }
2446#endif
2447
2448 //*************************************************************************
2450 //*************************************************************************
2451#ifdef ETL_IDEQUE_REPAIR_ENABLE
2452 virtual
2453#endif
2454 void repair()
2455#ifdef ETL_IDEQUE_REPAIR_ENABLE
2456 ETL_OVERRIDE
2457#endif
2458 {
2459#if ETL_CPP11_TYPE_TRAITS_IS_TRIVIAL_SUPPORTED
2461#endif
2462
2463 etl::ideque<T>::repair_buffer(reinterpret_cast<T*>(buffer.raw));
2464 }
2465
2466 private:
2467
2470 };
2471
2472 template <typename T, const size_t MAX_SIZE_>
2473 ETL_CONSTANT size_t deque<T, MAX_SIZE_>::MAX_SIZE;
2474
2475 //*************************************************************************
2477 //*************************************************************************
2478#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2479 template <typename... T>
2480 deque(T...) -> deque<typename etl::common_type_t<T...>, sizeof...(T)>;
2481#endif
2482
2483 //*************************************************************************
2485 //*************************************************************************
2486#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2487 template <typename T, typename... TValues>
2488 constexpr auto make_deque(TValues&&... values) -> etl::deque<T, sizeof...(TValues)>
2489 {
2490 return { { etl::forward<T>(values)... } };
2491 }
2492#endif
2493
2494 //***************************************************************************
2500 //***************************************************************************
2501 template <typename T>
2502 bool operator ==(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
2503 {
2504 return (lhs.size() == rhs.size()) && etl::equal(lhs.begin(), lhs.end(), rhs.begin());
2505 }
2506
2507 //***************************************************************************
2513 //***************************************************************************
2514 template <typename T>
2515 bool operator !=(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
2516 {
2517 return !(lhs == rhs);
2518 }
2519
2520 //***************************************************************************
2526 //***************************************************************************
2527 template <typename T>
2528 bool operator <(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
2529 {
2530 return etl::lexicographical_compare(lhs.begin(),
2531 lhs.end(),
2532 rhs.begin(),
2533 rhs.end());
2534 }
2535
2536 //***************************************************************************
2542 //***************************************************************************
2543 template <typename T>
2544 bool operator <=(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
2545 {
2546 return !(lhs > rhs);
2547 }
2548
2549 //***************************************************************************
2555 //***************************************************************************
2556 template <typename T>
2557 bool operator >(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
2558 {
2559 return (rhs < lhs);
2560 }
2561
2562 //***************************************************************************
2568 //***************************************************************************
2569 template <typename T>
2570 bool operator >=(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
2571 {
2572 return !(lhs < rhs);
2573 }
2574}
2575
2576#include "private/minmax_pop.h"
2577
2578#endif
Const Iterator.
Definition: deque.h:473
Iterator.
Definition: deque.h:245
reference emplace_front(const T1 &value1)
Definition: deque.h:1898
reference emplace_back(const T1 &value1, const T2 &value2, const T3 &value3)
Definition: deque.h:1801
const_reverse_iterator crbegin() const
Gets a const reverse iterator to the end of the deque.
Definition: deque.h:906
void clear()
Clears the deque.
Definition: deque.h:938
iterator erase(const_iterator erase_position)
Definition: deque.h:1608
const size_type CAPACITY
The maximum number of elements in the deque.
Definition: deque.h:215
void pop_back()
Removes the oldest item from the deque.
Definition: deque.h:1836
ideque & operator=(const ideque &rhs)
Assignment operator.
Definition: deque.h:2042
const size_type BUFFER_SIZE
The number of elements in the buffer.
Definition: deque.h:216
const_reverse_iterator rbegin() const
Gets a const reverse iterator to the end of the deque.
Definition: deque.h:898
void resize(size_t new_size, const value_type &value=value_type())
Definition: deque.h:1983
iterator emplace(const_iterator insert_position, const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition: deque.h:1326
iterator begin()
Gets an iterator to the beginning of the deque.
Definition: deque.h:842
reference front()
Definition: deque.h:807
reference at(size_t index)
Definition: deque.h:754
reference emplace_back(const T1 &value1, const T2 &value2)
Definition: deque.h:1783
pointer p_buffer
Iterator to the _end item in the deque.
Definition: deque.h:2128
friend difference_type operator-(const iterator &lhs, const iterator &rhs)
Definition: deque.h:2010
reference emplace_front(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition: deque.h:1952
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:719
void initialise()
Initialise the deque.
Definition: deque.h:2096
reference operator[](size_t index)
Definition: deque.h:783
~deque_base()
Destructor.
Definition: deque.h:210
iterator _end
Iterator to the _begin item in the deque.
Definition: deque.h:2127
reference emplace_front(const T1 &value1, const T2 &value2, const T3 &value3)
Definition: deque.h:1934
size_type size() const
Definition: deque.h:145
const_reference at(size_t index) const
Definition: deque.h:769
const_reverse_iterator crend() const
Gets a const reverse iterator to the beginning of the deque.
Definition: deque.h:930
iterator end()
Gets an iterator to the end of the deque.
Definition: deque.h:866
const_iterator end() const
Gets a const iterator to the end of the deque.
Definition: deque.h:874
void push_front(const_reference item)
Definition: deque.h:1849
size_type max_size() const
Definition: deque.h:172
~ideque()
Destructor.
Definition: deque.h:2300
iterator erase(const_iterator range_begin, const_iterator range_end)
Definition: deque.h:1650
iterator emplace(const_iterator insert_position, const T1 &value1)
Definition: deque.h:1131
deque(const deque &other)
Copy constructor.
Definition: deque.h:2354
iterator emplace(const_iterator insert_position, const T1 &value1, const T2 &value2)
Definition: deque.h:1196
iterator insert(const_iterator insert_position, size_type n, const value_type &value)
Definition: deque.h:1393
enable_if<!etl::is_integral< TIterator >::value, iterator >::type insert(const_iterator insert_position, TIterator range_begin, TIterator range_end)
Definition: deque.h:1504
bool full() const
Definition: deque.h:163
size_type capacity() const
Definition: deque.h:181
const_reference back() const
Definition: deque.h:834
bool empty() const
Definition: deque.h:154
void repair()
Fix the internal pointers after a low level memory copy.
Definition: deque.h:2454
const_reverse_iterator rend() const
Gets a const reverse iterator to the beginning of the deque.
Definition: deque.h:922
const_iterator cend() const
Gets a const iterator to the end of the deque.
Definition: deque.h:882
reference emplace_back(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition: deque.h:1819
deque_base(size_t max_size_, size_t buffer_size_)
Constructor.
Definition: deque.h:200
reference emplace_front(const T1 &value1, const T2 &value2)
Definition: deque.h:1916
void assign(size_type n, const value_type &value)
Definition: deque.h:736
deque()
Default constructor.
Definition: deque.h:2337
reference back()
Definition: deque.h:825
iterator emplace(const_iterator insert_position, const T1 &value1, const T2 &value2, const T3 &value3)
Definition: deque.h:1261
reverse_iterator rbegin()
Gets a reverse iterator to the end of the deque.
Definition: deque.h:890
void fill(const T &value)
Fills the deque.
Definition: deque.h:946
void pop_front()
Removes the oldest item from the deque.
Definition: deque.h:1969
reference emplace_back(const T1 &value1)
Definition: deque.h:1765
void push_back(const_reference item)
Definition: deque.h:1716
const_iterator cbegin() const
Gets a const iterator to the beginning of the deque.
Definition: deque.h:858
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:2388
~deque()
Destructor.
Definition: deque.h:2346
reverse_iterator rend()
Gets a reverse iterator to the beginning of the deque.
Definition: deque.h:914
const_reference front() const
Definition: deque.h:816
deque(size_t n, const_reference value=value_type())
Assigns data to the deque.
Definition: deque.h:2397
size_t available() const
Definition: deque.h:190
deque & operator=(const deque &rhs)
Assignment operator.
Definition: deque.h:2417
const_iterator begin() const
Gets a const iterator to the beginning of the deque.
Definition: deque.h:850
iterator insert(const_iterator insert_position, const value_type &value)
Definition: deque.h:957
void repair_buffer(pointer p_buffer_)
Fix the internal pointers after a low level memory copy.
Definition: deque.h:2118
size_type current_size
The current number of elements in the deque.
Definition: deque.h:214
ideque(pointer p_buffer_, size_t max_size_, size_t buffer_size_)
Constructor.
Definition: deque.h:2087
Definition: deque.h:2315
Definition: deque.h:136
Definition: deque.h:94
Definition: deque.h:66
Definition: deque.h:80
Definition: deque.h:108
Definition: deque.h:227
bool operator>=(const etl::ideque< T > &lhs, const etl::ideque< T > &rhs)
Definition: deque.h:2570
bool operator==(const etl::ideque< T > &lhs, const etl::ideque< T > &rhs)
Template deduction guides.
Definition: deque.h:2502
bool operator<(const etl::ideque< T > &lhs, const etl::ideque< T > &rhs)
Definition: deque.h:2528
bool operator<=(const etl::ideque< T > &lhs, const etl::ideque< T > &rhs)
Definition: deque.h:2544
bool operator>(const etl::ideque< T > &lhs, const etl::ideque< T > &rhs)
Definition: deque.h:2557
bool operator!=(const etl::ideque< T > &lhs, const etl::ideque< T > &rhs)
Definition: deque.h:2515
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
ETL_CONSTEXPR exception(string_type reason_, string_type, numeric_type line_)
Constructor.
Definition: exception.h:69
Definition: exception.h:47
ETL_CONSTEXPR17 T * addressof(T &t)
Definition: addressof.h:51
enable_if
Definition: type_traits_generator.h:1191
is_integral
Definition: type_traits_generator.h:1001
Definition: deque.h:122
bitset_ext
Definition: absolute.h:38
ETL_CONSTEXPR14 etl::circular_iterator< TIterator > operator-(etl::circular_iterator< TIterator > &lhs, typename etl::iterator_traits< TIterator >::difference_type offset)
Definition: circular_iterator.h:672
bool operator>(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:684
bool operator>=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:696
bool operator!=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:645
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition: array.h:621
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:633
ETL_CONSTEXPR14 etl::circular_iterator< TIterator > operator+(etl::circular_iterator< TIterator > &lhs, typename etl::iterator_traits< TIterator >::difference_type offset)
Definition: circular_iterator.h:659
bool operator<(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:657
bool operator<=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:672
Definition: type_traits_generator.h:2069
Definition: type_traits_generator.h:2055
iterator
Definition: iterator.h:399