Stxxl
1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/algo/scan.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2002-2004 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 00011 **************************************************************************/ 00012 00013 #ifndef STXXL_SCAN_HEADER 00014 #define STXXL_SCAN_HEADER 00015 00016 #include <stxxl/bits/namespace.h> 00017 #include <stxxl/bits/mng/buf_istream.h> 00018 #include <stxxl/bits/mng/buf_ostream.h> 00019 00020 00021 __STXXL_BEGIN_NAMESPACE 00022 00025 00035 template <typename _ExtIterator, typename _UnaryFunction> 00036 _UnaryFunction for_each(_ExtIterator _begin, _ExtIterator _end, _UnaryFunction _functor, int_type nbuffers) 00037 { 00038 typedef buf_istream<typename _ExtIterator::block_type, typename _ExtIterator::bids_container_iterator> buf_istream_type; 00039 00040 _begin.flush(); // flush container 00041 00042 // create prefetching stream, 00043 buf_istream_type in(_begin.bid(), _end.bid() + ((_end.block_offset()) ? 1 : 0), nbuffers / 2); 00044 00045 _ExtIterator _cur = _begin - _begin.block_offset(); 00046 00047 // leave part of the block before _begin untouched (e.g. copy) 00048 for ( ; _cur != _begin; ++_cur) 00049 { 00050 typename _ExtIterator::value_type tmp; 00051 in >> tmp; 00052 } 00053 00054 // apply _functor to the range [_begin,_end) 00055 for ( ; _cur != _end; ++_cur) 00056 { 00057 typename _ExtIterator::value_type tmp; 00058 in >> tmp; 00059 _functor(tmp); 00060 } 00061 00062 // leave part of the block after _end untouched 00063 if (_end.block_offset()) 00064 { 00065 _ExtIterator _last_block_end = _end - _end.block_offset() + _ExtIterator::block_type::size; 00066 for ( ; _cur != _last_block_end; ++_cur) 00067 { 00068 typename _ExtIterator::value_type tmp; 00069 in >> tmp; 00070 } 00071 } 00072 00073 return _functor; 00074 } 00075 00076 00086 template <typename _ExtIterator, typename _UnaryFunction> 00087 _UnaryFunction for_each_m(_ExtIterator _begin, _ExtIterator _end, _UnaryFunction _functor, int_type nbuffers) 00088 { 00089 typedef buf_istream<typename _ExtIterator::block_type, typename _ExtIterator::bids_container_iterator> buf_istream_type; 00090 typedef buf_ostream<typename _ExtIterator::block_type, typename _ExtIterator::bids_container_iterator> buf_ostream_type; 00091 00092 _begin.flush(); // flush container 00093 00094 // create prefetching stream, 00095 buf_istream_type in(_begin.bid(), _end.bid() + ((_end.block_offset()) ? 1 : 0), nbuffers / 2); 00096 // create buffered write stream for blocks 00097 buf_ostream_type out(_begin.bid(), nbuffers / 2); 00098 // REMARK: these two streams do I/O while 00099 // _functor is being computed (overlapping for free) 00100 00101 _ExtIterator _cur = _begin - _begin.block_offset(); 00102 00103 // leave part of the block before _begin untouched (e.g. copy) 00104 for ( ; _cur != _begin; ++_cur) 00105 { 00106 typename _ExtIterator::value_type tmp; 00107 in >> tmp; 00108 out << tmp; 00109 } 00110 00111 // apply _functor to the range [_begin,_end) 00112 for ( ; _cur != _end; ++_cur) 00113 { 00114 typename _ExtIterator::value_type tmp; 00115 in >> tmp; 00116 _functor(tmp); 00117 out << tmp; 00118 } 00119 00120 // leave part of the block after _end untouched 00121 if (_end.block_offset()) 00122 { 00123 _ExtIterator _last_block_end = _end - _end.block_offset() + _ExtIterator::block_type::size; 00124 for ( ; _cur != _last_block_end; ++_cur) 00125 { 00126 typename _ExtIterator::value_type tmp; 00127 in >> tmp; 00128 out << tmp; 00129 } 00130 } 00131 00132 return _functor; 00133 } 00134 00135 00142 template <typename _ExtIterator, typename _Generator> 00143 void generate(_ExtIterator _begin, _ExtIterator _end, _Generator _generator, int_type nbuffers) 00144 { 00145 typedef typename _ExtIterator::block_type block_type; 00146 typedef buf_ostream<block_type, typename _ExtIterator::bids_container_iterator> buf_ostream_type; 00147 00148 00149 while (_begin.block_offset()) // go to the beginning of the block 00150 // of the external vector 00151 { 00152 if (_begin == _end) 00153 return; 00154 00155 *_begin = _generator(); 00156 ++_begin; 00157 } 00158 00159 _begin.flush(); // flush container 00160 00161 // create buffered write stream for blocks 00162 buf_ostream_type outstream(_begin.bid(), nbuffers); 00163 00164 assert(_begin.block_offset() == 0); 00165 00166 while (_end != _begin) 00167 { 00168 if (_begin.block_offset() == 0) 00169 _begin.touch(); 00170 00171 *outstream = _generator(); 00172 ++_begin; 00173 ++outstream; 00174 } 00175 00176 typename _ExtIterator::const_iterator out = _begin; 00177 00178 while (out.block_offset()) // filling the rest of the block 00179 { 00180 *outstream = *out; 00181 ++out; 00182 ++outstream; 00183 } 00184 _begin.flush(); 00185 } 00186 00195 template <typename _ExtIterator, typename _EqualityComparable> 00196 _ExtIterator find(_ExtIterator _begin, _ExtIterator _end, const _EqualityComparable & _value, int_type nbuffers) 00197 { 00198 typedef buf_istream<typename _ExtIterator::block_type, typename _ExtIterator::bids_container_iterator> buf_istream_type; 00199 00200 _begin.flush(); // flush container 00201 00202 // create prefetching stream, 00203 buf_istream_type in(_begin.bid(), _end.bid() + ((_end.block_offset()) ? 1 : 0), nbuffers); 00204 00205 _ExtIterator _cur = _begin - _begin.block_offset(); 00206 00207 // skip part of the block before _begin untouched 00208 for ( ; _cur != _begin; ++_cur) 00209 ++in; 00210 00211 00212 // search in the the range [_begin,_end) 00213 for ( ; _cur != _end; ++_cur) 00214 { 00215 typename _ExtIterator::value_type tmp; 00216 in >> tmp; 00217 if (tmp == _value) 00218 return _cur; 00219 } 00220 00221 return _cur; 00222 } 00223 00225 00226 __STXXL_END_NAMESPACE 00227 00228 #endif // !STXXL_SCAN_HEADER