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