include/lang/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 <limits>
  25
  26 template <class Event, class TimeType, int N>
  27 class PriorityQueueT
  28 {
  29 public:
  30         PriorityQueueT() {
  31                 Empty();
  32         }
  33
  34         bool Add(Event& inEvent)
  35                 {
  36                         if (mSize >= N) return false;
  37                         long mom = mSize++;
  38                         long me = mom;
  39                         for (; mom>0;) {        /* percolate up heap */
  40                                 mom = mom - 1 >> 1;
  41                                 if (inEvent.mTime < mEvents[mom].mTime) {
  42                                         mEvents[me] = mEvents[mom];
  43                                         me = mom;
  44                                 } else break;
  45                         }
  46                         mEvents[me] = inEvent;
  47                         return true;
  48                 }
  49         void Perform(TimeType inNow)
  50                 {
  51                         while (NextTime() <= inNow) {
  52                                 Event event = Remove();
  53                                 event.Perform();
  54                         }
  55                 }
  56         TimeType NextTime() { return mEvents[0].mTime; }
  57         bool Ready(TimeType inTime) { return NextTime() <= inTime; }
  58         void Flush() { Perform(std::numeric_limits<TimeType>::max()); }
  59         void Empty() { mSize = 0; SetEmptyTime(); }
  60         void SetEmptyTime() { mEvents[0].mTime = std::numeric_limits<TimeType>::max(); }
  61
  62         Event Remove()
  63                 {
  64                         Event event = mEvents[0];
  65                         if (--mSize == 0) SetEmptyTime();
  66                         else {
  67                                 Event temp = mEvents[mSize];
  68                                 long mom = 0;
  69                                 long me = 1;
  70                                 for (;me < mSize;) { /* demote heap */
  71                                         if (me+1 < mSize && mEvents[me].mTime > mEvents[me+1].mTime) {
  72                                                 me ++;
  73                                         }
  74                                         if (temp.mTime > mEvents[me].mTime) {
  75                                                 mEvents[mom] = mEvents[me];
  76                                                 mom = me;
  77                                                 me = (me << 1) + 1;
  78                                         } else break;
  79                                 }
  80                                 mEvents[mom] = temp;
  81                         }
  82                         return event;
  83                 }
  84
  85 private:
  86         long mSize;
  87         Event mEvents[N];
  88 };
  89
  90 #endif