00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #ifndef STXXL_MNG_ADAPTOR_HEADER
00016 #define STXXL_MNG_ADAPTOR_HEADER
00017
00018 #include <iterator>
00019
00020 #include <stxxl/bits/common/types.h>
00021
00022
00023 __STXXL_BEGIN_NAMESPACE
00024
00028
00029
00030 template <unsigned_type modulo>
00031 class blocked_index
00032 {
00033 unsigned_type pos;
00034 unsigned_type block;
00035 unsigned_type offset;
00036
00038
00039 void set(unsigned_type pos)
00040 {
00041 this->pos = pos;
00042 block = pos / modulo;
00043 offset = pos % modulo;
00044 }
00045
00046 public:
00047 blocked_index()
00048 {
00049 set(0);
00050 }
00051
00052 blocked_index(unsigned_type pos)
00053 {
00054 set(pos);
00055 }
00056
00057 blocked_index(unsigned_type block, unsigned_type offset)
00058 {
00059 this->block = block;
00060 this->offset = offset;
00061 pos = block * modulo + offset;
00062 }
00063
00064 void operator = (unsigned_type pos)
00065 {
00066 set(pos);
00067 }
00068
00069
00070 blocked_index & operator ++ ()
00071 {
00072 ++pos;
00073 ++offset;
00074 if (offset == modulo)
00075 {
00076 offset = 0;
00077 ++block;
00078 }
00079 return *this;
00080 }
00081
00082
00083 blocked_index operator ++ (int)
00084 {
00085 blocked_index former(*this);
00086 operator ++ ();
00087 return former;
00088 }
00089
00090
00091 blocked_index & operator -- ()
00092 {
00093 --pos;
00094 if (offset == 0)
00095 {
00096 offset = modulo;
00097 --block;
00098 }
00099 --offset;
00100 return *this;
00101 }
00102
00103
00104 blocked_index operator -- (int)
00105 {
00106 blocked_index former(*this);
00107 operator -- ();
00108 return former;
00109 }
00110
00111 blocked_index & operator += (unsigned_type addend)
00112 {
00113 set(pos + addend);
00114 return *this;
00115 }
00116
00117 blocked_index & operator >>= (unsigned_type shift)
00118 {
00119 set(pos >> shift);
00120 return *this;
00121 }
00122
00123 operator unsigned_type () const
00124 {
00125 return pos;
00126 }
00127
00128 const unsigned_type & get_block() const
00129 {
00130 return block;
00131 }
00132
00133 const unsigned_type & get_offset() const
00134 {
00135 return offset;
00136 }
00137 };
00138
00139 #define STXXL_ADAPTOR_ARITHMETICS(pos) \
00140 bool operator == (const _Self & a) const \
00141 { \
00142 return (a.pos == pos); \
00143 } \
00144 bool operator != (const _Self & a) const \
00145 { \
00146 return (a.pos != pos); \
00147 } \
00148 bool operator < (const _Self & a) const \
00149 { \
00150 return (pos < a.pos); \
00151 } \
00152 bool operator > (const _Self & a) const \
00153 { \
00154 return (pos > a.pos); \
00155 } \
00156 bool operator <= (const _Self & a) const \
00157 { \
00158 return (pos <= a.pos); \
00159 } \
00160 bool operator >= (const _Self & a) const \
00161 { \
00162 return (pos >= a.pos); \
00163 } \
00164 _Self operator + (pos_type off) const \
00165 { \
00166 return _Self(array, pos + off); \
00167 } \
00168 _Self operator - (pos_type off) const \
00169 { \
00170 return _Self(array, pos - off); \
00171 } \
00172 _Self & operator ++ () \
00173 { \
00174 pos++; \
00175 return *this; \
00176 } \
00177 _Self operator ++ (int) \
00178 { \
00179 _Self tmp = *this; \
00180 pos++; \
00181 return tmp; \
00182 } \
00183 _Self & operator -- () \
00184 { \
00185 pos--; \
00186 return *this; \
00187 } \
00188 _Self operator -- (int) \
00189 { \
00190 _Self tmp = *this; \
00191 pos--; \
00192 return tmp; \
00193 } \
00194 pos_type operator - (const _Self & a) const \
00195 { \
00196 return pos - a.pos; \
00197 } \
00198 _Self & operator -= (pos_type off) \
00199 { \
00200 pos -= off; \
00201 return *this; \
00202 } \
00203 _Self & operator += (pos_type off) \
00204 { \
00205 pos += off; \
00206 return *this; \
00207 }
00208
00209 template <class one_dim_array_type, class data_type, class pos_type>
00210 struct TwoToOneDimArrayAdaptorBase
00211 : public std::iterator<std::random_access_iterator_tag, data_type, unsigned_type>
00212 {
00213 one_dim_array_type * array;
00214 pos_type pos;
00215 typedef pos_type _pos_type;
00216 typedef TwoToOneDimArrayAdaptorBase<one_dim_array_type,
00217 data_type, pos_type> _Self;
00218
00219
00220 TwoToOneDimArrayAdaptorBase()
00221 { }
00222
00223 TwoToOneDimArrayAdaptorBase(one_dim_array_type * a, pos_type p)
00224 : array(a), pos(p)
00225 { }
00226 TwoToOneDimArrayAdaptorBase(const TwoToOneDimArrayAdaptorBase & a)
00227 : array(a.array), pos(a.pos)
00228 { }
00229
00230 STXXL_ADAPTOR_ARITHMETICS(pos)
00231 };
00232
00233
00235
00236 #define BLOCK_ADAPTOR_OPERATORS(two_to_one_dim_array_adaptor_base) \
00237 \
00238 template <unsigned _blk_sz, typename _run_type, class __pos_type> \
00239 inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & operator ++ ( \
00240 two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a) \
00241 { \
00242 a.pos++; \
00243 return a; \
00244 } \
00245 \
00246 template <unsigned _blk_sz, typename _run_type, class __pos_type> \
00247 inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> operator ++ ( \
00248 two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, int) \
00249 { \
00250 two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> tmp = a; \
00251 a.pos++; \
00252 return tmp; \
00253 } \
00254 \
00255 template <unsigned _blk_sz, typename _run_type, class __pos_type> \
00256 inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & operator -- ( \
00257 two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a) \
00258 { \
00259 a.pos--; \
00260 return a; \
00261 } \
00262 \
00263 template <unsigned _blk_sz, typename _run_type, class __pos_type> \
00264 inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> operator -- ( \
00265 two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, int) \
00266 { \
00267 two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> tmp = a; \
00268 a.pos--; \
00269 return tmp; \
00270 } \
00271 \
00272 template <unsigned _blk_sz, typename _run_type, class __pos_type> \
00273 inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & operator -= ( \
00274 two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, \
00275 typename two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>::_pos_type off) \
00276 { \
00277 a.pos -= off; \
00278 return a; \
00279 } \
00280 \
00281 template <unsigned _blk_sz, typename _run_type, class __pos_type> \
00282 inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & operator += ( \
00283 two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, \
00284 typename two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>::_pos_type off) \
00285 { \
00286 a.pos += off; \
00287 return a; \
00288 } \
00289 \
00290 template <unsigned _blk_sz, typename _run_type, class __pos_type> \
00291 inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> operator + ( \
00292 const two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, \
00293 typename two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>::_pos_type off) \
00294 { \
00295 return two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>(a.array, a.pos + off); \
00296 } \
00297 \
00298 template <unsigned _blk_sz, typename _run_type, class __pos_type> \
00299 inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> operator + ( \
00300 typename two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>::_pos_type off, \
00301 const two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a) \
00302 { \
00303 return two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>(a.array, a.pos + off); \
00304 } \
00305 \
00306 template <unsigned _blk_sz, typename _run_type, class __pos_type> \
00307 inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> operator - ( \
00308 const two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, \
00309 typename two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>::_pos_type off) \
00310 { \
00311 return two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>(a.array, a.pos - off); \
00312 }
00313
00314
00315 #if 0
00316
00317 template <class one_dim_array_type, class data_type,
00318 unsigned dim_size, class pos_type = blocked_index<dim_size> >
00319 struct TwoToOneDimArrayRowAdaptor :
00320 public TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>
00321 {
00322 typedef TwoToOneDimArrayRowAdaptor<one_dim_array_type,
00323 data_type, dim_size, pos_type> _Self;
00324
00325 typedef TwoToOneDimArrayAdaptorBase<one_dim_array_type,
00326 data_type, pos_type> _Parent;
00327 using _Parent::array;
00328 using _Parent::pos;
00329
00330 TwoToOneDimArrayRowAdaptor()
00331 { }
00332 TwoToOneDimArrayRowAdaptor(one_dim_array_type * a, pos_type p)
00333 : TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>(a, p)
00334 { }
00335 TwoToOneDimArrayRowAdaptor(const TwoToOneDimArrayRowAdaptor & a)
00336 : TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>(a)
00337 { }
00338
00339 data_type & operator * ()
00340 {
00341 return array[(pos).get_block()][(pos).get_offset()];
00342 }
00343
00344 data_type * operator -> () const
00345 {
00346 return &(array[(pos).get_block()][(pos).get_offset()]);
00347 }
00348
00349 data_type & operator [] (pos_type n)
00350 {
00351 n += pos;
00352 return array[(n) / dim_size][(n) % dim_size];
00353 }
00354
00355 const data_type & operator [] (pos_type n) const
00356 {
00357 n += pos;
00358 return array[(n) / dim_size][(n) % dim_size];
00359 }
00360 STXXL_ADAPTOR_ARITHMETICS(pos)
00361 };
00362
00363 template <class one_dim_array_type, class data_type,
00364 unsigned dim_size, class pos_type = blocked_index<dim_size> >
00365 struct TwoToOneDimArrayColumnAdaptor
00366 : public TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>
00367 {
00368 typedef TwoToOneDimArrayColumnAdaptor<one_dim_array_type,
00369 data_type, dim_size, pos_type> _Self;
00370
00371 using TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>::pos;
00372 using TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>::array;
00373
00374 TwoToOneDimArrayColumnAdaptor(one_dim_array_type * a, pos_type p)
00375 : TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>(a, p)
00376 { }
00377 TwoToOneDimArrayColumnAdaptor(const _Self & a)
00378 : TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>(a)
00379 { }
00380
00381 data_type & operator * ()
00382 {
00383 return array[(pos).get_offset()][(pos).get_block()];
00384 }
00385
00386 data_type * operator -> () const
00387 {
00388 return &(array[(pos).get_offset()][(pos).get_block()]);
00389 }
00390
00391 const data_type & operator [] (pos_type n) const
00392 {
00393 n += pos;
00394 return array[(n) % dim_size][(n) / dim_size];
00395 }
00396
00397 data_type & operator [] (pos_type n)
00398 {
00399 n += pos;
00400 return array[(n) % dim_size][(n) / dim_size];
00401 }
00402 STXXL_ADAPTOR_ARITHMETICS(pos)
00403 };
00404 #endif
00405
00406
00407 template <typename array_type, typename value_type, unsigned_type modulo>
00408 class ArrayOfSequencesIterator : public std::iterator<std::random_access_iterator_tag, value_type, unsigned_type>
00409 {
00410 unsigned_type pos;
00411 unsigned_type offset;
00412 array_type * arrays;
00413 array_type * base;
00414 value_type * base_element;
00415
00417
00418 void set(unsigned_type pos)
00419 {
00420 this->pos = pos;
00421 offset = pos % modulo;
00422 base = arrays + pos / modulo;
00423 base_element = base->elem;
00424 }
00425
00426 public:
00427 ArrayOfSequencesIterator()
00428 {
00429 this->arrays = NULL;
00430 set(0);
00431 }
00432
00433 ArrayOfSequencesIterator(array_type * arrays)
00434 {
00435 this->arrays = arrays;
00436 set(0);
00437 }
00438
00439 ArrayOfSequencesIterator(array_type * arrays, unsigned_type pos)
00440 {
00441 this->arrays = arrays;
00442 set(pos);
00443 }
00444
00445 void operator = (unsigned_type pos)
00446 {
00447 set(pos);
00448 }
00449
00450
00451 ArrayOfSequencesIterator & operator ++ ()
00452 {
00453 ++pos;
00454 ++offset;
00455 if (offset == modulo)
00456 {
00457 offset = 0;
00458 ++base;
00459 base_element = base->elem;
00460 }
00461 return *this;
00462 }
00463
00464
00465 ArrayOfSequencesIterator operator ++ (int)
00466 {
00467 ArrayOfSequencesIterator former(*this);
00468 operator ++ ();
00469 return former;
00470 }
00471
00472
00473 ArrayOfSequencesIterator & operator -- ()
00474 {
00475 --pos;
00476 if (offset == 0)
00477 {
00478 offset = modulo;
00479 --base;
00480 base_element = base->elem;
00481 }
00482 --offset;
00483 return *this;
00484 }
00485
00486
00487 ArrayOfSequencesIterator operator -- (int)
00488 {
00489 ArrayOfSequencesIterator former(*this);
00490 operator -- ();
00491 return former;
00492 }
00493
00494 ArrayOfSequencesIterator & operator += (unsigned_type addend)
00495 {
00496 set(pos + addend);
00497 return *this;
00498 }
00499
00500 ArrayOfSequencesIterator & operator -= (unsigned_type addend)
00501 {
00502 set(pos - addend);
00503 return *this;
00504 }
00505
00506 ArrayOfSequencesIterator operator + (unsigned_type addend) const
00507 {
00508 return ArrayOfSequencesIterator(arrays, pos + addend);
00509 }
00510
00511 ArrayOfSequencesIterator operator - (unsigned_type subtrahend) const
00512 {
00513 return ArrayOfSequencesIterator(arrays, pos - subtrahend);
00514 }
00515
00516 unsigned_type operator - (const ArrayOfSequencesIterator & subtrahend) const
00517 {
00518 return pos - subtrahend.pos;
00519 }
00520
00521 bool operator == (const ArrayOfSequencesIterator & aoai) const
00522 {
00523 return pos == aoai.pos;
00524 }
00525
00526 bool operator != (const ArrayOfSequencesIterator & aoai) const
00527 {
00528 return pos != aoai.pos;
00529 }
00530
00531 bool operator < (const ArrayOfSequencesIterator & aoai) const
00532 {
00533 return pos < aoai.pos;
00534 }
00535
00536 bool operator <= (const ArrayOfSequencesIterator & aoai) const
00537 {
00538 return pos <= aoai.pos;
00539 }
00540
00541 bool operator > (const ArrayOfSequencesIterator & aoai) const
00542 {
00543 return pos > aoai.pos;
00544 }
00545
00546 bool operator >= (const ArrayOfSequencesIterator & aoai) const
00547 {
00548 return pos >= aoai.pos;
00549 }
00550
00551 const value_type & operator * () const
00552 {
00553 return base_element[offset];
00554 }
00555
00556 value_type & operator * ()
00557 {
00558 return base_element[offset];
00559 }
00560
00561 const value_type & operator -> () const
00562 {
00563 return &(base_element[offset]);
00564 }
00565
00566 value_type & operator -> ()
00567 {
00568 return &(base_element[offset]);
00569 }
00570
00571 const value_type & operator [] (unsigned_type index) const
00572 {
00573 return arrays[index / modulo][index % modulo];
00574 }
00575
00576 value_type & operator [] (unsigned_type index)
00577 {
00578 return arrays[index / modulo][index % modulo];
00579 }
00580 };
00581
00582 namespace helper
00583 {
00584 template <typename BlockType, bool can_use_trivial_pointer>
00585 class element_iterator_generator
00586 { };
00587
00588
00589 template <typename BlockType>
00590 class element_iterator_generator<BlockType, false>
00591 {
00592 typedef BlockType block_type;
00593 typedef typename block_type::value_type value_type;
00594
00595 public:
00596 typedef ArrayOfSequencesIterator<block_type, value_type, block_type::size> iterator;
00597
00598 iterator operator () (block_type * blocks, unsigned_type offset) const
00599 {
00600 return iterator(blocks, offset);
00601 }
00602 };
00603
00604
00605 template <typename BlockType>
00606 class element_iterator_generator<BlockType, true>
00607 {
00608 typedef BlockType block_type;
00609 typedef typename block_type::value_type value_type;
00610
00611 public:
00612 typedef value_type * iterator;
00613
00614 iterator operator () (block_type * blocks, unsigned_type offset) const
00615 {
00616 return blocks[0].elem + offset;
00617 }
00618 };
00619 }
00620
00621 template <typename BlockType>
00622 struct element_iterator_traits
00623 {
00624 typedef typename helper::element_iterator_generator<BlockType, BlockType::has_only_data>::iterator element_iterator;
00625 };
00626
00627 template <typename BlockType>
00628 inline
00629 typename element_iterator_traits<BlockType>::element_iterator
00630 make_element_iterator(BlockType * blocks, unsigned_type offset)
00631 {
00632 helper::element_iterator_generator<BlockType, BlockType::has_only_data> iter_gen;
00633 return iter_gen(blocks, offset);
00634 }
00635
00637
00638 __STXXL_END_NAMESPACE
00639
00640 #endif // !STXXL_MNG_ADAPTOR_HEADER
00641