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.
This entry was posted in Cocoa, Code, Oolite. Bookmark the permalink.

5 Responses to Priority Queue

  1. Bleyddyn says:

    There doesn’t seem to be a JAPriorityQueue.h file in the download.

  2. Jens Ayton says:

    Isn’t there? Oh, there isn’t. Oh, and the test file doesn’t do anything. Bit rot, I say!

    Anyway, it’s fixed now.

  3. Favo Yang says:

    Just looking for a priority queue, it’s sweet. Thanks!

  4. rich says:

    The framework does have a priority queue it’s called NSOperationQueue. you create custom subclasses of NSOperation and send them to the queue.

  5. Jens Ayton says:

    NSOperationQueue is specialised for, well, operations. It isn’t an appropriate model for everything that requires a priority queue. It wouldn’t be a good choice for my original use case, for instance.

    Besides, NSOperationQueue was not publicly available at the time this post was written, and as I mentioned (twice) I needed compatibility with GNUstep, which didn’t have NSOperationQueue until earlier this year.

Leave a Reply

Your email address will not be published. Required fields are marked *