src/sn-tex-cut.c

   1 /**
   2  * libsortnetwork - src/sn-tex.c
   3  * Copyright (C) 2008-2010  Florian octo Forster
   4  *
   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.
   8  *
   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.
  13  *
  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
  17  *
  18  * Authors:
  19  *   Florian octo Forster <ff at octo.it>
  20  **/
  21
  22 #include "config.h"
  23
  24 #ifndef _ISOC99_SOURCE
  25 # define _ISOC99_SOURCE
  26 #endif
  27 #ifndef _POSIX_C_SOURCE
  28 # define _POSIX_C_SOURCE 200112L
  29 #endif
  30
  31 #include <stdlib.h>
  32 #include <stdio.h>
  33 #include <string.h>
  34 #include <strings.h>
  35 #include <unistd.h>
  36 #include <assert.h>
  37 #include <errno.h>
  38
  39 #include "sn_network.h"
  40
  41 const char *input_file = NULL;
  42
  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;
  49
  50 static double x_offset;
  51 static int next_vertex_number = 0;
  52
  53 static int *mask = NULL;
  54
  55 #define INPUT_TO_Y(i) (((double) (i)) * vertical_spacing)
  56
  57 static void exit_usage (void) /* {{{ */
  58 {
  59   printf ("Usage: sn-tex-cut [options] <num>[:min|max] [<num>[:min|max] ...]\n"
  60       "\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"
  64       "\n");
  65   exit (EXIT_FAILURE);
  66 } /* }}} void exit_usage */
  67
  68 static int read_options (int argc, char **argv) /* {{{ */
  69 {
  70   int option;
  71
  72   while ((option = getopt (argc, argv, "w:i:h?")) != -1)
  73   {
  74     switch (option)
  75     {
  76       case 'w':
  77       {
  78         double width = atof (optarg);
  79         if (width <= 0.0)
  80         {
  81           fprintf (stderr, "Invalid width argument: %s\n", optarg);
  82           exit (EXIT_FAILURE);
  83         }
  84         output_width = width;
  85         break;
  86       }
  87
  88       case 'i':
  89       input_file = optarg;
  90       break;
  91
  92       case 'h':
  93       case '?':
  94       default:
  95         exit_usage ();
  96     }
  97   }
  98
  99   return (0);
 100 } /* }}} int read_options */
 101
 102 static int read_mask (sn_network_t *n, int argc, char **argv) /* {{{ */
 103 {
 104   int i;
 105
 106   mask = calloc (SN_NETWORK_INPUT_NUM (n), sizeof (*mask));
 107   if (mask == NULL)
 108     return (ENOMEM);
 109
 110   for (i = 0; i < argc; i++)
 111   {
 112     char *endptr = NULL;
 113     int pos;
 114     int val = 1;
 115
 116     pos = (int) strtol (argv[i], &endptr, /* base = */ 0);
 117     if (strcasecmp (":min", endptr) == 0)
 118       val = -1;
 119
 120     if ((pos < 0) || (pos >= SN_NETWORK_INPUT_NUM (n)))
 121     {
 122       fprintf (stderr, "Invalid line number: %i\n", pos);
 123       return (-1);
 124     }
 125
 126     mask[pos] = val;
 127   }
 128
 129   return (0);
 130 } /* }}} int read_mask */
 131
 132 static double determine_stage_width (sn_stage_t *s) /* {{{ */
 133 {
 134   int lines[s->comparators_num];
 135   int right[s->comparators_num];
 136   int lines_used = 0;
 137   int i;
 138
 139   if (SN_STAGE_COMP_NUM (s) == 0)
 140     return (0.0);
 141
 142   for (i = 0; i < SN_STAGE_COMP_NUM (s); i++)
 143   {
 144     lines[i] = -1;
 145     right[i] = -1;
 146   }
 147
 148   for (i = 0; i < SN_STAGE_COMP_NUM (s); i++)
 149   {
 150     int j;
 151     sn_comparator_t *c = SN_STAGE_COMP_GET (s, i);
 152
 153     for (j = 0; j < lines_used; j++)
 154       if (SN_COMP_LEFT (c) > right[j])
 155         break;
 156
 157     lines[i] = j;
 158     right[j] = SN_COMP_RIGHT (c);
 159     if (j >= lines_used)
 160       lines_used = j + 1;
 161   }
 162   assert (lines_used >= 1);
 163
 164   return (((double) (lines_used - 1)) * inner_spacing);
 165 } /* }}} double determine_stage_width */
 166
 167 static double determine_network_width (sn_network_t *n) /* {{{ */
 168 {
 169   double width;
 170   int i;
 171
 172   /* Spacing between stages and at the beginning and end of the network */
 173   width = (SN_NETWORK_STAGE_NUM (n) + 1) * outer_spacing;
 174
 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));
 178
 179   return (width);
 180 } /* }}} double determine_network_width */
 181
 182 static int stage_print_lines (sn_stage_t *s, int *mask, double *x_left) /* {{{ */
 183 {
 184   int lines[s->comparators_num];
 185   int right[s->comparators_num];
 186   int lines_used = 0;
 187   int i;
 188
 189   for (i = 0; i < s->comparators_num; i++)
 190   {
 191     lines[i] = -1;
 192     right[i] = -1;
 193   }
 194
 195   for (i = 0; i < s->comparators_num; i++)
 196   {
 197     int j;
 198     sn_comparator_t *c = s->comparators + i;
 199     double x_right;
 200     int comp_left;
 201     int comp_right;
 202     int mask_left;
 203     int mask_right;
 204     const char *left_class  = "edge";
 205     const char *right_class = "edge";
 206
 207     comp_left  = SN_COMP_LEFT (c);
 208     comp_right = SN_COMP_RIGHT (c);
 209
 210     mask_left = mask[comp_left];
 211     mask_right = mask[comp_right];
 212
 213     for (j = 0; j < lines_used; j++)
 214       if (comp_left > right[j])
 215         break;
 216
 217     lines[i] = j;
 218     right[j] = comp_right;
 219     if (j >= lines_used)
 220       lines_used = j + 1;
 221
 222     if ((mask_left == mask_right)
 223         || ((mask_left <= 0) && (mask_right >= 0)))
 224       continue;
 225
 226     if (mask_left > 0)
 227       left_class = "edge maximum";
 228     if (mask_right < 0)
 229       right_class = "edge minimum";
 230
 231     x_right = x_offset + (j * inner_spacing);
 232
 233     printf ("\\path[%s] (%.2f,%.2f) -- (%.2f,%.2f);\n",
 234         left_class,
 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",
 238         right_class,
 239         x_left[comp_right], INPUT_TO_Y (comp_right),
 240         x_right, INPUT_TO_Y (comp_right));
 241
 242     x_left[comp_left] = x_right;
 243     x_left[comp_right] = x_right;
 244   }
 245
 246   x_offset = x_offset + ((lines_used - 1) * inner_spacing) + outer_spacing;
 247
 248   return (0);
 249 } /* }}} int stage_print_lines */
 250
 251 static int network_print_lines (sn_network_t *n, int *mask_orig) /* {{{ */
 252 {
 253   int mask[SN_NETWORK_INPUT_NUM (n)];
 254   double x_left[SN_NETWORK_INPUT_NUM (n)];
 255   int i;
 256
 257   memcpy (mask, mask_orig, sizeof (mask));
 258   for (i = 0; i < SN_NETWORK_INPUT_NUM (n); i++)
 259     x_left[i] = 0.0;
 260
 261   x_offset = outer_spacing;
 262   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
 263   {
 264     stage_print_lines (SN_NETWORK_STAGE_GET (n, i), mask, x_left);
 265     sn_stage_sort (SN_NETWORK_STAGE_GET (n, i), mask);
 266   }
 267
 268   for (i = 0; i < SN_NETWORK_INPUT_NUM (n); i++)
 269   {
 270     const char *class = "edge";
 271
 272     if (mask[i] < 0)
 273       class = "edge minimum";
 274     else if (mask[i] > 0)
 275       class = "edge maximum";
 276
 277     printf ("\\path[%s] (%.2f,%.2f) -- (%.2f,%.2f);\n",
 278         class,
 279         x_left[i], INPUT_TO_Y (i),
 280         x_offset, INPUT_TO_Y (i));
 281   }
 282
 283   return (0);
 284 } /* }}} int network_print_lines */
 285
 286 static const char *mask_to_class (int left, int right, int *mask) /* {{{ */
 287 {
 288   if (mask[left] == mask[right])
 289   {
 290     if (mask[left] == 0)
 291       return ("");
 292     else if (mask[left] > 0)
 293       return (" inactive maximum");
 294     else
 295       return (" inactive minimum");
 296   }
 297   else if (mask[left] < mask[right])
 298   {
 299     if ((mask[left] < 0) && (mask[right] > 0))
 300       return (" inactive minimum maximum");
 301     else if (mask[left] < 0)
 302       return (" inactive minimum");
 303     else
 304       return (" inactive maximum");
 305   }
 306   else
 307   {
 308     const char *class;
 309     int tmp;
 310
 311     if ((mask[left] > 0) && (mask[right] < 0))
 312       class = " active minimum maximum";
 313     else if (mask[left] > 0)
 314       class = " active maximum";
 315     else
 316       class = " active minimum";
 317
 318     tmp = mask[left];
 319     mask[left] = mask[right];
 320     mask[right] = tmp;
 321
 322     return (class);
 323   }
 324 } /* }}} const char *mask_to_class */
 325
 326 static int stage_print_comparators (sn_stage_t *s, int *mask) /* {{{ */
 327 {
 328   int lines[s->comparators_num];
 329   int right[s->comparators_num];
 330   int lines_used = 0;
 331   int i;
 332
 333   for (i = 0; i < s->comparators_num; i++)
 334   {
 335     lines[i] = -1;
 336     right[i] = -1;
 337   }
 338
 339   for (i = 0; i < s->comparators_num; i++)
 340   {
 341     int j;
 342     sn_comparator_t *c = s->comparators + i;
 343     const char *class;
 344
 345     int min_num;
 346     int max_num;
 347
 348     min_num = next_vertex_number;
 349     next_vertex_number++;
 350
 351     max_num = next_vertex_number;
 352     next_vertex_number++;
 353
 354     for (j = 0; j < lines_used; j++)
 355       if (SN_COMP_LEFT (c) > right[j])
 356         break;
 357
 358     lines[i] = j;
 359     right[j] = SN_COMP_RIGHT (c);
 360     if (j >= lines_used)
 361       lines_used = j + 1;
 362
 363     class = mask_to_class (SN_COMP_LEFT (c), SN_COMP_RIGHT (c), mask);
 364
 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"
 368         "\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);
 372   }
 373
 374   x_offset = x_offset + ((lines_used - 1) * inner_spacing) + outer_spacing;
 375
 376   return (0);
 377 } /* }}} int stage_print_comparators */
 378
 379 static int network_print_comparators (sn_network_t *n, int *mask_orig) /* {{{ */
 380 {
 381   int mask[SN_NETWORK_INPUT_NUM (n)];
 382   int i;
 383
 384   memcpy (mask, mask_orig, sizeof (mask));
 385
 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);
 389
 390   return (0);
 391 } /* }}} int network_print_comparators */
 392
 393 int main (int argc, char **argv) /* {{{ */
 394 {
 395   sn_network_t *n;
 396   FILE *fh = NULL;
 397   double orig_width;
 398   int status;
 399
 400   read_options (argc, argv);
 401
 402   if (input_file == NULL)
 403     fh = stdin;
 404   else
 405     fh = fopen (input_file, "r");
 406
 407   if (fh == NULL)
 408     exit_usage ();
 409
 410   n = sn_network_read (fh);
 411   if (n == NULL)
 412   {
 413     fprintf (stderr, "Unable to read network from file handle.\n");
 414     exit (EXIT_FAILURE);
 415   }
 416
 417   status = read_mask (n, argc - optind, argv + optind);
 418   if (status != 0)
 419   {
 420     fprintf (stderr, "read_mask failed.\n");
 421     exit (EXIT_FAILURE);
 422   }
 423   assert (mask != NULL);
 424
 425   orig_width = determine_network_width (n);
 426   if (orig_width <= 0.0)
 427   {
 428     fprintf (stderr, "determine_network_width returned invalid value %g.\n",
 429         orig_width);
 430     exit (EXIT_FAILURE);
 431   }
 432
 433   scale = output_width / orig_width;
 434   inner_spacing *= scale;
 435   outer_spacing *= scale;
 436   vertical_spacing *= scale;
 437
 438   printf ("\\begin{tikzpicture}[auto]\n");
 439
 440   network_print_lines (n, mask);
 441   network_print_comparators (n, mask);
 442
 443   printf ("\\end{tikzpicture}\n");
 444
 445   return (0);
 446 } /* }}} int main */
 447
 448 /* vim: set shiftwidth=2 softtabstop=2 fdm=marker : */