# singleton priority queue

Write a singleton priority queue, a priority queue that suppresses duplicate elements.

``` \$ cat spq.rkt
#lang racket

(provide
spq-dq!
spq-empty?
spq-new
spq-nq!
)

(require "priority-queue.rkt")

#| An obvious implementation of a singleton priority queue, except
filtering is done on egress rather than ingress.  Egress filtering
uses no extra space (the queue is the filter), but dequeuing is now
O(n log n) (the size operation is also a mess).
|#

(define (spq-dq! spq)

; Remove and return the head of the given singleton priority
; queue, or die if there's no such element.

(let ((pq (cdr spq)))
(if (pq-empty? pq)
(raise-arguments-error 'spq-dq!
"Dequeuing from an empty singleton priority queue")
(let ((e (pq-dq! pq)))
(do () ((or (pq-empty? pq) (not (= (pq-top pq) e))) e)
(pq-dq! pq))))))

(define (spq-empty? spq)

; Return #t iff the given priority queue contains no elements.

(pq-empty? (cdr spq)))

; Return the head of the given priority queue; die
; if there's no such element.

(let ((pq (cdr spq)))
(if (pq-empty? pq)
"Returning the head of an empty singleton priority queue")
(pq-top pq))))

(define (spq-new p l)

; Return a new priority queue containing the given elements in the
; order determined by the given predicate.

(cons 'spq (pq-new p l)))

(define (spq-nq! spq e)

; Add the given element to the given singleton priority queue.

(pq-nq! (cdr spq) e))

(require rackunit "utl.rkt")

(let ((spq (spq-new < '(1 1 1 1 1))))
(check-eq? (spq-empty? spq) #f)
(check-eq? (spq-dq! spq) 1)
(check-eq? (spq-empty? spq) #t))

(let*

((n 10)
(l (permuted-iota n))
(spq (spq-new < (append l (permute-list l)))))

(do ((i 0 (+ i 1))) ((>= i n) (check-eq? (spq-empty? spq) #t))
(check-eq? (spq-dq! spq) i)))

\$ racket spq.rkt

\$
```