aboutsummaryrefslogtreecommitdiff
path: root/src/heap.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2008-02-19 09:24:27 +0000
committerMike Buland <eichlan@xagasoft.com>2008-02-19 09:24:27 +0000
commite2a10c7b77b03bacf4d8b8dcf08f8f8f47628314 (patch)
tree5745237cd2a340a6a69dc34596ba87c9ba403c84 /src/heap.h
parent8bbe1d4a61288a2998fbae05ac61ef50a8cfc4e6 (diff)
downloadlibbu++-e2a10c7b77b03bacf4d8b8dcf08f8f8f47628314.tar.gz
libbu++-e2a10c7b77b03bacf4d8b8dcf08f8f8f47628314.tar.bz2
libbu++-e2a10c7b77b03bacf4d8b8dcf08f8f8f47628314.tar.xz
libbu++-e2a10c7b77b03bacf4d8b8dcf08f8f8f47628314.zip
Bu::Heap is a real class, it works great, except it doesn't grow right now.
I'm thinking the heap should add one layer to the binary tree each time it grows, which means double+1 each time. The Bu::ItoHeap will be implemented as soon as the rest of Bu::Heap is done. Also, I finally added bu/util.h which is mainly handy template functions like Bu::swap, Bu::min, Bu::max, and Bu::mid. A few more may be added.
Diffstat (limited to 'src/heap.h')
-rw-r--r--src/heap.h134
1 files changed, 134 insertions, 0 deletions
diff --git a/src/heap.h b/src/heap.h
new file mode 100644
index 0000000..0ca4422
--- /dev/null
+++ b/src/heap.h
@@ -0,0 +1,134 @@
1/*
2 * Copyright (C) 2007-2008 Xagasoft, All rights reserved.
3 *
4 * This file is part of the libbu++ library and is released under the
5 * terms of the license contained in the file LICENSE.
6 */
7
8#ifndef BU_HEAP_H
9#define BU_HEAP_H
10
11#include <stddef.h>
12#include <string.h>
13#include <memory>
14#include <iostream>
15#include "bu/util.h"
16
17namespace Bu
18{
19 template<typename item>
20 struct __basicLTCmp
21 {
22 bool operator()( const item &a, const item &b )
23 {
24 return a <= b;
25 }
26 };
27
28 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
29 class Heap
30 {
31 public:
32 Heap() :
33 iSize( 40 ),
34 iFill( 0 ),
35 aItem( new item[iSize] )
36 {
37 }
38
39 virtual ~Heap()
40 {
41 delete[] aItem;
42 aItem = NULL;
43 }
44
45 void push( item i )
46 {
47 for( int j = 0; j < iFill; )
48 {
49 if( cmp( i, aItem[j] ) )
50 {
51 swap( i, aItem[j] );
52 }
53
54 if( cmp( i, aItem[j*2+1] ) )
55 {
56 j = j*2+1;
57 }
58 else
59 {
60 j = j*2+2;
61 }
62 }
63 aItem[iFill] = i;
64 for( int j = iFill; j >= 0; )
65 {
66 int k = (j-1)/2;
67 if( cmp( aItem[k], aItem[j] ) )
68 break;
69
70 swap( aItem[k], aItem[j] );
71 j = k;
72 }
73 iFill++;
74 }
75
76 item &peek()
77 {
78 return aItem[0];
79 }
80
81 void pop()
82 {
83 int j;
84 for( j = 0; j < iFill; )
85 {
86 if( cmp( aItem[j*2+2], aItem[j*2+1] ) && j*2+2 < iFill )
87 {
88 aItem[j] = aItem[j*2+2];
89 j = j*2+2;
90 }
91 else if( j*2+1 < iFill )
92 {
93 aItem[j] = aItem[j*2+1];
94 j = j*2+1;
95 }
96 else
97 break;
98 }
99 aItem[j] = aItem[iFill-1];
100 iFill--;
101 }
102
103 void print()
104 {
105 printf("graph G {\n");
106 for( int j = 0; j < iFill; j++ )
107 {
108 if( j*2+1 < iFill )
109 printf(" %d -- %d;\n",
110 j, j*2+1
111 );
112 if( j*2+2 < iFill )
113 printf(" %d -- %d;\n",
114 j, j*2+2
115 );
116 }
117 for( int j = 0; j < iFill; j++ )
118 {
119 printf(" %d [label=\"%d\"];\n",
120 j, aItem[j]
121 );
122 }
123 printf("}\n");
124 }
125
126 private:
127 int iSize;
128 int iFill;
129 item *aItem;
130 cmpfunc cmp;
131 };
132};
133
134#endif