/usr/include/stxxl/bits/containers
Edit: /usr/include/stxxl/bits/containers/deque.h (18855B)
/***************************************************************************
* include/stxxl/bits/containers/deque.h
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2006 Roman Dementiev
* Copyright (C) 2008, 2009 Andreas Beckmann
* Copyright (C) 2013 Timo Bingmann
*
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
**************************************************************************/
#ifndef STXXL_CONTAINERS_DEQUE_HEADER
#define STXXL_CONTAINERS_DEQUE_HEADER
#include
#include
STXXL_BEGIN_NAMESPACE
template
class deque;
template
class const_deque_iterator;
template
class deque_iterator
{
public:
typedef DequeType deque_type;
typedef typename deque_type::vector_type vector_type;
typedef typename deque_type::value_type value_type;
typedef typename deque_type::pointer pointer;
typedef typename deque_type::const_pointer const_pointer;
typedef typename deque_type::reference reference;
typedef typename deque_type::const_reference const_reference;
typedef typename deque_type::size_type size_type;
typedef typename deque_type::difference_type difference_type;
typedef deque_iterator iterator;
typedef const_deque_iterator const_iterator;
typedef std::random_access_iterator_tag iterator_category;
friend class const_deque_iterator;
friend class deque;
protected:
typedef deque_iterator self_type;
deque_type* m_deque;
size_type m_offset;
deque_iterator(deque_type* deque, size_type offset)
: m_deque(deque), m_offset(offset)
{ }
public:
deque_iterator() : m_deque(NULL), m_offset(0) { }
difference_type operator - (const self_type& a) const
{
size_type SelfAbsOffset = (m_offset >= m_deque->m_begin) ?
m_offset : (m_deque->m_vector.size() + m_offset);
size_type aAbsOffset = (a.m_offset >= m_deque->m_begin) ?
a.m_offset : (m_deque->m_vector.size() + a.m_offset);
return SelfAbsOffset - aAbsOffset;
}
difference_type operator - (const const_iterator& a) const
{
size_type SelfAbsOffset = (m_offset >= m_deque->m_begin) ?
m_offset : (m_deque->m_vector.size() + m_offset);
size_type aAbsOffset = (a.m_offset >= m_deque->m_begin) ?
a.m_offset : (m_deque->m_vector.size() + a.m_offset);
return SelfAbsOffset - aAbsOffset;
}
self_type operator - (size_type op) const
{
return self_type(m_deque, (m_offset + m_deque->m_vector.size() - op) % m_deque->m_vector.size());
}
self_type operator + (size_type op) const
{
return self_type(m_deque, (m_offset + op) % m_deque->m_vector.size());
}
self_type& operator -= (size_type op)
{
m_offset = (m_offset + m_deque->m_vector.size() - op) % m_deque->m_vector.size();
return *this;
}
self_type& operator += (size_type op)
{
m_offset = (m_offset + op) % m_deque->m_vector.size();
return *this;
}
reference operator * ()
{
return m_deque->m_vector[m_offset];
}
pointer operator -> ()
{
return &(m_deque->m_vector[m_offset]);
}
const_reference operator * () const
{
return m_deque->m_vector[m_offset];
}
const_pointer operator -> () const
{
return &(m_deque->m_vector[m_offset]);
}
reference operator [] (size_type op)
{
return m_deque->m_vector[(m_offset + op) % m_deque->m_vector.size()];
}
const_reference operator [] (size_type op) const
{
return m_deque->m_vector[(m_offset + op) % m_deque->m_vector.size()];
}
self_type& operator ++ ()
{
m_offset = (m_offset + 1) % m_deque->m_vector.size();
return *this;
}
self_type operator ++ (int)
{
self_type tmp = *this;
m_offset = (m_offset + 1) % m_deque->m_vector.size();
return tmp;
}
self_type& operator -- ()
{
m_offset = (m_offset + m_deque->m_vector.size() - 1) % m_deque->m_vector.size();
return *this;
}
self_type operator -- (int)
{
self_type tmp = *this;
m_offset = (m_offset + m_deque->m_vector.size() - 1) % m_deque->m_vector.size();
return tmp;
}
bool operator == (const self_type& a) const
{
assert(m_deque == a.m_deque);
return m_offset == a.m_offset;
}
bool operator != (const self_type& a) const
{
assert(m_deque == a.m_deque);
return m_offset != a.m_offset;
}
bool operator < (const self_type& a) const
{
assert(m_deque == a.m_deque);
return (a - (*this)) > 0;
}
bool operator > (const self_type& a) const
{
return a < (*this);
}
bool operator <= (const self_type& a) const
{
return !((*this) > a);
}
bool operator >= (const self_type& a) const
{
return !((*this) < a);
}
bool operator == (const const_iterator& a) const
{
assert(m_deque == a.m_deque);
return m_offset == a.m_offset;
}
bool operator != (const const_iterator& a) const
{
assert(m_deque == a.m_deque);
return m_offset != a.m_offset;
}
bool operator < (const const_iterator& a) const
{
assert(m_deque == a.m_deque);
return (a - (*this)) > 0;
}
bool operator > (const const_iterator& a) const
{
return a < (*this);
}
bool operator <= (const const_iterator& a) const
{
return !((*this) > a);
}
bool operator >= (const const_iterator& a) const
{
return !((*this) < a);
}
};
template
class const_deque_iterator
{
public:
typedef DequeType deque_type;
typedef typename deque_type::vector_type vector_type;
typedef typename deque_type::value_type value_type;
typedef typename deque_type::const_pointer pointer;
typedef typename deque_type::const_pointer const_pointer;
typedef typename deque_type::const_reference reference;
typedef typename deque_type::const_reference const_reference;
typedef typename deque_type::size_type size_type;
typedef typename deque_type::difference_type difference_type;
typedef deque_iterator iterator;
typedef const_deque_iterator const_iterator;
typedef std::random_access_iterator_tag iterator_category;
friend class deque_iterator;
friend class deque;
protected:
typedef const_deque_iterator self_type;
const deque_type* m_deque;
size_type m_offset;
const_deque_iterator(const deque_type* deque, size_type offset)
: m_deque(deque), m_offset(offset)
{ }
public:
const_deque_iterator() : m_deque(NULL), m_offset(0) { }
const_deque_iterator(const deque_iterator& it)
: m_deque(it.m_deque), m_offset(it.m_offset)
{ }
difference_type operator - (const self_type& a) const
{
size_type SelfAbsOffset = (m_offset >= m_deque->m_begin) ?
m_offset : (m_deque->m_vector.size() + m_offset);
size_type aAbsOffset = (a.m_offset >= m_deque->m_begin) ?
a.m_offset : (m_deque->m_vector.size() + a.m_offset);
return SelfAbsOffset - aAbsOffset;
}
difference_type operator - (const iterator& a) const
{
size_type SelfAbsOffset = (m_offset >= m_deque->m_begin) ?
m_offset : (m_deque->m_vector.size() + m_offset);
size_type aAbsOffset = (a.m_offset >= m_deque->m_begin) ?
a.m_offset : (m_deque->m_vector.size() + a.m_offset);
return SelfAbsOffset - aAbsOffset;
}
self_type operator - (size_type op) const
{
return self_type(m_deque, (m_offset + m_deque->m_vector.size() - op) % m_deque->m_vector.size());
}
self_type operator + (size_type op) const
{
return self_type(m_deque, (m_offset + op) % m_deque->m_vector.size());
}
self_type& operator -= (size_type op)
{
m_offset = (m_offset + m_deque->m_vector.size() - op) % m_deque->m_vector.size();
return *this;
}
self_type& operator += (size_type op)
{
m_offset = (m_offset + op) % m_deque->m_vector.size();
return *this;
}
const_reference operator * () const
{
return m_deque->m_vector[m_offset];
}
const_pointer operator -> () const
{
return &(m_deque->m_vector[m_offset]);
}
const_reference operator [] (size_type op) const
{
return m_deque->m_vector[(m_offset + op) % m_deque->m_vector.size()];
}
self_type& operator ++ ()
{
m_offset = (m_offset + 1) % m_deque->m_vector.size();
return *this;
}
self_type operator ++ (int)
{
self_type tmp = *this;
m_offset = (m_offset + 1) % m_deque->m_vector.size();
return tmp;
}
self_type& operator -- ()
{
m_offset = (m_offset + m_deque->m_vector.size() - 1) % m_deque->m_vector.size();
return *this;
}
self_type operator -- (int)
{
self_type tmp = *this;
m_offset = (m_offset + m_deque->m_vector.size() - 1) % m_deque->m_vector.size();
return tmp;
}
bool operator == (const self_type& a) const
{
assert(m_deque == a.m_deque);
return m_offset == a.m_offset;
}
bool operator != (const self_type& a) const
{
assert(m_deque == a.m_deque);
return m_offset != a.m_offset;
}
bool operator < (const self_type& a) const
{
assert(m_deque == a.m_deque);
return (a - (*this)) > 0;
}
bool operator > (const self_type& a) const
{
return a < (*this);
}
bool operator <= (const self_type& a) const
{
return !((*this) > a);
}
bool operator >= (const self_type& a) const
{
return !((*this) < a);
}
bool operator == (const iterator& a) const
{
assert(m_deque == a.m_deque);
return m_offset == a.m_offset;
}
bool operator != (const iterator& a) const
{
assert(m_deque == a.m_deque);
return m_offset != a.m_offset;
}
bool operator < (const iterator& a) const
{
assert(m_deque == a.m_deque);
return (a - (*this)) > 0;
}
bool operator > (const iterator& a) const
{
return a < (*this);
}
bool operator <= (const iterator& a) const
{
return !((*this) > a);
}
bool operator >= (const iterator& a) const
{
return !((*this) < a);
}
};
//! \addtogroup stlcont
//! \{
//! A deque container. \n
//! Introduction to deque container: see \ref tutorial_deque tutorial. \n
//! Design and Internals of deque container: see \ref design_deque
//!
//! It is an adaptor of the \c VectorType.
//! The implementation wraps the elements around
//! the end of the \c VectorType circularly.
//! \tparam ValueType type of the contained objects (POD with no references to internal memory)
//! \tparam VectorType the type of the underlying vector container,
//! the default is \c stxxl::vector
template >
class deque : private noncopyable
{
typedef deque self_type;
public:
typedef typename VectorType::size_type size_type;
typedef typename VectorType::difference_type difference_type;
typedef VectorType vector_type;
typedef ValueType value_type;
typedef ValueType* pointer;
typedef const value_type* const_pointer;
typedef ValueType& reference;
typedef const ValueType& const_reference;
typedef deque_iterator iterator;
typedef const_deque_iterator const_iterator;
typedef std::reverse_iterator reverse_iterator;
typedef std::reverse_iterator const_reverse_iterator;
friend class deque_iterator;
friend class const_deque_iterator;
private:
vector_type m_vector;
size_type m_begin, m_end, m_size;
void double_array()
{
const size_type old_size = m_vector.size();
m_vector.resize(2 * old_size);
if (m_begin > m_end)
{ // copy data to the new end of the vector
const size_type new_begin = old_size + m_begin;
std::copy(m_vector.begin() + m_begin,
m_vector.begin() + old_size,
m_vector.begin() + new_begin);
m_begin = new_begin;
}
}
public:
//! \name Constructors/Destructors
//! \{
deque()
: m_vector((STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(value_type)),
m_begin(0), m_end(0), m_size(0)
{ }
deque(size_type n)
: m_vector(STXXL_MAX(STXXL_DEFAULT_BLOCK_SIZE(ValueType) / sizeof(value_type), 2 * n)),
m_begin(0), m_end(n), m_size(n)
{ }
~deque() // empty so far
{ }
//! \}
//! \name Iterators
//! \{
iterator begin()
{
return iterator(this, m_begin);
}
iterator end()
{
return iterator(this, m_end);
}
const_iterator begin() const
{
return const_iterator(this, m_begin);
}
const_iterator cbegin() const
{
return begin();
}
const_iterator end() const
{
return const_iterator(this, m_end);
}
const_iterator cend() const
{
return 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(end());
}
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(begin());
}
//! \}
//! \name Capacity
//! \{
size_type size() const
{
return m_size;
}
size_type max_size() const
{
return std::numeric_limits::max() / 2 - 1;
}
bool empty() const
{
return m_size == 0;
}
//! \}
//! \name Operators
//! \{
reference operator [] (size_type n)
{
assert(n < size());
return m_vector[(m_begin + n) % m_vector.size()];
}
const_reference operator [] (size_type n) const
{
assert(n < size());
return m_vector[(m_begin + n) % m_vector.size()];
}
reference front()
{
assert(!empty());
return m_vector[m_begin];
}
const_reference front() const
{
assert(!empty());
return m_vector[m_begin];
}
reference back()
{
assert(!empty());
return m_vector[(m_end + m_vector.size() - 1) % m_vector.size()];
}
const_reference back() const
{
assert(!empty());
return m_vector[(m_end + m_vector.size() - 1) % m_vector.size()];
}
//! \}
//! \name Modifiers
//! \{
void push_front(const value_type& el)
{
if ((m_begin + m_vector.size() - 1) % m_vector.size() == m_end)
{
// an overflow will occur: resize the array
double_array();
}
m_begin = (m_begin + m_vector.size() - 1) % m_vector.size();
m_vector[m_begin] = el;
++m_size;
}
void push_back(const value_type& el)
{
if ((m_end + 1) % m_vector.size() == m_begin)
{
// an overflow will occur: resize the array
double_array();
}
m_vector[m_end] = el;
m_end = (m_end + 1) % m_vector.size();
++m_size;
}
void pop_front()
{
assert(!empty());
m_begin = (m_begin + 1) % m_vector.size();
--m_size;
}
void pop_back()
{
assert(!empty());
m_end = (m_end + m_vector.size() - 1) % m_vector.size();
--m_size;
}
//! \}
//! \name Modifiers
//! \{
void swap(deque& obj)
{
std::swap(m_vector, obj.m_vector);
std::swap(m_begin, obj.m_begin);
std::swap(m_end, obj.m_end);
std::swap(m_size, obj.m_size);
}
void clear()
{
m_vector.clear();
m_vector.resize((STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(value_type));
m_begin = 0;
m_end = 0;
m_size = 0;
}
//! \}
//! \name Capacity
//! \{
void resize(size_type n)
{
if (n < size())
{
do
{
pop_back();
} while (n < size());
}
else
{
if (n + 1 > m_vector.size())
{ // need to resize
const size_type old_size = m_vector.size();
m_vector.resize(2 * n);
if (m_begin > m_end)
{ // copy data to the new end of the vector
const size_type new_begin = m_vector.size() - old_size + m_begin;
std::copy(m_vector.begin() + m_begin,
m_vector.begin() + old_size,
m_vector.begin() + new_begin);
m_begin = new_begin;
}
}
m_end = (m_end + n - size()) % m_vector.size();
m_size = n;
}
}
//! \}
};
template
bool operator == (const deque& a, const deque& b)
{
return std::equal(a.begin(), a.end(), b.begin());
}
template
bool operator < (const deque& a, const deque& b)
{
return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}
//! \}
STXXL_END_NAMESPACE
namespace std {
template
void swap(stxxl::deque& a,
stxxl::deque& b)
{
a.swap(b);
}
} // namespace std
#endif // !STXXL_CONTAINERS_DEQUE_HEADER