package edu.claflin.finder.algo.clustering;

import static edu.claflin.finder.Global.getLogger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

import edu.claflin.finder.algo.ArgumentsBundle;
import edu.claflin.finder.log.LogLevel;
import edu.claflin.finder.logic.Graph;
import edu.claflin.finder.logic.Node;

/**
 * TODO: MAKE COMMENTS NICE 
 * abc 
 * @author Adam
 *
 */
public class LabelPropagation extends ClusteringAlgorithm
{

	/**
	 * Label Propagation Algorithm (LPA) for Community Detection. Based on python's igraph library.
	 * 
	 * @see <a href="https://arxiv.org/pdf/0709.2938.pdf">Original Paper</a> 
	 * @see <a href="https://github.com/igraph/igraph/blob/master/src/community/label_propagation.c">Original igraph implementation</a>
	 * @param args args 
	 * @author Adam Samson, Damani Cephas, and Gabriel Albuquerque Ribeiro
	 */
	public LabelPropagation(ArgumentsBundle args)
	{
		super(args);

		if (getLogger() != null)
		{
			getLogger().logInfo(LogLevel.DEBUG, "Label Propagation algorithm initialized.");
		}

	}

	@Override
	public String toString()
	{
		return "Label Propagation Algorithm";
	}

	/**
	 * Makes a random order for LPA algorithm. 
	 *
	 * @param allNodes is the list of nodes 
	 * @return The a random order for node changing in the next iteration. 
	 */
	public List<Node> generateRandomOrder(List<Node> allNodes)
	{
		Collections.shuffle(allNodes);

		return allNodes;
	}

	/**
	 * Performs FastGreedy community detection on a given Graph, returning the
	 * clustering with the maximum modularity.
	 *
	 * @param target the Graph to perform FastGreedy on
	 * @param labels the Graph to perform FastGreedy on
	 * @param graph the Graph to perform function on
	 * @return the list of Graphs representing the clustering with the maximum
	 *         modularity
	 */
	private List<Node> generateCommunityFromLabel(int target, int[] labels, Graph graph)
	{
		List<Node> originalNodeList = graph.getNodeList();
		List<Node> community = new ArrayList<Node>();
		for (int i = 0; i < labels.length; i++)
		{
			if (labels[i] == target)
				community.add(originalNodeList.get(i));
		}
		return community;
	}

	/**
	 * Performs Label Propagation (LPA) community detection on a given Graph, returning the
	 * significant communities present within a network.
	 *
	 * @param graph the Graph to perform LPA on
	 * @return the list of Graphs representing the significant partitioned clusters. 
	 */
	@Override
	public ArrayList<Graph> process(Graph graph)
	{
		if (getLogger() != null)
		{
			getLogger().logAlgo(LogLevel.NORMAL,
					"Label Propagation: Searching Graph: " + graph.getName());
		}

		if (graph.getNodeCount() < 1)
		{
			return new ArrayList<Graph>();
		}
		
		//INITIALIZE LABEL ARRAY WITH INCREMENTING INTS. [0, 1, 2, 3, ... n - 1] | STEP #1
		int[] labels = new int[graph.getNodeCount()];
		for (int i = 0; i < labels.length; i++)
			labels[i] = i;
		int[] previousLabels = Arrays.copyOf(labels, graph.getNodeCount());

		//DONT 'NEED' VAR T DUE TO KEEPING CONSTANT ARRAY OF LABELS. | STEP #2
		int t = 1;
		
		Communities initialCm = new Communities(graph, isWeighted());
		double maxModularity = initialCm.modularity();
		while (t < 500)
		{
			//FILL LIST WITH ALL NODES & SHUFFLE ORDER | STEP #3 (Begin LPA Loop)
			List<Node> randomOrder = generateRandomOrder(graph.getNodeList());
			//System.out.println("\nRandom order for " + "#" + t + " iteration: " + randomOrder.toString());

			for (int i = 0; i < randomOrder.size(); i++)
			{ //FOR EACH NODE, SET IT'S LABEL TO THE GREATEST REPRESENTED OF ITS NEIGHBORS | STEP #4
				Node currentNode = randomOrder.get(i);
				int originalIndex = graph.getNodeIndex(currentNode);
				int label = labels[originalIndex];
				// -->WE HAVE A RANDOM NODE WITH A LABEL

				// -->GET ALL OF THE NODE'S NEIGHBOR'S LABELS (weights later)
				List<Node> neighbors = currentNode.getNeighbors();
				int[] neighborLabels = new int[neighbors.size()];
				for (int j = 0; j < neighbors.size(); j++)
				{
					neighborLabels[j] = labels[graph.getNodeIndex(neighbors.get(j))];
				}

				int[] labelCount = new int[labels.length]; //ARRAY OF COUNT FOR EACH NEIGHBOR LABEL: [0, 0, 0, 0,...]
				for (int j = 0; j < labelCount.length; j++)
				{ //SET COUNTS TO 0 via LOOP
					labelCount[j] = 0;
				}

				//System.out.println("For node " + currentNode +" with label: "+ label + " the neighbors are: " + neighbors.toString());
				//System.out.println("\tTHE NEIGHBOR LABELS FOR THIS ITERATION ARE: " + Arrays.toString(neighborLabels));

				for (int j = 0; j < neighborLabels.length; j++)
				{
					int currentLabel = neighborLabels[j];
					labelCount[currentLabel] += 1;
					//System.out.println("\tThe count of " + currentLabel + " is equal to " + labelCount[currentLabel]);
				}
				/*
				 * ALGORITHM VARIABLE OUTLINE:
				 * currentNode ---- The node in the (randomized) order currently having it's label changes
				 * label ---------- the label of the currentNode
				 * neighbors ------ the list of attached nodes to our currentNode
				 * neighborLabels - An array of the attached labels to currentNode
				 * labelCount ----- A count of how many time(s) a label is represented/attached to currentNode
				 */

				//Find maximum weighted label(s)
				int requiredWeight = 0;
				for (int j = 0; j < labelCount.length; j++)
				{
					if (labelCount[j] > requiredWeight)
						requiredWeight = labelCount[j];
				}

				//Add labels that are 'most represented' to List
				List<Integer> accquiredLabels = new ArrayList<Integer>();
				for (int j = 0; j < labelCount.length; j++)
				{
					if (labelCount[j] == requiredWeight)
						accquiredLabels.add(j);
				}

				//System.out.println("\tAfter this iteration, the most represented labels are: " + accquiredLabels.toString());
				Collections.shuffle(accquiredLabels); //When multiple labels tie, pick a random one.
				if (!accquiredLabels.contains(label)) //If one of the multiple labels is the current label, do nothing. 
					labels[originalIndex] = accquiredLabels.get(0);

				//System.out.println("The new label for " + currentNode + " is " + accquiredLabels.get(0) + "\n");

			}

			t++;
//			System.out.println("The original node list was.............: " + graph.getNodeList().toString());
//			System.out.println("The final labels after " + t + " iteration is: " + Arrays.toString(labels) + "\n\n");

			//System.out.println("PREV:" + Arrays.toString(previousLabels));
			//System.out.println("CURRENT:" + Arrays.toString(labels));

			if (Arrays.equals(labels, previousLabels))
				break;
			previousLabels = Arrays.copyOf(labels, graph.getNodeCount());

			Map<Integer, List<Node>> community = new HashMap<Integer, List<Node>>();

			Set<Integer> uniqueLabels = Arrays.stream(labels).boxed().collect(Collectors.toSet());
			for (Integer label : uniqueLabels)
				community.put(label, generateCommunityFromLabel(label, labels, graph));
			
			Communities cm = new Communities(community, graph, isWeighted());
			double currentMod = cm.modularity();
			if (currentMod > maxModularity)
			{
				maxModularity = currentMod;
				initialCm = cm;
			}
			//System.out.println("Current mod: " + currentMod);
		}
		
		if (getLogger() != null)
		{
			getLogger().logAlgo(LogLevel.NORMAL,
					"Label Propagation: Algorithm done. Getting Clustering with Maximum Modularity");
		}
		//System.out.println("!!! LABEL PROPAGATION COMPLETE !!!\nTHE NUMBER OF ITERATIONS NEEDED WAS: " + t + "\n\n");
		return cull(this.buildCommunityGraphs(initialCm.getList(), graph, "Label Propagation"));
	}
}
