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 /* The official name of this program (e.g., no `g' prefix). */
38 #define PROGRAM_NAME "tsort"
40 /* 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 head of the sorted list. */
70 static struct item *head = NULL;
72 /* The tail of the list of `zeros', strings that have no predecessors. */
73 static struct item *zeros = NULL;
75 /* The number of strings to sort. */
76 static int n_strings = 0;
78 static struct option const long_options[] =
87 fprintf (stderr, _("Try `%s --help' for more information.\n"),
92 Usage: %s [OPTION] [FILE]\n\
93 Write totally ordered list consistent with the partial ordering in FILE.\n\
94 With no FILE, or when FILE is -, read standard input.\n\
96 --help display this help and exit\n\
97 --version output version information and exit\n"),
99 puts (_("\nReport bugs to <textutils-bugs@gnu.org>."));
102 exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
105 /* Create a new item/node for STR. */
107 new_item (const char *str)
109 struct item *k = xmalloc (sizeof (struct item));
111 k->str = (str ? xstrdup (str): NULL);
112 k->left = k->right = NULL;
115 /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^). */
123 /* Search binary tree rooted at *ROOT for STR. Allocate a new tree if
124 *ROOT is NULL. Insert a node/item for STR if not found. Return
125 the node/item found/created for STR.
127 This is done according to Algorithm A (Balanced tree search and
128 insertion) in Donald E. Knuth, The Art of Computer Programming,
129 Volume 3/Searching and Sorting, pages 455--457. */
132 search_item (struct item *root, const char *str)
134 struct item *p, *q, *r, *s, *t;
139 /* Make sure the tree is not empty, since that is what the algorithm
141 if (root->right == NULL)
142 return (root->right = new_item (str));
144 /* A1. Initialize. */
151 a = strcmp (str, p->str);
155 /* A3 & A4. Move left & right. */
166 /* A3 & A4. (continued). */
172 /* A6. Adjust balance factors. */
173 assert (!STREQ (str, s->str));
174 if (strcmp (str, s->str) < 0)
187 assert (!STREQ (str, p->str));
188 if (strcmp (str, p->str) < 0)
200 /* A7. Balancing act. */
201 if (s->balance == 0 || s->balance == -a)
209 /* A8. Single Rotation. */
221 s->balance = r->balance = 0;
225 /* A9. Double rotation. */
247 else if (p->balance == -a)
252 /* A10. Finishing touch. */
261 /* A3 & A4. (continued). */
274 /* Record the fact that J precedes K. */
277 record_relation (struct item *j, struct item *k)
281 if (!STREQ (j->str, k->str))
284 p = xmalloc (sizeof (struct successor));
292 count_items (struct item *k)
298 scan_zeros (struct item *k)
311 /* If K is part of a loop, print the loop on standard error, and exit. */
314 detect_loop (struct item *k)
318 while (k && k->count > 0)
321 fprintf (stderr, "%s: %s\n", program_name, k->str);
329 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node. */
332 recurse_tree (struct item *root, void (*action) (struct item *))
334 if (root->left == NULL && root->right == NULL)
338 if (root->left != NULL)
339 recurse_tree (root->left, action);
341 if (root->right != NULL)
342 recurse_tree (root->right, action);
346 /* Walk the tree specified by the head ROOT, calling ACTION for
350 walk_tree (struct item *root, void (*action) (struct item *))
353 recurse_tree (root->right, action);
356 /* Do a topological sort on FILE. */
359 tsort (const char *file)
362 struct item *j = NULL;
363 struct item *k = NULL;
365 token_buffer tokenbuffer;
367 /* Intialize the head of the tree will hold the strings we're sorting. */
368 root = new_item (NULL);
370 if (STREQ (file, "-"))
377 fp = fopen (file, "r");
379 error (EXIT_FAILURE, errno, "%s", file);
382 init_tokenbuffer (&tokenbuffer);
388 /* T2. Next Relation. */
389 len = readtoken (fp, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
395 k = search_item (root, tokenbuffer.buffer);
398 /* T3. Record the relation. */
399 record_relation (j, k);
406 /* T1. Initialize (N <- n). */
407 walk_tree (root, count_items);
409 /* T4. Scan for zeros. */
410 walk_tree (root, scan_zeros);
414 struct successor *p = head->top;
416 /* T5. Output front of queue. */
417 printf ("%s\n", head->str);
420 /* T6. Erase relations. */
424 if (p->suc->count == 0)
426 zeros->qlink = p->suc;
433 /* T7. Remove from queue. */
437 /* T8. End of process. */
438 assert (n_strings >= 0);
441 error (0, 0, _("%s: input contains a loop:\n"),
442 (have_read_stdin ? "-" : file));
444 /* Print out loop. */
445 walk_tree (root, detect_loop);
447 /* Should not happen. */
448 error (EXIT_FAILURE, 0, _("could not find loop"));
453 main (int argc, char **argv)
457 program_name = argv[0];
458 setlocale (LC_ALL, "");
459 bindtextdomain (PACKAGE, LOCALEDIR);
460 textdomain (PACKAGE);
462 parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
463 "Mark Kettenis", usage);
465 while ((opt = getopt_long (argc, argv, "", long_options, NULL)) != -1)
468 case 0: /* long option */
471 usage (EXIT_FAILURE);
476 if (optind + 1 < argc)
478 error (0, 0, _("only one argument may be specified"));
479 usage (EXIT_FAILURE);
483 tsort (argv[optind]);
487 if (fclose (stdout) == EOF)
488 error (EXIT_FAILURE, errno, _("write error"));
490 if (have_read_stdin && fclose (stdin) == EOF)
491 error (EXIT_FAILURE, errno, _("standard input"));