;;; protocol for priority queues (defgeneric priority-queue-empty-p (priority-queue)) (defgeneric priority-queue-insert (priority-queue element prio)) (defgeneric priority-queue-dequeue-max (priority-queue)) ;;; protocol class for priority queues (defclass priority-queue () ()) (defclass fixed-max-priority-queue (priority-queue) ((contents :initarg :contents))) (defun make-fixed-max-priority-queue (max-priority) (make-instance 'fixed-max-priority-queue :contents (make-array (list max-priority) :initial-element '()))) (defmethod priority-queue-empty-p ((p fixed-max-priority-queue)) (every #'null (slot-value p 'contents))) (defmethod priority-queue-insert ((p fixed-max-priority-queue) elem prio) (push elem (aref (slot-value p 'contents) prio))) (defmethod priority-queue-dequeue-max ((p fixed-max-priority-queue)) (let* ((array (slot-value p 'contents)) (pos (position-if-not #'null array :from-end t))) (assert pos) (pop (aref array pos))))