1 /* tsort - topological sort.
2 Copyright (C) 1998-2005, 2007-2008 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 3 of the License, or
7 (at your option) any later version.
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, see <http://www.gnu.org/licenses/>. */
17 /* Written by Mark Kettenis <kettenis@phys.uva.nl>. */
19 /* The topological sort is done according to Algorithm T (Topological
20 sort) in Donald E. Knuth, The Art of Computer Programming, Volume
21 1/Fundamental Algorithms, page 262. */
28 #include <sys/types.h>
31 #include "long-options.h"
34 #include "readtokens.h"
36 /* The official name of this program (e.g., no `g' prefix). */
37 #define PROGRAM_NAME "tsort"
39 #define AUTHORS proper_name ("Mark Kettenis")
41 /* Token delimiters when reading from a file. */
44 /* Members of the list of successors. */
48 struct successor *next;
51 /* Each string is held in core as the head of a list of successors. */
55 struct item *left, *right;
56 int balance; /* -1, 0, or +1 */
59 struct successor *top;
62 /* The name this program was run with. */
63 char const *program_name;
65 /* The head of the sorted list. */
66 static struct item *head = NULL;
68 /* The tail of the list of `zeros', strings that have no predecessors. */
69 static struct item *zeros = NULL;
71 /* Used for loop detection. */
72 static struct item *loop = NULL;
74 /* The number of strings to sort. */
75 static size_t n_strings = 0;
80 if (status != EXIT_SUCCESS)
81 fprintf (stderr, _("Try `%s --help' for more information.\n"),
86 Usage: %s [OPTION] [FILE]\n\
87 Write totally ordered list consistent with the partial ordering in FILE.\n\
88 With no FILE, or when FILE is -, read standard input.\n\
91 fputs (HELP_OPTION_DESCRIPTION, stdout);
92 fputs (VERSION_OPTION_DESCRIPTION, stdout);
93 emit_bug_reporting_address ();
99 /* Create a new item/node for STR. */
101 new_item (const char *str)
103 struct item *k = xmalloc (sizeof *k);
105 k->str = (str ? xstrdup (str): NULL);
106 k->left = k->right = NULL;
109 /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^). */
117 /* Search binary tree rooted at *ROOT for STR. Allocate a new tree if
118 *ROOT is NULL. Insert a node/item for STR if not found. Return
119 the node/item found/created for STR.
121 This is done according to Algorithm A (Balanced tree search and
122 insertion) in Donald E. Knuth, The Art of Computer Programming,
123 Volume 3/Searching and Sorting, pages 455--457. */
126 search_item (struct item *root, const char *str)
128 struct item *p, *q, *r, *s, *t;
133 /* Make sure the tree is not empty, since that is what the algorithm
135 if (root->right == NULL)
136 return (root->right = new_item (str));
138 /* A1. Initialize. */
145 a = strcmp (str, p->str);
149 /* A3 & A4. Move left & right. */
160 /* A3 & A4. (continued). */
166 /* A6. Adjust balance factors. */
167 assert (!STREQ (str, s->str));
168 if (strcmp (str, s->str) < 0)
181 assert (!STREQ (str, p->str));
182 if (strcmp (str, p->str) < 0)
194 /* A7. Balancing act. */
195 if (s->balance == 0 || s->balance == -a)
203 /* A8. Single Rotation. */
215 s->balance = r->balance = 0;
219 /* A9. Double rotation. */
241 else if (p->balance == -a)
246 /* A10. Finishing touch. */
255 /* A3 & A4. (continued). */
268 /* Record the fact that J precedes K. */
271 record_relation (struct item *j, struct item *k)
275 if (!STREQ (j->str, k->str))
278 p = xmalloc (sizeof *p);
286 count_items (struct item *unused ATTRIBUTE_UNUSED)
293 scan_zeros (struct item *k)
295 /* Ignore strings that have already been printed. */
296 if (k->count == 0 && k->str)
309 /* Try to detect the loop. If we have detected that K is part of a
310 loop, print the loop on standard error, remove a relation to break
311 the loop, and return true.
313 The loop detection strategy is as follows: Realise that what we're
314 dealing with is essentially a directed graph. If we find an item
315 that is part of a graph that contains a cycle we traverse the graph
316 in backwards direction. In general there is no unique way to do
317 this, but that is no problem. If we encounter an item that we have
318 encountered before, we know that we've found a cycle. All we have
319 to do now is retrace our steps, printing out the items until we
320 encounter that item again. (This is not necessarily the item that
321 we started from originally.) Since the order in which the items
322 are stored in the tree is not related to the specified partial
323 ordering, we may need to walk the tree several times before the
324 loop has completely been constructed. If the loop was found, the
325 global variable LOOP will be NULL. */
328 detect_loop (struct item *k)
332 /* K does not have to be part of a cycle. It is however part of
333 a graph that contains a cycle. */
336 /* Start traversing the graph at K. */
340 struct successor **p = &k->top;
344 if ((*p)->suc == loop)
348 /* We have found a loop. Retrace our steps. */
351 struct item *tmp = loop->qlink;
353 fprintf (stderr, "%s: %s\n", program_name,
356 /* Until we encounter K again. */
359 /* Remove relation. */
365 /* Tidy things up since we might have to
366 detect another loop. */
373 struct item *tmp = loop->qlink;
379 /* Since we have found the loop, stop walking
399 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.
400 Stop when ACTION returns true. */
403 recurse_tree (struct item *root, bool (*action) (struct item *))
405 if (root->left == NULL && root->right == NULL)
406 return (*action) (root);
409 if (root->left != NULL)
410 if (recurse_tree (root->left, action))
412 if ((*action) (root))
414 if (root->right != NULL)
415 if (recurse_tree (root->right, action))
422 /* Walk the tree specified by the head ROOT, calling ACTION for
426 walk_tree (struct item *root, bool (*action) (struct item *))
429 recurse_tree (root->right, action);
432 /* Do a topological sort on FILE. Return true if successful. */
435 tsort (const char *file)
439 struct item *j = NULL;
440 struct item *k = NULL;
441 token_buffer tokenbuffer;
442 bool is_stdin = STREQ (file, "-");
444 /* Intialize the head of the tree will hold the strings we're sorting. */
445 root = new_item (NULL);
447 if (!is_stdin && ! freopen (file, "r", stdin))
448 error (EXIT_FAILURE, errno, "%s", file);
450 init_tokenbuffer (&tokenbuffer);
454 /* T2. Next Relation. */
455 size_t len = readtoken (stdin, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
456 if (len == (size_t) -1)
461 k = search_item (root, tokenbuffer.buffer);
464 /* T3. Record the relation. */
465 record_relation (j, k);
473 error (EXIT_FAILURE, 0, _("%s: input contains an odd number of tokens"),
476 /* T1. Initialize (N <- n). */
477 walk_tree (root, count_items);
479 while (n_strings > 0)
481 /* T4. Scan for zeros. */
482 walk_tree (root, scan_zeros);
486 struct successor *p = head->top;
488 /* T5. Output front of queue. */
490 head->str = NULL; /* Avoid printing the same string twice. */
493 /* T6. Erase relations. */
497 if (p->suc->count == 0)
499 zeros->qlink = p->suc;
506 /* T7. Remove from queue. */
510 /* T8. End of process. */
513 /* The input contains a loop. */
514 error (0, 0, _("%s: input contains a loop:"), file);
517 /* Print the loop and remove a relation to break it. */
519 walk_tree (root, detect_loop);
524 if (fclose (stdin) != 0)
525 error (EXIT_FAILURE, errno, "%s",
526 is_stdin ? _("standard input") : quote (file));
532 main (int argc, char **argv)
536 initialize_main (&argc, &argv);
537 program_name = argv[0];
538 setlocale (LC_ALL, "");
539 bindtextdomain (PACKAGE, LOCALEDIR);
540 textdomain (PACKAGE);
542 atexit (close_stdout);
544 parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE, VERSION,
545 usage, AUTHORS, (char const *) NULL);
546 if (getopt_long (argc, argv, "", NULL, NULL) != -1)
547 usage (EXIT_FAILURE);
549 if (1 < argc - optind)
551 error (0, 0, _("extra operand %s"), quote (argv[optind + 1]));
552 usage (EXIT_FAILURE);
555 ok = tsort (optind == argc ? "-" : argv[optind]);
557 exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);