aboutsummaryrefslogtreecommitdiff
path: root/src/heap.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/heap.h42
1 files changed, 28 insertions, 14 deletions
diff --git a/src/heap.h b/src/heap.h
index a8d904c..523c8e2 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -12,14 +12,14 @@
12#include <memory> 12#include <memory>
13#include "bu/exceptionbase.h" 13#include "bu/exceptionbase.h"
14#include "bu/util.h" 14#include "bu/util.h"
15// #include "bu/formatter.h" 15#include "bu/queue.h"
16 16
17namespace Bu 17namespace Bu
18{ 18{
19 subExceptionDecl( HeapException ); 19 subExceptionDecl( HeapException );
20 20
21 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> > 21 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
22 class Heap 22 class Heap : public Queue<item>
23 { 23 {
24 public: 24 public:
25 Heap() : 25 Heap() :
@@ -64,8 +64,10 @@ namespace Bu
64 aItem = NULL; 64 aItem = NULL;
65 } 65 }
66 66
67 void enqueue( item i ) 67 virtual void enqueue( const item &it )
68 { 68 {
69 item i = it; // TODO: This is a silly workaround, put the i item
70 // at the end.
69 if( iFill+1 >= iSize ) 71 if( iFill+1 >= iSize )
70 upSize(); 72 upSize();
71 73
@@ -103,14 +105,21 @@ namespace Bu
103 iFill++; 105 iFill++;
104 } 106 }
105 107
106 item &peek() 108 virtual item &peek()
107 { 109 {
108 if( iFill == 0 ) 110 if( iFill == 0 )
109 throw HeapException("Heap empty."); 111 throw HeapException("Heap empty.");
110 return aItem[0]; 112 return aItem[0];
111 } 113 }
112 114
113 item dequeue() 115 virtual const item &peek() const
116 {
117 if( iFill == 0 )
118 throw HeapException("Heap empty.");
119 return aItem[0];
120 }
121
122 virtual item dequeue()
114 { 123 {
115 if( iFill == 0 ) 124 if( iFill == 0 )
116 throw HeapException("Heap empty."); 125 throw HeapException("Heap empty.");
@@ -121,11 +130,15 @@ namespace Bu
121 int k = j*2+1; 130 int k = j*2+1;
122 if( k+1 < iFill && cmp( aItem[k+1], aItem[k] ) ) 131 if( k+1 < iFill && cmp( aItem[k+1], aItem[k] ) )
123 { 132 {
133 if( k+1 < iFill-1 && cmp( aItem[iFill-1], aItem[k+1] ) )
134 break;
124 aItem[j] = aItem[k+1]; 135 aItem[j] = aItem[k+1];
125 j = k+1; 136 j = k+1;
126 } 137 }
127 else if( k < iFill ) 138 else if( k < iFill )
128 { 139 {
140 if( k < iFill-1 && cmp( aItem[iFill-1], aItem[k] ) )
141 break;
129 aItem[j] = aItem[k]; 142 aItem[j] = aItem[k];
130 j = k; 143 j = k;
131 } 144 }
@@ -140,31 +153,32 @@ namespace Bu
140 return iRet; 153 return iRet;
141 } 154 }
142 155
143 bool isEmpty() 156 virtual bool isEmpty() const
144 { 157 {
145 return (iFill==0); 158 return (iFill==0);
146 } 159 }
147 160
148 int getSize() 161 virtual int getSize() const
149 { 162 {
150 return iFill; 163 return iFill;
151 } 164 }
152/* 165
153 void print( Formatter &f ) 166 /*
167 void print( class Formatter &f )
154 { 168 {
155 f << "graph G {" << f.nl; 169 f << "graph G {" << "\n";
156 for( int j = 0; j < iFill; j++ ) 170 for( int j = 0; j < iFill; j++ )
157 { 171 {
158 if( j*2+1 < iFill ) 172 if( j*2+1 < iFill )
159 f << " " << j << " -- " << j*2+1 << ";" << f.nl; 173 f << " " << j << " -- " << j*2+1 << ";" << "\n";
160 if( j*2+2 < iFill ) 174 if( j*2+2 < iFill )
161 f << " " << j << " -- " << j*2+2 << ";" << f.nl; 175 f << " " << j << " -- " << j*2+2 << ";" << "\n";
162 } 176 }
163 for( int j = 0; j < iFill; j++ ) 177 for( int j = 0; j < iFill; j++ )
164 { 178 {
165 f << " " << j << " [label=\"" << aItem[j] << "\"];" << f.nl; 179 f << " " << j << " [label=\"" << aItem[j] << "\"];" << "\n";
166 } 180 }
167 f << "}" << f.nl; 181 f << "}" << "\n";
168 } */ 182 } */
169 183
170 private: 184 private: