/************************************************************
* Implementation of 2-dimensional kd-trees.
* Søren Gaardbo Jensen, 1999.03.14
***********************************************************
*/
import java.awt.*;
import java.applet.*;
import java.lang.Math;

// *** Class kdTreeDemo *******************************************************
public class kdTreeDemo extends Applet
{
	
	public void init()
	{
		Button clearButton = new Button(clearButtonStr);
		clearButton.resize(50, 50);
		clearButton.move(250, 10);
		add(clearButton);
		Button kdtreeButton = new Button(calcButtonStr);
		kdtreeButton.move(250, 30);
		kdtreeButton.resize(50, 50);
		add(kdtreeButton);
		kdCanvas.resize(size().width, size().height);
		kdCanvas.move(0, 0);
		add(kdCanvas);
	}
	
	public boolean action(Event e, Object o)
	{
		if(e.target instanceof Button)
		{
			String result = (String)o;
			if(result.equals(clearButtonStr))
			{
				kdCanvas.points.clear();
				kdCanvas.repaint();
			}
			if(result.equals(calcButtonStr))
			{
				Graphics g = kdCanvas.getGraphics();
				kdTree myKdTree = new kdTree(kdCanvas.points, g);
				myKdTree.draw(g, 0, 0, size().width, size().height);
			}
		}
		return true;
	}
	kdTreeCanvas kdCanvas = new kdTreeCanvas();
	private static final String calcButtonStr = new String("Calc. kd-tree");
	private static final String clearButtonStr = new String("Clear");
}

// *** Class kdTreeCanvas *****************************************************
class kdTreeCanvas extends Canvas
{
	
	public void paint(Graphics g)
	{
		
		// draw a frame around the canvas...
		g.setColor(new Color(0, 0, 0));
		g.fillRect(0, 0, size().width, size().height);
		g.setColor(new Color(250, 250, 250));
		g.fillRect(5, 5, size().width - 10, size().height - 40);
		g.setColor(getForeground());
		
		// draw all points...
		for(int i = 0;i < points.count;points.XList[i++].draw(g))
			;
	}
	
	public boolean mouseDown(Event e, int x, int y)
	{
		pointElement p = new pointElement(x, y);
		points.addPoint(p);
		Graphics g = this.getGraphics();
		p.draw(g);
		return true;
	}
	pointList pointList1, pointList2;
	pointList points = new pointList();
}

// *** Class pointElement *****************************************************
class pointElement extends Point
{
	
	public pointElement(int x, int y) 
	{
		super(x, y);
	}
	
	public void draw(Graphics g)
	{
		g.fillOval(x - (DIAMETER / 2), y - (DIAMETER / 2), DIAMETER, DIAMETER);
	}
	private final static int DIAMETER = 5;
}

// *** Class pointList ********************************************************
class pointList
{
	
	public void splitPointSet(pointList left, pointList right, pointElement p, pointCompare cmp)
	{
		int leftXIndex = 0;
		int rightXIndex = 0;
		int leftYIndex = 0;
		int rightYIndex = 0;
		for(int i = 0;i < this.count;i++)
		{
			if(cmp.compare(this.XList[i], p) < 0)
				left.XList[leftXIndex++] = this.XList[i];
			else
				right.XList[rightXIndex++] = this.XList[i];
			if(cmp.compare(this.YList[i], p) < 0)
				left.YList[leftYIndex++] = this.YList[i];
			else
				right.YList[rightYIndex++] = this.YList[i];
		}
		left.count = leftXIndex;
		right.count = rightXIndex;
	}
	
	public void addPoint(pointElement p)
	{
		YList[count] = p;
		XList[count] = p;
		count++;
	}
	
	public void clear()
	{
		count = 0;
	}
	
	public void pointList()
	{
		count = 0;
	}
	public static final int MAXPOINTS = 5000;
	pointElement YList[] = new pointElement[MAXPOINTS];
	pointElement XList[] = new pointElement[MAXPOINTS];
	int count;
}

// *** Class twoDTreeNode *****************************************************
class twoDTreeNode
{
	
	public twoDTreeNode(pointElement _p) 
	{
		p = _p;
		leftChild = null;
		rightChild = null;
	}
	twoDTreeNode rightChild;
	twoDTreeNode leftChild;
	pointElement p;
}

// *** Class kdTree ***********************************************************
class kdTree
{
	
	public void draw(Graphics g, int lowx, int lowy, int heighx, int heighy)
	{
		
		// Draw the
		drawHelper(root, lowx, lowy, heighx, heighy, 0, g);
	}
	
	kdTree(pointList plist, Graphics g) 
	{
		mergeSort(plist.XList, plist.count, new leftToRight());
		mergeSort(plist.YList, plist.count, new bottomToTop());
		root = buildkdTree(plist, 0, g);
	}
	
	private twoDTreeNode buildkdTree(pointList pList, int level, Graphics g)
	{
		if(pList.count == 0)
			return null;
		if(pList.count == 1)
			return new twoDTreeNode(pList.XList[0]);
		int medianIndex = (pList.count) / 2;
		twoDTreeNode newPoint;
		pointCompare cmp;
		pointList left = new pointList();
		pointList right = new pointList();
		if((level % 2) == 0)
		{ // Cut vertical
			
			// Split up the list vertically at medianIndex
			newPoint = new twoDTreeNode(pList.XList[medianIndex]);
			cmp = new leftToRight();
		}
		else
		{ // Cut horizontal
			
			// Split up the list horizontally at mendianIndex
			newPoint = new twoDTreeNode(pList.YList[medianIndex]);
			cmp = new bottomToTop();
		}
		pList.splitPointSet(left, right, newPoint.p, cmp);
		
		//        g.setColor(new Color(250,0,0));
		
		//        newPoint.p.draw(g);
		newPoint.leftChild = buildkdTree(left, level + 1, g);
		newPoint.rightChild = buildkdTree(right, level + 1, g);
		return newPoint;
	}
	
	private void drawHelper(twoDTreeNode node, int lowx, int lowy, int highx, int highy, int level, Graphics g)
	{
		
		// Draw the subtree "node" limited by (lowx, lowy) - (heighx, heighy)
		if(node == null)
			return ;
		if((level % 2) == 0)
		{
			
			// draw vertically
			if((node.leftChild != null) | (node.rightChild != null))
				g.drawLine(node.p.x, lowy, node.p.x, highy);
			
			// draw leftChild
			drawHelper(node.leftChild, lowx, lowy, node.p.x, highy, level + 1, g);
			
			// draw rightChild
			drawHelper(node.rightChild, node.p.x, lowy, highx, highy, level + 1, g);
		}
		else
		{
			
			// draw horizontally
			if((node.leftChild != null) | (node.rightChild != null))
				g.drawLine(lowx, node.p.y, highx, node.p.y);
			
			// draw leftChild
			drawHelper(node.leftChild, lowx, lowy, highx, node.p.y, level + 1, g);
			
			// draw rightChild
			drawHelper(node.rightChild, lowx, node.p.y, highx, highy, level + 1, g);
		}
	}
	
	private void mergeSort(pointElement pList[], int length, pointCompare cmp)
	{
		mSort(pList, 0, length - 1, cmp);
	}
	
	private void mSort(pointElement pList[], int l, int r, pointCompare cmp)
	{
		if(l < r)
		{
			int m = (l + r) / 2;
			mSort(pList, l, m, cmp);
			mSort(pList, m + 1, r, cmp);
			merge(pList, l, m, r, cmp);
		}
	}
	
	private void merge(pointElement pList[], int l, int m, int r, pointCompare cmp)
	{
		pointElement tmpPoints[] = new pointElement[r - l + 1];
		int aindex = l;
		int bindex = m + 1;
		int cindex = 0;
		while((aindex <= m) && (bindex <= r))
		{
			if(cmp.compare(pList[aindex], pList[bindex]) < 0) // pList[aindex] < pList[bindex]
				tmpPoints[cindex++] = pList[aindex++];
			else
				tmpPoints[cindex++] = pList[bindex++];
		}
		while(aindex <= m) // copy rest of the sublist
			tmpPoints[cindex++] = pList[aindex++];
		while(bindex <= r)
			tmpPoints[cindex++] = pList[bindex++];
		
		// Copy the sorted sublist back into pList
		for(aindex = l,cindex = 0;aindex <= r;aindex++,cindex++)
			pList[aindex] = tmpPoints[cindex];
	}
	twoDTreeNode root;
}

// *** Class pointCompare *****************************************************
abstract class pointCompare
{
	
	abstract int compare(pointElement p1, pointElement p2);

// Compare the points p1 and p2, return:

// -1 if p1 < p2,

// 1 if p1 > p2

// 0 otherwise
}
class leftToRight extends pointCompare
{
	
	int compare(pointElement p1, pointElement p2)
	{
		if((p1.x == p2.x) && (p1.y == p2.y))
			return 0;
		if((p1.x < p2.x) || ((p1.x == p2.x) && (p1.y < p2.y)))
			return -1;
		return 1; // p2 > p1
	}
}
class bottomToTop extends pointCompare
{
	
	int compare(pointElement p1, pointElement p2)
	{
		if((p1.x == p2.x) && (p1.y == p2.y))
			return 0;
		if((p1.y < p2.y) || ((p1.y == p2.y) && (p1.x < p2.x)))
			return -1;
		return 1;
	}
}