X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=src%2Fsn_network.c;h=e2a8df8dc203d148ce614960b4b5c7baa49d32b8;hb=ddd57e49e6fe256f83948fa3e4d71b8da1b6d409;hp=07d811dd66d3c7111310c3b245d3bd6fd647672c;hpb=02dd5a8e9890f7b16b950db238eeff42a57e9142;p=sort-networks.git

diff --git a/src/sn_network.c b/src/sn_network.c
index 07d811d..e2a8df8 100644
--- a/src/sn_network.c
+++ b/src/sn_network.c
@@ -6,6 +6,7 @@
 #include <assert.h>
 
 #include "sn_network.h"
+#include "sn_random.h"
 
 sn_network_t *sn_network_create (int inputs_num)
 {
@@ -34,6 +35,7 @@ void sn_network_destroy (sn_network_t *n)
       sn_stage_destroy (n->stages[i]);
       n->stages[i] = NULL;
     }
+    free (n->stages);
     n->stages = NULL;
   }
 
@@ -68,20 +70,63 @@ int sn_network_stage_remove (sn_network_t *n, int s_num)
   n->stages[s_num] = NULL;
 
   if (nmemb > 0)
+  {
     memmove (n->stages + s_num, n->stages + (s_num + 1),
 	nmemb * sizeof (sn_stage_t *));
+    n->stages[n->stages_num - 1] = NULL;
+  }
   n->stages_num--;
 
   /* Free the unused memory */
-  temp = (sn_stage_t **) realloc (n->stages,
-      n->stages_num * sizeof (sn_stage_t *));
-  if (temp == NULL)
-    return (-1);
-  n->stages = temp;
+  if (n->stages_num == 0)
+  {
+    free (n->stages);
+    n->stages = NULL;
+  }
+  else
+  {
+    temp = (sn_stage_t **) realloc (n->stages,
+	n->stages_num * sizeof (sn_stage_t *));
+    if (temp == NULL)
+      return (-1);
+    n->stages = temp;
+  }
 
   return (0);
 } /* int sn_network_stage_remove */
 
+sn_network_t *sn_network_clone (const sn_network_t *n)
+{
+  sn_network_t *n_copy;
+  int i;
+
+  n_copy = sn_network_create (n->inputs_num);
+  if (n_copy == NULL)
+    return (NULL);
+
+  for (i = 0; i < n->stages_num; i++)
+  {
+    sn_stage_t *s;
+    int status;
+
+    s = sn_stage_clone (n->stages[i]);
+    if (s == NULL)
+      break;
+
+    status = sn_network_stage_add (n_copy, s);
+    if (status != 0)
+      break;
+  }
+
+  if (i < n->stages_num)
+  {
+    sn_network_destroy (n_copy);
+    return (NULL);
+  }
+
+  return (n_copy);
+} /* sn_network_t *sn_network_clone */
+
 int sn_network_show (sn_network_t *n)
 {
   int i;
@@ -145,9 +190,48 @@ int sn_network_compress (sn_network_t *n)
     }
   }
 
+  while ((n->stages_num > 0)
+      && (SN_STAGE_COMP_NUM (n->stages[n->stages_num - 1]) == 0))
+    sn_network_stage_remove (n, n->stages_num - 1);
+
   return (0);
 } /* int sn_network_compress */
 
+int sn_network_normalize (sn_network_t *n)
+{
+  int i;
+
+  for (i = n->stages_num - 1; i >= 0; i--)
+  {
+    sn_stage_t *s;
+    int j;
+
+    s = n->stages[i];
+
+    for (j = 0; j < SN_STAGE_COMP_NUM (s); j++)
+    {
+      sn_comparator_t *c;
+      int min;
+      int max;
+
+      c = SN_STAGE_COMP_GET (s, j);
+
+      min = c->min;
+      max = c->max;
+
+      if (min > max)
+      {
+	int k;
+
+	for (k = i; k >= 0; k--)
+	  sn_stage_swap (n->stages[k], min, max);
+      }
+    } /* for (j = 0 .. #comparators) */
+  } /* for (i = n->stages_num - 1 .. 0) */
+
+  return (0);
+} /* int sn_network_normalize */
+
 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir)
 {
   int i;
@@ -175,7 +259,6 @@ int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir
   assert (((dir == DIR_MIN) && (position == 0))
       || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
 
-
   for (i = 0; i < n->stages_num; i++)
     sn_stage_remove_input (n->stages[i], position);
 
@@ -191,13 +274,13 @@ static int sn_network_add_bitonic_merger_recursive (sn_network_t *n,
   int m;
   int i;
 
+  if (num == 1)
+    return (0);
+
   s = sn_stage_create (n->stages_num);
   if (s == NULL)
     return (-1);
 
-  if (num == 1)
-    return (0);
-
   m = num / 2;
 
   for (i = low; i < (low + m); i++)
@@ -248,6 +331,104 @@ static int sn_network_add_bitonic_merger (sn_network_t *n)
   return (0);
 } /* int sn_network_add_bitonic_merger */
 
+static int sn_network_add_odd_even_merger_recursive (sn_network_t *n,
+    int *indizes, int indizes_num)
+{
+  if (indizes_num > 2)
+  {
+    sn_comparator_t c;
+    sn_stage_t *s;
+    int indizes_half_num;
+    int *indizes_half;
+    int status;
+    int i;
+
+    indizes_half_num = indizes_num / 2;
+    indizes_half = (int *) malloc (indizes_num * sizeof (int));
+    if (indizes_half == NULL)
+      return (-1);
+
+    for (i = 0; i < indizes_half_num; i++)
+    {
+      indizes_half[i] = indizes[2 * i];
+      indizes_half[indizes_half_num + i] = indizes[(2 * i) + 1];
+    }
+
+    status = sn_network_add_odd_even_merger_recursive (n,
+	indizes_half, indizes_half_num);
+    if (status != 0)
+    {
+      free (indizes_half);
+      return (status);
+    }
+
+    status = sn_network_add_odd_even_merger_recursive (n,
+	indizes_half + indizes_half_num, indizes_half_num);
+    if (status != 0)
+    {
+      free (indizes_half);
+      return (status);
+    }
+
+    free (indizes_half);
+
+    s = sn_stage_create (n->stages_num);
+    if (s == NULL)
+      return (-1);
+
+    for (i = 1; i < (indizes_num - 2); i += 2)
+    {
+      c.min = indizes[i];
+      c.max = indizes[i + 1];
+
+      sn_stage_comparator_add (s, &c);
+    }
+
+    sn_network_stage_add (n, s);
+  }
+  else
+  {
+    sn_comparator_t c;
+    sn_stage_t *s;
+
+    assert (indizes_num == 2);
+
+    c.min = indizes[0];
+    c.max = indizes[1];
+
+    s = sn_stage_create (n->stages_num);
+    if (s == NULL)
+      return (-1);
+
+    sn_stage_comparator_add (s, &c);
+    sn_network_stage_add (n, s);
+  }
+
+  return (0);
+} /* int sn_network_add_odd_even_merger_recursive */
+
+static int sn_network_add_odd_even_merger (sn_network_t *n)
+{
+  int *indizes;
+  int indizes_num;
+  int status;
+  int i;
+
+  indizes_num = n->inputs_num;
+  indizes = (int *) malloc (indizes_num * sizeof (int));
+  if (indizes == NULL)
+    return (-1);
+
+  for (i = 0; i < indizes_num; i++)
+    indizes[i] = i;
+
+  status = sn_network_add_odd_even_merger_recursive (n,
+      indizes, indizes_num);
+  
+  free (indizes);
+  return (status);
+} /* int sn_network_add_bitonic_merger */
+
 sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1)
 {
   sn_network_t *n;
@@ -289,7 +470,15 @@ sn_network_t *sn_network_combine (sn_network_t *n0, sn_network_t *n1)
     sn_network_stage_add (n, s);
   }
 
-  sn_network_add_bitonic_merger (n);
+  if (sn_bounded_random (0, 1) == 0)
+  {
+    sn_network_add_bitonic_merger (n);
+  }
+  else
+  {
+    sn_network_add_odd_even_merger (n);
+  }
+
   sn_network_compress (n);
 
   return (n);
@@ -388,4 +577,20 @@ int sn_network_write (sn_network_t *n, FILE *fh)
   return (0);
 } /* int sn_network_write */
 
+int sn_network_write_file (sn_network_t *n, const char *file)
+{
+  int status;
+  FILE *fh;
+
+  fh = fopen (file, "w");
+  if (fh == NULL)
+    return (-1);
+
+  status = sn_network_write (n, fh);
+
+  fclose (fh);
+
+  return (status);
+} /* int sn_network_write_file */
+
 /* vim: set shiftwidth=2 softtabstop=2 : */