aboutsummaryrefslogtreecommitdiff
path: root/src/heap.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2009-11-12 17:05:30 +0000
committerMike Buland <eichlan@xagasoft.com>2009-11-12 17:05:30 +0000
commit509d136e9adb60c56369565b9545e613cac3678e (patch)
treef118d676edeae2d5e17f48b32b180d4761b60520 /src/heap.h
parent3166bd631a093f42ea44a4b0f4d914cf51518bd4 (diff)
downloadlibbu++-509d136e9adb60c56369565b9545e613cac3678e.tar.gz
libbu++-509d136e9adb60c56369565b9545e613cac3678e.tar.bz2
libbu++-509d136e9adb60c56369565b9545e613cac3678e.tar.xz
libbu++-509d136e9adb60c56369565b9545e613cac3678e.zip
I've started my campaign to clean up all of the header files in libbu++ as far
as includes go. This required a little bit of reworking as far as archive goes, but I've been planning on changing it aronud for a bit anyway. The final result here is that you may need to add some more includes in your own code, libbu++ doesn't include as many random things you didn't ask for anymore, most of these seem to be bu/hash.h, unistd.h, and time.h. Also, any Archive functions and operators should use ArchiveBase when they can instead of Archive, archivebase.h is a much lighterweight include that will be used everywhere in core that it can be, there are a few classes that actually want a specific archiver to be used, they will use it (such as the nids storage class). So far, except for adding header files, nothing has changed in functionality, and no other code changes should be required, although the above mentioned archive changeover is reccomended.
Diffstat (limited to '')
-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;