package com.exh.bevel.algo;

import java.util.Formatter;

import com.exh.math.primitive.Geo;
import com.exh.math.primitive.Point3;
import com.exh.math.primitive.Polygon;

/* Clip one polygon by another.  Implemented by finding the intersection
 * points between polygons, removing duplicates (with a very high level of
 * precision), then applying a "turn right" rule to trace the minimal path.
 */
public final class PolygonClipper {
	private final List				mInput = new List(),
									mClip = new List(),
									mOutput = new List(),
									mFactory = new List();
	
	private final Step				mStep = new Step();
	
	// Store
	private final Point3			mPt = new Point3();
	
	private final static boolean	PRINT_FLATTEN = false;
	private final static boolean	PRINT_BUILD = false;
	private final boolean			mPrint, mPrintFlatten;

	// An interface for clients to set the starting point of the op.
	protected interface FirstPoint {
		// Step is which direction the source list moves through its points.
		public void setFirstPoint(	final List list, final int idx,
									final int stepA, final int stepB);
	}

	public PolygonClipper(final boolean print) {
		mPrint = print;
		mPrintFlatten = (PRINT_FLATTEN ? print : false);
	}
	
	// Subtract clip from input, placing the results in output.
	// If I return false then output is unchanged.
	public boolean on(final Polygon input, final Polygon clip, final Polygon output) {
		// special conditions
		if (input.mSize < 1 || clip.mSize < 1) {
			output.rewind();
			return true;
		}
		
		mOutput.moveTo(mFactory);
		mInput.setTo(input, mFactory, true);
		mClip.setTo(clip, mFactory, false);
		if (mInput.mHead == null || mClip.mHead == null) return false;
		makeIntersections(mInput, mClip);
		mInput.mHead.tail().mHead = mInput.mHead;
		mClip.mHead.tail().mHead = mClip.mHead;

if (mPrint) {
	System.out.println("Input A");
	input.print();
	System.out.println("Input B");
	clip.print();
	System.out.println("Input A (flat) size=" + mInput.size());
	mInput.print();
	System.out.println("Input B (flat) size=" + mClip.size());
	mClip.print();
}
		if (!startBuild(mInput, mClip, mStep)) {
			System.out.println("Error building poly");
			return false;
		}
//System.out.println("START BUILD on " + mStep.mVertex);

		final int			looping = mInput.size() + mClip.size() + 2;
		int					c = 0;
		
		mStep.mPrev = null;
		Vertex		start = null;
		while (start != mStep.mVertex) {
			if (start == null) start = mStep.mVertex;
			
			final Vertex		tail = mFactory.pop(mStep.mVertex.mX, mStep.mVertex.mY);
			mOutput.addTail(tail);
//	System.out.println("ADDED " + mOutput.mHead.tail());
			if (!next(mInput, mClip, mStep, clip)) break;
			mStep.mPrev = tail;
			
			if (c++ >= looping) {
				System.out.println("ERROR cycle during polygon subtraction");
				return false;
			}
		}
		
//		System.out.println("RESULT");
//		mOutput.print();
		
		output.rewind();
		Vertex			v = mOutput.mHead;
		while (v != null) {
			output.add(v.mX, v.mY, 0);
			v = v.mNext;
		}
		return true;
	}
	
	private void makeIntersections(final List a, final List b) {
		Vertex				prvA = a.mHead.tail(),
							curA = a.mHead;
		while (curA != null) {
			Vertex			prvB = b.mHead.tail(),
							curB = b.mHead;
			while (curB != null) {
				if (Geo.lineSegmentIntersection(prvA.mX, prvA.mY, curA.mX, curA.mY, prvB.mX, prvB.mY, curB.mX, curB.mY, mPt)) {
					final Vertex	iA = mFactory.pop(mPt.x, mPt.y),
									iB = mFactory.pop(mPt.x, mPt.y);
					iA.mIntersection = iB;
					iB.mIntersection = iA;
					prvA.addWaitingIntersection(iA);
					prvB.addWaitingIntersection(iB);
				}
				prvB = curB;
				curB = curB.mNext;
			}
			
			prvA = curA;
			curA = curA.mNext;
		}
		
		// Place all intersections in the correct place in their segment
		a.insertWaiting();
		b.insertWaiting();
		
		// The intersection stage can produce a lot of identical points,
		// so remove them.  First weed out the non-intersections, since
		// intersections must always be preserved.
		a.removeExtranneousOriginals(mFactory);
		b.removeExtranneousOriginals(mFactory);
		a.removeExtranneousIntersections(b, mFactory);
	}

	// Find the first point that's in a but not b.
	private boolean startBuild(final List a, final List b, final Step step) {
		Vertex			v = a.mHead;
		while (v != null) {
			if (v.mIntersection == null && !b.contains(v.mX, v.mY)) {
				step.mVertex = v;
				return true;
			}
			v = v.mNext;
		}
		return false;
	}

	// Perform subtraction by examining all non-intersecting
	// vertices after the intersecting ones.  Choose the vertex
	// that is not in the subtraction list.
	private boolean next(final List input, final List clip, final Step step, final Polygon clipP) {
		if (!step.mVertex.isIntersection()) {
			step.mVertex = step.mVertex.circularNext();
			return true;
		}
		
		// OK, I'm an intersection.  I want to follow whatever point is
		// not in the clip list, or just continue, if both are.
		final Vertex		nextA = step.mVertex.circularNext(),
							nextB = step.mVertex.mIntersection.circularNext();
		if (nextA == null || nextB == null) {
			System.out.println("ERROR building new polygon, no next");
			return false;
		}

		step.mVertex = turnRight(step, nextA, nextB);
		return true;
	}

	// Choose the right-most vertex by looking at its degree in relation to
	// a start degree (which would be the previous and current vertices).
	// Since we build a clockwise list, right is always the degree closest
	// to the start, continuing counter clockwise.
	private Vertex turnRight(final Step step, final Vertex a, final Vertex b) {
		// Get the baseline degree
		final double		dir = Geo.degree(step.mPrev.mX - step.mVertex.mX, step.mVertex.mY - step.mPrev.mY);
//System.out.println("\t" + step.mPrev + " to " + step.mVertex + " dir=" + dir);
		double				aD = Geo.degree(a.mX - step.mVertex.mX, step.mVertex.mY - a.mY),
							bD = Geo.degree(b.mX - step.mVertex.mX, step.mVertex.mY - b.mY);
//System.out.println("\t\tad=" + aD + " is " + step.mVertex + " to " + a);
//System.out.println("\t\tbd=" + bD + " is " + step.mVertex + " to " + b);
		// If The baseline is at zero, then just continue CCW, which means
		// the highest number wins, with the exception of 0 itself
		if (dir == 0.0) {
			if (aD == 0.0) return a;
			if (bD == 0.0) return b;
			if (aD >= bD) return a;
			return b;
		}
		// Now I have two cases to consider -- everything from myself down to
		// zero, and everything below that.
		final boolean		aInTop = (aD <= dir && aD >= 0.0),
							bInTop = (bD <= dir && bD >= 0.0);
		if (aInTop && !bInTop) return a;
		if (!aInTop && bInTop) return b;
		// If they're both in the same half, larger wins.
		if (aD >= bD) return a;
		return b;
	}

	// VERTEX
	// --------------------------------------------
	private final static class Vertex {

		Vertex			mNext;
		double			mX, mY;
		Vertex			mIntersection;	// If I have an intersection,
										// point to it in the other list
		Vertex			mHead;
		Vertex			mWaiting;		// While flattening the lists, I store
										// all intersections along this segment
		
		private double	mD;				// only while sorting
		
		boolean isIntersection() {
			return mIntersection != null;
		}
		
		Vertex circularNext() {
			if (mNext == null) return mHead;
			return mNext;
		}
		
		Vertex tail() {
			Vertex	o = this;
			while (o.mNext != null) o = o.mNext;
			return o;
		}
		
		void addWaitingIntersection(final Vertex v) {
			v.mWaiting = mWaiting;
			mWaiting = v;
		}

		void insertWaiting() {
			// Sort the list
			Vertex			v = mWaiting;
			while (v != null) {
				v.mD = Geo.distSquared(mX, mY, v.mX, v.mY);
				v = v.mWaiting;
			}
			while (sortWaiting()) ;
			// Insert everyone correctly
			v = mWaiting;
			while (v != null) {
				final Vertex		next = v.mWaiting;
				v.mNext = next;
				v.mWaiting = null;
				v = next;
			}
			mWaiting.tail().mNext = mNext;
			mNext = mWaiting;
			mWaiting = null;
		}

		private boolean sortWaiting() {
			Vertex			prev = null,
							cur = mWaiting;
			boolean			changed = false;
			while (cur.mWaiting != null) {
				if (cur.mD > cur.mWaiting.mD) {
					changed = true;
					final Vertex	next = cur.mWaiting;
					if (prev == null) {
						cur.mWaiting = next.mWaiting;
						next.mWaiting = cur;
						mWaiting = next;
					} else {
						prev.mWaiting = next;
						cur.mWaiting = next.mWaiting;
						next.mWaiting = cur;
					}
					prev = next;
				} else {
					prev = cur;
					cur = cur.mWaiting;
				}
			}
			return changed;
		}
		
		public String toString() {
			final Formatter		fmt = new Formatter();
			if (mIntersection != null) return fmt.format("(%.2f, %.2f) i", mX, mY).toString();
			return fmt.format("(%.2f, %.2f)", mX, mY).toString();
		}
	}
	
	// LIST
	// --------------------------------------------
	private final static class List {
		Vertex		mHead = null;
	
		int size() {
			int			c = 0;
			Vertex		v = mHead;
			while (v != null) {
				c++;
				v = v.mNext;
			}
			return c;
		}
		
		void push(final Vertex v) {
			if (v == null) {
				System.out.println("ERROR asked to push a null vertex");
				return;
			}
			v.mNext = mHead;
			mHead = v;
		}

		Vertex pop(final double x, final double y) {
			final Vertex		ans = pop();
			ans.mX = x;
			ans.mY = y;
			return ans;
		}
		
		Vertex pop() {
			if (mHead == null) return new Vertex();
			final Vertex		ans = mHead;
			mHead = mHead.mNext;
			ans.mNext = null;
			ans.mIntersection = null;
			ans.mHead = null;
			ans.mWaiting = null;
			return ans;
		}

		void addTail(final Vertex v) {
			if (mHead == null) mHead = v;
			else mHead.tail().mNext = v;
		}

		Vertex remove(final Vertex v) {
			if (mHead == null) return null;
			if (v == null) {
				System.out.println("ERROR asked to remove a null vertex");
				return null;
			}
			if (mHead == v) return pop();
			
			Vertex		cur = mHead;
			while (cur.mNext != null) {
				if (cur.mNext == v) {
					cur.mNext = v.mNext;
					v.mNext = null;
					return v;
				}
				cur = cur.mNext;
			}
			return null;
		}
		
		void moveTo(final List o) {
			if (mHead != null) {
				if (o.mHead != null) mHead.tail().mNext = o.mHead;
				o.mHead = mHead;
				mHead = null;
			}
		}
		
		boolean contains(final double x, final double y) {
			Vertex			prv = mHead.tail(),
							cur = mHead;
			boolean			ans = false;
			while (cur != null) {
				if (( ((cur.mY <= y) && (y < prv.mY))
						|| ((prv.mY <= y) && (y < cur.mY)))
						&& (x < (prv.mX - cur.mX) * (y - cur.mY) / (prv.mY - cur.mY) + cur.mX))
					ans = !ans;
				
				prv = cur;
				cur = cur.mNext;
			}
			return ans;
		}

		void setTo(final Polygon p, final List factory, final boolean tails) {
			moveTo(factory);
			
			for (int k=0; k<p.mSize; k++) {
				final double	x = p.mPt[k].x,
								y = p.mPt[k].y;
				final Vertex	v = factory.pop(x, y);
				if (tails) addTail(v);
				else push(v);
			}
		}
		
		void insertWaiting() {
			Vertex		v = mHead;
			while (v != null) {
				if (v.mWaiting != null) v.insertWaiting();
				v = v.mNext;
			}
		}
		
		public void print() {
			if (mHead == null) {
				System.out.println("\tempty");
			} else {
				Vertex		v = mHead;
				while (v != null) {
					System.out.println("\t" + v);
					v = v.mNext;
				}
			}
		}
		
		// Remove all non-intersecting points that have identical intersections.
		void removeExtranneousOriginals(final List factory) {
			while (mHead != null && mHead.mNext != null && !mHead.isIntersection()
					&& !isUnique(mHead, mHead.mNext)) {
				factory.push(pop());
			}
			if (mHead == null) return;
			Vertex			cur = mHead.mNext;
			while (cur.mNext != null) {
				if (!cur.mNext.isIntersection() && !isUnique(cur, cur.mNext)) {
					final Vertex	pop = cur.mNext;
					cur.mNext = pop.mNext;
					pop.mNext = null;
					factory.push(pop);
				} else {
					cur = cur.mNext;
				}
			}
		}
		
		// Remove all intersecting points that have duplicates.
		void removeExtranneousIntersections(final List b, final List factory) {
			while (mHead != null && mHead.mNext != null && mHead.isIntersection()
					&& mHead.mNext.isIntersection() && !isUnique(mHead, mHead.mNext)) {
				factory.push(b.remove(mHead.mIntersection));
				factory.push(pop());
			}
			if (mHead == null) return;
			Vertex			cur = mHead.mNext;
			while (cur.mNext != null) {
				if (cur.isIntersection() && cur.mNext.isIntersection() && !isUnique(cur, cur.mNext)) {
					factory.push(b.remove(cur.mNext.mIntersection));
					final Vertex	pop = cur.mNext;
					cur.mNext = pop.mNext;
					pop.mNext = null;
					factory.push(pop);
				} else {
					cur = cur.mNext;
				}
			}
		}

		private final static boolean isUnique(final Vertex v1, final Vertex v2) {
			return isUnique(v1.mX, v1.mY, v2.mX, v2.mY);
		}

		private final static double		TOLERANCE = 0.000000001;
		
		private final static boolean isUnique(	final double x1, final double y1,
												final double x2, final double y2) {
			return Math.abs(x1-x2) > TOLERANCE || Math.abs(y1-y2) > TOLERANCE;
		}
	}
	
	// STEP
	// --------------------------------------------
	private final static class Step {
		Vertex			mVertex;
		Vertex			mPrev;
	}
}