home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1994 June / NEBULA_SE.ISO / SourceCode / MiscKit / Temp / DataStructures / MiscPriorityQueue.m < prev    next >
Encoding:
Text File  |  1994-03-22  |  2.9 KB  |  191 lines
  1. //
  2. //    MiscPriorityQueue.m -- a Priority Queue
  3. //        Written by Doug McClure (c) 1994 by Doug McClure.
  4. //                Version 1.0.  All rights reserved.
  5. //
  6. //        This notice may not be removed from this source code.
  7. //
  8. //    This object is included in the MiscKit by permission from the author
  9. //    and its use is governed by the MiscKit license, found in the file
  10. //    "LICENSE.rtf" in the MiscKit distribution.  Please refer to that file
  11. //    for a list of all applicable permissions and restrictions.
  12. //    
  13.  
  14. /*
  15.  * $RCSfile$
  16.  *
  17.  * $Author$
  18.  *
  19.  * $Revision$
  20.  *
  21.  * $Date$
  22.  *
  23. */
  24.  
  25. #import <misckit/MiscPriorityQueue.h>
  26.  
  27. #define MiscPriorityQueueVersion    100
  28.  
  29. typedef struct _Node
  30. {
  31.   unsigned priority;
  32.   id object;
  33. }
  34. Node;
  35.  
  36. @implementation MiscPriorityQueue
  37.  
  38. - dequeue
  39. {
  40.   Node *node;
  41.   
  42.   if ( [self count] )
  43.     {
  44.       node = ((Node *)[self lastElement]);
  45.       [self removeLastElement];
  46.       return node->object;
  47.     }
  48.   
  49.   return nil;
  50. }
  51.  
  52.  
  53. - enqueue:anObject withPriority:(int)priority
  54. {
  55.   Node *newNode;
  56.   
  57.   newNode = (Node *)NXZoneMalloc([self zone], sizeof(Node));
  58.   newNode->priority = priority;
  59.   newNode->object = anObject;
  60.  
  61.   return [self addElement:newNode];
  62. }
  63.  
  64.  
  65. - init
  66. {
  67.   return [self initCount:0];
  68. }
  69.  
  70.  
  71. - initCount:(unsigned int)numSlots
  72. {
  73.   return [self initCount:numSlots elementSize:sizeof(Node) description:@encode(Node)];
  74. }
  75.  
  76.  
  77. - (BOOL)isEqual:anObject
  78. {
  79.   return NO;
  80. }
  81.  
  82.  
  83. - (unsigned)highestPriority
  84. {
  85.   return [self priorityAt:([self count]-1)];
  86. }
  87.  
  88.  
  89. - (unsigned)lowestPriority
  90. {
  91.   return [self priorityAt:0];
  92. }
  93.  
  94.  
  95. - makeObjectsPerform:(SEL)aSelector
  96. {
  97.   Node *node;
  98.  
  99.   for ( node = ((Node *)[self setFirstElement]) ; (id)node != nil ; node = ((Node *)[self setNextElement]) )
  100.     {
  101.       if ( [node->object respondsTo:aSelector] )
  102.     {
  103.       [node->object perform:aSelector];
  104.     }
  105.     }
  106.   
  107.   return self;
  108. }
  109.  
  110.  
  111. - makeObjectsPerform:(SEL)aSelector with:anObject
  112. {
  113.   Node *node;
  114.  
  115.   for ( node = ((Node *)[self setFirstElement]) ; (id)node != nil ; node = ((Node *)[self setNextElement]) )
  116.     {
  117.       if ( [node->object respondsTo:aSelector] )
  118.     {
  119.       [node->object perform:aSelector with:anObject];
  120.     }
  121.     }
  122.   
  123.   return self;
  124. }
  125.  
  126.  
  127. - objectAt:(unsigned)index
  128. {
  129.   Node *node;
  130.   
  131.   if ( index < [self count] )
  132.     {
  133.       node = ((Node*)[self elementAt:index]);
  134.       return node->object;
  135.     }
  136.   
  137.   return nil;
  138. }
  139.  
  140.   
  141. - (unsigned)priorityAt:(unsigned)index
  142. {
  143.   Node *node;
  144.   
  145.   if ( index < [self count] )
  146.     {
  147.       node = ((Node*)[self elementAt:index]);
  148.       return node->priority;
  149.     }
  150.   
  151.   return NX_NOT_IN_LIST;
  152. }
  153.  
  154.  
  155. - read:(NXTypedStream *)stream
  156. {
  157.   return self;
  158. }
  159.  
  160.  
  161. - write:(NXTypedStream *)stream
  162. {
  163.   return self;
  164. }
  165.  
  166. @end
  167.  
  168.  
  169. @implementation MiscPriorityQueue(OverrideMethods)
  170.  
  171. - (int)compare:(void *)elementA to:(void *)elementB caseCheck:(BOOL)flag
  172. {
  173.   Node *nodeA = ((Node *)elementA);
  174.   Node *nodeB = ((Node *)elementB);
  175.  
  176.   if ( nodeA->priority < nodeB->priority )
  177.     {
  178.       return -1;
  179.     }
  180.   else if ( nodeA->priority > nodeB->priority )
  181.     {
  182.       return 1;
  183.     }
  184.   else
  185.     {
  186.       return 0;
  187.     }
  188. }
  189.  
  190. @end
  191.