tqueue: a queue-like data structure for topological 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.