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 'belt '(pants))
  > (tqueue-add! a-tqueue 'pants '(socks underwear))
  > (tqueue-add! a-tqueue 'shoes '(socks pants))
  > (tqueue-add! a-tqueue 'shirt '(underwear))
  > (tqueue-add! a-tqueue 'underwear '())
  > (tqueue-add! a-tqueue 'socks '())
  > (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.

(tqueue-ready-channel a-tqueue) -> async-channel?
  a-tqueue : tqueue?

Provides low-level access to the async-channel that fills with
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.