Stxxl  1.2.1
mng/adaptor.h
1 /***************************************************************************
2  * include/stxxl/bits/mng/adaptor.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002-2003 Roman Dementiev <dementiev@mpi-sb.mpg.de>
7  * Copyright (C) 2007 Johannes Singler <singler@ira.uka.de>
8  *
9  * Distributed under the Boost Software License, Version 1.0.
10  * (See accompanying file LICENSE_1_0.txt or copy at
11  * http://www.boost.org/LICENSE_1_0.txt)
12  **************************************************************************/
13 
14 #ifndef STXXL_MNG_ADAPTOR_HEADER
15 #define STXXL_MNG_ADAPTOR_HEADER
16 
17 #include <iterator>
18 
19 #include <stxxl/bits/common/types.h>
20 
21 
22 __STXXL_BEGIN_NAMESPACE
23 
27 
28 
29 template <unsigned_type modulo>
30 class blocked_index
31 {
32  unsigned_type pos;
33  unsigned_type block;
34  unsigned_type offset;
35 
37 
38  void set(unsigned_type pos)
39  {
40  this->pos = pos;
41  block = pos / modulo;
42  offset = pos % modulo;
43  }
44 
45 public:
46  blocked_index()
47  {
48  set(0);
49  }
50 
51  blocked_index(unsigned_type pos)
52  {
53  set(pos);
54  }
55 
56  blocked_index(unsigned_type block, unsigned_type offset)
57  {
58  this->block = block;
59  this->offset = offset;
60  pos = block * modulo + offset;
61  }
62 
63  void operator = (unsigned_type pos)
64  {
65  set(pos);
66  }
67 
68  //pre-increment operator
69  blocked_index & operator ++ ()
70  {
71  ++pos;
72  ++offset;
73  if (offset == modulo)
74  {
75  offset = 0;
76  ++block;
77  }
78  return *this;
79  }
80 
81  //post-increment operator
82  blocked_index operator ++ (int)
83  {
84  blocked_index former(*this);
85  operator ++ ();
86  return former;
87  }
88 
89  //pre-increment operator
90  blocked_index & operator -- ()
91  {
92  --pos;
93  if (offset == 0)
94  {
95  offset = modulo;
96  --block;
97  }
98  --offset;
99  return *this;
100  }
101 
102  //post-increment operator
103  blocked_index operator -- (int)
104  {
105  blocked_index former(*this);
106  operator -- ();
107  return former;
108  }
109 
110  blocked_index & operator += (unsigned_type addend)
111  {
112  set(pos + addend);
113  return *this;
114  }
115 
116  blocked_index & operator >>= (unsigned_type shift)
117  {
118  set(pos >> shift);
119  return *this;
120  }
121 
122  operator unsigned_type () const
123  {
124  return pos;
125  }
126 
127  const unsigned_type & get_block() const
128  {
129  return block;
130  }
131 
132  const unsigned_type & get_offset() const
133  {
134  return offset;
135  }
136 };
137 
138 #define STXXL_ADAPTOR_ARITHMETICS(pos) \
139  bool operator == (const _Self & a) const \
140  { \
141  return (a.pos == pos); \
142  } \
143  bool operator != (const _Self & a) const \
144  { \
145  return (a.pos != pos); \
146  } \
147  bool operator < (const _Self & a) const \
148  { \
149  return (pos < a.pos); \
150  } \
151  bool operator > (const _Self & a) const \
152  { \
153  return (pos > a.pos); \
154  } \
155  bool operator <= (const _Self & a) const \
156  { \
157  return (pos <= a.pos); \
158  } \
159  bool operator >= (const _Self & a) const \
160  { \
161  return (pos >= a.pos); \
162  } \
163  _Self operator + (pos_type off) const \
164  { \
165  return _Self(array, pos + off); \
166  } \
167  _Self operator - (pos_type off) const \
168  { \
169  return _Self(array, pos - off); \
170  } \
171  _Self & operator ++ () \
172  { \
173  pos++; \
174  return *this; \
175  } \
176  _Self operator ++ (int) \
177  { \
178  _Self tmp = *this; \
179  pos++; \
180  return tmp; \
181  } \
182  _Self & operator -- () \
183  { \
184  pos--; \
185  return *this; \
186  } \
187  _Self operator -- (int) \
188  { \
189  _Self tmp = *this; \
190  pos--; \
191  return tmp; \
192  } \
193  pos_type operator - (const _Self & a) const \
194  { \
195  return pos - a.pos; \
196  } \
197  _Self & operator -= (pos_type off) \
198  { \
199  pos -= off; \
200  return *this; \
201  } \
202  _Self & operator += (pos_type off) \
203  { \
204  pos += off; \
205  return *this; \
206  }
207 
208 template <class one_dim_array_type, class data_type, class pos_type>
209 struct TwoToOneDimArrayAdaptorBase
210  : public std::iterator<std::random_access_iterator_tag, data_type, unsigned_type>
211 {
212  one_dim_array_type * array;
213  pos_type pos;
214  typedef pos_type _pos_type;
215  typedef TwoToOneDimArrayAdaptorBase<one_dim_array_type,
216  data_type, pos_type> _Self;
217 
218 
219  TwoToOneDimArrayAdaptorBase()
220  { }
221 
222  TwoToOneDimArrayAdaptorBase(one_dim_array_type * a, pos_type p)
223  : array(a), pos(p)
224  { }
225  TwoToOneDimArrayAdaptorBase(const TwoToOneDimArrayAdaptorBase & a)
226  : array(a.array), pos(a.pos)
227  { }
228 
229  STXXL_ADAPTOR_ARITHMETICS(pos)
230 };
231 
232 
234 
235 #define BLOCK_ADAPTOR_OPERATORS(two_to_one_dim_array_adaptor_base) \
236 \
237  template <unsigned _blk_sz, typename _run_type, class __pos_type> \
238  inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & operator ++ ( \
239  two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a) \
240  { \
241  a.pos++; \
242  return a; \
243  } \
244 \
245  template <unsigned _blk_sz, typename _run_type, class __pos_type> \
246  inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> operator ++ ( \
247  two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, int) \
248  { \
249  two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> tmp = a; \
250  a.pos++; \
251  return tmp; \
252  } \
253 \
254  template <unsigned _blk_sz, typename _run_type, class __pos_type> \
255  inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & operator -- ( \
256  two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a) \
257  { \
258  a.pos--; \
259  return a; \
260  } \
261 \
262  template <unsigned _blk_sz, typename _run_type, class __pos_type> \
263  inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> operator -- ( \
264  two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, int) \
265  { \
266  two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> tmp = a; \
267  a.pos--; \
268  return tmp; \
269  } \
270 \
271  template <unsigned _blk_sz, typename _run_type, class __pos_type> \
272  inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & operator -= ( \
273  two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, \
274  typename two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>::_pos_type off) \
275  { \
276  a.pos -= off; \
277  return a; \
278  } \
279 \
280  template <unsigned _blk_sz, typename _run_type, class __pos_type> \
281  inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & operator += ( \
282  two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, \
283  typename two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>::_pos_type off) \
284  { \
285  a.pos += off; \
286  return a; \
287  } \
288 \
289  template <unsigned _blk_sz, typename _run_type, class __pos_type> \
290  inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> operator + ( \
291  const two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, \
292  typename two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>::_pos_type off) \
293  { \
294  return two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>(a.array, a.pos + off); \
295  } \
296 \
297  template <unsigned _blk_sz, typename _run_type, class __pos_type> \
298  inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> operator + ( \
299  typename two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>::_pos_type off, \
300  const two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a) \
301  { \
302  return two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>(a.array, a.pos + off); \
303  } \
304 \
305  template <unsigned _blk_sz, typename _run_type, class __pos_type> \
306  inline two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> operator - ( \
307  const two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type> & a, \
308  typename two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>::_pos_type off) \
309  { \
310  return two_to_one_dim_array_adaptor_base<_blk_sz, _run_type, __pos_type>(a.array, a.pos - off); \
311  }
312 
313 
314 #if 0
315 
316 template <class one_dim_array_type, class data_type,
317  unsigned dim_size, class pos_type = blocked_index<dim_size> >
318 struct TwoToOneDimArrayRowAdaptor : public
319  TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>
320 {
321  typedef TwoToOneDimArrayRowAdaptor<one_dim_array_type,
322  data_type, dim_size, pos_type> _Self;
323 
324  typedef TwoToOneDimArrayAdaptorBase<one_dim_array_type,
325  data_type, pos_type> _Parent;
326  using _Parent::array;
327  using _Parent::pos;
328 
329  TwoToOneDimArrayRowAdaptor()
330  { }
331  TwoToOneDimArrayRowAdaptor(one_dim_array_type * a, pos_type p)
332  : TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>(a, p)
333  { }
334  TwoToOneDimArrayRowAdaptor(const TwoToOneDimArrayRowAdaptor & a)
335  : TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>(a)
336  { }
337 
338  data_type & operator * ()
339  {
340  return array[(pos).get_block()][(pos).get_offset()];
341  }
342 
343  data_type * operator -> () const
344  {
345  return &(array[(pos).get_block()][(pos).get_offset()]);
346  }
347 
348  data_type & operator [] (pos_type n)
349  {
350  n += pos;
351  return array[(n) / dim_size][(n) % dim_size];
352  }
353 
354  const data_type & operator [] (pos_type n) const
355  {
356  n += pos;
357  return array[(n) / dim_size][(n) % dim_size];
358  }
359  STXXL_ADAPTOR_ARITHMETICS(pos)
360 };
361 
362 template <class one_dim_array_type, class data_type,
363  unsigned dim_size, class pos_type = blocked_index<dim_size> >
364 struct TwoToOneDimArrayColumnAdaptor
365  : public TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>
366 {
367  typedef TwoToOneDimArrayColumnAdaptor<one_dim_array_type,
368  data_type, dim_size, pos_type> _Self;
369 
370  using TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>::pos;
371  using TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>::array;
372 
373  TwoToOneDimArrayColumnAdaptor(one_dim_array_type * a, pos_type p)
374  : TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>(a, p)
375  { }
376  TwoToOneDimArrayColumnAdaptor(const _Self & a)
377  : TwoToOneDimArrayAdaptorBase<one_dim_array_type, data_type, pos_type>(a)
378  { }
379 
380  data_type & operator * ()
381  {
382  return array[(pos).get_offset()][(pos).get_block()];
383  }
384 
385  data_type * operator -> () const
386  {
387  return &(array[(pos).get_offset()][(pos).get_block()]);
388  }
389 
390  const data_type & operator [] (pos_type n) const
391  {
392  n += pos;
393  return array[(n) % dim_size][(n) / dim_size];
394  }
395 
396  data_type & operator [] (pos_type n)
397  {
398  n += pos;
399  return array[(n) % dim_size][(n) / dim_size];
400  }
401  STXXL_ADAPTOR_ARITHMETICS(pos)
402 };
403 #endif
404 
405 
406 template <typename array_type, typename value_type, unsigned_type modulo>
407 class ArrayOfSequencesIterator : public std::iterator<std::random_access_iterator_tag, value_type, unsigned_type>
408 {
409  unsigned_type pos;
410  unsigned_type offset;
411  array_type * arrays;
412  array_type * base;
413  value_type * base_element;
414 
416 
417  void set(unsigned_type pos)
418  {
419  this->pos = pos;
420  offset = pos % modulo;
421  base = arrays + pos / modulo;
422  base_element = base->elem;
423  }
424 
425 public:
426  ArrayOfSequencesIterator()
427  {
428  this->arrays = NULL;
429  set(0);
430  }
431 
432  ArrayOfSequencesIterator(array_type * arrays)
433  {
434  this->arrays = arrays;
435  set(0);
436  }
437 
438  ArrayOfSequencesIterator(array_type * arrays, unsigned_type pos)
439  {
440  this->arrays = arrays;
441  set(pos);
442  }
443 
444  void operator = (unsigned_type pos)
445  {
446  set(pos);
447  }
448 
449  //pre-increment operator
450  ArrayOfSequencesIterator & operator ++ ()
451  {
452  ++pos;
453  ++offset;
454  if (offset == modulo)
455  {
456  offset = 0;
457  ++base;
458  base_element = base->elem;
459  }
460  return *this;
461  }
462 
463  //post-increment operator
464  ArrayOfSequencesIterator operator ++ (int)
465  {
466  ArrayOfSequencesIterator former(*this);
467  operator ++ ();
468  return former;
469  }
470 
471  //pre-increment operator
472  ArrayOfSequencesIterator & operator -- ()
473  {
474  --pos;
475  if (offset == 0)
476  {
477  offset = modulo;
478  --base;
479  base_element = base->elem;
480  }
481  --offset;
482  return *this;
483  }
484 
485  //post-increment operator
486  ArrayOfSequencesIterator operator -- (int)
487  {
488  ArrayOfSequencesIterator former(*this);
489  operator -- ();
490  return former;
491  }
492 
493  ArrayOfSequencesIterator & operator += (unsigned_type addend)
494  {
495  set(pos + addend);
496  return *this;
497  }
498 
499  ArrayOfSequencesIterator & operator -= (unsigned_type addend)
500  {
501  set(pos - addend);
502  return *this;
503  }
504 
505  ArrayOfSequencesIterator operator + (unsigned_type addend) const
506  {
507  return ArrayOfSequencesIterator(arrays, pos + addend);
508  }
509 
510  ArrayOfSequencesIterator operator - (unsigned_type subtrahend) const
511  {
512  return ArrayOfSequencesIterator(arrays, pos - subtrahend);
513  }
514 
515  unsigned_type operator - (const ArrayOfSequencesIterator & subtrahend) const
516  {
517  return pos - subtrahend.pos;
518  }
519 
520  bool operator == (const ArrayOfSequencesIterator & aoai) const
521  {
522  return pos == aoai.pos;
523  }
524 
525  bool operator != (const ArrayOfSequencesIterator & aoai) const
526  {
527  return pos != aoai.pos;
528  }
529 
530  bool operator < (const ArrayOfSequencesIterator & aoai) const
531  {
532  return pos < aoai.pos;
533  }
534 
535  bool operator <= (const ArrayOfSequencesIterator & aoai) const
536  {
537  return pos <= aoai.pos;
538  }
539 
540  bool operator > (const ArrayOfSequencesIterator & aoai) const
541  {
542  return pos > aoai.pos;
543  }
544 
545  bool operator >= (const ArrayOfSequencesIterator & aoai) const
546  {
547  return pos >= aoai.pos;
548  }
549 
550  const value_type & operator * () const
551  {
552  return base_element[offset];
553  }
554 
555  value_type & operator * ()
556  {
557  return base_element[offset];
558  }
559 
560  const value_type & operator -> () const
561  {
562  return &(base_element[offset]);
563  }
564 
565  value_type & operator -> ()
566  {
567  return &(base_element[offset]);
568  }
569 
570  const value_type & operator [] (unsigned_type index) const
571  {
572  return arrays[index / modulo][index % modulo];
573  }
574 
575  value_type & operator [] (unsigned_type index)
576  {
577  return arrays[index / modulo][index % modulo];
578  }
579 };
580 
581 
583 
584 __STXXL_END_NAMESPACE
585 
586 #endif // !STXXL_MNG_ADAPTOR_HEADER