Priority queue: Difference between revisions

=={{header|XLISP}}==

It does not seem necessary that <i>every</i> queue should support arbitrarily many distinct priority levels, so long as <i>each particular</i> queue supports as many levels as the user anticipates needing. We therefore store a priority queue as a fixed-length vector of queues and allow the user to pass the least urgent level needed (counting from 0 as the most urgent) as a parameter when a new priority queue is instantiated.

A vector can be efficiently indexed into, and we can eliminate a lot of searching by providing for each priority queue to know its most urgent priority level at any given time. The <code>'POP</code> method can then return the first item stored at that level, without needing to search. If this operation leaves that level empty, however, it does need to search for the next non-empty level. The worst case would be popping from a queue that contained only one item, at the most urgent priority level: the program would have to search down all the levels looking for one that wasn't empty. In the nature of a priority queue, however, this case is probably unusual.

The <code>'PUSH</code> method never needs to search down the levels. The efficiency bottleneck here is probably the implementation of <code>NCONC</code> (used for adding the new item to the end of the queue at the relevant level). A priority <i>stack</i>, with first in / last out at each priority level rather than first in / first out, would be faster.

<lang lisp>(define-class priority-queue

(instance-variables queue lowest-priority most-urgent) )

(define-method (priority-queue 'initialize limit)

(defun setup (x)

(vector-set! queue x nil)

(if (< x limit)

(setup (+ x 1)) ) )

(setq lowest-priority limit)

(setq most-urgent limit)

(setq queue (make-vector (+ limit 1)))

(setup 0)

self )

(define-method (priority-queue 'push item priority)

(if (and (integerp priority) (>= priority 0) (<= priority lowest-priority))

(progn

(setq most-urgent (min priority most-urgent))

(vector-set! queue priority (nconc (vector-ref queue priority) (cons item nil))) ) ) )

(define-method (priority-queue 'pop)

(defun find-next (q)

(if (or (= q lowest-priority) (not (null (vector-ref queue q))))

q

(find-next (+ q 1)) ) )

(define item (car (vector-ref queue most-urgent)))

(vector-set! queue most-urgent (cdr (vector-ref queue most-urgent)))

(setq most-urgent (find-next most-urgent))

item )

(define-method (priority-queue 'peek)

(car (vector-ref queue most-urgent)) )

(define-method (priority-queue 'emptyp)

(and (= most-urgent lowest-priority) (null (vector-ref queue most-urgent))) )</lang>

The example uses strings, but the data items stored in the priority queue can be of any type (including the empty list—or even other priority queues).

<lang lisp>(define pq (priority-queue 'new 5))

(pq 'push "Clear drains" 3)

(pq 'push "Feed cat" 4)

(pq 'push "Make tea" 5)

(pq 'push "Solve RC tasks" 1)

(pq 'push "Tax return" 2)</lang>

{{out}}

Items are popped beginning from the most urgent:

<lang lisp>[1] (pq 'pop)

"Solve RC tasks"

[2] (pq 'pop)

"Tax return"</lang>

Within each priority level, new items are pushed onto the end and popped from the beginning of the list (a queue is a first in / first out data structure):

<lang lisp>[3] (pq 'push "Answer emails" 4)

("Feed cat" "Answer emails")</lang>

Attempting to push with an invalid priority value returns the empty list, i.e. false:

<lang lisp>[4] (pq 'push "Weed garden" 17)

()</lang>

<code>'EMPTYP</code> returns false if the priority queue is not empty:

<lang lisp>[5] (pq 'emptyp)

()</lang>

<code>'PEEK</code> non-destructively returns the item that would be popped if you called <code>'POP</code>:

<lang lisp>[6] (pq 'peek)

"Clear drains"</lang>

If you want to examine a whole priority queue, the built-in <code>'SHOW</code> method allows you to do so:

<lang scheme>[7] (pq 'show)

Object is #<Object:PRIORITY-QUEUE #x4e2cba8>, Class is #<Class:PRIORITY-QUEUE #x4e254c8>

Instance variables:

QUEUE = #(() () () ("Clear drains") ("Feed cat" "Answer emails") ("Make tea"))

LOWEST-PRIORITY = 5

MOST-URGENT = 3

#<Object:PRIORITY-QUEUE #x4e2cba8></lang>

Once all the items have been popped, the priority queue is empty and <code>'EMPTYP</code> then returns true:

<lang lisp>[8] (pq 'pop)

"Clear drains"

[9] (pq 'pop)

"Feed cat"

[10] (pq 'pop)

"Answer emails"

[11] (pq 'pop)

"Make tea"

[12] (pq 'emptyp)

#T</lang>

Attempting to pop from an empty priority queue returns false:

<lang lisp>[13] (pq 'pop)

()</lang>