doc.txt
```tqueue: a queue-like data structure for topologicial sorting.

(require (planet dyoo/tqueue:1/tqueue))

tqueue provides a data structure for maintaining elements
with dependencies.  It keeps track of known satisfied dependencies;
any elements whose dependencies are all satisifed can pop off a
tqueue.  This is basically an implementation of Algorithm T from
Section 2.2.3 of The Art of Computer Programming [TAOCP].

1. Example

As a simple application, we can topologically sort a sequence of
elements by feeding a tqueue all the dependency information.
We can then alternate the following steps until we exhaust the
tqueue:

* Pop off a ready element.

* Tell the queue that we’ve satisfied the element.

Examples:
> (require (planet dyoo/tqueue:1/tqueue))
> (define a-tqueue (new-tqueue))
> (tqueue-add! a-tqueue 'pants '(socks underwear))
> (tqueue-add! a-tqueue 'shoes '(socks pants))
> (define (toposort a-tqueue)
(let loop ()
(let ([next-elt (tqueue-try-get a-tqueue)])
(cond
[next-elt
(tqueue-satisfy! a-tqueue next-elt)
(cons next-elt (loop))]
[else
'()]))))
> (toposort a-tqueue)
(underwear socks shirt pants shoes belt)

2. API

(new-tqueue) -> tqueue?

Creates a new tqueue.

(tqueue? datum) -> boolean?
datum : any/c

Returns true if the datum is a tqueue.

(tqueue-add! a-tqueue elt deps) -> any
a-tqueue : tqueue?
elt : any/c
deps : (listof any/c)

Adds an elements and its list of dependencies to a tqueue.

(tqueue-satisfy! a-tqueue dep) -> any
a-tqueue : tqueue?
dep : any/c

Notifies the tqueue that a dependency has been satisfied.

(tqueue-get a-tqueue) -> any/c
a-tqueue : tqueue?

Returns the next element from a tqueue.  Blocks if no element
is available.

(tqueue-try-get a-tqueue) -> (or/c any/c false/c)
a-tqueue : tqueue?

Returns the next element from a tqueue, or #f if no
element is available.

a-tqueue : tqueue?

ready elements that have all their dependencies satisfied.

3. Notes

A tqueue will remember all dependencies that are passed by
tqueue-satisfy!, so be careful if the tqueue is
long-lived.

Elements and dependencies are allowed to be of any type.  Equality of
dependencies are compared by eq?, not equal?.

Bibliography

[TAOCP] D. E. Knuth, “The Art of Computer Programming.  Volume 1: Fundamental Algorithms,” Reading, Massachusetts: Addison-Wesley, 1997.```