stream/test_stream.cpp

This is an example of how to use some basic algorithms from the stream package. The example sorts characters of a string producing an array of sorted tuples (character, index position).

00001 /***************************************************************************
00002  *  stream/test_stream.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 
00017 
00018 #include <vector>
00019 #include <stxxl/stream>
00020 #include <stxxl/vector>
00021 
00022 
00023 #define USE_FORMRUNS_N_MERGE    // comment if you want to use one 'sort' algorithm
00024                                 // without producing intermediate sorted runs.
00025 
00026 #define USE_EXTERNAL_ARRAY      // comment if you want to use internal vectors as
00027                                 // input/output of the algorithm
00028 
00029 #define block_size (8 * 1024)
00030 
00031 typedef stxxl::tuple<char, int> tuple_type;
00032 
00033 namespace std
00034 {
00035     std::ostream & operator << (std::ostream & os, const tuple_type & t)
00036     {
00037         os << "<" << t.first << "," << t.second << ">";
00038         return os;
00039     }
00040 }
00041 
00042 #ifdef USE_EXTERNAL_ARRAY
00043 typedef stxxl::VECTOR_GENERATOR<char>::result input_array_type;
00044 typedef stxxl::VECTOR_GENERATOR<tuple_type>::result output_array_type;
00045 #else
00046 typedef std::vector<char> input_array_type;
00047 typedef std::vector<tuple_type> output_array_type;
00048 #endif
00049 
00050 using stxxl::stream::streamify;
00051 using stxxl::stream::streamify_traits;
00052 using stxxl::stream::make_tuple;
00053 using stxxl::tuple;
00054 
00055 
00056 const char * phrase = "Hasta la vista, baby";
00057 
00058 
00059 template <class Container_, class It_>
00060 void fill_input_array(Container_ & container, It_ p)
00061 {
00062     while (*p)
00063     {
00064         container.push_back(*p);
00065         ++p;
00066     }
00067 }
00068 
00069 template <class ValTp>
00070 struct counter
00071 {
00072     typedef ValTp value_type;
00073 
00074     value_type cnt;
00075     counter() : cnt(0) { }
00076 
00077     value_type operator () ()
00078     {
00079         value_type ret = cnt;
00080         ++cnt;
00081         return ret;
00082     }
00083 };
00084 
00085 typedef counter<int> counter_type;
00086 
00087 struct cmp_type : std::binary_function<tuple_type, tuple_type, bool>
00088 {
00089     typedef tuple_type value_type;
00090     bool operator () (const value_type & a, const value_type & b) const
00091     {
00092         return a.first < b.first;
00093     }
00094 
00095     value_type min_value() const
00096     {
00097         return value_type((std::numeric_limits<char>::min)(), 0);
00098     }
00099     value_type max_value() const
00100     {
00101         return value_type((std::numeric_limits<char>::max)(), 0);
00102     }
00103 };
00104 
00105 struct cmp_int : std::binary_function<int, int, bool>
00106 {
00107     typedef int value_type;
00108     bool operator () (const value_type & a, const value_type & b) const
00109     {
00110         return a > b;
00111     }
00112 
00113     value_type max_value() const
00114     {
00115         return (((std::numeric_limits<value_type>::min))());
00116     }
00117     value_type min_value() const
00118     {
00119         return (((std::numeric_limits<value_type>::max))());
00120     }
00121 };
00122 
00123 int main()
00124 {
00125     input_array_type input;
00126     output_array_type output;
00127 
00128     stxxl::stats * s = stxxl::stats::get_instance();
00129 
00130     std::cout << *s;
00131 
00132     fill_input_array(input, phrase);
00133 
00134     output.resize(input.size());
00135 
00136     // HERE streaming part begins (streamifying)
00137     // create input stream
00138 #ifdef BOOST_MSVC
00139     typedef streamify_traits<input_array_type::iterator>::stream_type input_stream_type;
00140 #else
00141     typedef __typeof__(streamify(input.begin(), input.end())) input_stream_type;
00142 #endif
00143 
00144     input_stream_type input_stream = streamify(input.begin(), input.end());
00145 
00146 
00147     // create counter stream
00148 #ifdef BOOST_MSVC
00149     typedef stxxl::stream::generator2stream<counter_type> counter_stream_type;
00150 #else
00151     typedef __typeof__(streamify(counter_type())) counter_stream_type;
00152 #endif
00153     counter_stream_type counter_stream = streamify(counter_type());
00154 
00155     // create tuple stream
00156     typedef make_tuple<input_stream_type, counter_stream_type> tuple_stream_type;
00157     tuple_stream_type tuple_stream(input_stream, counter_stream);
00158 
00159 #ifdef USE_FORMRUNS_N_MERGE
00160     // sort tuples by character
00161     // 1. form runs
00162     typedef stxxl::stream::runs_creator<tuple_stream_type, cmp_type, block_size> runs_creator_stream_type;
00163     runs_creator_stream_type runs_creator_stream(tuple_stream, cmp_type(), 128 * 1024);
00164     // 2. merge runs
00165     typedef stxxl::stream::runs_merger<runs_creator_stream_type::sorted_runs_type, cmp_type> runs_merger_stream_type;
00166     runs_merger_stream_type sorted_stream(runs_creator_stream.result(), cmp_type(), 128 * 1024);
00167 #else
00168     // sort tuples by character
00169     // (combination of the previous two steps in one algorithm: form runs and merge)
00170     typedef stxxl::stream::sort<tuple_stream_type, cmp_type, block_size> sorted_stream_type;
00171     sorted_stream_type sorted_stream(tuple_stream, cmp_type(), 128 * 1024);
00172 #endif
00173 
00174     // HERE streaming part ends (materializing)
00175     output_array_type::iterator o = stxxl::stream::materialize(sorted_stream, output.begin(), output.end());
00176     // or materialize(sorted_stream,output.begin());
00177     assert(o == output.end());
00178 
00179 
00180     STXXL_MSG("input string (character,position) :");
00181     for (unsigned i = 0; i < input.size(); ++i)
00182     {
00183         STXXL_MSG("('" << input[i] << "'," << i << ")");
00184     }
00185     STXXL_MSG("sorted tuples (character,position):");
00186     for (unsigned i = 0; i < input.size(); ++i)
00187     {
00188         STXXL_MSG("('" << output[i].first << "'," << output[i].second << ")");
00189     }
00190 
00191     std::cout << *s;
00192 
00193     std::vector<int> InternalArray(1024 * 1024);
00194     std::sort(InternalArray.begin(), InternalArray.end(), cmp_int());
00195     stxxl::sort<1024 * 1024>(InternalArray.begin(), InternalArray.end(),
00196                              cmp_int(), 1024 * 1024 * 10, stxxl::RC());
00197 }

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