#include "config.h"
+#ifndef _ISOC99_SOURCE
+# define _ISOC99_SOURCE
+#endif
+#ifndef _POSIX_C_SOURCE
+# define _POSIX_C_SOURCE 200809L
+#endif
+#ifdef _XOPEN_SOURCE
+# define _XOPEN_SOURCE 700
+#endif
+
#include <stdlib.h>
#include <stdio.h>
+#include <string.h>
#include <strings.h>
#include "sn_network.h"
-void exit_usage (const char *name)
+static void exit_usage (const char *name)
{
- printf ("%s <position> <min|max>\n", name);
+ printf ("Usage: %s <num>[:min|max] [<num>[:min|max] ...]\n", name);
exit (EXIT_FAILURE);
}
+static int do_cut (sn_network_t *n, int defs_num, char **defs)
+{
+ int mask[SN_NETWORK_INPUT_NUM (n)];
+ int status;
+ int i;
+
+ memset (mask, 0, sizeof (mask));
+ for (i = 0; i < defs_num; i++)
+ {
+ char *endptr = NULL;
+ int pos;
+ int val = 1;
+
+ pos = (int) strtol (defs[i], &endptr, /* base = */ 0);
+ if (strcasecmp (":min", endptr) == 0)
+ val = -1;
+
+ if ((pos < 0) || (pos >= SN_NETWORK_INPUT_NUM (n)))
+ {
+ fprintf (stderr, "Invalid line number: %i\n", pos);
+ return (-1);
+ }
+
+ mask[pos] = val;
+ }
+
+ status = sn_network_cut (n, mask);
+ if (status != 0)
+ {
+ fprintf (stderr, "sn_network_cut failed with status %i.\n", status);
+ return (-1);
+ }
+
+ return (0);
+} /* }}} int do_cut */
+
int main (int argc, char **argv)
{
sn_network_t *n;
- int pos = 0;
- enum sn_network_cut_dir_e dir = DIR_MIN;
-
- if (argc != 3)
+ if (argc < 2)
exit_usage (argv[0]);
- pos = atoi (argv[1]);
- if (strcasecmp ("max", argv[2]) == 0)
- dir = DIR_MAX;
-
n = sn_network_read (stdin);
if (n == NULL)
{
- printf ("n == NULL!\n");
- return (1);
+ fprintf (stderr, "Unable to read network from STDIN.\n");
+ exit (EXIT_FAILURE);
}
- sn_network_cut_at (n, pos, dir);
+ do_cut (n, argc - 1, argv + 1);
sn_network_compress (n);
sn_network_write (n, stdout);
return (0);
} /* }}} int read_options */
-static int apply_cut (sn_network_t *n, int input) /* {{{ */
-{
- enum sn_network_cut_dir_e dir = DIR_MAX;
-
- if (input < 0)
- {
- dir = DIR_MIN;
- input *= (-1);
- }
- input--;
-
- return (sn_network_cut_at (n, input, dir));
-} /* }}} int apply_cut */
-
-static int apply (sn_network_t *n, const individuum_t *ind) /* {{{ */
-{
- int i;
-
- for (i = 0; i < cuts_num; i++)
- apply_cut (n, ind[i]);
-
- return (0);
-} /* }}} int apply */
-
static int rate_network (const sn_network_t *n) /* {{{ */
{
int rate;
int i;
- rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
+ rate = SN_NETWORK_STAGE_NUM (n);
for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
{
sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
- rate += SN_STAGE_COMP_NUM (s);
+ rate += 2 * SN_STAGE_COMP_NUM (s);
}
return (rate);
static sn_network_t *individuum_to_network (const individuum_t *ind) /* {{{ */
{
sn_network_t *n;
+ int mask[SN_NETWORK_INPUT_NUM (initial_network)];
+
+ memcpy (mask, ind, sizeof (mask));
n = sn_network_clone (initial_network);
if (n == NULL)
return (NULL);
- apply (n, ind);
+ sn_network_cut (n, mask);
sn_network_normalize (n);
sn_network_compress (n);
static void *ind_copy (const void *in) /* {{{ */
{
- size_t s = sizeof (individuum_t) * cuts_num;
+ size_t s = sizeof (individuum_t) * inputs_num;
void *out;
out = malloc (s);
free (ind);
} /* }}} void ind_free */
-static void ind_print (const individuum_t *ind)
+static void ind_print (const individuum_t *ind) /* {{{ */
+{
+ int i;
+
+ for (i = 0; i < inputs_num; i++)
+ {
+ printf ("%3i: %s\n", i, (ind[i] == 0) ? "-" :
+ (ind[i] < 0) ? "MIN" : "MAX");
+ }
+
+ printf ("# sn-cut");
+ for (i = 0; i < inputs_num; i++)
+ {
+ if (ind[i] == 0)
+ continue;
+ printf (" %i:%s", i, (ind[i] < 0) ? "MIN" : "MAX");
+ }
+ printf ("\n");
+} /* }}} void ind_print */
+
+/* Simply makes sure the right amount of cutting positions exist. */
+static void mutate (individuum_t *ind, int this_cuts_num) /* {{{ */
{
int i;
- for (i = 0; i < cuts_num; i++)
+ if (this_cuts_num < 0)
+ {
+ this_cuts_num = 0;
+ for (i = 0; i < inputs_num; i++)
+ if (ind[i] != 0)
+ this_cuts_num++;
+ }
+
+ while (this_cuts_num != cuts_num)
{
- int input = ind[i];
- int dir = 0;
+ i = sn_bounded_random (0, inputs_num - 1);
- if (input < 0)
+ if ((this_cuts_num < cuts_num)
+ && (ind[i] == 0))
{
- input *= -1;
- dir = 1;
+ ind[i] = (sn_bounded_random (0, 1) * 2) - 1;
+ assert (ind[i] != 0);
+ this_cuts_num++;
+ }
+ else if ((this_cuts_num > cuts_num)
+ && (ind[i] != 0))
+ {
+ ind[i] = 0;
+ this_cuts_num--;
}
- input--;
-
- printf ("%s(%3i)\n", (dir == 0) ? "MAX" : "MIN", input);
}
-} /* }}} void ind_print */
+} /* }}} void mutate */
static individuum_t *recombine (individuum_t *i0, individuum_t *i1) /* {{{ */
{
individuum_t *offspring;
- int cut_at;
+ int this_cuts_num;
int i;
if ((i0 == NULL) || (i1 == NULL))
return (NULL);
- offspring = malloc (sizeof (*offspring) * cuts_num);
+ offspring = malloc (sizeof (*offspring) * inputs_num);
if (offspring == NULL)
return (NULL);
- memset (offspring, 0, sizeof (*offspring) * cuts_num);
+ memset (offspring, 0, sizeof (*offspring) * inputs_num);
- cut_at = sn_bounded_random (0, cuts_num);
- for (i = 0; i < cuts_num; i++)
+ this_cuts_num = 0;
+ for (i = 0; i < this_cuts_num; i++)
{
- if (i < cut_at)
+ if (sn_bounded_random (0, 1) == 0)
offspring[i] = i0[i];
else
offspring[i] = i1[i];
+
+ if (offspring[i] != 0)
+ this_cuts_num++;
}
+ mutate (offspring, this_cuts_num);
+
return (offspring);
} /* }}} individuum_t *recombine */
-static void random_cut (individuum_t *ind, int index) /* {{{ */
-{
- int max_input = inputs_num - index;
-
- ind[index] = 0;
- while (ind[index] == 0)
- ind[index] = sn_bounded_random ((-1) * max_input, max_input);
-} /* }}} void random_cut */
-
-static void mutate (individuum_t *ind) /* {{{ */
-{
- int reset_input;
- int i;
-
- reset_input = sn_bounded_random (0, 3 * cuts_num);
- for (i = 0; i < cuts_num; i++)
- {
- if (reset_input == i)
- random_cut (ind, i);
-
- if (sn_bounded_random (0, 100))
- ind[i] *= (-1);
- }
-} /* }}} void mutate */
-
static int create_offspring (void) /* {{{ */
{
individuum_t *i0;
i1 = population_get_random (population);
i2 = recombine (i0, i1);
- mutate (i2);
population_insert (population, i2);
for (i = 0; i < max_population_size; i++)
{ /* create a random initial individuum */
individuum_t *ind;
- int i;
- ind = malloc (sizeof (*ind) * cuts_num);
+ ind = calloc (inputs_num, sizeof (*ind));
if (ind == NULL)
{
- fprintf (stderr, "malloc failed.\n");
+ fprintf (stderr, "calloc failed.\n");
exit (EXIT_FAILURE);
}
-
- for (i = 0; i < cuts_num; i++)
- random_cut (ind, i);
+ mutate (ind, /* num cuts = */ 0);
population_insert (population, ind);
ind_free (ind);
int main (int argc, char **argv)
{
- sn_network_t *n;
- size_t inputs_num;
+ sn_network_t *sn_left;
+ sn_network_t *sn_right;
+ sn_network_t *oem;
+ int inputs_left;
+ int inputs_right;
- if (argc != 2)
+ if (argc != 3)
{
- printf ("Usage: %s <num inputs>\n", argv[0]);
+ printf ("Usage: %s <inputs left> <inputs right>\n", argv[0]);
return (0);
}
- inputs_num = (size_t) atoi (argv[1]);
- if (inputs_num < 2)
+ inputs_left = atoi (argv[1]);
+ inputs_right = atoi (argv[2]);
+ if ((inputs_left < 1) || (inputs_right < 1))
{
- fprintf (stderr, "Invalid number of inputs: %zu\n", inputs_num);
+ fprintf (stderr, "Invalid number of inputs: %i/%i\n",
+ inputs_left, inputs_right);
return (1);
}
- n = sn_network_create_odd_even_mergesort (inputs_num);
- if (n == NULL)
- {
- printf ("n == NULL!\n");
- return (1);
- }
+ sn_left = sn_network_create (inputs_left);
+ sn_right = sn_network_create (inputs_right);
+ oem = sn_network_combine_odd_even_merge (sn_left, sn_right);
+
+ sn_network_write (oem, stdout);
- sn_network_write (n, stdout);
+ sn_network_destroy (sn_left);
+ sn_network_destroy (sn_right);
+ sn_network_destroy (oem);
return (0);
} /* int main */
#include <stdlib.h>
#include <stdio.h>
+#include <unistd.h>
#include <assert.h>
#include "sn_network.h"
#define Y_SPACING 40
static double x_offset = OUTER_SPACING;
+static _Bool embedded = 0;
+
+static void exit_usage (void) /* {{{ */
+{
+ printf ("Usage: sn-svg [options] [file]\n"
+ "\n"
+ "Valid options are:\n"
+ " -e Create output suitable for embedding into other XML files.\n"
+ "\n");
+ exit (EXIT_FAILURE);
+} /* }}} void exit_usage */
+
+static int read_options (int argc, char **argv) /* {{{ */
+{
+ int option;
+
+ while ((option = getopt (argc, argv, "eh?")) != -1)
+ {
+ switch (option)
+ {
+ case 'e':
+ embedded = 1;
+ break;
+
+ case 'h':
+ case '?':
+ default:
+ exit_usage ();
+ }
+ }
+
+ return (0);
+} /* }}} int read_options */
static double determine_stage_width (sn_stage_t *s)
{
return (width);
} /* }}} double determine_network_width */
-static int sn_svg_show_stage (sn_stage_t *s)
+static int sn_svg_show_stage (sn_stage_t *s) /* {{{ */
{
int lines[s->comparators_num];
int right[s->comparators_num];
int y1 = Y_OFFSET + (SN_COMP_MIN (c) * Y_SPACING);
int y2 = Y_OFFSET + (SN_COMP_MAX (c) * Y_SPACING);
- printf (" <line x1=\"%g\" y1=\"%i\" x2=\"%g\" y2=\"%i\" "
+ printf (" <svg:line x1=\"%g\" y1=\"%i\" x2=\"%g\" y2=\"%i\" "
"stroke=\"black\" stroke-width=\"1\" />\n"
- " <circle cx=\"%g\" cy=\"%i\" r=\"%g\" fill=\"black\" />\n"
- " <circle cx=\"%g\" cy=\"%i\" r=\"%g\" fill=\"black\" />\n",
+ " <svg:circle cx=\"%g\" cy=\"%i\" r=\"%g\" fill=\"black\" />\n"
+ " <svg:circle cx=\"%g\" cy=\"%i\" r=\"%g\" fill=\"black\" />\n",
x1, y1, x2, y2,
x1, y1, RADIUS,
x2, y2, RADIUS);
printf ("\n");
return (0);
-} /* int sn_svg_show_stage */
+} /* }}} int sn_svg_show_stage */
-int main (int argc, char **argv)
+int main (int argc, char **argv) /* {{{ */
{
sn_network_t *n;
FILE *fh = NULL;
int i;
- if (argc == 1)
+ read_options (argc, argv);
+
+ if ((argc - optind) == 0)
fh = stdin;
- else if (argc == 2)
- fh = fopen (argv[1], "r");
+ else if ((argc - optind) == 1)
+ fh = fopen (argv[optind], "r");
if (fh == NULL)
- {
- printf ("fh == NULL!\n");
- return (1);
- }
+ exit_usage ();
n = sn_network_read (fh);
svg_height = (2 * Y_OFFSET) + ((SN_NETWORK_INPUT_NUM (n) - 1) * Y_SPACING);
svg_width = determine_network_width (n);
- printf ("<?xml version=\"1.0\" standalone=\"no\"?>\n"
- "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" "
- "\"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n"
- "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" "
- "width=\"%gpt\" height=\"%gpt\" viewBox=\"0 0 %g %g\">\n",
- svg_width, svg_height, svg_width, svg_height);
+ if (embedded)
+ printf ("<svg:svg version=\"1.1\" viewBox=\"0 0 %g %g\">\n",
+ svg_width, svg_height);
+ else
+ printf ("<?xml version=\"1.0\" standalone=\"no\"?>\n"
+ "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" "
+ "\"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n"
+ "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" "
+ "width=\"%gpt\" height=\"%gpt\" viewBox=\"0 0 %g %g\">\n",
+ svg_width, svg_height, svg_width, svg_height);
printf ("<!-- Output generated with sn-svg from %s -->\n", PACKAGE_STRING);
printf (" <!-- horizontal lines -->\n");
for (i = 0; i < SN_NETWORK_INPUT_NUM (n); i++)
- printf (" <line x1=\"%g\" y1=\"%i\" x2=\"%g\" y2=\"%i\" "
+ printf (" <svg:line x1=\"%g\" y1=\"%i\" x2=\"%g\" y2=\"%i\" "
"stroke=\"black\" stroke-width=\"1\" />\n",
0.0, Y_OFFSET + (i * Y_SPACING),
x_offset, Y_OFFSET + (i * Y_SPACING));
- printf ("</svg>\n");
+ printf ("</svg:svg>\n");
return (0);
-} /* int main */
+} /* }}} int main */
-/* vim: set shiftwidth=2 softtabstop=2 : */
+/* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */
c->min = min;
c->max = max;
+ c->user_data = NULL;
+ c->free_func = NULL;
return (c);
} /* sn_comparator_t *sn_comparator_create */
void sn_comparator_destroy (sn_comparator_t *c)
{
+ if (c->free_func != NULL)
+ c->free_func (c->user_data);
+
if (c != NULL)
free (c);
} /* void sn_comparator_destroy */
{
int min; /**< Index of the line onto which the smaller element will be put. */
int max; /**< Index of the line onto which the larger element will be put. */
+ void *user_data; /**< Pointer to user data. */
+ void (*free_func) (void *); /**< Pointer to a function used to free the user data pointer. */
};
typedef struct sn_comparator_s sn_comparator_t;
/** Returns the index of the line onto which the larger element will be put. */
#define SN_COMP_MAX(c) (c)->max
+/** Expands to the user data pointer. */
+#define SN_COMP_USER_DATA(c) (c)->user_data
+/** Expands to the free-function pointer. */
+#define SN_COMP_FREE_FUNC(c) (c)->free_func
+
/**
* Allocates, initializes and returns a new comparator object. The returned
* pointer must be freed by sn_comparator_destroy().
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)
{
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
*
* \endverbatim
**/
-
#ifndef SN_NETWORK_H
#define SN_NETWORK_H 1
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
*/
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().
*/
return (NULL);
}
- memcpy (s_copy->comparators, s->comparators,
- s->comparators_num * sizeof (sn_comparator_t));
+ for (i = 0; i < s->comparators_num; i++)
+ {
+ SN_COMP_MIN (s_copy->comparators + i) = SN_COMP_MIN (s->comparators + i);
+ SN_COMP_MAX (s_copy->comparators + i) = SN_COMP_MAX (s->comparators + i);
+ SN_COMP_USER_DATA (s_copy->comparators + i) = NULL;
+ SN_COMP_FREE_FUNC (s_copy->comparators + i) = NULL;
+ }
s_copy->comparators_num = s->comparators_num;
return (s_copy);
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;
*/
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.
projects / sort-networks.git / commitdiff