Stxxl 1.2.1
adaptor.h
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