Stxxl 1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/containers/deque.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2006 Roman Dementiev <dementiev@ira.uka.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 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 { // copy data to the new end of the vector 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 { // empty so far 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 // an overflow will occur: resize the array 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 // an overflow will occur: resize the array 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 { // need to resize 00539 const size_type old_size = Vector.size(); 00540 Vector.resize(2 * n); 00541 if (begin_o > end_o) 00542 { // copy data to the new end of the vector 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 /* _STXXL_DEQUE_H */