Loading...
Searching...
No Matches
deque.h
Go to the documentation of this file.
/******************************************************************************
The MIT License(MIT)
Embedded Template Library.
https://github.com/ETLCPP/etl
https://www.etlcpp.com
Copyright(c) 2014 John Wellbelove
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files(the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions :
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
******************************************************************************/
#ifndef ETL_DEQUE_INCLUDED
#define ETL_DEQUE_INCLUDED
#include "platform.h"
#include "algorithm.h"
#include "debug_count.h"
#include "error_handler.h"
#include "exception.h"
#include "initializer_list.h"
#include "iterator.h"
#include "memory.h"
#include "placement_new.h"
#include "type_traits.h"
#include "utility.h"
#include <stddef.h>
#include "private/minmax_push.h"
//*****************************************************************************
//*****************************************************************************
namespace etl
{
//***************************************************************************
//***************************************************************************
class deque_exception : public etl::exception
{
public:
deque_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
: exception(reason_, file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class deque_full : public etl::deque_exception
{
public:
deque_full(string_type file_name_, numeric_type line_number_)
: etl::deque_exception(ETL_ERROR_TEXT("deque:full", ETL_DEQUE_FILE_ID"A"), file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class deque_empty : public etl::deque_exception
{
public:
deque_empty(string_type file_name_, numeric_type line_number_)
: etl::deque_exception(ETL_ERROR_TEXT("deque:empty", ETL_DEQUE_FILE_ID"B"), file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class deque_out_of_bounds : public etl::deque_exception
{
public:
deque_out_of_bounds(string_type file_name_, numeric_type line_number_)
: etl::deque_exception(ETL_ERROR_TEXT("deque:bounds", ETL_DEQUE_FILE_ID"C"), file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class deque_incompatible_type : public deque_exception
{
public:
deque_incompatible_type(string_type file_name_, numeric_type line_number_)
: deque_exception(ETL_ERROR_TEXT("deque:type", ETL_DEQUE_FILE_ID"D"), file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class deque_base
{
public:
typedef size_t size_type;
//*************************************************************************
//*************************************************************************
size_type size() const
{
return current_size;
}
//*************************************************************************
//*************************************************************************
bool empty() const
{
return (current_size == 0);
}
//*************************************************************************
//*************************************************************************
bool full() const
{
return current_size == CAPACITY;
}
//*************************************************************************
//*************************************************************************
size_type max_size() const
{
return CAPACITY;
}
//*************************************************************************
//*************************************************************************
size_type capacity() const
{
return CAPACITY;
}
//*************************************************************************
//*************************************************************************
size_t available() const
{
return max_size() - size();
}
protected:
//*************************************************************************
//*************************************************************************
deque_base(size_t max_size_, size_t buffer_size_)
: current_size(0)
, CAPACITY(max_size_)
, Buffer_Size(buffer_size_)
{
}
//*************************************************************************
//*************************************************************************
~deque_base() {}
size_type current_size;
const size_type CAPACITY;
const size_type Buffer_Size;
ETL_DECLARE_DEBUG_COUNT;
};
//***************************************************************************
//***************************************************************************
template <typename T>
class ideque : public etl::deque_base
{
public:
typedef T value_type;
typedef size_t size_type;
typedef T& reference;
typedef const T& const_reference;
#if ETL_USING_CPP11
typedef T&& rvalue_reference;
#endif
typedef T* pointer;
typedef const T* const_pointer;
typedef typename etl::iterator_traits<pointer>::difference_type difference_type;
//*************************************************************************
//*************************************************************************
class iterator : public etl::iterator<ETL_OR_STD::random_access_iterator_tag, T>
{
public:
friend class ideque;
friend class const_iterator;
//***************************************************
iterator()
: index(0)
, p_deque(0)
, p_buffer(0)
{
}
//***************************************************
iterator(const iterator& other)
: index(other.index)
, p_deque(other.p_deque)
, p_buffer(other.p_buffer)
{
}
//***************************************************
iterator& operator=(const iterator& other)
{
index = other.index;
p_deque = other.p_deque;
p_buffer = other.p_buffer;
return *this;
}
//***************************************************
iterator& operator++()
{
index = (static_cast<size_t>(index) == p_deque->Buffer_Size - 1) ? 0 : index + 1;
return *this;
}
//***************************************************
iterator operator++(int)
{
iterator previous(*this);
index = (static_cast<size_t>(index) == p_deque->Buffer_Size - 1) ? 0 : index + 1;
return previous;
}
//***************************************************
iterator& operator+=(difference_type offset)
{
if (offset > 0)
{
index += offset;
index = (static_cast<size_t>(index) > p_deque->Buffer_Size - 1) ? index - static_cast<difference_type>(p_deque->Buffer_Size) : index;
}
else if (offset < 0)
{
operator-=(-offset);
}
return *this;
}
//***************************************************
iterator& operator-=(difference_type offset)
{
if (offset > 0)
{
index -= offset;
index = (index < 0) ? index + static_cast<difference_type>(p_deque->Buffer_Size) : index;
}
else if (offset < 0)
{
operator+=(-offset);
}
return *this;
}
//***************************************************
iterator& operator--()
{
index = (index == 0) ? static_cast<difference_type>(p_deque->Buffer_Size) - 1 : index - 1;
return *this;
}
//***************************************************
iterator operator--(int)
{
iterator previous(*this);
index = (index == 0) ? static_cast<difference_type>(p_deque->Buffer_Size) - 1 : index - 1;
return previous;
}
//***************************************************
reference operator*() const
{
return p_buffer[index];
}
//***************************************************
pointer operator->() const
{
return &p_buffer[index];
}
//***************************************************
reference operator[](size_t i)
{
iterator result(*this);
result += i;
return *result;
}
//***************************************************
const_reference operator[](size_t i) const
{
iterator result(*this);
result += i;
return *result;
}
//***************************************************
friend iterator operator+(const iterator& lhs, difference_type offset)
{
iterator result(lhs);
result += offset;
return result;
}
//***************************************************
friend iterator operator+(difference_type offset, const iterator& lhs)
{
iterator result(lhs);
result += offset;
return result;
}
//***************************************************
friend iterator operator-(const iterator& lhs, difference_type offset)
{
iterator result(lhs);
result -= offset;
return result;
}
//***************************************************
friend bool operator==(const iterator& lhs, const iterator& rhs)
{
return lhs.index == rhs.index;
}
//***************************************************
friend bool operator!=(const iterator& lhs, const iterator& rhs)
{
return !(lhs == rhs);
}
//***************************************************
friend bool operator<(const iterator& lhs, const iterator& rhs)
{
const difference_type lhs_index = lhs.get_index();
const difference_type rhs_index = rhs.get_index();
const difference_type reference_index = lhs.container().begin().get_index();
const difference_type buffer_size = static_cast<difference_type>(lhs.container().max_size() + 1);
const difference_type lhs_distance = (lhs_index < reference_index) ? buffer_size + lhs_index - reference_index : lhs_index - reference_index;
const difference_type rhs_distance = (rhs_index < reference_index) ? buffer_size + rhs_index - reference_index : rhs_index - reference_index;
return lhs_distance < rhs_distance;
}
//***************************************************
friend bool operator<=(const iterator& lhs, const iterator& rhs)
{
return !(lhs > rhs);
}
//***************************************************
friend bool operator>(const iterator& lhs, const iterator& rhs)
{
return (rhs < lhs);
}
//***************************************************
friend bool operator>=(const iterator& lhs, const iterator& rhs)
{
return !(lhs < rhs);
}
//***************************************************
difference_type get_index() const
{
return index;
}
//***************************************************
ideque& container() const
{
return *p_deque;
}
//***************************************************
pointer get_buffer() const
{
return p_buffer;
}
//***************************************************
void swap(iterator& other)
{
using ETL_OR_STD::swap; // Allow ADL
swap(index, other.index);
swap(p_deque, other.p_deque);
swap(p_buffer, other.p_buffer);
}
private:
//***************************************************
iterator(difference_type index_, ideque& the_deque, pointer p_buffer_)
: index(index_)
, p_deque(&the_deque)
, p_buffer(p_buffer_)
{
}
difference_type index;
ideque* p_deque;
pointer p_buffer;
};
//*************************************************************************
//*************************************************************************
class const_iterator : public etl::iterator<ETL_OR_STD::random_access_iterator_tag, const T>
{
public:
friend class ideque;
//***************************************************
const_iterator()
: index(0)
, p_deque(0)
, p_buffer(0)
{
}
//***************************************************
const_iterator(const const_iterator& other)
: index(other.index)
, p_deque(other.p_deque)
, p_buffer(other.p_buffer)
{
}
//***************************************************
const_iterator(const typename ideque::iterator& other)
: index(other.index)
, p_deque(other.p_deque)
, p_buffer(other.p_buffer)
{
}
//***************************************************
const_iterator& operator=(const const_iterator& other)
{
index = other.index;
p_deque = other.p_deque;
p_buffer = other.p_buffer;
return *this;
}
const_iterator& operator=(const typename ideque::iterator& other)
{
index = other.index;
p_deque = other.p_deque;
p_buffer = other.p_buffer;
return *this;
}
//***************************************************
const_iterator& operator++()
{
index = (static_cast<size_t>(index) == p_deque->Buffer_Size - 1) ? 0 : index + 1;
return *this;
}
//***************************************************
const_iterator operator++(int)
{
const_iterator previous(*this);
index = (static_cast<size_t>(index) == p_deque->Buffer_Size - 1) ? 0 : index + 1;
return previous;
}
//***************************************************
const_iterator& operator+=(difference_type offset)
{
if (offset > 0)
{
index += offset;
index = (static_cast<size_t>(index) > p_deque->Buffer_Size - 1) ? index - static_cast<difference_type>(p_deque->Buffer_Size) : index;
}
else if (offset < 0)
{
operator-=(-offset);
}
return *this;
}
//***************************************************
const_iterator& operator-=(difference_type offset)
{
if (offset > 0)
{
index -= offset;
index = (index < 0) ? index + static_cast<difference_type>(p_deque->Buffer_Size) : index;
}
else if (offset < 0)
{
operator+=(-offset);
}
return *this;
}
//***************************************************
const_iterator& operator--()
{
index = (index == 0) ? static_cast<difference_type>(p_deque->Buffer_Size) - 1 : index - 1;
return *this;
}
//***************************************************
const_iterator operator--(int)
{
const_iterator previous(*this);
index = (index == 0) ? static_cast<difference_type>(p_deque->Buffer_Size) - 1 : index - 1;
return previous;
}
//***************************************************
const_reference operator*() const
{
return p_buffer[index];
}
//***************************************************
const_pointer operator->() const
{
return &p_buffer[index];
}
//***************************************************
const_reference operator[](size_t i) const
{
const_iterator result(*this);
result += static_cast<difference_type>(i);
return *result;
}
//***************************************************
friend const_iterator operator+(const const_iterator& lhs, difference_type offset)
{
const_iterator result(lhs);
result += offset;
return result;
}
//***************************************************
friend const_iterator operator+(difference_type offset, const const_iterator& lhs)
{
const_iterator result(lhs);
result += offset;
return result;
}
//***************************************************
friend const_iterator operator-(const const_iterator& lhs, difference_type offset)
{
const_iterator result(lhs);
result -= offset;
return result;
}
//***************************************************
friend bool operator==(const const_iterator& lhs, const const_iterator& rhs)
{
return lhs.index == rhs.index;
}
//***************************************************
friend bool operator!=(const const_iterator& lhs, const const_iterator& rhs)
{
return !(lhs == rhs);
}
//***************************************************
friend bool operator<(const const_iterator& lhs, const const_iterator& rhs)
{
const difference_type lhs_index = lhs.get_index();
const difference_type rhs_index = rhs.get_index();
const difference_type reference_index = lhs.container().begin().get_index();
const difference_type buffer_size = static_cast<difference_type>(lhs.container().max_size() + 1UL);
const difference_type lhs_distance = (lhs_index < reference_index) ? buffer_size + lhs_index - reference_index : lhs_index - reference_index;
const difference_type rhs_distance = (rhs_index < reference_index) ? buffer_size + rhs_index - reference_index : rhs_index - reference_index;
return lhs_distance < rhs_distance;
}
//***************************************************
friend bool operator<=(const const_iterator& lhs, const const_iterator& rhs)
{
return !(lhs > rhs);
}
//***************************************************
friend bool operator>(const const_iterator& lhs, const const_iterator& rhs)
{
return (rhs < lhs);
}
//***************************************************
friend bool operator>=(const const_iterator& lhs, const const_iterator& rhs)
{
return !(lhs < rhs);
}
//***************************************************
difference_type get_index() const
{
return index;
}
//***************************************************
ideque& container() const
{
return *p_deque;
}
//***************************************************
pointer get_buffer() const
{
return p_buffer;
}
//***************************************************
void swap(const_iterator& other)
{
ETL_OR_STD::swap(index, other.index);
ETL_OR_STD::swap(p_deque, other.p_deque);
ETL_OR_STD::swap(p_buffer, other.p_buffer);
}
private:
//***************************************************
const_iterator(difference_type index_, ideque& the_deque, pointer p_buffer_)
: index(index_)
, p_deque(&the_deque)
, p_buffer(p_buffer_)
{
}
difference_type index;
ideque* p_deque;
pointer p_buffer;
};
typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
//*************************************************************************
//*************************************************************************
template <typename TIterator>
typename etl::enable_if<!etl::is_integral<TIterator>::value, void>::type assign(TIterator range_begin, TIterator range_end)
{
initialise();
while (range_begin != range_end)
{
push_back(*range_begin);
++range_begin;
}
}
//*************************************************************************
//*************************************************************************
void assign(size_type n, const value_type& value)
{
ETL_ASSERT(n <= CAPACITY, ETL_ERROR(deque_full));
initialise();
while (n > 0)
{
create_element_back(value);
--n;
}
}
//*************************************************************************
//*************************************************************************
reference at(size_t index)
{
ETL_ASSERT(index < current_size, ETL_ERROR(deque_out_of_bounds));
iterator result(_begin);
result += static_cast<difference_type>(index);
return *result;
}
//*************************************************************************
//*************************************************************************
const_reference at(size_t index) const
{
ETL_ASSERT(index < current_size, ETL_ERROR(deque_out_of_bounds));
iterator result(_begin);
result += static_cast<difference_type>(index);
return *result;
}
//*************************************************************************
//*************************************************************************
reference operator[](size_t index)
{
iterator result(_begin);
result += static_cast<difference_type>(index);
return *result;
}
//*************************************************************************
//*************************************************************************
const_reference operator[](size_t index) const
{
iterator result(_begin);
result += static_cast<difference_type>(index);
return *result;
}
//*************************************************************************
//*************************************************************************
reference front()
{
ETL_ASSERT_CHECK_EXTRA(!empty(), ETL_ERROR(deque_empty));
return *_begin;
}
//*************************************************************************
//*************************************************************************
const_reference front() const
{
ETL_ASSERT_CHECK_EXTRA(!empty(), ETL_ERROR(deque_empty));
return *_begin;
}
//*************************************************************************
//*************************************************************************
reference back()
{
ETL_ASSERT_CHECK_EXTRA(!empty(), ETL_ERROR(deque_empty));
return *(_end - 1);
}
//*************************************************************************
//*************************************************************************
const_reference back() const
{
ETL_ASSERT_CHECK_EXTRA(!empty(), ETL_ERROR(deque_empty));
return *(_end - 1);
}
//*************************************************************************
//*************************************************************************
iterator begin()
{
return _begin;
}
//*************************************************************************
//*************************************************************************
const_iterator begin() const
{
return _begin;
}
//*************************************************************************
//*************************************************************************
const_iterator cbegin() const
{
return _begin;
}
//*************************************************************************
//*************************************************************************
iterator end()
{
return iterator(_end);
}
//*************************************************************************
//*************************************************************************
const_iterator end() const
{
return iterator(_end);
}
//*************************************************************************
//*************************************************************************
const_iterator cend() const
{
return const_iterator(_end);
}
//*************************************************************************
//*************************************************************************
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
//*************************************************************************
//*************************************************************************
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
//*************************************************************************
//*************************************************************************
const_reverse_iterator crbegin() const
{
return const_reverse_iterator(cend());
}
//*************************************************************************
//*************************************************************************
reverse_iterator rend()
{
return reverse_iterator(begin());
}
//*************************************************************************
//*************************************************************************
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
//*************************************************************************
//*************************************************************************
const_reverse_iterator crend() const
{
return const_reverse_iterator(cbegin());
}
//*************************************************************************
//*************************************************************************
void clear()
{
initialise();
}
//*************************************************************************
//*************************************************************************
void fill(const T& value)
{
etl::fill(begin(), end(), value);
}
//*************************************************************************
//*************************************************************************
iterator insert(const_iterator insert_position, const value_type& value)
{
iterator position(to_iterator(insert_position));
ETL_ASSERT(!full(), ETL_ERROR(deque_full));
if (insert_position == begin())
{
create_element_front(value);
position = _begin;
}
else if (insert_position == end())
{
create_element_back(value);
position = _end - 1;
}
else
{
// Are we closer to the front?
if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
{
// Construct the _begin.
create_element_front(*_begin);
// Move the values.
etl::move(_begin + 1, position, _begin);
// Write the new value.
*--position = value;
}
else
{
// Construct the _end.
create_element_back(*(_end - 1));
// Move the values.
etl::move_backward(position, _end - 2, _end - 1);
// Write the new value.
*position = value;
}
}
return position;
}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
iterator insert(const_iterator insert_position, value_type&& value)
{
iterator position(insert_position.index, *this, p_buffer);
ETL_ASSERT(!full(), ETL_ERROR(deque_full));
if (insert_position == begin())
{
create_element_front(etl::move(value));
position = _begin;
}
else if (insert_position == end())
{
create_element_back(etl::move(value));
position = _end - 1;
}
else
{
// Are we closer to the front?
if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
{
// Construct the _begin.
create_element_front(etl::move(*_begin));
// Move the values.
etl::move(_begin + 1, position, _begin);
// Write the new value.
*--position = etl::move(value);
}
else
{
// Construct the _end.
create_element_back(etl::move(*(_end - 1)));
// Move the values.
etl::move_backward(position, _end - 2, _end - 1);
// Write the new value.
*position = etl::move(value);
}
}
return position;
}
#endif
//*************************************************************************
//*************************************************************************
#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
template <typename... Args>
iterator emplace(const_iterator insert_position, Args&&... args)
{
iterator position(insert_position.index, *this, p_buffer);
ETL_ASSERT(!full(), ETL_ERROR(deque_full));
void* p;
if (insert_position == begin())
{
--_begin;
p = etl::addressof(*_begin);
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
position = _begin;
}
else if (insert_position == end())
{
p = etl::addressof(*_end);
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
position = _end - 1;
}
else
{
// Are we closer to the front?
if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
{
// Construct the _begin.
create_element_front(*_begin);
// Move the values.
etl::move(_begin + 1, position, _begin);
// Write the new value.
--position;
(*position).~T();
p = etl::addressof(*position);
}
else
{
// Construct the _end.
create_element_back(*(_end - 1));
// Move the values.
etl::move_backward(position, _end - 2, _end - 1);
// Write the new value.
(*position).~T();
p = etl::addressof(*position);
}
}
::new (p) T(etl::forward<Args>(args)...);
return position;
}
#else
//*************************************************************************
//*************************************************************************
template <typename T1>
iterator emplace(const_iterator insert_position, const T1& value1)
{
iterator position(insert_position.index, *this, p_buffer);
ETL_ASSERT(!full(), ETL_ERROR(deque_full));
void* p;
if (insert_position == begin())
{
--_begin;
p = etl::addressof(*_begin);
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
position = _begin;
}
else if (insert_position == end())
{
p = etl::addressof(*_end);
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
position = _end - 1;
}
else
{
// Are we closer to the front?
if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
{
// Construct the _begin.
create_element_front(*_begin);
// Move the values.
etl::move(_begin + 1, position, _begin);
// Write the new value.
--position;
(*position).~T();
p = etl::addressof(*position);
}
else
{
// Construct the _end.
create_element_back(*(_end - 1));
// Move the values.
etl::move_backward(position, _end - 2, _end - 1);
// Write the new value.
(*position).~T();
p = etl::addressof(*position);
}
}
::new (p) T(value1);
return position;
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2>
iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2)
{
iterator position(insert_position.index, *this, p_buffer);
ETL_ASSERT(!full(), ETL_ERROR(deque_full));
void* p;
if (insert_position == begin())
{
--_begin;
p = etl::addressof(*_begin);
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
position = _begin;
}
else if (insert_position == end())
{
p = etl::addressof(*_end);
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
position = _end - 1;
}
else
{
// Are we closer to the front?
if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
{
// Construct the _begin.
create_element_front(*_begin);
// Move the values.
etl::move(_begin + 1, position, _begin);
// Write the new value.
--position;
(*position).~T();
p = etl::addressof(*position);
}
else
{
// Construct the _end.
create_element_back(*(_end - 1));
// Move the values.
etl::move_backward(position, _end - 2, _end - 1);
// Write the new value.
(*position).~T();
p = etl::addressof(*position);
}
}
::new (p) T(value1, value2);
return position;
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2, typename T3>
iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2, const T3& value3)
{
iterator position(insert_position.index, *this, p_buffer);
ETL_ASSERT(!full(), ETL_ERROR(deque_full));
void* p;
if (insert_position == begin())
{
--_begin;
p = etl::addressof(*_begin);
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
position = _begin;
}
else if (insert_position == end())
{
p = etl::addressof(*_end);
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
position = _end - 1;
}
else
{
// Are we closer to the front?
if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
{
// Construct the _begin.
create_element_front(*_begin);
// Move the values.
etl::move(_begin + 1, position, _begin);
// Write the new value.
--position;
(*position).~T();
p = etl::addressof(*position);
}
else
{
// Construct the _end.
create_element_back(*(_end - 1));
// Move the values.
etl::move_backward(position, _end - 2, _end - 1);
// Write the new value.
(*position).~T();
p = etl::addressof(*position);
}
}
::new (p) T(value1, value2, value3);
return position;
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2, typename T3, typename T4>
iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2, const T3& value3, const T4& value4)
{
iterator position(insert_position.index, *this, p_buffer);
ETL_ASSERT(!full(), ETL_ERROR(deque_full));
void* p;
if (insert_position == begin())
{
--_begin;
p = etl::addressof(*_begin);
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
position = _begin;
}
else if (insert_position == end())
{
p = etl::addressof(*_end);
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
position = _end - 1;
}
else
{
// Are we closer to the front?
if (etl::distance(_begin, position) < etl::distance(position, _end - 1))
{
// Construct the _begin.
create_element_front(*_begin);
// Move the values.
etl::move(_begin + 1, position, _begin);
// Write the new value.
--position;
(*position).~T();
p = etl::addressof(*position);
}
else
{
// Construct the _end.
create_element_back(*(_end - 1));
// Move the values.
etl::move_backward(position, _end - 2, _end - 1);
// Write the new value.
(*position).~T();
p = etl::addressof(*position);
}
}
::new (p) T(value1, value2, value3, value4);
return position;
}
#endif
//*************************************************************************
//*************************************************************************
iterator insert(const_iterator insert_position, size_type n, const value_type& value)
{
iterator position;
ETL_ASSERT((current_size + n) <= CAPACITY, ETL_ERROR(deque_full));
if (insert_position == begin())
{
for (size_t i = 0UL; i < n; ++i)
{
create_element_front(value);
}
position = _begin;
}
else if (insert_position == end())
{
for (size_t i = 0UL; i < n; ++i)
{
create_element_back(value);
}
position = _end - static_cast<difference_type>(n);
}
else
{
// Non-const insert iterator.
position = iterator(insert_position.index, *this, p_buffer);
// Are we closer to the front?
if (distance(_begin, insert_position) <= difference_type(current_size / 2))
{
size_t n_insert = n;
size_t n_move = static_cast<size_t>(etl::distance(begin(), position));
size_t n_create_copy = etl::min(n_insert, n_move);
size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0;
size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0;
size_t n_copy_old = n_move - n_create_copy;
// Remember the original start.
iterator from = _begin + static_cast<difference_type>(n_create_copy) - 1;
iterator to;
// Create new.
for (size_t i = 0UL; i < n_create_new; ++i)
{
create_element_front(value);
}
// Create copy.
for (size_t i = 0UL; i < n_create_copy; ++i)
{
create_element_front(*from);
--from;
}
// Move old.
from = position - static_cast<difference_type>(n_copy_old);
to = _begin + static_cast<difference_type>(n_create_copy);
etl::move(from, from + static_cast<difference_type>(n_copy_old), to);
// Copy new.
to = position - static_cast<difference_type>(n_create_copy);
etl::fill_n(to, n_copy_new, value);
position = _begin + static_cast<difference_type>(n_move);
}
else
{
size_t n_insert = n;
size_t n_move = static_cast<size_t>(etl::distance(position, end()));
size_t n_create_copy = etl::min(n_insert, n_move);
size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0;
size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0;
size_t n_copy_old = n_move - n_create_copy;
// Create new.
for (size_t i = 0UL; i < n_create_new; ++i)
{
create_element_back(value);
}
// Create copy.
const_iterator from = position + static_cast<difference_type>(n_copy_old);
for (size_t i = 0UL; i < n_create_copy; ++i)
{
create_element_back(*from);
++from;
}
// Move old.
etl::move_backward(position, position + static_cast<difference_type>(n_copy_old),
position + static_cast<difference_type>(n_insert + n_copy_old));
// Copy new.
etl::fill_n(position, n_copy_new, value);
}
}
return position;
}
//*************************************************************************
//*************************************************************************
template <typename TIterator>
typename enable_if<!etl::is_integral<TIterator>::value, iterator>::type insert(const_iterator insert_position, TIterator range_begin,
TIterator range_end)
{
iterator position;
difference_type n = etl::distance(range_begin, range_end);
ETL_ASSERT((current_size + static_cast<size_t>(n)) <= CAPACITY, ETL_ERROR(deque_full));
if (insert_position == begin())
{
create_element_front(static_cast<size_t>(n), range_begin);
position = _begin;
}
else if (insert_position == end())
{
for (difference_type i = 0; i < n; ++i)
{
create_element_back(*range_begin);
++range_begin;
}
position = _end - n;
}
else
{
// Non-const insert iterator.
position = iterator(insert_position.index, *this, p_buffer);
// Are we closer to the front?
if (distance(_begin, insert_position) < difference_type(current_size / 2))
{
size_t n_insert = static_cast<size_t>(n);
size_t n_move = static_cast<size_t>(etl::distance(begin(), position));
size_t n_create_copy = etl::min(n_insert, n_move);
size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0;
size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0;
size_t n_copy_old = n_move - n_create_copy;
// Remember the original start.
iterator from;
iterator to;
// Create new.
create_element_front(n_create_new, range_begin);
// Create copy.
create_element_front(n_create_copy, _begin + static_cast<difference_type>(n_create_new));
// Move old.
from = position - static_cast<difference_type>(n_copy_old);
to = _begin + static_cast<difference_type>(n_create_copy);
etl::move(from, from + static_cast<difference_type>(n_copy_old), to);
// Copy new.
to = position - static_cast<difference_type>(n_create_copy);
range_begin += static_cast<difference_type>(n_create_new);
etl::copy(range_begin, range_begin + static_cast<difference_type>(n_copy_new), to);
position = _begin + static_cast<difference_type>(n_move);
}
else
{
size_t n_insert = static_cast<size_t>(n);
size_t n_move = static_cast<size_t>(etl::distance(position, end()));
size_t n_create_copy = etl::min(n_insert, n_move);
size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0;
size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0;
size_t n_copy_old = n_move - n_create_copy;
// Create new.
TIterator item = range_begin + static_cast<difference_type>(n_insert - n_create_new);
for (size_t i = 0UL; i < n_create_new; ++i)
{
create_element_back(*item);
++item;
}
// Create copy.
const_iterator from = position + static_cast<difference_type>(n_copy_old);
for (size_t i = 0UL; i < n_create_copy; ++i)
{
create_element_back(*from);
++from;
}
// Move old.
etl::move_backward(position, position + static_cast<difference_type>(n_copy_old),
position + static_cast<difference_type>(n_insert + n_copy_old));
// Copy new.
item = range_begin;
etl::copy(item, item + static_cast<difference_type>(n_copy_new), position);
}
}
return position;
}
//*************************************************************************
//*************************************************************************
iterator erase(const_iterator erase_position)
{
iterator position(to_iterator(erase_position));
// iterator position(erase_position.index, *this, p_buffer);
ETL_ASSERT(distance(position) <= difference_type(current_size), ETL_ERROR(deque_out_of_bounds));
if (position == _begin)
{
destroy_element_front();
position = begin();
}
else if (position == _end - 1)
{
destroy_element_back();
position = end();
}
else
{
// Are we closer to the front?
if (distance(_begin, position) < difference_type(current_size / 2))
{
etl::move_backward(_begin, position, position + 1);
destroy_element_front();
++position;
}
else
{
etl::move(position + 1, _end, position);
destroy_element_back();
}
}
return position;
}
//*************************************************************************
//*************************************************************************
iterator erase(const_iterator range_begin, const_iterator range_end)
{
iterator position(to_iterator(range_begin));
ETL_ASSERT((distance(range_begin) <= difference_type(current_size)) && (distance(range_end) <= difference_type(current_size)),
ETL_ERROR(deque_out_of_bounds));
// How many to erase?
size_t length = static_cast<size_t>(etl::distance(range_begin, range_end));
// At the beginning?
if (position == _begin)
{
for (size_t i = 0UL; i < length; ++i)
{
destroy_element_front();
}
position = begin();
}
// At the end?
else if (position == _end - static_cast<difference_type>(length))
{
for (size_t i = 0UL; i < length; ++i)
{
destroy_element_back();
}
position = end();
}
else
{
// Copy the smallest number of items.
// Are we closer to the front?
if (distance(_begin, position) < difference_type(current_size / 2))
{
// Move the items.
etl::move_backward(_begin, position, position + static_cast<difference_type>(length));
for (size_t i = 0UL; i < length; ++i)
{
destroy_element_front();
}
position += static_cast<difference_type>(length);
}
else
// Must be closer to the back.
{
// Move the items.
etl::move(position + static_cast<difference_type>(length), _end, position);
for (size_t i = 0UL; i < length; ++i)
{
destroy_element_back();
}
}
}
return position;
}
//*************************************************************************
//*************************************************************************
void push_back(const_reference item)
{
ETL_ASSERT_CHECK_PUSH_POP_OR_RETURN(!full(), ETL_ERROR(deque_full));
create_element_back(item);
}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
void push_back(rvalue_reference item)
{
ETL_ASSERT_CHECK_PUSH_POP_OR_RETURN(!full(), ETL_ERROR(deque_full));
create_element_back(etl::move(item));
}
#endif
#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
//*************************************************************************
//*************************************************************************
template <typename... Args>
reference emplace_back(Args&&... args)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
::new (&(*_end)) T(etl::forward<Args>(args)...);
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return back();
}
#else
//*************************************************************************
//*************************************************************************
reference emplace_back()
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
::new (&(*_end)) T();
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return back();
}
//*************************************************************************
//*************************************************************************
template <typename T1>
reference emplace_back(const T1& value1)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
::new (&(*_end)) T(value1);
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return back();
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2>
reference emplace_back(const T1& value1, const T2& value2)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
::new (&(*_end)) T(value1, value2);
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return back();
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2, typename T3>
reference emplace_back(const T1& value1, const T2& value2, const T3& value3)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
::new (&(*_end)) T(value1, value2, value3);
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return back();
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2, typename T3, typename T4>
reference emplace_back(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
::new (&(*_end)) T(value1, value2, value3, value4);
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return back();
}
#endif
//*************************************************************************
//*************************************************************************
void pop_back()
{
ETL_ASSERT_CHECK_PUSH_POP_OR_RETURN(!empty(), ETL_ERROR(deque_empty));
destroy_element_back();
}
//*************************************************************************
//*************************************************************************
void push_front(const_reference item)
{
ETL_ASSERT_CHECK_PUSH_POP_OR_RETURN(!full(), ETL_ERROR(deque_full));
create_element_front(item);
}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
void push_front(rvalue_reference item)
{
ETL_ASSERT_CHECK_PUSH_POP_OR_RETURN(!full(), ETL_ERROR(deque_full));
create_element_front(etl::move(item));
}
#endif
#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
//*************************************************************************
//*************************************************************************
template <typename... Args>
reference emplace_front(Args&&... args)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
--_begin;
::new (&(*_begin)) T(etl::forward<Args>(args)...);
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return front();
}
#else
//*************************************************************************
//*************************************************************************
reference emplace_front()
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
--_begin;
::new (&(*_begin)) T();
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return front();
}
//*************************************************************************
//*************************************************************************
template <typename T1>
reference emplace_front(const T1& value1)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
--_begin;
::new (&(*_begin)) T(value1);
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return front();
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2>
reference emplace_front(const T1& value1, const T2& value2)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
--_begin;
::new (&(*_begin)) T(value1, value2);
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return front();
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2, typename T3>
reference emplace_front(const T1& value1, const T2& value2, const T3& value3)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
--_begin;
::new (&(*_begin)) T(value1, value2, value3);
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return front();
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2, typename T3, typename T4>
reference emplace_front(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(deque_full));
--_begin;
::new (&(*_begin)) T(value1, value2, value3, value4);
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
return front();
}
#endif
//*************************************************************************
//*************************************************************************
void pop_front()
{
ETL_ASSERT_CHECK_PUSH_POP_OR_RETURN(!empty(), ETL_ERROR(deque_empty));
destroy_element_front();
}
//*************************************************************************
//*************************************************************************
void resize(size_t new_size, const value_type& value = value_type())
{
ETL_ASSERT(new_size <= CAPACITY, ETL_ERROR(deque_full));
// Make it smaller?
if (new_size < current_size)
{
while (current_size > new_size)
{
destroy_element_back();
}
}
// Make it larger?
else if (new_size > current_size)
{
size_t count = new_size - current_size;
for (size_t i = 0UL; i < count; ++i)
{
create_element_back(value);
}
}
}
//*************************************************************************
//*************************************************************************
friend difference_type operator-(const iterator& lhs, const iterator& rhs)
{
return distance(rhs, lhs);
}
//*************************************************************************
//*************************************************************************
friend difference_type operator-(const const_iterator& lhs, const const_iterator& rhs)
{
return distance(rhs, lhs);
}
//*************************************************************************
//*************************************************************************
ideque& operator=(const ideque& rhs)
{
if (&rhs != this)
{
assign(rhs.begin(), rhs.end());
}
return *this;
}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
ideque& operator=(ideque&& rhs)
{
if (&rhs != this)
{
clear();
iterator itr = rhs.begin();
while (itr != rhs.end())
{
push_back(etl::move(*itr));
++itr;
}
rhs.initialise();
}
return *this;
}
#endif
#ifdef ETL_IDEQUE_REPAIR_ENABLE
//*************************************************************************
//*************************************************************************
virtual void repair() = 0;
#endif
protected:
//*************************************************************************
//*************************************************************************
ideque(pointer p_buffer_, size_t max_size_, size_t buffer_size_)
: deque_base(max_size_, buffer_size_)
, p_buffer(p_buffer_)
{
}
//*********************************************************************
//*********************************************************************
void initialise()
{
if ETL_IF_CONSTEXPR (etl::is_trivially_destructible<T>::value)
{
current_size = 0;
ETL_RESET_DEBUG_COUNT;
}
else
{
while (current_size > 0)
{
destroy_element_back();
}
}
_begin = iterator(0, *this, p_buffer);
_end = iterator(0, *this, p_buffer);
}
//*************************************************************************
//*************************************************************************
void repair_buffer(pointer p_buffer_)
{
p_buffer = p_buffer_;
_begin = iterator(_begin.index, *this, p_buffer);
_end = iterator(_end.index, *this, p_buffer);
}
iterator _begin;
iterator _end;
pointer p_buffer;
private:
//*********************************************************************
//*********************************************************************
void create_element_front()
{
--_begin;
::new (&(*_begin)) T();
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
}
//*********************************************************************
//*********************************************************************
template <typename TIterator>
void create_element_front(size_t n, TIterator from)
{
if (n == 0)
{
return;
}
_begin -= static_cast<difference_type>(n);
iterator item = _begin;
do {
::new (&(*item)) T(*from);
++item;
++from;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
} while (--n != 0);
}
//*********************************************************************
//*********************************************************************
void create_element_back()
{
::new (&(*_end)) T();
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
}
//*********************************************************************
//*********************************************************************
void create_element_front(const_reference value)
{
--_begin;
::new (&(*_begin)) T(value);
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
}
//*********************************************************************
//*********************************************************************
void create_element_back(const_reference value)
{
::new (&(*_end)) T(value);
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
}
#if ETL_USING_CPP11
//*********************************************************************
//*********************************************************************
void create_element_front(rvalue_reference value)
{
--_begin;
::new (&(*_begin)) T(etl::move(value));
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
}
//*********************************************************************
//*********************************************************************
void create_element_back(rvalue_reference value)
{
::new (&(*_end)) T(etl::move(value));
++_end;
++current_size;
ETL_INCREMENT_DEBUG_COUNT;
}
#endif
//*********************************************************************
//*********************************************************************
void destroy_element_front()
{
(*_begin).~T();
--current_size;
ETL_DECREMENT_DEBUG_COUNT;
++_begin;
}
//*********************************************************************
//*********************************************************************
void destroy_element_back()
{
--_end;
(*_end).~T();
--current_size;
ETL_DECREMENT_DEBUG_COUNT;
}
//*************************************************************************
//*************************************************************************
template <typename TIterator1, typename TIterator2>
static difference_type distance(const TIterator1& range_begin, const TIterator2& range_end)
{
difference_type distance1 = distance(range_begin);
difference_type distance2 = distance(range_end);
return distance2 - distance1;
}
//*************************************************************************
//*************************************************************************
template <typename TIterator>
static difference_type distance(const TIterator& other)
{
const difference_type index = other.get_index();
const difference_type reference_index = other.container()._begin.index;
const difference_type buffer_size = static_cast<difference_type>(other.container().Buffer_Size);
if (index < reference_index)
{
return buffer_size + index - reference_index;
}
else
{
return index - reference_index;
}
}
//*************************************************************************
//*************************************************************************
iterator to_iterator(const_iterator itr) const
{
return iterator(itr.index, const_cast<ideque&>(*this), p_buffer);
}
// Disable copy construction.
ideque(const ideque&);
//*************************************************************************
//*************************************************************************
#if defined(ETL_POLYMORPHIC_DEQUE) || defined(ETL_POLYMORPHIC_CONTAINERS) || defined(ETL_IDEQUE_REPAIR_ENABLE)
public:
virtual ~ideque() {}
#else
protected:
~ideque() {}
#endif
};
//***************************************************************************
//***************************************************************************
template <typename T, const size_t MAX_SIZE_>
class deque : public etl::ideque<T>
{
public:
static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
private:
static ETL_CONSTANT size_t Buffer_Size = MAX_SIZE + 1;
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef typename etl::iterator_traits<pointer>::difference_type difference_type;
//*************************************************************************
//*************************************************************************
deque()
: etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, Buffer_Size)
{
this->initialise();
}
//*************************************************************************
//*************************************************************************
~deque()
{
this->initialise();
}
//*************************************************************************
//*************************************************************************
deque(const deque& other)
: etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, Buffer_Size)
{
if (this != &other)
{
this->assign(other.begin(), other.end());
}
}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
deque(deque&& other)
: etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, Buffer_Size)
{
if (this != &other)
{
this->initialise();
typename etl::ideque<T>::iterator itr = other.begin();
while (itr != other.end())
{
this->push_back(etl::move(*itr));
++itr;
}
}
}
#endif
//*************************************************************************
//*************************************************************************
template <typename TIterator>
deque(TIterator begin_, TIterator end_, typename etl::enable_if<!etl::is_integral<TIterator>::value, int>::type = 0)
: etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, Buffer_Size)
{
this->assign(begin_, end_);
}
//*************************************************************************
//*************************************************************************
explicit deque(size_t n, const_reference value = value_type())
: etl::ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, Buffer_Size)
{
this->assign(n, value);
}
#if ETL_HAS_INITIALIZER_LIST
//*************************************************************************
//*************************************************************************
deque(std::initializer_list<T> init)
: ideque<T>(reinterpret_cast<T*>(buffer.raw), MAX_SIZE, Buffer_Size)
{
this->assign(init.begin(), init.end());
}
#endif
//*************************************************************************
//*************************************************************************
deque& operator=(const deque& rhs)
{
if (&rhs != this)
{
this->assign(rhs.begin(), rhs.end());
}
return *this;
}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
deque& operator=(deque&& rhs)
{
if (&rhs != this)
{
this->clear();
typename etl::ideque<T>::iterator itr = rhs.begin();
while (itr != rhs.end())
{
this->push_back(etl::move(*itr));
++itr;
}
}
return *this;
}
#endif
//*************************************************************************
//*************************************************************************
#ifdef ETL_IDEQUE_REPAIR_ENABLE
virtual void repair() ETL_OVERRIDE
#else
void repair()
#endif
{
#if ETL_CPP11_TYPE_TRAITS_IS_TRIVIAL_SUPPORTED
ETL_ASSERT(etl::is_trivially_copyable<T>::value, ETL_ERROR(etl::deque_incompatible_type));
#endif
etl::ideque<T>::repair_buffer(reinterpret_cast<T*>(buffer.raw));
}
private:
etl::uninitialized_buffer_of<T, Buffer_Size> buffer;
};
template <typename T, const size_t MAX_SIZE_>
ETL_CONSTANT size_t deque<T, MAX_SIZE_>::MAX_SIZE;
//*************************************************************************
//*************************************************************************
#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
template <typename... T>
deque(T...) -> deque<typename etl::common_type_t<T...>, sizeof...(T)>;
#endif
//*************************************************************************
//*************************************************************************
#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
template <typename T, typename... TValues>
constexpr auto make_deque(TValues&&... values) -> etl::deque<T, sizeof...(TValues)>
{
return {etl::forward<T>(values)...};
}
#endif
//***************************************************************************
//***************************************************************************
template <typename T>
bool operator==(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
{
return (lhs.size() == rhs.size()) && etl::equal(lhs.begin(), lhs.end(), rhs.begin());
}
//***************************************************************************
//***************************************************************************
template <typename T>
bool operator!=(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
{
return !(lhs == rhs);
}
//***************************************************************************
//***************************************************************************
template <typename T>
bool operator<(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
{
return etl::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
//***************************************************************************
//***************************************************************************
template <typename T>
bool operator<=(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
{
return !(lhs > rhs);
}
//***************************************************************************
//***************************************************************************
template <typename T>
bool operator>(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
{
return (rhs < lhs);
}
//***************************************************************************
//***************************************************************************
template <typename T>
bool operator>=(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs)
{
return !(lhs < rhs);
}
} // namespace etl
#include "private/minmax_pop.h"
#endif
algorithm.h
swap
void swap(etl::array_view< T > &lhs, etl::array_view< T > &rhs) ETL_NOEXCEPT
Swaps the values.
Definition array_view.h:692
etl::ideque::const_iterator
Const Iterator.
Definition deque.h:483
etl::ideque::iterator
Iterator.
Definition deque.h:240
debug_count.h
error_handler.h
exception.h
etl::uninitialized_buffer_of
Definition memory.h:3153
etl::const_iterator
etl::ideque::emplace_front
reference emplace_front(const T1 &value1)
Definition deque.h:1968
etl::ideque::emplace_back
reference emplace_back(const T1 &value1, const T2 &value2, const T3 &value3)
Definition deque.h:1859
etl::ideque::crbegin
const_reverse_iterator crbegin() const
Gets a const reverse iterator to the end of the deque.
Definition deque.h:936
etl::ideque::clear
void clear()
Clears the deque.
Definition deque.h:968
etl::ideque::erase
iterator erase(const_iterator erase_position)
Definition deque.h:1650
etl::deque_base::CAPACITY
const size_type CAPACITY
The maximum number of elements in the deque.
Definition deque.h:210
etl::ideque::pop_back
void pop_back()
Removes the oldest item from the deque.
Definition deque.h:1891
etl::ideque::operator=
ideque & operator=(const ideque &rhs)
Assignment operator.
Definition deque.h:2092
etl::ideque::rbegin
const_reverse_iterator rbegin() const
Gets a const reverse iterator to the end of the deque.
Definition deque.h:928
etl::deque_base::ETL_DECLARE_DEBUG_COUNT
ETL_DECLARE_DEBUG_COUNT
Internal debugging.
Definition deque.h:212
etl::ideque::resize
void resize(size_t new_size, const value_type &value=value_type())
Definition deque.h:2049
etl::ideque::emplace
iterator emplace(const_iterator insert_position, const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition deque.h:1363
etl::ideque::begin
iterator begin()
Gets an iterator to the beginning of the deque.
Definition deque.h:872
etl::ideque::front
reference front()
Definition deque.h:827
etl::ideque::at
reference at(size_t index)
Definition deque.h:771
etl::ideque::emplace_back
reference emplace_back(const T1 &value1, const T2 &value2)
Definition deque.h:1842
etl::ideque::p_buffer
pointer p_buffer
Iterator to the _end item in the deque.
Definition deque.h:2178
etl::ideque::operator-
friend difference_type operator-(const iterator &lhs, const iterator &rhs)
Definition deque.h:2076
etl::ideque::emplace_front
reference emplace_front(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition deque.h:2019
etl::ideque::emplace_front
reference emplace_front()
Definition deque.h:1951
etl::ideque::assign
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:734
etl::ideque::initialise
void initialise()
Initialise the deque.
Definition deque.h:2146
etl::ideque::operator[]
reference operator[](size_t index)
Definition deque.h:801
etl::deque_base::~deque_base
~deque_base()
Destructor.
Definition deque.h:207
etl::ideque::_end
iterator _end
Iterator to the _begin item in the deque.
Definition deque.h:2177
etl::ideque::emplace_front
reference emplace_front(const T1 &value1, const T2 &value2, const T3 &value3)
Definition deque.h:2002
etl::deque_base::size
size_type size() const
Definition deque.h:142
etl::ideque::at
const_reference at(size_t index) const
Definition deque.h:787
etl::ideque::crend
const_reverse_iterator crend() const
Gets a const reverse iterator to the beginning of the deque.
Definition deque.h:960
etl::deque_base::Buffer_Size
const size_type Buffer_Size
The number of elements in the buffer.
Definition deque.h:211
etl::ideque::end
iterator end()
Gets an iterator to the end of the deque.
Definition deque.h:896
etl::ideque::end
const_iterator end() const
Gets a const iterator to the end of the deque.
Definition deque.h:904
etl::ideque::push_front
void push_front(const_reference item)
Definition deque.h:1904
etl::deque_base::max_size
size_type max_size() const
Definition deque.h:169
etl::ideque::~ideque
~ideque()
Destructor.
Definition deque.h:2352
etl::ideque::erase
iterator erase(const_iterator range_begin, const_iterator range_end)
Definition deque.h:1693
etl::ideque::emplace
iterator emplace(const_iterator insert_position, const T1 &value1)
Definition deque.h:1165
etl::deque::deque
deque(const deque &other)
Copy constructor.
Definition deque.h:2404
etl::ideque::operator-
friend difference_type operator-(const const_iterator &lhs, const const_iterator &rhs)
Definition deque.h:2084
etl::ideque::emplace
iterator emplace(const_iterator insert_position, const T1 &value1, const T2 &value2)
Definition deque.h:1231
etl::ideque::insert
iterator insert(const_iterator insert_position, size_type n, const value_type &value)
Definition deque.h:1431
etl::ideque::insert
enable_if<!etl::is_integral< TIterator >::value, iterator >::type insert(const_iterator insert_position, TIterator range_begin, TIterator range_end)
Definition deque.h:1543
etl::deque_base::full
bool full() const
Definition deque.h:160
etl::ideque::operator[]
const_reference operator[](size_t index) const
Definition deque.h:813
etl::deque_base::capacity
size_type capacity() const
Definition deque.h:178
etl::ideque::back
const_reference back() const
Definition deque.h:863
etl::deque_base::empty
bool empty() const
Definition deque.h:151
etl::deque::repair
void repair()
Fix the internal pointers after a low level memory copy.
Definition deque.h:2504
etl::ideque::rend
const_reverse_iterator rend() const
Gets a const reverse iterator to the beginning of the deque.
Definition deque.h:952
etl::ideque::cend
const_iterator cend() const
Gets a const iterator to the end of the deque.
Definition deque.h:912
etl::ideque::emplace_back
reference emplace_back(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition deque.h:1876
etl::ideque::emplace_back
reference emplace_back()
Definition deque.h:1808
etl::deque_base::deque_base
deque_base(size_t max_size_, size_t buffer_size_)
Constructor.
Definition deque.h:197
etl::ideque::emplace_front
reference emplace_front(const T1 &value1, const T2 &value2)
Definition deque.h:1985
etl::ideque::assign
void assign(size_type n, const value_type &value)
Definition deque.h:752
etl::deque::deque
deque()
Default constructor.
Definition deque.h:2387
etl::ideque::back
reference back()
Definition deque.h:851
etl::ideque::emplace
iterator emplace(const_iterator insert_position, const T1 &value1, const T2 &value2, const T3 &value3)
Definition deque.h:1297
etl::ideque::rbegin
reverse_iterator rbegin()
Gets a reverse iterator to the end of the deque.
Definition deque.h:920
etl::ideque::fill
void fill(const T &value)
Fills the deque.
Definition deque.h:976
etl::ideque::pop_front
void pop_front()
Removes the oldest item from the deque.
Definition deque.h:2034
etl::ideque::emplace_back
reference emplace_back(const T1 &value1)
Definition deque.h:1825
etl::ideque::push_back
void push_back(const_reference item)
Definition deque.h:1761
etl::ideque::cbegin
const_iterator cbegin() const
Gets a const iterator to the beginning of the deque.
Definition deque.h:888
etl::deque::deque
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:2438
etl::deque::~deque
~deque()
Destructor.
Definition deque.h:2396
etl::ideque::rend
reverse_iterator rend()
Gets a reverse iterator to the beginning of the deque.
Definition deque.h:944
etl::ideque::front
const_reference front() const
Definition deque.h:839
etl::deque::deque
deque(size_t n, const_reference value=value_type())
Assigns data to the deque.
Definition deque.h:2447
etl::deque_base::available
size_t available() const
Definition deque.h:187
etl::deque::operator=
deque & operator=(const deque &rhs)
Assignment operator.
Definition deque.h:2467
etl::ideque::begin
const_iterator begin() const
Gets a const iterator to the beginning of the deque.
Definition deque.h:880
etl::ideque::insert
iterator insert(const_iterator insert_position, const value_type &value)
Definition deque.h:988
etl::ideque::repair_buffer
void repair_buffer(pointer p_buffer_)
Fix the internal pointers after a low level memory copy.
Definition deque.h:2168
etl::deque_base::current_size
size_type current_size
The current number of elements in the deque.
Definition deque.h:209
etl::ideque::ideque
ideque(pointer p_buffer_, size_t max_size_, size_t buffer_size_)
Constructor.
Definition deque.h:2137
etl::deque
Definition deque.h:2365
etl::deque_base
Definition deque.h:133
etl::deque_empty
Definition deque.h:91
etl::deque_exception
Definition deque.h:63
etl::deque_full
Definition deque.h:77
etl::deque_out_of_bounds
Definition deque.h:105
etl::ideque
Definition deque.h:222
ETL_ASSERT
#define ETL_ASSERT(b, e)
Definition error_handler.h:511
etl::exception::exception
ETL_EXCEPTION_CONSTEXPR exception(string_type reason_, string_type, numeric_type)
Constructor.
Definition exception.h:81
etl::exception
Definition exception.h:59
etl::addressof
ETL_CONSTEXPR17 etl::enable_if<!etl::is_same< T, etl::nullptr_t >::value, T >::type * addressof(T &t)
Definition addressof.h:52
etl::deque_incompatible_type
Definition deque.h:119
initializer_list.h
iterator.h
memory.h
minmax_pop.h
minmax_push.h
etl
Definition absolute.h:40
etl::operator==
ETL_CONSTEXPR14 bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:1078
etl::operator>
bool operator>(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:1130
etl::operator>=
bool operator>=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:1144
etl::operator!=
ETL_CONSTEXPR14 bool operator!=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:1090
etl::operator<
bool operator<(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:1103
etl::operator<=
bool operator<=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:1117
placement_new.h
platform.h
etl::value_type
etl::iterator
iterator
Definition iterator.h:482
etl::type
operator==
ETL_CONSTEXPR14 bool operator==(const etl::to_arithmetic_result< T > &lhs, const etl::to_arithmetic_result< T > &rhs)
Equality test for etl::to_arithmetic_result.
Definition to_arithmetic.h:903
operator!=
ETL_CONSTEXPR14 bool operator!=(const etl::to_arithmetic_result< T > &lhs, const etl::to_arithmetic_result< T > &rhs)
Inequality test for etl::to_arithmetic_result.
Definition to_arithmetic.h:937
type_traits.h
utility.h