/*******************************************************************************
 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
 * in Industry THTH ry.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.utils.datastructures;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;


/**
 * This class contains utilities for finding solutions for a tree of problems.
 * (e.g. path finding, routing, etc)
 * 
 * @author Toni Kalajainen
 */
public class TreeProblem {

	public interface ProblemNode {
		/**
		 * Get the cost to reach this node
		 * @return cost of reaching this node
		 */
		double getCost(); 
		
		/** 
		 * Is this problem node a solution
		 * @return true if this node is a solution
		 */
		boolean isComplete();
		
		/**
		 * Branch this problem into sub-problem
		 * @param list add sub-problems to the list
		 */
		void branch(Collection<ProblemNode> list);
	}
	
	private final static Comparator<ProblemNode> COST_COMPARATOR =
		new Comparator<ProblemNode>() {
			@Override
			public int compare(ProblemNode o1, ProblemNode o2) {
				double c1 = o1.getCost();
				double c2 = o2.getCost();
				if (c1<c2) return -1;
				if (c1>c2) return 1;
				return 0;
			}};

    /**
     * Find any solution greedily (not optimal)
     * 
     * @param root
     * @return a node that is complete, i.e. solves the specified problem or
     *         <code>null</code> if no solution was found
     */
	public static ProblemNode findSolution(ProblemNode root, int degree)
	{
		LinkedList<LinkedList<ProblemNode>> stack = new LinkedList<LinkedList<ProblemNode>>();		
		LinkedList<ProblemNode> lst = new LinkedList<ProblemNode>();		
		lst.add(root);
		stack.add(lst);
		while (!stack.isEmpty()) {
			lst = stack.peekLast();
			ProblemNode b = lst.removeFirst();
			if (lst.isEmpty()) stack.removeLast();
			if (b.isComplete()) return b;
			lst = new LinkedList<ProblemNode>();
			b.branch(lst);
			if (!lst.isEmpty()) {
				Collections.sort(lst, COST_COMPARATOR);
				stack.addLast(lst);
			}
		}
		return null;
	}

    /**
     * Find optimal solution
     * 
     * @param root
     * @return the optimal solution for the specified problem or
     *         <code>null</code> if no solution exists.
     */
	public static ProblemNode findOptimalSolution(ProblemNode root)
	{
		ArrayList<ProblemNode> lst = new ArrayList<ProblemNode>();
		PriorityQueue<ProblemNode> pq = new PriorityQueue<ProblemNode>(16, COST_COMPARATOR);
		pq.add(root);
		while (!pq.isEmpty()) {
			ProblemNode node = pq.poll();
			if (node.isComplete()) return node;
			//node.branch(pq);
			lst.clear();
			node.branch(lst);
			pq.addAll(lst);
		}
		return null;
	}
	
}