home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1994 June / NEBULA_SE.ISO / SourceCode / MiscKit / Temp / DataStructures / PriorityQueue.m < prev   
Encoding:
Text File  |  1994-01-31  |  3.5 KB  |  101 lines
  1. #import "PriorityQueue.h"
  2.  
  3. // (C) 1993 by Don Yacktman
  4.  
  5. // To Do:  make sure that all List methods that add an object are overridden
  6. // to make sure that added objects follow the protocol.  Note that I could
  7. // also provide a default key (like use -hash) if the protocol isn't
  8. // followed, but I doubt this would be particularly useful.  A given
  9. // application for this object will know how it wants things sorted and
  10. // will, therefore, implement the necessary method.
  11.  
  12.  
  13. // Implementation note:  we keep the list organized as a heap, which allows
  14. // us to do extremely fast searching and insertion.  The key point is that
  15. // the heap structure will _always_ leave us with the next event in slot #1.
  16.  
  17. @interface PriorityQueue(private)
  18.  
  19. // utility methods that shouldn't be called or modified by you.  :-)
  20. - _swapObjectsAt:(int)index1 and:(int)index2;
  21. - _heapify:(int)node;
  22.  
  23. @end
  24.  
  25. @implementation PriorityQueue(private)
  26.  
  27. - _swapObjectsAt:(unsigned int)index1 and:(unsigned int)index2
  28. {    // right now only heapify uses this, so it could be folded into
  29.     // it for speed.  This is easier to read, IMHO...
  30.     [self replaceObjectAt:index2
  31.           with:[self replaceObjectAt:index1
  32.                      with:[self objectAt:index2]]];
  33.     return self;
  34. }
  35.  
  36. - _heapify:(unsigned int)node
  37. {
  38.     unsigned int smallest = node;            // the current node's index
  39.     unsigned int left = 2 * (node + 1) - 1;    // left child node's index
  40.     unsigned int right = 2 * (node + 1);    // right child node's index
  41.     unsigned int max = [self count];
  42.  
  43.     // find out which has the smaller key, parent, left child, or right child.
  44.     // the smallest becomes the parent; if no change, we're done, but if we have
  45.     // to move a node, then we will check the new child to make sure it's
  46.     // children aren't smaller... so we recursively descend into the heap.
  47.     if (left < max)
  48.         if ([[self objectAt:left] sortKey] < [[self objectAt:smallest] sortKey])
  49.             smallest = left;
  50.     if (right < max)
  51.         if ([[self objectAt:right] sortKey] < [[self objectAt:smallest] sortKey])
  52.             smallest = right;
  53.     if (smallest != node) { // left or right is smaller...
  54.         [self _swapObjectsAt:node and:smallest];    // swap to keep sorted
  55.         [self _heapify:smallest];    // propagate down the heap
  56.     }
  57.     return self;
  58. }
  59.  
  60. @end
  61.  
  62. @implementation PriorityQueue
  63.  
  64. // we override to sort it as we go...
  65. - addObject:anObject
  66. {
  67.     unsigned int i, newKey;
  68.     if ([anObject conformsTo:@protocol()]) newKey = [anObject sortKey];
  69.     else return nil;    // error, object can't be sorted without a key!
  70.     [super addObject:anObject]; // make sure that we have dynamically
  71.                     // grown to the right size to fit the new object
  72.     i = [self count]; // start at the bottom of the heap
  73.     // All the "x - 1" in the while loop are 'cos the List starts at
  74.     // index zero and the heap algorithm want us to used start index=1
  75.     while ((i > 1) && ([[self objectAt:((i/2) - 1)] sortKey] > newKey)) {
  76.         // shift object to bottom of heap if they have larger keys
  77.         // so that we'll have room to insert our new object
  78.         [self replaceObjectAt:(i-1) with:[self objectAt:((i/2)-1)]];
  79.         i /= 2; // heap is a binary tree, implemented in a linear array;
  80.         // dividing by two always gives the parent node...
  81.     }
  82.     // insert the new object in the right place
  83.     [self replaceObjectAt:(i-1) with:anObject];
  84.     return self;
  85. }
  86.  
  87. - removeNextObject
  88. {
  89.     id ret = [self objectAt:0];
  90.     // put the last object in the heap at the top
  91.     [self replaceObjectAt:0 with:[self lastObject]];
  92.     // get rid of the duplicate we just created
  93.     [self removeLastObject];
  94.     // and then propagate it to the bottom of the heap
  95.     [self _heapify:0];
  96.     return ret;
  97. }
  98.  
  99. @end
  100.  
  101.