package Exercise4;

public class Point
{
	private int x;
	private int y;
	private int z = 0;
	public static final int X = 0;
	public static final int Y = 1;
	public static final int Z = 2;
	public static final int AI = 3;

	private String name = null;
	private int arrayindex = 0;

	public Point(int _arrayindex, String n, int _x, int _y, int _z)
	{
		arrayindex = _arrayindex;
		name = n;
		setX(_x);
		setY(_y);
		setZ(_z);
	}

	public Point(int _arrayindex, String n, int _x, int _y)
	{
		arrayindex = _arrayindex;
		name = n;
		setX(_x);
		setY(_y);
	}

	public Point(int _x, int _y)
	{
		setX(_x);
		setY(_y);
	}

	public void setX(int _x)
	{
		x = _x;
	}

	public void setY(int _y)
	{
		y = _y;
	}
	
	public void setZ(int _z)
	{
		z = _z;
	}
	
	public int getX()
	{
		return x;
	}

	public int getY()
	{
		return y;
	}
	
	public int getZ()
	{
		return z;
	}

	public int get(int axis)
	{
		if(axis == X) return getX();
		if(axis == Y) return getY();
		if(axis == Z) return getZ();

		return arrayindex;
	}

	public String toString()
	{
		if(name != null) return name;
		return "(" + x + ", " + y + ")";
	}
}


package Exercise4;

public class Pair
{
	private static boolean always3d = false;

	private Point p1;
	private Point p2;
	private float distance;
	private float distance3d;

	public Pair(Point _p1, Point _p2)
	{
		p1 = _p1;
		p2 = _p2;
		float x_dist = (p1.getX() - p2.getX());
		float y_dist = (p1.getY() - p2.getY());
		float z_dist = (p1.getZ() - p2.getZ());
		distance = (float)Math.sqrt((x_dist*x_dist) + (y_dist*y_dist));
		distance3d = (float)Math.sqrt((x_dist*x_dist) + (y_dist*y_dist) + (z_dist*z_dist));

	}

	public float getDistance()
	{
		if(always3d) return distance3d;
		else return distance;
	}

	public float get3DDistance()
	{
		return distance3d;
	}

	public Point getPoint1()
	{
		return p1;
	}

	public Point getPoint2()
	{
		return p2;
	}

	public static void setAlways3D(boolean a3d)
	{
		always3d = a3d;
	}

	public String toString()
	{
		return "" + p1 + " " + p2 + "";
	}
}



package Exercise4;

public class Exercise
{
	
	public static int filterOn(int axis, Point[] fspo, Point spi[], float left, float right)
	{
		int length = 0;

		for(int i = 0; i < spi.length; i++)
		{
			if(left < spi[i].get(axis) && spi[i].get(axis) < right)
			{
				fspo[length] = spi[i];
				length++;
			}
		}
		return length;

	}

	public static Point[] mergesort(Point p[], int lower, int upper, int axis)
	{

		Point ret[] = new Point[upper-lower+1];

		if((upper - lower) == 0)
		{
			ret[0] = p[lower];
			return ret;
		}
		if((upper - lower) == 1)
		{
			//this is where we have to sort
			if(p[lower].get(axis) > p[upper].get(axis))
			{
				ret[0] = p[upper];
				ret[1] = p[lower];
			}else{
				ret[0] = p[lower];
				ret[1] = p[upper];
			}			
			return ret;
		}
		int middle = (upper+lower)/2;
		Point right[] = mergesort(p, middle+1, upper, axis);
		Point left[] = mergesort(p, lower, middle, axis);

		int l = 0,r = 0;
		for(int i = 0; i < p.length; i++)
		{
			if((l < left.length) && (r < right.length))
			{
				if(right[r].get(axis) < left[l].get(axis))
				{
					ret[i] = right[r];
					r++;
				}else{
					ret[i] = left[l];
					l++;
				}
			}else{
				if(l < left.length)
				{
					ret[i] = left[l];
					l++;
				}else if(r < right.length){
					ret[i] = right[r];
					r++;
				}
			}
		}
		return ret;
	}

	public static Pair closestpair(Point spx[], Point spy[], int lower, int upper)
	{
		
		if((upper - lower) < 3) //3 points or less left
		{
			if(lower==upper) //we have a problem
				return null;
			Pair min = new Pair(spx[lower], spx[upper]);
			if((lower-upper) > 1)
			{
				Pair p1 = new Pair(spx[lower], spx[lower+1]);
				Pair p2 = new Pair(spx[upper-1], spx[upper]);
				if(p2.getDistance() < p1.getDistance())
				{
					p1 = p2;
				}

				if(p1.getDistance() < min.getDistance())
				{
					min = p1;
				}
			}
			return min;
		}

		int middle = (upper + lower) / 2;

		Pair l = closestpair(spx, spy, lower, middle);
		Pair r = closestpair(spx, spy, middle + 1, upper);
		Pair min;
		
		if(l.getDistance() < r.getDistance())
			min = l;
		else
			min = r;
				
		Point fpy[] = new Point[spy.length];
		int length = filterOn(Point.X, fpy, spy, (float)(spx[(middle + 1)].getX()) - min.getDistance(), (float)(spx[middle].getX()) + min.getDistance());
		
		for(int i = 0; i < length;i++)
		{
			for(int j = 1; j <= 3; j++) //The reason I look 6 nodes around this one is explained in the documentation
			{
				if(i+j < length)
				{
					Pair p = new Pair(fpy[i], fpy[i+j]);
					if(p.getDistance() < min.getDistance())
						min = p;
				}

				if(i-j > 0)			
				{
					Pair p = new Pair(fpy[i-j], fpy[i]);
					if(p.getDistance() < min.getDistance())
					{
						min = p;
					}
				}
			}
		}

		return min;

	}

	public static Pair closestpair3d(Point spx[], Point spy[], Point spz[], int lower, int upper)
	{
		if((upper - lower) < 3) //3 points or less left
		{
			if(lower==upper) //we have a problem
				return null;
				Pair min = new Pair(spz[lower], spz[upper]);
			if((lower-upper) > 1)
			{
				Pair p1 = new Pair(spz[lower], spz[lower+1]);
				Pair p2 = new Pair(spz[upper-1], spz[upper]);
				if(p2.get3DDistance() < p1.get3DDistance())
				{
					p1 = p2;
				}

				if(p1.get3DDistance() < min.get3DDistance())
				{
					min = p1;
				}
			}
			return min;
		}

		int middle = (upper + lower) / 2;

		Pair l = closestpair3d(spx, spy, spz, lower, middle);
		Pair r = closestpair3d(spx, spy, spz, middle + 1, upper);
		Pair min;
		
		if(l.get3DDistance() < r.get3DDistance())
			min = l;
		else
			min = r;
				
		Point fspx[] = new Point[spx.length];
		int length = filterOn(Point.Z, fspx, spx, (float)(spz[(middle + 1)].getZ()) - min.get3DDistance(), (float)(spz[middle].getZ()) + min.get3DDistance());

		
		for(int i = 0; i < length;i++)
		{
			for(int j = 1; j <= 3; j++) //The reason I look 6 nodes around this one is explained in the documentation
			{
				if(i+j < length)
				{
					Pair p = new Pair(fpy[i], fpy[i+j]);
					if(p.get3DDistance() < min.get3DDistance())
						min = p;
				}

				if(i-j > 0)			
				{
					Pair p = new Pair(fpy[i-j], fpy[i]);
					if(p.get3DDistance() < min.get3DDistance())
					{
						min = p;
					}
				}
			}
		}

		return min;
	}


	public static void main(String args[])
	{
		Point p[] = DataReader.getData(args[0]);

		Point spx[] = mergesort(p, 0, p.length - 1, Point.X);
		Point spy[] = mergesort(p, 0, p.length - 1, Point.Y);
		Point spz[] = mergesort(p, 0, p.length - 1, Point.Z);

		Pair cp2d = closestpair(spx, spy, 0, p.length - 1);
		
		if(cp2d.getPoint1().get(Point.AI) > cp2d.getPoint2().get(Point.AI))
			cp2d = new Pair(cp2d.getPoint2(), cp2d.getPoint1());
		
		System.out.print("" + cp2d);


		Pair.setAlways3D(true);
		Pair cp3d = closestpair3d(spx, spy, spz, 0, p.length - 1);
		
		if(cp3d.getPoint1().get(Point.AI) > cp3d.getPoint2().get(Point.AI))
			cp3d = new Pair(cp3d.getPoint2(), cp3d.getPoint1());

		System.out.println(" bonus: " + cp3d);


	}
}