/*******************************************************************************
 * 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.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import edu.duke.donaldLab.jdshot.disco.AnnulusIndex.AnnulusEntry;
import edu.duke.donaldLab.jdshot.disco.cgal.Arrangement;
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.Hole;
import edu.duke.donaldLab.jdshot.disco.cgal.ShotCgal;
import edu.duke.donaldLab.jdshot.disco.cgal.Vertex;
import edu.duke.donaldLab.share.nmr.DistanceRestraint;
import edu.duke.donaldLab.share.perf.Progress;
import edu.duke.donaldLab.share.protein.AtomAddressInternal;

public class ArrangementDepthCalculator
{
	/**************************
	 *   Definitions
	 **************************/
	
	private static class Node
	{
		public Face face;
		public Halfedge crossedHalfedge;
		public int previousDepth;
		
		public Node( Face face, Halfedge crossedHalfedge, int previousDepth )
		{
			this.face = face;
			this.crossedHalfedge = crossedHalfedge;
			this.previousDepth = previousDepth;
		}
	}
	
	
	/**************************
	 *   Data Members
	 **************************/
	
	private Arrangement m_arrangement;
	private Progress m_progress;
	private List<AnnulusIndex> m_annulusIndices;
	private LinkedList<Node> m_unexploredNodes;
	
	
	/**************************
	 *   Constructors
	 **************************/
	
	public ArrangementDepthCalculator( Arrangement arrangement, Progress progress, List<AnnulusIndex> annulusIndices )
	{
		m_arrangement = arrangement;
		m_progress = progress;
		m_annulusIndices = annulusIndices;
		m_unexploredNodes = new LinkedList<Node>();
	}
	
	
	/**************************
	 *   Methods
	 **************************/
	
	public void computeDepths( )
	{
		// initialize all faces with depth -1
		for( Face face : m_arrangement )
		{
			face.setData( -1 );
		}
		
		m_unexploredNodes.clear();
		
		// start with the unbounded face at a depth of 0
		m_arrangement.getUnboundedFace().setData( 0 );
		m_progress.incrementProgress();
		explore( m_arrangement.getUnboundedFace() );
		
		// BFS
		while( !m_unexploredNodes.isEmpty() )
		{
			Node node = m_unexploredNodes.pollFirst();
			
			// does this node already have a depth?
			if( node.face.getData() != -1 )
			{
				continue;
			}
			
			// find which index contains this circle
			// and get the unions whose boundaries contains the crossed edge
			List<ArrayList<AnnulusEntry>> unions = null;
			for( AnnulusIndex index : m_annulusIndices )
			{
				Set<DistanceRestraint<AtomAddressInternal>> restraints = index.getRestraints( node.crossedHalfedge.getCircle() );
				if( restraints != null )
				{
					unions = new ArrayList<ArrayList<AnnulusEntry>>();
					for( DistanceRestraint<AtomAddressInternal> restraint : restraints )
					{
						unions.add( index.getEntries( restraint ) );
					}
				}
			}
			assert( unions != null );
			
			// is this edge interior to a union?
			int depth = node.previousDepth;
			for( ArrayList<AnnulusEntry> union : unions )
			{
				if( !isInteriorEdge( node.crossedHalfedge, union ) )
				{
					// compute the new depth
					Circle supportingCircle = node.crossedHalfedge.getCircle();
					switch( supportingCircle.getOrientation() )
					{
						case Counterclockwise:
							// outer boundaries are ccw
							if( supportingCircle.isOnBoundedSide( node.face ) )
							{
								// we entered the circle
								depth += 1;
							}
							else
							{
								// we left the circle
								depth -= 1;
							}
						break;
						
						case Clockwise:
							// inner boundaries are cw
							if( supportingCircle.isOnBoundedSide( node.face ) )
							{
								// we entered the circle
								depth -= 1;
							}
							else
							{
								// we left the circle
								depth += 1;
							}
						break;
					}
				}
			}
			node.face.setData( depth );
			explore( node.face );
			
			m_progress.incrementProgress();
			ShotCgal.cleanupUnreferenced();
		}
		
		ShotCgal.cleanupUnreferenced();
	}
	
	
	/**************************
	 *   Functions
	 **************************/
	
	private void explore( Face face )
	{
		// explore adjacent faces along the outer boundary
		if( !face.isUnbounded() )
		{
			for( Halfedge halfedge : face )
			{
				Face adjacentFace = halfedge.getAdjacentFace();
				if( adjacentFace.getData() == -1 )
				{
					m_unexploredNodes.add( new Node( adjacentFace, halfedge, face.getData() ) );
				}
			}
		}
		
		// explore adjaces faces along the interior boundaries
		for( Hole hole : face.holes() )
		{
			for( Halfedge halfedge : hole )
			{
				Face adjacentFace = halfedge.getAdjacentFace();
				if( adjacentFace.getData() == -1 )
				{
					m_unexploredNodes.add( new Node( adjacentFace, halfedge, face.getData() ) );
				}
			}
		}
	}
	
	private boolean isInteriorEdge( Halfedge crossedHalfedge, ArrayList<AnnulusEntry> union )
	{
		// UNDONE: check the midpoint instead of the edges!
		
		// are either of the end points of the edge in the interior of an annulus?
		return isInteriorVertex( crossedHalfedge.getSource(), union )
			|| isInteriorVertex( crossedHalfedge.getTarget(), union );
	}
	
	private boolean isInteriorVertex( Vertex vertex, ArrayList<AnnulusEntry> union )
	{
		for( AnnulusEntry entry : union )
		{
			if( entry.outerCircle == null )
			{
				continue;
			}
			else if( entry.outerCircle.isOnBoundedSide( vertex ) )
			{
				if( entry.innerCircle == null )
				{
					return true;
				}
				else if( entry.innerCircle.isOnUnboundedSide( vertex ) )
				{
					return true;
				}
			}
		}
		return false;
	}
}
