Gerbil Scheme

Priority Queues

To use the bindings from this module:

(import :std/misc/pqueue)

make-pqueue

(make-pqueue prio [cmp = <] [capacity = 15]) -> pqueue

  prio     := function returning priority of elements
  cmp      := optional heap comparison function, min-heap by default
  capacity := optional initial size

Creates a new empty priority queue, a data structure similar to a simple queue, but extended to take the associated priority value of an element into account when pushing, popping and peeking elements.

  • prio is a function returning the real priority of an element. It is utilized to determine the insert position whenever some element is about to be pushed onto the priority queue.
  • cmp, a comparison function, is used to order the elements based on their priority, defaulting to <.
  • capacity is the number of elements the pqueue can hold before it needs to resize itself.

Examples:

For example, let's assume we always want to retrieve the longest string currently within our queue. This could be achieved with string-length as our priority function and ordering these lengths via >:

> (def pq (make-pqueue string-length >))
> (pqueue-push! pq "shortest")
> (pqueue-push! pq "very, very, long")
> (pqueue-push! pq "medium length")
> (pqueue-peek pq)
"very, very, long"
> (pqueue-pop! pq)
"very, very, long"
> (pqueue-peek pq)
"medium length"

pqueue?

(pqueue? pq) -> boolean

  pq := priority queue to check

Returns #t if pq is a priority queue, #f otherwise.

Examples:

> (let (pq (make-pqueue identity))
    (when (pqueue? pq)
      (pqueue-push! pq 1000)
      (pqueue-push! pq 100)
      (pqueue-push! pq 10)
      (pqueue-peek pq)))
10

> (import :std/misc/queue)
> (pqueue? (make-queue))
#f

pqueue-size

(pqueue-size pq) -> fixnum

  pq := priority queue to inspect

Returns the number of elements queued in pq.

This operation is O(1), since priority queues always keep track of their size.

Examples:

> (let (pq (make-pqueue char->integer))
    (string-for-each (cut pqueue-push! pq <>) "ABCDEF")
    (pqueue-size pq))
6

pqueue-empty?

(pqueue-empty? pq) -> boolean

  pq := priority queue to check

Returns #t if pq has no elements queued, #f otherwise.

Examples:

> (pqueue-empty? (make-pqueue identity < 1000))
#t

> (make-pqueue identity)
#<pqueue #21>
> (pqueue-push! #21 1)
> (pqueue-push! #21 3)
> (pqueue-push! #21 5)
> (pqueue-empty? #21)
#f

pqueue-push!

(pqueue-push! pq elem) -> unspecified

  pq   := priority queue to push onto
  elem := element to push to pq

Enqueues elem in pq. The insert position depends on the priority and comparison functions specified in make-pqueue. Similar to set!, it's unspecified what pqueue-push! returns afterwards.

Examples:

> (defstruct city (name population))
> (def cities [(make-city "Salto" 104028)
               (make-city "Санкт-Петербург" 4879566)
               (make-city "Qaqortoq" 3089)
               (make-city "አዲስ ፡ አበባ" 3352000)
               (make-city "Jayapura" 315872)
               (make-city "香港" 7448900)])
> (let (pq (make-pqueue city-population))
    (for-each (cut pqueue-push! pq <>) cities)
    (city-name (pqueue-peek pq)))
"Qaqortoq"

pqueue-pop!

(pqueue-pop! pq [default = absent-obj]) -> any | default | error

  pq      := priority queue to pop from
  default := optional element returned when pq is empty

Pops the next value in pq and returns it. Which element gets popped depends on the priority and comparison function specified in make-pqueue. If pq is empty and a default value is supplied, then default is returned. Otherwise an error is raised.

Examples:

> (import :std/sugar)
> (let (pq (make-pqueue values))
    (for-each (cut pqueue-push! pq <>) [10 1 20 2 30 3])
    (until (pqueue-empty? pq)
      (displayln (pqueue-pop! pq)))
    ;; would signal error without default value:
    (pqueue-pop! pq 100))
1
2
3
10
20
30
100

pqueue-peek

(pqueue-peek pq) -> any | error

  pq := priority queue to peek

Returns the next value in pq without popping it from the priority queue like pqueue-pop! does. An error is raised when pq is empty.

Examples:

> (import :std/srfi/1)
> (def pq (make-pqueue length))
> (pqueue-push! pq (iota (random-integer 10)))
> (pqueue-peek pq)
(0 1 2 3 4 5 6 7)
> (pqueue-push! pq [13 21 34 55])
> (pqueue-peek pq)
(13 21 34 55)

pqueue-contents

(pqueue-contents pq) -> list

  pq := priority queue of which to extract the contents

Returns the contents of the priority queue as a list, without modifying the priority queue.

Examples:

> (def pq (make-pqueue identity))
> (for-each (cut pqueue-push! pq <>) [8 2 3 4 1 9 7])
> (pqueue-contents pq)
(1 2 3 8 4 9 7)

pqueue

(defsyntax pqueue)

Priority queue type for user-defined generics and destructuring.

Examples:

> (let (pq (make-pqueue string-length >))
    (pqueue-push! pq "Mimas")
    (pqueue-push! pq "Enceladus")
    (pqueue-push! pq "Tethys")
    (with ((pqueue internal-heap) pq)
      (with ((vector size . vals) internal-heap)
        (displayln "size: " size "\nvals: " vals))))
size: 3
vals: ((9 . Enceladus) (5 . Mimas) (6 . Tethys) 0 0 0 0 0 0 0 0 0 0 0 0)

← Prime Number Functions→