From ef4a319984d22b88a9024ff523700d657621124d Mon Sep 17 00:00:00 2001
From: Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au>
Date: Tue, 10 Jul 2012 13:44:21 +1000
Subject: Add the LEMON graph library source to the repo

I'll likely be using it, so this just makes it easier to get to from
elsewhere. If I end up not using it then I can just delete it.
---
 lemon/test/radix_sort_test.cc | 147 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 147 insertions(+)
 create mode 100644 lemon/test/radix_sort_test.cc

(limited to 'lemon/test/radix_sort_test.cc')

diff --git a/lemon/test/radix_sort_test.cc b/lemon/test/radix_sort_test.cc
new file mode 100644
index 0000000..2a27a7e
--- /dev/null
+++ b/lemon/test/radix_sort_test.cc
@@ -0,0 +1,147 @@
+/* -*- 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 <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; }
+
+
+void generateIntSequence(int n, std::vector<int>& 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;
+  }
+}
+
+void generateCharSequence(int n, std::vector<unsigned char>& 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");
+    }
+
+  }
+}
+
+
+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");
+    }
+
+  }
+}
+
+int main() {
+
+  checkRadixSort();
+  checkStableRadixSort();
+
+  return 0;
+}
-- 
cgit v1.2.3