Dear fellow Mozart User,if you are looking for an efficient thread safe priority queue whose size grows incrementally without other limits than the amount of available memory, the attached code may be of interest to you. The code is also interesting because it demonstrates what I think is an elegant style of packaging an ADT securely. To instantiate the provided ADT in some context, you could write something like this in a declaration section (for example before the "in" inside a local-statement):
pq(
push:Push
pop:Pop
clear:Clear
empty:Empty
notEmpty:NotEmpty
toList:ToList
forAll:ForAll
forAllInOrder:ForAllInOrder
newClone:NewClone
) = {NewPQ PriorityOf}
You need to define PriorityOf, which is supposed to be a function that for
each item X to be stored in the queue returns the priority of X as a number
(where smaller numbers means higher priorities). The above declaration
enables the following operations:
* {Push X}. Adds the item X to the priority queue.
* {Pop}. Returns the item X in the priority queue that has the highest
priority and removes it from the queue. If the queue is empty, the
exception 'pqEmpty' is raised. (You may want to add a CondPop to the ADT.)
* {Clear}. Removes all items from the priority queue.
* {Empty}. Returns true if the queue is empty. Otherwise returns false.
* {NotEmpty}. Returns false if the queue is empty. Otherwise returns true.
* {ToList} Returns all items in the queue ordered by their priority in
descending order (the order in which they would be popped from the queue).
The queue itself is not changed in any way.
* {ForAll Action}: Applies the unary procedure Action on all items currently stored in the queue (in any order).
* {ForAllInOrder Action}: Applies the unary procedure Action on all items in the order in which they are enumerated by ToList. In other words, equivalent to {ForAll {ToList} Action}.
* {NewClone}: Returns a copy of the queue.
The time complexity of Push and Pop is logarithmic in the size n of the
queue (that is, the number of items already stored in the queue). Clear,
Empty, NotEmpty and NewClone takes constant time. ForAll looks linear to me.
The time complexity of ForAllInOrder and ToList is probably n * log(n), but
I am too lazy right now to make myself sure of that. Note that the thread
safety of the ADT relies completely on the atomicity of Exchange. Also note
that ADT security is maintained without using NewName and without doing
wrapping or unwrapping every time an operation is performed. Finally, note
that the queue operations can be invoked as ordinary procedures without
having to pass around the queue itself as an extra argument. This is a good
thing. Procedures with many parameters should always be avoided to the
greatest extent possible (at least as long as it can be done without
introducing unnecesary statefulness), because such procedures threaten the
readability of the code where they are used.
You can use the "..." wildcard if you only want to import a subset of the queue operations. And of course, the names of the procedures providing the queue operations can be chosen freely. For example, you could write
pq(
push:Run
pop:CurrentTask
notEmpty:Active
newClone:PqClone
...
) = {NewPQ PriorityOf}
If you need a priority queue instance that can easily passed around, it may
be better to write something like
PQ = {NewPQ PriorityOf}
and access the queue operations by using the dot-operator. (PQ.push, PQ.pop,
etc). The different importing styles can of course be combined.
At this point, you may wonder why the ADT is not packaged as a functor? I would really like to do that! But as far as I understand Mozart, it does not seem possible to instantiate functors with an argument (such as the PriorityOf fed to NewPQ). If someone knows how to do this elegantly, please let me know.
The observant reader may have noticed that the provided ADT actually supports one more important operation that is not exposed in the interface: computing the union of two priority queues. Exposing the Union operation elegantly and securely is a bit more challenging, but perfectly possible without any packing style changes. (Hint: Mozart allows not only atoms, but also unforgeable names to be used as features.)
As some of you have already recognized, the provided code is highly inspired by the good old "Data Structures & Their Algorithms" by Lewis & Denenberg. I guess there are more sophisticated PQ algorithms out there, but this one is simple and good enough for many and my purposes. The code is a tiny part of the incremental interactive constraint solving environment that I am building with Mozart, and spending more time on priority queues at this point would be "premature optimization". In case you didn't know, premature optimization is one of seven deadly sins!
Feel free to point out significant errors in the above text or code. It is appreciated.
Regards .Björn PSI love Mozart! Since I started to use it, my productivity has increased with a factor 10. For the first
time since the eighties, programming is fun again! DS
PQ.oz
Description: Binary data
_________________________________________________________________________________ mozart-users mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-users
