deque.h

/***************************************************************************
 * 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]>
 *
 * 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_DEQUE_H
#define _STXXL_DEQUE_H

#include <limits>
#include <stxxl/vector>


__STXXL_BEGIN_NAMESPACE

template <class T, class VectorType>
class deque;

template <class DequeType>
class const_deque_iterator;

template <class DequeType>
class deque_iterator
{
 typedef typename DequeType::size_type size_type;
 typedef typename DequeType::vector_type vector_type;
 typedef deque_iterator<DequeType> _Self;
 DequeType * Deque;
 size_type Offset;

 deque_iterator(DequeType * Deque_, size_type Offset_) :
 Deque(Deque_), Offset(Offset_)
 { }

 friend class const_deque_iterator<DequeType>;

public:
 typedef typename DequeType::value_type value_type;
 typedef typename DequeType::pointer pointer;
 typedef typename DequeType::const_pointer const_pointer;
 typedef typename DequeType::reference reference;
 typedef typename DequeType::const_reference const_reference;
 typedef deque_iterator<DequeType> iterator;
 typedef const_deque_iterator<DequeType> const_iterator;
 friend class deque<value_type, vector_type>;
 typedef std::random_access_iterator_tag iterator_category;
 typedef typename DequeType::difference_type difference_type;

 deque_iterator() : Deque(NULL), Offset(0) { }

 difference_type operator - (const _Self & a) const
 {
 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
 Offset : (Deque->Vector.size() + Offset);
 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
 a.Offset : (Deque->Vector.size() + a.Offset);

 return SelfAbsOffset - aAbsOffset;
 }

 difference_type operator - (const const_iterator & a) const
 {
 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
 Offset : (Deque->Vector.size() + Offset);
 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
 a.Offset : (Deque->Vector.size() + a.Offset);

 return SelfAbsOffset - aAbsOffset;
 }

 _Self operator - (size_type op) const
 {
 return _Self(Deque, (Offset + Deque->Vector.size() - op) % Deque->Vector.size());
 }

 _Self operator + (size_type op) const
 {
 return _Self(Deque, (Offset + op) % Deque->Vector.size());
 }

 _Self & operator -= (size_type op)
 {
 Offset = (Offset + Deque->Vector.size() - op) % Deque->Vector.size();
 return *this;
 }

 _Self & operator += (size_type op)
 {
 Offset = (Offset + op) % Deque->Vector.size();
 return *this;
 }

 reference operator * ()
 {
 return Deque->Vector[Offset];
 }

 pointer operator -> ()
 {
 return &(Deque->Vector[Offset]);
 }

 const_reference operator * () const
 {
 return Deque->Vector[Offset];
 }

 const_pointer operator -> () const
 {
 return &(Deque->Vector[Offset]);
 }

 reference operator [] (size_type op)
 {
 return Deque->Vector[(Offset + op) % Deque->Vector.size()];
 }

 const_reference operator [] (size_type op) const
 {
 return Deque->Vector[(Offset + op) % Deque->Vector.size()];
 }

 _Self & operator ++ ()
 {
 Offset = (Offset + 1) % Deque->Vector.size();
 return *this;
 }
 _Self operator ++ (int)
 {
 _Self __tmp = *this;
 Offset = (Offset + 1) % Deque->Vector.size();
 return __tmp;
 }
 _Self & operator -- ()
 {
 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
 return *this;
 }
 _Self operator -- (int)
 {
 _Self __tmp = *this;
 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
 return __tmp;
 }
 bool operator == (const _Self & a) const
 {
 assert(Deque == a.Deque);
 return Offset == a.Offset;
 }
 bool operator != (const _Self & a) const
 {
 assert(Deque == a.Deque);
 return Offset != a.Offset;
 }

 bool operator < (const _Self & a) const
 {
 assert(Deque == a.Deque);
 return (a - (*this)) > 0;
 }

 bool operator > (const _Self & a) const
 {
 return a < (*this);
 }

 bool operator <= (const _Self & a) const
 {
 return !((*this) > a);
 }

 bool operator >= (const _Self & a) const
 {
 return !((*this) < a);
 }

 bool operator == (const const_iterator & a) const
 {
 assert(Deque == a.Deque);
 return Offset == a.Offset;
 }
 bool operator != (const const_iterator & a) const
 {
 assert(Deque == a.Deque);
 return Offset != a.Offset;
 }

 bool operator < (const const_iterator & a) const
 {
 assert(Deque == a.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
{
 typedef const_deque_iterator<DequeType> _Self;
 typedef typename DequeType::size_type size_type;
 typedef typename DequeType::vector_type vector_type;
 const DequeType * Deque;
 size_type Offset;

 const_deque_iterator(const DequeType * Deque_, size_type Offset_) :
 Deque(Deque_), Offset(Offset_)
 { }

public:
 typedef typename DequeType::value_type value_type;
 typedef typename DequeType::const_pointer pointer;
 typedef typename DequeType::const_pointer const_pointer;
 typedef typename DequeType::const_reference reference;
 typedef typename DequeType::const_reference const_reference;
 typedef deque_iterator<DequeType> iterator;
 typedef const_deque_iterator<DequeType> const_iterator;
 friend class deque<value_type, vector_type>;
 friend class deque_iterator<DequeType>;

 typedef std::random_access_iterator_tag iterator_category;
 typedef typename DequeType::difference_type difference_type;

 const_deque_iterator() : Deque(NULL), Offset(0) { }
 const_deque_iterator(const deque_iterator<DequeType> & it) :
 Deque(it.Deque), Offset(it.Offset)
 { }

 difference_type operator - (const _Self & a) const
 {
 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
 Offset : (Deque->Vector.size() + Offset);
 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
 a.Offset : (Deque->Vector.size() + a.Offset);

 return SelfAbsOffset - aAbsOffset;
 }

 difference_type operator - (const iterator & a) const
 {
 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
 Offset : (Deque->Vector.size() + Offset);
 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
 a.Offset : (Deque->Vector.size() + a.Offset);

 return SelfAbsOffset - aAbsOffset;
 }

 _Self operator - (size_type op) const
 {
 return _Self(Deque, (Offset + Deque->Vector.size() - op) % Deque->Vector.size());
 }

 _Self operator + (size_type op) const
 {
 return _Self(Deque, (Offset + op) % Deque->Vector.size());
 }

 _Self & operator -= (size_type op)
 {
 Offset = (Offset + Deque->Vector.size() - op) % Deque->Vector.size();
 return *this;
 }

 _Self & operator += (size_type op)
 {
 Offset = (Offset + op) % Deque->Vector.size();
 return *this;
 }

 const_reference operator * () const
 {
 return Deque->Vector[Offset];
 }

 const_pointer operator -> () const
 {
 return &(Deque->Vector[Offset]);
 }

 const_reference operator [] (size_type op) const
 {
 return Deque->Vector[(Offset + op) % Deque->Vector.size()];
 }

 _Self & operator ++ ()
 {
 Offset = (Offset + 1) % Deque->Vector.size();
 return *this;
 }
 _Self operator ++ (int)
 {
 _Self __tmp = *this;
 Offset = (Offset + 1) % Deque->Vector.size();
 return __tmp;
 }
 _Self & operator -- ()
 {
 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
 return *this;
 }
 _Self operator -- (int)
 {
 _Self __tmp = *this;
 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
 return __tmp;
 }
 bool operator == (const _Self & a) const
 {
 assert(Deque == a.Deque);
 return Offset == a.Offset;
 }
 bool operator != (const _Self & a) const
 {
 assert(Deque == a.Deque);
 return Offset != a.Offset;
 }

 bool operator < (const _Self & a) const
 {
 assert(Deque == a.Deque);
 return (a - (*this)) > 0;
 }

 bool operator > (const _Self & a) const
 {
 return a < (*this);
 }

 bool operator <= (const _Self & a) const
 {
 return !((*this) > a);
 }

 bool operator >= (const _Self & a) const
 {
 return !((*this) < a);
 }

 bool operator == (const iterator & a) const
 {
 assert(Deque == a.Deque);
 return Offset == a.Offset;
 }
 bool operator != (const iterator & a) const
 {
 assert(Deque == a.Deque);
 return Offset != a.Offset;
 }

 bool operator < (const iterator & a) const
 {
 assert(Deque == a.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);
 }
};


template <class T, class VectorType = stxxl::vector<T> >
class deque : private noncopyable
{
 typedef deque<T, VectorType> Self_;

public:
 typedef typename VectorType::size_type size_type;
 typedef typename VectorType::difference_type difference_type;
 typedef VectorType vector_type;
 typedef T value_type;
 typedef T * pointer;
 typedef const value_type * const_pointer;
 typedef T & reference;
 typedef const T & const_reference;
 typedef deque_iterator<Self_> iterator;
 typedef const_deque_iterator<Self_> const_iterator;
 typedef std::reverse_iterator<iterator> reverse_iterator;
 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

 friend class deque_iterator<Self_>;
 friend class const_deque_iterator<Self_>;

private:
 VectorType Vector;
 size_type begin_o, end_o, size_;

 void double_array()
 {
 const size_type old_size = Vector.size();
 Vector.resize(2 * old_size);
 if (begin_o > end_o)
 { // copy data to the new end of the vector
 const size_type new_begin_o = old_size + begin_o;
 std::copy(Vector.begin() + begin_o,
 Vector.begin() + old_size,
 Vector.begin() + new_begin_o);
 begin_o = new_begin_o;
 }
 }

public:
 deque() : Vector((STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(T)), begin_o(0), end_o(0), size_(0)
 { }

 deque(size_type n)
 : Vector(STXXL_MAX<size_type>(STXXL_DEFAULT_BLOCK_SIZE(T) / sizeof(T), 2 * n)),
 begin_o(0), end_o(n), size_(n)
 { }

 ~deque() // empty so far
 { }

 iterator begin()
 {
 return iterator(this, begin_o);
 }
 iterator end()
 {
 return iterator(this, end_o);
 }
 const_iterator begin() const
 {
 return const_iterator(this, begin_o);
 }
 const_iterator cbegin() const
 {
 return begin();
 }
 const_iterator end() const
 {
 return const_iterator(this, end_o);
 }
 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());
 }

 size_type size() const
 {
 return size_;
 }

 size_type max_size() const
 {
 return (std::numeric_limits<size_type>::max)() / 2 - 1;
 }

 bool empty() const
 {
 return size_ == 0;
 }

 reference operator [] (size_type n)
 {
 assert(n < size());
 return Vector[(begin_o + n) % Vector.size()];
 }

 const_reference operator [] (size_type n) const
 {
 assert(n < size());
 return Vector[(begin_o + n) % Vector.size()];
 }

 reference front()
 {
 assert(!empty());
 return Vector[begin_o];
 }

 const_reference front() const
 {
 assert(!empty());
 return Vector[begin_o];
 }

 reference back()
 {
 assert(!empty());
 return Vector[(end_o + Vector.size() - 1) % Vector.size()];
 }

 const_reference back() const
 {
 assert(!empty());
 return Vector[(end_o + Vector.size() - 1) % Vector.size()];
 }

 void push_front(const T & el)
 {
 if ((begin_o + Vector.size() - 1) % Vector.size() == end_o)
 {
 // an overflow will occur: resize the array
 double_array();
 }

 begin_o = (begin_o + Vector.size() - 1) % Vector.size();
 Vector[begin_o] = el;
 ++size_;
 }

 void push_back(const T & el)
 {
 if ((end_o + 1) % Vector.size() == begin_o)
 {
 // an overflow will occur: resize the array
 double_array();
 }
 Vector[end_o] = el;
 end_o = (end_o + 1) % Vector.size();
 ++size_;
 }

 void pop_front()
 {
 assert(!empty());
 begin_o = (begin_o + 1) % Vector.size();
 --size_;
 }

 void pop_back()
 {
 assert(!empty());
 end_o = (end_o + Vector.size() - 1) % Vector.size();
 --size_;
 }

 void swap(deque & obj)
 {
 std::swap(Vector, obj.Vector);
 std::swap(begin_o, obj.begin_o);
 std::swap(end_o, obj.end_o);
 std::swap(size_, obj.size_);
 }

 void clear()
 {
 Vector.clear();
 Vector.resize((STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(T));
 begin_o = 0;
 end_o = 0;
 size_ = 0;
 }

 void resize(size_type n)
 {
 if (n < size())
 {
 do
 {
 pop_back();
 } while (n < size());
 }
 else
 {
 if (n + 1 > Vector.size())
 { // need to resize
 const size_type old_size = Vector.size();
 Vector.resize(2 * n);
 if (begin_o > end_o)
 { // copy data to the new end of the vector
 const size_type new_begin_o = Vector.size() - old_size + begin_o;
 std::copy(Vector.begin() + begin_o,
 Vector.begin() + old_size,
 Vector.begin() + new_begin_o);
 begin_o = new_begin_o;
 }
 }
 end_o = (end_o + n - size()) % Vector.size();
 size_ = n;
 }
 }
};

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

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


__STXXL_END_NAMESPACE

namespace std
{
 template <typename T, typename VT>
 void swap(stxxl::deque<T, VT> & a,
 stxxl::deque<T, VT> & b)
 {
 a.swap(b);
 }
}

#endif /* _STXXL_DEQUE_H */