utilSort.c

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

  FileName    [utilSort.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Merge sort with user-specified cost.]

  Synopsis    [Merge sort with user-specified cost.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - Feburary 13, 2011.]

  Revision    [$Id: utilSort.c,v 1.00 2011/02/11 00:00:00 alanmi Exp $]

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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#include "abc_global.h"

ABC_NAMESPACE_IMPL_START

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

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

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

  Synopsis    [Merging two lists of entries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_SortMerge( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut )
{
    int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
    int * pOutBeg = pOut;
    while ( p1Beg < p1End && p2Beg < p2End )
    {
        if ( *p1Beg == *p2Beg )
            *pOut++ = *p1Beg++, *pOut++ = *p2Beg++; 
        else if ( *p1Beg < *p2Beg )
            *pOut++ = *p1Beg++; 
        else // if ( *p1Beg > *p2Beg )
            *pOut++ = *p2Beg++; 
    }
    while ( p1Beg < p1End )
        *pOut++ = *p1Beg++; 
    while ( p2Beg < p2End )
        *pOut++ = *p2Beg++;
    assert( pOut - pOutBeg == nEntries );
}

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

  Synopsis    [Recursive sorting.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_Sort_rec( int * pInBeg, int * pInEnd, int * pOutBeg )
{
    int nSize = pInEnd - pInBeg;
    assert( nSize > 0 );
    if ( nSize == 1 )
        return;
    if ( nSize == 2 )
    {
         if ( pInBeg[0] > pInBeg[1] )
         {
             pInBeg[0] ^= pInBeg[1];
             pInBeg[1] ^= pInBeg[0];
             pInBeg[0] ^= pInBeg[1];
         }
    }
    else if ( nSize < 8 )
    {
        int temp, i, j, best_i;
        for ( i = 0; i < nSize-1; i++ )
        {
            best_i = i;
            for ( j = i+1; j < nSize; j++ )
                if ( pInBeg[j] < pInBeg[best_i] )
                    best_i = j;
            temp = pInBeg[i]; 
            pInBeg[i] = pInBeg[best_i]; 
            pInBeg[best_i] = temp;
        }
    }
    else
    {
        Abc_Sort_rec( pInBeg, pInBeg + nSize/2, pOutBeg );
        Abc_Sort_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2 );
        Abc_SortMerge( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg );
        memcpy( pInBeg, pOutBeg, sizeof(int) * nSize );
    }
}

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

  Synopsis    [Returns the sorted array of integers.]

  Description [This procedure is about 10% faster than qsort().]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_MergeSort( int * pInput, int nSize )
{
    int * pOutput;
    if ( nSize < 2 )
        return;
    pOutput = (int *) malloc( sizeof(int) * nSize );
    Abc_Sort_rec( pInput, pInput + nSize, pOutput );
    free( pOutput );
}


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

  Synopsis    [Merging two lists of entries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_SortMergeCost2( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut, int * pCost )
{
    int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
    int * pOutBeg = pOut;
    while ( p1Beg < p1End && p2Beg < p2End )
    {
        if ( pCost[*p1Beg] == pCost[*p2Beg] )
            *pOut++ = *p1Beg++, *pOut++ = *p2Beg++; 
        else if ( pCost[*p1Beg] < pCost[*p2Beg] )
            *pOut++ = *p1Beg++; 
        else // if ( pCost[*p1Beg] > pCost[*p2Beg] )
            *pOut++ = *p2Beg++; 
    }
    while ( p1Beg < p1End )
        *pOut++ = *p1Beg++; 
    while ( p2Beg < p2End )
        *pOut++ = *p2Beg++;
    assert( pOut - pOutBeg == nEntries );
}

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

  Synopsis    [Recursive sorting.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_SortCost2_rec( int * pInBeg, int * pInEnd, int * pOutBeg, int * pCost )
{
    int nSize = pInEnd - pInBeg;
    assert( nSize > 0 );
    if ( nSize == 1 )
        return;
    if ( nSize == 2 )
    {
         if ( pCost[pInBeg[0]] > pCost[pInBeg[1]] )
         {
             pInBeg[0] ^= pInBeg[1];
             pInBeg[1] ^= pInBeg[0];
             pInBeg[0] ^= pInBeg[1];
         }
    }
    else if ( nSize < 8 )
    {
        int temp, i, j, best_i;
        for ( i = 0; i < nSize-1; i++ )
        {
            best_i = i;
            for ( j = i+1; j < nSize; j++ )
                if ( pCost[pInBeg[j]] < pCost[pInBeg[best_i]] )
                    best_i = j;
            temp = pInBeg[i]; 
            pInBeg[i] = pInBeg[best_i]; 
            pInBeg[best_i] = temp;
        }
    }
    else
    {
        Abc_SortCost2_rec( pInBeg, pInBeg + nSize/2, pOutBeg, pCost );
        Abc_SortCost2_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2, pCost );
        Abc_SortMergeCost2( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg, pCost );
        memcpy( pInBeg, pOutBeg, sizeof(int) * nSize );
    }
}

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

  Synopsis    [Returns the sorted array of integers.]

  Description [This procedure is about 10% faster than qsort().]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_MergeSortCost2( int * pInput, int nSize, int * pCost )
{
    int * pOutput;
    if ( nSize < 2 )
        return;
    pOutput = (int *) malloc( sizeof(int) * nSize );
    Abc_SortCost2_rec( pInput, pInput + nSize, pOutput, pCost );
    free( pOutput );
}


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

  Synopsis    [Merging two lists of entries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_SortMergeCost2Reverse( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut, int * pCost )
{
    int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
    int * pOutBeg = pOut;
    while ( p1Beg < p1End && p2Beg < p2End )
    {
        if ( pCost[*p1Beg] == pCost[*p2Beg] )
            *pOut++ = *p1Beg++, *pOut++ = *p2Beg++; 
        else if ( pCost[*p1Beg] > pCost[*p2Beg] )
            *pOut++ = *p1Beg++; 
        else // if ( pCost[*p1Beg] < pCost[*p2Beg] )
            *pOut++ = *p2Beg++; 
    }
    while ( p1Beg < p1End )
        *pOut++ = *p1Beg++; 
    while ( p2Beg < p2End )
        *pOut++ = *p2Beg++;
    assert( pOut - pOutBeg == nEntries );
}

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

  Synopsis    [Recursive sorting.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_SortCost2Reverse_rec( int * pInBeg, int * pInEnd, int * pOutBeg, int * pCost )
{
    int nSize = pInEnd - pInBeg;
    assert( nSize > 0 );
    if ( nSize == 1 )
        return;
    if ( nSize == 2 )
    {
         if ( pCost[pInBeg[0]] < pCost[pInBeg[1]] )
         {
             pInBeg[0] ^= pInBeg[1];
             pInBeg[1] ^= pInBeg[0];
             pInBeg[0] ^= pInBeg[1];
         }
    }
    else if ( nSize < 8 )
    {
        int temp, i, j, best_i;
        for ( i = 0; i < nSize-1; i++ )
        {
            best_i = i;
            for ( j = i+1; j < nSize; j++ )
                if ( pCost[pInBeg[j]] > pCost[pInBeg[best_i]] )
                    best_i = j;
            temp = pInBeg[i]; 
            pInBeg[i] = pInBeg[best_i]; 
            pInBeg[best_i] = temp;
        }
    }
    else
    {
        Abc_SortCost2Reverse_rec( pInBeg, pInBeg + nSize/2, pOutBeg, pCost );
        Abc_SortCost2Reverse_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2, pCost );
        Abc_SortMergeCost2Reverse( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg, pCost );
        memcpy( pInBeg, pOutBeg, sizeof(int) * nSize );
    }
}

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

  Synopsis    [Returns the sorted array of integers.]

  Description [This procedure is about 10% faster than qsort().]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_MergeSortCost2Reverse( int * pInput, int nSize, int * pCost )
{
    int * pOutput;
    if ( nSize < 2 )
        return;
    pOutput = (int *) malloc( sizeof(int) * nSize );
    Abc_SortCost2Reverse_rec( pInput, pInput + nSize, pOutput, pCost );
    free( pOutput );
}



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

  Synopsis    [Merging two lists of entries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_MergeSortCostMerge( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut )
{
    int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
    int * pOutBeg = pOut;
    while ( p1Beg < p1End && p2Beg < p2End )
    {
        if ( p1Beg[1] == p2Beg[1] )
            *pOut++ = *p1Beg++, *pOut++ = *p1Beg++, *pOut++ = *p2Beg++, *pOut++ = *p2Beg++; 
        else if ( p1Beg[1] < p2Beg[1] )
            *pOut++ = *p1Beg++, *pOut++ = *p1Beg++; 
        else // if ( p1Beg[1] > p2Beg[1] )
            *pOut++ = *p2Beg++, *pOut++ = *p2Beg++; 
    }
    while ( p1Beg < p1End )
        *pOut++ = *p1Beg++, *pOut++ = *p1Beg++; 
    while ( p2Beg < p2End )
        *pOut++ = *p2Beg++, *pOut++ = *p2Beg++;
    assert( pOut - pOutBeg == nEntries );
}

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

  Synopsis    [Recursive sorting.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_MergeSortCost_rec( int * pInBeg, int * pInEnd, int * pOutBeg )
{
    int nSize = (pInEnd - pInBeg)/2;
    assert( nSize > 0 );
    if ( nSize == 1 )
        return;
    if ( nSize == 2 )
    {
         if ( pInBeg[1] > pInBeg[3] )
         {
             pInBeg[1] ^= pInBeg[3];
             pInBeg[3] ^= pInBeg[1];
             pInBeg[1] ^= pInBeg[3];
             pInBeg[0] ^= pInBeg[2];
             pInBeg[2] ^= pInBeg[0];
             pInBeg[0] ^= pInBeg[2];
         }
    }
    else if ( nSize < 8 )
    {
        int temp, i, j, best_i;
        for ( i = 0; i < nSize-1; i++ )
        {
            best_i = i;
            for ( j = i+1; j < nSize; j++ )
                if ( pInBeg[2*j+1] < pInBeg[2*best_i+1] )
                    best_i = j;
            temp = pInBeg[2*i]; 
            pInBeg[2*i] = pInBeg[2*best_i]; 
            pInBeg[2*best_i] = temp;
            temp = pInBeg[2*i+1]; 
            pInBeg[2*i+1] = pInBeg[2*best_i+1]; 
            pInBeg[2*best_i+1] = temp;
        }
    }
    else
    {
        Abc_MergeSortCost_rec( pInBeg, pInBeg + 2*(nSize/2), pOutBeg );
        Abc_MergeSortCost_rec( pInBeg + 2*(nSize/2), pInEnd, pOutBeg + 2*(nSize/2) );
        Abc_MergeSortCostMerge( pInBeg, pInBeg + 2*(nSize/2), pInBeg + 2*(nSize/2), pInEnd, pOutBeg );
        memcpy( pInBeg, pOutBeg, sizeof(int) * 2 * nSize );
    }
}

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

  Synopsis    [Sorting procedure.]

  Description [Returns permutation for the non-decreasing order of costs.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int * Abc_MergeSortCost( int * pCosts, int nSize )
{
    int i, * pResult, * pInput, * pOutput;
    pResult = (int *) calloc( sizeof(int), nSize );
    if ( nSize < 2 )
        return pResult;
    pInput  = (int *) malloc( sizeof(int) * 2 * nSize );
    pOutput = (int *) malloc( sizeof(int) * 2 * nSize );
    for ( i = 0; i < nSize; i++ )
        pInput[2*i] = i, pInput[2*i+1] = pCosts[i];
    Abc_MergeSortCost_rec( pInput, pInput + 2*nSize, pOutput );
    for ( i = 0; i < nSize; i++ )
        pResult[i] = pInput[2*i];
    free( pOutput );
    free( pInput );
    return pResult;
}


// this implementation uses 3x less memory but is 30% slower due to cache misses

#if 0  

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

  Synopsis    [Merging two lists of entries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_MergeSortCostMerge( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut, int * pCost )
{
    int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
    int * pOutBeg = pOut;
    while ( p1Beg < p1End && p2Beg < p2End )
    {
        if ( pCost[*p1Beg] == pCost[*p2Beg] )
            *pOut++ = *p1Beg++, *pOut++ = *p2Beg++; 
        else if ( pCost[*p1Beg] < pCost[*p2Beg] )
            *pOut++ = *p1Beg++; 
        else // if ( pCost[*p1Beg] > pCost[*p2Beg] )
            *pOut++ = *p2Beg++; 
    }
    while ( p1Beg < p1End )
        *pOut++ = *p1Beg++; 
    while ( p2Beg < p2End )
        *pOut++ = *p2Beg++;
    assert( pOut - pOutBeg == nEntries );
}

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

  Synopsis    [Recursive sorting.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_MergeSortCost_rec( int * pInBeg, int * pInEnd, int * pOutBeg, int * pCost )
{
    int nSize = pInEnd - pInBeg;
    assert( nSize > 0 );
    if ( nSize == 1 )
        return;
    if ( nSize == 2 )
    {
         if ( pCost[pInBeg[0]] > pCost[pInBeg[1]] )
         {
             pInBeg[0] ^= pInBeg[1];
             pInBeg[1] ^= pInBeg[0];
             pInBeg[0] ^= pInBeg[1];
         }
    }
    else if ( nSize < 8 )
    {
        int temp, i, j, best_i;
        for ( i = 0; i < nSize-1; i++ )
        {
            best_i = i;
            for ( j = i+1; j < nSize; j++ )
                if ( pCost[pInBeg[j]] < pCost[pInBeg[best_i]] )
                    best_i = j;
            temp = pInBeg[i]; 
            pInBeg[i] = pInBeg[best_i]; 
            pInBeg[best_i] = temp;
        }
    }
    else
    {
        Abc_MergeSortCost_rec( pInBeg, pInBeg + nSize/2, pOutBeg, pCost );
        Abc_MergeSortCost_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2, pCost );
        Abc_MergeSortCostMerge( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg, pCost );
        memcpy( pInBeg, pOutBeg, sizeof(int) * nSize );
    }
}

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

  Synopsis    [Sorting procedure.]

  Description [Returns permutation for the non-decreasing order of costs.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int * Abc_MergeSortCost( int * pCosts, int nSize )
{
    int i, * pInput, * pOutput;
    pInput = (int *) malloc( sizeof(int) * nSize );
    for ( i = 0; i < nSize; i++ )
        pInput[i] = i;
    if ( nSize < 2 )
        return pInput;
    pOutput = (int *) malloc( sizeof(int) * nSize );
    Abc_MergeSortCost_rec( pInput, pInput + nSize, pOutput, pCosts );
    free( pOutput );
    return pInput;
}

#endif




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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_SortNumCompare( int * pNum1, int * pNum2 )
{
    return *pNum1 - *pNum2;
}

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

  Synopsis    [Testing the sorting procedure.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_SortTest()
{
    int fUseNew = 0;
    int i, nSize = 50000000;
    int * pArray = (int *)malloc( sizeof(int) * nSize );
    int * pPerm;
    abctime clk;
    // generate numbers
    srand( 1000 );
    for ( i = 0; i < nSize; i++ )
        pArray[i] = rand();

    // try sorting
    if ( fUseNew )
    {
        int fUseCost = 1;
        if ( fUseCost )
        {
            clk = Abc_Clock();
            pPerm = Abc_MergeSortCost( pArray, nSize );
            Abc_PrintTime( 1, "New sort", Abc_Clock() - clk );
            // check
            for ( i = 1; i < nSize; i++ )
                assert( pArray[pPerm[i-1]] <= pArray[pPerm[i]] );
            free( pPerm );
        }
        else
        {
            clk = Abc_Clock();
            Abc_MergeSort( pArray, nSize );
            Abc_PrintTime( 1, "New sort", Abc_Clock() - clk );
            // check
            for ( i = 1; i < nSize; i++ )
                assert( pArray[i-1] <= pArray[i] );
        }
    }
    else
    {
        clk = Abc_Clock();
        qsort( (void *)pArray, (size_t)nSize, sizeof(int), (int (*)(const void *, const void *)) Abc_SortNumCompare );
        Abc_PrintTime( 1, "Old sort", Abc_Clock() - clk );
        // check
        for ( i = 1; i < nSize; i++ )
            assert( pArray[i-1] <= pArray[i] );
    }

    free( pArray );
}




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

  Synopsis    [QuickSort algorithm as implemented by qsort().]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_QuickSort1CompareInc( word * p1, word * p2 )
{
    if ( (unsigned)(*p1) < (unsigned)(*p2) )
        return -1;
    if ( (unsigned)(*p1) > (unsigned)(*p2) )
        return 1;
    return 0;
}
int Abc_QuickSort1CompareDec( word * p1, word * p2 )
{
    if ( (unsigned)(*p1) > (unsigned)(*p2) )
        return -1;
    if ( (unsigned)(*p1) < (unsigned)(*p2) )
        return 1;
    return 0;
}
void Abc_QuickSort1( word * pData, int nSize, int fDecrease )
{
    int i, fVerify = 0;
    if ( fDecrease )
    {
        qsort( (void *)pData, (size_t)nSize, sizeof(word), (int (*)(const void *, const void *))Abc_QuickSort1CompareDec );
        if ( fVerify )
            for ( i = 1; i < nSize; i++ )
                assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
    }
    else
    {
        qsort( (void *)pData, (size_t)nSize, sizeof(word), (int (*)(const void *, const void *))Abc_QuickSort1CompareInc );
        if ( fVerify )
            for ( i = 1; i < nSize; i++ )
                assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
    }
}

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

  Synopsis    [QuickSort algorithm based on 2/3-way partitioning.]

  Description [This code is based on the online presentation 
  "QuickSort is Optimal" by Robert Sedgewick and Jon Bentley.
  http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf 

  The first 32-bits of the input data contain values to be compared. 
  The last 32-bits contain the user's data. When sorting is finished, 
  the 64-bit words are ordered in the increasing order of their value ]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Abc_SelectSortInc( word * pData, int nSize )
{
    int i, j, best_i;
    for ( i = 0; i < nSize-1; i++ )
    {
        best_i = i;
        for ( j = i+1; j < nSize; j++ )
            if ( (unsigned)pData[j] < (unsigned)pData[best_i] )
                best_i = j;
        ABC_SWAP( word, pData[i], pData[best_i] );
    }
}
static inline void Abc_SelectSortDec( word * pData, int nSize )
{
    int i, j, best_i;
    for ( i = 0; i < nSize-1; i++ )
    {
        best_i = i;
        for ( j = i+1; j < nSize; j++ )
            if ( (unsigned)pData[j] > (unsigned)pData[best_i] )
                best_i = j;
        ABC_SWAP( word, pData[i], pData[best_i] );
    }
}

void Abc_QuickSort2Inc_rec( word * pData, int l, int r )
{
    word v = pData[r];
    int i = l-1, j = r;
    if ( l >= r )
        return;
    assert( l < r );
    if ( r - l < 10 )
    {
        Abc_SelectSortInc( pData + l, r - l + 1 );
        return;
    }
    while ( 1 )
    {
        while ( (unsigned)pData[++i] < (unsigned)v );
        while ( (unsigned)v < (unsigned)pData[--j] )
            if ( j == l )
                break;
        if ( i >= j )
            break;
        ABC_SWAP( word, pData[i], pData[j] );
    }
    ABC_SWAP( word, pData[i], pData[r] ); 
    Abc_QuickSort2Inc_rec( pData, l, i-1 );
    Abc_QuickSort2Inc_rec( pData, i+1, r );
}
void Abc_QuickSort2Dec_rec( word * pData, int l, int r )
{
    word v = pData[r];
    int i = l-1, j = r;
    if ( l >= r )
        return;
    assert( l < r );
    if ( r - l < 10 )
    {
        Abc_SelectSortDec( pData + l, r - l + 1 );
        return;
    }
    while ( 1 )
    {
        while ( (unsigned)pData[++i] > (unsigned)v );
        while ( (unsigned)v > (unsigned)pData[--j] )
            if ( j == l )
                break;
        if ( i >= j )
            break;
        ABC_SWAP( word, pData[i], pData[j] );
    }
    ABC_SWAP( word, pData[i], pData[r] ); 
    Abc_QuickSort2Dec_rec( pData, l, i-1 );
    Abc_QuickSort2Dec_rec( pData, i+1, r );
}

void Abc_QuickSort3Inc_rec( word * pData, int l, int r )
{
    word v = pData[r];
    int k, i = l-1, j = r, p = l-1, q = r;
    if ( l >= r )
        return;
    assert( l < r );
    if ( r - l < 10 )
    {
        Abc_SelectSortInc( pData + l, r - l + 1 );
        return;
    }
    while ( 1 )
    {
        while ( (unsigned)pData[++i] < (unsigned)v );
        while ( (unsigned)v < (unsigned)pData[--j] )
            if ( j == l )
                break;
        if ( i >= j )
            break;
        ABC_SWAP( word, pData[i], pData[j] );
        if ( (unsigned)pData[i] == (unsigned)v ) 
            { p++; ABC_SWAP( word, pData[p], pData[i] ); }
        if ( (unsigned)v == (unsigned)pData[j] ) 
            { q--; ABC_SWAP( word, pData[j], pData[q] ); }
    }
    ABC_SWAP( word, pData[i], pData[r] ); 
    j = i-1; i = i+1;
    for ( k = l; k < p; k++, j-- ) 
        ABC_SWAP( word, pData[k], pData[j] );
    for ( k = r-1; k > q; k--, i++ ) 
        ABC_SWAP( word, pData[i], pData[k] );
    Abc_QuickSort3Inc_rec( pData, l, j );
    Abc_QuickSort3Inc_rec( pData, i, r );
}
void Abc_QuickSort3Dec_rec( word * pData, int l, int r )
{
    word v = pData[r];
    int k, i = l-1, j = r, p = l-1, q = r;
    if ( l >= r )
        return;
    assert( l < r );
    if ( r - l < 10 )
    {
        Abc_SelectSortDec( pData + l, r - l + 1 );
        return;
    }
    while ( 1 )
    {
        while ( (unsigned)pData[++i] > (unsigned)v );
        while ( (unsigned)v > (unsigned)pData[--j] )
            if ( j == l )
                break;
        if ( i >= j )
            break;
        ABC_SWAP( word, pData[i], pData[j] );
        if ( (unsigned)pData[i] == (unsigned)v ) 
            { p++; ABC_SWAP( word, pData[p], pData[i] ); }
        if ( (unsigned)v == (unsigned)pData[j] ) 
            { q--; ABC_SWAP( word, pData[j], pData[q] ); }
    }
    ABC_SWAP( word, pData[i], pData[r] ); 
    j = i-1; i = i+1;
    for ( k = l; k < p; k++, j-- ) 
        ABC_SWAP( word, pData[k], pData[j] );
    for ( k = r-1; k > q; k--, i++ ) 
        ABC_SWAP( word, pData[i], pData[k] );
    Abc_QuickSort3Dec_rec( pData, l, j );
    Abc_QuickSort3Dec_rec( pData, i, r );
}

void Abc_QuickSort2( word * pData, int nSize, int fDecrease )
{
    int i, fVerify = 0;
    if ( fDecrease )
    {
        Abc_QuickSort2Dec_rec( pData, 0, nSize - 1 );
        if ( fVerify )
            for ( i = 1; i < nSize; i++ )
                assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
    }
    else
    {
        Abc_QuickSort2Inc_rec( pData, 0, nSize - 1 );
        if ( fVerify )
            for ( i = 1; i < nSize; i++ )
                assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
    }
}
void Abc_QuickSort3( word * pData, int nSize, int fDecrease )
{
    int i, fVerify = 1;
    if ( fDecrease )
    {
        Abc_QuickSort2Dec_rec( pData, 0, nSize - 1 );
        if ( fVerify )
            for ( i = 1; i < nSize; i++ )
                assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
    }
    else
    {
        Abc_QuickSort2Inc_rec( pData, 0, nSize - 1 );
        if ( fVerify )
            for ( i = 1; i < nSize; i++ )
                assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
    }
}

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

  Synopsis    [Wrapper around QuickSort to sort entries based on cost.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_QuickSortCostData( int * pCosts, int nSize, int fDecrease, word * pData, int * pResult )
{
    int i;
    for ( i = 0; i < nSize; i++ )
        pData[i] = ((word)i << 32) | pCosts[i];
    Abc_QuickSort3( pData, nSize, fDecrease );
    for ( i = 0; i < nSize; i++ )
        pResult[i] = (int)(pData[i] >> 32);
}
int * Abc_QuickSortCost( int * pCosts, int nSize, int fDecrease )
{
    word * pData = ABC_ALLOC( word, nSize );
    int * pResult = ABC_ALLOC( int, nSize );
    Abc_QuickSortCostData( pCosts, nSize, fDecrease, pData, pResult );
    ABC_FREE( pData );
    return pResult;
}

//        extern void Abc_QuickSortTest();
//        Abc_QuickSortTest();

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_QuickSortTest()
{
    int nSize = 1000000;
    int fVerbose = 0;
    word * pData1, * pData2;
    int i;
    abctime clk = Abc_Clock();
    // generate numbers
    pData1 = ABC_ALLOC( word, nSize );
    pData2 = ABC_ALLOC( word, nSize );
    srand( 1111 );
    for ( i = 0; i < nSize; i++ )
        pData2[i] = pData1[i] = ((word)i << 32) | rand();
    Abc_PrintTime( 1, "Prepare ", Abc_Clock() - clk );
    // perform sorting
    clk = Abc_Clock();
    Abc_QuickSort3( pData1, nSize, 1 );
    Abc_PrintTime( 1, "Sort new", Abc_Clock() - clk );
    // print the result
    if ( fVerbose )
    {
        for ( i = 0; i < nSize; i++ )
            printf( "(%d,%d) ", (int)(pData1[i] >> 32), (int)pData1[i] );
        printf( "\n" );
    }
    // create new numbers
    clk = Abc_Clock();
    Abc_QuickSort1( pData2, nSize, 1 );
    Abc_PrintTime( 1, "Sort old", Abc_Clock() - clk );
    // print the result
    if ( fVerbose )
    {
        for ( i = 0; i < nSize; i++ )
            printf( "(%d,%d) ", (int)(pData2[i] >> 32), (int)pData2[i] );
        printf( "\n" );
    }
    ABC_FREE( pData1 );
    ABC_FREE( pData2 );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

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

// Creates a sequence of random numbers.
// http://www.codeproject.com/KB/recipes/SimpleRNG.aspx

#define NUMBER1  3716960521u
#define NUMBER2  2174103536u

unsigned Abc_Random( int fReset )
{
    static unsigned int m_z = NUMBER1;
    static unsigned int m_w = NUMBER2;
    if ( fReset )
    {
        m_z = NUMBER1;
        m_w = NUMBER2;
    }
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;
}
word Abc_RandomW( int fReset )
{
    return ((word)Abc_Random(fReset) << 32) | ((word)Abc_Random(fReset) << 0);
}

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


ABC_NAMESPACE_IMPL_END