/*******************************************************************************
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 * USA
 * 
 * Contact Info:
 * 	Bruce Donald
 * 	Duke University
 * 	Department of Computer Science
 * 	Levine Science Research Center (LSRC)
 * 	Durham
 * 	NC 27708-0129 
 * 	USA
 * 	brd@cs.duke.edu
 * 
 * Copyright (C) 2011 Jeffrey W. Martin and Bruce R. Donald
 * 
 * <signature of Bruce Donald>, April 2011
 * Bruce Donald, Professor of Computer Science
 ******************************************************************************/


package edu.duke.donaldLab.jdshot.disco;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;

import edu.duke.donaldLab.jdshot.disco.cgal.Box;
import edu.duke.donaldLab.jdshot.disco.cgal.Circle;
import edu.duke.donaldLab.jdshot.disco.cgal.Face;
import edu.duke.donaldLab.jdshot.disco.cgal.Halfedge;
import edu.duke.donaldLab.jdshot.disco.cgal.Circle.Side;
import edu.duke.donaldLab.share.geom.Annulus2;
import edu.duke.donaldLab.share.geom.CircularArc;
import edu.duke.donaldLab.share.geom.Vector2;
import edu.duke.donaldLab.share.nmr.DistanceRestraint;
import edu.duke.donaldLab.share.protein.AtomAddressInternal;

public class FaceInfo implements Serializable
{
	/**************************
	 *   Definitions
	 **************************/
	
	private static final long serialVersionUID = -8491335221820111692L;
	
	
	/**************************
	 *   Fields
	 **************************/
	
	public LinkedHashMap<DistanceRestraint<AtomAddressInternal>,Boolean> satisfaction;
	public ArrayList<Circle> circles;
	public ArrayList<Vector2> vertices;
	public Box boundingBox;
	
	public transient ArrayList<CircularArc> edges;
	
	// UNDONE: this class could be definitely be re-factored to make these private
	//         so callers don't have to worry about the edges list
	
	
	/**************************
	 *   Constructors
	 **************************/
	
	public FaceInfo( Face face )
	{
		this( face, null );
	}
	
	public FaceInfo( Face face, LinkedHashMap<DistanceRestraint<AtomAddressInternal>,Boolean> satisfaction )
	{
		this( satisfaction, face.getBoundingBox() );
		
		// get the circles and vertices
		int numHalfedges = face.getNumHalfedges();
		circles = new ArrayList<Circle>( numHalfedges );
		vertices = new ArrayList<Vector2>( numHalfedges );
		int i = 0;
		for( Halfedge halfedge : face.transientHalfedges() )
		{
			circles.add( halfedge.getCircle() );
			vertices.add( halfedge.getSource().toPoint() );
			i++;
		}
		
		edges = edges();
	}
	
	private FaceInfo( LinkedHashMap<DistanceRestraint<AtomAddressInternal>,Boolean> satisfaction, Box boundingBox )
	{
		this.satisfaction = null;
		if( satisfaction != null )
		{
			this.satisfaction = new LinkedHashMap<DistanceRestraint<AtomAddressInternal>,Boolean>( satisfaction );
		}
		this.boundingBox = boundingBox;
	}
	
	
	/**************************
	 *   Static Methods
	 **************************/
	
	public static FaceInfo merge( FaceInfo left, FaceInfo right, List<CircularArc> sharedEdges )
	{
		// just in case...
		assert( left.satisfaction.equals( right.satisfaction ) );
		assert( sharedEdges != null );
		assert( !sharedEdges.isEmpty() );
		
		// create the merged face, but don't define the geometry yet
		Box boundingBox = new Box( left.boundingBox );
		boundingBox.expand( right.boundingBox );
		FaceInfo merged = new FaceInfo( left.satisfaction, boundingBox );
		
		// locate the first edges in the exclusive chains
		int leftStartIndex = getExclusiveEdgeStartIndex( left.edges, sharedEdges );
		int numLeftEdges = left.edges.size() - sharedEdges.size();
		int rightStartIndex = getExclusiveEdgeStartIndex( right.edges, sharedEdges );
		int numRightEdges = right.edges.size() - sharedEdges.size();
		
		merged.circles = new ArrayList<Circle>();
		merged.vertices = new ArrayList<Vector2>();
		
		if( leftStartIndex == -1 && rightStartIndex == -1 )
		{
			throw new RuntimeException( "Faces to merge don't share any edges!" );
		}
		
		if( leftStartIndex >= 0 )
		{
			// add the left exclusive edges to the merged face
			for( int i=0; i<numLeftEdges; i++ )
			{
				int leftIndex = ( i + leftStartIndex ) % left.edges.size();
				merged.circles.add( left.circles.get( leftIndex ) );
				merged.vertices.add( left.vertices.get( leftIndex ) );
			}
		}
		else if( leftStartIndex == -2 )
		{
			// left exclusive edges have multiple chains, don't merge these faces
			return null;
		}
		// else: left face is a hole in the right face, so don't add its edges
		
		if( rightStartIndex >= 0 )
		{
			// add the right exclusive edges to the merged face
			for( int i=0; i<numRightEdges; i++ )
			{
				int rightIndex = ( i + rightStartIndex ) % right.edges.size();
				merged.circles.add( right.circles.get( rightIndex ) );
				merged.vertices.add( right.vertices.get( rightIndex ) );
			}
		}
		else if( rightStartIndex == -2 )
		{
			// right exclusive edges have multiple chains, don't merge these faces
			return null;
		}
		// else: right face is a hole in the left face, so don't add its edges
		
		// don't forget to update the edges cache
		merged.edges = merged.edges();
		
		return merged;
	}
	
	public static Vector2 getPointClosestTo( List<FaceInfo> faces, Vector2 q )
	{
		Vector2 closestPoint = null;
		double closestDistSq = Double.POSITIVE_INFINITY;
		for( FaceInfo face : faces )
		{
			Vector2 point = face.getPointClosestTo( q );
			if( point == null )
			{
				return null;
			}
			double distSq = point.getSquaredDistance( q );
			if( distSq < closestDistSq )
			{
				closestPoint = point;
				closestDistSq = distSq;
			}
		}
		return closestPoint;
	}
	
	public static Vector2 getPointFarthestFrom( List<FaceInfo> faces, Vector2 q )
	{
		Vector2 farthestPoint = null;
		double farthestDistSq = 0.0;
		for( FaceInfo face : faces )
		{
			Vector2 point = face.getPointFarthestFrom( q );
			double distSq = point.getSquaredDistance( q );
			if( distSq > farthestDistSq )
			{
				farthestPoint = point;
				farthestDistSq = distSq;
			}
		}
		return farthestPoint;
	}
	

	/**************************
	 *   Methods
	 **************************/
	
	public int getNumRestraints( )
	{
		return satisfaction.size();
	}
	
	public int getNumSatisfiedRestraints( )
	{
		int count = 0;
		for( Boolean isSatisfied : satisfaction.values() )
		{
			if( isSatisfied )
			{
				count++;
			}
		}
		return count;
	}
	
	public boolean containsPoint( Vector2 point )
	{
		// quick check against the bounding box
		if( !boundingBox.containsPoint( point ) )
		{
			return false;
		}
		
		// long check against the circles
		for( Circle circle : circles )
		{
			switch( circle.getOrientation() )
			{
				case Clockwise:
					// point must be outside
					if( circle.getSide( point ) == Side.BoundedSide )
					{
						return false;
					}
				break;
				
				case Counterclockwise:
					// point must be inside
					if( circle.getSide( point ) == Side.UnboundedSide )
					{
						return false;
					}
				break;
			}
		}
		
		return true;
	}
	
	public ArrayList<CircularArc> edges( )
	{
		return edges( 0 );
	}
	
	public ArrayList<CircularArc> edges( int startIndex )
	{
		// collect the arcs in a list
		ArrayList<CircularArc> newEdges = new ArrayList<CircularArc>();
		for( int i=0; i<vertices.size(); i++ )
		{
			// compute the start and stop indices
			int from = ( startIndex + i ) % vertices.size();
			int to = ( startIndex + i + 1 ) % vertices.size();
			
			newEdges.add( new CircularArc( circles.get( from ).toCircle(), vertices.get( from ), vertices.get( to ) ) );
		}
		return newEdges;
	}
	
	public Vector2 getPointFarthestFrom( Vector2 q )
	{
		double maxDistSq = 0.0;
		Vector2 farthestPoint = null;
		for( CircularArc arc : edges )
		{
			Vector2 point = arc.getPointFarthestFrom( q );
			double distSq = point.getSquaredDistance( q );
			if( distSq > maxDistSq )
			{
				maxDistSq = distSq;
				farthestPoint = point;
			}
		}
		return farthestPoint;
	}
	
	public Vector2 getPointClosestTo( Vector2 q )
	{
		// we don't care about the closest point if the face contains q
		if( containsPoint( q ) )
		{
			return null;
		}
		
		double minDistSq = Double.POSITIVE_INFINITY;
		Vector2 closestPoint = null;
		for( CircularArc arc : edges )
		{
			Vector2 point = arc.getPointClosestTo( q );
			double distSq = point.getSquaredDistance( q );
			if( distSq < minDistSq )
			{
				minDistSq = distSq;
				closestPoint = point;
			}
		}
		return closestPoint;
	}
	
	public boolean intersects( Annulus2 annulus )
	{
		Vector2 closestPoint = getPointClosestTo( annulus.center );
		Vector2 farthestPoint = getPointFarthestFrom( annulus.center );
		
		double innerDist = closestPoint != null ? annulus.center.getDistance( closestPoint ) : 0.0;
		double outerDist = annulus.center.getDistance( farthestPoint );
		
		return ( innerDist >= annulus.minRadius && innerDist <= annulus.maxRadius )
			|| ( outerDist >= annulus.minRadius && outerDist <= annulus.maxRadius );
	}
	
	public ArrayList<CircularArc> getSharedEdges( FaceInfo other )
	{
		// return all edges the two faces share in common, but detect if they span multiple chains
		ArrayList<CircularArc> sharedEdges = new ArrayList<CircularArc>();
		for( CircularArc selfArc : edges )
		{
			for( CircularArc otherArc : other.edges )
			{
				if( selfArc.equals( otherArc ) )
				{
					sharedEdges.add( selfArc );
					break;
				}
			}
		}
		
		// nothing found? No need to examine further
		if( sharedEdges.isEmpty() )
		{
			return sharedEdges;
		}
		
		// a single shared edge is easy
		if( sharedEdges.size() == 1 )
		{
			return sharedEdges;
		}
		
		// if there are multiple chains of shared edges, signal the caller
		if( getNumBreaks( sharedEdges ) > 1 )
		{
			return null;
		}
		
		return sharedEdges;
	}
	
	public void simplify( )
	{
		// collapse edges sharing the same circle
		Circle previousCircle = null;
		for( int i=0; i<circles.size()+1; i++ )
		{
			int thisIndex = i % circles.size();
			int previousIndex = ( i - 1 + circles.size() ) % circles.size();
			int nextIndex = ( i + 1 ) % circles.size();
			
			Circle thisCircle = circles.get( thisIndex );
			if( previousCircle != null && thisCircle.equals( previousCircle ) )
			{
				// examine the edges?
				Vector2 thisPoint = vertices.get( thisIndex );
				Vector2 previousPoint = vertices.get( previousIndex );
				Vector2 nextPoint = vertices.get( nextIndex );
				CircularArc firstEdge = new CircularArc( thisCircle.toCircle(), previousPoint, thisPoint );
				CircularArc secondEdge = new CircularArc( thisCircle.toCircle(), thisPoint, nextPoint );
				
				// are the two edges different and will a merge here preserve x-monotonicity?
				if( !firstEdge.equals( secondEdge ) && firstEdge.getState() == secondEdge.getState() )
				{
					// simplify the edge
					circles.remove( thisIndex );
					vertices.remove( thisIndex );
					i--;
				}
			}
			previousCircle = thisCircle;
		}
		
		edges = edges();
	}
	
	
	/**************************
	 *   Static Functions
	 **************************/
	
	private static int getExclusiveEdgeStartIndex( ArrayList<CircularArc> edges, List<CircularArc> sharedEdges )
	{
		// return the index of the first exclusive edge after a shared edge
		
		// first, find the indices of all first exclusive edges (there can be more than one)
		int numFirstExclusiveEdges = 0;
		boolean isAtLeastOneSharedEdge = false;
		int index = -1;
		for( int i=0; i<edges.size(); i++ )
		{
			int nextIndex = ( i + 1 ) % edges.size();
			boolean thisEdgeIsShared = sharedEdges.contains( edges.get( i ) );
			boolean nextEdgeIsShared = sharedEdges.contains( edges.get( nextIndex ) );
			isAtLeastOneSharedEdge = isAtLeastOneSharedEdge || thisEdgeIsShared || nextEdgeIsShared;
			
			// is this a first exclusive edge?
			if( thisEdgeIsShared && !nextEdgeIsShared )
			{
				numFirstExclusiveEdges++;
				index = nextIndex;
			}
		}
		
		if( numFirstExclusiveEdges == 0 )
		{
			if( isAtLeastOneSharedEdge )
			{
				// all edges must be shared
				return -1;
			}
			else
			{
				throw new RuntimeException( "no edges are shared!" );
			}
		}
		else if( numFirstExclusiveEdges == 1 )
		{
			return index;
		}
		else
		{
			// there's no unique first exclusive edge
			return -2;
		}
	}
	
	private static int getNumBreaks( List<CircularArc> edges )
	{
		int numBreaks = 0;
		for( int i=0; i<edges.size(); i++ )
		{
			CircularArc thisEdge = edges.get( i % edges.size() );
			CircularArc nextEdge = edges.get( ( i + 1 ) % edges.size() );
			
			if( !thisEdge.isAdjacentTo( nextEdge ) )
			{
				numBreaks++;
			}
		}
		return numBreaks;
	}
	
	
	/**************************
	 *   Functions
	 **************************/
	
	private void readObject( ObjectInputStream in )
	throws IOException, ClassNotFoundException
	{
		in.defaultReadObject();
		
		// restore the edge list after deserialization
		edges = edges();
	}
}
