/**CFile****************************************************************

  FileName    [fxuHeapS.c]

  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]

  Synopsis    [The priority queue for variables.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - February 1, 2003.]

  Revision    [$Id: fxuHeapS.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $]

***********************************************************************/

#include "fxuInt.h"

////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

#define FXU_HEAP_SINGLE_WEIGHT(pSingle)           ((pSingle)->Weight)
#define FXU_HEAP_SINGLE_CURRENT(p, pSingle)       ((p)->pTree[(pSingle)->HNum])
#define FXU_HEAP_SINGLE_PARENT_EXISTS(p, pSingle) ((pSingle)->HNum > 1)
#define FXU_HEAP_SINGLE_CHILD1_EXISTS(p, pSingle) (((pSingle)->HNum << 1) <= p->nItems)
#define FXU_HEAP_SINGLE_CHILD2_EXISTS(p, pSingle) ((((pSingle)->HNum << 1)+1) <= p->nItems)
#define FXU_HEAP_SINGLE_PARENT(p, pSingle)        ((p)->pTree[(pSingle)->HNum >> 1])
#define FXU_HEAP_SINGLE_CHILD1(p, pSingle)        ((p)->pTree[(pSingle)->HNum << 1])
#define FXU_HEAP_SINGLE_CHILD2(p, pSingle)        ((p)->pTree[((pSingle)->HNum << 1)+1])
#define FXU_HEAP_SINGLE_ASSERT(p, pSingle)        assert( (pSingle)->HNum >= 1 && (pSingle)->HNum <= p->nItemsAlloc )

static void Fxu_HeapSingleResize( Fxu_HeapSingle * p );                  
static void Fxu_HeapSingleSwap( Fxu_Single ** pSingle1, Fxu_Single ** pSingle2 );  
static void Fxu_HeapSingleMoveUp( Fxu_HeapSingle * p, Fxu_Single * pSingle );  
static void Fxu_HeapSingleMoveDn( Fxu_HeapSingle * p, Fxu_Single * pSingle );  

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fxu_HeapSingle * Fxu_HeapSingleStart()
{
	Fxu_HeapSingle * p;
	p = ALLOC( Fxu_HeapSingle, 1 );
	memset( p, 0, sizeof(Fxu_HeapSingle) );
	p->nItems      = 0;
	p->nItemsAlloc = 2000;
	p->pTree       = ALLOC( Fxu_Single *, p->nItemsAlloc + 10 );
	p->pTree[0]    = NULL;
	return p;
}


/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_HeapSingleResize( Fxu_HeapSingle * p )
{
	p->nItemsAlloc *= 2;
	p->pTree = REALLOC( Fxu_Single *, p->pTree, p->nItemsAlloc + 10 );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_HeapSingleStop( Fxu_HeapSingle * p )
{
    int i;
    i = 0;
	free( p->pTree );
    i = 1;
	free( p );
}


/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_HeapSinglePrint( FILE * pFile, Fxu_HeapSingle * p )
{
	Fxu_Single * pSingle;
	int Counter = 1;
	int Degree  = 1;

	Fxu_HeapSingleCheck( p );
	fprintf( pFile, "The contents of the heap:\n" );
	fprintf( pFile, "Level %d:  ", Degree );
	Fxu_HeapSingleForEachItem( p, pSingle )
	{
		assert( Counter == p->pTree[Counter]->HNum );
		fprintf( pFile, "%2d=%3d  ", Counter, FXU_HEAP_SINGLE_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" );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_HeapSingleCheck( Fxu_HeapSingle * p )
{
	Fxu_Single * pSingle;
	Fxu_HeapSingleForEachItem( p, pSingle )
	{
		assert( pSingle->HNum == p->i );
        Fxu_HeapSingleCheckOne( p, pSingle );
	}
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_HeapSingleCheckOne( Fxu_HeapSingle * p, Fxu_Single * pSingle )
{
    int Weight1, Weight2;
	if ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,pSingle) )
	{
        Weight1 = FXU_HEAP_SINGLE_WEIGHT(pSingle);
        Weight2 = FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD1(p,pSingle) );
        assert( Weight1 >= Weight2 );
	}
	if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,pSingle) )
	{
        Weight1 = FXU_HEAP_SINGLE_WEIGHT(pSingle);
        Weight2 = FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD2(p,pSingle) );
        assert( Weight1 >= Weight2 );
	}
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_HeapSingleInsert( Fxu_HeapSingle * p, Fxu_Single * pSingle )
{
	if ( p->nItems == p->nItemsAlloc )
		Fxu_HeapSingleResize( p );
	// put the last entry to the last place and move up
	p->pTree[++p->nItems] = pSingle;
	pSingle->HNum = p->nItems;
	// move the last entry up if necessary
	Fxu_HeapSingleMoveUp( p, pSingle );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_HeapSingleUpdate( Fxu_HeapSingle * p, Fxu_Single * pSingle )
{
	FXU_HEAP_SINGLE_ASSERT(p,pSingle);
	if ( FXU_HEAP_SINGLE_PARENT_EXISTS(p,pSingle) && 
         FXU_HEAP_SINGLE_WEIGHT(pSingle) > FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_PARENT(p,pSingle) ) )
		Fxu_HeapSingleMoveUp( p, pSingle );
	else if ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,pSingle) && 
        FXU_HEAP_SINGLE_WEIGHT(pSingle) < FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD1(p,pSingle) ) )
		Fxu_HeapSingleMoveDn( p, pSingle );
	else if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,pSingle) && 
        FXU_HEAP_SINGLE_WEIGHT(pSingle) < FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD2(p,pSingle) ) )
		Fxu_HeapSingleMoveDn( p, pSingle );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_HeapSingleDelete( Fxu_HeapSingle * p, Fxu_Single * pSingle )
{
    int Place = pSingle->HNum;
	FXU_HEAP_SINGLE_ASSERT(p,pSingle);
	// put the last entry to the deleted place
	// decrement the number of entries
	p->pTree[Place] = p->pTree[p->nItems--];
	p->pTree[Place]->HNum = Place;
	// move the top entry down if necessary
	Fxu_HeapSingleUpdate( p, p->pTree[Place] );
    pSingle->HNum = 0;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fxu_Single * Fxu_HeapSingleReadMax( Fxu_HeapSingle * p )
{
	if ( p->nItems == 0 )
		return NULL;
	return p->pTree[1];
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fxu_Single * Fxu_HeapSingleGetMax( Fxu_HeapSingle * p )
{
	Fxu_Single * pSingle;
	if ( p->nItems == 0 )
		return NULL;
	// prepare the return value
	pSingle = p->pTree[1];
	pSingle->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_HeapSingleMoveDn( p, p->pTree[1] );
	return pSingle;	 
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int  Fxu_HeapSingleReadMaxWeight( Fxu_HeapSingle * p )
{
	if ( p->nItems == 0 )
		return -1;
	return FXU_HEAP_SINGLE_WEIGHT(p->pTree[1]);
}



/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_HeapSingleSwap( Fxu_Single ** pSingle1, Fxu_Single ** pSingle2 )
{
	Fxu_Single * pSingle;
	int Temp;
	pSingle   = *pSingle1;
	*pSingle1 = *pSingle2;
	*pSingle2 = pSingle;
	Temp          = (*pSingle1)->HNum;
	(*pSingle1)->HNum = (*pSingle2)->HNum;
	(*pSingle2)->HNum = Temp;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_HeapSingleMoveUp( Fxu_HeapSingle * p, Fxu_Single * pSingle )
{
	Fxu_Single ** ppSingle, ** ppPar;
	ppSingle = &FXU_HEAP_SINGLE_CURRENT(p, pSingle);
	while ( FXU_HEAP_SINGLE_PARENT_EXISTS(p,*ppSingle) )
	{
		ppPar = &FXU_HEAP_SINGLE_PARENT(p,*ppSingle);
		if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) > FXU_HEAP_SINGLE_WEIGHT(*ppPar) )
		{
			Fxu_HeapSingleSwap( ppSingle, ppPar );
			ppSingle = ppPar;
		}
		else
			break;
	}
}
 
/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_HeapSingleMoveDn( Fxu_HeapSingle * p, Fxu_Single * pSingle )
{
	Fxu_Single ** ppChild1, ** ppChild2, ** ppSingle;
	ppSingle = &FXU_HEAP_SINGLE_CURRENT(p, pSingle);
	while ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,*ppSingle) )
	{ // if Child1 does not exist, Child2 also does not exists

		// get the children
		ppChild1 = &FXU_HEAP_SINGLE_CHILD1(p,*ppSingle);
        if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,*ppSingle) )
        {
            ppChild2 = &FXU_HEAP_SINGLE_CHILD2(p,*ppSingle);

            // consider two cases
            if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild1) &&
                 FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild2) )
            { // Var is larger than both, skip
                break;
            }
            else
            { // Var is smaller than one of them, then swap it with larger 
                if ( FXU_HEAP_SINGLE_WEIGHT(*ppChild1) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild2) )
                {
			        Fxu_HeapSingleSwap( ppSingle, ppChild1 );
		            // update the pointer
		            ppSingle = ppChild1;
                }
                else
                {
			        Fxu_HeapSingleSwap( ppSingle, ppChild2 );
		            // update the pointer
		            ppSingle = ppChild2;
                }
            }
        }
        else // Child2 does not exist
        {
            // consider two cases
            if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild1) )
            { // Var is larger than Child1, skip
                break;
            }
            else
            { // Var is smaller than Child1, then swap them
			    Fxu_HeapSingleSwap( ppSingle, ppChild1 );
		        // update the pointer
		        ppSingle = ppChild1;
            }
        }
	}
}


////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////
