stream/test_sorted_runs.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 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 }

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