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. */
32 #include "long-options.h"
38 /* Members of the list of successors. */
42 struct successor *next;
45 /* Each string is held in core as the head of a list of successors. */
49 struct item *left, *right;
53 struct successor *top;
56 /* The name this program was run with. */
59 /* Nonzero if any of the input files are the standard input. */
60 static int have_read_stdin;
62 /* The head of the sorted list. */
63 static struct item *head;
65 /* A scratch variable. */
66 static struct item *r = NULL;
68 /* The number of strings to sort. */
71 static struct option const long_options[] =
80 fprintf (stderr, _("Try `%s --help' for more information.\n"),
85 Usage: %s [OPTION] [FILE]\n\
86 Write totally ordered list consistent with the partial ordering in FILE.\n\
87 With no FILE, or when FILE is -, read standard input.\n\
89 --help display this help and exit\n\
90 --version output version information and exit\n"),
92 puts (_("\nReport bugs to <textutils-bugs@gnu.org>."));
95 exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
98 /* Create a new item/node for STR. */
100 new_item (const char *str)
102 struct item *k = xmalloc (sizeof (struct item));
104 k->str = (str ? xstrdup (str): NULL);
105 k->left = k->right = NULL;
108 /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^). */
116 /* Search binary tree rooted at *ROOT for STR. Allocate a new tree if
117 *ROOT is NULL. Insert a node/item for STR if not found. Return
118 the node/item found/created for STR.
120 This is done according to Algorithm A (Balanced tree search and
121 insertion) in Donald E. Knuth, The Art of Computer Programming,
122 Volume 3/Searching and Sorting, pages 455--457. */
125 search_item (struct item *root, const char *str)
127 struct item *p, *q, *r, *s, *t;
132 /* Make sure the tree is not empty, since that is what the algorithm
134 if (root->right == NULL)
135 return (root->right = new_item (str));
137 /* A1. Initialize. */
144 a = strcmp (str, p->str);
148 /* A3 & A4. Move left & right. */
159 /* A3 & A4. (continued). */
165 /* A6. Adjust balance factors. */
166 assert (strcmp (str, s->str));
167 if (strcmp (str, s->str) < 0)
180 assert (strcmp (str, p->str));
181 if (strcmp (str, p->str) < 0)
193 /* A7. Balancing act. */
194 if (s->balance == 0 || s->balance == -a)
202 /* A8. Single Rotation. */
214 s->balance = r->balance = 0;
218 /* A9. Double rotation. */
240 else if (p->balance == -a)
245 /* A10. Finishing touch. */
254 /* A3 & A4. (continued). */
267 /* Record the fact that J precedes K. */
270 record_relation (struct item *j, struct item *k)
274 if (strcmp (j->str, k->str))
277 p = xmalloc (sizeof (struct successor));
285 count_items (struct item *k)
291 scan_zeros (struct item *k)
304 /* If K is part of a loop, print the loop on standard error, and exit. */
307 detect_loop (struct item *k)
311 while (k && k->count > 0)
314 fprintf (stderr, "%s: %s\n", program_name, k->str);
322 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node. */
325 recurse_tree (struct item *root, void (*action) (struct item *))
327 if (root->left == NULL && root->right == NULL)
331 if (root->left != NULL)
332 recurse_tree (root->left, action);
334 if (root->right != NULL)
335 recurse_tree (root->right, action);
339 /* Walk the tree specified by the head ROOT, calling ACTION for
343 walk_tree (struct item *root, void (*action) (struct item *))
346 recurse_tree (root->right, action);
349 /* The following function was copied from getline.c, but with these changes:
350 - Read up to and not including any "whitespace" character.
351 - Remove unused argument, OFFSET.
352 - Use xmalloc and xrealloc instead of malloc and realloc.
353 - Declare this function static. */
355 /* Always add at least this many bytes when extending the buffer. */
358 /* Read up to (and not including) any "whitespace" character from STREAM
359 into *LINEPTR (and null-terminate it). *LINEPTR is a pointer returned
360 from xmalloc (or NULL), pointing to *N characters of space. It is
361 xrealloc'd as necessary. Return the number of characters read (not
362 including the null terminator), or -1 on error or EOF. */
365 getstr (char **lineptr, int *n, FILE *stream)
367 int nchars_avail; /* Allocated but unused chars in *LINEPTR. */
368 char *read_pos; /* Where we're reading into *LINEPTR. */
370 if (!lineptr || !n || !stream)
376 *lineptr = (char *) xmalloc (*n);
386 register int c = getc (stream);
388 /* We always want at least one char left in the buffer, since we
389 always (unless we get an error while reading the first char)
390 NUL-terminate the line buffer. */
392 assert (*n - nchars_avail == read_pos - *lineptr);
393 if (nchars_avail < 1)
400 nchars_avail = *n + *lineptr - read_pos;
401 *lineptr = xrealloc (*lineptr, *n);
404 read_pos = *n - nchars_avail + *lineptr;
405 assert (*n - nchars_avail == read_pos - *lineptr);
408 if (feof (stream) || ferror (stream))
410 /* Return partial line, if any. */
411 if (read_pos == *lineptr)
418 /* Return the string. */
425 /* Done - NUL terminate and return the number of chars read. */
428 return read_pos - *lineptr;
433 sort (const char *file)
436 struct item *j = NULL;
437 struct item *k = NULL;
443 /* Intialize the head of the tree will hold the strings we're sorting. */
444 root = new_item (NULL);
446 if (STREQ (file, "-"))
453 fp = fopen (file, "r");
455 error (EXIT_FAILURE, errno, "%s", file);
460 /* T2. Next Relation. */
461 len = getstr (&str, &size, fp);
467 k = search_item (root, str);
470 /* T3. Record the relation. */
471 record_relation (j, k);
478 /* T1. Initialize (N <- n). */
479 walk_tree (root, count_items);
481 /* T4. Scan for zeros. */
482 walk_tree (root, scan_zeros);
486 struct successor *p = head->top;
488 /* T5. Output front of queue. */
489 printf ("%s\n", head->str);
492 /* T6. Erase relations. */
496 if (p->suc->count == 0)
505 /* T7. Remove from queue. */
509 /* T8. End of process. */
514 fprintf (stderr, _("%s: input contains a loop:\n"), program_name);
516 fprintf (stderr, _("%s: %s: input contains a loop:\n"),
519 /* Print out loop. */
520 walk_tree (root, detect_loop);
522 /* Should not happen. */
523 error (EXIT_FAILURE, 0, _("%s: could not find loop"));
529 main (int argc, char **argv)
533 program_name = argv[0];
534 setlocale (LC_ALL, "");
535 bindtextdomain (PACKAGE, LOCALEDIR);
536 textdomain (PACKAGE);
538 parse_long_options (argc, argv, "tsort", GNU_PACKAGE, VERSION, usage);
540 while ((opt = getopt_long (argc, argv, "", long_options, NULL)) != -1)
543 case 0: /* long option */
546 usage (EXIT_FAILURE);
551 if (optind + 1 < argc)
553 error (0, 0, _("only one argument may be specified"));
554 usage (EXIT_FAILURE);
562 if (fclose (stdout) == EOF)
563 error (EXIT_FAILURE, errno, _("write error"));
565 if (have_read_stdin && fclose (stdin) == EOF)
566 error (EXIT_FAILURE, errno, _("standard input"));