summaryrefslogtreecommitdiff
path: root/usr.bin/tsort
AgeCommit message (Collapse)Author
2001-05-01Revert stupid buggy optimisation.Marc Espie
Another Murphy's law: complicated code always works right the first time. Stupid dumb details, on the other hand. Of course we can't share both arrays, as we don't know how they will grow, duh !
2001-04-30Better hints handling (used for sorting package lists):Marc Espie
- nodes without a hint should be fully transparent. The make_transparent procedure is potentially slow, but in reality, it's very fast. - don't automatically add an order to un-hinted nodes, so that they are truely transparent. Better memory allocation: split the hash of nodes into a single array instead of duplicating the memory requirements. Okay Todd.
2001-04-18Fix `hinted' options: set initial order to maximal, so that any hintMarc Espie
will be first. Also, keep order around between hints file and reading normal pairt, so that this option actually is useful.
2001-04-07Small changes, user-friendly:Marc Espie
- just warn if hints file holds duplicates. So what ? We sure can't use uniq to remove those. - on the other hand, warn in verbose mode if main file holds nodes that are not in hints file. Ok millert@
2001-03-26Replacement for original tsort.Marc Espie
The old code suffers from a few defects: - it does not even implement the standard optimal topological sort algorithm. It's much slower. - its longest cycle computation is completely bogus. This is clean-slate code, that does implement the actual standard optimal topological sort, together with a correct graph traversal to find longest cycles. It does also feature a `stable tsort' mode, where it uses a heap to yield the least disturbed permutation of input nodes that satisfies the ordering constraints (in particular, try tsort -f). Thanks to the nature of the problem, the actual output won't exactly match the old one, but it does pass the regression suite (and it is a topological sorter). Ok millert@
2000-03-11Various cleanups and standardizations.Aaron Campbell
2000-03-04In Unix land we prefer "whitespace" to "white space" or "white-space". AtAaron Campbell
least, this is the impression I get from looking at a lot of Perl docs.
1998-10-30usr.bin/ man page fixes, t-zAaron Campbell
1997-09-21$OpenBSD$Theo de Raadt
1997-01-15getopt(3) returns -1 when out of args, not EOF, whee!Todd C. Miller
1996-06-26rcsidTheo de Raadt
1996-01-29add -q option for silence; from mouse@collatz.mcrcim.mcgill.edu;Theo de Raadt
netbsd pr#1204
1995-10-18initial import of NetBSD treeTheo de Raadt