aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/heap.cpp9
-rw-r--r--src/heap.h134
-rw-r--r--src/itoheap.cpp0
-rw-r--r--src/itoheap.h0
-rw-r--r--src/tests/heap.cpp29
-rw-r--r--src/util.h40
6 files changed, 212 insertions, 0 deletions
diff --git a/src/heap.cpp b/src/heap.cpp
new file mode 100644
index 0000000..00a5d5d
--- /dev/null
+++ b/src/heap.cpp
@@ -0,0 +1,9 @@
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#include "heap.h"
9
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
diff --git a/src/itoheap.cpp b/src/itoheap.cpp
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/itoheap.cpp
diff --git a/src/itoheap.h b/src/itoheap.h
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/itoheap.h
diff --git a/src/tests/heap.cpp b/src/tests/heap.cpp
new file mode 100644
index 0000000..e93749f
--- /dev/null
+++ b/src/tests/heap.cpp
@@ -0,0 +1,29 @@
1#include <stdlib.h>
2#include <stdio.h>
3
4#include "bu/heap.h"
5
6int main()
7{
8 Bu::Heap<int> hInt;
9
10 for( int j = 0; j < 15; j++ )
11 {
12 int r = rand()%10;
13 printf("Pushing: %d, top: ", r );
14 hInt.push( r );
15 printf("%d\n", hInt.peek() );
16 }
17
18 for( int j = 0; j < 15; j++ )
19 {
20 printf("%d ", hInt.peek() );
21 hInt.pop();
22 }
23 printf("\n");
24
25// hInt.print();
26
27 return 0;
28}
29
diff --git a/src/util.h b/src/util.h
new file mode 100644
index 0000000..977645c
--- /dev/null
+++ b/src/util.h
@@ -0,0 +1,40 @@
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_UTIL_H
9#define BU_UTIL_H
10
11namespace Bu
12{
13 template<typename item>
14 void swap( item &a, item &b )
15 {
16 item tmp = a;
17 a = b;
18 b = tmp;
19 }
20
21 template<typename item>
22 item &min( item &a, item &b )
23 {
24 return a<b?a:b;
25 }
26
27 template<typename item>
28 item &max( item &a, item &b )
29 {
30 return a>b?a:b;
31 }
32
33 template<typename item>
34 item &mid( item &a, item &b, item &c )
35 {
36 return min( max( a, b ), c );
37 }
38};
39
40#endif