/******************************************************************************************
> [KAZOE]                                                                                 <
> Initial Sofware by [Yannick Verdie, Florent Lafarge], Copyright (C) Inria (GEOMETRICA)  <
> All Rights Reserved, 2012, [Version 1.0].                                               <
******************************************************************************************/
#ifndef _QUAD_H_
#define _QUAD_H_

#include <vector>
#include <map>
#include <iostream>
#include <sstream>
#include <fstream>

#include <CImg.h>


using namespace cimg_library;

#define M_PI 3.141592654f

using namespace std;

class Point_cell
{
public:
	Point_cell(){};

	Point_cell(int x, int y, int level);

	Point_cell(const Point_cell& p);

	Point_cell& operator= (const Point_cell &p);

	void set(int x, int y, int level);

	int x()	const					{return	m_x;}
	int y()	const					{return	m_y;}
	void setCost(int val)			{m_levelP = val;}
	int getCost() const				{return m_levelP;}
	int getLevelP() const			{return	m_levelP;}

private:
	int m_x, m_y, m_levelP;

	friend bool operator< (const Point_cell& p1, const Point_cell& p2)
	{
		 if (p1.x() == p2.x()) return p1.y() < p2.y();
		 return p1.x() < p2.x();
	}
 
	friend bool operator== (const Point_cell& p1, const Point_cell& p2)
	{
		return p1.x() == p2.x() && p1.y() == p2.y() && p1.getCost() == p2.getCost();
	}

};

class node
{

public:
	
	//for root
   node(int x1, int y1, int x2, int y2, int level,int min_size, int max_level,float min_ratio, int threshold, int* image,  vector<Point_cell>	*list_points, map<Point_cell,int> *list_points_index, int limit_x = 1e9, int limit_y = 1e9);

	 //for child
    node(node* parent, int* index, int level, bool not_empty);
	 
   node* subnode(int i){ return m_subnode[i];} 
   ~node()
	{
		
		/*
		for (int i=0;i<4;i++)
			if (m_subnode[i])
			{
				free(m_subnode[i]);
				m_subnode[i] = NULL;
			}
		*/
	}
   bool isNotOutside(int* new_index);
   bool isEnd(){return m_subnode[0] == NULL && m_subnode[1] == NULL && m_subnode[2] == NULL && m_subnode[3] == NULL;}

   	//see Spatial Decomposition And Quadtree Mesh
	//http://www-tcad.stanford.edu/tcad/pubs/theses/danyang/Chap3.ps
	//-----------------------------------------------------------START---------------------------------------------------
	static void balance_tree(node* currentNode);

	static void recompute_vertices_neighbor(node* currentNode);


	//get/set index ----------------------------------
	//order is ul, ur, ll, lr
	node* subnodeinOrder(int i)					{switch(i) {case 0: return  m_subnode[3];
															case 1: return  m_subnode[2];
															case 2: return  m_subnode[0];
															case 3: return  m_subnode[1];
															};return  m_subnode[0];
												} 
   inline int indexFace(int i)					{switch(i) {case 0: return m_index_points_in_vector[6];
															case 1: return m_index_points_in_vector[8];
															case 2: return m_index_points_in_vector[2];
															case 3: return m_index_points_in_vector[0];
															};return 0;
												}
   	inline int getIndexCenter()					{return m_index_points_in_vector[4];};
	inline int getIndexPmi(int i)				{switch(i) {case 0: return m_index_points_in_vector[3];//index mid before
															case 1: return m_index_points_in_vector[7];
															case 2: return m_index_points_in_vector[5];
															case 3: return m_index_points_in_vector[1];
															};return 0;
												}
	inline int getIndexPmj(int i)				{switch(i) {case 0: return m_index_points_in_vector[7];//index mid after
															case 1: return m_index_points_in_vector[5];
															case 2: return m_index_points_in_vector[1];
															case 3: return m_index_points_in_vector[3];
															};return 0;
												}
	
   void setLevel(int index,int val)			    {if (index == -1)return; ms_list_points->at(index).setCost(val);};
	int getLevel(int index)						{if (index == -1)return -1; return ms_list_points->at(index).getCost();};
	inline int getLevelQ()						{return m_levelQ;}
	inline int getLevelP(int i)					{return getLevel(indexFace(i));};
	inline int getLevelPi(int i)				{return (i == 0 ? getLevel(indexFace(3)) : getLevel(indexFace(i-1)) ) ;};
	inline int getLevelPj(int i)				{return (i == 3 ? getLevel(indexFace(0)) : getLevel(indexFace(i+1)) ) ;};
	inline int getLevelPmi(int i)				{return getLevel(getIndexPmi(i));};
	inline int getLevelPmj(int i)				{return getLevel(getIndexPmj(i));};
	inline int getLevelPc()						{return getLevel(getIndexCenter());};

	inline void setLevelP(int i, int val)		{setLevel(indexFace(i),val);};
	inline void setLevelPc(int a)				{setLevel(getIndexCenter(),a);};
	inline void setLevelPmi(int i,int a)		{setLevel(getIndexPmi(i),a);};
	inline void setLevelPmj(int i, int a)		{setLevel(getIndexPmj(i),a);};

private:
	static int ms_minsize;
	static int ms_max_level;
	static int ms_min_ratio;  //if we have more than that number of candidate, we subdivise
	static int ms_threshold;	  //if a pixel has a value higher than this threshold, it is a candidate
	static int m_limit_x, m_limit_y;
	static std::vector<Point_cell>	*ms_list_points;
	static std::map<Point_cell, int>     *ms_map_points_index;
	static int* ms_image;   static int ms_w;  static int ms_h;

	int m_size, m_levelQ;
	node* m_subnode[4];//ll, lr, ur, ul
	node* m_parent;
	int m_index_points_in_vector[9];

		
	
	void ModifyLCF();

	bool isIrregular();

	void SubQuadrantGeneration();

	//------------------------------------------------------

	void init(int level,  int* ind, bool recursive_build);

   	bool isWithDataInside(int* index);

	 
	std::vector<Point_cell> get_and_update_Neighbor();

	node* SubQuadrant(int a, bool recursive_build); 
};

class ImgSaver
{
public:
	 ImgSaver(int* vecValues ,int hwidth,int hheight );
	 ImgSaver(int hwidth,int hheight );

	 ~ImgSaver();

	void applyTo ( int x, int y );

	void applyTo ( int x, int y , int val)   ;

	void increase ( int x, int y )   ;

	void blank();


	void createColorMap ( int min , int max) ;
	void createColorMap_Florent( int min , int max);

	void save ( const char* const pathPicture );

	int getVal(int x, int y){return (*ptrCImgInt)(x,y,0,0);}
	int getVal_i(int pos,int x, int y){return (*ptrCImgInt)(x,y,0,pos);}

	int getWidth(){return width;};
	int getHeight(){return height;};

private:
	CImg<int>* ptrCImgInt;
	int width; int height;

};

class cell
{
public:
	cell(){}
	cell(int x, int y, int w, int h)
	{
		m_x = x; m_y = y;  m_w = w;  m_h = h;
	}
	cell& operator=(const cell& rhs) 
    { 
		m_x = rhs.m_x; m_y = rhs.m_y;  m_w = rhs.m_w;  m_h = rhs.m_h;
		return *this;  
    }
	int size(){return m_w*m_h;}

	void draw(ImgSaver *saver)
	{
		for (int i=m_x;i<m_x+m_w && i < saver->getWidth();i++)
		{
			saver->applyTo ( i,m_y, 255 );
			saver->applyTo ( i,m_h+m_y, 255 );
		}

		for (int j=m_y;j<m_y+m_h && j < saver->getHeight();j++)
		{
			saver->applyTo ( m_x,j, 255 );
			saver->applyTo ( m_w+m_x,j, 255 );
		} 

	}
	int increase(ImgSaver *saver)
	{		
		int max = 0;

		for (int i=m_x;i<m_x+m_w && i < saver->getWidth();i++)
			for (int j=m_y;j<m_y+m_h && j < saver->getHeight();j++)
			{
				saver->applyTo ( i,j, saver->getVal(i,j) + 1);

				if (saver->getVal(i,j) > max) max = saver->getVal(i,j);
			}

		return max;
	}

	int increase(ImgSaver *saver, int val)
	{	
		int max = 0;

		for (int i=m_x;i<m_x+m_w && i < saver->getWidth();i++)
			for (int j=m_y;j<m_y+m_h && j < saver->getHeight();j++)
			{
				saver->applyTo ( i,j, saver->getVal(i,j) + val);

				if (saver->getVal(i,j) > max) max = saver->getVal(i,j);
			}

		return max;
	}

	int m_x ,m_y ,m_w ,m_h;
};

class quadtree
{
public:

	quadtree(int* image, int w, int h, int min_size, bool initRand = true, int elargeSize = -1, bool force_squared_and_min_size = false);

	quadtree(int* image, int w, int h, bool initRand = true);

	~quadtree();

	void prepare();
	void prepare(node* n, int a);
	void coalescingMem();

	unsigned int getOffset(int method = 0);
	unsigned int getCDF(int offset);
	unsigned int getNbCells(int offset);
	unsigned int getStartIndex(int offset);//for arrayx, ...
	unsigned int getSizeCell(int offset){if (m_give_index)return m_w/(m_coeff_multi*pow(2.,offset/4)); return m_w/pow(2.,offset/4);}

	void kill(node* n);

	void saveImage(char* Path, char* name);
	void draw(char*  ptrPath);
	void draw_grid(int offset, std::string Path, std::string name);
	void draw_grid_coal(int offset, std::string Path, std::string name);
	void draw_cells(ImgSaver *saver, node* n, int color = 255) ;
	void draw_levels(std::string Path, std::string name, bool blackImage = false);
	void draw_cell(ImgSaver *saver, int x1, int y1, int x2, int y2, bool drawCenter = false, int color = 255);
	void draw_pixelMap(std::string Path, std::string name);
	void draw_pixelMap_pretty(std::string Path, std::string name);
	void draw_pixelMap_grid(std::string Path, std::string name)	;
	
	void balance()   ;

	vector< vector<vector<cell> > > getList(){return list_cells;}
	int getWidth()   {return m_w;};
	int get_avg_cell(){return m_avg_cell;}
	//int getSizeCell(int level) {if (m_force_squared_and_min_size) return (m_w_image_orig+2*m_border)/pow(2.,level);else return list_cells[level*4][0][0].m_w;);
	bool isConstrained(){return m_force_squared_and_min_size;};

private:
	const static int m_coeff_multi = 10;	//use for map on manifold
	int* m_image;
	bool m_force_squared_and_min_size;
	int m_border;
	int m_w_image_orig ,m_h_image_orig;
	int m_avg_cell;
	int m_min_size;
	bool m_give_index;//ask index instead of real position during prepare and coalMemory
	int m_w; int m_h;
	node* m_rootnode;
	vector<Point_cell>	    list_points;
	map<Point_cell,int> 	map_point_index;
	void draw_cells_fromLevel(ImgSaver *saver, node* n, int level,bool *more);

	//Manifold<PointLidar> m_manifold;	 //use in 3D case on manifold



//--------------------for prepare:
private:
	vector< vector<vector<cell> > > list_cells;
	//list_cells[i] cells at level i
	//list_cells[i][j] cells at level i, grid j (j E [ 0, 3] )
	//list_cells[i][j][k] cell k at level i, grid j (j E [ 0, 3] )

	vector<unsigned int> CDF;//to celect the level and grid, and also the ofsset for coalescing memory
	vector<unsigned int> nb_cells;
public:
	vector<unsigned int> arrayx;  
	vector<unsigned int> arrayy; 
	vector<unsigned int> arrayw;   
	vector<unsigned int> arrayh;
};


#endif