Stxxl  1.2.1
inmemsort.h
1 /***************************************************************************
2  * include/stxxl/bits/algo/inmemsort.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2003 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_IN_MEMORY_SORT_HEADER
14 #define STXXL_IN_MEMORY_SORT_HEADER
15 
16 #include <stxxl/bits/namespace.h>
17 #include <stxxl/bits/common/simple_vector.h>
18 #include <stxxl/bits/algo/adaptor.h>
19 #include <stxxl/bits/mng/adaptor.h>
20 
21 #include <algorithm>
22 
23 
24 __STXXL_BEGIN_NAMESPACE
25 
26 template <typename ExtIterator_, typename StrictWeakOrdering_>
27 void stl_in_memory_sort(ExtIterator_ first, ExtIterator_ last, StrictWeakOrdering_ cmp)
28 {
29  typedef typename ExtIterator_::vector_type::value_type value_type;
30  typedef typename ExtIterator_::block_type block_type;
31 
32  STXXL_VERBOSE("stl_in_memory_sort, range: " << (last - first));
33  unsigned_type nblocks = last.bid() - first.bid() + (last.block_offset() ? 1 : 0);
34  simple_vector<block_type> blocks(nblocks);
35  simple_vector<request_ptr> reqs(nblocks);
36  unsigned_type i;
37 
38  for (i = 0; i < nblocks; ++i)
39  reqs[i] = blocks[i].read(*(first.bid() + i));
40 
41 
42  wait_all(reqs.begin(), nblocks);
43 
44  unsigned_type last_block_correction = last.block_offset() ? (block_type::size - last.block_offset()) : 0;
45  if (block_type::has_filler)
46  std::sort(
47 #if 1
48  ArrayOfSequencesIterator<
49  block_type, typename block_type::value_type, block_type::size
50  >(blocks.begin(), first.block_offset()),
51  ArrayOfSequencesIterator<
52  block_type, typename block_type::value_type, block_type::size
53  >(blocks.begin(), nblocks * block_type::size - last_block_correction),
54 #else
55  TwoToOneDimArrayRowAdaptor<
56  block_type, typename block_type::value_type, block_type::size
57  >(blocks.begin(), first.block_offset()),
58  TwoToOneDimArrayRowAdaptor<
59  block_type, typename block_type::value_type, block_type::size
60  >(blocks.begin(), nblocks * block_type::size - last_block_correction),
61 #endif
62  cmp);
63 
64  else
65  std::sort(blocks[0].elem + first.block_offset(),
66  blocks[nblocks].elem - last_block_correction, cmp);
67 
68 
69  for (i = 0; i < nblocks; ++i)
70  reqs[i] = blocks[i].write(*(first.bid() + i));
71 
72 
73  wait_all(reqs.begin(), nblocks);
74 }
75 
76 
77 __STXXL_END_NAMESPACE
78 
79 #endif // !STXXL_IN_MEMORY_SORT_HEADER