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