/*******************************************************************************
 * 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.share.clustering.distance;

import java.util.ArrayList;
import java.util.LinkedList;

import edu.duke.donaldLab.share.dataStructures.MinHeap;
import edu.duke.donaldLab.share.dataStructures.MinHeapNode;


public class DistanceCluster
{
	/**************************
	 *   Data Members
	 **************************/
	
	private int m_index;
	private DistanceCluster m_child;
	private DistanceCluster m_end;
	private MinHeap<DistanceCluster> m_queue;
	private ArrayList<MinHeapNode<DistanceCluster>> m_map;
	
	
	/**************************
	 *   Constructors
	 **************************/
	
	public DistanceCluster( int index )
	{
		this( index, 16 );
	}
	
	public DistanceCluster( int index, int numPoints )
	{
		// save parameters
		m_index = index;
		
		// init defaults
		m_child = null;
		m_end = this;
		m_queue = null;
		m_map = new ArrayList<MinHeapNode<DistanceCluster>>( numPoints );
		for( int i=0; i<numPoints; i++ )
		{
			m_map.add( null );
		}
	}
	
	
	/**************************
	 *   Accessors
	 **************************/
	
	public int getIndex( )
	{
		return m_index;
	}
	
	public DistanceCluster getChild( )
	{
		return m_child;
	}
	
	
	/**************************
	 *   Methods
	 **************************/
	
	public void init( DistanceMatrix distances, LinkedList<DistanceCluster> clusters )
	{
		// cleanup the old queue if needed
		if( m_queue != null )
		{
			m_queue.clear();
		}
		
		// make a new queue
		int heapSize = clusters.size() == 0 ? 0 : clusters.size() - 1;
		m_queue = new MinHeap<DistanceCluster>( heapSize );
		m_queue.setComparator( new DistanceClusterComparator( distances, this ) );
		
		// add all the pairwise distances to the queue
		for( DistanceCluster cluster : clusters )
		{
			// no self-pairings
			if( cluster == this )
			{
				continue;
			}
			
			addCluster( cluster );
		}
	}
	
	public DistanceCluster getMinDist( )
	{
		return m_queue.getMin();
	}
	
	public void addCluster( DistanceCluster cluster )
	{
		// add the cluster
		MinHeapNode<DistanceCluster> node = m_queue.add( cluster );
		m_map.set( cluster.getIndex(), node );
	}
	
	public void removeCluster( DistanceCluster cluster )
	{
		// lookup the head node index
		int nodeIndex = m_map.get( cluster.getIndex() ).getIndex();
		m_queue.remove( nodeIndex );
	}
	
	public void join( DistanceCluster append, DistanceMatrix distances, LinkedList<DistanceCluster> clusters )
	{
		// handle pointers
		m_end.m_child = append;
		m_end = append.m_end;
		
		// removed cluster doesn't need a queue or links any more
		if( append.m_queue != null )
		{
			append.m_queue.clear();
			append.m_queue = null;
		}
		
		// update this queue
		init( distances, clusters );
	}
	
	public int getReprepresentativeIndex( DistanceMatrix distances )
	{
		// simple naive O(n^2) implementation
		// find the index of min summed distance to all other indices
		
		double minDist = Double.POSITIVE_INFINITY;
		int minIndex = -1;
		
		DistanceClusterIterator iterI = new DistanceClusterIterator( this );
		DistanceClusterIterator iterJ = null;
		while( iterI.hasNext() )
		{
			DistanceCluster clusterI = iterI.next();
			double distSum = 0.0;
			
			iterJ = new DistanceClusterIterator( this );
			while( iterJ.hasNext() )
			{
				DistanceCluster clusterJ = iterJ.next();
				
				// no self-pairings
				if( clusterI == clusterJ )
				{
					continue;
				}
				
				distSum += distances.get( clusterI.getIndex(), clusterJ.getIndex() );
			}
			
			if( distSum < minDist )
			{
				minDist = distSum;
				minIndex = clusterI.getIndex();
			}
		}
		
		// just in case...
		assert( minIndex >= 0 && minIndex < distances.getNumPoints() );
		
		return minIndex;
	}
	
	
	/**************************
	 *   Functions
	 **************************/
}
