13 #ifndef _STXXL_DEQUE_H
14 #define _STXXL_DEQUE_H
16 #include <stxxl/vector>
19 __STXXL_BEGIN_NAMESPACE
21 template <
class T,
class VectorType>
24 template <
class DequeType>
25 class const_deque_iterator;
27 template <
class DequeType>
30 typedef typename DequeType::size_type size_type;
31 typedef typename DequeType::vector_type vector_type;
32 typedef deque_iterator<DequeType> _Self;
36 deque_iterator(DequeType * Deque_, size_type Offset_) :
37 Deque(Deque_), Offset(Offset_)
40 friend class const_deque_iterator<DequeType>;
43 typedef typename DequeType::value_type value_type;
44 typedef typename DequeType::pointer pointer;
45 typedef typename DequeType::const_pointer const_pointer;
46 typedef typename DequeType::reference reference;
47 typedef typename DequeType::const_reference const_reference;
48 typedef deque_iterator<DequeType> iterator;
49 typedef const_deque_iterator<DequeType> const_iterator;
50 friend class deque<value_type, vector_type>;
51 typedef std::random_access_iterator_tag iterator_category;
52 typedef typename DequeType::difference_type difference_type;
54 deque_iterator() : Deque(NULL), Offset(0) { }
56 difference_type operator - (
const _Self & a)
const
58 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
59 Offset : (Deque->Vector.size() + Offset);
60 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
61 a.Offset : (Deque->Vector.size() + a.Offset);
63 return SelfAbsOffset - aAbsOffset;
66 difference_type operator - (
const const_iterator & a)
const
68 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
69 Offset : (Deque->Vector.size() + Offset);
70 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
71 a.Offset : (Deque->Vector.size() + a.Offset);
73 return SelfAbsOffset - aAbsOffset;
76 _Self operator - (size_type op)
const
78 return _Self(Deque, (Offset + Deque->Vector.size() - op) % Deque->Vector.size());
81 _Self operator + (size_type op)
const
83 return _Self(Deque, (Offset + op) % Deque->Vector.size());
86 _Self & operator -= (size_type op)
88 Offset = (Offset + Deque->Vector.size() - op) % Deque->Vector.size();
92 _Self & operator += (size_type op)
94 Offset = (Offset + op) % Deque->Vector.size();
98 reference operator * ()
100 return Deque->Vector[Offset];
103 pointer operator -> ()
105 return &(Deque->Vector[Offset]);
108 const_reference operator * ()
const
110 return Deque->Vector[Offset];
113 const_pointer operator -> ()
const
115 return &(Deque->Vector[Offset]);
118 reference operator [] (size_type op)
120 return Deque->Vector[(Offset + op) % Deque->Vector.size()];
123 const_reference operator [] (size_type op)
const
125 return Deque->Vector[(Offset + op) % Deque->Vector.size()];
128 _Self & operator ++ ()
130 Offset = (Offset + 1) % Deque->Vector.size();
133 _Self operator ++ (
int)
136 Offset = (Offset + 1) % Deque->Vector.size();
139 _Self & operator -- ()
141 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
144 _Self operator -- (
int)
147 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
150 bool operator == (
const _Self & a)
const
152 assert(Deque == a.Deque);
153 return Offset == a.Offset;
155 bool operator != (
const _Self & a)
const
157 assert(Deque == a.Deque);
158 return Offset != a.Offset;
161 bool operator < (
const _Self & a)
const
163 assert(Deque == a.Deque);
164 return (a - (*
this)) > 0;
167 bool operator == (
const const_iterator & a)
const
169 assert(Deque == a.Deque);
170 return Offset == a.Offset;
172 bool operator != (
const const_iterator & a)
const
174 assert(Deque == a.Deque);
175 return Offset != a.Offset;
178 bool operator < (
const const_iterator & a)
const
180 assert(Deque == a.Deque);
181 return (a - (*
this)) > 0;
185 template <
class DequeType>
186 class const_deque_iterator
188 typedef const_deque_iterator<DequeType> _Self;
189 typedef typename DequeType::size_type size_type;
190 typedef typename DequeType::vector_type vector_type;
191 const DequeType * Deque;
194 const_deque_iterator(
const DequeType * Deque_, size_type Offset_) :
195 Deque(Deque_), Offset(Offset_)
199 typedef typename DequeType::value_type value_type;
200 typedef typename DequeType::pointer pointer;
201 typedef typename DequeType::const_pointer const_pointer;
202 typedef typename DequeType::reference reference;
203 typedef typename DequeType::const_reference const_reference;
204 typedef deque_iterator<DequeType> iterator;
205 typedef const_deque_iterator<DequeType> const_iterator;
206 friend class deque<value_type, vector_type>;
207 friend class deque_iterator<DequeType>;
209 typedef std::random_access_iterator_tag iterator_category;
210 typedef typename DequeType::difference_type difference_type;
212 const_deque_iterator() : Deque(NULL), Offset(0) { }
213 const_deque_iterator(
const deque_iterator<DequeType> & it) :
214 Deque(it.Deque), Offset(it.Offset)
217 difference_type operator - (
const _Self & a)
const
219 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
220 Offset : (Deque->Vector.size() + Offset);
221 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
222 a.Offset : (Deque->Vector.size() + a.Offset);
224 return SelfAbsOffset - aAbsOffset;
227 difference_type operator - (
const iterator & a)
const
229 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
230 Offset : (Deque->Vector.size() + Offset);
231 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
232 a.Offset : (Deque->Vector.size() + a.Offset);
234 return SelfAbsOffset - aAbsOffset;
237 _Self operator - (size_type op)
const
239 return _Self(Deque, (Offset + Deque->Vector.size() - op) % Deque->Vector.size());
242 _Self operator + (size_type op)
const
244 return _Self(Deque, (Offset + op) % Deque->Vector.size());
247 _Self & operator -= (size_type op)
249 Offset = (Offset + Deque->Vector.size() - op) % Deque->Vector.size();
253 _Self & operator += (size_type op)
255 Offset = (Offset + op) % Deque->Vector.size();
259 const_reference operator * ()
const
261 return Deque->Vector[Offset];
264 const_pointer operator -> ()
const
266 return &(Deque->Vector[Offset]);
269 const_reference operator [] (size_type op)
const
271 return Deque->Vector[(Offset + op) % Deque->Vector.size()];
274 _Self & operator ++ ()
276 Offset = (Offset + 1) % Deque->Vector.size();
279 _Self operator ++ (
int)
282 Offset = (Offset + 1) % Deque->Vector.size();
285 _Self & operator -- ()
287 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
290 _Self operator -- (
int)
293 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
296 bool operator == (
const _Self & a)
const
298 assert(Deque == a.Deque);
299 return Offset == a.Offset;
301 bool operator != (
const _Self & a)
const
303 assert(Deque == a.Deque);
304 return Offset != a.Offset;
307 bool operator < (
const _Self & a)
const
309 assert(Deque == a.Deque);
310 return (a - (*
this)) > 0;
313 bool operator == (
const iterator & a)
const
315 assert(Deque == a.Deque);
316 return Offset == a.Offset;
318 bool operator != (
const iterator & a)
const
320 assert(Deque == a.Deque);
321 return Offset != a.Offset;
324 bool operator < (
const iterator & a)
const
326 assert(Deque == a.Deque);
327 return (a - (*
this)) > 0;
343 template <
class T,
class VectorType = stxxl::vector<T> >
349 typedef typename VectorType::size_type size_type;
350 typedef typename VectorType::difference_type difference_type;
351 typedef VectorType vector_type;
352 typedef T value_type;
354 typedef const value_type * const_pointer;
355 typedef T & reference;
356 typedef const T & const_reference;
357 typedef deque_iterator<Self_> iterator;
358 typedef const_deque_iterator<Self_> const_iterator;
360 friend class deque_iterator<Self_>;
361 friend class const_deque_iterator<Self_>;
365 size_type begin_o, end_o, size_;
369 const size_type old_size = Vector.size();
370 Vector.resize(2 * old_size);
373 const size_type new_begin_o = old_size + begin_o;
374 std::copy(Vector.begin() + begin_o,
375 Vector.begin() + old_size,
376 Vector.begin() + new_begin_o);
377 begin_o = new_begin_o;
382 deque() : Vector((STXXL_DEFAULT_BLOCK_SIZE(T)) /
sizeof(T)), begin_o(0), end_o(0), size_(0)
386 : Vector((std::max)((size_type)(STXXL_DEFAULT_BLOCK_SIZE(T)) /
sizeof(T), 2 * n)),
387 begin_o(0), end_o(n), size_(n)
396 return iterator(
this, begin_o);
400 return iterator(
this, end_o);
402 const_iterator begin()
const
404 return const_iterator(
this, begin_o);
406 const_iterator cbegin()
const
410 const_iterator end()
const
412 return const_iterator(
this, end_o);
414 const_iterator cend()
const
419 size_type size()
const
424 size_type max_size()
const
426 return (std::numeric_limits<size_type>::max)() / 2 - 1;
434 reference operator [] (size_type n)
437 return Vector[(begin_o + n) % Vector.size()];
440 const_reference operator [] (size_type n)
const
443 return Vector[(begin_o + n) % Vector.size()];
449 return Vector[begin_o];
452 const_reference front()
const
455 return Vector[begin_o];
461 return Vector[(end_o + Vector.size() - 1) % Vector.size()];
464 const_reference back()
const
467 return Vector[(end_o + Vector.size() - 1) % Vector.size()];
470 void push_front(
const T & el)
472 if ((begin_o + Vector.size() - 1) % Vector.size() == end_o)
478 begin_o = (begin_o + Vector.size() - 1) % Vector.size();
479 Vector[begin_o] = el;
483 void push_back(
const T & el)
485 if ((end_o + 1) % Vector.size() == begin_o)
491 end_o = (end_o + 1) % Vector.size();
498 begin_o = (begin_o + 1) % Vector.size();
505 end_o = (end_o + Vector.size() - 1) % Vector.size();
509 void swap(
deque & obj)
511 std::swap(Vector, obj.Vector);
512 std::swap(begin_o, obj.begin_o);
513 std::swap(end_o, obj.end_o);
514 std::swap(size_, obj.size_);
520 Vector.resize((STXXL_DEFAULT_BLOCK_SIZE(T)) /
sizeof(T));
526 void resize(size_type n)
533 }
while (n < size());
537 if (n + 1 > Vector.size())
539 const size_type old_size = Vector.size();
540 Vector.resize(2 * n);
543 const size_type new_begin_o = Vector.size() - old_size + begin_o;
544 std::copy(Vector.begin() + begin_o,
545 Vector.begin() + old_size,
546 Vector.begin() + new_begin_o);
547 begin_o = new_begin_o;
550 end_o = (end_o + n - size()) % Vector.size();
556 template <
class T,
class VectorType>
559 return std::equal(a.begin(), a.end(), b.begin());
562 template <
class T,
class VectorType>
565 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
570 __STXXL_END_NAMESPACE
574 template <
typename T,
typename VT>
575 void swap(stxxl::deque<T, VT> & a,
576 stxxl::deque<T, VT> & b)