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 java.util.List;
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;

/**
 * SpatialNeighborCluster(SNC) is proposed by Meng Fang .etc,
 * detail of SNC refer to Meng Fang, Shuliang Wang, Hong Jin.
 * 		 Spatial Neighborhood Clustering Based on Data Field.
 * 		 In: Proc. Of the 6th International Conference on
 * 		 Advanced Data Mining and Applications: Part I [C], 
 * 		 Spernger-Verlag Press, 2010, 262-269.
 * SNC needs only one parameter K, the grid number parameter.
 * SNC consists of three steps
 * 1	initialize grids
 * 		SNC first quantize the original feature space into K 
 * 		intervals, and then assign each data object into quantized
 * 		grids.
 * 		the  
 * 2	identify clustering centers
 * 3	cluster data objects
 * @author ethonchan
 *
 */
public class SNC {

	// 将数据空间的每个维度划分的网格数目
	private int K;
	// 算法所处理的数据的最小值（x,y）以及划分网格的宽度
	private double dx, dy, xmin, ymin;
	// 数据场的影响因子，设定为Max(dx,dy)
	private double sigma;
	// 划分后的网格
	private Grid[][] grids;
	// 算法找到的聚类
	List<SCluster> cls;

	/**
	 * 根据用户指定的划分网格数目，将数据空间划分为一定数量的网格，并且将所有的数据分配到网格中
	 * 
	 * @param K
	 *            数据空间的每个维度划分的网格数目
	 */
	public SNC(int K) {
		this.K = K;
	}

	public void process() {
		// 初始化网格
		initializeGrids();

		// 搜索局部极大势值，找出聚类中心
		cls = new ArrayList<SCluster>();
		for (int x = 0, clusterNumber = 1; x < K; x++) {
			for (int y = 0; y < K; y++) {
				if (isLocalMax(x, y))
					cls.add(new SCluster(x, y, clusterNumber++));
			}
		}
		
		//将每个数据点归类
		for(int y=0;y<K;y++){
			for(int x=0;x<K;x++){
				int index=getClusterNumber(x, y);
				SCluster cluster = cls.get(index);
				List<Coord> list = cluster.contentList;
				list.add(new Coord(x,y));
				cls.set(index, cluster);
			}
		}

		// 准备绘图
		BufferedImage img = ImageGenerator.drawImage(null, DataBase.sLen);
		img = showCoord(img);
		Graphics g = img.getGraphics();
		CoordTransfer tsf = new CoordTransfer();

		DataPoint[] points = DataBase.getInstance().getPoints();
		g.setColor(Color.gray);
		for (DataPoint point : points) {
			int[] coord = tsf.getPanelCoord(point.getCoord_X(),
					point.getCoord_Y());
			g.fillOval(coord[0] - 1, coord[1] - 1, 2, 2);
		}

		for (int i = 0, len = cls.size(); i < len; i++) {
			SCluster c = cls.get(i);
			float t = (float) c.clusterNumber / (float) cls.size();
			Color color = CounterUtil.HLStoRGB(t, (float) 0.5, (float) 0.5);
			c.color = color;
		}

		// 输出聚类信息
		for (SCluster cluster : cls) {
			List<Coord> content = cluster.contentList;

			g.setColor(cluster.color);
			for (Coord gnumber : content) {
				int x = gnumber.getX();
				int y = gnumber.getY();

				Grid grid = grids[x][y];
				ArrayList<DataPoint> list = grid.list;

				for (DataPoint point : list) {
					int[] coord = tsf.getPanelCoord(point.getCoord_X(),
							point.getCoord_Y());
					g.fillOval(coord[0] - 1, coord[1] - 1, 2, 2);
				}
			}
		}

		for (SCluster cluster : cls) {
			g.setColor(Color.black);
			Coord c = cluster.center;
			int x = c.getX();
			int y = c.getY();
			double xloc = xmin + dx / 2 + dx * x;
			double yloc = ymin + dy / 2 + dy * y;
			int[] coord = tsf.getPanelCoord(xloc, yloc);
			g.fillOval(coord[0] - 8, coord[1] - 8, 16, 16);
			g.setFont(new Font("SansSerif", Font.BOLD, 25));
			g.drawString(Integer.toString(cluster.clusterNumber), coord[0],
					coord[1]);
		}

		g.dispose();

		DataField.updateImagePanel(img);

	}
	
	/**
	 * 计算某个网格应该属于哪个聚类簇
	 * @param x	需要进行计算的网格X坐标
	 * @param y	需要进行计算的网格Y坐标
	 * @return	网格所属的聚类簇的序号，从0开始
	 */
	private int getClusterNumber(int x, int y){
		double xloc=grids[x][y].getXCenter();
		double yloc=grids[x][y].getYCenter();
		
		int len=cls.size();
		double[] values=new double[len];
		for(int i=0;i<len;i++){
			SCluster cluster = cls.get(i);
			Coord coord = cluster.center;
			Grid grid = grids[coord.getX()][coord.getY()];
			double xdist=grid.getXCenter()-xloc;
			double ydist=grid.getYCenter()-yloc;
			double value=xdist*xdist+ydist*ydist;
			values[i]=value;
		}
		double min=values[0];
		int index=0;
		for(int i=0;i<len;i++){
			if(min>values[i]){
				min=values[i];
				index=i;
			}
		}
		return index;
	}

	private BufferedImage showCoord(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++) {
			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;
	}

	/**
	 * 检验坐标为（gridX，gridY）的网格是否具有局部极大值
	 * 
	 * @param gridX
	 *            中心网格的x坐标
	 * @param gridY
	 *            中心网格的y坐标
	 * @return 具有局部极大值则返回true，反之返回false
	 */
	private boolean isLocalMax(int gridX, int gridY) {
		Grid[] ngb = getNeighborGrids(gridX, gridY);
		double pot = grids[gridX][gridY].getPotential();

		for (Grid g : ngb) {
			if (g.getPotential() > pot)
				return false;
		}

		return true;
	}

	/**
	 * 计算每个网格的一阶偏导势值
	 */
	public void initializeGrids() {
		grids = new Grid[K][K];

		DataPoint[] points = DataBase.getInstance().getPoints();
		// 遍历找出数据的最大最小取值，并据此确定每个网格的变长dx dy
		xmin = Double.MAX_VALUE;
		ymin = Double.MAX_VALUE;
		double xmax = Double.MIN_VALUE;
		double ymax = Double.MIN_VALUE;

		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.max(dx, dy);

		// 将每个数据点分配到相应的网格中，注意这里有可能有一部分网格为空
		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 (grids[xl][yl] == null)
				grids[xl][yl] = new Grid();

			grids[xl][yl].addDataPoint(p);
		}

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

					grid = new Grid();
					grid.setCenter(xloc, yloc);
					grids[x][y] = grid;
				}
			}
		}

		// 计算每个网格的势值及一阶偏导势值
		double sigma2 = sigma * sigma;
		for (int x = 0; x < K; x++) {
			for (int y = 0; y < K; y++) {
				double xloc = grids[x][y].getXCenter();
				double yloc = grids[x][y].getYCenter();
				double pot = 0;
				for (int xi = 0; xi < K; xi++) {
					for (int yi = 0; yi < K; yi++) {
						Grid gi = grids[xi][yi];
						if (gi.getPnumber() == 0)
							continue;

						double xdist = gi.getXCenter() - xloc;
						double ydist = gi.getYCenter() - yloc;
						double tpot = (xdist * xdist + ydist * ydist) / sigma2;
						tpot = gi.getPnumber() * Math.pow(Math.E, -tpot);
						pot += tpot;
					}
				}
				grids[x][y].setPotential(pot);
			}
		}
	}

	/**
	 * 获取坐标为（gridX，gridY）的网格的邻居网格，这里采用四邻域
	 * 
	 * @param gridX
	 *            中心网格x坐标
	 * @param gridY
	 *            中心网格y坐标
	 * @return 中心网格的四邻域网格
	 */
	private Grid[] getNeighborGrids(int gridX, int gridY) {
		LinkedList<Grid> result = new LinkedList<Grid>();

		if (gridX > 0)
			result.add(grids[gridX - 1][gridY]);
		if (gridY > 0)
			result.add(grids[gridX][gridY - 1]);
		if (gridX < K - 1)
			result.add(grids[gridX + 1][gridY]);
		if (gridY < K - 1)
			result.add(grids[gridX][gridY + 1]);

		Grid[] array = new Grid[result.size()];
		array = result.toArray(array);
		return array;
	}

	private class Coord {
		private int x;
		private int y;

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

		public int getX() {
			return x;
		}

		public int getY() {
			return 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 SNC getOuterType() {
			return SNC.this;
		}

		@Override
		public String toString() {
			return "[x=" + x + ", y=" + y + "]";
		}

	}

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

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

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

		public double getPotential() {
			return potential;
		}

		public void setPotential(double potential) {
			this.potential = potential;
		}

		public int getPnumber() {
			return pnumber;
		}

		public double getXCenter() {
			if (pnumber == 0)
				return xall;
			else
				return xall / pnumber;
		}

		public double getYCenter() {
			if (pnumber == 0)
				return yall;
			else
				return yall / pnumber;
		}
	}

	class SCluster {
		Coord center;
		Color color;
		int clusterNumber = 0;
		List<Coord> contentList = new LinkedList<Coord>();

		SCluster(int x, int y, int clusterNumber) {
			center = new Coord(x, y);
			color = Color.green;
			this.clusterNumber = clusterNumber;

			contentList.add(center);
			if (x > 0)
				contentList.add(new Coord(x - 1, y));
			if (x < K - 1)
				contentList.add(new Coord(x + 1, y));
			if (y > 0)
				contentList.add(new Coord(x, y - 1));
			if (y < K - 1)
				contentList.add(new Coord(x, y + 1));

		}

		void addGrid(int x, int y) {
			contentList.add(new Coord(x, y));
		}

		boolean containGrid(int x, int y) {
			Coord gridNumber = new Coord(x, y);
			return contentList.contains(gridNumber);
		}
	}
}
