Stxxl  1.2.1
scan.h
1 /***************************************************************************
2  * include/stxxl/bits/algo/scan.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002-2004 Roman Dementiev <dementiev@mpi-sb.mpg.de>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_SCAN_HEADER
14 #define STXXL_SCAN_HEADER
15 
16 #include <stxxl/bits/namespace.h>
17 #include <stxxl/bits/mng/buf_istream.h>
18 #include <stxxl/bits/mng/buf_ostream.h>
19 
20 
21 __STXXL_BEGIN_NAMESPACE
22 
25 
35 template <typename _ExtIterator, typename _UnaryFunction>
36 _UnaryFunction for_each(_ExtIterator _begin, _ExtIterator _end, _UnaryFunction _functor, int_type nbuffers)
37 {
39 
40  _begin.flush(); // flush container
41 
42  // create prefetching stream,
43  buf_istream_type in(_begin.bid(), _end.bid() + ((_end.block_offset()) ? 1 : 0), nbuffers / 2);
44 
45  _ExtIterator _cur = _begin - _begin.block_offset();
46 
47  // leave part of the block before _begin untouched (e.g. copy)
48  for ( ; _cur != _begin; ++_cur)
49  {
50  typename _ExtIterator::value_type tmp;
51  in >> tmp;
52  }
53 
54  // apply _functor to the range [_begin,_end)
55  for ( ; _cur != _end; ++_cur)
56  {
57  typename _ExtIterator::value_type tmp;
58  in >> tmp;
59  _functor(tmp);
60  }
61 
62  // leave part of the block after _end untouched
63  if (_end.block_offset())
64  {
65  _ExtIterator _last_block_end = _end - _end.block_offset() + _ExtIterator::block_type::size;
66  for ( ; _cur != _last_block_end; ++_cur)
67  {
68  typename _ExtIterator::value_type tmp;
69  in >> tmp;
70  }
71  }
72 
73  return _functor;
74 }
75 
76 
86 template <typename _ExtIterator, typename _UnaryFunction>
87 _UnaryFunction for_each_m(_ExtIterator _begin, _ExtIterator _end, _UnaryFunction _functor, int_type nbuffers)
88 {
91 
92  _begin.flush(); // flush container
93 
94  // create prefetching stream,
95  buf_istream_type in(_begin.bid(), _end.bid() + ((_end.block_offset()) ? 1 : 0), nbuffers / 2);
96  // create buffered write stream for blocks
97  buf_ostream_type out(_begin.bid(), nbuffers / 2);
98  // REMARK: these two streams do I/O while
99  // _functor is being computed (overlapping for free)
100 
101  _ExtIterator _cur = _begin - _begin.block_offset();
102 
103  // leave part of the block before _begin untouched (e.g. copy)
104  for ( ; _cur != _begin; ++_cur)
105  {
106  typename _ExtIterator::value_type tmp;
107  in >> tmp;
108  out << tmp;
109  }
110 
111  // apply _functor to the range [_begin,_end)
112  for ( ; _cur != _end; ++_cur)
113  {
114  typename _ExtIterator::value_type tmp;
115  in >> tmp;
116  _functor(tmp);
117  out << tmp;
118  }
119 
120  // leave part of the block after _end untouched
121  if (_end.block_offset())
122  {
123  _ExtIterator _last_block_end = _end - _end.block_offset() + _ExtIterator::block_type::size;
124  for ( ; _cur != _last_block_end; ++_cur)
125  {
126  typename _ExtIterator::value_type tmp;
127  in >> tmp;
128  out << tmp;
129  }
130  }
131 
132  return _functor;
133 }
134 
135 
142 template <typename _ExtIterator, typename _Generator>
143 void generate(_ExtIterator _begin, _ExtIterator _end, _Generator _generator, int_type nbuffers)
144 {
145  typedef typename _ExtIterator::block_type block_type;
147 
148 
149  while (_begin.block_offset()) // go to the beginning of the block
150  // of the external vector
151  {
152  if (_begin == _end)
153  return;
154 
155  *_begin = _generator();
156  ++_begin;
157  }
158 
159  _begin.flush(); // flush container
160 
161  // create buffered write stream for blocks
162  buf_ostream_type outstream(_begin.bid(), nbuffers);
163 
164  assert(_begin.block_offset() == 0);
165 
166  while (_end != _begin)
167  {
168  if (_begin.block_offset() == 0)
169  _begin.touch();
170 
171  *outstream = _generator();
172  ++_begin;
173  ++outstream;
174  }
175 
176  typename _ExtIterator::const_iterator out = _begin;
177 
178  while (out.block_offset()) // filling the rest of the block
179  {
180  *outstream = *out;
181  ++out;
182  ++outstream;
183  }
184  _begin.flush();
185 }
186 
195 template <typename _ExtIterator, typename _EqualityComparable>
196 _ExtIterator find(_ExtIterator _begin, _ExtIterator _end, const _EqualityComparable & _value, int_type nbuffers)
197 {
199 
200  _begin.flush(); // flush container
201 
202  // create prefetching stream,
203  buf_istream_type in(_begin.bid(), _end.bid() + ((_end.block_offset()) ? 1 : 0), nbuffers);
204 
205  _ExtIterator _cur = _begin - _begin.block_offset();
206 
207  // skip part of the block before _begin untouched
208  for ( ; _cur != _begin; ++_cur)
209  ++in;
210 
211 
212  // search in the the range [_begin,_end)
213  for ( ; _cur != _end; ++_cur)
214  {
215  typename _ExtIterator::value_type tmp;
216  in >> tmp;
217  if (tmp == _value)
218  return _cur;
219  }
220 
221  return _cur;
222 }
223 
225 
226 __STXXL_END_NAMESPACE
227 
228 #endif // !STXXL_SCAN_HEADER