sarray.h

任意给定三维空间的点集

/*--------------------------------------------------------------------
 * cutting - compute palanr cuttings
 * Copyright (C) 1998 Sariel Har-Peled
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA  02111-1307, USA.
\*--------------------------------------------------------------------*/

/*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
 * sarray.h -
 *    Small/static templated array.
\*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/

#ifndef  __SARRAY__H
#define  __SARRAY__H

#define  DASSERT( X, Y)   {if  ( !(X) ) { fprintf( stderr, Y ); assert(X); }}

/*----------------------------------------------------------------------
 * a function we need to implement a search.
\*----------------------------------------------------------------------*/

int        searchArrayEntry( const void  * ptr, int  size, int num,
                                    const void  * var );


int        searchTableEntry( const void  * ptr,
                                    int           localOffset,
                                    int           localSize,
                                    int           size,
                                    int           numEnt,
                                    const void  * var );
int        calcEntriesNum( void    * ptr, int      size );


template<class T>
void  * operator  new( size_t x, T  * ptr ) 
{
    //printf( "my new called!: %d\n", x ); 
    (void)x;
    return  (void *)ptr;
}

#define  SARRAY_NO_RANGE_CHECK

typedef  void    ( *ptrDestructFunc)( void  * ptr );
typedef  void    ( *ptrCopyConstructFunc)( void  * ptr, void  * src );

class  GenericArray
{
protected:
    bool        fInitialized;
    int         sizeEntry;
    int         maxSize;
    int         currSize;
    void      * ptrArr;
    int  id;
    ptrDestructFunc  ptrDestructor;
    ptrCopyConstructFunc  ptrCopyConstructor;

    void   dump() 
    {
        fflush( stdout );
        fflush( stderr );
        printf( "sarray dump\n" );
        printf( "   fInitialized: %d\n", fInitialized );
        printf( "   maxSize: %d\n", maxSize );
        printf( "   currSize: %d\n", currSize );
        printf( "   pArr: %p\n", (void *)ptrArr );
        printf( "   id: %d\n", id );
    }

    int   hash_gen( int  size_entry ) const
    {
        int  ind, val, jnd;
        const char  * ptr;

        val = 0;
        for  ( ind = 0; ind < getEntriesNum(); ind++ ) {
            ptr = (((char *)ptrArr) + ind * size_entry);
            for  ( jnd = size_entry-1; jnd >= 0; jnd-- ) {
                val = ((val ^ *ptr) << 3) + *ptr + val;
                ptr++;
            }
        }

        return  val;
    }

    void   term_Range( int  size ) 
    {
        (void)size;
        
        int  ind;
        char  * ptr;

        //printf( "term_Range - terminating range( %d )!\n", size );
        ptr = (char *)ptrArr;
        for  ( ind = 0; ind < size; ind++ ) {
            //intf( "ptrDestructor: %p\n", (void *)ptrDestructor );
            (*ptrDestructor)( ptr );
            ptr += sizeEntry;
        }       
    }


public:
    GenericArray( ptrDestructFunc  _ptrDestructor,
                  ptrCopyConstructFunc  _ptrConstructor )
    {
        ptrDestructor = _ptrDestructor;
        ptrCopyConstructor = _ptrConstructor;
    }

    void  init_funcs( ptrDestructFunc  _ptrDestructor,
                      ptrCopyConstructFunc  _ptrConstructor )
    {
        ptrDestructor = _ptrDestructor;
        ptrCopyConstructor = _ptrConstructor;
    }

    void  truncate( int      pos )
    {
        assert( pos >= 0 );
        if  ( currSize >= pos  &&   pos >= 0 )
            currSize = pos;
    }

    bool  isFull( void ) const
    {
        return   currSize >= maxSize;
    }

    bool  isEmpty( void ) const
    {
        return   currSize <= 0;
    }

    void  initToEmpty( void )
    {
        fInitialized = false;
    }

    int        getEntriesNum( void ) const
    {
        return    currSize;
    }
    int        size( void ) const
    {
        return    currSize;
    }

    void       reset( void )
    {
        term_Range( currSize );
        currSize = 0;
    }
};


template<class T>
class  Array : public GenericArray {
private:
    T         * pArr;
 
public:
    typedef  int        ( * ptrCompFunc )( const T     & a, const T    & b );
    typedef  int        ( * ptrCompFuncExt )( void  * data, const T     & a,
                                              const T    & b );

    static  void    destruct( void  * ptr ) 
    {
        //intf( "destructing: %p\n", (void *)ptr );
        ((T *)ptr)->~T();
    }
    static  void    copyConstruct( void  * ptr, void  * src ) 
    {
        ::new( (T *)ptr )  T( *(T *)src );
    }

                                                               
private:
    int               partitionExt( ptrCompFuncExt  pCompFunc,
                                    void  * data, long  left, 
                                    long  right );
   int               partition( ptrCompFunc  p_comp,
                                long  left, long  right );
   void             internalQSortExt( ptrCompFuncExt  pCompFunc,
                                      void  * data, int  left,
                                      int  right );
   void             internalQSort( ptrCompFunc   pCompFunc,
                                   int  left, int  right );

    /*
   void   termRange( int  size ) 
    {
        int  ind;

        for  ( ind = 0; ind < size; ind++ )
            (pArr + ind)->~T();
        //delete( pArr )  (pArr + ind);
    }*/


public:
    Array( void ) : GenericArray( destruct, copyConstruct )
    {
        sizeEntry = ((char *)(pArr + 1) - (char *)pArr);

        fInitialized = false;
    }

    void             quickSort( ptrCompFunc  pFunc );
    int              binarySearch( const T    & elem, ptrCompFunc  pCompFunc );
    int              binarySearchExt( const T    & elem, ptrCompFunc  pCompFunc,
                                      int  left, int  right );
    void             quickSortExt( ptrCompFuncExt  pCompFuncExt,
                                             void  * data );
    void             quickSortReverse( ptrCompFunc  pCompFunc );
    void             substractSet( Array     & set, ptrCompFunc  pCompFunc );
    void             substractSortedSet( Array      & set, ptrCompFunc  pCompFunc );

#ifdef  NO_THANKS
    void  permut()
    {
        int  newPos, ind;

        for   ( ind = 0; ind < currSize; ind++ ) {
            real  k;

            realRand(k);
            newPos = (to_int(k * (3 * currSize))) % currSize;
            assert( 0 <= newPos  &&  newPos < currSize );
            exchange( pArr[ ind ], pArr[ newPos ] );            
        }
    }
#endif  // NO_THANKS

    int   hash( void ) const
    {
        return  hash_gen( sizeof( T ) );
    }

        
    void  reverse( void )
    {
        int                ind;
        T                  tmp;

/*        printf( "reversing\n" );*/
        for  ( ind = (currSize / 2) - 1; ind >= 0; ind-- ) { 
            tmp = (*this)[ ind ];
            (*this)[ ind ] = (*this)[ currSize - ind - 1 ];
            (*this)[ currSize - ind - 1 ] = tmp;
        }
    }


    void  init( int   entriesNum, int  _id )
    {
        init_funcs( destruct, copyConstruct );
        sizeEntry = ( ((char *)(pArr + 1)) - (char *)pArr);

        id = _id;
        maxSize = entriesNum;
        currSize = 0;

        //pArr = new T[ max( sizeof( T ) * entriesNum, 256U ) ];
        //printf( "Malloc size: %d\n", (int)max( sizeof( T ) * entriesNum, 256U ) );

        pArr = (T *)malloc( max( sizeof( T ) * (2+ entriesNum), 256U ) );
        //printf( "%p malloc: %d\n", pArr, id );
        if  ( pArr == NULL ) {
          /*  DEBUG_SystemPanic( __POS__, "Fail to allocate array" ); */
            return;
        }
        ptrArr = pArr;
        fInitialized = true;
    }

    bool    resize( int        entriesNum )
    {
        int         size, ind;
        T         * pNewArr;
        
        ///printf( "resize - [%d]!\n", id );
        DASSERT( ( ((char *)&(pArr[ 1 ])) - ((char *)&(pArr[ 0 ])) ) 
                 == sizeEntry, "Size failure - not initialized?" );

	size = max( sizeof( T ) * (2 + entriesNum), 256U );
        pNewArr = (T *)malloc( size );

        if  ( pNewArr == NULL ) 
            return  false;
	memset( pNewArr, 0, size );

        //printf( "\tcurrSize: %d\n", currSize );
        for  ( ind = 0; ind < currSize; ind++ )
            ::new( pNewArr + ind )  T( pArr[ ind ] );

        //printf( "do termRange\n" );
        term_Range( currSize );
        free( (void *) pArr );

	pArr = pNewArr;
        ptrArr = pArr;
	maxSize = entriesNum;	

	return  true;
    }
    
    bool       grow( int          size ) 
    {
        if  ( size <= maxSize )
            return  true;
        
        return  resize( 256 + size * 4 );
    }

    const T  & top() const {
        assert( currSize > 0 );
        return  pArr[ currSize - 1 ];
    }


    const T &operator[]( int i )  const
    {
#ifndef SARRAY_NO_RANGE_CHECK
        DASSERT( 0 <= i  &&  i < currSize  &&  fInitialized, "range failure" );
#endif
        return( pArr[ i ] );
    }

    const T &getCellDirect( int i )  const
    {
        return( pArr[ i ] );
    }

    ~Array( void )
    {
        term();
    }

    T &operator[]( int i )
    {
#ifndef  SARRAY_NO_RANGE_CHECK
        DASSERT( 0 <= i  &&  i < currSize  &&  fInitialized, "range failure" );
#endif 
        return( pArr[ i ] );
    }    
    
    void       deleteEntry( const T   & var )
    {
        int                 ind;
        
        ind = searchEntry( var );
        if  ( ind >= 0 ) {
            pArr[ ind ] = pArr[ currSize - 1 ];
            currSize--;
        }
    }


    void       deleteEntryByPos( int       ind )
    {