1 /* tsort - topological sort.
2 Copyright (C) 1998, 1999 Free Software Foundation, Inc.
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)
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.
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. */
18 /* Written by Mark Kettenis <kettenis@phys.uva.nl>. */
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. */
33 #include "long-options.h"
35 #include "readtokens.h"
37 /* Token delimiters when reading from a file. */
42 /* Members of the list of successors. */
46 struct successor *next;
49 /* Each string is held in core as the head of a list of successors. */
53 struct item *left, *right;
57 struct successor *top;
60 /* The name this program was run with. */
63 /* Nonzero if any of the input files are the standard input. */
64 static int have_read_stdin;
66 /* The head of the sorted list. */
67 static struct item *head = NULL;
69 /* The tail of the list of `zeros', strings that have no predecessors. */
70 static struct item *zeros = NULL;
72 /* The number of strings to sort. */
73 static int n_strings = 0;
75 static struct option const long_options[] =
84 fprintf (stderr, _("Try `%s --help' for more information.\n"),
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\
93 --help display this help and exit\n\
94 --version output version information and exit\n"),
96 puts (_("\nReport bugs to <textutils-bugs@gnu.org>."));
99 exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
102 /* Create a new item/node for STR. */
104 new_item (const char *str)
106 struct item *k = xmalloc (sizeof (struct item));
108 k->str = (str ? xstrdup (str): NULL);
109 k->left = k->right = NULL;
112 /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^). */
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.
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. */
129 search_item (struct item *root, const char *str)
131 struct item *p, *q, *r, *s, *t;
136 /* Make sure the tree is not empty, since that is what the algorithm
138 if (root->right == NULL)
139 return (root->right = new_item (str));
141 /* A1. Initialize. */
148 a = strcmp (str, p->str);
152 /* A3 & A4. Move left & right. */
163 /* A3 & A4. (continued). */
169 /* A6. Adjust balance factors. */
170 assert (!STREQ (str, s->str));
171 if (strcmp (str, s->str) < 0)
184 assert (!STREQ (str, p->str));
185 if (strcmp (str, p->str) < 0)
197 /* A7. Balancing act. */
198 if (s->balance == 0 || s->balance == -a)
206 /* A8. Single Rotation. */
218 s->balance = r->balance = 0;
222 /* A9. Double rotation. */
244 else if (p->balance == -a)
249 /* A10. Finishing touch. */
258 /* A3 & A4. (continued). */
271 /* Record the fact that J precedes K. */
274 record_relation (struct item *j, struct item *k)
278 if (!STREQ (j->str, k->str))
281 p = xmalloc (sizeof (struct successor));
289 count_items (struct item *k)
295 scan_zeros (struct item *k)
308 /* If K is part of a loop, print the loop on standard error, and exit. */
311 detect_loop (struct item *k)
315 while (k && k->count > 0)
318 fprintf (stderr, "%s: %s\n", program_name, k->str);
326 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node. */
329 recurse_tree (struct item *root, void (*action) (struct item *))
331 if (root->left == NULL && root->right == NULL)
335 if (root->left != NULL)
336 recurse_tree (root->left, action);
338 if (root->right != NULL)
339 recurse_tree (root->right, action);
343 /* Walk the tree specified by the head ROOT, calling ACTION for
347 walk_tree (struct item *root, void (*action) (struct item *))
350 recurse_tree (root->right, action);
353 /* Do a topological sort on FILE. */
356 tsort (const char *file)
359 struct item *j = NULL;
360 struct item *k = NULL;
362 token_buffer tokenbuffer;
364 /* Intialize the head of the tree will hold the strings we're sorting. */
365 root = new_item (NULL);
367 if (STREQ (file, "-"))
374 fp = fopen (file, "r");
376 error (EXIT_FAILURE, errno, "%s", file);
379 init_tokenbuffer (&tokenbuffer);
385 /* T2. Next Relation. */
386 len = readtoken (fp, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
392 k = search_item (root, tokenbuffer.buffer);
395 /* T3. Record the relation. */
396 record_relation (j, k);
403 /* T1. Initialize (N <- n). */
404 walk_tree (root, count_items);
406 /* T4. Scan for zeros. */
407 walk_tree (root, scan_zeros);
411 struct successor *p = head->top;
413 /* T5. Output front of queue. */
414 printf ("%s\n", head->str);
417 /* T6. Erase relations. */
421 if (p->suc->count == 0)
423 zeros->qlink = p->suc;
430 /* T7. Remove from queue. */
434 /* T8. End of process. */
435 assert (n_strings >= 0);
438 error (0, 0, _("%s: input contains a loop:\n"),
439 (have_read_stdin ? "-" : file));
441 /* Print out loop. */
442 walk_tree (root, detect_loop);
444 /* Should not happen. */
445 error (EXIT_FAILURE, 0, _("could not find loop"));
450 main (int argc, char **argv)
454 program_name = argv[0];
455 setlocale (LC_ALL, "");
456 bindtextdomain (PACKAGE, LOCALEDIR);
457 textdomain (PACKAGE);
459 parse_long_options (argc, argv, "tsort", GNU_PACKAGE, VERSION,
460 "Mark Kettenis", usage);
462 while ((opt = getopt_long (argc, argv, "", long_options, NULL)) != -1)
465 case 0: /* long option */
468 usage (EXIT_FAILURE);
473 if (optind + 1 < argc)
475 error (0, 0, _("only one argument may be specified"));
476 usage (EXIT_FAILURE);
480 tsort (argv[optind]);
484 if (fclose (stdout) == EOF)
485 error (EXIT_FAILURE, errno, _("write error"));
487 if (have_read_stdin && fclose (stdin) == EOF)
488 error (EXIT_FAILURE, errno, _("standard input"));