00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef STXXL_IN_MEMORY_SORT_HEADER
00014 #define STXXL_IN_MEMORY_SORT_HEADER
00015
00016 #include <stxxl/bits/namespace.h>
00017 #include <stxxl/bits/common/simple_vector.h>
00018 #include <stxxl/bits/algo/adaptor.h>
00019 #include <stxxl/bits/mng/adaptor.h>
00020
00021 #include <algorithm>
00022
00023
00024 __STXXL_BEGIN_NAMESPACE
00025
00026 template <typename ExtIterator_, typename StrictWeakOrdering_>
00027 void stl_in_memory_sort(ExtIterator_ first, ExtIterator_ last, StrictWeakOrdering_ cmp)
00028 {
00029 typedef typename ExtIterator_::vector_type::value_type value_type;
00030 typedef typename ExtIterator_::block_type block_type;
00031
00032 STXXL_VERBOSE("stl_in_memory_sort, range: " << (last - first));
00033 first.flush();
00034 unsigned_type nblocks = last.bid() - first.bid() + (last.block_offset() ? 1 : 0);
00035 simple_vector<block_type> blocks(nblocks);
00036 simple_vector<request_ptr> reqs(nblocks);
00037 unsigned_type i;
00038
00039 for (i = 0; i < nblocks; ++i)
00040 reqs[i] = blocks[i].read(*(first.bid() + i));
00041
00042
00043 wait_all(reqs.begin(), nblocks);
00044
00045 unsigned_type last_block_correction = last.block_offset() ? (block_type::size - last.block_offset()) : 0;
00046 std::sort(make_element_iterator(blocks.begin(), first.block_offset()),
00047 make_element_iterator(blocks.begin(), nblocks * block_type::size - last_block_correction),
00048 cmp);
00049
00050 for (i = 0; i < nblocks; ++i)
00051 reqs[i] = blocks[i].write(*(first.bid() + i));
00052
00053 wait_all(reqs.begin(), nblocks);
00054 }
00055
00056
00057 __STXXL_END_NAMESPACE
00058
00059 #endif // !STXXL_IN_MEMORY_SORT_HEADER