#ifndef GREEDYINSERT_INCLUDED // -*- C++ -*-
#define GREEDYINSERT_INCLUDED

#include "Heap.hpp"
#include "Subdivision.hpp"
#include "Map.hpp"

class TrackedTriangle : public Triangle
{
    //
    // candidate position
    int sx, sy;


public:
    TrackedTriangle(Edge *e, int t=NOT_IN_HEAP)
	: Triangle(e, t)
    {
    }

    void update(Subdivision&);


    void setCandidate(int x,int y, real) { sx=x; sy=y; }
    void getCandidate(int *x, int *y) { *x=sx; *y=sy; }

	virtual real redo(void*);
};


class Candidate
{
public:

    int x, y;
    real import;
    real factor;

    Candidate() { import = -HUGE; factor = 1.0f; }

    void consider(int sx, int sy, real i, real f)
    {
		if( i*f > import*factor )
		{
			x = sx;
			y = sy;
			import = i;
			factor = f;
		}
    }
};

class Array2OfByte {
	protected:
		int w, h;
		unsigned char *data;

	public:
		Array2OfByte() { data = NULL; w=0; h=0; }
		Array2OfByte(int i, int j) { init(i, j); }
		~Array2OfByte() { if(data!=NULL) delete [] data; data = NULL; }

		void init(int i, int j, unsigned char set=0) { w=i; h=j; data = new unsigned char[w*h]; for(int a=0;a<w*h;a++) data[a] = set; }
		void init(int i, int j, unsigned char *d) { w=i; h=j; data = d; }

		inline unsigned char& operator()(int i,int j) { return data[j*w+i]; }
		inline int width() { return w; }
		inline int height() { return h; }

		const unsigned char *GetData(int i, int j) { return &data[j*w+i]; }
};

class Array2OfInt {
	protected:
		int w, h;
		int *data;

	public:
		Array2OfInt() { data = NULL; w=0; h=0; }
		Array2OfInt(int i, int j) { init(i, j); }
		~Array2OfInt() { if(data!=NULL) delete [] data; data = NULL; }

		void init(int i, int j, int set=0) { w=i; h=j; data = new int[w*h]; for(int a=0;a<w*h;a++) data[a] = set; }
		void init(int i, int j, int *d) { w=i; h=j; data = d; }

		inline int& operator()(int i,int j) { return data[j*w+i]; }
		inline int width() { return w; }
		inline int height() { return h; }

		const int *GetData(int i, int j) { return &data[j*w+i]; }
};

class GreedySubdivision : public Subdivision
{
    ::Heap *heap;
    int count;

protected:

    Map *H;

	int radius, lowPointCount, highPointCount;
	int lowPointCount_256, highPointCount_256;
	int lowPointCount_32, highPointCount_32;
	real oneOverH_P_Count;
	real oneOverH_P_Count_256;
	real oneOverH_P_Count_32;

    Triangle *allocFace(Edge *e);

    void compute_plane(PlaneX&, Triangle&, Map&);

    void scan_triangle_line(PlaneX& plane,
			    int y, real x1, real x2,
			    Candidate& candidate);

	bool radius_method, square_method, bigger_square_method, interest_method;

public:
    GreedySubdivision(Map *map, real);
    ~GreedySubdivision();

    Array2OfByte is_used;
    Array2OfByte interest_data;

	Array2OfInt are_used_256;
	Array2OfInt are_used_32;

    Edge *select(int sx, int sy, Triangle *t=NULL);

    Map& getData() { return *H; }

	int areUsed(int sx, int sy);
	real GetDensity(int sx, int sy);

    void scanTriangle(TrackedTriangle& t);
    int greedyInsert();

	void SetRadiusMethod(bool b=true) { radius_method = b; }
	void SetSquareMethod(bool b=true) { square_method = b; bigger_square_method = !b; }
	void SetBiggerSquareMethod(bool b=true) { square_method = !b; bigger_square_method = b; }
	void SetInterestMethod(bool b=true) { interest_method = b; }

    int pointCount() { return count; }
    real maxError();
    real rmsError();
    real eval(int x,int y);
};


//
// These are the possible values of is_used(x,y):
#define DATA_POINT_UNUSED  0
#define DATA_POINT_USED    1
#define DATA_POINT_IGNORED 2
#define DATA_VALUE_UNKNOWN 3

#endif