algo/test_ksort.cpp

This is an example of how to use stxxl::ksort() algorithm

00001 /***************************************************************************
00002  *  algo/test_ksort.cpp
00003  *
00004  *  Part of the STXXL. See http://stxxl.sourceforge.net
00005  *
00006  *  Copyright (C) 2002 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 
00015 
00016 #include <stxxl/mng>
00017 #include <stxxl/ksort>
00018 #include <stxxl/vector>
00019 
00020 
00021 struct my_type
00022 {
00023     typedef stxxl::uint64 key_type1;
00024 
00025     key_type1 _key;
00026     key_type1 _key_copy;
00027     char _data[32 - 2 * sizeof(key_type1)];
00028     key_type1 key() const
00029     {
00030         return _key;
00031     }
00032 
00033     my_type() : _key(0), _key_copy(0) { }
00034     my_type(key_type1 __key) : _key(__key) { }
00035 
00036     my_type min_value() const { return my_type((std::numeric_limits<key_type1>::min)()); }
00037     my_type max_value() const { return my_type((std::numeric_limits<key_type1>::max)()); }
00038 };
00039 
00040 std::ostream & operator << (std::ostream & o, const my_type & obj)
00041 {
00042     o << obj._key << " " << obj._key_copy;
00043     return o;
00044 }
00045 
00046 struct get_key
00047 {
00048     typedef my_type::key_type1 key_type;
00049     my_type dummy;
00050     key_type operator () (const my_type & obj) const
00051     {
00052         return obj._key;
00053     }
00054     my_type min_value() const
00055     {
00056         return my_type((dummy.min_value)());
00057     }
00058     my_type max_value() const
00059     {
00060         return my_type((dummy.max_value)());
00061     }
00062 };
00063 
00064 
00065 bool operator < (const my_type & a, const my_type & b)
00066 {
00067     return a.key() < b.key();
00068 }
00069 
00070 int main()
00071 {
00072     STXXL_MSG("Check config...");
00073     try {
00074         stxxl::block_manager::get_instance();
00075     }
00076     catch (std::exception & e)
00077     {
00078         STXXL_MSG("Exception: " << e.what());
00079         abort();
00080     }
00081     unsigned memory_to_use = 32 * 1024 * 1024;
00082     typedef stxxl::VECTOR_GENERATOR<my_type, 4, 4>::result vector_type;
00083     const stxxl::int64 n_records = 3 * 32 * stxxl::int64(1024 * 1024) / sizeof(my_type);
00084     vector_type v(n_records);
00085 
00086     stxxl::random_number32 rnd;
00087     STXXL_MSG("Filling vector... ");
00088     for (vector_type::size_type i = 0; i < v.size(); i++)
00089     {
00090         v[i]._key = rnd() + 1;
00091         v[i]._key_copy = v[i]._key;
00092     }
00093 
00094     STXXL_MSG("Checking order...");
00095     STXXL_MSG(((stxxl::is_sorted(v.begin(), v.end())) ? "OK" : "WRONG"));
00096 
00097     STXXL_MSG("Sorting...");
00098     stxxl::ksort(v.begin(), v.end(), get_key(), memory_to_use);
00099     //stxxl::ksort(v.begin(),v.end(),memory_to_use);
00100 
00101 
00102     STXXL_MSG("Checking order...");
00103     STXXL_MSG(((stxxl::is_sorted(v.begin(), v.end())) ? "OK" : "WRONG"));
00104     STXXL_MSG("Checking content...");
00105     my_type prev;
00106     for (vector_type::size_type i = 0; i < v.size(); i++)
00107     {
00108         if (v[i]._key != v[i]._key_copy)
00109         {
00110             STXXL_MSG("Bug at position " << i);
00111             abort();
00112         }
00113         if (i > 0 && prev._key == v[i]._key)
00114         {
00115             STXXL_MSG("Duplicate at position " << i << " key=" << v[i]._key);
00116             //abort();
00117         }
00118         prev = v[i];
00119     }
00120     STXXL_MSG("OK");
00121 
00122     return 0;
00123 }

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