home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / warphead.zip / H / PRIORTYQ.H < prev    next >
C/C++ Source or Header  |  1997-02-28  |  3KB  |  99 lines
  1. //====START_GENERATED_PROLOG======================================
  2. //
  3. //
  4. //   COMPONENT_NAME: odutils
  5. //
  6. //   CLASSES:   PriorityQueue
  7. //        Sortable
  8. //
  9. //   ORIGINS: 82,27
  10. //
  11. //
  12. //   (C) COPYRIGHT International Business Machines Corp. 1995,1996
  13. //   All Rights Reserved
  14. //   Licensed Materials - Property of IBM
  15. //   US Government Users Restricted Rights - Use, duplication or
  16. //   disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
  17. //       
  18. //   IBM DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  19. //   ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  20. //   PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  21. //   CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
  22. //   USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  23. //   OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
  24. //   OR PERFORMANCE OF THIS SOFTWARE.
  25. //
  26. //====END_GENERATED_PROLOG========================================
  27. //
  28. // @(#) 1.3 com/src/utils/include/PriortyQ.h, odutils, od96os2, odos29646d 7/15/96 18:01:52 [ 11/15/96 15:29:02 ]
  29. /*
  30.     File:        PriortyQ.h
  31.  
  32.     Contains:    Priority-Queue data structure.
  33.  
  34.     Owned by:    Jens Alfke
  35.  
  36.     Copyright:    ⌐ 1994 - 1995 by Apple Computer, Inc., all rights reserved.
  37.  
  38.     Theory of Operation:
  39.     
  40.     A Priority Queue is a sorted collection that allows entries to be added to
  41.     the queue in arbitrary order, and allows the first (in sort order) entry
  42.     -- and only the first entry -- to be viewed and removed. Its implementation
  43.     makes it very efficient, using a partially sorted data structure called a
  44.     heap. Any standard algorithms textbook will describe this; see Sedgewick's
  45.     "Algorithms in C++", ch.11.
  46. */
  47.  
  48.  
  49. #ifndef _PRIORTYQ_
  50. #define _PRIORTYQ_
  51.  
  52. #ifndef _ODTYPES_
  53. #include "ODTypes.h"
  54. #endif
  55.  
  56. #ifndef _PLFMDEF_
  57. #include "PlfmDef.h"
  58. #endif
  59.  
  60.  
  61. //=============================================================================
  62. // Queue-element mix-in class
  63. //=============================================================================
  64.  
  65. // Objects you put in the queue must inherit from this abstract mix-in class.
  66.  
  67. class Sortable {
  68.     public:
  69.         ODVMethod ODBoolean    ComesBefore( const Sortable* ) const
  70.             =0;
  71. };
  72.  
  73.  
  74. //=============================================================================
  75. // PriorityQueue
  76. //=============================================================================
  77.  
  78.  
  79. class PriorityQueue {
  80.     public:
  81.         PriorityQueue( ODULong suggestedSize =0 );
  82.         virtual ~PriorityQueue( );
  83.         
  84.         ODMethod    void        Add( const Sortable* );
  85.         ODMethod    Sortable*    GetFirst( ) const;
  86.         ODMethod    Sortable*    RemoveFirst( );
  87.         inline        void        RemoveAll( )        {fLast = 0;}
  88.         ODMethod    void        DeleteAll( );
  89.         
  90.         inline        ODBoolean    IsEmpty( ) const    {return fLast==0;}
  91.         
  92.     private:
  93.         ODULong        fSize;
  94.         ODULong        fLast;
  95.         const Sortable*    *fHeap;        // Points to array of Sortable*s
  96. };
  97.  
  98. #endif /*_PRIORTYQ_*/
  99.