package com.ethon.plugin;

import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.util.ArrayList;
import java.util.LinkedList;

import javax.swing.JOptionPane;

import com.ethon.DataBase;
import com.ethon.mode.DataPoint;
import com.ethon.tools.CoordTransfer;
import com.ethon.tools.CounterUtil;
import com.ethon.tools.ImageGenerator;
import com.ethon.ui.DataField;

/**
 * Hasta,short for Hierarchical grid-cluStering algorithm based on daTA field
 * Hasta uses two parameters, grid-number(k) and impact-factor-parameter(ifp)
 * 		k is used to quantize the feature space into k intervals in each dimension
 * 		ifp is used to calculate the impact factor sigma. (sigma=ifp*max(s), where
 * 				 max(s) is the maximum length of grid in each dimensions)
 * Noise in Hasta in filtered by a optional function f(min(x)). where min(x) is the 
 * 		minimal density of data objects in those found clustering grids.
 * Hasta consists of three steps:
 * 1	Initialize grids
 * 			Quantize feature space into grids and assign each data objects into grids;
 * 			Set the value of impact factor sigma;
 * 			Calculate first partial derivative potential value for each grid.
 * 
 * 2	identify clustering clusters
 * 			Since there is no need to accurately locate the clustering centers, Hasta
 * 			uses clustering grid instead. A clustering grid is the grid contains 
 * 			clustering center inside; 
 * 			A grid is a clustering only if MFL>=0 && MFR<=0. MFL and MFR here is the 
 * 			first partial derivative potential value of grid's left and right neighbor.
 * 
 * 3	detect edges
 * 			After clustering centers are identified, Hasta then starts to detect edges 
 * 			of cluster. this step is controlled by the change curve of grid's first partial
 * 			derivative potential value. Hasta reaches the edge when the first partial 
 * 			derivative potential value stops increasing.
 * 
 * 4	find full clusters
 * 			during the last step, all grids belong to edges are marked in the lookupTable. 
 * 			Hasta uses Flood-fill alogrithm to find full clusters in the original feature space.
 * 
 * @author ethonchan
 *
 */
public class Hasta {
	// 每个大网格的边所包含的小网格的数量
	private int IFP;
	// 小网格的边长、起点
	private double dx, dy, xmin, ymin;
	// 影响因子
	private double sigma;
	// 小网格类型的矩阵
	private Grid[][] steps;
	// 程序的开始运行时间
	private long start;
	// 聚类时过滤噪声的参数
	private int thread;
	// 每边包含小网格的数量
	private int K;
	// 小网格的标记矩阵
	private int[][] lookupTable;
	
	private BigGrid[][] grids;

	public Hasta(int K, int IFP) {
		start = System.currentTimeMillis();
		this.IFP = IFP;
		this.K=K;

		DataPoint[] points = DataBase.getInstance().getPoints();
		// 遍历找出每个网格的大小，并根据这个来设定影响因子
		xmin = Double.MAX_VALUE;
		ymin = Double.MAX_VALUE;
		double xmax = Double.MIN_VALUE;
		double ymax = Double.MIN_VALUE;
		steps = new Grid[K][K];

		for (DataPoint p : points) {
			double x = p.getCoord_X();
			double y = p.getCoord_Y();

			if (xmin > x)
				xmin = x;
			if (ymin > y)
				ymin = y;

			if (xmax < x)
				xmax = x;
			if (ymax < y)
				ymax = y;
		}
		dx = (xmax - xmin) / K;
		dy = (ymax - ymin) / K;
		sigma = Math.min(dx, dy);
		sigma = sigma * IFP;

		// 将每个数据点分配到相应的网格中，注意这里有可能有一部分网格为空
		for (DataPoint p : points) {
			double x = p.getCoord_X();
			double y = p.getCoord_Y();

			int xl = (int) Math.floor((x - xmin) / dx);
			int yl = (int) Math.floor((y - ymin) / dy);
			if (xl == K)
				xl = K - 1;
			if (yl == K)
				yl = K - 1;
			if (steps[xl][yl] == null)
				steps[xl][yl] = new Grid();

			steps[xl][yl].add(p);
		}

		// 确认小网格没有空的
		for (int x = 0; x < K; x++) {
			for (int y = 0; y < K; y++) {
				double xloc = xmin + dx / 2 + dx * x;
				double yloc = ymin + dy / 2 + dy * y;
				Grid grid = steps[x][y];
				if (grid == null) {
					grid = new Grid();
					grid.setCenter(xloc, yloc);
					steps[x][y] = grid;
				}
			}
		}

		// 初始化标记网格
		lookupTable = new int[K][K];
		for (int y = 0; y < K; y++) {
			for (int x = 0; x < K; x++) {
				lookupTable[x][y] = 0;
			}
		}
	}

	public void process() {
		// 标记小网格聚类矩阵，并且返回中心坐标
		ArrayList<Coord> centers = markCandidatePoints();
		// 找出聚类
		ArrayList<Cluster> clusters = searchCluster();
		// 修正聚类，某些不包含极大值的聚类被删除，并确保每个极大值都位于某个聚类中
		clusters = refineCluster(centers, clusters);
		long end = System.currentTimeMillis();
		String time = Long.toString(end - start) + "ms";

		// 准备绘图
		BufferedImage img = ImageGenerator.drawImage(null, DataBase.sLen);
//		img=showCoord(img);
//		img=showLargeCoord(img);

		Graphics g = img.getGraphics();
		DataPoint[] points = DataBase.getInstance().getPoints();
//		for (DataPoint p : points) {
//			ImageGenerator.show_DataPoint_on_Image(img, p, Color.BLACK);
//		}
		CoordTransfer tsf = new CoordTransfer();
		
		//此部分显示ResultMap中的聚类中心点
//		g.setColor(Color.black);
//		for(Coord c:centers){
//			SearchStepGrid sg = steps[c.x][c.y];
//			int[] coord = tsf.getPanelCoord(sg.getXloc(), sg.getYloc());
//			g.fillOval(coord[0]-4, coord[1]-4, 8, 8);
//		}
		
		//此部分显示标记后的ResultMap
//		g.setColor(Color.black);
//		SearchStepGrid sg = steps[0][0];
//		int[] coord1 = tsf.getPanelCoord(sg.getXloc(), sg.getYloc());
//		int[] coord2 = tsf.getPanelCoord(sg.getXloc()+dx, sg.getYloc()+dy);
//		int slenx=coord2[0]-coord1[0];
//		int sleny=coord2[1]-coord1[1];
//		
//		System.out.println(slenx+","+sleny);
//		for(int y=0;y<size;y++){
//			for(int x=0;x<size;x++){
//				int v=resultMap[x][y];
//				if(v==0)	continue;
//				double xloc=xmin+dx*x;
//				double yloc=ymin+dy*y;
//				int[] coord = tsf.getPanelCoord(xloc, yloc);
//				
//				g.fillRect(coord[0], coord[1], slenx, sleny);
//			}
//		}
		
//		此部分为显示大网格简化后的数据点		
//		int K=size/stepParam;
//		int ct=0;
//		for(int y=0;y<K;y++){
//			for(int x=0;x<K;x++){
//				DataGrid grid = grids[x][y];
//				if(ct<grid.getWeight())	ct=grid.getWeight();
//			}
//		}
//		
//		g.setColor(Color.black);
//		for(int y=0;y<K;y++){
//			for(int x=0;x<K;x++){
//				DataGrid grid = grids[x][y];
//				double xloc = grid.getXloc();
//				double yloc = grid.getYloc();
//				double w=grid.getWeight();
//				int sl=(int) Math.round(12*w/ct);
//				int[] coord = tsf.getPanelCoord(xloc, yloc);
//				g.fillOval(coord[0]-sl/2, coord[1]-sl/2, sl, sl);
//			}
//		}
		
				
		// 为每个cluster分配颜色并输出
		for (int i = 0, len = clusters.size(); i < len; i++) {
			Cluster cluster = clusters.get(i);
			float t = (float) (cluster.clusterLabel - 1) / len;
			Color color = CounterUtil.HLStoRGB(t, (float) 0.5, (float) 0.5);
			ArrayList<Coord> list = cluster.getCoordList();
			g.setColor(Color.black);
			g.setFont(new Font("SansSerif", Font.BOLD, 18));
			int[] coord = tsf.getPanelCoord(cluster.xloc, cluster.yloc);
			g.drawString(Integer.toString(cluster.clusterLabel), coord[0],
					coord[1]);
			for (Coord c : list) {
				Grid grid = steps[c.x][c.y];
				ArrayList<DataPoint> plist = grid.list;
				for (DataPoint point : plist) {
					ImageGenerator.show_DataPoint_on_Image(img, point, color);
				}
			}
		}

		g.setColor(Color.black);
		g.drawString("K=" + K  + ",IFP=" + IFP
				+ ",t=" + thread, 0, DataBase.sLen - 40);
		g.drawString("共" + points.length + "个点，聚成" + clusters.size() + "个类", 0,
				DataBase.sLen - 20);

		g.drawString(time, 0, DataBase.sLen - 5);
		g.dispose();

		g.dispose();
		DataField.updateImagePanel(img);
	}

	/**
	 * 根据resultMap的标记情况搜索聚类
	 */
	ArrayList<Cluster> searchCluster() {
		// 用洪泛法标记小网格类别矩阵
		int clusterSize = labelResultMap();
		ArrayList<Cluster> clusters = new ArrayList<Cluster>();
		for (int i = 0; i < clusterSize; i++)
			clusters.add(new Cluster(i + 1));
		for (int y = 0; y < K; y++) {
			for (int x = 0; x < K; x++) {
				int v = lookupTable[x][y];
				if (v < 1)
					continue;
				Cluster cluster = clusters.get(v - 1);
				cluster.addCoord(new Coord(x, y));
				clusters.set(v - 1, cluster);
			}
		}
		return clusters;
	}

	// 修正聚类，某些不包含极大值的聚类被删除，并确保每个极大值都位于某个聚类中
	ArrayList<Cluster> refineCluster(ArrayList<Coord> centers,
			ArrayList<Cluster> clusters) {
		// 将没有包含centers中的小cluster去掉
		ArrayList<Cluster> result = new ArrayList<Cluster>();
		for (Cluster c : clusters) {
			ArrayList<Coord> list = c.getCoordList();
			boolean pass = false;
			for (Coord center : centers) {
				if (list.contains(center)) {
					pass = true;
					break;
				}
			}
			if (pass)
				result.add(c);
		}
		
		// 重新为cluster分配序号
		for (int i = 0; i < result.size(); i++) {
			Cluster cluster = result.get(i);
			cluster.clusterLabel = i + 1;
			result.set(i, cluster);
		}

		return result;
	}

	// 用洪泛法标记小网格类别矩阵
	// 返回类别的数量
	private int labelResultMap() {
		int clusterLabel = 1;

		for (int y = 0; y < K; y++) {
			for (int x = 0; x < K; x++) {
				if (lookupTable[x][y] == -1) {
					floodFillResultMap(x, y, clusterLabel++);
				}
			}
		}
		return --clusterLabel;
	}

	// 用洪泛法搜索每个小网格的四邻域
	private void floodFillResultMap(int x, int y, int label) {
		LinkedList<Coord> list = new LinkedList<Coord>();
		list.addFirst(new Coord(x, y));
		while (list.size() != 0) {
			Coord c = list.removeLast();
			if (lookupTable[c.x][c.y] == -1) {
				lookupTable[c.x][c.y] = label;
				if (c.x > 0)
					list.add(new Coord(c.x - 1, c.y));
				if (c.x < K - 1)
					list.add(new Coord(c.x + 1, c.y));
				if (c.y > 0)
					list.add(new Coord(c.x, c.y - 1));
				if (c.y < K - 1)
					list.add(new Coord(c.x, c.y + 1));
			}
		}
	}

	/**
	 * resultMap中数据密集点标记为-1，并返回中心坐标
	 */
	ArrayList<Coord> markCandidatePoints() {
		// 首先计算x偏导和y偏导
		countPotential();

		// 然后找出聚类中心点
		ArrayList<Coord> xlist = getCanPointsOnX();
		ArrayList<Coord> ylist = getCanPointsOnY();
		ArrayList<Coord> centers = new ArrayList<Coord>();
		thread=Integer.MAX_VALUE;
		for (Coord c : xlist) {
			if (ylist.contains(c)){
				if(steps[c.x][c.y].pnumber<thread)	thread=steps[c.x][c.y].pnumber;
				centers.add(c);
			}
		}

		// 根据聚类中心点，找出所有的数据密集点
		ArrayList<Coord> dxlist = getDensityCoordsOnX(xlist);
		ArrayList<Coord> dylist = getDensityCoordsOnY(ylist);
		for (Coord c : dxlist) {
			if (!dylist.contains(c))
				dylist.add(c);
		}
		
		String input = JOptionPane.showInputDialog("请输入聚类的密度阀值",Integer.toString(thread-1>0?thread-1:0));
		thread=Integer.parseInt(input.trim());

		// 剔除密集点中的噪声，并且标记出非噪声的密集点
		for (Coord c : dylist) {
			int x = c.x;
			int y = c.y;

			if (steps[x][y].pnumber > thread) {
				if (lookupTable[x][y] == 0)
					lookupTable[x][y] = -1;
			}
		}
		return centers;
	}

	private ArrayList<Coord> getCanPointsOnX() {
		ArrayList<Coord> points = new ArrayList<Coord>();

		for (int y = 0; y < K; y++) {
			for (int x = 1; x < K; x++) {
				double dpx1 = steps[x - 1][y].getXdp();
				double dpx2 = steps[x][y].getXdp();

				if (dpx1 == 0 && dpx2 < 0)// dpx1是
					points.add(new Coord(x - 1, y));
				else if (dpx1 > 0 && dpx2 == 0)// dpx2是
					points.add(new Coord(x, y));
				else if (dpx1 > 0 && dpx2 < 0)// 看谁的绝对值较小
				{
					double t = dpx1 + dpx2;
					if (t > 0)
						points.add(new Coord(x, y));
					else
						points.add(new Coord(x - 1, y));
				}
			}
		}

		return points;
	}

	private ArrayList<Coord> getDensityCoordsOnX(ArrayList<Coord> centers) {
		int know = steps.length;
		ArrayList<Coord> result = new ArrayList<Coord>();
		for (Coord c : centers) {
			int x = c.x;
			int y = c.y;
			result.add(c);

			while (--x >= 0) {
				double dpx1 = steps[x][y].getXdp();
				double dpx2 = steps[x + 1][y].getXdp();

				if (dpx1 < dpx2)
					break;
				else
					result.add(new Coord(x, y));
			}

			x = c.x;
			y = c.y;
			while (++x < know) {
				double dpx1 = steps[x - 1][y].getXdp();
				double dpx2 = steps[x][y].getXdp();

				if (dpx1 < dpx2)
					break;
				else
					result.add(new Coord(x, y));

			}
		}
		return result;
	}

	private ArrayList<Coord> getCanPointsOnY() {
		ArrayList<Coord> points = new ArrayList<Coord>();
		for (int x = 0; x < K; x++) {
			for (int y = 1; y < K; y++) {
				double dpy1 = steps[x][y - 1].getYdp();
				double dpy2 = steps[x][y].getYdp();

				if (dpy1 == 0 && dpy2 < 0)// dpy1是
					points.add(new Coord(x, y - 1));
				else if (dpy1 > 0 && dpy2 == 0)// dpy2是
					points.add(new Coord(x, y));
				else if (dpy1 > 0 && dpy2 < 0)// 看谁的绝对值较小
				{
					double t = dpy1 + dpy2;
					if (t > 0)
						points.add(new Coord(x, y));
					else
						points.add(new Coord(x, y - 1));
				}
			}
		}

		return points;
	}

	private ArrayList<Coord> getDensityCoordsOnY(ArrayList<Coord> centers) {
		int know = steps.length;
		ArrayList<Coord> result = new ArrayList<Coord>();
		for (Coord c : centers) {
			int x = c.x;
			int y = c.y;
			result.add(c);

			while (--y >= 0) {
				double dpy1 = steps[x][y].getYdp();
				double dpy2 = steps[x][y + 1].getYdp();

				if (dpy1 < dpy2)
					break;
				else
					result.add(new Coord(x, y));
			}

			x = c.x;
			y = c.y;
			while (++y < know) {
				double dpy1 = steps[x][y - 1].getYdp();
				double dpy2 = steps[x][y].getYdp();

				if (dpy1 < dpy2)
					break;
				else
					result.add(new Coord(x, y));

			}
		}
		return result;
	}

	private BufferedImage showCoord(BufferedImage img) {
		CoordTransfer tsf = new CoordTransfer();
		Graphics g = img.getGraphics();
		g.setColor(Color.gray);
		// x的最大值，y的最大值
		int[] len = tsf.getPanelCoord(xmin + dx * K, ymin + dy * K);

		// 画出横的网格线
		for (int y = 0; y <= K; y++) {
			double yloc = ymin + dy * y;
			int[] coord = tsf.getPanelCoord(xmin, yloc);

			g.drawLine(coord[0], coord[1], len[0], coord[1]);
		}

		// 画出纵的网格线
		for (int x = 0; x <= K; x++) {
			double xloc = xmin + dx * x;
			int[] coord = tsf.getPanelCoord(xloc, ymin);

			g.drawLine(coord[0], coord[1], coord[0], len[1]);
		}

		g.dispose();
		return img;
	}
	
	private BufferedImage showLargeCoord(BufferedImage img) {
		CoordTransfer tsf = new CoordTransfer();
		Graphics g = img.getGraphics();
		g.setColor(Color.black);
		// x的最大值，y的最大值
		int[] len = tsf.getPanelCoord(xmin + dx * K, ymin + dy * K);

		// 画出横的网格线
		for (int y = 0; y <= K; y+=IFP) {
			double yloc = ymin + dy * y;
			int[] coord = tsf.getPanelCoord(xmin, yloc);

			g.drawLine(coord[0], coord[1], len[0], coord[1]);
		}

		// 画出纵的网格线
		for (int x = 0; x <= K; x+=IFP) {
			double xloc = xmin + dx * x;
			int[] coord = tsf.getPanelCoord(xloc, ymin);

			g.drawLine(coord[0], coord[1], coord[0], len[1]);
		}

		g.dispose();
		return img;
	}

	// 计算每个小网格的x偏导以及y偏导
	// dpx=(xi-x)*mi*Math.pow(e,-dist2/sigma2)
	// dpy=(yi-y)*mi*Math.pow(e,-dist2/sigma2)
	private void countPotential() {
		// 根据小网格初始化大网格
		int BK = K / IFP;
		grids = new BigGrid[BK][BK];
		for (int ky = 0; ky < BK; ky++) {
			for (int kx = 0; kx < BK; kx++) {
				double xall = 0;
				double yall = 0;
				int pall = 0;
				double xloc = -1;
				double yloc = -1;
				for (int y = 0; y < IFP; y++) {
					for (int x = 0; x < IFP; x++) {
						int xnum = kx * IFP + x;
						int ynum = ky * IFP + y;

						xall += steps[xnum][ynum].getXall();
						yall += steps[xnum][ynum].getYall();
						pall += steps[xnum][ynum].getWeight();
					}
				}
				if (pall > 0) {
					BigGrid grid = new BigGrid(xall / pall, yall / pall, pall);
					grids[kx][ky] = grid;
				} else {
					int c = IFP * IFP;
					BigGrid grid = new BigGrid(xloc / c, yloc / c, pall);
					grids[kx][ky] = grid;
				}

			}
		}

		// 以上为划分网格的部分

		// 计算x偏导和y偏导
		double sigma2 = sigma * sigma;
		for (int x = 0; x < K; x++) {
			for (int y = 0; y < K; y++) {
				double xloc = steps[x][y].getXloc();
				double yloc = steps[x][y].getYloc();
				double dpx = 0;
				double dpy = 0;

				// 每一个网格的重心为坐标点，网格内点的数量为权重，计算势值
				for (int bx = 0; bx < BK; bx++) {
					for (int by = 0; by < BK; by++) {
						BigGrid bg = grids[bx][by];
						double dx = bg.getXloc() - xloc;
						double dy = bg.getYloc() - yloc;
						double dist2 = dx * dx + dy * dy;
						double temp = bg.getWeight()
								* Math.pow(Math.E, -dist2 / sigma2);
						dpx += dx * temp;
						dpy += dy * temp;
					}
				}
				steps[x][y].setXdp(dpx);
				steps[x][y].setYdp(dpy);
			}
		}
	}

	private class Coord {
		int x, y;

		public Coord(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + getOuterType().hashCode();
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Coord other = (Coord) obj;
			if (!getOuterType().equals(other.getOuterType()))
				return false;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}

		private Hasta getOuterType() {
			return Hasta.this;
		}

	}

	private class BigGrid {
		private double xloc = -1;
		private double yloc = -1;
		private int pnumber = 0;

		public BigGrid(double xloc, double yloc, int pnumber) {
			this.xloc = xloc;
			this.yloc = yloc;
			this.pnumber = pnumber;
		}

		public double getXloc() {
			return xloc;
		}

		public double getYloc() {
			return yloc;
		}

		public int getWeight() {
			return pnumber;
		}
	}

	private class Cluster {
		int clusterLabel;
		double xloc = -1;
		double yloc = -1;
		ArrayList<Coord> list;

		public Cluster(int clusterLabel) {
			this.clusterLabel = clusterLabel;
			list = new ArrayList<Coord>();
		}

		void addCoord(Coord c) {
			if (xloc == -1) {
				xloc = steps[c.x][c.y].getXloc();
				yloc = steps[c.x][c.y].getYloc();
			}
			list.add(c);
		}

		ArrayList<Coord> getCoordList() {
			return list;
		}
	}

	private class Grid {
		private double xall = 0;
		private double yall = 0;
		private double xloc = -1;
		private double yloc = -1;
		private double xdp = -1;
		private double ydp = -1;
		private int pnumber = 0;
		private ArrayList<DataPoint> list = new ArrayList<DataPoint>();

		public void add(DataPoint point) {
			pnumber++;
			xall += point.getCoord_X();
			yall += point.getCoord_Y();
			list.add(point);
		}

		public void setCenter(double xloc, double yloc) {
			this.xloc = xloc;
			this.yloc = yloc;
		}

		public double getXall() {
			return xall;
		}

		public double getYall() {
			return yall;
		}

		public double getXloc() {
			if (xloc == -1) {
				if (pnumber != 0)
					xloc = xall / pnumber;
			}
			return xloc;
		}

		public double getYloc() {
			if (yloc == -1) {
				if (pnumber != 0)
					yloc = yall / pnumber;
			}

			return yloc;
		}

		public int getWeight() {
			return pnumber;
		}

		public double getXdp() {
			return xdp;
		}

		public void setXdp(double xdp) {
			this.xdp = xdp;
		}

		public double getYdp() {
			return ydp;
		}

		public void setYdp(double ydp) {
			this.ydp = ydp;
		}

	}
}
