/*
 * Created on 24-Aug-2004 by Ryan McNally
 */

package com.speckled.specksim.imp.stats;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import com.ryanm.util.math.Statistics;
import com.speckled.specksim.imp.state.NeighbourhoodAware;
import com.speckled.specksim.imp.state.NeighbourhoodProcessor;
import com.speckled.specksim.state.SpeckState;
import com.speckled.specksim.state.StateSink;
import com.speckled.specksim.statistics.StatisticsModule;

/**
 * This statistics module provides:
 * <ul>
 * <li>Average Neighbourhood size</li>
 * <li>Average Neighbourhood as a percentage of the total number of
 * specks</li>
 * </ul>
 * NB: Non-NeighbourhoodAware specks are not included in these
 * calculations
 * 
 * @author ryanm
 */
public class NeighbourhoodModule extends StatisticsModule
{
	@Override
	public String getName()
	{
		return "Neighbourhood";
	}

	@Override
	public float[] generateStatistics( StateSink state )
	{
		SpeckState[] specks = state.getState().getSpecks();
		boolean neighbourFound = false;

		int speckCount = 0;

		double[] neighbourhoodSizes = new double[ specks.length ];

		for( int i = 0; i < specks.length; i++ )
		{
			if( specks[ i ] instanceof NeighbourhoodAware && isIncluded( i ) )
			{
				neighbourFound = true;
				speckCount++;
				int[] neighbourIDs = ( ( NeighbourhoodAware ) specks[ i ] ).getNeighbourIDs();

				assert neighbourIDs != null : "NeighbourhoodAware speck states cannot return null when asked for neighbour ids";

				neighbourhoodSizes[ i ] = neighbourIDs.length;
			}
			else
			{
				neighbourhoodSizes[ i ] = Double.NaN;
			}
		}

		int[][] neighbourIndices =
				( ( NeighbourhoodProcessor ) state.getProcessor( NeighbourhoodProcessor.NAME ) )
						.getNeighbourIndices();

		// build the subgraphs
		int[] lowestLinkedIndex = new int[ state.getState().getSpecks().length ];
		for( int i = 0; i < lowestLinkedIndex.length; i++ )
		{
			lowestLinkedIndex[ i ] = -1;
		}
		for( int i = 0; i < lowestLinkedIndex.length; i++ )
		{
			if( specks[ i ] instanceof NeighbourhoodAware && isIncluded( i ) )
			{
				markNeighbours( i, i, lowestLinkedIndex, neighbourIndices );
			}
		}

		// count the subgraphs
		Map<Integer, Integer> graphSizes = new HashMap<Integer, Integer>();
		Integer zero = new Integer( 0 );
		int maxSize = -1;
		for( int i : lowestLinkedIndex )
		{
			Integer index = new Integer( i );
			if( !graphSizes.containsKey( index ) )
			{
				graphSizes.put( index, zero );
			}

			Integer size = new Integer( graphSizes.get( index ).intValue() + 1 );
			graphSizes.put( index, size );

			maxSize = Math.max( maxSize, size.intValue() );
		}

		if( neighbourFound )
		{
			double[] meanDev = Statistics.calculateMeanDeviation( neighbourhoodSizes );

			float meanN = ( float ) meanDev[ 0 ];

			return new float[] { meanN, ( ( float ) meanDev[ 1 ] ), ( meanN / ( speckCount - 1 ) ),
					graphSizes.size(), maxSize, ( float ) maxSize / speckCount };
		}

		return null;
	}

	@Override
	protected String[] statisticNames()
	{
		return new String[] { "Mean Neighbourhood", "Neighbourhood standard deviation",
				"Mean Neighbourhood coverage", "Disconnected subgraphs", "Largest subgraph size",
				"Largest subgraph coverage" };
	}

	@Override
	protected String[] statisticDescriptions()
	{
		return new String[] {
				"The average number of one-hop neighbours a speck has",
				"The standard deviation of neighbourhood sizes over the entire network",
				"The fraction of specks in the network that is included in the average neighbourhood",
				"The number of discrete sub-networks i.e. groups of specks that cannot communicate due to network disconnects",
				"The number of specks included in the most populous discrete sub-network",
				"The fraction of specks in the network that is included in the most populous discrete sub-network" };
	}

	/**
	 * Performs a flood-fill of the graph
	 * 
	 * @param index
	 * @param lowestLinkedIndex
	 * @param lowestEncounteredIndex
	 * @param neighbourIndices
	 */
	private void markNeighbours( int index, int lowestLinkedIndex, int[] lowestEncounteredIndex,
			int[][] neighbourIndices )
	{
		if( lowestEncounteredIndex[ index ] == -1
				|| lowestEncounteredIndex[ index ] > lowestLinkedIndex )
		{

			lowestEncounteredIndex[ index ] = lowestLinkedIndex;

			for( int i : neighbourIndices[ index ] )
			{
				// only follow two-way links
				if( isLinked( i, index, neighbourIndices ) )
				{
					markNeighbours( i, lowestLinkedIndex, lowestEncounteredIndex, neighbourIndices );
				}
			}
		}
	}

	/**
	 * Check if there is a link from A to B
	 * 
	 * @param indexA
	 *           The index of speck A
	 * @param indexB
	 *           The index of speck B
	 * @param neighbourhoods
	 *           The neighbourhoods
	 * @return true if there is a neighbourhood link between A and B
	 */
	private boolean isLinked( int indexA, int indexB, int[][] neighbourhoods )
	{
		if( indexA != -1 )
		{
			return Arrays.binarySearch( neighbourhoods[ indexA ], indexB ) >= 0;
		}

		return false;
	}

}