sorttest.cpp

Go to the documentation of this file.

#include <iostream>

#include "pairit.hh"

#include <boost/timer.hpp>
#include <boost/numeric/ublas/vector.hpp>
#include <boost/numeric/ublas/io.hpp>

using std::size_t;
using std::cout;
using std::endl;


using namespace boost::numeric::ublas;
using namespace iterators;

struct MyPairComparisonFunctor { 
  template<typename PairType> 
  bool operator()(const PairType& left,const PairType& right) const
  {
        return ( (left.first < right.first) ||
                         (left.first == right.first && left.second.first < right.second.first) );
  }
};
          
struct MyPairComparisonFunctor2 { 
  template<typename PairType> 
  bool operator()(const PairType& left,const PairType& right) const
  {
        return ( (left.first.first < right.first.first) ||
                         (left.first.first == right.first.first && left.first.second < right.first.second) );
  }
};
          
struct MyPairComparisonFunctor3 { 
  template<typename PairType> 
  bool operator()(const PairType& left,const PairType& right) const
  {
        return ( (left.first < right.first) ||
                         (left.first == right.first && left.second < right.second) );
  }
};
          
int main(size_t argc, char *argv[])
{
  size_t size = 20;

  if (argc > 1)
        size = ::atoi (argv [1]);

  typedef vector <size_t> V1;
  typedef vector <size_t> V2;
  typedef vector <long double> V3;

  V1 v1(size);
  V2 v2(size);
  V3 v3(size);

  for (size_t i=0; i<size; ++i) {
        v1(i) = (5*i+3) % size;
        v2(i) = (7*i+1) % size;
        v3(i) = i;
  }

  if (size < 200) {
        cout << v1 << endl;
        cout << v2 << endl;
        cout << v3 << endl;
  }

  boost::timer t;

  t.restart();
  std::stable_sort( makePairIterator(v1.begin(), makePairIterator(v2.begin(), v3.begin())),
                         makePairIterator(v1.end(), makePairIterator(v2.end(), v3.end())),
                         MyPairComparisonFunctor() );
//   std::stable_sort( makePairIterator(makePairIterator(v1.begin(), v2.begin()), v3.begin()),
//                                      makePairIterator(makePairIterator(v1.end(), v2.end()), v3.end()),
//                                      MyPairComparisonFunctor2() );
//   std::stable_sort( makePairIterator(v1.begin(), v2.begin()),
//                                      makePairIterator(v1.end(), v2.end()),
//                                      MyPairComparisonFunctor3() );

  cout << "sort time " << t.elapsed() << endl;

  if (size < 200) {
        cout << v1 << endl;
        cout << v2 << endl;
        cout << v3 << endl;
  }

  std::sort(v3.begin(), v3.end());
  bool ok = true;
  if (v3(0) == 0) {
        for (size_t i=1; i < size; ++i) {
          if ( (v1(i-1) > v1(i)) || 
                   (v1(i-1) == v1(i) && v2(i-1) > v2(i) ) ) {
                cout << "wrong order: " << i << endl;
                ok = false;
                break;
          }
          if (v3(i) != i) {
                ok = false;
                cout << "lost data: " << i << endl;
                break;
          }
        }
  } else {
        ok = false;
        cout << "lost data: 0" << endl;
  }

  cout << (ok?"ok":"not ok") << endl;

};

---