Stxxl 1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/mng/adaptor.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2002-2003 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * Copyright (C) 2007 Johannes Singler <singler@ira.uka.de> 00008 * 00009 * Distributed under the Boost Software License, Version 1.0. 00010 * (See accompanying file LICENSE_1_0.txt or copy at 00011 * http://www.boost.org/LICENSE_1_0.txt) 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 //pre-increment operator 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 //post-increment operator 00082 blocked_index operator ++ (int) 00083 { 00084 blocked_index former(*this); 00085 operator ++ (); 00086 return former; 00087 } 00088 00089 //pre-increment operator 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 //post-increment operator 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 //pre-increment operator 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 //post-increment operator 00464 ArrayOfSequencesIterator operator ++ (int) 00465 { 00466 ArrayOfSequencesIterator former(*this); 00467 operator ++ (); 00468 return former; 00469 } 00470 00471 //pre-increment operator 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 //post-increment operator 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