src/tsort.c

   1 /* tsort - topological sort.
   2    Copyright (C) 1998, 1999 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software Foundation,
  16    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  17
  18 /* Written by Mark Kettenis <kettenis@phys.uva.nl>.  */
  19
  20 /* The topological sort is done according to Algorithm T (Topological
  21    sort) in Donald E. Knuth, The Art of Computer Programming, Volume
  22    1/Fundamental Algorithms, page 262.  */
  23
  24 #ifdef HAVE_CONFIG_H
  25 # include <config.h>
  26 #endif
  27
  28 #include <stdio.h>
  29 #include <assert.h>
  30 #include <getopt.h>
  31
  32 #include "system.h"
  33 #include "long-options.h"
  34 #include "error.h"
  35 #include "readtokens.h"
  36
  37 /* The official name of this program (e.g., no `g' prefix).  */
  38 #define PROGRAM_NAME "tsort"
  39
  40 #define AUTHORS "Mark Kettenis"
  41
  42 /* Token delimiters when reading from a file.  */
  43 #define DELIM " \t\n"
  44
  45 char *xstrdup ();
  46
  47 /* Members of the list of successors.  */
  48 struct successor
  49 {
  50   struct item *suc;
  51   struct successor *next;
  52 };
  53
  54 /* Each string is held in core as the head of a list of successors.  */
  55 struct item
  56 {
  57   const char *str;
  58   struct item *left, *right;
  59   int balance;
  60   int count;
  61   struct item *qlink;
  62   struct successor *top;
  63 };
  64
  65 /* The name this program was run with. */
  66 char *program_name;
  67
  68 /* Nonzero if any of the input files are the standard input. */
  69 static int have_read_stdin;
  70
  71 /* The head of the sorted list.  */
  72 static struct item *head = NULL;
  73
  74 /* The tail of the list of `zeros', strings that have no predecessors.  */
  75 static struct item *zeros = NULL;
  76
  77 /* The number of strings to sort.  */
  78 static int n_strings = 0;
  79
  80 static struct option const long_options[] =
  81 {
  82   { NULL, 0, NULL, 0}
  83 };
  84 \f
  85 void
  86 usage (int status)
  87 {
  88   if (status != 0)
  89     fprintf (stderr, _("Try `%s --help' for more information.\n"),
  90              program_name);
  91   else
  92     {
  93       printf (_("\
  94 Usage: %s [OPTION] [FILE]\n\
  95 Write totally ordered list consistent with the partial ordering in FILE.\n\
  96 With no FILE, or when FILE is -, read standard input.\n\
  97 \n\
  98       --help       display this help and exit\n\
  99       --version    output version information and exit\n"),
 100               program_name);
 101       puts (_("\nReport bugs to <textutils-bugs@gnu.org>."));
 102     }
 103
 104   exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 105 }
 106
 107 /* Create a new item/node for STR.  */
 108 static struct item *
 109 new_item (const char *str)
 110 {
 111   struct item *k = xmalloc (sizeof (struct item));
 112
 113   k->str = (str ? xstrdup (str): NULL);
 114   k->left = k->right = NULL;
 115   k->balance = 0;
 116
 117   /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^).  */
 118   k->count = 0;
 119   k->qlink = NULL;
 120   k->top = NULL;
 121
 122   return k;
 123 }
 124
 125 /* Search binary tree rooted at *ROOT for STR.  Allocate a new tree if
 126    *ROOT is NULL.  Insert a node/item for STR if not found.  Return
 127    the node/item found/created for STR.
 128
 129    This is done according to Algorithm A (Balanced tree search and
 130    insertion) in Donald E. Knuth, The Art of Computer Programming,
 131    Volume 3/Searching and Sorting, pages 455--457.  */
 132
 133 static struct item *
 134 search_item (struct item *root, const char *str)
 135 {
 136   struct item *p, *q, *r, *s, *t;
 137   int a;
 138
 139   assert (root);
 140
 141   /* Make sure the tree is not empty, since that is what the algorithm
 142      below expects.  */
 143   if (root->right == NULL)
 144     return (root->right = new_item (str));
 145
 146   /* A1. Initialize.  */
 147   t = root;
 148   s = p = root->right;
 149
 150   for (;;)
 151     {
 152       /* A2. Compare.  */
 153       a = strcmp (str, p->str);
 154       if (a == 0)
 155         return p;
 156
 157       /* A3 & A4.  Move left & right.  */
 158       if (a < 0)
 159         q = p->left;
 160       else
 161         q = p->right;
 162
 163       if (q == NULL)
 164         {
 165           /* A5. Insert.  */
 166           q = new_item (str);
 167
 168           /* A3 & A4.  (continued).  */
 169           if (a < 0)
 170             p->left = q;
 171           else
 172             p->right = q;
 173
 174           /* A6. Adjust balance factors.  */
 175           assert (!STREQ (str, s->str));
 176           if (strcmp (str, s->str) < 0)
 177             {
 178               r = p = s->left;
 179               a = -1;
 180             }
 181           else
 182             {
 183               r = p = s->right;
 184               a = +1;
 185             }
 186
 187           while (p != q)
 188             {
 189               assert (!STREQ (str, p->str));
 190               if (strcmp (str, p->str) < 0)
 191                 {
 192                   p->balance = -1;
 193                   p = p->left;
 194                 }
 195               else
 196                 {
 197                   p->balance = +1;
 198                   p = p->right;
 199                 }
 200             }
 201
 202           /* A7. Balancing act.  */
 203           if (s->balance == 0 || s->balance == -a)
 204             {
 205               s->balance += a;
 206               return q;
 207             }
 208
 209           if (r->balance == a)
 210             {
 211               /* A8. Single Rotation.  */
 212               p = r;
 213               if (a < 0)
 214                 {
 215                   s->left = r->right;
 216                   r->right = s;
 217                 }
 218               else
 219                 {
 220                   s->right = r->left;
 221                   r->left = s;
 222                 }
 223               s->balance = r->balance = 0;
 224             }
 225           else
 226             {
 227               /* A9. Double rotation.  */
 228               if (a < 0)
 229                 {
 230                   p = r->right;
 231                   r->right = p->left;
 232                   p->left = r;
 233                   s->left = p->right;
 234                   p->right = s;
 235                 }
 236               else
 237                 {
 238                   p = r->left;
 239                   r->left = p->right;
 240                   p->right = r;
 241                   s->right = p->left;
 242                   p->left = s;
 243                 }
 244
 245               s->balance = 0;
 246               r->balance = 0;
 247               if (p->balance == a)
 248                 s->balance = -a;
 249               else if (p->balance == -a)
 250                 r->balance = a;
 251               p->balance = 0;
 252             }
 253
 254           /* A10. Finishing touch.  */
 255           if (s == t->right)
 256             t->right = p;
 257           else
 258             t->left = p;
 259
 260           return q;
 261         }
 262
 263       /* A3 & A4.  (continued).  */
 264       if (q->balance)
 265         {
 266           t = p;
 267           s = q;
 268         }
 269
 270       p = q;
 271     }
 272
 273   /* NOTREACHED */
 274 }
 275
 276 /* Record the fact that J precedes K.  */
 277
 278 static void
 279 record_relation (struct item *j, struct item *k)
 280 {
 281   struct successor *p;
 282
 283   if (!STREQ (j->str, k->str))
 284     {
 285       k->count++;
 286       p = xmalloc (sizeof (struct successor));
 287       p->suc = k;
 288       p->next = j->top;
 289       j->top = p;
 290     }
 291 }
 292
 293 static void
 294 count_items (struct item *k)
 295 {
 296   n_strings++;
 297 }
 298
 299 static void
 300 scan_zeros (struct item *k)
 301 {
 302   if (k->count == 0)
 303     {
 304       if (head == NULL)
 305         head = k;
 306       else
 307         zeros->qlink = k;
 308
 309       zeros = k;
 310     }
 311 }
 312
 313 /* If K is part of a loop, print the loop on standard error, and exit.  */
 314
 315 static void
 316 detect_loop (struct item *k)
 317 {
 318   if (k->count > 0)
 319     {
 320       while (k && k->count > 0)
 321         {
 322           k->count = 0;
 323           fprintf (stderr, "%s: %s\n", program_name, k->str);
 324           k = k->top->suc;
 325         }
 326
 327       exit (EXIT_FAILURE);
 328     }
 329 }
 330
 331 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.  */
 332
 333 static void
 334 recurse_tree (struct item *root, void (*action) (struct item *))
 335 {
 336   if (root->left == NULL && root->right == NULL)
 337     (*action) (root);
 338   else
 339     {
 340       if (root->left != NULL)
 341         recurse_tree (root->left, action);
 342       (*action) (root);
 343       if (root->right != NULL)
 344         recurse_tree (root->right, action);
 345     }
 346 }
 347
 348 /* Walk the tree specified by the head ROOT, calling ACTION for
 349    each node.  */
 350
 351 static void
 352 walk_tree (struct item *root, void (*action) (struct item *))
 353 {
 354   if (root->right)
 355     recurse_tree (root->right, action);
 356 }
 357
 358 /* Do a topological sort on FILE.   */
 359
 360 static void
 361 tsort (const char *file)
 362 {
 363   struct item *root;
 364   struct item *j = NULL;
 365   struct item *k = NULL;
 366   register FILE *fp;
 367   token_buffer tokenbuffer;
 368
 369   /* Intialize the head of the tree will hold the strings we're sorting.  */
 370   root = new_item (NULL);
 371
 372   if (STREQ (file, "-"))
 373     {
 374       fp = stdin;
 375       have_read_stdin = 1;
 376     }
 377   else
 378     {
 379       fp = fopen (file, "r");
 380       if (fp == NULL)
 381         error (EXIT_FAILURE, errno, "%s", file);
 382     }
 383
 384   init_tokenbuffer (&tokenbuffer);
 385
 386   while (1)
 387     {
 388       long int len;
 389
 390       /* T2. Next Relation.  */
 391       len = readtoken (fp, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
 392       if (len < 0)
 393         break;
 394
 395       assert (len != 0);
 396
 397       k = search_item (root, tokenbuffer.buffer);
 398       if (j)
 399         {
 400           /* T3. Record the relation.  */
 401           record_relation (j, k);
 402           k = NULL;
 403         }
 404
 405       j = k;
 406     }
 407
 408   /* T1. Initialize (N <- n).  */
 409   walk_tree (root, count_items);
 410
 411   /* T4. Scan for zeros.  */
 412   walk_tree (root, scan_zeros);
 413
 414   while (head)
 415     {
 416       struct successor *p = head->top;
 417
 418       /* T5. Output front of queue.  */
 419       printf ("%s\n", head->str);
 420       n_strings--;
 421
 422       /* T6. Erase relations.  */
 423       while (p)
 424         {
 425           p->suc->count--;
 426           if (p->suc->count == 0)
 427             {
 428               zeros->qlink = p->suc;
 429               zeros = p->suc;
 430             }
 431
 432           p = p->next;
 433         }
 434
 435       /* T7. Remove from queue.  */
 436       head = head->qlink;
 437     }
 438
 439   /* T8.  End of process.  */
 440   assert (n_strings >= 0);
 441   if (n_strings > 0)
 442     {
 443       error (0, 0, _("%s: input contains a loop:\n"),
 444              (have_read_stdin ? "-" : file));
 445
 446       /* Print out loop.  */
 447       walk_tree (root, detect_loop);
 448
 449       /* Should not happen.  */
 450       error (EXIT_FAILURE, 0, _("could not find loop"));
 451     }
 452 }
 453
 454 int
 455 main (int argc, char **argv)
 456 {
 457   int opt;
 458
 459   program_name = argv[0];
 460   setlocale (LC_ALL, "");
 461   bindtextdomain (PACKAGE, LOCALEDIR);
 462   textdomain (PACKAGE);
 463
 464   parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
 465                       "Mark Kettenis", usage);
 466
 467   while ((opt = getopt_long (argc, argv, "", long_options, NULL)) != -1)
 468     switch (opt)
 469       {
 470       case 0:                   /* long option */
 471         break;
 472       default:
 473         usage (EXIT_FAILURE);
 474       }
 475
 476   have_read_stdin = 0;
 477
 478   if (optind + 1 < argc)
 479     {
 480       error (0, 0, _("only one argument may be specified"));
 481       usage (EXIT_FAILURE);
 482     }
 483
 484   if (optind < argc)
 485     tsort (argv[optind]);
 486   else
 487     tsort ("-");
 488
 489   if (fclose (stdout) == EOF)
 490     error (EXIT_FAILURE, errno, _("write error"));
 491
 492   if (have_read_stdin && fclose (stdin) == EOF)
 493     error (EXIT_FAILURE, errno, _("standard input"));
 494
 495   exit (EXIT_SUCCESS);
 496 }