[03e621]: include / stxxl / bits / containers / sorter.h  Maximize  Restore  History

Download this file

282 lines (224 with data), 7.6 kB

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
/***************************************************************************
* include/stxxl/bits/containers/sorter.h
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2012 Timo Bingmann <tb@panthema.net>
*
* 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_CONTAINERS_SORTER_HEADER
#define STXXL_CONTAINERS_SORTER_HEADER
#include <stxxl/bits/deprecated.h>
#include <stxxl/bits/stream/sort_stream.h>
STXXL_BEGIN_NAMESPACE
#ifndef STXXL_VERBOSE_SORTER
#define STXXL_VERBOSE_SORTER STXXL_VERBOSE2
#endif
//! \addtogroup stlcont
//! \{
//! External sorter container. \n
//! <b> Introduction </b> to sorter container: see \ref tutorial_sorter tutorial. \n
//! <b> Design and Internals </b> of sorter container: see \ref design_sorter
/**
* \brief External Sorter: use stream package objects to keep a sorted
* container.
*
* This sorter container combines the two functions of runs_creator and
* runs_merger from the stream packages into a two-phase container.
*
* In the first phase the container is filled with unordered items via push(),
* which are presorted internally into runs of size M. When the internal memory
* overflows a runs is written to external memory in blocks of block_size.
*
* When sort() is called the container enters the output phase and push() is
* disallowed. After calling sort() the items can be read in sorted order using
* operator*() to get the top item, operator++() to advance to the next one and
* empty() to check for end of stream. This is exactly the stream interface.
*
* In the output phase the sorter can be returned to the beginning of the
* stream using rewind() and everything is read again in sorted order.
*
* Using clear() the object can be reset into input state and all items are
* destroyed.
*
* Added in STXXL 1.4
*
* \tparam ValueType type of the contained objects (POD with no references to internal memory)
* \tparam CompareType type of comparison object used for sorting the runs
* \tparam BlockSize size of the external memory block in bytes, default is \c STXXL_DEFAULT_BLOCK_SIZE(ValTp)
* \tparam AllocStr parallel disk allocation strategy, default is \c STXXL_DEFAULT_ALLOC_STRATEGY
*/
template <typename ValueType,
typename CompareType,
unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType),
class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
class sorter : private noncopyable
{
public:
// *** Template Parameters
typedef ValueType value_type;
typedef CompareType cmp_type;
enum {
block_size = BlockSize
};
typedef AllocStrategy alloc_strategy_type;
// *** Constructed Types
//! runs creator type with push() method
typedef stream::runs_creator<stream::use_push<ValueType>, cmp_type,
block_size, alloc_strategy_type> runs_creator_type;
//! corresponding runs merger type
typedef stream::runs_merger<typename runs_creator_type::sorted_runs_type,
cmp_type, alloc_strategy_type> runs_merger_type;
protected:
// *** Object Attributes
//! current state of sorter
enum { STATE_INPUT, STATE_OUTPUT } m_state;
//! runs creator object holding all items
runs_creator_type m_runs_creator;
//! runs merger reading items when in STATE_OUTPUT
runs_merger_type m_runs_merger;
public:
//! \name Constructors
//! \{
//! Constructor allocation memory_to_use bytes in ram for sorted runs.
sorter(const cmp_type& cmp, unsigned_type memory_to_use)
: m_state(STATE_INPUT),
m_runs_creator(cmp, memory_to_use),
m_runs_merger(cmp, memory_to_use)
{ }
//! Constructor variant with differently sizes runs_creator and runs_merger
sorter(const cmp_type& cmp, unsigned_type creator_memory_to_use, unsigned_type merger_memory_to_use)
: m_state(STATE_INPUT),
m_runs_creator(cmp, creator_memory_to_use),
m_runs_merger(cmp, merger_memory_to_use)
{ }
//! \}
//! \name Modifiers
//! \{
//! Remove all items and return to input state.
void clear()
{
if (m_state == STATE_OUTPUT)
m_runs_merger.deallocate();
m_runs_creator.allocate();
m_state = STATE_INPUT;
}
//! Push another item (only callable during input state).
void push(const value_type& val)
{
assert(m_state == STATE_INPUT);
m_runs_creator.push(val);
}
//! \}
//! \name Modus
//! \{
//! Finish push input state and deallocate input buffer.
void finish()
{
if (m_state == STATE_OUTPUT)
{
m_runs_merger.deallocate();
}
m_runs_creator.deallocate();
}
//! Deallocate buffers and clear result.
void finish_clear()
{
if (m_state == STATE_OUTPUT)
{
m_runs_merger.deallocate();
m_runs_creator.result()->clear();
}
m_runs_creator.deallocate();
}
//! \}
//! \name Modifiers
//! \{
//! Switch to output state, rewind() in case the output was already sorted.
void sort()
{
if (m_state == STATE_OUTPUT)
{
m_runs_merger.deallocate();
}
m_runs_creator.deallocate();
m_runs_merger.initialize(m_runs_creator.result());
m_state = STATE_OUTPUT;
}
//! Switch to output state, rewind() in case the output was already sorted.
void sort(unsigned_type merger_memory_to_use)
{
m_runs_merger.set_memory_to_use(merger_memory_to_use);
sort();
}
//! \}
//! \name Modus
//! \{
//! Switch to output state, rewind() in case the output was already sorted.
void sort_reuse()
{
assert(m_state == STATE_INPUT);
m_runs_merger.initialize(m_runs_creator.result());
m_state = STATE_OUTPUT;
}
//! Rewind output stream to beginning.
void rewind()
{
assert(m_state == STATE_OUTPUT);
m_runs_merger.deallocate();
m_state = STATE_INPUT;
return sort();
}
//! \}
//! Change runs_merger memory usage
void set_merger_memory_to_use(unsigned_type merger_memory_to_use)
{
m_runs_merger.set_memory_to_use(merger_memory_to_use);
}
//! \}
//! \name Capacity
//! \{
//! Number of items pushed or items remaining to be read.
unsigned_type size() const
{
if (m_state == STATE_INPUT)
return m_runs_creator.size();
else
return m_runs_merger.size();
}
//! Standard stream method
bool empty() const
{
assert(m_state == STATE_OUTPUT);
return m_runs_merger.empty();
}
//! \}
//! \name Operators
//! \{
//! Standard stream method
const value_type& operator * () const
{
assert(m_state == STATE_OUTPUT);
return *m_runs_merger;
}
//! Standard stream method
const value_type* operator -> () const
{
return &(operator * ());
}
//! Standard stream method (preincrement operator)
sorter& operator ++ ()
{
assert(m_state == STATE_OUTPUT);
++m_runs_merger;
return *this;
}
//! \}
};
//! \}
STXXL_END_NAMESPACE
#endif // !STXXL_CONTAINERS_SORTER_HEADER
// vim: et:ts=4:sw=4

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.





No, thanks