deque.h

Go to the documentation of this file.

/***************************************************************************
 * include/stxxl/bits/containers/deque.h
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2006 Roman Dementiev <[email protected]>
 * Copyright (C) 2008, 2009 Andreas Beckmann <[email protected]>
 * Copyright (C) 2013 Timo Bingmann <[email protected]>
 *
 * 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 <limits>
#include <stxxl/vector>

STXXL_BEGIN_NAMESPACE

template <class ValueType, class VectorType>
class deque;

template <class DequeType>
class const_deque_iterator;

template <class DequeType>
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<deque_type> iterator;
 typedef const_deque_iterator<deque_type> const_iterator;

 typedef std::random_access_iterator_tag iterator_category;

 friend class const_deque_iterator<deque_type>;
 friend class deque<value_type, vector_type>;

protected:
 typedef deque_iterator<deque_type> 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 DequeType>
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<deque_type> iterator;
 typedef const_deque_iterator<deque_type> const_iterator;

 typedef std::random_access_iterator_tag iterator_category;

 friend class deque_iterator<deque_type>;
 friend class deque<value_type, vector_type>;

protected:
 typedef const_deque_iterator<deque_type> 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<deque_type>& 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
//! <b> Introduction </b> to deque container: see \ref tutorial_deque tutorial. \n
//! <b> Design and Internals </b> 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<ValueType>
template <class ValueType, class VectorType = stxxl::vector<ValueType> >
class deque : private noncopyable
{
 typedef deque<ValueType, VectorType> 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<self_type> iterator;
 typedef const_deque_iterator<self_type> const_iterator;
 typedef std::reverse_iterator<iterator> reverse_iterator;
 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

 friend class deque_iterator<self_type>;
 friend class const_deque_iterator<self_type>;

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<size_type>(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<size_type>::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 <class ValueType, class VectorType>
bool operator == (const deque<ValueType, VectorType>& a, const deque<ValueType, VectorType>& b)
{
 return std::equal(a.begin(), a.end(), b.begin());
}

template <class ValueType, class VectorType>
bool operator < (const deque<ValueType, VectorType>& a, const deque<ValueType, VectorType>& b)
{
 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}

//! \}

STXXL_END_NAMESPACE

namespace std {

template <typename ValueType, typename VectorType>
void swap(stxxl::deque<ValueType, VectorType>& a,
 stxxl::deque<ValueType, VectorType>& b)
{
 a.swap(b);
}

} // namespace std

#endif // !STXXL_CONTAINERS_DEQUE_HEADER