31#ifndef ETL_DEQUE_INCLUDED
32#define ETL_DEQUE_INCLUDED
138 typedef size_t size_type;
224 template <
typename T>
238 typedef typename etl::iterator_traits<pointer>::difference_type difference_type;
261 , p_deque(
other.p_deque)
262 , p_buffer(
other.p_buffer)
270 p_deque =
other.p_deque;
271 p_buffer =
other.p_buffer;
279 index = (
static_cast<size_t>(index) == p_deque->
BUFFER_SIZE - 1) ? 0 : index + 1;
288 index = (
static_cast<size_t>(index) == p_deque->
BUFFER_SIZE - 1) ? 0 : index + 1;
315 index = (index < 0) ? index + p_deque->
BUFFER_SIZE : index;
328 index = (index == 0) ? p_deque->
BUFFER_SIZE - 1 : index - 1;
337 index = (index == 0) ? p_deque->
BUFFER_SIZE - 1 : index - 1;
345 return p_buffer[index];
351 return &p_buffer[index];
399 return lhs.index ==
rhs.index;
414 const size_t buffer_size =
lhs.container().max_size() + 1;
441 difference_type get_index()
const
461 using ETL_OR_STD::swap;
463 swap(index,
other.index);
469 difference_type distance(difference_type
firstIndex, difference_type
index_)
const
489 difference_type index;
514 , p_deque(
other.p_deque)
515 , p_buffer(
other.p_buffer)
522 , p_deque(
other.p_deque)
523 , p_buffer(
other.p_buffer)
531 p_deque =
other.p_deque;
532 p_buffer =
other.p_buffer;
540 p_deque =
other.p_deque;
541 p_buffer =
other.p_buffer;
549 index = (
static_cast<size_t>(index) == p_deque->
BUFFER_SIZE - 1) ? 0 : index + 1;
558 index = (
static_cast<size_t>(index) == p_deque->
BUFFER_SIZE - 1) ? 0 : index + 1;
598 index = (index == 0) ? p_deque->
BUFFER_SIZE - 1 : index - 1;
607 index = (index == 0) ? p_deque->
BUFFER_SIZE - 1 : index - 1;
615 return p_buffer[index];
621 return &p_buffer[index];
660 return lhs.index ==
rhs.index;
675 const size_t buffer_size =
lhs.container().max_size() + 1UL;
702 difference_type get_index()
const
722 ETL_OR_STD::swap(index,
other.index);
728 difference_type distance(difference_type
firstIndex, difference_type
index_)
const
748 difference_type index;
753 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
754 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
759 template<
typename TIterator>
786 create_element_back(value);
934 return reverse_iterator(
end());
942 return const_reverse_iterator(
end());
950 return const_reverse_iterator(
cend());
958 return reverse_iterator(
begin());
964 const_reverse_iterator
rend()
const
966 return const_reverse_iterator(
begin());
972 const_reverse_iterator
crend()
const
974 return const_reverse_iterator(
cbegin());
1007 create_element_front(value);
1012 create_element_back(value);
1013 position =
_end - 1;
1018 if (etl::distance(_begin, position) < etl::distance(position,
_end - 1))
1021 create_element_front(*_begin);
1024 etl::move(_begin + 1, position, _begin);
1027 *--position = value;
1032 create_element_back(*(
_end - 1));
1035 etl::move_backward(position,
_end - 2,
_end - 1);
1060 create_element_front(etl::move(value));
1063 else if (insert_position ==
end())
1065 create_element_back(etl::move(value));
1066 position =
_end - 1;
1071 if (etl::distance(_begin, position) < etl::distance(position,
_end - 1))
1074 create_element_front(etl::move(*_begin));
1077 etl::move(_begin + 1, position, _begin);
1080 *--position = etl::move(value);
1085 create_element_back(etl::move(*(
_end - 1)));
1088 etl::move_backward(position,
_end - 2,
_end - 1);
1091 *position = etl::move(value);
1104#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
1105 template <
typename ... Args>
1106 iterator
emplace(const_iterator insert_position, Args && ... args)
1108 iterator position(insert_position.index, *
this,
p_buffer);
1114 if (insert_position ==
begin())
1119 ETL_INCREMENT_DEBUG_COUNT;
1122 else if (insert_position ==
end())
1127 ETL_INCREMENT_DEBUG_COUNT;
1128 position =
_end - 1;
1133 if (etl::distance(_begin, position) < etl::distance(position,
_end - 1))
1136 create_element_front(*_begin);
1139 etl::move(_begin + 1, position, _begin);
1149 create_element_back(*(
_end - 1));
1152 etl::move_backward(position,
_end - 2,
_end - 1);
1172 template <
typename T1>
1186 ETL_INCREMENT_DEBUG_COUNT;
1194 ETL_INCREMENT_DEBUG_COUNT;
1195 position =
_end - 1;
1200 if (etl::distance(_begin, position) < etl::distance(position,
_end - 1))
1203 create_element_front(*_begin);
1206 etl::move(_begin + 1, position, _begin);
1216 create_element_back(*(
_end - 1));
1219 etl::move_backward(position,
_end - 2,
_end - 1);
1227 ::new (p)
T(value1);
1237 template <
typename T1,
typename T2>
1251 ETL_INCREMENT_DEBUG_COUNT;
1259 ETL_INCREMENT_DEBUG_COUNT;
1260 position =
_end - 1;
1265 if (etl::distance(_begin, position) < etl::distance(position,
_end - 1))
1268 create_element_front(*_begin);
1271 etl::move(_begin + 1, position, _begin);
1281 create_element_back(*(
_end - 1));
1284 etl::move_backward(position,
_end - 2,
_end - 1);
1292 ::new (p)
T(value1, value2);
1302 template <
typename T1,
typename T2,
typename T3>
1316 ETL_INCREMENT_DEBUG_COUNT;
1324 ETL_INCREMENT_DEBUG_COUNT;
1325 position =
_end - 1;
1330 if (etl::distance(_begin, position) < etl::distance(position,
_end - 1))
1333 create_element_front(*_begin);
1336 etl::move(_begin + 1, position, _begin);
1346 create_element_back(*(
_end - 1));
1349 etl::move_backward(position,
_end - 2,
_end - 1);
1357 ::new (p)
T(value1, value2, value3);
1367 template <
typename T1,
typename T2,
typename T3,
typename T4>
1381 ETL_INCREMENT_DEBUG_COUNT;
1389 ETL_INCREMENT_DEBUG_COUNT;
1390 position =
_end - 1;
1395 if (etl::distance(_begin, position) < etl::distance(position,
_end - 1))
1398 create_element_front(*_begin);
1401 etl::move(_begin + 1, position, _begin);
1411 create_element_back(*(
_end - 1));
1414 etl::move_backward(position,
_end - 2,
_end - 1);
1422 ::new (p)
T(value1, value2, value3, value4);
1443 for (
size_t i = 0
UL;
i <
n; ++
i)
1445 create_element_front(value);
1452 for (
size_t i = 0
UL;
i <
n; ++
i)
1454 create_element_back(value);
1457 position =
_end -
n;
1481 create_element_front(value);
1487 create_element_front(*
from);
1500 position = _begin +
n_move;
1505 size_t n_move = etl::distance(position,
end());
1514 create_element_back(value);
1522 create_element_back(*
from);
1544 template<
typename TIterator>
1562 for (difference_type
i = 0;
i <
n; ++
i)
1568 position =
_end -
n;
1605 position = _begin +
n_move;
1610 size_t n_move = etl::distance(position,
end());
1620 create_element_back(*
item);
1629 create_element_back(*
from);
1657 if (position == _begin)
1659 destroy_element_front();
1662 else if (position ==
_end - 1)
1664 destroy_element_back();
1670 if (distance(_begin, position) < difference_type(
current_size / 2))
1672 etl::move_backward(_begin, position, position + 1);
1673 destroy_element_front();
1678 etl::move(position + 1,
_end, position);
1679 destroy_element_back();
1702 if (position == _begin)
1704 for (
size_t i = 0
UL;
i < length; ++
i)
1706 destroy_element_front();
1712 else if (position ==
_end - length)
1714 for (
size_t i = 0
UL;
i < length; ++
i)
1716 destroy_element_back();
1725 if (distance(_begin, position) < difference_type(
current_size / 2))
1728 etl::move_backward(_begin, position, position + length);
1730 for (
size_t i = 0
UL;
i < length; ++
i)
1732 destroy_element_front();
1741 etl::move(position + length,
_end, position);
1743 for (
size_t i = 0
UL;
i < length; ++
i)
1745 destroy_element_back();
1760#if defined(ETL_CHECK_PUSH_POP)
1763 create_element_back(
item);
1774#if defined(ETL_CHECK_PUSH_POP)
1777 create_element_back(etl::move(
item));
1781#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
1786 template <
typename ... Args>
1789#if defined(ETL_CHECK_PUSH_POP)
1796 ETL_INCREMENT_DEBUG_COUNT;
1808#if defined(ETL_CHECK_PUSH_POP)
1812 ::new (&(*
_end))
T();
1815 ETL_INCREMENT_DEBUG_COUNT;
1823 template <
typename T1>
1826#if defined(ETL_CHECK_PUSH_POP)
1830 ::new (&(*
_end))
T(value1);
1833 ETL_INCREMENT_DEBUG_COUNT;
1841 template <
typename T1,
typename T2>
1844#if defined(ETL_CHECK_PUSH_POP)
1848 ::new (&(*
_end))
T(value1, value2);
1851 ETL_INCREMENT_DEBUG_COUNT;
1859 template <
typename T1,
typename T2,
typename T3>
1862#if defined(ETL_CHECK_PUSH_POP)
1866 ::new (&(*
_end))
T(value1, value2, value3);
1869 ETL_INCREMENT_DEBUG_COUNT;
1877 template <
typename T1,
typename T2,
typename T3,
typename T4>
1880#if defined(ETL_CHECK_PUSH_POP)
1884 ::new (&(*
_end))
T(value1, value2, value3, value4);
1887 ETL_INCREMENT_DEBUG_COUNT;
1897#if defined(ETL_CHECK_PUSH_POP)
1900 destroy_element_back();
1910#if defined(ETL_CHECK_PUSH_POP)
1913 create_element_front(
item);
1924#if defined(ETL_CHECK_PUSH_POP)
1927 create_element_front(etl::move(
item));
1931#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
1936 template <
typename ... Args>
1939#if defined(ETL_CHECK_PUSH_POP)
1946 ETL_INCREMENT_DEBUG_COUNT;
1958#if defined(ETL_CHECK_PUSH_POP)
1963 ::new (&(*_begin))
T();
1965 ETL_INCREMENT_DEBUG_COUNT;
1973 template <
typename T1>
1976#if defined(ETL_CHECK_PUSH_POP)
1981 ::new (&(*_begin))
T(value1);
1983 ETL_INCREMENT_DEBUG_COUNT;
1991 template <
typename T1,
typename T2>
1994#if defined(ETL_CHECK_PUSH_POP)
1999 ::new (&(*_begin))
T(value1, value2);
2001 ETL_INCREMENT_DEBUG_COUNT;
2009 template <
typename T1,
typename T2,
typename T3>
2012#if defined(ETL_CHECK_PUSH_POP)
2017 ::new (&(*_begin))
T(value1, value2, value3);
2019 ETL_INCREMENT_DEBUG_COUNT;
2027 template <
typename T1,
typename T2,
typename T3,
typename T4>
2030#if defined(ETL_CHECK_PUSH_POP)
2035 ::new (&(*_begin))
T(value1, value2, value3, value4);
2037 ETL_INCREMENT_DEBUG_COUNT;
2047#if defined(ETL_CHECK_PUSH_POP)
2050 destroy_element_front();
2068 destroy_element_back();
2076 for (
size_t i = 0
UL;
i < count; ++
i)
2078 create_element_back(value);
2088 return distance(
rhs,
lhs);
2096 return distance(
rhs,
lhs);
2122 while (itr !=
rhs.end())
2135#ifdef ETL_IDEQUE_REPAIR_ENABLE
2139 virtual void repair() = 0;
2161 ETL_RESET_DEBUG_COUNT;
2167 destroy_element_back();
2195 void create_element_front()
2198 ::new (&(*_begin))
T();
2200 ETL_INCREMENT_DEBUG_COUNT;
2206 template <
typename TIterator>
2216 iterator item = _begin;
2220 ::new (&(*item)) T(*from);
2224 ETL_INCREMENT_DEBUG_COUNT;
2231 void create_element_back()
2233 ::new (&(*
_end)) T();
2236 ETL_INCREMENT_DEBUG_COUNT;
2242 void create_element_front(const_reference value)
2245 ::new (&(*_begin)) T(value);
2247 ETL_INCREMENT_DEBUG_COUNT;
2253 void create_element_back(const_reference value)
2255 ::new (&(*
_end)) T(value);
2258 ETL_INCREMENT_DEBUG_COUNT;
2265 void create_element_front(rvalue_reference value)
2268 ::new (&(*_begin)) T(etl::move(value));
2270 ETL_INCREMENT_DEBUG_COUNT;
2276 void create_element_back(rvalue_reference value)
2278 ::new (&(*
_end)) T(etl::move(value));
2281 ETL_INCREMENT_DEBUG_COUNT;
2288 void destroy_element_front()
2292 ETL_DECREMENT_DEBUG_COUNT;
2299 void destroy_element_back()
2304 ETL_DECREMENT_DEBUG_COUNT;
2310 template <
typename TIterator1,
typename TIterator2>
2311 static difference_type distance(
const TIterator1& range_begin,
const TIterator2& range_end)
2313 difference_type distance1 = distance(range_begin);
2314 difference_type distance2 = distance(range_end);
2316 return distance2 - distance1;
2322 template <
typename TIterator>
2323 static difference_type distance(
const TIterator& other)
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;
2329 if (index < reference_index)
2331 return buffer_size + index - reference_index;
2335 return index - reference_index;
2342 iterator to_iterator(const_iterator itr)
const
2344 return iterator(itr.index,
const_cast<ideque&
>(*
this),
p_buffer);
2353#if defined(ETL_POLYMORPHIC_DEQUE) || defined(ETL_POLYMORPHIC_CONTAINERS) || defined(ETL_IDEQUE_REPAIR_ENABLE)
2373 template <
typename T, const
size_t MAX_SIZE_>
2378 static ETL_CONSTANT
size_t MAX_SIZE =
MAX_SIZE_;
2382 static ETL_CONSTANT
size_t BUFFER_SIZE = MAX_SIZE + 1;
2392 typedef typename etl::iterator_traits<pointer>::difference_type difference_type;
2435 while (itr !=
other.end())
2447 template <
typename TIterator>
2463#if ETL_HAS_INITIALIZER_LIST
2497 while (itr !=
rhs.end())
2511#ifdef ETL_IDEQUE_REPAIR_ENABLE
2512 virtual void repair() ETL_OVERRIDE
2517#if ETL_CPP11_TYPE_TRAITS_IS_TRIVIAL_SUPPORTED
2530 template <
typename T, const
size_t MAX_SIZE_>
2531 ETL_CONSTANT
size_t deque<T, MAX_SIZE_>::MAX_SIZE;
2536#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2537 template <
typename... T>
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)>
2559 template <
typename T>
2562 return (
lhs.size() ==
rhs.size()) && etl::equal(
lhs.begin(),
lhs.end(),
rhs.begin());
2572 template <
typename T>
2585 template <
typename T>
2588 return etl::lexicographical_compare(
lhs.begin(),
2601 template <
typename T>
2614 template <
typename T>
2627 template <
typename T>
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
#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
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