#lang scribble/manual
@(require scribble/eval
          planet/scribble
          (for-label (this-package-in main)))


@title{tqueue: a queue-like data structure for topological sorting.}

@defmodule/this-package[main]

@scheme[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
@scheme[tqueue].  This is basically an implementation of Algorithm T from
Section 2.2.3 of The Art of Computer Programming @cite["TAOCP"].


@section{Example}

As a simple application, we can topologically sort a sequence of
elements by feeding a @scheme[tqueue] all the dependency information.
We can then alternate the following steps until we exhaust the
@scheme[tqueue]:

@itemize{
  @item{Pop off a ready element.}
  @item{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)
]


@section{API}


@defproc[(new-tqueue) tqueue?]{
Creates a new @scheme[tqueue].
}


@defproc[(tqueue? [datum any/c]) boolean?]{
Returns true if the datum is a @scheme[tqueue].
}


@defproc[(tqueue-add! [a-tqueue tqueue?] [elt any/c] [deps (listof any/c)]) any]{
Adds an elements and its list of dependencies to a @scheme[tqueue].

Elements and dependencies are allowed to be of any type.  Equality of
dependencies are compared by @scheme[eq?], not @scheme[equal?].
}


@defproc[(tqueue-satisfy! [a-tqueue tqueue?] [dep any/c]) any]{
Notifies the @scheme[tqueue] that a dependency has been satisfied.

Note: the effect of this applies prospectively to any elements
added in the future with @racket[tqueue-add!].  For example:
@interaction[
(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))
]
}


@defproc[(tqueue-get [a-tqueue tqueue?]) any/c]{
Returns the next element from a @scheme[tqueue].  Blocks if no element
is available.
}

@defproc[(tqueue-try-get [a-tqueue tqueue?]) (or/c any/c false/c)]{
Returns the next element from a @scheme[tqueue], or @scheme[#f] if no
element is available.
}

@defproc[(tqueue-ready-channel [a-tqueue tqueue?]) async-channel?]{
Provides low-level access to the @scheme[async-channel] that fills with
ready elements that have all their dependencies satisfied.
}


@section{Notes}

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

For example,
the following interaction:
@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 @racket[tqueue-satisfy!] here does not satisfy
the dependency of @racket["a"], since it depends on a different @racket["b"].


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



@bibliography{
  @bib-entry[#:key "TAOCP" 
             #:title "The Art of Computer Programming.  Volume 1: Fundamental Algorithms" 
             #:author "D. E. Knuth"
             #:location "Reading, Massachusetts: Addison-Wesley"
             #:date "1997"]{}
}