sorted_runs
data structure from sorted sequences using stream::from_sorted_sequences
specialization of stream::runs_creator
class
00001 /*************************************************************************** 00002 * stream/test_sorted_runs.cpp 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 00018 00019 #include <stxxl/stream> 00020 00021 00022 typedef unsigned value_type; 00023 00024 struct Cmp : public std::binary_function<value_type, value_type, bool> 00025 { 00026 typedef unsigned value_type; 00027 bool operator () (const value_type & a, const value_type & b) const 00028 { 00029 return a < b; 00030 } 00031 value_type min_value() 00032 { 00033 return (std::numeric_limits<value_type>::min)(); 00034 } 00035 value_type max_value() 00036 { 00037 return (std::numeric_limits<value_type>::max)(); 00038 } 00039 }; 00040 00041 00042 int main() 00043 { 00044 // special parameter type 00045 typedef stxxl::stream::from_sorted_sequences<value_type> InputType; 00046 typedef stxxl::stream::runs_creator<InputType, Cmp, 4096, stxxl::RC> CreateRunsAlg; 00047 typedef CreateRunsAlg::sorted_runs_type SortedRunsType; 00048 00049 unsigned size = 30 * 1024 * 128 / (sizeof(value_type) * 2); 00050 00051 unsigned i = 0; 00052 00053 Cmp c; 00054 CreateRunsAlg SortedRuns(c, 1024 * 128); 00055 value_type oldcrc(0); 00056 00057 stxxl::random_number32 rnd; 00058 stxxl::random_number<> rnd_max; 00059 unsigned cnt = size; 00060 while (cnt > 0) 00061 { 00062 unsigned run_size = rnd_max(cnt) + 1; // random run length 00063 cnt -= run_size; 00064 STXXL_MSG("current run size:" << run_size); 00065 00066 std::vector<unsigned> tmp(run_size); // create temp storage for current run 00067 std::generate(tmp.begin(), tmp.end(), rnd); // fill with random numbers 00068 std::sort(tmp.begin(), tmp.end(), c); // sort 00069 for (unsigned j = 0; j < run_size; ++j) 00070 { 00071 oldcrc += tmp[j]; 00072 SortedRuns.push(tmp[j]); // push sorted values to the current run 00073 } 00074 SortedRuns.finish(); // finish current run 00075 } 00076 00077 00078 SortedRunsType Runs = SortedRuns.result(); // get sorted_runs data structure 00079 assert(check_sorted_runs(Runs, Cmp())); 00080 // merge the runs 00081 stxxl::stream::runs_merger<SortedRunsType, Cmp> merger(Runs, Cmp(), 1024 * 128 / 10 * stxxl::sort_memory_usage_factor()); 00082 stxxl::vector<value_type> array; 00083 STXXL_MSG(size << " " << Runs.elements); 00084 STXXL_MSG("CRC: " << oldcrc); 00085 value_type crc(0); 00086 for (i = 0; i < size; ++i) 00087 { 00088 crc += *merger; 00089 array.push_back(*merger); 00090 ++merger; 00091 } 00092 STXXL_MSG("CRC: " << crc); 00093 assert(stxxl::is_sorted(array.begin(), array.end(), Cmp())); 00094 assert(merger.empty()); 00095 00096 return 0; 00097 }