From: Florian Forster <octo@leeloo.octo.it>
Date: Fri, 17 Dec 2010 21:34:39 +0000 (+0100)
Subject: src/sn_network.[ch]: Implement sn_network_cut().
X-Git-Tag: v1.0.0~19
X-Git-Url: https://git.octo.it/?p=sort-networks.git;a=commitdiff_plain;h=1e765313eb44b5707ea9cdc3429ce5da48cfbcd3

src/sn_network.[ch]: Implement sn_network_cut().

Using this function it is possible to do multiple cuts at once.
---

diff --git a/src/sn_network.c b/src/sn_network.c
index 1b3dd36..6908cf8 100644
--- a/src/sn_network.c
+++ b/src/sn_network.c
@@ -464,6 +464,21 @@ int sn_network_normalize (sn_network_t *n) /* {{{ */
   return (0);
 } /* }}} int sn_network_normalize */
 
+int sn_network_remove_input (sn_network_t *n, int input) /* {{{ */
+{
+  int i;
+
+  if ((n == NULL) || (input < 0) || (input >= n->inputs_num))
+    return (EINVAL);
+
+  for (i = 0; i < n->stages_num; i++)
+    sn_stage_remove_input (n->stages[i], input);
+
+  n->inputs_num--;
+
+  return (0);
+} /* }}} int sn_network_remove_input */
+
 int sn_network_cut_at (sn_network_t *n, int input, /* {{{ */
     enum sn_network_cut_dir_e dir)
 {
@@ -492,13 +507,36 @@ int sn_network_cut_at (sn_network_t *n, int input, /* {{{ */
   assert (((dir == DIR_MIN) && (position == 0))
       || ((dir == DIR_MAX) && (position == (n->inputs_num - 1))));
 
+  sn_network_remove_input (n, position);
+
+  return (0);
+} /* }}} int sn_network_cut_at */
+
+int sn_network_cut (sn_network_t *n, int *mask) /* {{{ */
+{
+  int inputs_num;
+  int i;
+
   for (i = 0; i < n->stages_num; i++)
-    sn_stage_remove_input (n->stages[i], position);
+  {
+    sn_stage_t *s = n->stages[i];
 
-  n->inputs_num--;
+    sn_stage_cut (s, mask, n->stages);
+  }
+
+  /* Use a copy of this member since it will be updated by
+   * sn_network_remove_input(). */
+  inputs_num = n->inputs_num;
+  for (i = 0; i < inputs_num; i++)
+  {
+    if (mask[i] < 0)
+      sn_network_remove_input (n, 0);
+    else if (mask[i] > 0)
+      sn_network_remove_input (n, n->inputs_num - 1);
+  }
 
   return (0);
-} /* }}} int sn_network_cut_at */
+} /* }}} int sn_network_cut */
 
 /* sn_network_concatenate
  *
diff --git a/src/sn_network.h b/src/sn_network.h
index f56e3ca..8e6d492 100644
--- a/src/sn_network.h
+++ b/src/sn_network.h
@@ -26,7 +26,6 @@
  * \endverbatim
  **/
 
-
 #ifndef SN_NETWORK_H
 #define SN_NETWORK_H 1
 
@@ -211,6 +210,16 @@ int sn_network_compress (sn_network_t *n);
 int sn_network_normalize (sn_network_t *n);
 
 /**
+ * Removes an input and all comparators touching that input from the comparator
+ * network.
+ *
+ * \param n The network to modify.
+ * \param input The zero-based index of the input to remove.
+ * \return Zero on success, non-zero on failure.
+ */
+int sn_network_remove_input (sn_network_t *n, int input);
+
+/**
  * Removes an inputs from a comparator network by assuming positive or negative
  * infinity to be supplied to a given input. The value will take a
  * deterministic way through the comparator network. After removing the path
@@ -226,6 +235,9 @@ int sn_network_normalize (sn_network_t *n);
  */
 int sn_network_cut_at (sn_network_t *n, int input, enum sn_network_cut_dir_e dir);
 
+/* FIXME: Documentation */
+int sn_network_cut (sn_network_t *n, int *mask);
+
 /**
  * An alias for sn_network_combine_odd_even_merge().
  */
diff --git a/src/sn_stage.c b/src/sn_stage.c
index d89fc89..8288415 100644
--- a/src/sn_stage.c
+++ b/src/sn_stage.c
@@ -361,6 +361,47 @@ int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir)
   return (new_position);
 } /* int sn_stage_cut_at */
 
+int sn_stage_cut (sn_stage_t *s, int *mask, /* {{{ */
+    sn_stage_t **prev)
+{
+  int i;
+
+  if ((s == NULL) || (mask == NULL) || (prev == NULL))
+    return (EINVAL);
+
+  for (i = 0; i < s->comparators_num; i++)
+  {
+    sn_comparator_t *c = s->comparators + i;
+    int left = SN_COMP_LEFT (c);
+    int right = SN_COMP_RIGHT (c);
+
+    if ((mask[left] == 0)
+        && (mask[right] == 0))
+      continue;
+
+    /* Check if we need to update the cut position */
+    if ((mask[left] != mask[right])
+        && ((mask[left] > 0) || (mask[right] < 0)))
+    {
+      int tmp;
+      int j;
+
+      tmp = mask[right];
+      mask[right] = mask[left];
+      mask[left] = tmp;
+
+      for (j = s->depth - 1; j >= 0; j--)
+        sn_stage_swap (prev[j],
+            left, right);
+    }
+
+    sn_stage_comparator_remove (s, i);
+    i--;
+  } /* for (i = 0; i < s->comparators_num; i++) */
+
+  return (0);
+} /* }}} int sn_stage_cut */
+
 int sn_stage_remove_input (sn_stage_t *s, int input)
 {
   int i;
diff --git a/src/sn_stage.h b/src/sn_stage.h
index d947515..6d008d6 100644
--- a/src/sn_stage.h
+++ b/src/sn_stage.h
@@ -191,6 +191,9 @@ int sn_stage_swap (sn_stage_t *s, int con0, int con1);
  */
 int sn_stage_cut_at (sn_stage_t *s, int input, enum sn_network_cut_dir_e dir);
 
+/* FIXME: Documentation */
+int sn_stage_cut (sn_stage_t *s, int *mask, sn_stage_t **prev);
+
 /**
  * Remove an input from a stage, remove all touching comparators and adapt the
  * input indexes of all remaining comparators.