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 }