1 /*
2
3 *************************************************************************
4
5 ArmageTron -- Just another Tron Lightcycle Game in 3D.
6 Copyright (C) 2000 Manuel Moos (manuel@moosnet.de)
7
8 **************************************************************************
9
10 This program is free software; you can redistribute it and/or
11 modify it under the terms of the GNU General Public License
12 as published by the Free Software Foundation; either version 2
13 of the License, or (at your option) any later version.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
23
24 ***************************************************************************
25
26 */
27
28 #ifndef ArmageTron_HEAP_H
29 #define ArmageTron_HEAP_H
30
31 #include "tList.h"
32 #include "defs.h"
33
34 /*
35 Heap data structure
36 */
37
38 #ifdef DEBUG_EXPENSIVE
39 #define EVENT_DEB
40 #endif
41
42 // #define HEAP_DEB
43
44 class tHeapElement;
45
46 class tHeapBase:private tList<tHeapElement>{
47 friend class tHeapElement;
48 protected:
Lower(int i)49 int Lower(int i){ // the element below i in the heap
50 if(i%2==0) // just to make sure what happens; you never know what 1/2 is..
51 return i/2-1;
52 else
53 return (i-1)/2;
54 }
55
Len()56 int Len()const { return tList<tHeapElement>::Len(); }
operator()57 tHeapElement* operator()( int i ) { return const_cast< tHeapElement* >( tList<tHeapElement>::operator()(i) ); }
operator()58 const tHeapElement* operator()( int i )const { return tList<tHeapElement>::operator()(i); }
59
60 bool SwapIf(int i,int j); // swaps heap elements i and j if they are
61 // in wrong order; only then, TRUE is returned.
62 // i is assumed to lie lower in the heap than j.
63
64 void SwapDown(int j); // swap element j as far down as it may go.
65 void SwapUp(int i); // swap element j as far up as it must.
66
67 //#ifdef EVENT_DEB
68 void CheckHeap(); // checks the heap structure
69 //#endif
70
71 void Insert(tHeapElement *e); // starts to manage object e
72 void Remove(tHeapElement *e); // stops (does not delete e)
73 tHeapElement * Remove(int i); // stops to manage object i, wich is returned.
74 void Replace(int i); // puts element i to the right place (if the
75 // rest of the heap has correct order)
76 void Replace(tHeapElement *e);
77 public:
UpperL(int i)78 static int UpperL(int i){return 2*i+1;} // the elements left and
UpperR(int i)79 static int UpperR(int i){return 2*i+2;} // right above i
80
tHeapBase()81 tHeapBase(){}
82 ~tHeapBase();
83 };
84
85
86 // the heap elements.
87
88 class tHeapElement{
89 friend class tHeapBase;
90
91 public:
tHeapElement()92 tHeapElement():hID(-1),value_(0){}
93 virtual ~tHeapElement();
94
Val()95 REAL Val() const {return value_;}
96 void SetVal( REAL value, tHeapBase& heap );
97 void RemoveFromHeap();
98
99 protected:
100 virtual tHeapBase *Heap() const = 0; //{return NULL;} // in wich heap are we?
101
102 protected:
103 private:
104 int hID; // the id in the heap
105 REAL value_; // our value. lower values are lower in the heap.
106 };
107
108
109 template<class T> class tHeap: public tHeapBase{
110 public:
tHeap()111 tHeap(){}
~tHeap()112 ~tHeap(){}
113
Insert(T * e)114 void Insert(T *e){tHeapBase::Insert(e);} // starts to manage object e
Remove(T * e)115 void Remove(T *e){tHeapBase::Remove(e);} // stops (does not delete e)
Replace(T * e)116 void Replace(T *e){tHeapBase::Replace(e);}
Remove(int i)117 T * Remove(int i){return static_cast<T*> (tHeapBase::Remove(i));}
118
operator()119 T * operator()(int i){return static_cast< T *>(tHeapBase::operator()(i));}
operator()120 const T * operator()(int i) const {return static_cast<const T *>(tHeapBase::operator()(i));}
Events(int i)121 T * Events(int i){return static_cast<T *>(tHeapBase::operator()(i));}
122
Len()123 int Len() const {return tHeapBase::Len();}
124
125 tHeapBase * operator &(){return this;}
126 };
127
128 #endif
129
130