From 469bbcf0701e1eb8a6670c23145b0da87357e178 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Sun, 25 Mar 2012 20:00:08 +0000 Subject: Code is all reorganized. We're about ready to release. I should write up a little explenation of the arrangement. --- src/heap.h | 612 ------------------------------------------------------------- 1 file changed, 612 deletions(-) delete mode 100644 src/heap.h (limited to 'src/heap.h') diff --git a/src/heap.h b/src/heap.h deleted file mode 100644 index afe8be6..0000000 --- a/src/heap.h +++ /dev/null @@ -1,612 +0,0 @@ -/* - * Copyright (C) 2007-2011 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 "bu/exceptionbase.h" -#include "bu/util.h" -#include "bu/queue.h" -#include "bu/sharedcore.h" - -namespace Bu -{ - subExceptionDecl( HeapException ); - - template - class Heap; - - /** @cond DEVEL */ - template - class HeapCore - { - friend class Heap; - friend class SharedCore< - Heap, HeapCore - >; - private: - HeapCore() : - iSize( 0 ), - iFill( 0 ), - aItem( NULL ) - { - } - - virtual ~HeapCore() - { - clear(); - } - - void init() - { - if( iSize > 0 ) - return; - - iSize = 7; - iFill = 0; - aItem = ia.allocate( iSize ); - } - - void init( int iCap ) - { - if( iSize > 0 ) - return; - - for( iSize = 1; iSize < iCap; iSize=iSize*2+1 ) { } - iFill = 0; - aItem = ia.allocate( iSize ); - } - - void clear() - { - if( iSize == 0 ) - return; - - for( int j = 0; j < iFill; j++ ) - ia.destroy( &aItem[j] ); - ia.deallocate( aItem, iSize ); - aItem = NULL; - iSize = 0; - iFill = 0; - } - - void upSize() - { - if( iSize == 0 ) - { - init(); - return; - } - - item *aNewItems = ia.allocate( iSize*2+1 ); - // - // We cannot use a memcopy here because we don't know what kind - // of datastructures are being used, we have to copy them one at - // a time. - // - for( int j = 0; j < iFill; j++ ) - { - ia.construct( &aNewItems[j], aItem[j] ); - ia.destroy( &aItem[j] ); - } - ia.deallocate( aItem, iSize ); - aItem = aNewItems; - iSize = iSize*2+1; - } - - virtual void enqueue( const item &it ) - { - item i = it; // TODO: This is a silly workaround, put the i item - // at the end. - if( iFill+1 >= iSize ) - upSize(); - - for( int j = 0; j < iFill; ) - { - if( cmp( i, aItem[j] ) ) - { - Bu::swap( i, aItem[j] ); - } - - if( j*2+1 >= iFill ) - break; - if( cmp( i, aItem[j*2+1] ) ) - { - j = j*2+1; - } - else - { - j = j*2+2; - } - } - ia.construct( &aItem[iFill], i ); - if( iFill > 0 ) - { - for( int j = iFill; j >= 0; ) - { - int k = (j-1)/2; - if( j == k ) - break; - if( cmp( aItem[k], aItem[j] ) ) - break; - - Bu::swap( aItem[k], aItem[j] ); - j = k; - } - } - iFill++; - } - - virtual item dequeue() - { - if( iFill == 0 ) - throw HeapException("Heap empty."); - item iRet = aItem[0]; - int j; - for( j = 0; j < iFill; ) - { - int k = j*2+1; - if( k+1 < iFill && cmp( aItem[k+1], aItem[k] ) ) - { - if( k+1 < iFill-1 && cmp( aItem[iFill-1], aItem[k+1] ) ) - break; - aItem[j] = aItem[k+1]; - j = k+1; - } - else if( k < iFill ) - { - if( k < iFill-1 && cmp( aItem[iFill-1], aItem[k] ) ) - break; - aItem[j] = aItem[k]; - j = k; - } - else - break; - } - if( j < iFill-1 ) - aItem[j] = aItem[iFill-1]; - ia.destroy( &aItem[iFill-1] ); - iFill--; - - return iRet; - } - - private: - int iSize; - int iFill; - item *aItem; - cmpfunc cmp; - itemalloc ia; - }; - /** @endcond */ - - /** - * A priority queue that allows for an unlimited number of priorities. All - * objects enqueued must support less-than-comparison. Then every time an - * item is dequeued it is always the least item in the heap. The heap - * operates using a binary tree for storage, which allows most operations - * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins - * whereas peeking is constant time. - * - * This heap implementation allows iterating, however please note that any - * enqueue or dequeue operation will invalidate the iterator and make it - * unusable (if it still works, you shouldn't trust the results). Also, - * the items are not stored in memory in order, they are optomized into a - * tree. This means that the items will be in effectively random order - * while iterating through them, and the order cannot be trusted. Also, - * modifying an item in the heap will not cause that item to be re-sorted. - * If you want to change the position of an item in the heap you will have - * to dequeue every item before it, dequeue that item, change it, and - * re-enqueue all of the items removed. - */ - template, typename itemalloc=std::allocator > - class Heap : public Queue, public SharedCore< - Heap, - HeapCore - > - { - private: - typedef class Heap MyType; - typedef class HeapCore Core; - - protected: - using SharedCore::core; - using SharedCore::_hardCopy; - using SharedCore::_resetCore; - using SharedCore::_allocateCore; - - public: - Heap() - { - } - - Heap( cmpfunc cmpin ) - { - core->cmp = cmpin; - } - - Heap( int iInitialCapacity ) - { - core->init( iInitialCapacity ); - } - - Heap( cmpfunc cmpin, int iInitialCapacity ) - { - core->cmp = cmpin; - core->init( iInitialCapacity ); - } - - Heap( const MyType &rSrc ) : - SharedCore( rSrc ) - { - } - - virtual ~Heap() - { - } - - virtual void enqueue( const item &it ) - { - _hardCopy(); - - core->enqueue( it ); - } - - virtual item &peek() - { - _hardCopy(); - - if( core->iFill == 0 ) - throw HeapException("Heap empty."); - return core->aItem[0]; - } - - virtual const item &peek() const - { - if( core->iFill == 0 ) - throw HeapException("Heap empty."); - return core->aItem[0]; - } - - virtual item dequeue() - { - _hardCopy(); - - return core->dequeue(); - } - - virtual bool isEmpty() const - { - return (core->iFill==0); - } - - virtual int getSize() const - { - return core->iFill; - } - - class iterator - { - friend class const_iterator; - friend class Heap; - private: - Heap *pHeap; - int iIndex; - - iterator( Heap *pHeap, int iIndex ) : - pHeap( pHeap ), iIndex( iIndex ) - { - } - - void checkValid() - { - if( pHeap == NULL ) - throw Bu::ExceptionBase("Iterator not initialized."); - if( iIndex < 0 || iIndex >= pHeap->core->iFill ) - throw Bu::ExceptionBase("Iterator out of bounds."); - } - - public: - iterator() : - pHeap( NULL ), - iIndex( -1 ) - { - } - - iterator( const iterator &i ) : - pHeap( i.pHeap ), - iIndex( i.iIndex ) - { - } - - bool operator==( const iterator &oth ) const - { - return (oth.pHeap == pHeap) && (oth.iIndex == iIndex); - } - - bool operator!=( const iterator &oth ) const - { - return (oth.pHeap != pHeap) || (oth.iIndex != iIndex); - } - - item &operator*() - { - pHeap->_hardCopy(); - - return pHeap->core->aItem[iIndex]; - } - - item *operator->() - { - pHeap->_hardCopy(); - - return &(pHeap->core->aItem[iIndex]); - } - - iterator &operator++() - { - checkValid(); - iIndex++; - if( iIndex >= pHeap->iFill ) - iIndex = -1; - - return *this; - } - - iterator &operator--() - { - checkValid(); - iIndex--; - - return *this; - } - - iterator &operator++( int ) - { - checkValid(); - iIndex++; - if( iIndex >= pHeap->core->iFill ) - iIndex = -1; - - return *this; - } - - iterator &operator--( int ) - { - checkValid(); - iIndex--; - - return *this; - } - - iterator operator+( int iDelta ) - { - checkValid(); - iterator ret( *this ); - ret.iIndex += iDelta; - if( ret.iIndex >= pHeap->core->iFill ) - ret.iIndex = -1; - return ret; - } - - iterator operator-( int iDelta ) - { - checkValid(); - iterator ret( *this ); - ret.iIndex -= iDelta; - if( ret.iIndex < 0 ) - ret.iIndex = -1; - return ret; - } - - operator bool() const - { - return iIndex != -1; - } - - bool isValid() const - { - return iIndex != -1; - } - - iterator &operator=( const iterator &oth ) - { - pHeap = oth.pHeap; - iIndex = oth.iIndex; - } - }; - - class const_iterator - { - friend class Heap; - private: - Heap *pHeap; - int iIndex; - - const_iterator( Heap *pHeap, - int iIndex ) : - pHeap( pHeap ), iIndex( iIndex ) - { - } - - void checkValid() - { - if( pHeap == NULL ) - throw Bu::ExceptionBase("Iterator not initialized."); - if( iIndex < 0 || iIndex >= pHeap->core->iFill ) - throw Bu::ExceptionBase("Iterator out of bounds."); - } - - public: - const_iterator() : - pHeap( NULL ), - iIndex( -1 ) - { - } - - const_iterator( const const_iterator &i ) : - pHeap( i.pHeap ), - iIndex( i.iIndex ) - { - } - - const_iterator( const iterator &i ) : - pHeap( i.pHeap ), - iIndex( i.iIndex ) - { - } - - bool operator==( const const_iterator &oth ) const - { - return (oth.pHeap == pHeap) && (oth.iIndex == iIndex); - } - - bool operator!=( const const_iterator &oth ) const - { - return (oth.pHeap != pHeap) || (oth.iIndex != iIndex); - } - - const item &operator*() - { - pHeap->_hardCopy(); - - return pHeap->core->aItem[iIndex]; - } - - const item *operator->() - { - pHeap->_hardCopy(); - - return &(pHeap->core->aItem[iIndex]); - } - - const_iterator &operator++() - { - checkValid(); - iIndex++; - if( iIndex >= pHeap->core->iFill ) - iIndex = -1; - - return *this; - } - - const_iterator &operator--() - { - checkValid(); - iIndex--; - - return *this; - } - - const_iterator &operator++( int ) - { - checkValid(); - iIndex++; - if( iIndex >= pHeap->core->iFill ) - iIndex = -1; - - return *this; - } - - const_iterator &operator--( int ) - { - checkValid(); - iIndex--; - - return *this; - } - - const_iterator operator+( int iDelta ) - { - checkValid(); - const_iterator ret( *this ); - ret.iIndex += iDelta; - if( ret.iIndex >= pHeap->iFill ) - ret.iIndex = -1; - return ret; - } - - const_iterator operator-( int iDelta ) - { - checkValid(); - const_iterator ret( *this ); - ret.iIndex -= iDelta; - if( ret.iIndex < 0 ) - ret.iIndex = -1; - return ret; - } - - operator bool() const - { - return iIndex != -1; - } - - bool isValid() const - { - return iIndex != -1; - } - - const_iterator &operator=( const const_iterator &oth ) - { - pHeap = oth.pHeap; - iIndex = oth.iIndex; - } - - const_iterator &operator=( const iterator &oth ) - { - pHeap = oth.pHeap; - iIndex = oth.iIndex; - } - }; - - iterator begin() - { - if( core->iFill == 0 ) - return end(); - return iterator( this, 0 ); - } - - const_iterator begin() const - { - if( core->iFill == 0 ) - return end(); - return const_iterator( this, 0 ); - } - - iterator end() - { - return iterator( this, -1 ); - } - - const_iterator end() const - { - return const_iterator( this, -1 ); - } - - - protected: - virtual Core *_copyCore( Core *src ) - { - Core *pRet = _allocateCore(); - - pRet->iSize = src->iSize; - pRet->iFill = src->iFill; - pRet->cmp = src->cmp; - pRet->aItem = pRet->ia.allocate( pRet->iSize ); - for( int j = 0; j < pRet->iFill; j++ ) - { - pRet->ia.construct( &pRet->aItem[j], src->aItem[j] ); - } - - return pRet; - } - }; -}; - -#endif -- cgit v1.2.3