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 unsigned_type nblocks = last.bid() - first.bid() + (last.block_offset() ? 1 : 0);
00034 simple_vector<block_type> blocks(nblocks);
00035 simple_vector<request_ptr> reqs(nblocks);
00036 unsigned_type i;
00037
00038 for (i = 0; i < nblocks; ++i)
00039 reqs[i] = blocks[i].read(*(first.bid() + i));
00040
00041
00042 wait_all(reqs.begin(), nblocks);
00043
00044 unsigned_type last_block_correction = last.block_offset() ? (block_type::size - last.block_offset()) : 0;
00045 if (block_type::has_filler)
00046 std::sort(
00047 #if 1
00048 ArrayOfSequencesIterator<
00049 block_type, typename block_type::value_type, block_type::size
00050 >(blocks.begin(), first.block_offset()),
00051 ArrayOfSequencesIterator<
00052 block_type, typename block_type::value_type, block_type::size
00053 >(blocks.begin(), nblocks * block_type::size - last_block_correction),
00054 #else
00055 TwoToOneDimArrayRowAdaptor<
00056 block_type, typename block_type::value_type, block_type::size
00057 >(blocks.begin(), first.block_offset()),
00058 TwoToOneDimArrayRowAdaptor<
00059 block_type, typename block_type::value_type, block_type::size
00060 >(blocks.begin(), nblocks * block_type::size - last_block_correction),
00061 #endif
00062 cmp);
00063
00064 else
00065 std::sort(blocks[0].elem + first.block_offset(),
00066 blocks[nblocks].elem - last_block_correction, cmp);
00067
00068
00069 for (i = 0; i < nblocks; ++i)
00070 reqs[i] = blocks[i].write(*(first.bid() + i));
00071
00072
00073 wait_all(reqs.begin(), nblocks);
00074 }
00075
00076
00077 __STXXL_END_NAMESPACE
00078
00079 #endif // !STXXL_IN_MEMORY_SORT_HEADER