aboutsummaryrefslogtreecommitdiff
path: root/src/heap.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2008-02-19 21:51:48 +0000
committerMike Buland <eichlan@xagasoft.com>2008-02-19 21:51:48 +0000
commita4c22303b1044eee5ccbf0766895a879a8f4810e (patch)
treebe6563dfca81f57e4883a55c4517f5878c40dd4e /src/heap.h
parent62287ea894a1587553f017d0f6a09d4c87ad3b1f (diff)
downloadlibbu++-a4c22303b1044eee5ccbf0766895a879a8f4810e.tar.gz
libbu++-a4c22303b1044eee5ccbf0766895a879a8f4810e.tar.bz2
libbu++-a4c22303b1044eee5ccbf0766895a879a8f4810e.tar.xz
libbu++-a4c22303b1044eee5ccbf0766895a879a8f4810e.zip
Oops. I made the Bu::Heap API look like a stack, not a queue, that's been
fixed, and the Bu::ItoHeap is working and tested. Note that when multiple items have the same sort order, they will come out in random order.
Diffstat (limited to 'src/heap.h')
-rw-r--r--src/heap.h40
1 files changed, 28 insertions, 12 deletions
diff --git a/src/heap.h b/src/heap.h
index f276157..dd2764f 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -24,7 +24,7 @@ namespace Bu
24 { 24 {
25 bool operator()( const item &a, const item &b ) 25 bool operator()( const item &a, const item &b )
26 { 26 {
27 return a <= b; 27 return a < b;
28 } 28 }
29 }; 29 };
30 30
@@ -33,7 +33,7 @@ namespace Bu
33 { 33 {
34 bool operator()( const item &a, const item &b ) 34 bool operator()( const item &a, const item &b )
35 { 35 {
36 return a >= b; 36 return a > b;
37 } 37 }
38 }; 38 };
39 39
@@ -42,7 +42,7 @@ namespace Bu
42 { 42 {
43 bool operator()( const item &a, const item &b ) 43 bool operator()( const item &a, const item &b )
44 { 44 {
45 return *a <= *b; 45 return *a < *b;
46 } 46 }
47 }; 47 };
48 48
@@ -51,7 +51,7 @@ namespace Bu
51 { 51 {
52 bool operator()( const item &a, const item &b ) 52 bool operator()( const item &a, const item &b )
53 { 53 {
54 return *a >= *b; 54 return *a > *b;
55 } 55 }
56 }; 56 };
57 57
@@ -74,7 +74,7 @@ namespace Bu
74 aItem = NULL; 74 aItem = NULL;
75 } 75 }
76 76
77 void push( item i ) 77 void enqueue( item i )
78 { 78 {
79 if( iFill+1 >= iSize ) 79 if( iFill+1 >= iSize )
80 upSize(); 80 upSize();
@@ -96,14 +96,17 @@ namespace Bu
96 } 96 }
97 } 97 }
98 ia.construct( &aItem[iFill], i ); 98 ia.construct( &aItem[iFill], i );
99 for( int j = iFill; j >= 0; ) 99 if( iFill > 0 )
100 { 100 {
101 int k = (j-1)/2; 101 for( int j = iFill; j >= 0; )
102 if( cmp( aItem[k], aItem[j] ) ) 102 {
103 break; 103 int k = (j-1)/2;
104 if( cmp( aItem[k], aItem[j] ) )
105 break;
104 106
105 swap( aItem[k], aItem[j] ); 107 swap( aItem[k], aItem[j] );
106 j = k; 108 j = k;
109 }
107 } 110 }
108 iFill++; 111 iFill++;
109 } 112 }
@@ -115,10 +118,11 @@ namespace Bu
115 return aItem[0]; 118 return aItem[0];
116 } 119 }
117 120
118 void pop() 121 item dequeue()
119 { 122 {
120 if( iFill == 0 ) 123 if( iFill == 0 )
121 throw HeapException("Heap empty."); 124 throw HeapException("Heap empty.");
125 item iRet = aItem[0];
122 int j; 126 int j;
123 for( j = 0; j < iFill; ) 127 for( j = 0; j < iFill; )
124 { 128 {
@@ -138,6 +142,18 @@ namespace Bu
138 aItem[j] = aItem[iFill-1]; 142 aItem[j] = aItem[iFill-1];
139 ia.destroy( &aItem[iFill-1] ); 143 ia.destroy( &aItem[iFill-1] );
140 iFill--; 144 iFill--;
145
146 return iRet;
147 }
148
149 bool isEmpty()
150 {
151 return (iFill==0);
152 }
153
154 int getSize()
155 {
156 return iFill;
141 } 157 }
142 158
143 void print() 159 void print()