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

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:

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

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.

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