home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 January: Mac OS SDK / Dev.CD Jan 97 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc™ Source Code / Utilities / PriortyQ.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-08-28  |  3.9 KB  |  167 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        PriortyQ.cpp
  3.  
  4.     Contains:    Priority-Queue data structure.
  5.  
  6.     Owned by:    Jens Alfke
  7.  
  8.     Copyright:    © 1994 - 1995 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Theory of Operation:
  11.     
  12.     A Priority Queue is a sorted collection that allows entries to be added to
  13.     the queue in arbitrary order, and allows the first (in sort order) entry
  14.     -- and only the first entry -- to be viewed and removed. Its implementation
  15.     makes it very efficient, using a partially sorted data structure called a
  16.     heap. Any standard algorithms textbook will describe this; see Sedgewick's
  17.     "Algorithms in C++", ch.11.
  18.     
  19.     An abstract mix-in class "Sortable" is provided, which provides a single
  20.     method "ComesBefore" that allows its instances to be sorted.
  21.     Objects in the priority queue must inherit from Sortable.
  22. */
  23.  
  24.  
  25. #ifndef _PRIORTYQ_
  26. #include "PriortyQ.h"
  27. #endif
  28.  
  29. #ifndef _ODMEMORY_
  30. #include "ODMemory.h"
  31. #endif
  32.  
  33. #ifndef _ODUTILS_
  34. #include "ODUtils.h"
  35. #endif
  36.  
  37. #ifndef _EXCEPT_
  38. #include "Except.h"
  39. #endif
  40.  
  41. #ifndef _ODDEBUG_
  42. #include "ODDebug.h"
  43. #endif
  44.  
  45.  
  46. #define PARENT(N)        ((N)>>1)        // Parent of a node
  47. #define LEFTCHILD(N)    ((N)<<1)        // Left child of a node
  48. #define SIBLING(N)        ((N)+1)            // Right sibling of left child
  49.  
  50.  
  51. //=============================================================================
  52. // Housekeeping
  53. //=============================================================================
  54.  
  55.  
  56. PriorityQueue::PriorityQueue( ODULong suggestedSize /*=0*/ )
  57.     :fHeap(kODNULL),
  58.      fLast(0)                // Item 0 is not used so start fLast at 0
  59. {
  60.     if( suggestedSize==0 )
  61.         fSize = 32;
  62.     else if( suggestedSize >= 0x10000000 ) {
  63.         WARN("Ridiculous suggested size %ld",suggestedSize);
  64.         fSize = 128;
  65.     } else
  66.         fSize = suggestedSize;
  67. }
  68.  
  69.  
  70. PriorityQueue::~PriorityQueue( )
  71. {
  72.     ODDeleteObject(fHeap);
  73. }
  74.  
  75.  
  76. //=============================================================================
  77. // Insertion
  78. //=============================================================================
  79.  
  80.  
  81. void
  82. PriorityQueue::Add( const Sortable *s )
  83. {
  84.     ASSERT(s!=kODNULL, kODErrIllegalNullInput);
  85.     
  86.     // Create or grow the heap if necessary:
  87.     if( fHeap==kODNULL || fLast+1>=fSize ) {
  88.         ODULong newSize = fSize;
  89.         if( fHeap )
  90.             newSize <<= 1;            // Grow by a factor of 2
  91.         const Sortable* *newHeap = new const Sortable* [newSize];
  92.         newHeap[0] = kODNULL;
  93.         ODBlockMove(&fHeap[1],&newHeap[1], fLast*sizeof(Sortable*));
  94.         if( fHeap ) delete fHeap;
  95.         fHeap = newHeap;
  96.         fSize = newSize;
  97.     }
  98.     
  99.     // Standard heap insertion: (Sedgewick p.150)
  100.     ODULong k = ++fLast;                                // 1st item is at 1!
  101.     while( k>1 && s->ComesBefore(fHeap[PARENT(k)]) ) {
  102.         fHeap[k] = fHeap[PARENT(k)];
  103.         k = PARENT(k);
  104.     }
  105.     fHeap[k] = s;
  106. }
  107.  
  108.  
  109. //=============================================================================
  110. // Accessing
  111. //=============================================================================
  112.  
  113.  
  114. Sortable*
  115. PriorityQueue::GetFirst( ) const
  116. {
  117.     if( fLast==0 )
  118.         return kODNULL;
  119.     else
  120.         return (Sortable*)fHeap[1];    // Cast to non-const so client can modify!
  121. }
  122.  
  123.  
  124. //=============================================================================
  125. // Deletion
  126. //=============================================================================
  127.  
  128.  
  129. Sortable*
  130. PriorityQueue::RemoveFirst( )
  131. {
  132.     if( fLast==0 )
  133.         return kODNULL;
  134.     else {
  135.         const Sortable *first = fHeap[1];
  136.         
  137.         // Now remove the first element by moving the last atop it and sorting:
  138.         const Sortable *v = fHeap[fLast--];
  139.         ODULong k = 1;
  140.         ODULong j;
  141.         while( k <= (fLast>>1) ) {
  142.             j = LEFTCHILD(k);
  143.             if( j<fLast && fHeap[SIBLING(j)]->ComesBefore(fHeap[j]) )
  144.                 j = SIBLING(j);
  145.             if( v->ComesBefore(fHeap[j]) )
  146.                 break;
  147.             fHeap[k] = fHeap[j];
  148.             k = j;
  149.         }
  150.         fHeap[k] = v;
  151.         
  152.         return (Sortable*)first;    // Cast to non-const so client can modify!
  153.     }
  154. }
  155.  
  156.  
  157. void
  158. PriorityQueue::DeleteAll( )
  159. {
  160.     // This function does violate the constness of the contained objects
  161.     // (by deleting them) but this is often useful to do...
  162.     
  163.     for( ODULong i=1; i<=fLast; i++ )
  164.         delete (Sortable*) fHeap[i];
  165.     fLast = 0;
  166. }
  167.