; wirth problem 15.12

(define pq-empty '())
(define pq-empty? null?)

(define (pq-first pq)
  (if (null? pq)
      (error 'pq-first "can't extract minimum from null queue")
      (car pq)))

(define (pq-merge lt? p1 p2)
  (cond ((null? p1) p2)
        ((null? p2) p1)
        ((lt? (car p2) (car p1))
          (cons (car p2) (cons p1 (cdr p2))))
        (else (cons (car p1) (cons p2 (cdr p1))))))

(define (pq-insert lt? x pq)
  (pq-merge lt? (list x) pq))

(define (pq-merge-pairs lt? ps)
  (cond ((null? ps) '())
        ((null? (cdr ps)) (car ps))
        (else (pq-merge lt? (pq-merge lt? (car ps) (cadr ps))
                            (pq-merge-pairs lt? (cddr ps))))))

(define (pq-rest lt? pq)
  (if (null? pq)
      (error 'pq-rest "can't delete minimum from null queue")
      (pq-merge-pairs lt? (cdr pq))))

(define (wirth n)
  (let ((pq (pq-insert < 1 pq-empty)))
    (let loop ((n n) (pq pq) (ps (list)))
      (if (zero? n) (reverse ps)
        (let* ((p (pq-first pq))
               (pq (pq-rest < pq))
               (pq (if (and (not (pq-empty? pq))
                            (= (pq-first pq) p))
                       (pq-rest < pq) pq)))
          (loop (- n 1)
                (pq-insert < (+ (* 2 p) 1)
                  (pq-insert < (+ (* 3 p) 1) pq))
                (cons p ps)))))))

(display (wirth 100))

(1 3 4 7 9 10 13 15 19 21 22 27 28 31 39 40 43 45 46 55 57 58 63 64 67 79 81 82 85 87 91 93 94 111 115 117 118 121 127 129 130 135 136 139 159 163 165 166 171 172 175 183 187 189 190 193 202 223 231 235 237 238 243 244 247 255 256 259 261 262 271 273 274 279 280 283 319 327 331 333 334 343 345 346 351 352 355 364 367 375 379 381 382 387 388 391 405 406 409 418)