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\
104 --help display this help and exit\n\
105 --version output version information and exit\n\
107 puts (_("\nReport bugs to <bug-textutils@gnu.org>."));
110 exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
113 /* Create a new item/node for STR. */
115 new_item (const char *str)
117 struct item *k = xmalloc (sizeof (struct item));
119 k->str = (str ? xstrdup (str): NULL);
120 k->left = k->right = NULL;
123 /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^). */
131 /* Search binary tree rooted at *ROOT for STR. Allocate a new tree if
132 *ROOT is NULL. Insert a node/item for STR if not found. Return
133 the node/item found/created for STR.
135 This is done according to Algorithm A (Balanced tree search and
136 insertion) in Donald E. Knuth, The Art of Computer Programming,
137 Volume 3/Searching and Sorting, pages 455--457. */
140 search_item (struct item *root, const char *str)
142 struct item *p, *q, *r, *s, *t;
147 /* Make sure the tree is not empty, since that is what the algorithm
149 if (root->right == NULL)
150 return (root->right = new_item (str));
152 /* A1. Initialize. */
159 a = strcmp (str, p->str);
163 /* A3 & A4. Move left & right. */
174 /* A3 & A4. (continued). */
180 /* A6. Adjust balance factors. */
181 assert (!STREQ (str, s->str));
182 if (strcmp (str, s->str) < 0)
195 assert (!STREQ (str, p->str));
196 if (strcmp (str, p->str) < 0)
208 /* A7. Balancing act. */
209 if (s->balance == 0 || s->balance == -a)
217 /* A8. Single Rotation. */
229 s->balance = r->balance = 0;
233 /* A9. Double rotation. */
255 else if (p->balance == -a)
260 /* A10. Finishing touch. */
269 /* A3 & A4. (continued). */
282 /* Record the fact that J precedes K. */
285 record_relation (struct item *j, struct item *k)
289 if (!STREQ (j->str, k->str))
292 p = xmalloc (sizeof (struct successor));
300 count_items (struct item *unused ATTRIBUTE_UNUSED)
307 scan_zeros (struct item *k)
309 /* Ignore strings that have already been printed. */
310 if (k->count == 0 && k->str)
323 /* Try to detect the loop. If we have detected that K is part of a
324 loop, print the loop on standard error, remove a relation to break
325 the loop, and return non-zero.
327 The loop detection strategy is as follows: Realise that what we're
328 dealing with is essentially a directed graph. If we find an item
329 that is part of a graph that contains a cycle we traverse the graph
330 in backwards direction. In general there is no unique way to do
331 this, but that is no problem. If we encounter an item that we have
332 encountered before, we know that we've found a cycle. All we have
333 to do now is retrace our steps, printing out the items until we
334 encounter that item again. (This is not necessarily the item that
335 we started from originally.) Since the order in which the items
336 are stored in the tree is not related to the specified partial
337 ordering, we may need to walk the tree several times before the
338 loop has completely been constructed. If the loop was found, the
339 global variable LOOP will be NULL. */
342 detect_loop (struct item *k)
346 /* K does not have to be part of a cycle. It is however part of
347 a graph that contains a cycle. */
350 /* Start traversing the graph at K. */
354 struct successor **p = &k->top;
358 if ((*p)->suc == loop)
362 /* We have found a loop. Retrace our steps. */
365 struct item *tmp = loop->qlink;
367 fprintf (stderr, "%s: %s\n", program_name,
370 /* Until we encounter K again. */
373 /* Remove relation. */
379 /* Tidy things up since we might have to
380 detect another loop. */
387 struct item *tmp = loop->qlink;
393 /* Since we have found the loop, stop walking
413 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.
414 Stop when ACTION returns non-zero. */
417 recurse_tree (struct item *root, int (*action) (struct item *))
419 if (root->left == NULL && root->right == NULL)
420 return (*action) (root);
423 if (root->left != NULL)
424 if (recurse_tree (root->left, action))
426 if ((*action) (root))
428 if (root->right != NULL)
429 if (recurse_tree (root->right, action))
436 /* Walk the tree specified by the head ROOT, calling ACTION for
440 walk_tree (struct item *root, int (*action) (struct item *))
443 recurse_tree (root->right, action);
446 /* Do a topological sort on FILE. */
449 tsort (const char *file)
452 struct item *j = NULL;
453 struct item *k = NULL;
455 token_buffer tokenbuffer;
457 /* Intialize the head of the tree will hold the strings we're sorting. */
458 root = new_item (NULL);
460 if (STREQ (file, "-"))
467 fp = fopen (file, "r");
469 error (EXIT_FAILURE, errno, "%s", file);
472 init_tokenbuffer (&tokenbuffer);
478 /* T2. Next Relation. */
479 len = readtoken (fp, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
485 k = search_item (root, tokenbuffer.buffer);
488 /* T3. Record the relation. */
489 record_relation (j, k);
496 /* T1. Initialize (N <- n). */
497 walk_tree (root, count_items);
499 while (n_strings > 0)
501 /* T4. Scan for zeros. */
502 walk_tree (root, scan_zeros);
506 struct successor *p = head->top;
508 /* T5. Output front of queue. */
509 printf ("%s\n", head->str);
510 head->str = NULL; /* Avoid printing the same string twice. */
513 /* T6. Erase relations. */
517 if (p->suc->count == 0)
519 zeros->qlink = p->suc;
526 /* T7. Remove from queue. */
530 /* T8. End of process. */
531 assert (n_strings >= 0);
534 /* The input contains a loop. */
535 error (0, 0, _("%s: input contains a loop:"),
536 (have_read_stdin ? "-" : file));
539 /* Print the loop and remove a relation to break it. */
541 walk_tree (root, detect_loop);
548 main (int argc, char **argv)
552 program_name = argv[0];
553 setlocale (LC_ALL, "");
554 bindtextdomain (PACKAGE, LOCALEDIR);
555 textdomain (PACKAGE);
557 atexit (close_stdout);
561 parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE, VERSION,
564 while ((opt = getopt_long (argc, argv, "", long_options, NULL)) != -1)
567 case 0: /* long option */
570 usage (EXIT_FAILURE);
575 if (optind + 1 < argc)
577 error (0, 0, _("only one argument may be specified"));
578 usage (EXIT_FAILURE);
582 tsort (argv[optind]);
586 if (have_read_stdin && fclose (stdin) == EOF)
587 error (EXIT_FAILURE, errno, _("standard input"));
589 exit (exit_status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);