xsatUtils.h

Go to the documentation of this file.

#ifndef ABC__sat__xSAT__xsatUtils_h
#define ABC__sat__xSAT__xsatUtils_h

#include "misc/util/abc_global.h"
 
ABC_NAMESPACE_HEADER_START

static inline void xSAT_UtilSelectSort( void** pArray, int nSize, int(* CompFnct )( const void *, const void * ) )
{
    int i, j, iBest;
    void* pTmp;
 
    for ( i = 0; i < ( nSize - 1 ); i++ )
    {
        iBest = i;
        for ( j = i + 1; j < nSize; j++ )
        {
            if ( CompFnct( pArray[j], pArray[iBest] ) )
                iBest = j;
        }
        pTmp = pArray[i];
        pArray[i] = pArray[iBest];
        pArray[iBest] = pTmp;
    }
}

static void xSAT_UtilSort( void** pArray, int nSize, int(* CompFnct )( const void *, const void *) )
{
    if ( nSize <= 15 )
        xSAT_UtilSelectSort( pArray, nSize, CompFnct );
    else
    {
        void* pPivot = pArray[nSize / 2];
        void* pTmp;
        int i = -1;
        int j = nSize;
 
        for(;;)
        {
            do i++; while( CompFnct( pArray[i], pPivot ) );
            do j--; while( CompFnct( pPivot, pArray[j] ) );
 
            if ( i >= j )
                break;
 
            pTmp = pArray[i];
            pArray[i] = pArray[j];
            pArray[j] = pTmp;
        }
 
        xSAT_UtilSort( pArray, i, CompFnct );
        xSAT_UtilSort( pArray + i, ( nSize - i ), CompFnct );
    }
}
 
ABC_NAMESPACE_HEADER_END
 
#endif