scan.h

/***************************************************************************
 * include/stxxl/bits/algo/scan.h
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2002-2004 Roman Dementiev <[email protected]>
 * Copyright (C) 2008, 2009 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_SCAN_HEADER
#define STXXL_SCAN_HEADER

#include <stxxl/bits/namespace.h>
#include <stxxl/bits/mng/buf_istream.h>
#include <stxxl/bits/mng/buf_ostream.h>


__STXXL_BEGIN_NAMESPACE


template <typename _ExtIterator, typename _UnaryFunction>
_UnaryFunction for_each(_ExtIterator _begin, _ExtIterator _end, _UnaryFunction _functor, int_type nbuffers)
{
 if (_begin == _end)
 return _functor;

 typedef buf_istream<typename _ExtIterator::block_type, typename _ExtIterator::bids_container_iterator> buf_istream_type;

 _begin.flush(); // flush container

 // create prefetching stream,
 buf_istream_type in(_begin.bid(), _end.bid() + ((_end.block_offset()) ? 1 : 0), nbuffers);

 _ExtIterator _cur = _begin - _begin.block_offset();

 // leave part of the block before _begin untouched (e.g. copy)
 for ( ; _cur != _begin; ++_cur)
 {
 typename _ExtIterator::value_type tmp;
 in >> tmp;
 }

 // apply _functor to the range [_begin,_end)
 for ( ; _cur != _end; ++_cur)
 {
 typename _ExtIterator::value_type tmp;
 in >> tmp;
 _functor(tmp);
 }

 // leave part of the block after _end untouched
 if (_end.block_offset())
 {
 _ExtIterator _last_block_end = _end - _end.block_offset() + _ExtIterator::block_type::size;
 for ( ; _cur != _last_block_end; ++_cur)
 {
 typename _ExtIterator::value_type tmp;
 in >> tmp;
 }
 }

 return _functor;
}


template <typename _ExtIterator, typename _UnaryFunction>
_UnaryFunction for_each_m(_ExtIterator _begin, _ExtIterator _end, _UnaryFunction _functor, int_type nbuffers)
{
 if (_begin == _end)
 return _functor;

 typedef buf_istream<typename _ExtIterator::block_type, typename _ExtIterator::bids_container_iterator> buf_istream_type;
 typedef buf_ostream<typename _ExtIterator::block_type, typename _ExtIterator::bids_container_iterator> buf_ostream_type;

 _begin.flush(); // flush container

 // create prefetching stream,
 buf_istream_type in(_begin.bid(), _end.bid() + ((_end.block_offset()) ? 1 : 0), nbuffers / 2);
 // create buffered write stream for blocks
 buf_ostream_type out(_begin.bid(), nbuffers / 2);
 // REMARK: these two streams do I/O while
 // _functor is being computed (overlapping for free)

 _ExtIterator _cur = _begin - _begin.block_offset();

 // leave part of the block before _begin untouched (e.g. copy)
 for ( ; _cur != _begin; ++_cur)
 {
 typename _ExtIterator::value_type tmp;
 in >> tmp;
 out << tmp;
 }

 // apply _functor to the range [_begin,_end)
 for ( ; _cur != _end; ++_cur)
 {
 typename _ExtIterator::value_type tmp;
 in >> tmp;
 _functor(tmp);
 out << tmp;
 }

 // leave part of the block after _end untouched
 if (_end.block_offset())
 {
 _ExtIterator _last_block_end = _end - _end.block_offset() + _ExtIterator::block_type::size;
 for ( ; _cur != _last_block_end; ++_cur)
 {
 typename _ExtIterator::value_type tmp;
 in >> tmp;
 out << tmp;
 }
 }

 return _functor;
}


template <typename _ExtIterator, typename _Generator>
void generate(_ExtIterator _begin, _ExtIterator _end, _Generator _generator, int_type nbuffers)
{
 typedef typename _ExtIterator::block_type block_type;
 typedef buf_ostream<block_type, typename _ExtIterator::bids_container_iterator> buf_ostream_type;


 while (_begin.block_offset()) // go to the beginning of the block
 // of the external vector
 {
 if (_begin == _end)
 return;

 *_begin = _generator();
 ++_begin;
 }

 _begin.flush(); // flush container

 // create buffered write stream for blocks
 buf_ostream_type outstream(_begin.bid(), nbuffers);

 assert(_begin.block_offset() == 0);

 // delay calling block_externally_updated() until the block is
 // completely filled (and written out) in outstream
 typename _ExtIterator::const_iterator prev_block = _begin;

 while (_end != _begin)
 {
 if (_begin.block_offset() == 0) {
 if (prev_block != _begin) {
 prev_block.block_externally_updated();
 prev_block = _begin;
 }
 }

 *outstream = _generator();
 ++_begin;
 ++outstream;
 }

 typename _ExtIterator::const_iterator out = _begin;

 while (out.block_offset()) // filling the rest of the block
 {
 *outstream = *out;
 ++out;
 ++outstream;
 }

 if (prev_block != out)
 prev_block.block_externally_updated();

 _begin.flush();
}

template <typename _ExtIterator, typename _EqualityComparable>
_ExtIterator find(_ExtIterator _begin, _ExtIterator _end, const _EqualityComparable & _value, int_type nbuffers)
{
 if (_begin == _end)
 return _end;

 typedef buf_istream<typename _ExtIterator::block_type, typename _ExtIterator::bids_container_iterator> buf_istream_type;

 _begin.flush(); // flush container

 // create prefetching stream,
 buf_istream_type in(_begin.bid(), _end.bid() + ((_end.block_offset()) ? 1 : 0), nbuffers);

 _ExtIterator _cur = _begin - _begin.block_offset();

 // skip part of the block before _begin untouched
 for ( ; _cur != _begin; ++_cur)
 ++in;


 // search in the the range [_begin,_end)
 for ( ; _cur != _end; ++_cur)
 {
 typename _ExtIterator::value_type tmp;
 in >> tmp;
 if (tmp == _value)
 return _cur;
 }

 return _cur;
}


__STXXL_END_NAMESPACE

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