Priority Queue

The Foundation framework: it has some collections. It doesn’t have others.

In particular, it doesn’t have a priority queue, which I need. CoreFoundation does, but this is for Oolite so it needs to work with GNUstep. Yes, I could bring in all of CFLite, but without the toll-free-bridging it’s not particularly attractive.

Mike Ash (who seems to be getting an indecent amount of exposure in this blog, to the extent that it counts as an exposed location) wrote about the issue last year. His solution was to use the C++ Standard Template Library, but I don’t like that solution much because a) GNUstep doesn’t play nice with Objective-C++ (its headers aren’t C++-clean) and b) it’s C++.

So, as you may have guessed, I’ve gone and written one. Here it is, with the small amount of Oolite dependency ripped out. MIT/X11 license.

Operations supported:

• Add object.
• Add all objects in a collection (anything that responds to -objectEnumerator or -nextObject).
• Retrieve highest-priority object. Priority is defined by a comparison method specified when creating the priority queue. Priority is defined such that the NSOrderedDescendingmost object has the highest priority; as such, using caseInsensitiveCompare: as the comparator will cause strings to be retrieved in lexicographic order.
• Delete highest-priority object.
• Delete specific object.
• Delete equal object (i.e., delete one object such that the comparator returns NSOrderedSame).
• Retrieve all objects in sorted order, emptying the queue.
• Equality testing and (low-quality) hashing.
• Copying of the entire queue.