1 Example
3 Notes
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].

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:


> (require (planet dyoo/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)])
           (tqueue-satisfy! a-tqueue next-elt)
           (cons next-elt (loop))]
> (toposort a-tqueue)

'(underwear socks shirt pants shoes belt)


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


(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

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


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.


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