source: lemon-0.x/test/radix_sort_test.cc @ 2392:4bbeaf115cdb

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * 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;

typedef unsigned char uchar;

void checkRadixSort() {
  {
    int n = 10000;
    vector<int> data1(n), data2(n);
    for (int i = 0; i < n; ++i) {
      data1[i] = data2[i] = rnd[1000] - 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] = rnd[uchar(200)];
    }
    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] = rnd[1000] - 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] = rnd[uchar(200)];
    }
    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 = rnd[n];
    int t = rnd[n];
    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 = rnd[n];
    int t = rnd[n];
    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;
}