/*-------------------------------------------------------------------- * 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_CHECKtypedef  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 )    {