/**
    \file DistanceTransform.h
    Header file for DistanceTransform class which, given and input
    binary image, calculates the corresponding distance transform via
    various methods.

    \author George J. Grevera, Ph.D., ggrevera@sju.edu

    Copyright (C) 2002, George J. Grevera

    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.

    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 or from http://www.gnu.org/licenses/gpl.txt.

    This General Public License does not permit incorporating this
    code into proprietary programs.  (So a hypothetical company such
    as GH (Generally Hectic) should NOT incorporate this code into
    their proprietary programs.)
 */
#ifndef DistanceTransform_h
#define DistanceTransform_h

#include <assert.h>
#include <float.h>
#include <limits.h>

#include <math.h>
/// Define the sqrt(2) if not defined in math.h (such as the Windows NiceTry
/// compiler).
#ifndef M_SQRT2
    #define M_SQRT2     1.41421356237309504880
#endif

#include <stdio.h>
//----------------------------------------------------------------------
/// an abstract distance transform class
class DistanceTransform {

public:
    /**
     * an integer representing infinity (but one such that smaller values
     * may still be added to it)
     */
    static const int     IntInfinity;
    /**
     * a double representing infinity (but one such that smaller values
     * may still be added to it)
     */
    static const double  FloatInfinity;

    /// construct a distance transform object for an image of size (xSize,ySize).
    /**
     * if 'unload' is true, transforms that use ratios of integers should convert
     * their integer results to the actual double values (of the ratios).
     */
    DistanceTransform    ( const int xSize, const int ySize,
                           const bool unload=true );
    virtual ~DistanceTransform   ( );

    /// calculate the distance transform
    virtual void doTransform ( const unsigned char* const I ) = 0;

    /// return the distance value assigned to a particular position
    inline double getD   ( const int x, const int y ) const {
        if (dD != NULL)  return dD[sub(x,y)];
        //otherwise, use int's
        assert( iD!=NULL );
        return iD[sub(x,y)];
    }

    /// return the "parent" (border point) associated with this point
    /**
     * @param x is the x location
     * @param y is the y location
     * @param px is the parent's x location to be returned
     * @param py is the parent's y location to be returned
     * @return true if the parent is know; otherwise false.
     */
    virtual inline bool getP ( const int x, const int y, int& px, int& py )
    const {
        px = py = -1;
        return false;
    }

protected:
    int        xSize;  ///< integer size (width) in pixels
    int        ySize;  ///< integer size (height) in pixels
    //calculated distance transforms (some distance transforms use int's
    // and others use double's to represent the distance values
    double*    dD;     ///< result of distance transform (as doubles)
    int*       iD;     ///< the calculated distance transform (as ints)

    /// DistanceTransform::P class.  Simply a 2D point.
    class P {
        public:
            int x;
            int y;
            inline P ( const int x, const int y ) {
                this->x = x;
                this->y = y;
            }
    };

    /// given a point (x,y) in an image, this method returns the corresponding
    /// 1d subscript into the 1d image array
    inline int sub ( const int x, const int y ) const {
        if (x<0 || x>=this->xSize) {
            assert( x>=0 && x<this->xSize );
        }
        if (y<0 || y>=this->ySize) {
            assert( y>=0 && y<this->ySize );
        }
        assert( rowOffsets!=NULL );
        return rowOffsets[y] + x;
    }

    /// init elements of the immediate interior (i.e., border points).
    template <class T>
        void initImmediate ( const unsigned char* const I, T* d,
                             const T halfDx=0, const T halfDy=0 ) {
            //initialize elements of the immediate exterior
            // & the immediate interior
            for (int y=1; y<ySize-1; y++) {
                for (int x=1; x<xSize-1; x++) {
                    if ( I[sub(x-1,y)] != I[sub(x,y)] ||
                         I[sub(x+1,y)] != I[sub(x,y)] ) {
                        if (halfDx < d[sub(x,y)])    d[sub(x,y)] = halfDx;
                    }
                    if ( I[sub(x,y-1)] != I[sub(x,y)] ||
                         I[sub(x,y+1)] != I[sub(x,y)] ) {
                        if (halfDy < d[sub(x,y)])    d[sub(x,y)] = halfDy;
                    }
                }
            }
    };

    template <class T>
        inline void check ( T* d, const int center, const int X, const int Y,
                            const T Delta ) {
            const int Near     = sub(X,Y);
            const T   possible = d[Near] + Delta;
            if (possible < d[center]) {
                d[center] = possible;
            }
    }

    virtual void borderCheck ( const unsigned char* const I );
    void cleanUp ( );
    void finish ( const unsigned char* const I, double* d );
    void finish ( const unsigned char* const I, int* d,
                  const int dx, const int dy );

private:
    int*       rowOffsets;    ///< used to speed up 2d array indexing
    bool       unloadFlag;    ///< convert ints to doubles (if necessary)
};

#endif
//----------------------------------------------------------------------

