From 7f5611eaa2e099c4422c49a8c47fd437b291dfb4 Mon Sep 17 00:00:00 2001
From: Florian Forster <octo@leeloo.octo.it>
Date: Tue, 22 Feb 2011 08:01:40 +0100
Subject: [PATCH] sn-transpositionsort: New tool.

---
 README                     |  4 +++
 src/Makefile.am            |  5 ++-
 src/sn-transpositionsort.c | 79 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 87 insertions(+), 1 deletion(-)
 create mode 100644 src/sn-transpositionsort.c

diff --git a/README b/README
index c5dfe69..2fece43 100644
--- a/README
+++ b/README
@@ -79,6 +79,10 @@ The distribution includes the following utility programs:
     Prints the TikZ / TeX sources of a graphic representation of a cut sequence
     to STDOUT.
 
+  * sn-transpositionsort
+    Creates an odd-even transpositionsort network with the given number of
+    inputs and prints the network to STDOUT.
+
 Experimental / research applications:
 
   * sn-bb
diff --git a/src/Makefile.am b/src/Makefile.am
index 09a9959..c14c188 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -8,7 +8,7 @@ bin_PROGRAMS = sn-apply \
 	       sn-count-cuts sn-count-markov sn-cut \
 	       sn-info sn-markov sn-merge sn-normalize \
 	       sn-oddevenmerge sn-oddevensort sn-pairwisesort \
-	       sn-shmoo sn-show sn-svg sn-tex sn-tex-cut
+	       sn-shmoo sn-show sn-svg sn-tex sn-tex-cut sn-transpositionsort
 
 libsortnetwork_la_SOURCES = sn_network.c sn_network.h       \
 			    sn_stage.c sn_stage.h           \
@@ -83,6 +83,9 @@ sn_tex_LDADD = libsortnetwork.la
 sn_tex_cut_SOURCES = sn-tex-cut.c
 sn_tex_cut_LDADD = libsortnetwork.la
 
+sn_transpositionsort_SOURCES = sn-transpositionsort.c
+sn_transpositionsort_LDADD = libsortnetwork.la
+
 if BUILD_WITH_LIBPOPULATION
 bin_PROGRAMS += sn-evolution sn-evolution2 sn-evolution-cut sn-evolution-merge
 
diff --git a/src/sn-transpositionsort.c b/src/sn-transpositionsort.c
new file mode 100644
index 0000000..2637a27
--- /dev/null
+++ b/src/sn-transpositionsort.c
@@ -0,0 +1,79 @@
+/**
+ * libsortnetwork - src/sn-transpositionsort.c
+ * Copyright (C) 2011  Florian Forster
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; only version 2 of the License is applicable.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
+ *
+ * Authors:
+ *   Florian octo Forster <ff at octo.it>
+ **/
+
+#ifndef _ISOC99_SOURCE
+# define _ISOC99_SOURCE
+#endif
+#ifndef _POSIX_C_SOURCE
+# define _POSIX_C_SOURCE 200112L
+#endif
+
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "sn_network.h"
+
+int main (int argc, char **argv)
+{
+  sn_network_t *n;
+  int inputs_num;
+  int i;
+
+  if (argc != 2)
+  {
+    printf ("Usage: %s <num inputs>\n", argv[0]);
+    exit (EXIT_FAILURE);
+  }
+
+  inputs_num = atoi (argv[1]);
+  if (inputs_num < 2)
+  {
+    fprintf (stderr, "Invalid number of inputs: %i\n", inputs_num);
+    exit (EXIT_FAILURE);
+  }
+
+  n = sn_network_create (inputs_num);
+  if (n == NULL)
+  {
+    printf ("n == NULL!\n");
+    exit (EXIT_FAILURE);
+  }
+
+  for (i = 0; i < inputs_num; i++)
+  {
+    int j;
+
+    for (j = 1 + (i % 2); j < inputs_num; j += 2)
+    {
+      sn_comparator_t *c = sn_comparator_create (j - 1, j);
+      sn_network_comparator_add (n, c);
+      sn_comparator_destroy (c);
+    }
+  }
+
+  sn_network_compress (n);
+  sn_network_write (n, stdout);
+  sn_network_destroy (n);
+
+  return (0);
+} /* int main */
+
+/* vim: set shiftwidth=2 softtabstop=2 : */
-- 
2.11.0