/**********************************************************************/ /** Microsoft LAN Manager **/ /** Copyright(c) Microsoft Corp., 1991 **/ /**********************************************************************/ /* aheap.hxx HEAP_BASE declaration and heap subclass macro definitions FILE HISTORY: rustanl 05-Jul-1991 Created rustanl 15-Jul-1991 Code review changes (no functional changes). CR attended by BenG, ChuckC, JimH, Hui-LiCh, TerryK, RustanL. */ #ifndef _AHEAP_HXX_ #define _AHEAP_HXX_ #include "uibuffer.hxx" /************************************************************************* NAME: HEAP_BASE SYNOPSIS: Heap data structure base class INTERFACE: HEAP_BASE() - Constructor ~HEAP_BASE() - Destructor QueryCount() - Returns the number of items in the heap SetAllocCount() - Resizes the heap to be able to hold some given number of items Trim() - Trims the heap to only keep enough space for the current heap items. Interface of the derived subclasses: AddItem() - Adds an item to the heap. If heap is in auto-readjust mode, the heap will automatically be readjusted; otherwise, it will not. RemoveTopItem() - Removes the top item, returns it, and readjusts the heap. Method is only valid when the heap is non-empty and is in the auto-readjusting mode. PeekTopItem() - Returns the top item of the heap without removing it. Does not alter the heap. Method is only valid when the heap is non-empty and is in the auto-readjusting mode. Adjust() - Puts the heap in auto-readjust mode, and adjusts the heap. PARENT: BASE USES: BUFFER NOTES: The top item in the heap is the smallest one according to the subclass-defined Compare method. Compare takes a pointer to another item of the same class, and returns < 0 if *this < *pThat 0 if *this = *pThat > 1 if *this > *pThat AddItem requires O(1) time when not in auto-readjust mode, and O(log n) time in auto-readjust mode (where n is the number of items in the heap) RemoveTopItem requires O(log n) time. Adjust runs in O(n) time. Hence, if all items are known at the time the heap is constructed, the fastest way to initialize the heap is to start not in the auto-readjusting mode, then call AddItem for each item, and finally call Adjust. HISTORY: rustanl 05-Jul-1991 Created **************************************************************************/ DLL_CLASS HEAP_BASE : public BASE { private: int _cItems; BOOL _fAutoReadjust; BUFFER _buf; protected: HEAP_BASE( int cInitialAllocCount = 0, BOOL fAutoReadjust = TRUE ); ~HEAP_BASE(); APIERR I_AddItem( VOID * pv ); void * I_RemoveTopItem( void ); void * PeekItem( int i ) const; void SetItem( int i, void * pv ); /* The following inline methods are used by subclasses * to enhance readability. Note, it is up to the caller to make * sure the item queried for exists before using the return * value; these methods just do the calculations. */ int QueryParent( int iChild ) const { return (iChild + 1) / 2 - 1; } int QueryLeftChild( int iParent ) const { return 2 * (iParent + 1) - 1; } int QueryRightSibling( int iLeftSibling ) const { return iLeftSibling + 1; } int QueryLastParent( void ) const /* Return the parent of the last item. */ { return QueryParent( QueryCount() - 1 ); } int QueryFirstLeaf( void ) const /* Return the node following the parent of the last child node. * Note, intermediate values may not correspond to existing * items. */ { return QueryParent( QueryCount() - 1 ) + 1; } BOOL IsRoot( int i ) const { return ( i == 0 ); } BOOL IsAutoReadjusting( void ) const { return _fAutoReadjust; } void SetAutoReadjust( BOOL f ) { _fAutoReadjust = f; } public: int QueryCount( void ) const { return _cItems; } APIERR SetAllocCount( int cNewAllocCount ); void Trim( void ); }; // class HEAP_BASE #define DECLARE_HEAP_OF( type ) \ \ class type##_HEAP : public HEAP_BASE \ { \ private: \ void AdjustUpwards( int i ); \ void AdjustDownwards( int i ); \ \ public: \ type##_HEAP( int cInitialAllocCount = 0, BOOL fAutoReadjust = TRUE ) \ : HEAP_BASE( cInitialAllocCount, fAutoReadjust ) {} \ \ APIERR AddItem( type * pt ); \ type * RemoveTopItem( void ); \ type * PeekTopItem( void ) const \ { UIASSERT( IsAutoReadjusting()); return (type *)PeekItem( 0 ); } \ \ void Adjust( void ); \ \ }; /* type##_HEAP */ #define DEFINE_HEAP_OF( type ) \ \ void type##_HEAP::AdjustUpwards( int i ) \ { \ UIASSERT( 0 <= i && i < QueryCount()); \ \ /* Loop invariant: */ \ /* 0 <= i < QueryCount() && */ \ /* Item i's left and right subtrees have the heap property */ \ \ type * const pt = (type *)PeekItem( i ); \ while ( ! IsRoot( i )) \ { \ int iParent = QueryParent( i ); \ type * ptParent = (type *)PeekItem( iParent ); \ \ if ( ptParent->Compare( pt ) <= 0 ) \ { \ /* *ptParent is at most *pt. Now the heap is */ \ /* completely adjusted. */ \ break; \ } \ \ /* Move parent down (in effect, swap item with its parent) */ \ SetItem( i, ptParent ); \ \ i = iParent; \ } \ \ SetItem( i, pt ); \ \ } /* type##_HEAP::AdjustUpwards */ \ \ \ void type##_HEAP::AdjustDownwards( int i ) \ { \ UIASSERT( 0 <= i && i < QueryCount()); \ \ type * const pt = (type *)PeekItem( i ); \ \ /* We get and cache the index of the first leaf node (i.e., the */ \ /* leaf node with the smallest index). We know such an item */ \ /* exists, because we know the heap contains items, since we */ \ /* assume that i is the index of an existing item. */ \ int iFirstLeaf = QueryFirstLeaf(); \ \ while ( i < iFirstLeaf ) \ { \ /* Since i is less than the index of the first leaf, it */ \ /* must be the index of a parent node. */ \ \ /* Since i is a parent, there must be a left child. */ \ int iMinChild = QueryLeftChild( i ); \ UIASSERT( 0 <= iMinChild && iMinChild < QueryCount()); \ type * ptMinChild = (type *)PeekItem( iMinChild ); \ if ( QueryRightSibling( iMinChild ) < QueryCount()) \ { \ /* There is also a right child, since computing the */ \ /* index of the right sibling yields a valid index. */ \ \ /* Pick the smaller of the two to be the minimum */ \ /* child. */ \ UIASSERT( 0 <= QueryRightSibling( iMinChild ) && \ QueryRightSibling( iMinChild ) < QueryCount()); \ type * ptRightChild = (type *)PeekItem( \ QueryRightSibling( iMinChild )); \ if ( ptRightChild->Compare( ptMinChild ) < 0 ) \ { \ /* The right child is smaller. Use it. */ \ iMinChild = QueryRightSibling( iMinChild ); \ ptMinChild = ptRightChild; \ } \ } \ \ if ( pt->Compare( ptMinChild ) <= 0 ) \ { \ /* *pt is at most *ptMinChild. Hence, heap now has */ \ /* proper heap property. */ \ break; \ } \ \ /* Move child up (in effect, swap item with its min child) */ \ SetItem( i, ptMinChild ); \ \ i = iMinChild; \ } \ \ SetItem( i, pt ); \ \ } /* type##_HEAP::AdjustDownwards */ \ \ \ APIERR type##_HEAP::AddItem( type * pt ) \ { \ /* Add the item to the bottom of the heap */ \ \ int iNew = QueryCount(); \ \ APIERR err = I_AddItem( pt ); \ if ( err != NERR_Success ) \ return err; \ \ /* If heap is in the auto-readjusting state, restore */ \ /* the heap property by adjusting the heap from the */ \ /* new item upwards */ \ \ if ( IsAutoReadjusting()) \ AdjustUpwards( iNew ); \ \ return NERR_Success; \ \ } /* type##_HEAP::AddItem */ \ \ \ void type##_HEAP::Adjust( void ) \ { \ /* If the heap already is in the auto-readjusting state, */ \ /* it is already fully adjusted. */ \ if ( IsAutoReadjusting()) \ return; \ \ /* From now on, the heap will be auto-readjust. */ \ SetAutoReadjust( TRUE ); \ \ /* If the heap contains any items at all, adjust them in a */ \ /* bottom-up fashion. In different terms, this creates */ \ /* small heaps and then merges them. Note, this */ \ /* operation, which is commonly used after inserting all */ \ /* items into a non-auto-readjusting heap, runs in O(n) */ \ /* time! Compare this to the O(n log n) needed if each */ \ /* item was added to an auto-readjusting heap. (A proof */ \ /* of the O(n) running time and the correctness of this */ \ /* approach is left to the reader.) */ \ if ( QueryCount() > 0 ) \ { \ int i = QueryFirstLeaf(); \ while ( ! IsRoot( i )) \ { \ i--; \ AdjustDownwards( i ); \ } \ } \ \ } /* type##_HEAP::Adjust */ \ \ \ type * type##_HEAP::RemoveTopItem( void ) \ { \ /* Only allowed to be called on heaps in the auto-readjusting */ \ /* state. This is asserted in I_RemoveTopItem, so that line */ \ /* numbers in assertion failures make better sense at run- */ \ /* time. */ \ \ /* Get the top item, and move the bottom-most item to the top */ \ \ type * ptReturnItem = (type *)I_RemoveTopItem(); \ \ /* Restore the heap property, provided there are items left in */ \ /* the heap. */ \ \ if ( QueryCount() > 0 ) \ AdjustDownwards( 0 ); \ \ return ptReturnItem; \ \ } /* type##_HEAP::RemoveTopItem */ #endif // _AHEAP_HXX_