fxuHeapD.c

Go to the documentation of this file.

 
#include "fxuInt.h"
 
ABC_NAMESPACE_IMPL_START
 

 
#define FXU_HEAP_DOUBLE_WEIGHT(pDiv)           ((pDiv)->Weight)
#define FXU_HEAP_DOUBLE_CURRENT(p, pDiv)       ((p)->pTree[(pDiv)->HNum])
#define FXU_HEAP_DOUBLE_PARENT_EXISTS(p, pDiv) ((pDiv)->HNum > 1)
#define FXU_HEAP_DOUBLE_CHILD1_EXISTS(p, pDiv) (((pDiv)->HNum << 1) <= p->nItems)
#define FXU_HEAP_DOUBLE_CHILD2_EXISTS(p, pDiv) ((((pDiv)->HNum << 1)+1) <= p->nItems)
#define FXU_HEAP_DOUBLE_PARENT(p, pDiv)        ((p)->pTree[(pDiv)->HNum >> 1])
#define FXU_HEAP_DOUBLE_CHILD1(p, pDiv)        ((p)->pTree[(pDiv)->HNum << 1])
#define FXU_HEAP_DOUBLE_CHILD2(p, pDiv)        ((p)->pTree[((pDiv)->HNum << 1)+1])
#define FXU_HEAP_DOUBLE_ASSERT(p, pDiv)        assert( (pDiv)->HNum >= 1 && (pDiv)->HNum <= p->nItemsAlloc )
 
static void Fxu_HeapDoubleResize( Fxu_HeapDouble * p );                  
static void Fxu_HeapDoubleSwap( Fxu_Double ** pDiv1, Fxu_Double ** pDiv2 );  
static void Fxu_HeapDoubleMoveUp( Fxu_HeapDouble * p, Fxu_Double * pDiv );  
static void Fxu_HeapDoubleMoveDn( Fxu_HeapDouble * p, Fxu_Double * pDiv );  


Fxu_HeapDouble * Fxu_HeapDoubleStart()
{
    Fxu_HeapDouble * p;
    p = ABC_ALLOC( Fxu_HeapDouble, 1 );
    memset( p, 0, sizeof(Fxu_HeapDouble) );
    p->nItems      = 0;
    p->nItemsAlloc = 10000;
    p->pTree       = ABC_ALLOC( Fxu_Double *, p->nItemsAlloc + 1 );
    p->pTree[0]    = NULL;
    return p;
}
 

void Fxu_HeapDoubleResize( Fxu_HeapDouble * p )
{
    p->nItemsAlloc *= 2;
    p->pTree = ABC_REALLOC( Fxu_Double *, p->pTree, p->nItemsAlloc + 1 );
}

void Fxu_HeapDoubleStop( Fxu_HeapDouble * p )
{
    ABC_FREE( p->pTree );
    ABC_FREE( p );
}
 

void Fxu_HeapDoublePrint( FILE * pFile, Fxu_HeapDouble * p )
{
    Fxu_Double * pDiv;
    int Counter = 1;
    int Degree  = 1;
 
    Fxu_HeapDoubleCheck( p );
    fprintf( pFile, "The contents of the heap:\n" );
    fprintf( pFile, "Level %d:  ", Degree );
    Fxu_HeapDoubleForEachItem( p, pDiv )
    {
        assert( Counter == p->pTree[Counter]->HNum );
        fprintf( pFile, "%2d=%3d  ", Counter, FXU_HEAP_DOUBLE_WEIGHT(p->pTree[Counter]) );
        if ( ++Counter == (1 << Degree) )
        {
            fprintf( pFile, "\n" );
            Degree++;
            fprintf( pFile, "Level %d:  ", Degree );
        }
    }
    fprintf( pFile, "\n" );
    fprintf( pFile, "End of the heap printout.\n" );
}

void Fxu_HeapDoubleCheck( Fxu_HeapDouble * p )
{
    Fxu_Double * pDiv;
    Fxu_HeapDoubleForEachItem( p, pDiv )
    {
        assert( pDiv->HNum == p->i );
        Fxu_HeapDoubleCheckOne( p, pDiv );
    }
}

void Fxu_HeapDoubleCheckOne( Fxu_HeapDouble * p, Fxu_Double * pDiv )
{
    int Weight1, Weight2;
    if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) )
    {
        Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv);
        Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) );
        assert( Weight1 >= Weight2 );
    }
    if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) )
    {
        Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv);
        Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) );
        assert( Weight1 >= Weight2 );
    }
}

void Fxu_HeapDoubleInsert( Fxu_HeapDouble * p, Fxu_Double * pDiv )
{
    if ( p->nItems == p->nItemsAlloc )
        Fxu_HeapDoubleResize( p );
    // put the last entry to the last place and move up
    p->pTree[++p->nItems] = pDiv;
    pDiv->HNum = p->nItems;
    // move the last entry up if necessary
    Fxu_HeapDoubleMoveUp( p, pDiv );
}

void Fxu_HeapDoubleUpdate( Fxu_HeapDouble * p, Fxu_Double * pDiv )
{
//printf( "Updating divisor %d.\n", pDiv->Num );
 
    FXU_HEAP_DOUBLE_ASSERT(p,pDiv);
    if ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,pDiv) && 
         FXU_HEAP_DOUBLE_WEIGHT(pDiv) > FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_PARENT(p,pDiv) ) )
        Fxu_HeapDoubleMoveUp( p, pDiv );
    else if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) && 
        FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) ) )
        Fxu_HeapDoubleMoveDn( p, pDiv );
    else if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) && 
        FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) ) )
        Fxu_HeapDoubleMoveDn( p, pDiv );
}

void Fxu_HeapDoubleDelete( Fxu_HeapDouble * p, Fxu_Double * pDiv )
{
    FXU_HEAP_DOUBLE_ASSERT(p,pDiv);
    // put the last entry to the deleted place
    // decrement the number of entries
    p->pTree[pDiv->HNum] = p->pTree[p->nItems--];
    p->pTree[pDiv->HNum]->HNum = pDiv->HNum;
    // move the top entry down if necessary
    Fxu_HeapDoubleUpdate( p, p->pTree[pDiv->HNum] );
    pDiv->HNum = 0;
}

Fxu_Double * Fxu_HeapDoubleReadMax( Fxu_HeapDouble * p )
{
    if ( p->nItems == 0 )
        return NULL;
    return p->pTree[1];     
}

Fxu_Double * Fxu_HeapDoubleGetMax( Fxu_HeapDouble * p )
{
    Fxu_Double * pDiv;
    if ( p->nItems == 0 )
        return NULL;
    // prepare the return value
    pDiv = p->pTree[1];
    pDiv->HNum = 0;
    // put the last entry on top
    // decrement the number of entries
    p->pTree[1] = p->pTree[p->nItems--];
    p->pTree[1]->HNum = 1;
    // move the top entry down if necessary
    Fxu_HeapDoubleMoveDn( p, p->pTree[1] );
    return pDiv;     
}

int  Fxu_HeapDoubleReadMaxWeight( Fxu_HeapDouble * p )
{
    if ( p->nItems == 0 )
        return -1;
    else
        return FXU_HEAP_DOUBLE_WEIGHT(p->pTree[1]);
}
 
 

void Fxu_HeapDoubleSwap( Fxu_Double ** pDiv1, Fxu_Double ** pDiv2 )
{
    Fxu_Double * pDiv;
    int Temp;
    pDiv   = *pDiv1;
    *pDiv1 = *pDiv2;
    *pDiv2 = pDiv;
    Temp          = (*pDiv1)->HNum;
    (*pDiv1)->HNum = (*pDiv2)->HNum;
    (*pDiv2)->HNum = Temp;
}

void Fxu_HeapDoubleMoveUp( Fxu_HeapDouble * p, Fxu_Double * pDiv )
{
    Fxu_Double ** ppDiv, ** ppPar;
    ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv);
    while ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,*ppDiv) )
    {
        ppPar = &FXU_HEAP_DOUBLE_PARENT(p,*ppDiv);
        if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) > FXU_HEAP_DOUBLE_WEIGHT(*ppPar) )
        {
            Fxu_HeapDoubleSwap( ppDiv, ppPar );
            ppDiv = ppPar;
        }
        else
            break;
    }
}
 
void Fxu_HeapDoubleMoveDn( Fxu_HeapDouble * p, Fxu_Double * pDiv )
{
    Fxu_Double ** ppChild1, ** ppChild2, ** ppDiv;
    ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv);
    while ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,*ppDiv) )
    { // if Child1 does not exist, Child2 also does not exists
 
        // get the children
        ppChild1 = &FXU_HEAP_DOUBLE_CHILD1(p,*ppDiv);
        if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,*ppDiv) )
        {
            ppChild2 = &FXU_HEAP_DOUBLE_CHILD2(p,*ppDiv);
 
            // consider two cases
            if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) &&
                 FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) )
            { // Div is larger than both, skip
                break;
            }
            else
            { // Div is smaller than one of them, then swap it with larger 
                if ( FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) )
                {
                    Fxu_HeapDoubleSwap( ppDiv, ppChild1 );
                    // update the pointer
                    ppDiv = ppChild1;
                }
                else
                {
                    Fxu_HeapDoubleSwap( ppDiv, ppChild2 );
                    // update the pointer
                    ppDiv = ppChild2;
                }
            }
        }
        else // Child2 does not exist
        {
            // consider two cases
            if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) )
            { // Div is larger than Child1, skip
                break;
            }
            else
            { // Div is smaller than Child1, then swap them
                Fxu_HeapDoubleSwap( ppDiv, ppChild1 );
                // update the pointer
                ppDiv = ppChild1;
            }
        }
    }
}
 

 
 
ABC_NAMESPACE_IMPL_END