00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef _STXXL_DEQUE_H
00014 #define _STXXL_DEQUE_H
00015
00016 #include <stxxl/vector>
00017
00018
00019 __STXXL_BEGIN_NAMESPACE
00020
00021 template <class T, class VectorType>
00022 class deque;
00023
00024 template <class DequeType>
00025 class const_deque_iterator;
00026
00027 template <class DequeType>
00028 class deque_iterator
00029 {
00030 typedef typename DequeType::size_type size_type;
00031 typedef typename DequeType::vector_type vector_type;
00032 typedef deque_iterator<DequeType> _Self;
00033 DequeType * Deque;
00034 size_type Offset;
00035
00036 deque_iterator(DequeType * Deque_, size_type Offset_) :
00037 Deque(Deque_), Offset(Offset_)
00038 { }
00039
00040 friend class const_deque_iterator<DequeType>;
00041
00042 public:
00043 typedef typename DequeType::value_type value_type;
00044 typedef typename DequeType::pointer pointer;
00045 typedef typename DequeType::const_pointer const_pointer;
00046 typedef typename DequeType::reference reference;
00047 typedef typename DequeType::const_reference const_reference;
00048 typedef deque_iterator<DequeType> iterator;
00049 typedef const_deque_iterator<DequeType> const_iterator;
00050 friend class deque<value_type, vector_type>;
00051 typedef std::random_access_iterator_tag iterator_category;
00052 typedef typename DequeType::difference_type difference_type;
00053
00054 deque_iterator() : Deque(NULL), Offset(0) { }
00055
00056 difference_type operator - (const _Self & a) const
00057 {
00058 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
00059 Offset : (Deque->Vector.size() + Offset);
00060 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
00061 a.Offset : (Deque->Vector.size() + a.Offset);
00062
00063 return SelfAbsOffset - aAbsOffset;
00064 }
00065
00066 difference_type operator - (const const_iterator & a) const
00067 {
00068 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
00069 Offset : (Deque->Vector.size() + Offset);
00070 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
00071 a.Offset : (Deque->Vector.size() + a.Offset);
00072
00073 return SelfAbsOffset - aAbsOffset;
00074 }
00075
00076 _Self operator - (size_type op) const
00077 {
00078 return _Self(Deque, (Offset + Deque->Vector.size() - op) % Deque->Vector.size());
00079 }
00080
00081 _Self operator + (size_type op) const
00082 {
00083 return _Self(Deque, (Offset + op) % Deque->Vector.size());
00084 }
00085
00086 _Self & operator -= (size_type op)
00087 {
00088 Offset = (Offset + Deque->Vector.size() - op) % Deque->Vector.size();
00089 return *this;
00090 }
00091
00092 _Self & operator += (size_type op)
00093 {
00094 Offset = (Offset + op) % Deque->Vector.size();
00095 return *this;
00096 }
00097
00098 reference operator * ()
00099 {
00100 return Deque->Vector[Offset];
00101 }
00102
00103 pointer operator -> ()
00104 {
00105 return &(Deque->Vector[Offset]);
00106 }
00107
00108 const_reference operator * () const
00109 {
00110 return Deque->Vector[Offset];
00111 }
00112
00113 const_pointer operator -> () const
00114 {
00115 return &(Deque->Vector[Offset]);
00116 }
00117
00118 reference operator [] (size_type op)
00119 {
00120 return Deque->Vector[(Offset + op) % Deque->Vector.size()];
00121 }
00122
00123 const_reference operator [] (size_type op) const
00124 {
00125 return Deque->Vector[(Offset + op) % Deque->Vector.size()];
00126 }
00127
00128 _Self & operator ++ ()
00129 {
00130 Offset = (Offset + 1) % Deque->Vector.size();
00131 return *this;
00132 }
00133 _Self operator ++ (int)
00134 {
00135 _Self __tmp = *this;
00136 Offset = (Offset + 1) % Deque->Vector.size();
00137 return __tmp;
00138 }
00139 _Self & operator -- ()
00140 {
00141 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
00142 return *this;
00143 }
00144 _Self operator -- (int)
00145 {
00146 _Self __tmp = *this;
00147 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
00148 return __tmp;
00149 }
00150 bool operator == (const _Self & a) const
00151 {
00152 assert(Deque == a.Deque);
00153 return Offset == a.Offset;
00154 }
00155 bool operator != (const _Self & a) const
00156 {
00157 assert(Deque == a.Deque);
00158 return Offset != a.Offset;
00159 }
00160
00161 bool operator < (const _Self & a) const
00162 {
00163 assert(Deque == a.Deque);
00164 return (a - (*this)) > 0;
00165 }
00166
00167 bool operator == (const const_iterator & a) const
00168 {
00169 assert(Deque == a.Deque);
00170 return Offset == a.Offset;
00171 }
00172 bool operator != (const const_iterator & a) const
00173 {
00174 assert(Deque == a.Deque);
00175 return Offset != a.Offset;
00176 }
00177
00178 bool operator < (const const_iterator & a) const
00179 {
00180 assert(Deque == a.Deque);
00181 return (a - (*this)) > 0;
00182 }
00183 };
00184
00185 template <class DequeType>
00186 class const_deque_iterator
00187 {
00188 typedef const_deque_iterator<DequeType> _Self;
00189 typedef typename DequeType::size_type size_type;
00190 typedef typename DequeType::vector_type vector_type;
00191 const DequeType * Deque;
00192 size_type Offset;
00193
00194 const_deque_iterator(const DequeType * Deque_, size_type Offset_) :
00195 Deque(Deque_), Offset(Offset_)
00196 { }
00197
00198 public:
00199 typedef typename DequeType::value_type value_type;
00200 typedef typename DequeType::pointer pointer;
00201 typedef typename DequeType::const_pointer const_pointer;
00202 typedef typename DequeType::reference reference;
00203 typedef typename DequeType::const_reference const_reference;
00204 typedef deque_iterator<DequeType> iterator;
00205 typedef const_deque_iterator<DequeType> const_iterator;
00206 friend class deque<value_type, vector_type>;
00207 friend class deque_iterator<DequeType>;
00208
00209 typedef std::random_access_iterator_tag iterator_category;
00210 typedef typename DequeType::difference_type difference_type;
00211
00212 const_deque_iterator() : Deque(NULL), Offset(0) { }
00213 const_deque_iterator(const deque_iterator<DequeType> & it) :
00214 Deque(it.Deque), Offset(it.Offset)
00215 { }
00216
00217 difference_type operator - (const _Self & a) const
00218 {
00219 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
00220 Offset : (Deque->Vector.size() + Offset);
00221 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
00222 a.Offset : (Deque->Vector.size() + a.Offset);
00223
00224 return SelfAbsOffset - aAbsOffset;
00225 }
00226
00227 difference_type operator - (const iterator & a) const
00228 {
00229 size_type SelfAbsOffset = (Offset >= Deque->begin_o) ?
00230 Offset : (Deque->Vector.size() + Offset);
00231 size_type aAbsOffset = (a.Offset >= Deque->begin_o) ?
00232 a.Offset : (Deque->Vector.size() + a.Offset);
00233
00234 return SelfAbsOffset - aAbsOffset;
00235 }
00236
00237 _Self operator - (size_type op) const
00238 {
00239 return _Self(Deque, (Offset + Deque->Vector.size() - op) % Deque->Vector.size());
00240 }
00241
00242 _Self operator + (size_type op) const
00243 {
00244 return _Self(Deque, (Offset + op) % Deque->Vector.size());
00245 }
00246
00247 _Self & operator -= (size_type op)
00248 {
00249 Offset = (Offset + Deque->Vector.size() - op) % Deque->Vector.size();
00250 return *this;
00251 }
00252
00253 _Self & operator += (size_type op)
00254 {
00255 Offset = (Offset + op) % Deque->Vector.size();
00256 return *this;
00257 }
00258
00259 const_reference operator * () const
00260 {
00261 return Deque->Vector[Offset];
00262 }
00263
00264 const_pointer operator -> () const
00265 {
00266 return &(Deque->Vector[Offset]);
00267 }
00268
00269 const_reference operator [] (size_type op) const
00270 {
00271 return Deque->Vector[(Offset + op) % Deque->Vector.size()];
00272 }
00273
00274 _Self & operator ++ ()
00275 {
00276 Offset = (Offset + 1) % Deque->Vector.size();
00277 return *this;
00278 }
00279 _Self operator ++ (int)
00280 {
00281 _Self __tmp = *this;
00282 Offset = (Offset + 1) % Deque->Vector.size();
00283 return __tmp;
00284 }
00285 _Self & operator -- ()
00286 {
00287 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
00288 return *this;
00289 }
00290 _Self operator -- (int)
00291 {
00292 _Self __tmp = *this;
00293 Offset = (Offset + Deque->Vector.size() - 1) % Deque->Vector.size();
00294 return __tmp;
00295 }
00296 bool operator == (const _Self & a) const
00297 {
00298 assert(Deque == a.Deque);
00299 return Offset == a.Offset;
00300 }
00301 bool operator != (const _Self & a) const
00302 {
00303 assert(Deque == a.Deque);
00304 return Offset != a.Offset;
00305 }
00306
00307 bool operator < (const _Self & a) const
00308 {
00309 assert(Deque == a.Deque);
00310 return (a - (*this)) > 0;
00311 }
00312
00313 bool operator == (const iterator & a) const
00314 {
00315 assert(Deque == a.Deque);
00316 return Offset == a.Offset;
00317 }
00318 bool operator != (const iterator & a) const
00319 {
00320 assert(Deque == a.Deque);
00321 return Offset != a.Offset;
00322 }
00323
00324 bool operator < (const iterator & a) const
00325 {
00326 assert(Deque == a.Deque);
00327 return (a - (*this)) > 0;
00328 }
00329 };
00330
00333
00343 template <class T, class VectorType = stxxl::vector<T> >
00344 class deque : private noncopyable
00345 {
00346 typedef deque<T, VectorType> Self_;
00347
00348 public:
00349 typedef typename VectorType::size_type size_type;
00350 typedef typename VectorType::difference_type difference_type;
00351 typedef VectorType vector_type;
00352 typedef T value_type;
00353 typedef T * pointer;
00354 typedef const value_type * const_pointer;
00355 typedef T & reference;
00356 typedef const T & const_reference;
00357 typedef deque_iterator<Self_> iterator;
00358 typedef const_deque_iterator<Self_> const_iterator;
00359
00360 friend class deque_iterator<Self_>;
00361 friend class const_deque_iterator<Self_>;
00362
00363 private:
00364 VectorType Vector;
00365 size_type begin_o, end_o, size_;
00366
00367 void double_array()
00368 {
00369 const size_type old_size = Vector.size();
00370 Vector.resize(2 * old_size);
00371 if (begin_o > end_o)
00372 {
00373 const size_type new_begin_o = old_size + begin_o;
00374 std::copy(Vector.begin() + begin_o,
00375 Vector.begin() + old_size,
00376 Vector.begin() + new_begin_o);
00377 begin_o = new_begin_o;
00378 }
00379 }
00380
00381 public:
00382 deque() : Vector((STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(T)), begin_o(0), end_o(0), size_(0)
00383 { }
00384
00385 deque(size_type n)
00386 : Vector((std::max)((size_type)(STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(T), 2 * n)),
00387 begin_o(0), end_o(n), size_(n)
00388 { }
00389
00390 ~deque()
00391 {
00392 }
00393
00394 iterator begin()
00395 {
00396 return iterator(this, begin_o);
00397 }
00398 iterator end()
00399 {
00400 return iterator(this, end_o);
00401 }
00402 const_iterator begin() const
00403 {
00404 return const_iterator(this, begin_o);
00405 }
00406 const_iterator cbegin() const
00407 {
00408 return begin();
00409 }
00410 const_iterator end() const
00411 {
00412 return const_iterator(this, end_o);
00413 }
00414 const_iterator cend() const
00415 {
00416 return end();
00417 }
00418
00419 size_type size() const
00420 {
00421 return size_;
00422 }
00423
00424 size_type max_size() const
00425 {
00426 return (std::numeric_limits<size_type>::max)() / 2 - 1;
00427 }
00428
00429 bool empty() const
00430 {
00431 return size_ == 0;
00432 }
00433
00434 reference operator [] (size_type n)
00435 {
00436 assert(n < size());
00437 return Vector[(begin_o + n) % Vector.size()];
00438 }
00439
00440 const_reference operator [] (size_type n) const
00441 {
00442 assert(n < size());
00443 return Vector[(begin_o + n) % Vector.size()];
00444 }
00445
00446 reference front()
00447 {
00448 assert(!empty());
00449 return Vector[begin_o];
00450 }
00451
00452 const_reference front() const
00453 {
00454 assert(!empty());
00455 return Vector[begin_o];
00456 }
00457
00458 reference back()
00459 {
00460 assert(!empty());
00461 return Vector[(end_o + Vector.size() - 1) % Vector.size()];
00462 }
00463
00464 const_reference back() const
00465 {
00466 assert(!empty());
00467 return Vector[(end_o + Vector.size() - 1) % Vector.size()];
00468 }
00469
00470 void push_front(const T & el)
00471 {
00472 if ((begin_o + Vector.size() - 1) % Vector.size() == end_o)
00473 {
00474
00475 double_array();
00476 }
00477
00478 begin_o = (begin_o + Vector.size() - 1) % Vector.size();
00479 Vector[begin_o] = el;
00480 ++size_;
00481 }
00482
00483 void push_back(const T & el)
00484 {
00485 if ((end_o + 1) % Vector.size() == begin_o)
00486 {
00487
00488 double_array();
00489 }
00490 Vector[end_o] = el;
00491 end_o = (end_o + 1) % Vector.size();
00492 ++size_;
00493 }
00494
00495 void pop_front()
00496 {
00497 assert(!empty());
00498 begin_o = (begin_o + 1) % Vector.size();
00499 --size_;
00500 }
00501
00502 void pop_back()
00503 {
00504 assert(!empty());
00505 end_o = (end_o + Vector.size() - 1) % Vector.size();
00506 --size_;
00507 }
00508
00509 void swap(deque & obj)
00510 {
00511 std::swap(Vector, obj.Vector);
00512 std::swap(begin_o, obj.begin_o);
00513 std::swap(end_o, obj.end_o);
00514 std::swap(size_, obj.size_);
00515 }
00516
00517 void clear()
00518 {
00519 Vector.clear();
00520 Vector.resize((STXXL_DEFAULT_BLOCK_SIZE(T)) / sizeof(T));
00521 begin_o = 0;
00522 end_o = 0;
00523 size_ = 0;
00524 }
00525
00526 void resize(size_type n)
00527 {
00528 if (n < size())
00529 {
00530 do
00531 {
00532 pop_back();
00533 } while (n < size());
00534 }
00535 else
00536 {
00537 if (n + 1 > Vector.size())
00538 {
00539 const size_type old_size = Vector.size();
00540 Vector.resize(2 * n);
00541 if (begin_o > end_o)
00542 {
00543 const size_type new_begin_o = Vector.size() - old_size + begin_o;
00544 std::copy(Vector.begin() + begin_o,
00545 Vector.begin() + old_size,
00546 Vector.begin() + new_begin_o);
00547 begin_o = new_begin_o;
00548 }
00549 }
00550 end_o = (end_o + n - size()) % Vector.size();
00551 size_ = n;
00552 }
00553 }
00554 };
00555
00556 template <class T, class VectorType>
00557 bool operator == (const deque<T, VectorType> & a, const deque<T, VectorType> & b)
00558 {
00559 return std::equal(a.begin(), a.end(), b.begin());
00560 }
00561
00562 template <class T, class VectorType>
00563 bool operator < (const deque<T, VectorType> & a, const deque<T, VectorType> & b)
00564 {
00565 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
00566 }
00567
00569
00570 __STXXL_END_NAMESPACE
00571
00572 namespace std
00573 {
00574 template <typename T, typename VT>
00575 void swap(stxxl::deque<T, VT> & a,
00576 stxxl::deque<T, VT> & b)
00577 {
00578 a.swap(b);
00579 }
00580 }
00581
00582 #endif