include/server/PriorityQueue.h

   1 /*
   2         SuperCollider real time audio synthesis system
   3     Copyright (c) 2002 James McCartney. All rights reserved.
   4         http://www.audiosynth.com
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  19 */
  20
  21 #ifndef _PriorityQueue_
  22 #define _PriorityQueue_
  23
  24 #include <stdio.h>
  25 #include <math.h>
  26 // #include <stdexcept>
  27
  28 #define SANITYCHECK 0
  29
  30 #if defined(_WIN32) && !defined(__MINGW32__)
  31 const int64 kMaxInt64 = 0x7FFFFFFFFFFFFFFF;
  32 #else
  33 const int64 kMaxInt64 = ~(1LL<<63);
  34 #endif
  35
  36 template <class Event, int N>
  37 class PriorityQueueT
  38 {
  39 public:
  40         PriorityQueueT() {
  41                 Empty();
  42         }
  43
  44         bool Add(Event& inEvent)
  45                 {
  46                         if (mSize >= N) return false;
  47                         long mom = mSize++;
  48                         long me = mom;
  49                         for (; mom>0;) {        /* percolate up heap */
  50                                 mom = (mom - 1) >> 1;
  51                                 if (inEvent.mTime < mEvents[mom].mTime) {
  52                                         mEvents[me] = mEvents[mom];
  53                                         me = mom;
  54                                 } else break;
  55                         }
  56                         mEvents[me] = inEvent;
  57 #if SANITYCHECK
  58                         SanityCheck();
  59 #endif
  60                         return true;
  61                 }
  62         void Perform(int64 inTime)
  63                 {
  64                         while (NextTime() <= inTime) {
  65                                 Event event = Remove();
  66                                 event.Perform();
  67                         }
  68                 }
  69         int64 NextTime() { return mEvents[0].mTime; }
  70         bool Ready(int64 inTime) { return NextTime() <= inTime; }
  71         void Flush() { Perform(kMaxInt64); }
  72         void Empty() { mSize = 0; SetEmptyTime(); }
  73         void SetEmptyTime() { mEvents[0].mTime = kMaxInt64; }
  74         int Size() { return mSize; }
  75
  76         Event Remove()
  77                 {
  78                         Event event = mEvents[0];
  79                         if (--mSize == 0) SetEmptyTime();
  80                         else {
  81                                 Event temp = mEvents[mSize];
  82                                 long mom = 0;
  83                                 long me = 1;
  84                                 for (;me < mSize;) { /* demote heap */
  85                                         if (me+1 < mSize && mEvents[me].mTime > mEvents[me+1].mTime) {
  86                                                 me ++;
  87                                         }
  88                                         if (temp.mTime > mEvents[me].mTime) {
  89                                                 mEvents[mom] = mEvents[me];
  90                                                 mom = me;
  91                                                 me = (me << 1) + 1;
  92                                         } else break;
  93                                 }
  94                                 mEvents[mom] = temp;
  95                         }
  96 #if SANITYCHECK
  97                         SanityCheck();
  98 #endif
  99                         return event;
 100                 }
 101         void SanityCheck()
 102         {
 103                 for (int i=0; i<mSize; ++i)
 104                 {
 105                         // int j = (i<<1)+1;
 106                         //if (j<mSize && mEvents[i].mTime > mEvents[j].mTime) throw std::runtime_error("priority queue unsorted");
 107                         //if (k<mSize && mEvents[i].mTime > mEvents[k].mTime) throw std::runtime_error("priority queue unsorted");
 108                 }
 109         }
 110         void DebugDump()
 111         {
 112                 for (int i=0; i<mSize; ++i)
 113                 {
 114                         printf("%d %016llX\n", i, mEvents[i].mTime);
 115                 }
 116         }
 117 private:
 118         int mSize;
 119         Event mEvents[N];
 120 };
 121
 122 #endif