stream/test_push_sort.cpp

This is an example of how to use some basic algorithms from stream package. This example shows how to create sorted_runs data structure using stream::use_push specialization of stream::runs_creator class

00001 /***************************************************************************
00002  *  stream/test_push_sort.cpp
00003  *
00004  *  Part of the STXXL. See http://stxxl.sourceforge.net
00005  *
00006  *  Copyright (C) 2004 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 
00025 struct Cmp : public std::binary_function<value_type, value_type, bool>
00026 {
00027     typedef unsigned value_type;
00028     bool operator () (const value_type & a, const value_type & b) const
00029     {
00030         return a < b;
00031     }
00032     value_type min_value()
00033     {
00034         return (std::numeric_limits<value_type>::min)();
00035     }
00036     value_type max_value()
00037     {
00038         return (std::numeric_limits<value_type>::max)();
00039     }
00040 };
00041 
00042 int main()
00043 {
00044     // special parameter type
00045     typedef stxxl::stream::use_push<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         const value_type tmp = rnd();
00063         oldcrc += tmp;
00064         SortedRuns.push(tmp);                   // push into the sorter
00065         --cnt;
00066     }
00067 
00068     SortedRunsType Runs = SortedRuns.result();  // get sorted_runs data structure
00069     assert(stxxl::stream::check_sorted_runs(Runs, Cmp()));
00070 
00071     // merge the runs
00072     stxxl::stream::runs_merger<SortedRunsType, Cmp> merger(Runs, Cmp(), 1024 * 128 / 10 * stxxl::sort_memory_usage_factor());
00073     stxxl::vector<value_type> array;
00074     STXXL_MSG(size << " " << Runs.elements);
00075     STXXL_MSG("CRC: " << oldcrc);
00076     value_type crc(0);
00077     for (i = 0; i < size; ++i)
00078     {
00079         crc += *merger;
00080         array.push_back(*merger);
00081         ++merger;
00082     }
00083     STXXL_MSG("CRC: " << crc);
00084     assert(stxxl::is_sorted(array.begin(), array.end(), Cmp()));
00085     assert(merger.empty());
00086 
00087     return 0;
00088 }

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