Stxxl  1.2.1
deque.h
1 /***************************************************************************
2  * include/stxxl/bits/containers/deque.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2006 Roman Dementiev <dementiev@ira.uka.de>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef _STXXL_DEQUE_H
14 #define _STXXL_DEQUE_H
15 
16 #include <stxxl/vector>
17 
18 
19 __STXXL_BEGIN_NAMESPACE
20 
21 template <class T, class VectorType>
22 class deque;
23 
24 template <class DequeType>
25 class const_deque_iterator;
26 
27 template <class DequeType>
28 class deque_iterator
29 {
30  typedef typename DequeType::size_type size_type;
31  typedef typename DequeType::vector_type vector_type;
32  typedef deque_iterator<DequeType> _Self;
33  DequeType * Deque;
34  size_type Offset;
35 
36  deque_iterator(DequeType * Deque_, size_type Offset_) :
37  Deque(Deque_), Offset(Offset_)
38  { }
39 
40  friend class const_deque_iterator<DequeType>;
41 
42 public:
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;
53 
54  deque_iterator() : Deque(NULL), Offset(0) { }
55 
56  difference_type operator - (const _Self & a) const
57  {
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);
62 
63  return SelfAbsOffset - aAbsOffset;
64  }
65 
66  difference_type operator - (const const_iterator & a) const
67  {
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);
72 
73  return SelfAbsOffset - aAbsOffset;
74  }
75 
76  _Self operator - (size_type op) const
77  {
78  return _Self(Deque, (Offset + Deque->Vector.size() - op) % Deque->Vector.size());
79  }
80 
81  _Self operator + (size_type op) const
82  {
83  return _Self(Deque, (Offset + op) % Deque->Vector.size());
84  }
85 
86  _Self & operator -= (size_type op)
87  {
88  Offset = (Offset + Deque->Vector.size() - op) % Deque->Vector.size();
89  return *this;
90  }
91 
92  _Self & operator += (size_type op)
93  {
94  Offset = (Offset + op) % Deque->Vector.size();
95  return *this;
96  }
97 
98  reference operator * ()
99  {
100  return Deque->Vector[Offset];
101  }
102 
103  pointer operator -> ()
104  {
105  return &(Deque->Vector[Offset]);
106  }
107 
108  const_reference operator * () const
109  {
110  return Deque->Vector[Offset];
111  }
112 
113  const_pointer operator -> () const
114  {
115  return &(Deque->Vector[Offset]);
116  }
117 
118  reference operator [] (size_type op)
119  {
120  return Deque->Vector[(Offset + op) % Deque->Vector.size()];
121  }
122 
123  const_reference operator [] (size_type op) const
124  {
125  return Deque->Vector[(Offset + op) % Deque->Vector.size()];
126  }
127 
128  _Self & operator ++ ()
129  {
130  Offset = (Offset + 1) % Deque->Vector.size();
131  return *this;
132  }
133  _Self operator ++ (int)
134  {
135  _Self __tmp = *this;
136  Offset = (Offset + 1) % Deque->Vector.size();
137  return __tmp;
138  }
139  _Self & operator -- ()
140  {
141  Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
142  return *this;
143  }
144  _Self operator -- (int)
145  {
146  _Self __tmp = *this;
147  Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
148  return __tmp;
149  }
150  bool operator == (const _Self & a) const
151  {
152  assert(Deque == a.Deque);
153  return Offset == a.Offset;
154  }
155  bool operator != (const _Self & a) const
156  {
157  assert(Deque == a.Deque);
158  return Offset != a.Offset;
159  }
160 
161  bool operator < (const _Self & a) const
162  {
163  assert(Deque == a.Deque);
164  return (a - (*this)) > 0;
165  }
166 
167  bool operator == (const const_iterator & a) const
168  {
169  assert(Deque == a.Deque);
170  return Offset == a.Offset;
171  }
172  bool operator != (const const_iterator & a) const
173  {
174  assert(Deque == a.Deque);
175  return Offset != a.Offset;
176  }
177 
178  bool operator < (const const_iterator & a) const
179  {
180  assert(Deque == a.Deque);
181  return (a - (*this)) > 0;
182  }
183 };
184 
185 template <class DequeType>
186 class const_deque_iterator
187 {
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;
192  size_type Offset;
193 
194  const_deque_iterator(const DequeType * Deque_, size_type Offset_) :
195  Deque(Deque_), Offset(Offset_)
196  { }
197 
198 public:
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>;
208 
209  typedef std::random_access_iterator_tag iterator_category;
210  typedef typename DequeType::difference_type difference_type;
211 
212  const_deque_iterator() : Deque(NULL), Offset(0) { }
213  const_deque_iterator(const deque_iterator<DequeType> & it) :
214  Deque(it.Deque), Offset(it.Offset)
215  { }
216 
217  difference_type operator - (const _Self & a) const
218  {
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);
223 
224  return SelfAbsOffset - aAbsOffset;
225  }
226 
227  difference_type operator - (const iterator & a) const
228  {
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);
233 
234  return SelfAbsOffset - aAbsOffset;
235  }
236 
237  _Self operator - (size_type op) const
238  {
239  return _Self(Deque, (Offset + Deque->Vector.size() - op) % Deque->Vector.size());
240  }
241 
242  _Self operator + (size_type op) const
243  {
244  return _Self(Deque, (Offset + op) % Deque->Vector.size());
245  }
246 
247  _Self & operator -= (size_type op)
248  {
249  Offset = (Offset + Deque->Vector.size() - op) % Deque->Vector.size();
250  return *this;
251  }
252 
253  _Self & operator += (size_type op)
254  {
255  Offset = (Offset + op) % Deque->Vector.size();
256  return *this;
257  }
258 
259  const_reference operator * () const
260  {
261  return Deque->Vector[Offset];
262  }
263 
264  const_pointer operator -> () const
265  {
266  return &(Deque->Vector[Offset]);
267  }
268 
269  const_reference operator [] (size_type op) const
270  {
271  return Deque->Vector[(Offset + op) % Deque->Vector.size()];
272  }
273 
274  _Self & operator ++ ()
275  {
276  Offset = (Offset + 1) % Deque->Vector.size();
277  return *this;
278  }
279  _Self operator ++ (int)
280  {
281  _Self __tmp = *this;
282  Offset = (Offset + 1) % Deque->Vector.size();
283  return __tmp;
284  }
285  _Self & operator -- ()
286  {
287  Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
288  return *this;
289  }
290  _Self operator -- (int)
291  {
292  _Self __tmp = *this;
293  Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
294  return __tmp;
295  }
296  bool operator == (const _Self & a) const
297  {
298  assert(Deque == a.Deque);
299  return Offset == a.Offset;
300  }
301  bool operator != (const _Self & a) const
302  {
303  assert(Deque == a.Deque);
304  return Offset != a.Offset;
305  }
306 
307  bool operator < (const _Self & a) const
308  {
309  assert(Deque == a.Deque);
310  return (a - (*this)) > 0;
311  }
312 
313  bool operator == (const iterator & a) const
314  {
315  assert(Deque == a.Deque);
316  return Offset == a.Offset;
317  }
318  bool operator != (const iterator & a) const
319  {
320  assert(Deque == a.Deque);
321  return Offset != a.Offset;
322  }
323 
324  bool operator < (const iterator & a) const
325  {
326  assert(Deque == a.Deque);
327  return (a - (*this)) > 0;
328  }
329 };
330 
333 
343 template <class T, class VectorType = stxxl::vector<T> >
344 class deque : private noncopyable
345 {
346  typedef deque<T, VectorType> Self_;
347 
348 public:
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;
353  typedef T * pointer;
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;
359 
360  friend class deque_iterator<Self_>;
361  friend class const_deque_iterator<Self_>;
362 
363 private:
364  VectorType Vector;
365  size_type begin_o, end_o, size_;
366 
367  void double_array()
368  {
369  const size_type old_size = Vector.size();
370  Vector.resize(2 * old_size);
371  if (begin_o > end_o)
372  { // copy data to the new end of the vector
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;
378  }
379  }
380 
381 public:
382  deque() : Vector((STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(T)), begin_o(0), end_o(0), size_(0)
383  { }
384 
385  deque(size_type n)
386  : Vector((std::max)((size_type)(STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(T), 2 * n)),
387  begin_o(0), end_o(n), size_(n)
388  { }
389 
390  ~deque()
391  { // empty so far
392  }
393 
394  iterator begin()
395  {
396  return iterator(this, begin_o);
397  }
398  iterator end()
399  {
400  return iterator(this, end_o);
401  }
402  const_iterator begin() const
403  {
404  return const_iterator(this, begin_o);
405  }
406  const_iterator cbegin() const
407  {
408  return begin();
409  }
410  const_iterator end() const
411  {
412  return const_iterator(this, end_o);
413  }
414  const_iterator cend() const
415  {
416  return end();
417  }
418 
419  size_type size() const
420  {
421  return size_;
422  }
423 
424  size_type max_size() const
425  {
426  return (std::numeric_limits<size_type>::max)() / 2 - 1;
427  }
428 
429  bool empty() const
430  {
431  return size_ == 0;
432  }
433 
434  reference operator [] (size_type n)
435  {
436  assert(n < size());
437  return Vector[(begin_o + n) % Vector.size()];
438  }
439 
440  const_reference operator [] (size_type n) const
441  {
442  assert(n < size());
443  return Vector[(begin_o + n) % Vector.size()];
444  }
445 
446  reference front()
447  {
448  assert(!empty());
449  return Vector[begin_o];
450  }
451 
452  const_reference front() const
453  {
454  assert(!empty());
455  return Vector[begin_o];
456  }
457 
458  reference back()
459  {
460  assert(!empty());
461  return Vector[(end_o + Vector.size() - 1) % Vector.size()];
462  }
463 
464  const_reference back() const
465  {
466  assert(!empty());
467  return Vector[(end_o + Vector.size() - 1) % Vector.size()];
468  }
469 
470  void push_front(const T & el)
471  {
472  if ((begin_o + Vector.size() - 1) % Vector.size() == end_o)
473  {
474  // an overflow will occur: resize the array
475  double_array();
476  }
477 
478  begin_o = (begin_o + Vector.size() - 1) % Vector.size();
479  Vector[begin_o] = el;
480  ++size_;
481  }
482 
483  void push_back(const T & el)
484  {
485  if ((end_o + 1) % Vector.size() == begin_o)
486  {
487  // an overflow will occur: resize the array
488  double_array();
489  }
490  Vector[end_o] = el;
491  end_o = (end_o + 1) % Vector.size();
492  ++size_;
493  }
494 
495  void pop_front()
496  {
497  assert(!empty());
498  begin_o = (begin_o + 1) % Vector.size();
499  --size_;
500  }
501 
502  void pop_back()
503  {
504  assert(!empty());
505  end_o = (end_o + Vector.size() - 1) % Vector.size();
506  --size_;
507  }
508 
509  void swap(deque & obj)
510  {
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_);
515  }
516 
517  void clear()
518  {
519  Vector.clear();
520  Vector.resize((STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(T));
521  begin_o = 0;
522  end_o = 0;
523  size_ = 0;
524  }
525 
526  void resize(size_type n)
527  {
528  if (n < size())
529  {
530  do
531  {
532  pop_back();
533  } while (n < size());
534  }
535  else
536  {
537  if (n + 1 > Vector.size())
538  { // need to resize
539  const size_type old_size = Vector.size();
540  Vector.resize(2 * n);
541  if (begin_o > end_o)
542  { // copy data to the new end of the vector
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;
548  }
549  }
550  end_o = (end_o + n - size()) % Vector.size();
551  size_ = n;
552  }
553  }
554 };
555 
556 template <class T, class VectorType>
557 bool operator == (const deque<T, VectorType> & a, const deque<T, VectorType> & b)
558 {
559  return std::equal(a.begin(), a.end(), b.begin());
560 }
561 
562 template <class T, class VectorType>
563 bool operator < (const deque<T, VectorType> & a, const deque<T, VectorType> & b)
564 {
565  return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
566 }
567 
569 
570 __STXXL_END_NAMESPACE
571 
572 namespace std
573 {
574  template <typename T, typename VT>
575  void swap(stxxl::deque<T, VT> & a,
576  stxxl::deque<T, VT> & b)
577  {
578  a.swap(b);
579  }
580 }
581 
582 #endif /* _STXXL_DEQUE_H */