1 /* tsort - topological sort.
2 Copyright (C) 1998, 1999, 2000, 2001 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. */
29 #include <sys/types.h>
33 #include "long-options.h"
35 #include "readtokens.h"
37 /* The official name of this program (e.g., no `g' prefix). */
38 #define PROGRAM_NAME "tsort"
40 #define AUTHORS "Mark Kettenis"
42 /* Token delimiters when reading from a file. */
45 /* Members of the list of successors. */
49 struct successor *next;
52 /* Each string is held in core as the head of a list of successors. */
56 struct item *left, *right;
60 struct successor *top;
63 /* The name this program was run with. */
66 /* Nonzero if any of the input files are the standard input. */
67 static int have_read_stdin;
69 /* The error code to return to the system. */
70 static int exit_status;
72 /* The head of the sorted list. */
73 static struct item *head = NULL;
75 /* The tail of the list of `zeros', strings that have no predecessors. */
76 static struct item *zeros = NULL;
78 /* Used for loop detection. */
79 static struct item *loop = NULL;
81 /* The number of strings to sort. */
82 static int n_strings = 0;
84 static struct option const long_options[] =
93 fprintf (stderr, _("Try `%s --help' for more information.\n"),
98 Usage: %s [OPTION] [FILE]\n\
99 Write totally ordered list consistent with the partial ordering in FILE.\n\
100 With no FILE, or when FILE is -, read standard input.\n\
102 --help display this help and exit\n\
103 --version output version information and exit\n"),
105 puts (_("\nReport bugs to <bug-textutils@gnu.org>."));
108 exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
111 /* Create a new item/node for STR. */
113 new_item (const char *str)
115 struct item *k = xmalloc (sizeof (struct item));
117 k->str = (str ? xstrdup (str): NULL);
118 k->left = k->right = NULL;
121 /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^). */
129 /* Search binary tree rooted at *ROOT for STR. Allocate a new tree if
130 *ROOT is NULL. Insert a node/item for STR if not found. Return
131 the node/item found/created for STR.
133 This is done according to Algorithm A (Balanced tree search and
134 insertion) in Donald E. Knuth, The Art of Computer Programming,
135 Volume 3/Searching and Sorting, pages 455--457. */
138 search_item (struct item *root, const char *str)
140 struct item *p, *q, *r, *s, *t;
145 /* Make sure the tree is not empty, since that is what the algorithm
147 if (root->right == NULL)
148 return (root->right = new_item (str));
150 /* A1. Initialize. */
157 a = strcmp (str, p->str);
161 /* A3 & A4. Move left & right. */
172 /* A3 & A4. (continued). */
178 /* A6. Adjust balance factors. */
179 assert (!STREQ (str, s->str));
180 if (strcmp (str, s->str) < 0)
193 assert (!STREQ (str, p->str));
194 if (strcmp (str, p->str) < 0)
206 /* A7. Balancing act. */
207 if (s->balance == 0 || s->balance == -a)
215 /* A8. Single Rotation. */
227 s->balance = r->balance = 0;
231 /* A9. Double rotation. */
253 else if (p->balance == -a)
258 /* A10. Finishing touch. */
267 /* A3 & A4. (continued). */
280 /* Record the fact that J precedes K. */
283 record_relation (struct item *j, struct item *k)
287 if (!STREQ (j->str, k->str))
290 p = xmalloc (sizeof (struct successor));
298 count_items (struct item *unused ATTRIBUTE_UNUSED)
305 scan_zeros (struct item *k)
307 /* Ignore strings that have already been printed. */
308 if (k->count == 0 && k->str)
321 /* Try to detect the loop. If we have detected that K is part of a
322 loop, print the loop on standard error, remove a relation to break
323 the loop, and return non-zero.
325 The loop detection strategy is as follows: Realise that what we're
326 dealing with is essentially a directed graph. If we find an item
327 that is part of a graph that contains a cycle we traverse the graph
328 in backwards direction. In general there is no unique way to do
329 this, but that is no problem. If we encounter an item that we have
330 encountered before, we know that we've found a cycle. All we have
331 to do now is retrace our steps, printing out the items until we
332 encounter that item again. (This is not necessarily the item that
333 we started from originally.) Since the order in which the items
334 are stored in the tree is not related to the specified partial
335 ordering, we may need to walk the tree several times before the
336 loop has completely been constructed. If the loop was found, the
337 global variable LOOP will be NULL. */
340 detect_loop (struct item *k)
344 /* K does not have to be part of a cycle. It is however part of
345 a graph that contains a cycle. */
348 /* Start traversing the graph at K. */
352 struct successor **p = &k->top;
356 if ((*p)->suc == loop)
360 /* We have found a loop. Retrace our steps. */
363 struct item *tmp = loop->qlink;
365 fprintf (stderr, "%s: %s\n", program_name,
368 /* Until we encounter K again. */
371 /* Remove relation. */
377 /* Tidy things up since we might have to
378 detect another loop. */
385 struct item *tmp = loop->qlink;
391 /* Since we have found the loop, stop walking
411 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.
412 Stop when ACTION returns non-zero. */
415 recurse_tree (struct item *root, int (*action) (struct item *))
417 if (root->left == NULL && root->right == NULL)
418 return (*action) (root);
421 if (root->left != NULL)
422 if (recurse_tree (root->left, action))
424 if ((*action) (root))
426 if (root->right != NULL)
427 if (recurse_tree (root->right, action))
434 /* Walk the tree specified by the head ROOT, calling ACTION for
438 walk_tree (struct item *root, int (*action) (struct item *))
441 recurse_tree (root->right, action);
444 /* Do a topological sort on FILE. */
447 tsort (const char *file)
450 struct item *j = NULL;
451 struct item *k = NULL;
453 token_buffer tokenbuffer;
455 /* Intialize the head of the tree will hold the strings we're sorting. */
456 root = new_item (NULL);
458 if (STREQ (file, "-"))
465 fp = fopen (file, "r");
467 error (EXIT_FAILURE, errno, "%s", file);
470 init_tokenbuffer (&tokenbuffer);
476 /* T2. Next Relation. */
477 len = readtoken (fp, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
483 k = search_item (root, tokenbuffer.buffer);
486 /* T3. Record the relation. */
487 record_relation (j, k);
494 /* T1. Initialize (N <- n). */
495 walk_tree (root, count_items);
497 while (n_strings > 0)
499 /* T4. Scan for zeros. */
500 walk_tree (root, scan_zeros);
504 struct successor *p = head->top;
506 /* T5. Output front of queue. */
507 printf ("%s\n", head->str);
508 head->str = NULL; /* Avoid printing the same string twice. */
511 /* T6. Erase relations. */
515 if (p->suc->count == 0)
517 zeros->qlink = p->suc;
524 /* T7. Remove from queue. */
528 /* T8. End of process. */
529 assert (n_strings >= 0);
532 /* The input contains a loop. */
533 error (0, 0, _("%s: input contains a loop:"),
534 (have_read_stdin ? "-" : file));
537 /* Print the loop and remove a relation to break it. */
539 walk_tree (root, detect_loop);
546 main (int argc, char **argv)
550 program_name = argv[0];
551 setlocale (LC_ALL, "");
552 bindtextdomain (PACKAGE, LOCALEDIR);
553 textdomain (PACKAGE);
555 atexit (close_stdout);
559 parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE, VERSION,
562 while ((opt = getopt_long (argc, argv, "", long_options, NULL)) != -1)
565 case 0: /* long option */
568 usage (EXIT_FAILURE);
573 if (optind + 1 < argc)
575 error (0, 0, _("only one argument may be specified"));
576 usage (EXIT_FAILURE);
580 tsort (argv[optind]);
584 if (have_read_stdin && fclose (stdin) == EOF)
585 error (EXIT_FAILURE, errno, _("standard input"));
587 exit (exit_status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);