Version: 5.2.1

## tqueue: a queue-like data structure for topological sorting.

 (require (planet dyoo/tqueue:2:=0))

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].

### 1Example

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))
> (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)

### 2API

 (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.

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

 (tqueue-satisfy! a-tqueue dep) → any a-tqueue : tqueue? dep : any/c
Notifies the tqueue that a dependency has been satisfied.

Note: the effect of this applies prospectively to any elements added in the future with tqueue-add!. For example:
> (require (planet dyoo/tqueue))
 > (let ([a-queue (new-tqueue)]) (tqueue-satisfy! a-queue 'milk) (tqueue-satisfy! a-queue 'cookies) (tqueue-add! a-queue 'mouse '(cookies milk)) (tqueue-try-get a-queue))

'mouse

 (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.

### 3Notes

Be careful that the dependencies fed with tqueue-add! and satisfied with tqueue-satisfy! are eq?.

For example, the following interaction:
> (require (planet dyoo/tqueue))
 > (let ([tqueue (new-tqueue)]) (tqueue-add! tqueue "a" (list "b")) (tqueue-satisfy! tqueue (string-copy "b")) (tqueue-try-get tqueue))

#f

shows that the use of tqueue-satisfy! here does not satisfy the dependency of "a", since it depends on a different "b".

Also, a tqueue will remember all dependencies that are passed by tqueue-satisfy!, so be careful if the tqueue is long-lived, as it will continue to hold references in memory.

### Bibliography

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