source: lemon-main/test/radix_sort_test.cc @ 1048:dbaf21739390

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2009
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <lemon/time_measure.h>
#include <lemon/smart_graph.h>
#include <lemon/maps.h>
#include <lemon/radix_sort.h>
#include <lemon/math.h>

#include "test_tools.h"

#include <vector>
#include <list>
#include <algorithm>

using namespace lemon;

static const int n = 10000;

struct Negate {
  typedef int argument_type;
  typedef int result_type;
  int operator()(int a) { return - a; }
};

int negate(int a) { return - a; }

template<class T>
bool isTheSame(T &a, T&b)
{
  typename T::iterator ai=a.begin();
  typename T::iterator bi=b.begin();
  for(;ai!=a.end()||bi!=b.end();++ai,++bi)
    if(*ai!=*bi) return false;
  return ai==a.end()&&bi==b.end();
}

template<class T>
T listsort(typename T::iterator b, typename T::iterator e)
{ 
  if(b==e) return T();
  typename T::iterator bn=b;
  if(++bn==e) {
    T l;
    l.push_back(*b);
    return l;
  }
  typename T::iterator m=b;
  bool x=false;
  for(typename T::iterator i=b;i!=e;++i,x=!x)
    if(x) ++m;
  T l1(listsort<T>(b,m));
  T l2(listsort<T>(m,e));
  T l;
  while((!l1.empty())&&(!l2.empty()))
    if(l1.front()<=l2.front())
      {
        l.push_back(l1.front());
        l1.pop_front();
      }
    else {
      l.push_back(l2.front());
      l2.pop_front();
    }
  while(!l1.empty())
    {
      l.push_back(l1.front());
      l1.pop_front();
    }
  while(!l2.empty())
    {
      l.push_back(l2.front());
      l2.pop_front();
    }
  return l;
}

template<class T>
void generateIntSequence(int n, T & data) {
  int prime = 9973;
  int root = 136, value = 1;
  for (int i = 0; i < n; ++i) {
    data.push_back(value - prime / 2);
    value = (value * root) % prime;
  }
}

template<class T>
void generateCharSequence(int n, T & data) {
  int prime = 251;
  int root = 3, value = root;
  for (int i = 0; i < n; ++i) {
    data.push_back(static_cast<unsigned char>(value));
    value = (value * root) % prime;
  }
}

void checkRadixSort() {
  {
    std::vector<int> data1;
    generateIntSequence(n, data1);

    std::vector<int> data2(data1);
    std::sort(data1.begin(), data1.end());

    radixSort(data2.begin(), data2.end());
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[i], "Test failed");
    }

    // radixSort(data2.begin(), data2.end(), Negate());
    // for (int i = 0; i < n; ++i) {
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
    // }

    // radixSort(data2.begin(), data2.end(), negate);
    // for (int i = 0; i < n; ++i) {
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
    // }

  }

  {
    std::vector<unsigned char> data1(n);
    generateCharSequence(n, data1);

    std::vector<unsigned char> data2(data1);
    std::sort(data1.begin(), data1.end());

    radixSort(data2.begin(), data2.end());
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[i], "Test failed");
    }

  }
  {
    std::list<int> data1;
    generateIntSequence(n, data1);

    std::list<int> data2(listsort<std::list<int> >(data1.begin(), data1.end()));

    radixSort(data1.begin(), data1.end());

    check(isTheSame(data1,data2), "Test failed");


    // radixSort(data2.begin(), data2.end(), Negate());
    // check(isTheSame(data1,data2), "Test failed");
    // for (int i = 0; i < n; ++i) {
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
    // }

    // radixSort(data2.begin(), data2.end(), negate);
    // for (int i = 0; i < n; ++i) {
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
    // }

  }

  {
    std::list<unsigned char> data1(n);
    generateCharSequence(n, data1);

    std::list<unsigned char> data2(listsort<std::list<unsigned char> >
                                   (data1.begin(),
                                    data1.end()));

    radixSort(data1.begin(), data1.end());
    check(isTheSame(data1,data2), "Test failed");

  }
}


void checkStableRadixSort() {
  {
    std::vector<int> data1;
    generateIntSequence(n, data1);

    std::vector<int> data2(data1);
    std::sort(data1.begin(), data1.end());

    stableRadixSort(data2.begin(), data2.end());
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[i], "Test failed");
    }

    stableRadixSort(data2.begin(), data2.end(), Negate());
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[n - 1 - i], "Test failed");
    }

    stableRadixSort(data2.begin(), data2.end(), negate);
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[n - 1 - i], "Test failed");
    }
  }

  {
    std::vector<unsigned char> data1(n);
    generateCharSequence(n, data1);

    std::vector<unsigned char> data2(data1);
    std::sort(data1.begin(), data1.end());

    radixSort(data2.begin(), data2.end());
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[i], "Test failed");
    }

  }
  {
    std::list<int> data1;
    generateIntSequence(n, data1);

    std::list<int> data2(listsort<std::list<int> >(data1.begin(),
                                                   data1.end()));
    stableRadixSort(data1.begin(), data1.end());
    check(isTheSame(data1,data2), "Test failed");

    // stableRadixSort(data2.begin(), data2.end(), Negate());
    // for (int i = 0; i < n; ++i) {
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
    // }

    // stableRadixSort(data2.begin(), data2.end(), negate);
    // for (int i = 0; i < n; ++i) {
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
    // }
  }

  {
    std::list<unsigned char> data1(n);
    generateCharSequence(n, data1);

    std::list<unsigned char> data2(listsort<std::list<unsigned char> >
                                   (data1.begin(),
                                    data1.end()));
    radixSort(data1.begin(), data1.end());
    check(isTheSame(data1,data2), "Test failed");

  }
}

int main() {

  checkRadixSort();
  checkStableRadixSort();

  return 0;
}