aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/heap.cpp1
-rw-r--r--src/heap.h61
-rw-r--r--src/tests/heap.cpp2
3 files changed, 58 insertions, 6 deletions
diff --git a/src/heap.cpp b/src/heap.cpp
index 00a5d5d..01a5f50 100644
--- a/src/heap.cpp
+++ b/src/heap.cpp
@@ -7,3 +7,4 @@
7 7
8#include "heap.h" 8#include "heap.h"
9 9
10namespace Bu { subExceptionDef( HeapException ) }
diff --git a/src/heap.h b/src/heap.h
index 0ca4422..f276157 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -12,10 +12,13 @@
12#include <string.h> 12#include <string.h>
13#include <memory> 13#include <memory>
14#include <iostream> 14#include <iostream>
15#include "bu/exceptionbase.h"
15#include "bu/util.h" 16#include "bu/util.h"
16 17
17namespace Bu 18namespace Bu
18{ 19{
20 subExceptionDecl( HeapException );
21
19 template<typename item> 22 template<typename item>
20 struct __basicLTCmp 23 struct __basicLTCmp
21 { 24 {
@@ -24,26 +27,58 @@ namespace Bu
24 return a <= b; 27 return a <= b;
25 } 28 }
26 }; 29 };
30
31 template<typename item>
32 struct __basicGTCmp
33 {
34 bool operator()( const item &a, const item &b )
35 {
36 return a >= b;
37 }
38 };
39
40 template<typename item>
41 struct __basicPtrLTCmp
42 {
43 bool operator()( const item &a, const item &b )
44 {
45 return *a <= *b;
46 }
47 };
48
49 template<typename item>
50 struct __basicPtrGTCmp
51 {
52 bool operator()( const item &a, const item &b )
53 {
54 return *a >= *b;
55 }
56 };
27 57
28 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> > 58 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
29 class Heap 59 class Heap
30 { 60 {
31 public: 61 public:
32 Heap() : 62 Heap() :
33 iSize( 40 ), 63 iSize( 7 ),
34 iFill( 0 ), 64 iFill( 0 ),
35 aItem( new item[iSize] ) 65 aItem( ia.allocate( iSize ) )
36 { 66 {
37 } 67 }
38 68
39 virtual ~Heap() 69 virtual ~Heap()
40 { 70 {
41 delete[] aItem; 71 for( int j = 0; j < iFill; j++ )
72 ia.destroy( &aItem[j] );
73 ia.deallocate( aItem, iSize );
42 aItem = NULL; 74 aItem = NULL;
43 } 75 }
44 76
45 void push( item i ) 77 void push( item i )
46 { 78 {
79 if( iFill+1 >= iSize )
80 upSize();
81
47 for( int j = 0; j < iFill; ) 82 for( int j = 0; j < iFill; )
48 { 83 {
49 if( cmp( i, aItem[j] ) ) 84 if( cmp( i, aItem[j] ) )
@@ -60,7 +95,7 @@ namespace Bu
60 j = j*2+2; 95 j = j*2+2;
61 } 96 }
62 } 97 }
63 aItem[iFill] = i; 98 ia.construct( &aItem[iFill], i );
64 for( int j = iFill; j >= 0; ) 99 for( int j = iFill; j >= 0; )
65 { 100 {
66 int k = (j-1)/2; 101 int k = (j-1)/2;
@@ -75,11 +110,15 @@ namespace Bu
75 110
76 item &peek() 111 item &peek()
77 { 112 {
113 if( iFill == 0 )
114 throw HeapException("Heap empty.");
78 return aItem[0]; 115 return aItem[0];
79 } 116 }
80 117
81 void pop() 118 void pop()
82 { 119 {
120 if( iFill == 0 )
121 throw HeapException("Heap empty.");
83 int j; 122 int j;
84 for( j = 0; j < iFill; ) 123 for( j = 0; j < iFill; )
85 { 124 {
@@ -97,6 +136,7 @@ namespace Bu
97 break; 136 break;
98 } 137 }
99 aItem[j] = aItem[iFill-1]; 138 aItem[j] = aItem[iFill-1];
139 ia.destroy( &aItem[iFill-1] );
100 iFill--; 140 iFill--;
101 } 141 }
102 142
@@ -121,13 +161,24 @@ namespace Bu
121 ); 161 );
122 } 162 }
123 printf("}\n"); 163 printf("}\n");
124 } 164 }
165
166 private:
167 void upSize()
168 {
169 item *aNewItems = ia.allocate( iSize*2+1 );
170 memcpy( aNewItems, aItem, sizeof(item)*iFill );
171 ia.deallocate( aItem, iSize );
172 aItem = aNewItems;
173 iSize = iSize*2+1;
174 }
125 175
126 private: 176 private:
127 int iSize; 177 int iSize;
128 int iFill; 178 int iFill;
129 item *aItem; 179 item *aItem;
130 cmpfunc cmp; 180 cmpfunc cmp;
181 itemalloc ia;
131 }; 182 };
132}; 183};
133 184
diff --git a/src/tests/heap.cpp b/src/tests/heap.cpp
index e93749f..3217715 100644
--- a/src/tests/heap.cpp
+++ b/src/tests/heap.cpp
@@ -5,7 +5,7 @@
5 5
6int main() 6int main()
7{ 7{
8 Bu::Heap<int> hInt; 8 Bu::Heap<int, Bu::__basicGTCmp<int> > hInt;
9 9
10 for( int j = 0; j < 15; j++ ) 10 for( int j = 0; j < 15; j++ )
11 { 11 {