(load-option 'wt-tree)


;;; Q OPERATIONS using weight balanced treed

(define Q? wt-tree?)
  
(define (make-Q path)		; constructor with a single path
  (singleton-wt-tree number-wt-type
		     (path-value path) (list path)))

(define Q-empty? wt-tree/empty?)

(define (Q-add-paths new-paths Q)
  (for-each (lambda (p)
	      (let ((entry (wt-tree/lookup Q (path-value p) #f)))
		(cond (entry
		       (set-cdr! entry (cons (car entry) (cdr entry)))
		       (set-car! entry p)
		       )
		      (else
		       (wt-tree/add! Q (path-value p) (list p)))))
	      )
	    new-paths)
  Q)

;;; Used for heuristic searches, pick the path with the best heuristic value
;;; modifies Q to remove the best path.

(define (Q-pick-and-remove-best-path Q)
  (let* ((best (wt-tree/min-datum Q))
	 (best-path (car best)))
    (cond ((null? (cdr best))
	   (wt-tree/delete-min! Q))
	  (else
	   (set-car! best (car (cdr best)))
	   (set-cdr! best (cddr best))
	   ))
    best-path))

(define (Q-length Q)
  (let ((size 0))
    (wt-tree/for-each (lambda (key value) (set! size (+ (length value) size))) Q)
    size))

(define (Q-print Q)
  (display* "Q=")
  (wt-tree/for-each
   (lambda (key value) (pretty-print (cons key value)) (newline))
   Q))