/*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
 * cache.h -
 *     Simple implementation of memoizatiom mechnism
 *. 
 * This code is copyrighted under the GPL by Sariel Har-Peled.
\*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/

#ifndef  __CACHE__H
#define  __CACHE__H


template<class T>
class Cache1d
{
private:
    int  n;
    T  * arr;
    bool  * arr_init;

public:
    Cache1d() {
        n = -1;
        arr = NULL;
        arr_init = NULL;
    }
    ~Cache1d() {
        free( arr );
        free( arr_init );
    }

    int  pos( int x ) const {
        assert( ( x >= 0 )  &&  ( x < n ) );
        return  x;
    }

    void  set( int  x, T  val ) {
        assert( arr != NULL );

        arr[ pos( x ) ] = val;
        arr_init[ pos( x ) ] = true;
    }

    void  set_undef( int  x  ) {
        assert( x < n );

        arr[ pos( x ) ] = 0;
        arr_init[ pos( x ) ] = false;
    }

    void  init( int _n ) {
        n = _n;
        assert( n >= 1 );

        arr = (T *)malloc( n * sizeof(T) );
        arr_init = (bool *)malloc( n * sizeof(bool) );
        assert( arr != NULL );
        for  ( int xnd = 0; xnd < n; xnd++ )
            set_undef( xnd );
    }

    bool   is_defined( int  x ) const {
        assert( arr != NULL );
        assert( arr_init != NULL );
        
        return   ( arr_init[ pos( x ) ] );
    }

    T  & get( int  x ) const {
        assert( x < n );
        assert( x >= 0 );
        assert( arr != NULL );

        return  arr[ pos( x ) ];
    }
};


template<class T>
class Cache2d
{
private:
    int  n_x, n_y;
    T     * arr;
    bool  * arr_init;

    int  pos( int x, int  y ) const {
        assert( x < n_x );
        assert( y < n_y );
        assert( x >= 0 );
        assert( y >= 0 );
        return  x * n_y + y;
    }

public:
    Cache2d() {
        n_x = n_y = -1;
        arr = NULL;
        arr_init = NULL;
    }
    ~Cache2d() {
        free( arr );
        free( arr_init );
    }

    void  set( int  x,  int  y, const T  & val ) {
        assert( arr != NULL );

        arr[ pos( x, y ) ] = val;
        arr_init[ pos( x, y ) ] = true;
    }

    void  set_undef( int  x,  int  y  ) {
        assert( x < n_x );

        arr[ pos( x, y ) ] = 0;
        arr_init[ pos( x, y ) ] = false;
    }

    void  init( int _n_x, int _n_y ) {
        n_x = _n_x;
        n_y = _n_y;
        assert( ( n_x >= 1 )  &&  (n_y >= 1) );

        arr = (T *)malloc( n_x*n_y * sizeof(T) );
        arr_init = (bool *)malloc( n_x*n_y * sizeof(bool) );

        assert( arr != NULL );
        assert( arr_init != NULL );

        for  ( int xnd = 0; xnd < n_x; xnd++ )
            for  ( int ynd = 0; ynd < n_y; ynd++ ) {
                set( xnd, ynd, 0 );
                set_undef( xnd, ynd );
            }
    }

    T  & get( int  x,  int  y ) const {
        assert( arr != NULL );
        
        return  arr[ pos( x, y ) ];
    }

    bool   is_defined( int  x,  int  y ) const {
        assert( arr != NULL );
        assert( arr_init != NULL );
        
        return   ( arr_init[ pos( x, y ) ] );
    }
};

#else   /* __CACHE__H */
#error  Header file cache.h included twice
#endif  /* __CACHE__H */

/* cache.h - End of File ------------------------------------------*/