Stxxl 1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/algo/inmemsort.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2003 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 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