inmemsort.h

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

Generated on Thu Jun 4 10:30:00 2009 for Stxxl by  doxygen 1.4.7