2 * libsortnetwork - src/sn-tex.c
3 * Copyright (C) 2008-2010 Florian octo Forster
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation; only version 2 of the License is applicable.
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
14 * You should have received a copy of the GNU General Public License along
15 * with this program; if not, write to the Free Software Foundation, Inc.,
16 * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 * Florian octo Forster <ff at octo.it>
24 #ifndef _ISOC99_SOURCE
25 # define _ISOC99_SOURCE
27 #ifndef _POSIX_C_SOURCE
28 # define _POSIX_C_SOURCE 200112L
39 #include "sn_network.h"
41 const char *input_file = NULL;
43 /* 21cm (DIN-A4) - 2x3cm Rand = 15cm */
44 static double output_width = 15.0;
45 static double scale = 1.0;
46 static double inner_spacing = 0.3;
47 static double outer_spacing = 1.0;
48 static double vertical_spacing = 0.8;
50 static double x_offset;
51 static int next_vertex_number = 0;
53 static int *mask = NULL;
55 #define INPUT_TO_Y(i) (((double) (i)) * vertical_spacing)
57 static void exit_usage (void) /* {{{ */
59 printf ("Usage: sn-tex-cut [options] <num>[:min|max] [<num>[:min|max] ...]\n"
61 "Valid options are:\n"
62 " -i <file> Read comparator network from file.\n"
63 " -w <width> Specify the width of the graph (in TikZ default units).\n"
66 } /* }}} void exit_usage */
68 static int read_options (int argc, char **argv) /* {{{ */
72 while ((option = getopt (argc, argv, "w:i:h?")) != -1)
78 double width = atof (optarg);
81 fprintf (stderr, "Invalid width argument: %s\n", optarg);
100 } /* }}} int read_options */
102 static int read_mask (sn_network_t *n, int argc, char **argv) /* {{{ */
106 mask = calloc (SN_NETWORK_INPUT_NUM (n), sizeof (*mask));
110 for (i = 0; i < argc; i++)
116 pos = (int) strtol (argv[i], &endptr, /* base = */ 0);
117 if (strcasecmp (":min", endptr) == 0)
120 if ((pos < 0) || (pos >= SN_NETWORK_INPUT_NUM (n)))
122 fprintf (stderr, "Invalid line number: %i\n", pos);
130 } /* }}} int read_mask */
132 static double determine_stage_width (sn_stage_t *s) /* {{{ */
134 int lines[s->comparators_num];
135 int right[s->comparators_num];
139 if (SN_STAGE_COMP_NUM (s) == 0)
142 for (i = 0; i < SN_STAGE_COMP_NUM (s); i++)
148 for (i = 0; i < SN_STAGE_COMP_NUM (s); i++)
151 sn_comparator_t *c = SN_STAGE_COMP_GET (s, i);
153 for (j = 0; j < lines_used; j++)
154 if (SN_COMP_LEFT (c) > right[j])
158 right[j] = SN_COMP_RIGHT (c);
162 assert (lines_used >= 1);
164 return (((double) (lines_used - 1)) * inner_spacing);
165 } /* }}} double determine_stage_width */
167 static double determine_network_width (sn_network_t *n) /* {{{ */
172 /* Spacing between stages and at the beginning and end of the network */
173 width = (SN_NETWORK_STAGE_NUM (n) + 1) * outer_spacing;
175 /* Spacing required within a stage */
176 for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
177 width += determine_stage_width (SN_NETWORK_STAGE_GET (n, i));
180 } /* }}} double determine_network_width */
182 static int stage_print_lines (sn_stage_t *s, int *mask, double *x_left) /* {{{ */
184 int lines[s->comparators_num];
185 int right[s->comparators_num];
189 for (i = 0; i < s->comparators_num; i++)
195 for (i = 0; i < s->comparators_num; i++)
198 sn_comparator_t *c = s->comparators + i;
204 const char *left_class = "edge";
205 const char *right_class = "edge";
207 comp_left = SN_COMP_LEFT (c);
208 comp_right = SN_COMP_RIGHT (c);
210 mask_left = mask[comp_left];
211 mask_right = mask[comp_right];
213 for (j = 0; j < lines_used; j++)
214 if (comp_left > right[j])
218 right[j] = comp_right;
222 if ((mask_left == mask_right)
223 || ((mask_left <= 0) && (mask_right >= 0)))
227 left_class = "edge maximum";
229 right_class = "edge minimum";
231 x_right = x_offset + (j * inner_spacing);
233 printf ("\\path[%s] (%.2f,%.2f) -- (%.2f,%.2f);\n",
235 x_left[comp_left], INPUT_TO_Y (comp_left),
236 x_right, INPUT_TO_Y (comp_left));
237 printf ("\\path[%s] (%.2f,%.2f) -- (%.2f,%.2f);\n",
239 x_left[comp_right], INPUT_TO_Y (comp_right),
240 x_right, INPUT_TO_Y (comp_right));
242 x_left[comp_left] = x_right;
243 x_left[comp_right] = x_right;
246 x_offset = x_offset + ((lines_used - 1) * inner_spacing) + outer_spacing;
249 } /* }}} int stage_print_lines */
251 static int network_print_lines (sn_network_t *n, int *mask_orig) /* {{{ */
253 int mask[SN_NETWORK_INPUT_NUM (n)];
254 double x_left[SN_NETWORK_INPUT_NUM (n)];
257 memcpy (mask, mask_orig, sizeof (mask));
258 for (i = 0; i < SN_NETWORK_INPUT_NUM (n); i++)
261 x_offset = outer_spacing;
262 for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
264 stage_print_lines (SN_NETWORK_STAGE_GET (n, i), mask, x_left);
265 sn_stage_sort (SN_NETWORK_STAGE_GET (n, i), mask);
268 for (i = 0; i < SN_NETWORK_INPUT_NUM (n); i++)
270 const char *class = "edge";
273 class = "edge minimum";
274 else if (mask[i] > 0)
275 class = "edge maximum";
277 printf ("\\path[%s] (%.2f,%.2f) -- (%.2f,%.2f);\n",
279 x_left[i], INPUT_TO_Y (i),
280 x_offset, INPUT_TO_Y (i));
284 } /* }}} int network_print_lines */
286 static const char *mask_to_class (int left, int right, int *mask) /* {{{ */
288 if (mask[left] == mask[right])
292 else if (mask[left] > 0)
293 return (" inactive maximum");
295 return (" inactive minimum");
297 else if (mask[left] < mask[right])
299 if ((mask[left] < 0) && (mask[right] > 0))
300 return (" inactive minimum maximum");
301 else if (mask[left] < 0)
302 return (" inactive minimum");
304 return (" inactive maximum");
311 if ((mask[left] > 0) && (mask[right] < 0))
312 class = " active minimum maximum";
313 else if (mask[left] > 0)
314 class = " active maximum";
316 class = " active minimum";
319 mask[left] = mask[right];
324 } /* }}} const char *mask_to_class */
326 static int stage_print_comparators (sn_stage_t *s, int *mask) /* {{{ */
328 int lines[s->comparators_num];
329 int right[s->comparators_num];
333 for (i = 0; i < s->comparators_num; i++)
339 for (i = 0; i < s->comparators_num; i++)
342 sn_comparator_t *c = s->comparators + i;
348 min_num = next_vertex_number;
349 next_vertex_number++;
351 max_num = next_vertex_number;
352 next_vertex_number++;
354 for (j = 0; j < lines_used; j++)
355 if (SN_COMP_LEFT (c) > right[j])
359 right[j] = SN_COMP_RIGHT (c);
363 class = mask_to_class (SN_COMP_LEFT (c), SN_COMP_RIGHT (c), mask);
365 printf ("\\node[vertex%s] (v%i) at (%.2f,%.2f) {};\n"
366 "\\node[vertex%s] (v%i) at (%.2f,%.2f) {};\n"
367 "\\path[comp%s] (v%i) -- (v%i);\n"
369 class, min_num, x_offset + (j * inner_spacing), INPUT_TO_Y (c->min),
370 class, max_num, x_offset + (j * inner_spacing), INPUT_TO_Y (c->max),
371 class, min_num, max_num);
374 x_offset = x_offset + ((lines_used - 1) * inner_spacing) + outer_spacing;
377 } /* }}} int stage_print_comparators */
379 static int network_print_comparators (sn_network_t *n, int *mask_orig) /* {{{ */
381 int mask[SN_NETWORK_INPUT_NUM (n)];
384 memcpy (mask, mask_orig, sizeof (mask));
386 x_offset = outer_spacing;
387 for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
388 stage_print_comparators (SN_NETWORK_STAGE_GET (n, i), mask);
391 } /* }}} int network_print_comparators */
393 int main (int argc, char **argv) /* {{{ */
400 read_options (argc, argv);
402 if (input_file == NULL)
405 fh = fopen (input_file, "r");
410 n = sn_network_read (fh);
413 fprintf (stderr, "Unable to read network from file handle.\n");
417 status = read_mask (n, argc - optind, argv + optind);
420 fprintf (stderr, "read_mask failed.\n");
423 assert (mask != NULL);
425 orig_width = determine_network_width (n);
426 if (orig_width <= 0.0)
428 fprintf (stderr, "determine_network_width returned invalid value %g.\n",
433 scale = output_width / orig_width;
434 inner_spacing *= scale;
435 outer_spacing *= scale;
436 vertical_spacing *= scale;
438 printf ("\\begin{tikzpicture}[auto]\n");
440 network_print_lines (n, mask);
441 network_print_comparators (n, mask);
443 printf ("\\end{tikzpicture}\n");
448 /* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */