source: lemon-0.x/test/radix_sort_test.cc @ 2121:09a07a851506

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * 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/graph_utils.h>
#include <lemon/maps.h>
#include <lemon/radix_sort.h>

#include "test_tools.h"


#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
using namespace lemon;

void checkRadixSort() {
  {
    int n = 10000;
    vector<int> data1(n), data2(n);
    for (int i = 0; i < n; ++i) {
      data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
    }
    radixSort(data1.begin(), data1.end());
    sort(data2.begin(), data2.end());
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[i], "Test failed");
    }
  } {
    int n = 10000;
    vector<unsigned char> data1(n), data2(n);
    for (int i = 0; i < n; ++i) {
      data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
    }
    radixSort(data1.begin(), data1.end());
    sort(data2.begin(), data2.end());
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[i], "Test failed");
    }
  }
}


void checkCounterSort() {
  {
    int n = 10000;
    vector<int> data1(n), data2(n);
    for (int i = 0; i < n; ++i) {
      data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
    }
    counterSort(data1.begin(), data1.end());
    sort(data2.begin(), data2.end());
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[i], "Test failed");
    } 
  } {
    int n = 10000;
    vector<unsigned char> data1(n), data2(n);
    for (int i = 0; i < n; ++i) {
      data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
    }
    counterSort(data1.begin(), data1.end());
    sort(data2.begin(), data2.end());
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[i], "Test failed");
    } 
  }
}

void checkSorts() {
  checkRadixSort();
  checkCounterSort();
}

void checkGraphRadixSort() {
  typedef SmartGraph Graph;
  typedef Graph::Node Node;
  typedef Graph::Edge Edge;

  const int n = 100;
  const int e = (int)(n * log((double)n));

  Graph graph;
  vector<Node> nodes;

  for (int i = 0; i < n; ++i) {
    nodes.push_back(graph.addNode());
  }
  vector<Edge> edges;
  for (int i = 0; i < e; ++i) {
    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
  }

  radixSort(edges.begin(), edges.end(), 
            mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
                                  sourceMap(graph))));

  Graph::EdgeMap<bool> was(graph, false);

  for (int i = 0; i < (int)edges.size(); ++i) {
    check(!was[edges[i]], "Test failed");
    was[edges[i]] = true;
  }

  for (int i = 1; i < (int)edges.size(); ++i) {
    check(graph.id(graph.source(edges[i - 1])) <= 
          graph.id(graph.source(edges[i])), "Test failed");
  }

}

void checkGraphCounterSort() {
  typedef SmartGraph Graph;
  typedef Graph::Node Node;
  typedef Graph::Edge Edge;

  const int n = 100;
  const int e = (int)(n * log((double)n));

  Graph graph;
  vector<Node> nodes;

  for (int i = 0; i < n; ++i) {
    nodes.push_back(graph.addNode());
  }
  vector<Edge> edges;
  for (int i = 0; i < e; ++i) {
    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
  }

  counterSort(edges.begin(), edges.end(), 
              mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
                                    sourceMap(graph))));

  counterSort(edges.begin(), edges.end(), 
              mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
                                    targetMap(graph))));

  Graph::EdgeMap<bool> was(graph, false);

  for (int i = 0; i < (int)edges.size(); ++i) {
    check(!was[edges[i]], "Test failed");
    was[edges[i]] = true;
  }

  for (int i = 1; i < (int)edges.size(); ++i) {
    check(graph.id(graph.target(edges[i - 1])) < 
          graph.id(graph.target(edges[i])) || 
          (graph.id(graph.target(edges[i - 1])) ==
           graph.id(graph.target(edges[i])) &&
           graph.id(graph.source(edges[i - 1])) <= 
           graph.id(graph.source(edges[i]))), "Test failed");
  }

}

void checkGraphSorts() {
  checkGraphRadixSort();
  checkGraphCounterSort();
}

int main() {
  checkSorts();
  checkGraphSorts();
  return 0;
}