/*******************************************************************************
 * 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.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import org.apache.log4j.Level;
import org.apache.log4j.Logger;

import edu.duke.donaldLab.jdshot.disco.AnnulusIndex.AnnulusEntry;
import edu.duke.donaldLab.jdshot.disco.cgal.Arrangement;
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.ShotCgal;
import edu.duke.donaldLab.share.geom.CircularArc;
import edu.duke.donaldLab.share.geom.Vector2;
import edu.duke.donaldLab.share.math.PointIteratorDelta;
import edu.duke.donaldLab.share.nmr.Assignment;
import edu.duke.donaldLab.share.nmr.DistanceRestraint;
import edu.duke.donaldLab.share.perf.LoggingMessageListener;
import edu.duke.donaldLab.share.perf.Progress;
import edu.duke.donaldLab.share.perf.Timer;
import edu.duke.donaldLab.share.protein.AtomAddressInternal;

public class PositionCalculator
{
	/**************************
	 *   Data Members
	 **************************/
	
	private static final Logger m_log = Logger.getLogger( PositionCalculator.class );
	
	
	/**************************
	 *   Static Methods
	 **************************/
	
	public static Arrangement computeArrangementSweep( List<AnnulusIndex> annulusIndices )
	{
		// collect all the circles
		ArrayList<Circle> circles = getCircles( annulusIndices );
		
		// compute the arrangement
		// NOTE: bulk insert (sweep-line) should be faster than incremental
		m_log.info( String.format( "Computing the arrangement of %d circles...", circles.size() ) );
		Arrangement arrangement = new Arrangement();
		Timer timer = new Timer();
		timer.start();
		arrangement.insertAll( circles );
		timer.stop();
		m_log.info( "Computed arrangement in " + timer.getElapsedTime() );
		
		return arrangement;
	}
	
	public static Arrangement computeArrangementIncremental( List<AnnulusIndex> annulusIndices )
	{
		// collect all the circles
		ArrayList<Circle> circles = getCircles( annulusIndices );
		
		// compute the arrangement incrementally
		m_log.info( String.format( "Computing the arrangement of %d circles...", circles.size() ) );
		Arrangement arrangement = new Arrangement();
		Progress progress = new Progress( circles.size(), 10000, Progress.Model.Quadratic );
		progress.setMessageListener( new LoggingMessageListener( m_log, Level.INFO ) );
		for( Circle circle : circles )
		{
			arrangement.insert( circle );
			progress.incrementProgress();
		}
		m_log.info( "Computed arrangement in " + progress.getElapsedTime() );
		
		return arrangement;
	}
	
	public static ArrayList<FaceInfo> computeMsrs( Arrangement arrangement, List<AnnulusIndex> annulusIndices )
	{
		Timer timer = new Timer();
		timer.start();
		
		// compute the depths of the arrangement
		m_log.info( "Computing depths for " + arrangement.getNumFaces() + " faces..." );
		Progress progress = new Progress( arrangement.getNumFaces(), 10000 );
		progress.setMessageListener( new LoggingMessageListener( m_log, Level.INFO ) );
		new ArrangementDepthCalculator( arrangement, progress, annulusIndices ).computeDepths();
		
		// collect the MSRs
		m_log.info( "Collecting MSRs..." );
		progress = new Progress( arrangement.getNumFaces(), 1000 );
		progress.setMessageListener( new LoggingMessageListener( m_log, Level.INFO ) );
		ArrayList<Face> msrFaces = new ArrayList<Face>();
		int maxDepth = 0;
		for( Face face : arrangement )
		{
			if( face.isUnbounded() )
			{
				continue;
			}
			
			int depth = face.getData();
			if( depth > maxDepth )
			{
				msrFaces.clear();
				maxDepth = depth;
			}
			if( depth == maxDepth )
			{
				msrFaces.add( face );
			}
			progress.incrementProgress();
		}
		ShotCgal.cleanupUnreferenced();
		m_log.info( "Collected " + msrFaces.size() +  " MSRs with depth " + maxDepth );
		
		// compute satisfying restraints
		m_log.info( "Computing MSR Satisfaction..." );
		progress = new Progress( msrFaces.size(), 10000 );
		progress.setMessageListener( new LoggingMessageListener( m_log, Level.INFO ) );
		ArrayList<FaceInfo> msrs = new ArrayList<FaceInfo>( msrFaces.size() );
		for( Face face : msrFaces )
		{
			msrs.add( new FaceInfo( face, getRestraintSatisfaction( annulusIndices, face ) ) );
			progress.incrementProgress();
		}
		
		// merge adjacent faces
		m_log.info( "Merging MSRs..." );
		timer.start();
		mergeFaces( msrs );
		timer.stop();
		m_log.info( String.format( "Merged to %d MSRs : %s.", msrs.size(), timer.getElapsedTime() ) );
		
		ShotCgal.cleanupUnreferenced();
		
		timer.stop();
		m_log.info( "Computed MSRs in total time: " + timer.getElapsedTime() );
		
		return msrs;
	}
	
	public static int getNumRestraints( ArrayList<FaceInfo> msrs )
	{
		return msrs.get( 0 ).getNumRestraints();
	}
	
	public static int getNumSatisfiedRestraints( ArrayList<FaceInfo> msrs )
	{
		return msrs.get( 0 ).getNumSatisfiedRestraints();
	}
	
	public static ArrayList<Vector2> sampleMsrs( ArrayList<FaceInfo> msrs, double resolution )
	{
		return sampleMsrs( msrs, resolution, getMsrsBoundingBox( msrs ) );
	}
	
	public static ArrayList<Vector2> sampleMsrs( ArrayList<FaceInfo> msrs, int numSamples )
	{
		Box box = getMsrsBoundingBox( msrs );
		
		/* NOTE:
			This is a messy iterative search to find the resolution that
			will yield a sampling of at least numSamples points.
			The search will always terminate, but the search won't
			always converge - sometimes it oscillates. However, it will
			always return the best resolution found. Here, best means the
			resolution that returns the smallest number of samples that is
			still greater than numSamples.
		*/
		
		// compute the initial resolution
		double resolution = box.getWidth();
		
		double bestResolution = 0.0;
		int minNumOver = Integer.MAX_VALUE;
		
		ArrayList<Vector2> sampledPoints = null;
		double ratio = 0.0;
		for( int i=0; i<20; i++ )
		{
			sampledPoints = sampleMsrs( msrs, resolution, box );
			
			// is this a good resolution?
			int numOver = sampledPoints.size() - numSamples;
			if( numOver > 0 && numOver < minNumOver )
			{
				minNumOver = numOver;
				bestResolution = resolution;
			}
			
			ratio = (double)sampledPoints.size() / (double)numSamples;
			
			// apply dampening to the ratio to keep it close to 1
			ratio = Math.pow( ratio, 0.2 );
			
			// don't let the ratio get too crazy
			if( ratio < 0.5 )
			{
				ratio = 0.5;
			}
			if( ratio > 2.0 )
			{
				ratio = 2.0;
			}
			
			resolution *= ratio;
			
			// did we win?
			if( sampledPoints.size() == numSamples )
			{
				return sampledPoints;
			}
		}
		
		return sampleMsrs( msrs, bestResolution, box );
	}
	
	public static ArrayList<DistanceRestraint<AtomAddressInternal>> getConsistentRestraints( ArrayList<FaceInfo> msrs, List<DistanceRestraint<AtomAddressInternal>> restraints )
	{
		return getRestraintsByConsistency( msrs, restraints, true );
	}
	
	public static ArrayList<DistanceRestraint<AtomAddressInternal>> getInconsistentRestraints( List<FaceInfo> msrs, List<DistanceRestraint<AtomAddressInternal>> restraints )
	{
		return getRestraintsByConsistency( msrs, restraints, false );
	}
	
	public static ArrayList<DistanceRestraint<AtomAddressInternal>> getRestraintsByConsistency( List<FaceInfo> msrs, List<DistanceRestraint<AtomAddressInternal>> restraints, boolean isConsistent )
	{
		// find out if each distance restraint is satisfied by at least one MSR
		LinkedHashMap<DistanceRestraint<AtomAddressInternal>,Boolean> satisfaction = getRestraintSatisfaction( msrs );
		
		ArrayList<DistanceRestraint<AtomAddressInternal>> satisfiedRestraints = new ArrayList<DistanceRestraint<AtomAddressInternal>>();
		for( DistanceRestraint<AtomAddressInternal> restraint : restraints )
		{
			Boolean isSatisfied = satisfaction.get( restraint );
			if( isSatisfied != null && isSatisfied == isConsistent )
			{
				satisfiedRestraints.add( restraint );
			}
		}
		return satisfiedRestraints;
	}
	
	
	/**************************
	 *   Static Functions
	 **************************/
	
	private static ArrayList<Circle> getCircles( List<AnnulusIndex> annulusIndices )
	{
		// collect the circles (and remove duplicates)
		HashSet<Circle> set = new HashSet<Circle>();
		for( AnnulusIndex annulusIndex : annulusIndices )
		{
			for( Entry<DistanceRestraint<AtomAddressInternal>,HashMap<Assignment<AtomAddressInternal>,AnnulusEntry>> entry : annulusIndex )
			{
				for( AnnulusEntry annulusEntry : entry.getValue().values() )
				{
					if( annulusEntry.innerCircle != null )
					{
						set.add( annulusEntry.innerCircle );
					}
					if( annulusEntry.outerCircle != null )
					{
						set.add( annulusEntry.outerCircle );
					}
				}
			}
		}
		return new ArrayList<Circle>( set );
	}
	
	private static void mergeFaces( ArrayList<FaceInfo> faces )
	{
		while( mergeNextFaces( faces ) );
		
		for( FaceInfo face : faces )
		{
			face.simplify();
		}
	}
	
	private static boolean mergeNextFaces( ArrayList<FaceInfo> msrs )
	{
		// Jeff: 2011-01-08: NOTE UNDONE - this merge code is a big kludegy mess! Maybe I can clean it up later...
		
		// for each pair of faces (in random order)
		for( FaceInfo left : msrs )
		{
			for( FaceInfo right : msrs )
			{
				// don't pair identical faces
				if( left == right )
				{
					continue;
				}
				
				// can these faces possibly be adjacent?
				if( !left.boundingBox.intersects( right.boundingBox ) )
				{
					continue;
				}
				
				// are these faces adjacent?
				ArrayList<CircularArc> sharedEdges = left.getSharedEdges( right );
				if( sharedEdges == null )
				{
					// the two faces share edges, but in multiple chains, skip these faces for now
					continue;
				}
				if( sharedEdges.isEmpty() )
				{
					// the two faces share no edges
					continue;
				}
				
				// remove the shared edges and join the faces
				FaceInfo mergedFace = FaceInfo.merge( left, right, sharedEdges );
				
				// did the merge fail? just skip it. maybe we merged in the wrong order
				if( mergedFace == null )
				{
					continue;
				}
				
				// remove the old faces from the MSRs and replace with the new face
				msrs.remove( left );
				msrs.remove( right );
				msrs.add( mergedFace );
				
				return true;
			}
		}
		
		// nothing was merged
		return false;
	}
	
	private static Box getMsrsBoundingBox( ArrayList<FaceInfo> msrs )
	{
		// compute the grand bounding box
		Box box = null;
		for( FaceInfo msr : msrs )
		{
			if( box == null )
			{
				box = msr.boundingBox;
			}
			else
			{
				box.expand( msr.boundingBox );
			}
		}
		return box;
	}
	
	private static ArrayList<Vector2> sampleMsrs( ArrayList<FaceInfo> msrs, double resolution, Box box )
	{
		// sample the box uniformly
		ArrayList<Vector2> sampledPoints = new ArrayList<Vector2>();
		PointIteratorDelta iter = new PointIteratorDelta(
			2,
			new double[] {
				( box.getXMax() + box.getXMin() ) / 2.0,
				( box.getYMax() + box.getYMin() ) / 2.0
			},
			new double[] { resolution, resolution },
			new double[] {
				( box.getXMax() - box.getXMin() ) / 2.0,
				( box.getYMax() - box.getYMin() ) / 2.0
			}
		);
		Vector2 point = new Vector2();
		while( iter.hasNext() )
		{
			point.set( iter.next() );
			
			// is this point in a MSR?
			for( FaceInfo msr : msrs )
			{
				if( msr.containsPoint( point ) )
				{
					sampledPoints.add( new Vector2( point ) );
				}
			}
		}
		
		return sampledPoints;
	}
	
	private static LinkedHashMap<DistanceRestraint<AtomAddressInternal>,Boolean> getRestraintSatisfaction( List<FaceInfo> msrs )
	{
		LinkedHashMap<DistanceRestraint<AtomAddressInternal>,Boolean> satisfaction = new LinkedHashMap<DistanceRestraint<AtomAddressInternal>,Boolean>();
		for( FaceInfo msr : msrs )
		{
			for( Map.Entry<DistanceRestraint<AtomAddressInternal>,Boolean> entry : msr.satisfaction.entrySet() )
			{
				Boolean satisfied = satisfaction.get( entry.getKey() );
				if( satisfied == null )
				{
					satisfaction.put( entry.getKey(), entry.getValue() );
				}
				else
				{
					satisfaction.put( entry.getKey(), satisfied || entry.getValue() );
				}
			}
		}
		return satisfaction;
	}
	
	private static LinkedHashMap<DistanceRestraint<AtomAddressInternal>,Boolean> getRestraintSatisfaction( List<AnnulusIndex> annulusIndices, Face face )
	{
		LinkedHashMap<DistanceRestraint<AtomAddressInternal>,Boolean> satisfaction = new LinkedHashMap<DistanceRestraint<AtomAddressInternal>,Boolean>();
		for( AnnulusIndex annulusIndex : annulusIndices )
		{
			for( Entry<DistanceRestraint<AtomAddressInternal>,HashMap<Assignment<AtomAddressInternal>,AnnulusEntry>> entry : annulusIndex )
			{
				boolean isSatisfied = isFaceInAnyAnnulus( face, entry.getValue().values() );
				satisfaction.put( entry.getKey(), isSatisfied );
			}
		}
		return satisfaction;
	}
	
	private static boolean isFaceInAnyAnnulus( Face face, Iterable<AnnulusEntry> entries )
	{
		for( AnnulusEntry annulusEntry : entries )
		{
			if( isFaceInAnnulus( face, annulusEntry ) )
			{
				return true;
			}
		}
		return false;
	}
	
	private static boolean isFaceInAnnulus( Face face, AnnulusEntry entry )
	{
		if( entry.outerCircle == null )
		{
			return false;
		}
		
		if( entry.outerCircle.isOnUnboundedSide( face ) )
		{
			return false;
		}
		
		if( entry.innerCircle != null )
		{
			if( entry.innerCircle.isOnBoundedSide( face ) )
			{
				return false;
			}
		}
		
		return true;
	}
}
