Common Lisp Package: PETTOMATO-INDEXED-PRIORITY-QUEUE

README:

FUNCTION

Public

MAKE-EMPTY-QUEUE (COMPARE-FN SET-INDEX-FN GET-INDEX-FN &KEY (SIZE 100))

Return a new empty queue. compare-fn is a function that takes two arguments and returns a true value iff the first argument should be prioritized higher in the queue. If the two items have equal priority, then compare-fn should return nil. set-index-fn and get-index-fn are a pair. Some queue operations (e.g., queue-delete) require that the index for an item can be retrieved. These functions allow the user to control how that mapping is maintained. set-index-fn is a function that takes two arguments: the first is an item in the queue and the second is the current index position of that item in the heap. This function should do something to record the association between the item and the index. Each item's index may change many times while it is stored in the queue; this function will be called each time. get-index-fn is a function that takes an item and returns the heap index that was associated with it via set-index-fn. get-index-fn must return -1 if the item is not in the queue. The priority queue will call set-index-fn with -1 when an item is being removed from the queue, but that obviously only works for items it has seen before. If there is a chance client code will try to call one of the operations that relies on get-index-fn with items that have never been in the queue, you must make sure that get-index-fn returns -1. See example below. A trivial way to implement set-index-fn / get-index-fn would be like this: (let* ((hash (make-hash-table)) (set-index-fn (lambda (item index)) (setf (gethash item hash) index)) (get-index-fn (lamda (item) (gethash item hash -1)))) (make-empty-queue #'< set-index-fn get-index-fn)) Notice that get-index-fn returns -1 for items that aren't in the hash. It might also be a good idea to change set-index-fn to something like this: (lambda (item index) (if (= index -1) (remhash item hash) (setf (gethash item hash) index))) Of course, this code all depends on each item being distinguishable via 'eql, since that is the default test for a hash-table. The motivation for handling the index maintenance this way is that it is straightforward and flexible. Any item can be stored in the queue and the user has control over how they are identified and where this storage takes place. In many cases, it may make sense to store the index directly as a property of the item being stored. In other cases, we may want a looser mapping that only uses some attributes of the item being stored, so that we can lookup similar items (e.g., if we were using the priority queue in a search algorithm we could check to see if the queue already contains a node with the same state as a newly discovered node).

QUEUE-DELETE (Q ITEM)

Delete item from the queue. Returns the queue. Signals empty-queue-error if the queue is empty. Signals item-not-found-error if the item wasn't found.

QUEUE-EMPTY-P (Q)

Are there no items in the queue?

QUEUE-FIND (Q ITEM)

Checks if item is in the queue (using the supplied get-index-fn). If it is, returns two values: the actual item from the queue (which could be different than the supplied item, since the client can setup the mapping however they like) and the index. If it isn't, returns nil and -1.

QUEUE-INSERT (Q ITEM)

Insert the item by priority according to the compare function. Returns the queue. [Page 140 CL&R 2nd ed.].

QUEUE-PEEK (Q)

Return the element at the front of the queue. Signals empty-queue-error if the queue is empty.

QUEUE-POP (Q)

Remove the element from the front of the queue and return it. Signals empty-queue-error if the queue is empty. [Page 139 CL&R 2nd ed.].

QUEUE-REPLACE (Q OLD NEW)

Replace old with new in the queue. This is analogous to deleting the old item and inserting the new one, but it is almost always more efficient (and never less efficient) because we can just fix up the heap from the position of the swapped item. Obviously, this only makes sense if you expect the two items to be located very close to each other in the queue (perhaps even in the same location, such as if the priority is the same, but you need to swap the item being stored because of other data it contains). Returns the queue. Signals item-not-found-error if the old item wasn't found.

QUEUE-UPDATE (Q ITEM)

queue-update makes sure that item is sorted correctly in q. Call queue-update after changing item in such a way that would affect its priority. Returns the queue. Signals item-not-found-error if the item wasn't found.

Undocumented

QUEUE-SIZE (Q)

Private

HEAPIFY (HEAP I COMPARE-FN SET-INDEX-FN)

Assume that the children of i are heaps, but that heap[i] may be worse than its children. If it is, move heap[i] down where it belongs. [Page 130 CL&R 2nd ed.].

IMPROVE-KEY (HEAP I COMPARE-FN SET-INDEX-FN)

The item at i may be better than its parent. Promote the item until it is in the correct position.

Q-COMPARE-FN (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

Q-GET-INDEX-FN (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

Q-ITEMS (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

Q-SET-INDEX-FN (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

Undocumented

COPY-Q (INSTANCE)

LEFT (I)

MAKE-Q (&KEY ((COMPARE-FN DUM46) NIL) ((SET-INDEX-FN DUM47) NIL) ((GET-INDEX-FN DUM48) NIL) ((ITEMS DUM49) NIL))

PARENT (I)

SETFQ-COMPARE-FN (NEW-VALUE INSTANCE)

SETFQ-GET-INDEX-FN (NEW-VALUE INSTANCE)

SETFQ-ITEMS (NEW-VALUE INSTANCE)

Q-P (OBJECT)

SETFQ-SET-INDEX-FN (NEW-VALUE INSTANCE)

CLASS

Private

Undocumented

Q

CONDITION

Public

EMPTY-QUEUE-ERROR

Signaled when an operation depends on a non-empty queue.

ITEM-NOT-FOUND-ERROR

Signaled when an operation depends on an item that was not found in the queue.

CONSTANT

Private

+NOT-IN-QUEUE+

A sentinel value associated with an item that is not in the queue.