adaptor.h

Go to the documentation of this file.

/***************************************************************************
 * include/stxxl/bits/mng/adaptor.h
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2002-2003 Roman Dementiev <[email protected]>
 * Copyright (C) 2007 Johannes Singler <[email protected]>
 * Copyright (C) 2009-2010 Andreas Beckmann <[email protected]>
 *
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_MNG_ADAPTOR_HEADER
#define STXXL_MNG_ADAPTOR_HEADER

#include <iterator>

#include <stxxl/bits/common/types.h>

STXXL_BEGIN_NAMESPACE

//! \addtogroup mnglayer
//!
//! \{

template <unsigned_type modulo>
class blocked_index
{
 unsigned_type pos;
 unsigned_type block;
 unsigned_type offset;

 //! \invariant block * modulo + offset = pos

 void set(unsigned_type pos)
 {
 this->pos = pos;
 block = pos / modulo;
 offset = pos % modulo;
 }

public:
 blocked_index()
 {
 set(0);
 }

 blocked_index(unsigned_type pos)
 {
 set(pos);
 }

 blocked_index(unsigned_type block, unsigned_type offset)
 {
 this->block = block;
 this->offset = offset;
 pos = block * modulo + offset;
 }

 void operator = (unsigned_type pos)
 {
 set(pos);
 }

 //pre-increment operator
 blocked_index& operator ++ ()
 {
 ++pos;
 ++offset;
 if (offset == modulo)
 {
 offset = 0;
 ++block;
 }
 return *this;
 }

 //post-increment operator
 blocked_index operator ++ (int)
 {
 blocked_index former(*this);
 operator ++ ();
 return former;
 }

 //pre-increment operator
 blocked_index& operator -- ()
 {
 --pos;
 if (offset == 0)
 {
 offset = modulo;
 --block;
 }
 --offset;
 return *this;
 }

 //post-increment operator
 blocked_index operator -- (int)
 {
 blocked_index former(*this);
 operator -- ();
 return former;
 }

 blocked_index& operator += (unsigned_type addend)
 {
 set(pos + addend);
 return *this;
 }

 blocked_index& operator >>= (unsigned_type shift)
 {
 set(pos >> shift);
 return *this;
 }

 operator unsigned_type () const
 {
 return pos;
 }

 const unsigned_type & get_block() const
 {
 return block;
 }

 const unsigned_type & get_offset() const
 {
 return offset;
 }
};

#define STXXL_ADAPTOR_ARITHMETICS(pos) \
 bool operator == (const self_type &a) const \
 { \
 return (a.pos == pos); \
 } \
 bool operator != (const self_type& a) const \
 { \
 return (a.pos != pos); \
 } \
 bool operator < (const self_type& a) const \
 { \
 return (pos < a.pos); \
 } \
 bool operator > (const self_type& a) const \
 { \
 return (pos > a.pos); \
 } \
 bool operator <= (const self_type& a) const \
 { \
 return (pos <= a.pos); \
 } \
 bool operator >= (const self_type& a) const \
 { \
 return (pos >= a.pos); \
 } \
 self_type operator + (pos_type off) const \
 { \
 return self_type(array, pos + off); \
 } \
 self_type operator - (pos_type off) const \
 { \
 return self_type(array, pos - off); \
 } \
 self_type& operator ++ () \
 { \
 pos++; \
 return *this; \
 } \
 self_type operator ++ (int) \
 { \
 self_type tmp = *this; \
 pos++; \
 return tmp; \
 } \
 self_type& operator -- () \
 { \
 pos--; \
 return *this; \
 } \
 self_type operator -- (int) \
 { \
 self_type tmp = *this; \
 pos--; \
 return tmp; \
 } \
 pos_type operator - (const self_type& a) const \
 { \
 return pos - a.pos; \
 } \
 self_type& operator -= (pos_type off) \
 { \
 pos -= off; \
 return *this; \
 } \
 self_type& operator += (pos_type off) \
 { \
 pos += off; \
 return *this; \
 }

template <class OneDimArrayType, class DataType, class PosType>
struct two2one_dim_array_adapter_base
 : public std::iterator<std::random_access_iterator_tag, DataType, unsigned_type>
{
 typedef OneDimArrayType one_dim_array_type;
 typedef DataType data_type;
 typedef PosType pos_type;

 typedef two2one_dim_array_adapter_base<one_dim_array_type,
 data_type, pos_type> self_type;

 one_dim_array_type* array;
 pos_type pos;

 two2one_dim_array_adapter_base()
 { }

 two2one_dim_array_adapter_base(one_dim_array_type* a, pos_type p)
 : array(a), pos(p)
 { }
 two2one_dim_array_adapter_base(const two2one_dim_array_adapter_base& a)
 : array(a.array), pos(a.pos)
 { }

 STXXL_ADAPTOR_ARITHMETICS(pos)
};

//////////////////////////////

#define BLOCK_ADAPTOR_OPERATORS(two_to_one_dim_array_adaptor_base) \
 \
 template <unsigned BlockSize, typename RunType, class PosType> \
 inline two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& operator ++ ( \
 two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& a) \
 { \
 a.pos++; \
 return a; \
 } \
 \
 template <unsigned BlockSize, typename RunType, class PosType> \
 inline two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType> operator ++ ( \
 two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& a, int) \
 { \
 two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType> tmp = a; \
 a.pos++; \
 return tmp; \
 } \
 \
 template <unsigned BlockSize, typename RunType, class PosType> \
 inline two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& operator -- ( \
 two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& a) \
 { \
 a.pos--; \
 return a; \
 } \
 \
 template <unsigned BlockSize, typename RunType, class PosType> \
 inline two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType> operator -- ( \
 two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& a, int) \
 { \
 two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType> tmp = a; \
 a.pos--; \
 return tmp; \
 } \
 \
 template <unsigned BlockSize, typename RunType, class PosType> \
 inline two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& operator -= ( \
 two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& a, \
 typename two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>::_pos_type off) \
 { \
 a.pos -= off; \
 return a; \
 } \
 \
 template <unsigned BlockSize, typename RunType, class PosType> \
 inline two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& operator += ( \
 two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& a, \
 typename two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>::_pos_type off) \
 { \
 a.pos += off; \
 return a; \
 } \
 \
 template <unsigned BlockSize, typename RunType, class PosType> \
 inline two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType> operator + ( \
 const two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& a, \
 typename two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>::_pos_type off) \
 { \
 return two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>(a.array, a.pos + off); \
 } \
 \
 template <unsigned BlockSize, typename RunType, class PosType> \
 inline two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType> operator + ( \
 typename two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>::_pos_type off, \
 const two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& a) \
 { \
 return two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>(a.array, a.pos + off); \
 } \
 \
 template <unsigned BlockSize, typename RunType, class PosType> \
 inline two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType> operator - ( \
 const two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>& a, \
 typename two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>::_pos_type off) \
 { \
 return two_to_one_dim_array_adaptor_base<BlockSize, RunType, PosType>(a.array, a.pos - off); \
 }

#if 0
//////////////////////////
template <class OneDimArrayType, class DataType,
 unsigned DimSize, class PosType = blocked_index<DimSize> >
struct two2one_dim_array_row_adapter
 : public two2one_dim_array_adapter_base<OneDimArrayType, DataType, PosType>
{
 typedef OneDimArrayType one_dim_array_type;
 typedef DataType data_type;
 typedef DimSize dim_type;
 typedef PosType pos_type;

 typedef two2one_dim_array_row_adapter<one_dim_array_type,
 data_type, dim_size, pos_type> self_type;

 typedef two2one_dim_array_adapter_base<one_dim_array_type,
 data_type, pos_type> base_type;
 using base_type::array;
 using base_type::pos;

 two2one_dim_array_row_adapter()
 { }
 two2one_dim_array_row_adapter(one_dim_array_type* a, pos_type p)
 : two2one_dim_array_adapter_base<one_dim_array_type, data_type, pos_type>(a, p)
 { }
 two2one_dim_array_row_adapter(const two2one_dim_array_row_adapter& a)
 : two2one_dim_array_adapter_base<one_dim_array_type, data_type, pos_type>(a)
 { }

 data_type& operator * ()
 {
 return array[(pos).get_block()][(pos).get_offset()];
 }

 data_type* operator -> () const
 {
 return &(array[(pos).get_block()][(pos).get_offset()]);
 }

 data_type& operator [] (pos_type n)
 {
 n += pos;
 return array[(n) / dim_size][(n) % dim_size];
 }

 const data_type& operator [] (pos_type n) const
 {
 n += pos;
 return array[(n) / dim_size][(n) % dim_size];
 }
 STXXL_ADAPTOR_ARITHMETICS(pos)
};

template <class OneDimArrayType, class DataType,
 unsigned DimSize, class PosType = blocked_index<DimSize> >
struct two2one_dim_array_column_adapter
 : public two2one_dim_array_adapter_base<OneDimArrayType, DataType, PosType>
{
 typedef two2one_dim_array_column_adapter<one_dim_array_type,
 data_type, dim_size, pos_type> self_type;

 using two2one_dim_array_adapter_base<one_dim_array_type, data_type, pos_type>::pos;
 using two2one_dim_array_adapter_base<one_dim_array_type, data_type, pos_type>::array;

 two2one_dim_array_column_adapter(one_dim_array_type* a, pos_type p)
 : two2one_dim_array_adapter_base<one_dim_array_type, data_type, pos_type>(a, p)
 { }
 two2one_dim_array_column_adapter(const self_type& a)
 : two2one_dim_array_adapter_base<one_dim_array_type, data_type, pos_type>(a)
 { }

 data_type& operator * ()
 {
 return array[(pos).get_offset()][(pos).get_block()];
 }

 data_type* operator -> () const
 {
 return &(array[(pos).get_offset()][(pos).get_block()]);
 }

 const data_type& operator [] (pos_type n) const
 {
 n += pos;
 return array[(n) % dim_size][(n) / dim_size];
 }

 data_type& operator [] (pos_type n)
 {
 n += pos;
 return array[(n) % dim_size][(n) / dim_size];
 }
 STXXL_ADAPTOR_ARITHMETICS(pos)
};
#endif

template <typename ArrayType, typename ValueType, unsigned_type modulo>
class array_of_sequences_iterator
 : public std::iterator<std::random_access_iterator_tag, ValueType, unsigned_type>
{
public:
 typedef ArrayType array_type;
 typedef ValueType value_type;

protected:
 unsigned_type pos;
 unsigned_type offset;
 array_type* arrays;
 array_type* base;
 value_type* base_element;

 //! \invariant block * modulo + offset = pos

 void set(unsigned_type pos)
 {
 this->pos = pos;
 offset = pos % modulo;
 base = arrays + pos / modulo;
 base_element = base->elem;
 }

public:
 array_of_sequences_iterator()
 {
 this->arrays = NULL;
 set(0);
 }

 array_of_sequences_iterator(array_type* arrays)
 {
 this->arrays = arrays;
 set(0);
 }

 array_of_sequences_iterator(array_type* arrays, unsigned_type pos)
 {
 this->arrays = arrays;
 set(pos);
 }

 void operator = (unsigned_type pos)
 {
 set(pos);
 }

 //pre-increment operator
 array_of_sequences_iterator& operator ++ ()
 {
 ++pos;
 ++offset;
 if (offset == modulo)
 {
 offset = 0;
 ++base;
 base_element = base->elem;
 }
 return *this;
 }

 //post-increment operator
 array_of_sequences_iterator operator ++ (int)
 {
 array_of_sequences_iterator former(*this);
 operator ++ ();
 return former;
 }

 //pre-increment operator
 array_of_sequences_iterator& operator -- ()
 {
 --pos;
 if (offset == 0)
 {
 offset = modulo;
 --base;
 base_element = base->elem;
 }
 --offset;
 return *this;
 }

 //post-increment operator
 array_of_sequences_iterator operator -- (int)
 {
 array_of_sequences_iterator former(*this);
 operator -- ();
 return former;
 }

 array_of_sequences_iterator& operator += (unsigned_type addend)
 {
 set(pos + addend);
 return *this;
 }

 array_of_sequences_iterator& operator -= (unsigned_type addend)
 {
 set(pos - addend);
 return *this;
 }

 array_of_sequences_iterator operator + (unsigned_type addend) const
 {
 return array_of_sequences_iterator(arrays, pos + addend);
 }

 array_of_sequences_iterator operator - (unsigned_type subtrahend) const
 {
 return array_of_sequences_iterator(arrays, pos - subtrahend);
 }

 unsigned_type operator - (const array_of_sequences_iterator& subtrahend) const
 {
 return pos - subtrahend.pos;
 }

 bool operator == (const array_of_sequences_iterator& aoai) const
 {
 return pos == aoai.pos;
 }

 bool operator != (const array_of_sequences_iterator& aoai) const
 {
 return pos != aoai.pos;
 }

 bool operator < (const array_of_sequences_iterator& aoai) const
 {
 return pos < aoai.pos;
 }

 bool operator <= (const array_of_sequences_iterator& aoai) const
 {
 return pos <= aoai.pos;
 }

 bool operator > (const array_of_sequences_iterator& aoai) const
 {
 return pos > aoai.pos;
 }

 bool operator >= (const array_of_sequences_iterator& aoai) const
 {
 return pos >= aoai.pos;
 }

 const value_type& operator * () const
 {
 return base_element[offset];
 }

 value_type& operator * ()
 {
 return base_element[offset];
 }

 const value_type& operator -> () const
 {
 return &(base_element[offset]);
 }

 value_type& operator -> ()
 {
 return &(base_element[offset]);
 }

 const value_type& operator [] (unsigned_type index) const
 {
 return arrays[index / modulo][index % modulo];
 }

 value_type& operator [] (unsigned_type index)
 {
 return arrays[index / modulo][index % modulo];
 }
};

namespace helper {

template <typename BlockType, typename SizeType, bool CanUseTrivialPointer>
class element_iterator_generator
{ };

// default case for blocks with fillers or other data: use array_of_sequences_iterator
template <typename BlockType, typename SizeType>
class element_iterator_generator<BlockType, SizeType, false>
{
 typedef BlockType block_type;
 typedef typename block_type::value_type value_type;

 typedef SizeType size_type;

public:
 typedef array_of_sequences_iterator<block_type, value_type, block_type::size> iterator;

 iterator operator () (block_type* blocks, SizeType offset) const
 {
 return iterator(blocks, offset);
 }
};

// special case for completely filled blocks: use trivial pointers
template <typename BlockType, typename SizeType>
class element_iterator_generator<BlockType, SizeType, true>
{
 typedef BlockType block_type;
 typedef typename block_type::value_type value_type;

 typedef SizeType size_type;

public:
 typedef value_type* iterator;

 iterator operator () (block_type* blocks, SizeType offset) const
 {
 return blocks[0].elem + offset;
 }
};

} // namespace helper

template <typename BlockType, typename SizeType>
struct element_iterator_traits
{
 typedef typename helper::element_iterator_generator<
 BlockType, SizeType, BlockType::has_only_data
 >::iterator element_iterator;
};

template <typename BlockType, typename SizeType>
inline
typename element_iterator_traits<BlockType, SizeType>::element_iterator
make_element_iterator(BlockType* blocks, SizeType offset)
{
 helper::element_iterator_generator<
 BlockType, SizeType, BlockType::has_only_data
 > iter_gen;
 return iter_gen(blocks, offset);
}

//! \}

STXXL_END_NAMESPACE

#endif // !STXXL_MNG_ADAPTOR_HEADER
// vim: et:ts=4:sw=4