sarray.t

任意给定三维空间的点集

/*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
 * sarray.t -
 *    Template functions. 
\*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/

#ifndef  __SARRAY__T
#define  __SARRAY__T


template<class T>
int              Array<T>::partition( int   ( * pCompFunc )( const T   & a, const T  & b ),
                                      long                   left,
                                      long                   right )
{
    long                   i, j, pivot;

    if  ( left >= right )
        return  left;

    pivot = ( left + right ) / 2;

    i = left;
    j = right;
    
    while  ( i < j )  {
        if  ( (*pCompFunc)( (*this)[ i ], (*this)[ j ] ) > 0 ) {
            if  ( i == pivot )
                pivot = j;
            else
                if  ( j == pivot )
                    pivot = i;
	    exchange( (*this)[ i ], (*this)[ j ] );
        }
        if  ( (*pCompFunc)( (*this)[ i ], (*this)[ pivot ] ) < 0 ) {
            i++;
        } else
            if  ( (*pCompFunc)( (*this)[ pivot ], (*this)[ j ] ) <= 0 ) {
                j--;
            }
    }

    return  (i > left)? i - 1 : left;
}

 
template<class T>
int              Array<T>::partitionExt(  
                   int  ( *pCompFunc )( void * data, const T     & a, const T    & b ),
                   void                 * data,
                   long                   left,
                   long                   right )
{
    long                   i, j, pivot;

    if  ( left >= right )
        return  left;

    pivot = ( left + right ) / 2;

    i = left;
    j = right;
    
    while  ( i < j )  {
        if  ( (*pCompFunc)( data, (*this)[ i ], (*this)[ j ] ) > 0 ) {
            if  ( i == pivot )
                pivot = j;
            else
                if  ( j == pivot )
                    pivot = i;
	    exchange( (*this)[ i ], (*this)[ j ] );
        }
        if  ( (*pCompFunc)( data, (*this)[ i ], (*this)[ pivot ] ) < 0 ) {
            i++;
        } else
            if  ( (*pCompFunc)( data, (*this)[ pivot ], (*this)[ j ] ) <= 0 ) {
                j--;
            }
    }

    return  (i > left)? i - 1 : left;
}

 
template<class T>
void             Array<T>::internalQSort(  int   ( * pCompFunc )( const T  & a, const T  & b ),
                                           int           left, int        right )
{
    long                    mid;

    if ( left < right ) {
        mid = partition( pCompFunc, left, right );
        //        printf( "mid: %d\n", (int)mid );
        internalQSort( pCompFunc, left, mid );
        internalQSort( pCompFunc,  mid + 1, right );
    }
}


template<class T>
void             Array<T>::internalQSortExt(  int   ( *pCompFunc )( void * data, const T     & a, const T    & b ),
                                             void     * data, int    left, int   right )
{
    long                    mid;

    if ( left < right ) {
        mid = partitionExt( pCompFunc, data, left, right );
        internalQSortExt( pCompFunc, data, left, mid );
        internalQSortExt( pCompFunc, data, mid + 1, right );
    }
}


template<class T>
void             Array<T>::quickSort(  int   ( * pCompFunc )( const T     & a, const T    & b ) )
{
    int  i;

    //  printf( "calling internalQSort( ?, %d, %d )\n", 0, currSize - 1 );
    internalQSort( pCompFunc, 0, currSize - 1 );
    
    for  ( i = 0; i < currSize - 2; i++ ) {
        if  (  (*pCompFunc)( (*this)[ i ], (*this)[ i + 1 ] ) > 0 ) {
            fprintf( stderr, "Quick sort failure\n" );
            exit( -1 );
        }
   } 
}


template<class T>
void             Array<T>::quickSortExt(  
                      int        ( * pCompFunc )( void * data, const T     & a, const T    & b ), void  * data )
{
    int  i;

    //  printf( "calling internalQSort( ?, %d, %d )\n", 0, currSize - 1 );
    internalQSortExt( pCompFunc, data, 0, currSize - 1 );
    
    for  ( i = 0; i < currSize - 2; i++ ) {
        if  (  (*pCompFunc)( data, (*this)[ i ], (*this)[ i + 1 ] ) > 0 ) {
            fprintf( stderr, "Quick sort failure\n" );
            exit( -1 );
        }
   } 
}


template<class T>
void    Array<T>::quickSortReverse(  int   ( * pCompFunc )( const T     & a, const T    & b ) )
{
    quickSort( pCompFunc );
    reverse();
}


template<class T>
void             Array<T>::substractSet( Array<T>            & set,
                                          int   ( * pCompFunc )( const T     & a, const T    & b ) )
{
//    FUNC_NAME                ( "Array<T>::substractSet" );
    int                        ind, ind1;

    for  ( ind = getEntriesNum() - 1; ind >= 0; ind-- ) {
         for  ( ind1 = 0; ind1 < set.getEntriesNum(); ind1++ ) {
            if  ( (*pCompFunc)( (*this)[ ind ], set[ ind1 ] ) == 0 ) {
                deleteEntryByPos( ind );
                break; 
            }
        }
    }
}


template<class T>  
int              Array<T>::binarySearch( const T    & elem,
                    int   ( * pCompFunc )( const T     & a, const T    & b ) )
{
    int  mid, ord, left, right;

    if  ( getEntriesNum() <= 0 )
        return  -1;

    left = 0;
    right = getEntriesNum() - 1;
    while   ( left < right ) {
        mid = ( left + right ) / 2; 
        ord = (*pCompFunc)( elem, (*this)[ mid ] );
    
        if  ( ord == 0 )
            return  mid;

        if  ( ord < 0 ) 
            right = mid - 1;
        else
            left = mid + 1;
    }
    if  ( ( left == right )  &&  ( (*pCompFunc)( elem, (*this)[ left ] ) == 0 ) )
        return  left;

    return  -1;    
}


template<class T>  
int              Array<T>::binarySearchExt( const T    & elem,
                             int   ( * pCompFunc )( const T    & a, const T   & b ),
                             int  left, int  right )
{
    int  mid, ord;

    if  ( getEntriesNum() <= 0  ||  left > right )
        return  -1;

    if  ( ( right - left ) <= 5 ) {
        while  ( left <= right ) {
            if  ( (*pCompFunc)( elem, (*this)[ left ] ) == 0 )
                return  left;
            left++;
        }
        return  -1;
    }
    assert( 0 <= left  &&  left <= right  &&  right < getEntriesNum() );

    while   ( left < right ) {
        mid = ( left + right ) / 2; 
        ord = (*pCompFunc)( elem, (*this)[ mid ] );
    
        if  ( ord == 0 )
            return  mid;

        if  ( ord < 0 ) 
            right = mid - 1;
        else
            left = mid + 1;
    }
    if  ( ( left == right )  &&  ( (*pCompFunc)( elem, (*this)[ left ] ) == 0 ) )
        return  left;

    return  -1;    
}


template<class T>
void             Array<T>::substractSortedSet( Array<T>            & set,
                                               int   ( * pCompFunc )( const T     & a, const T    & b ) )
{
//    FUNC_NAME                ( "Array<T>::substractSortedSet" );
    int                        ind, ind1, res, count, startEntriesCount, readPos;

    ind = ind1 = count = readPos = 0;
    startEntriesCount = getEntriesNum();

    while  ( readPos < getEntriesNum()  &&  ind1 < set.getEntriesNum() ) {
        res = (*pCompFunc)( (*this)[ readPos ], set[ ind1 ] );
 
        if  ( res == 0 ) {
            readPos++; 
            count++; 
            continue;   
        }
        if  ( res < 0 ) { 
            (*this)[ ind ] = (*this)[ readPos ];
            readPos++;
            ind++;
        } else
            ind1++;
    }     

    while  ( readPos < getEntriesNum() ) {
        (*this)[ ind ] = (*this)[ readPos ];
        readPos++;  
        ind++;
    } 

    truncate( ind );
 
    DASSERT( (startEntriesCount - count) == getEntriesNum(),
             "Subtraction failed" ); 
}


#endif  /* __SARRAY__T */


/*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
 *     
 * sarray.t - End of File
\*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/