aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2009-11-18 21:22:54 +0000
committerMike Buland <eichlan@xagasoft.com>2009-11-18 21:22:54 +0000
commit92fef73aa43f48e01c5c2e884cfd1e6706a3ce3e (patch)
tree1211ddf7e5d1034e5a981df8231590625a5eb73b /src
parent509d136e9adb60c56369565b9545e613cac3678e (diff)
downloadlibbu++-92fef73aa43f48e01c5c2e884cfd1e6706a3ce3e.tar.gz
libbu++-92fef73aa43f48e01c5c2e884cfd1e6706a3ce3e.tar.bz2
libbu++-92fef73aa43f48e01c5c2e884cfd1e6706a3ce3e.tar.xz
libbu++-92fef73aa43f48e01c5c2e884cfd1e6706a3ce3e.zip
Hey, fixed the problems in heap. It should now work properly no matter what the
data or order etc.
Diffstat (limited to '')
-rw-r--r--src/heap.h42
-rw-r--r--src/queue.h21
-rw-r--r--src/tests/heap.cpp7
-rw-r--r--src/tests/listsort.cpp12
4 files changed, 62 insertions, 20 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:
diff --git a/src/queue.h b/src/queue.h
index 78f6db6..8b5c607 100644
--- a/src/queue.h
+++ b/src/queue.h
@@ -8,14 +8,29 @@
8#ifndef BU_QUEUE_H 8#ifndef BU_QUEUE_H
9#define BU_QUEUE_H 9#define BU_QUEUE_H
10 10
11#include <memory>
12
13namespace Bu 11namespace Bu
14{ 12{
15 template<typename value, typename valuealloc = std::allocator<value> > 13 /**
14 * Queue abstract baseclass
15 */
16 template<typename value>
16 class Queue 17 class Queue
17 { 18 {
18 public: 19 public:
20 Queue()
21 {
22 }
23
24 virtual ~Queue()
25 {
26 }
27
28 virtual void enqueue( const value &i )=0;
29 virtual value dequeue()=0;
30 virtual value &peek()=0;
31 virtual const value &peek() const=0;
32 virtual bool isEmpty() const=0;
33 virtual int getSize() const=0;
19 34
20 private: 35 private:
21 36
diff --git a/src/tests/heap.cpp b/src/tests/heap.cpp
index ae130ec..b1f510a 100644
--- a/src/tests/heap.cpp
+++ b/src/tests/heap.cpp
@@ -38,13 +38,14 @@ typedef struct num
38 } 38 }
39} num; 39} num;
40 40
41void printHeap( Bu::Heap<Bu::FString> &h, int j ) 41void printHeap( Bu::Heap<Bu::FString> &/*h*/, int j )
42{ 42{
43 return;
43 Bu::FString sFName; 44 Bu::FString sFName;
44 sFName.format("graph-step-%02d.dot", j ); 45 sFName.format("graph-step-%02d.dot", j );
45 Bu::File fOut( sFName, Bu::File::WriteNew ); 46 Bu::File fOut( sFName, Bu::File::WriteNew );
46 Bu::Formatter f( Bu::File ); 47 Bu::Formatter f( fOut );
47 //h.print( f ); 48// h.print( f );
48} 49}
49 50
50int main() 51int main()
diff --git a/src/tests/listsort.cpp b/src/tests/listsort.cpp
index f9236e6..09c0273 100644
--- a/src/tests/listsort.cpp
+++ b/src/tests/listsort.cpp
@@ -6,6 +6,18 @@ using namespace Bu;
6 6
7int main() 7int main()
8{ 8{
9 /*
10 List<int> il;
11 il.append( 5 );
12 il.append( 12 );
13 il.append( 0 );
14 il.append( 7 );
15 il.append( 3 );
16 il.append( 5 );
17 Bu::__basicLTCmp<int> cmp;
18 il.sortI( cmp );
19 */
20
9 FString a("Soggy"), b("Sam"); 21 FString a("Soggy"), b("Sam");
10 22
11 if( a < b ) 23 if( a < b )