This is PriorityQueue.m in view mode; [Download] [Up]
#import "PriorityQueue.h"
// Copyright (C) 1993 by Don Yacktman
// To Do: make sure that all List methods that add an object are overridden
// to make sure that added objects follow the protocol. Note that I could
// also provide a default key (like use -hash) if the protocol isn't
// followed, but I doubt this would be particularly useful. A given
// application for this object will know how it wants things sorted and
// will, therefore, implement the necessary method.
// Implementation note: we keep the list organized as a heap, which allows
// us to do extremely fast searching and insertion. The key point is that
// the heap structure will _always_ leave us with the next event in slot #1.
@interface PriorityQueue(private)
// utility methods that shouldn't be called or modified by you. :-)
- _swapObjectsAt:(int)index1 and:(int)index2;
- _heapify:(int)node;
@end
@implementation PriorityQueue(private)
- _swapObjectsAt:(unsigned int)index1 and:(unsigned int)index2
{ // right now only heapify uses this, so it could be folded into
// it for speed. This is easier to read, IMHO...
[self replaceObjectAt:index2
with:[self replaceObjectAt:index1
with:[self objectAt:index2]]];
return self;
}
- _heapify:(unsigned int)node
{
unsigned int smallest = node; // the current node's index
unsigned int left = 2 * (node + 1) - 1; // left child node's index
unsigned int right = 2 * (node + 1); // right child node's index
unsigned int max = [self count];
// find out which has the smaller key, parent, left child, or right child.
// the smallest becomes the parent; if no change, we're done, but if we have
// to move a node, then we will check the new child to make sure it's
// children aren't smaller... so we recursively descend into the heap.
if (left < max)
if ([[self objectAt:left] sortKey] < [[self objectAt:smallest] sortKey])
smallest = left;
if (right < max)
if ([[self objectAt:right] sortKey] < [[self objectAt:smallest] sortKey])
smallest = right;
if (smallest != node) { // left or right is smaller...
[self _swapObjectsAt:node and:smallest]; // swap to keep sorted
[self _heapify:smallest]; // propagate down the heap
}
return self;
}
@end
@implementation PriorityQueue
// we override to sort it as we go...
- addObject:anObject
{
unsigned int i, newKey;
if ([anObject conformsTo:@protocol()]) newKey = [anObject sortKey];
else return nil; // error, object can't be sorted without a key!
[super addObject:anObject]; // make sure that we have dynamically
// grown to the right size to fit the new object
i = [self count]; // start at the bottom of the heap
// All the "x - 1" in the while loop are 'cos the List starts at
// index zero and the heap algorithm want us to used start index=1
while ((i > 1) && ([[self objectAt:((i/2) - 1)] sortKey] > newKey)) {
// shift object to bottom of heap if they have larger keys
// so that we'll have room to insert our new object
[self replaceObjectAt:(i-1) with:[self objectAt:((i/2)-1)]];
i /= 2; // heap is a binary tree, implemented in a linear array;
// dividing by two always gives the parent node...
}
// insert the new object in the right place
[self replaceObjectAt:(i-1) with:anObject];
return self;
}
- removeNextObject
{
id ret = [self objectAt:0];
// put the last object in the heap at the top
[self replaceObjectAt:0 with:[self lastObject]];
// get rid of the duplicate we just created
[self removeLastObject];
// and then propagate it to the bottom of the heap
[self _heapify:0];
return ret;
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.