• Main Page
  • Related Pages
  • Modules
  • Namespaces
  • Classes
  • Files
  • Examples
  • File List

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     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

Generated on Sun Oct 17 2010 06:13:43 for Stxxl by  doxygen 1.7.1