diff options
author | IOhannes m zmölnig <zmoelnig@iem.at> | 2015-10-14 15:14:38 +0200 |
---|---|---|
committer | IOhannes m zmölnig <zmoelnig@iem.at> | 2015-10-14 15:14:38 +0200 |
commit | 28b7e464fd119b8c848753a1f41070422c463c41 (patch) | |
tree | 07449abdf85d8f1fd4068839b974242b429720ca /sc4pd/headers/server/PriorityQueue.h | |
parent | 90c6018a9401e38859f733b3521c919e042322b7 (diff) | |
parent | 6932ee2d22511226378218992b0005cb01eb235e (diff) |
Merge branchesHEADsvn2git-headmaster
- abstractions/tb
- externals/tb
Diffstat (limited to 'sc4pd/headers/server/PriorityQueue.h')
-rw-r--r-- | sc4pd/headers/server/PriorityQueue.h | 123 |
1 files changed, 123 insertions, 0 deletions
diff --git a/sc4pd/headers/server/PriorityQueue.h b/sc4pd/headers/server/PriorityQueue.h new file mode 100644 index 0000000..eb1064f --- /dev/null +++ b/sc4pd/headers/server/PriorityQueue.h @@ -0,0 +1,123 @@ +/* + SuperCollider real time audio synthesis system + Copyright (c) 2002 James McCartney. All rights reserved. + http://www.audiosynth.com + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ + +#ifndef _PriorityQueue_ +#define _PriorityQueue_ + +#include <stdio.h> +#include <math.h> +#include <stdexcept> + +#define SANITYCHECK 0 + +#ifdef SC_WIN32 +const int64 kMaxInt64 = 0x7FFFFFFFFFFFFFFF; +#else +const int64 kMaxInt64 = ~(1LL<<63); +#endif + +template <class Event, int N> +class PriorityQueueT +{ +public: + PriorityQueueT() { + Empty(); + } + + bool Add(Event& inEvent) + { + if (mSize >= N) return false; + long mom = mSize++; + long me = mom; + for (; mom>0;) { /* percolate up heap */ + mom = mom - 1 >> 1; + if (inEvent.mTime < mEvents[mom].mTime) { + mEvents[me] = mEvents[mom]; + me = mom; + } else break; + } + mEvents[me] = inEvent; +#if SANITYCHECK + SanityCheck(); +#endif + return true; + } + void Perform(int64 inTime) + { + while (NextTime() <= inTime) { + Event event = Remove(); + event.Perform(); + } + } + int64 NextTime() { return mEvents[0].mTime; } + bool Ready(int64 inTime) { return NextTime() <= inTime; } + void Flush() { Perform(kMaxInt64); } + void Empty() { mSize = 0; SetEmptyTime(); } + void SetEmptyTime() { mEvents[0].mTime = kMaxInt64; } + int Size() { return mSize; } + + Event Remove() + { + Event event = mEvents[0]; + if (--mSize == 0) SetEmptyTime(); + else { + Event temp = mEvents[mSize]; + long mom = 0; + long me = 1; + for (;me < mSize;) { /* demote heap */ + if (me+1 < mSize && mEvents[me].mTime > mEvents[me+1].mTime) { + me ++; + } + if (temp.mTime > mEvents[me].mTime) { + mEvents[mom] = mEvents[me]; + mom = me; + me = (me << 1) + 1; + } else break; + } + mEvents[mom] = temp; + } +#if SANITYCHECK + SanityCheck(); +#endif + return event; + } + void SanityCheck() + { + for (int i=0; i<mSize; ++i) + { + int j = (i<<1)+1; + int k = j+1; + //if (j<mSize && mEvents[i].mTime > mEvents[j].mTime) throw std::runtime_error("priority queue unsorted"); + //if (k<mSize && mEvents[i].mTime > mEvents[k].mTime) throw std::runtime_error("priority queue unsorted"); + } + } + void DebugDump() + { + for (int i=0; i<mSize; ++i) + { + printf("%d %016llX\n", i, mEvents[i].mTime); + } + } +private: + int mSize; + Event mEvents[N]; +}; + +#endif |