import java.util.Iterator;
import java.util.Vector;








public class DistributedDelaunayClip implements 
	Iterator<DistributedDelaunayClip.Edge>
{

	final static boolean bDebug = true;
	
	public interface ClipGeom {
	
	}
	
	
	// DOES NOT WORK
	// abandoning for better implementation idea
	public class Arc implements CommLink.IChannelData, ClipGeom
	{
		double m_arrLfCtr[];
		double m_lfRad;
		double m_lfStartAng, m_lfEndAng;

		Arc() { setCenter(0,0);}
		
		public Arc(double lfCX, double lfCY, Edge clipWith, boolean bLR) {
			setCenter(lfCX, lfCY);
			double [] arrLfClosestPt = clipWith.getClosestPt();
			double lfCloseX = arrLfClosestPt[0] - lfCX;
			double lfCloseY = arrLfClosestPt[1] - lfCY;
			double lfCloseDistSqrd = lfCloseX*lfCloseX + lfCloseY*lfCloseY;
			double lfLenSqrd = m_lfRad*m_lfRad - lfCloseDistSqrd;
			lfLenSqrd = Math.max(0, lfLenSqrd);
			double lfCenterTheta = Math.atan2(lfCloseY, lfCloseX);
			double lfLen = Math.sqrt(lfLenSqrd);
			double lfThetaOff = Math.atan2(lfLen,
					Math.sqrt(lfCloseDistSqrd));
			
			// WARNING this code does not handle backwards edges
			// correctly.  FIX LATER.
			if(bLR) {
				if(clipWith.isEndFinite()) {
					double [] arrLfEdgeEnd = clipWith.getEdgeEnd(m_lfRad);
					m_lfEndAng = Math.atan2(arrLfEdgeEnd[1], 
							arrLfEdgeEnd[0]);
				} else {
					m_lfEndAng = lfCenterTheta + Math.PI*0.5;
				}
				m_lfStartAng = lfCenterTheta + lfThetaOff;
			} else {
				if(clipWith.isStartFinite()) {
					double [] arrLfEdgeStart = clipWith.getEdgeStart(m_lfRad);
					m_lfEndAng = Math.atan2(arrLfEdgeStart[1], 
							arrLfEdgeStart[0]);
				} else {
					m_lfEndAng = lfCenterTheta + Math.PI*0.5;
				}
				m_lfStartAng = lfCenterTheta + lfThetaOff;
			}
		}
		
		public Arc(Arc src) {
			setCenter(src.m_arrLfCtr[0], src.m_arrLfCtr[1]);
			m_lfRad = src.m_lfRad;
			m_lfStartAng = src.m_lfStartAng;
			m_lfEndAng = src.m_lfEndAng;
		}
		
		void setCenter(double lfCX, double lfCY) {
			m_arrLfCtr = new double[2];
			m_arrLfCtr[0] = lfCX; m_arrLfCtr[1] = lfCY;
		}
		
		public synchronized CommLink.IChannelData cloneData() {
			return new Arc(this);
		}

	}
	
	/**
	 * Holds a (possible infinite, and possibly) empty edge in 2d)
	 * @author mds
	 *
	 */
	public class Edge implements CommLink.IChannelData, ClipGeom
	{
		double m_arrLfClosestPt[];
		double m_arrLfDirVec[];
		double m_lfDist;

		double m_lfStart, m_lfEnd;

		int m_nAssociatedId;
		
		/**
		 * whether start and end points are valid -- if false, this is infinity
		 */
		boolean m_bStart, m_bEnd; 

		public Edge() {
			m_bStart = false; m_bEnd = false; // infinite line through origin
			// with no direction
			m_arrLfClosestPt = new double[2];
			m_arrLfDirVec = new double[2];
		}

		public Edge(double lfX, double lfY) {
			m_bStart = false; m_bEnd = false;
			m_arrLfClosestPt = new double[2];
			m_arrLfDirVec = new double[2];
			m_arrLfClosestPt[0] = lfX;
			m_arrLfClosestPt[1] = lfY;	
			setFromClosestPt();
			if(bDebug && !CheckValid()) {
				System.out.println("Invalid edge");
			}
		}

		public Edge(Edge src) {
			m_arrLfClosestPt = new double[2];
			m_arrLfDirVec = new double[2];
			m_bStart = src.m_bStart; m_bEnd = src.m_bEnd;
			m_arrLfClosestPt[0] = src.m_arrLfClosestPt[0];
			m_arrLfClosestPt[1] = src.m_arrLfClosestPt[1];
			m_arrLfDirVec[0] = src.m_arrLfDirVec[0];
			m_arrLfDirVec[1] = src.m_arrLfDirVec[1];
			m_lfDist = src.m_lfDist;
			m_lfStart = src.m_lfStart;
			m_lfEnd = src.m_lfEnd;
			if(bDebug && !CheckValid()) {
				System.out.println("Invalid edge");
			}
		}
		
		public synchronized CommLink.IChannelData cloneData() {

			if(bDebug && !CheckValid()) {
				System.out.println("Invalid edge");
			}
			return new Edge(this);
		}

		public boolean CheckValid() {
			double lfDot = m_arrLfClosestPt[0]*m_arrLfDirVec[0] +
			m_arrLfClosestPt[1]*m_arrLfDirVec[1];
			if(Math.abs(m_lfDist) > MathUtils.lfEps) {
				lfDot = lfDot/m_lfDist;
			}
			return (lfDot <= 5*MathUtils.lfEps);
				
			
		}
		
		public void setFromClosestPt() {
			m_lfDist = Math.sqrt(m_arrLfClosestPt[0]*m_arrLfClosestPt[0] +
					m_arrLfClosestPt[1]*m_arrLfClosestPt[1]);
			if(m_lfDist <= MathUtils.lfEps) {
				m_arrLfDirVec[0] = 0.0;
				m_arrLfDirVec[1] = 1.0;
				return;
			}
			double lfDistInv = 1.0/m_lfDist;
			m_arrLfDirVec[0] = -lfDistInv*m_arrLfClosestPt[1];
			m_arrLfDirVec[1] =  lfDistInv*m_arrLfClosestPt[0];
			if(bDebug && !CheckValid()) {
				System.out.println("Invalid edge");
			}
		}

		public void setId(int nId) {
			m_nAssociatedId = nId;
		}
		
		public int getId() {
			return m_nAssociatedId;
		}
		
		boolean edgesIsect(Edge edgeToIsect) {
			double lfD1CrossD2 = 
				m_arrLfDirVec[0]*edgeToIsect.m_arrLfDirVec[1] -
				m_arrLfDirVec[1]*edgeToIsect.m_arrLfDirVec[0];
			if(Math.abs(lfD1CrossD2) <= MathUtils.lfEps ) {
				return false;
			}
			return true;
		}

		/**
		 * Finds length along this edge at which it intersects edgeToIsect.
		 * Doesn't check against start and end of edgeToIsect -- assumes it is infinite
		 * @param edgeToIsect
		 * @return length along this edge at which it intersects edgeToIsect
		 */
		public double getIsect(Edge edgeToIsect) {
			double lfResult = 0.0;
			double lfDenom = 
				edgeToIsect.m_arrLfClosestPt[0]*m_arrLfDirVec[0] +
				edgeToIsect.m_arrLfClosestPt[1]*m_arrLfDirVec[1];
			lfDenom = 1.0/lfDenom;
			lfResult = 
				edgeToIsect.m_arrLfClosestPt[0]*edgeToIsect.m_arrLfClosestPt[0] +
				edgeToIsect.m_arrLfClosestPt[1]*edgeToIsect.m_arrLfClosestPt[1] -
				m_arrLfClosestPt[0]*edgeToIsect.m_arrLfClosestPt[0] -
				m_arrLfClosestPt[1]*edgeToIsect.m_arrLfClosestPt[1];
			if(bDebug && !CheckValid()) {
				System.out.println("Invalid edge");
			}
			return lfResult*lfDenom;
		}

		boolean ptInEdge(double lfLenAlongEdge) {
			return (lfLenAlongEdge <= m_lfEnd || !m_bEnd) &&
			(lfLenAlongEdge >= m_lfStart || !m_bStart);
		}

		/**
		 * Whether clipping should occur in the positive or negative direction
		 * @param edgeClipWith edge to consider clipping with
		 * @return "true" if "edgeClipWith" should clip m_lfEnd, "false" ifm_lfStart
		 */
		boolean bClipAlongLen(Edge edgeClipWith) {
			return ((m_arrLfDirVec[0]*edgeClipWith.m_arrLfClosestPt[0] + 
					m_arrLfDirVec[1]*edgeClipWith.m_arrLfClosestPt[1]) 
					> 0.0 );
		}

		/**
		 * Performs clipping between this edge and edgeToIsect
		 * @param edgeToIsect edge to clip with (both edges clipped to each-other)
		 * @return "true" iff clipping occured.
		 */
		public boolean clipWith(Edge edgeToIsect) {
			if(!edgesIsect(edgeToIsect)) {
				return false;
			}
			double lfPt1 = getIsect(edgeToIsect);
			/* if(!ptInEdge(lfPt1)) {
				return false;
			} */

			if(bClipAlongLen(edgeToIsect)) {
				if(!m_bEnd) {
					m_lfEnd = lfPt1; m_bEnd = true;
				}
				m_lfEnd = Math.min(m_lfEnd, lfPt1);
			} else {
				if(!m_bStart) {
					m_lfStart = lfPt1; m_bStart = true;
				}
				m_lfStart = Math.max(m_lfStart, lfPt1);
			}


			if(bDebug && !CheckValid()) {
				System.out.println("Invalid edge");
			}
			return true;
		}

		public boolean edgeValid() {
			/* if((m_bStart) && (m_bEnd) && (m_lfStart >= m_lfEnd)) {
				System.out.println("Rejecting an edge");
			} */
			return (!m_bStart) || (!m_bEnd) || (m_lfStart < m_lfEnd );
		}
		
		public double [] getEdgeStart(double lfMaxLen) {
			lfMaxLen = -lfMaxLen;
			if(m_bStart) {
				lfMaxLen = m_lfStart;
				// lfMaxLen = Math.max(lfMaxLen, m_lfStart);
			}  else if(m_bEnd) {
				lfMaxLen += m_lfEnd;
			}
			double [] arrLfResult = new double[2];
			arrLfResult[0] = m_arrLfClosestPt[0] +
				lfMaxLen*m_arrLfDirVec[0];
			arrLfResult[1] = m_arrLfClosestPt[1] +
				lfMaxLen*m_arrLfDirVec[1];
			if(bDebug && !CheckValid()) {
				System.out.println("Invalid edge");
			}
			return arrLfResult;
		}
		
		public double [] getEdgeStartClip(double lfMaxLen, double lfBigClip) {
			lfMaxLen = -lfMaxLen;
			if(m_bStart) {
				lfMaxLen = m_lfStart;
				// lfMaxLen = Math.max(lfMaxLen, m_lfStart);
			}  else if(m_bEnd) {
				lfMaxLen += m_lfEnd;
			}
			lfMaxLen = Math.max(-lfBigClip, lfMaxLen);
			lfMaxLen = Math.min(lfBigClip, lfMaxLen);
			double [] arrLfResult = new double[2];
			arrLfResult[0] = m_arrLfClosestPt[0] +
				lfMaxLen*m_arrLfDirVec[0];
			arrLfResult[1] = m_arrLfClosestPt[1] +
				lfMaxLen*m_arrLfDirVec[1];
			if(bDebug && !CheckValid()) {
				System.out.println("Invalid edge");
			}
			return arrLfResult;
		}
		
		public double [] getClosestPt() {
			return m_arrLfClosestPt;
		}
		
		public boolean isStartFinite() {
			return m_bStart;
		}
		
		public boolean isEndFinite() {
			return m_bEnd;
		}
		
		public double [] getEdgeEnd(double lfMaxLen) {
			if(m_bEnd) {
				lfMaxLen = m_lfEnd;
				// lfMaxLen = Math.min(lfMaxLen, m_lfEnd);
			}  else if(m_bStart) {
				lfMaxLen += m_lfStart;
			}
			double [] arrLfResult = new double[2];
			arrLfResult[0] = m_arrLfClosestPt[0] +
				lfMaxLen*m_arrLfDirVec[0];
			arrLfResult[1] = m_arrLfClosestPt[1] +
				lfMaxLen*m_arrLfDirVec[1];
			if(bDebug && !CheckValid()) {
				System.out.println("Invalid edge");
			}
			return arrLfResult;
		}
	
		public double getClosePtDistSqrd() {
			double lfDistSqrd = 
				m_arrLfClosestPt[0]*m_arrLfClosestPt[0] +
				m_arrLfClosestPt[1]*m_arrLfClosestPt[1];
			return lfDistSqrd;
		}

		
		public double getClosePtDist() {
			double lfDistSqrd = 
				m_arrLfClosestPt[0]*m_arrLfClosestPt[0] +
				m_arrLfClosestPt[1]*m_arrLfClosestPt[1];
			return Math.sqrt(lfDistSqrd);
		}
		
	public double [] getEdgeEndClip(double lfMaxLen, double lfBigClip) {
		if(m_bEnd) {
			lfMaxLen = m_lfEnd;
			// lfMaxLen = Math.min(lfMaxLen, m_lfEnd);
		}  else if(m_bStart) {
			lfMaxLen += m_lfStart;
		}
		lfMaxLen = Math.max(-lfBigClip, lfMaxLen);
		lfMaxLen = Math.min(lfBigClip, lfMaxLen);
		double [] arrLfResult = new double[2];
		arrLfResult[0] = m_arrLfClosestPt[0] +
			lfMaxLen*m_arrLfDirVec[0];
		arrLfResult[1] = m_arrLfClosestPt[1] +
			lfMaxLen*m_arrLfDirVec[1];
		if(bDebug && !CheckValid()) {
			System.out.println("Invalid edge");
		}
		return arrLfResult;
	}
}

	
	Vector<Edge> m_vecEdges;
	//	Vector<Integer> m_vecIndices;
	int m_nIterIdx;

	double m_arrLfPtCenter[];

	public DistributedDelaunayClip() {
		m_vecEdges = new Vector<Edge>();
		//m_vecIndices = new Vector<Integer>();
		m_arrLfPtCenter = new double[2];
		m_nIterIdx = 0;
	}

	public DistributedDelaunayClip(double lfXCen, double lfYCen) {
		m_vecEdges = new Vector<Edge>();
		// m_vecIndices = new Vector<Integer>();
		m_arrLfPtCenter = new double[2];
		m_arrLfPtCenter[0] = lfXCen; m_arrLfPtCenter[1] = lfYCen;
		m_nIterIdx = 0;
	}

	public DistributedDelaunayClip(DistributedDelaunayClip src) {
		m_vecEdges = new Vector<Edge>(src.m_vecEdges.size());
		for(int i = 0; i < src.m_vecEdges.size(); ++i) {
			m_vecEdges.add(new Edge(src.m_vecEdges.elementAt(i)));
		}
		m_arrLfPtCenter = MathUtils.arrDblCpy(src.m_arrLfPtCenter,2);
		m_nIterIdx = src.m_nIterIdx;
	}

	DistributedDelaunayClip(DistributedDelaunayClip src, int nIdx) {
		m_vecEdges = src.m_vecEdges;
		m_arrLfPtCenter = src.m_arrLfPtCenter;
		m_nIterIdx = nIdx;
	}
	
	public Iterator<DistributedDelaunayClip.Edge> iterator() {
		return new DistributedDelaunayClip(this,0);
	}
	
	public void addEdge(int nIdx, double lfX, double lfY) {
		Edge currEdge = new Edge(0.5*(lfX-m_arrLfPtCenter[0]),
				0.5*(lfY-m_arrLfPtCenter[1]));
		for(int i = 0; i < m_vecEdges.size(); ++i) {
			Edge edgeToIsect = m_vecEdges.elementAt(i);
			currEdge.clipWith(edgeToIsect);
			edgeToIsect.clipWith(currEdge);
		}
		currEdge.setId(nIdx);
		// m_vecIndices.add(new Integer(nIdx));
		m_vecEdges.add(currEdge);
	}

	public double [] getEdgeStart(Edge e, double lfMaxRad) {
		double lfMaxLen = Math.sqrt(
				Math.max(0.0, lfMaxRad*lfMaxRad - 
						e.getClosePtDistSqrd()));
		double [] arrLfResult = e.getEdgeStartClip(lfMaxLen, lfMaxLen);
		arrLfResult[0] += m_arrLfPtCenter[0];
		arrLfResult[1] += m_arrLfPtCenter[1];
		return arrLfResult;
	}
	
	public double [] getEdgeEnd(Edge e, double lfMaxRad) {
		double lfMaxLen = Math.sqrt(
				Math.max(0.0, lfMaxRad*lfMaxRad - 
						e.getClosePtDistSqrd()));
		double [] arrLfResult = e.getEdgeEndClip(lfMaxLen, lfMaxLen);
		arrLfResult[0] += m_arrLfPtCenter[0];
		arrLfResult[1] += m_arrLfPtCenter[1];
		return arrLfResult;
	}
	
	// iterator interface implementatiosn
	public boolean hasNext() 
	{
		if(m_nIterIdx >= m_vecEdges.size()) {
			return false;
		}
		Edge currEdge = m_vecEdges.elementAt(m_nIterIdx);
		boolean bValid = currEdge.edgeValid();
		while(!bValid && m_nIterIdx < m_vecEdges.size()-1) {
			++m_nIterIdx;
			currEdge = m_vecEdges.elementAt(m_nIterIdx);
			bValid = currEdge.edgeValid();
		}
		return bValid;
	}
	
	public void remove() {
		throw new UnsupportedOperationException();
	}
	public DistributedDelaunayClip.Edge next() 
	{
		if(!hasNext()) {
			return null;
		}
		Edge edgeResult = m_vecEdges.elementAt(m_nIterIdx);
		++m_nIterIdx;
		return edgeResult;
	}
}