From e2a10c7b77b03bacf4d8b8dcf08f8f8f47628314 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Tue, 19 Feb 2008 09:24:27 +0000 Subject: 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. --- src/heap.cpp | 9 ++++ src/heap.h | 134 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/itoheap.cpp | 0 src/itoheap.h | 0 src/tests/heap.cpp | 29 ++++++++++++ src/util.h | 40 ++++++++++++++++ 6 files changed, 212 insertions(+) create mode 100644 src/heap.cpp create mode 100644 src/heap.h create mode 100644 src/itoheap.cpp create mode 100644 src/itoheap.h create mode 100644 src/tests/heap.cpp create mode 100644 src/util.h (limited to 'src') 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 @@ +/* + * Copyright (C) 2007-2008 Xagasoft, All rights reserved. + * + * This file is part of the libbu++ library and is released under the + * terms of the license contained in the file LICENSE. + */ + +#include "heap.h" + 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 @@ +/* + * Copyright (C) 2007-2008 Xagasoft, All rights reserved. + * + * This file is part of the libbu++ library and is released under the + * terms of the license contained in the file LICENSE. + */ + +#ifndef BU_HEAP_H +#define BU_HEAP_H + +#include +#include +#include +#include +#include "bu/util.h" + +namespace Bu +{ + template + struct __basicLTCmp + { + bool operator()( const item &a, const item &b ) + { + return a <= b; + } + }; + + template, typename itemalloc=std::allocator > + class Heap + { + public: + Heap() : + iSize( 40 ), + iFill( 0 ), + aItem( new item[iSize] ) + { + } + + virtual ~Heap() + { + delete[] aItem; + aItem = NULL; + } + + void push( item i ) + { + for( int j = 0; j < iFill; ) + { + if( cmp( i, aItem[j] ) ) + { + swap( i, aItem[j] ); + } + + if( cmp( i, aItem[j*2+1] ) ) + { + j = j*2+1; + } + else + { + j = j*2+2; + } + } + aItem[iFill] = i; + for( int j = iFill; j >= 0; ) + { + int k = (j-1)/2; + if( cmp( aItem[k], aItem[j] ) ) + break; + + swap( aItem[k], aItem[j] ); + j = k; + } + iFill++; + } + + item &peek() + { + return aItem[0]; + } + + void pop() + { + int j; + for( j = 0; j < iFill; ) + { + if( cmp( aItem[j*2+2], aItem[j*2+1] ) && j*2+2 < iFill ) + { + aItem[j] = aItem[j*2+2]; + j = j*2+2; + } + else if( j*2+1 < iFill ) + { + aItem[j] = aItem[j*2+1]; + j = j*2+1; + } + else + break; + } + aItem[j] = aItem[iFill-1]; + iFill--; + } + + void print() + { + printf("graph G {\n"); + for( int j = 0; j < iFill; j++ ) + { + if( j*2+1 < iFill ) + printf(" %d -- %d;\n", + j, j*2+1 + ); + if( j*2+2 < iFill ) + printf(" %d -- %d;\n", + j, j*2+2 + ); + } + for( int j = 0; j < iFill; j++ ) + { + printf(" %d [label=\"%d\"];\n", + j, aItem[j] + ); + } + printf("}\n"); + } + + private: + int iSize; + int iFill; + item *aItem; + cmpfunc cmp; + }; +}; + +#endif diff --git a/src/itoheap.cpp b/src/itoheap.cpp new file mode 100644 index 0000000..e69de29 diff --git a/src/itoheap.h b/src/itoheap.h new file mode 100644 index 0000000..e69de29 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 @@ +#include +#include + +#include "bu/heap.h" + +int main() +{ + Bu::Heap hInt; + + for( int j = 0; j < 15; j++ ) + { + int r = rand()%10; + printf("Pushing: %d, top: ", r ); + hInt.push( r ); + printf("%d\n", hInt.peek() ); + } + + for( int j = 0; j < 15; j++ ) + { + printf("%d ", hInt.peek() ); + hInt.pop(); + } + printf("\n"); + +// hInt.print(); + + return 0; +} + 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 @@ +/* + * Copyright (C) 2007-2008 Xagasoft, All rights reserved. + * + * This file is part of the libbu++ library and is released under the + * terms of the license contained in the file LICENSE. + */ + +#ifndef BU_UTIL_H +#define BU_UTIL_H + +namespace Bu +{ + template + void swap( item &a, item &b ) + { + item tmp = a; + a = b; + b = tmp; + } + + template + item &min( item &a, item &b ) + { + return a + item &max( item &a, item &b ) + { + return a>b?a:b; + } + + template + item &mid( item &a, item &b, item &c ) + { + return min( max( a, b ), c ); + } +}; + +#endif -- cgit v1.2.3