summaryrefslogtreecommitdiff
path: root/src/heap.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/heap.h')
-rw-r--r--src/heap.h81
1 files changed, 55 insertions, 26 deletions
diff --git a/src/heap.h b/src/heap.h
index 2741818..a8d904c 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -9,11 +9,10 @@
9#define BU_HEAP_H 9#define BU_HEAP_H
10 10
11#include <stddef.h> 11#include <stddef.h>
12#include <string.h>
13#include <memory> 12#include <memory>
14#include <iostream>
15#include "bu/exceptionbase.h" 13#include "bu/exceptionbase.h"
16#include "bu/util.h" 14#include "bu/util.h"
15// #include "bu/formatter.h"
17 16
18namespace Bu 17namespace Bu
19{ 18{
@@ -29,6 +28,33 @@ namespace Bu
29 aItem( ia.allocate( iSize ) ) 28 aItem( ia.allocate( iSize ) )
30 { 29 {
31 } 30 }
31
32 Heap( cmpfunc cmpin ) :
33 iSize( 7 ),
34 iFill( 0 ),
35 aItem( ia.allocate( iSize ) ),
36 cmp( cmpin )
37 {
38 }
39
40 Heap( int iInitialCapacity ) :
41 iSize( 0 ),
42 iFill( 0 ),
43 aItem( NULL )
44 {
45 for( iSize = 1; iSize < iInitialCapacity; iSize=iSize*2+1 ) { }
46 aItem = ia.allocate( iSize );
47 }
48
49 Heap( cmpfunc cmpin, int iInitialCapacity ) :
50 iSize( 0 ),
51 iFill( 0 ),
52 aItem( NULL ),
53 cmp( cmpin )
54 {
55 for( iSize = 1; iSize < iInitialCapacity; iSize=iSize*2+1 ) { }
56 aItem = ia.allocate( iSize );
57 }
32 58
33 virtual ~Heap() 59 virtual ~Heap()
34 { 60 {
@@ -47,9 +73,11 @@ namespace Bu
47 { 73 {
48 if( cmp( i, aItem[j] ) ) 74 if( cmp( i, aItem[j] ) )
49 { 75 {
50 swap( i, aItem[j] ); 76 Bu::swap( i, aItem[j] );
51 } 77 }
52 78
79 if( j*2+1 >= iFill )
80 break;
53 if( cmp( i, aItem[j*2+1] ) ) 81 if( cmp( i, aItem[j*2+1] ) )
54 { 82 {
55 j = j*2+1; 83 j = j*2+1;
@@ -68,7 +96,7 @@ namespace Bu
68 if( cmp( aItem[k], aItem[j] ) ) 96 if( cmp( aItem[k], aItem[j] ) )
69 break; 97 break;
70 98
71 swap( aItem[k], aItem[j] ); 99 Bu::swap( aItem[k], aItem[j] );
72 j = k; 100 j = k;
73 } 101 }
74 } 102 }
@@ -90,20 +118,22 @@ namespace Bu
90 int j; 118 int j;
91 for( j = 0; j < iFill; ) 119 for( j = 0; j < iFill; )
92 { 120 {
93 if( cmp( aItem[j*2+2], aItem[j*2+1] ) && j*2+2 < iFill ) 121 int k = j*2+1;
122 if( k+1 < iFill && cmp( aItem[k+1], aItem[k] ) )
94 { 123 {
95 aItem[j] = aItem[j*2+2]; 124 aItem[j] = aItem[k+1];
96 j = j*2+2; 125 j = k+1;
97 } 126 }
98 else if( j*2+1 < iFill ) 127 else if( k < iFill )
99 { 128 {
100 aItem[j] = aItem[j*2+1]; 129 aItem[j] = aItem[k];
101 j = j*2+1; 130 j = k;
102 } 131 }
103 else 132 else
104 break; 133 break;
105 } 134 }
106 aItem[j] = aItem[iFill-1]; 135 if( j < iFill-1 )
136 aItem[j] = aItem[iFill-1];
107 ia.destroy( &aItem[iFill-1] ); 137 ia.destroy( &aItem[iFill-1] );
108 iFill--; 138 iFill--;
109 139
@@ -119,35 +149,34 @@ namespace Bu
119 { 149 {
120 return iFill; 150 return iFill;
121 } 151 }
122 152/*
123 void print() 153 void print( Formatter &f )
124 { 154 {
125 printf("graph G {\n"); 155 f << "graph G {" << f.nl;
126 for( int j = 0; j < iFill; j++ ) 156 for( int j = 0; j < iFill; j++ )
127 { 157 {
128 if( j*2+1 < iFill ) 158 if( j*2+1 < iFill )
129 printf(" %d -- %d;\n", 159 f << " " << j << " -- " << j*2+1 << ";" << f.nl;
130 j, j*2+1
131 );
132 if( j*2+2 < iFill ) 160 if( j*2+2 < iFill )
133 printf(" %d -- %d;\n", 161 f << " " << j << " -- " << j*2+2 << ";" << f.nl;
134 j, j*2+2
135 );
136 } 162 }
137 for( int j = 0; j < iFill; j++ ) 163 for( int j = 0; j < iFill; j++ )
138 { 164 {
139 printf(" %d [label=\"%d\"];\n", 165 f << " " << j << " [label=\"" << aItem[j] << "\"];" << f.nl;
140 j, aItem[j]
141 );
142 } 166 }
143 printf("}\n"); 167 f << "}" << f.nl;
144 } 168 } */
145 169
146 private: 170 private:
147 void upSize() 171 void upSize()
148 { 172 {
149 item *aNewItems = ia.allocate( iSize*2+1 ); 173 item *aNewItems = ia.allocate( iSize*2+1 );
150 memcpy( aNewItems, aItem, sizeof(item)*iFill ); 174// memcpy( aNewItems, aItem, sizeof(item)*iFill );
175 for( int j = 0; j < iFill; j++ )
176 {
177 ia.construct( &aNewItems[j], aItem[j] );
178 ia.destroy( &aItem[j] );
179 }
151 ia.deallocate( aItem, iSize ); 180 ia.deallocate( aItem, iSize );
152 aItem = aNewItems; 181 aItem = aNewItems;
153 iSize = iSize*2+1; 182 iSize = iSize*2+1;