HintCO/HintCOEngine/src/ua/ansymo/hintco/LazySearchTree.xtend

package ua.ansymo.hintco

import org.eclipse.core.runtime.Assert
import org.jgrapht.graph.DefaultWeightedEdge
import org.jgrapht.graph.DirectedMultigraph
import org.jgrapht.graph.SimpleDirectedWeightedGraph
import org.jgrapht.util.SupplierUtil
import org.eclipse.xtend.lib.annotations.Accessors

/*
 * Represents the search space used in the algebraic loop optimizer. Lazily expands the graph as the search algorithm works it's way towards the optimal solution.
 */
class LazySearchTree extends SimpleDirectedWeightedGraph<LazySearchNode, DefaultWeightedEdge> {
	
	DirectedMultigraph<CosimUnitInstance, DefaultWeightedEdge> triggerGraph
	
	@Accessors(PUBLIC_GETTER, NONE) EmptyTriggerSequence root = new EmptyTriggerSequence
	@Accessors(PUBLIC_GETTER, NONE) CompleteTriggerSequence bottom = new CompleteTriggerSequence
	
	
	new(DirectedMultigraph<CosimUnitInstance, DefaultWeightedEdge> tg) {
		super(SupplierUtil.createSupplier(LazySearchNode), SupplierUtil.createSupplier(DefaultWeightedEdge))
		Assert.isTrue(!tg.vertexSet.empty)
		triggerGraph = tg
		// Define the default start and end nodes.
		this.addVertex(root)
		this.addVertex(bottom)
	}
	
	/*
	 * Computes the edges and vertices that are outgoing from vertex, and adds them to the graph.
	 * It considers three kinds of LazySearchNode: the EmptyTriggerSequence, the PartialTriggerSequence, and the CompleteTriggerSequence.
	 * In the case of EmptyTriggerSequence, then the successors are all possible vertices on the graph.
	 * In the case of PartialTriggerSequence, then the successors are all possible vertices on the graph, except for those that are already part of the trigger sequence (this is naive, see below).
	 * In the case of CompleteTriggerSequence, then there are no successors, and an exception should be thrown.
	 * I think it is possible to reduce the successors in the case of a PartialTriggerSequence. Essentially, one would expect the optimal trigger sequence to be a path in the triggerGraph. 
	 * This is because whenever we pick a cosim unit A, any cosim units that depend on A have their cost reduced, so it would make sense that the optimal choice will be among them. 
	 * However, for cosim scenarios that results in non strongly connected graphs, one may be forced to chose a successor which is not a successor of A in triggerGraph.
	 * Therefore I'm going for the most naive approach to just enum all, and let A* select the best choice.
	 */
	override outgoingEdgesOf(LazySearchNode vertex) {
		if (vertex instanceof EmptyTriggerSequence) {
			Assert.isTrue(vertex.inDegreeOf == 0, "This vertex should be the root of the search tree.")
			for (v : triggerGraph.vertexSet) {
				createNewEdge(vertex, v)
			}
		} else if (vertex instanceof CompleteTriggerSequence) {
			throw new IllegalArgumentException()
		} else if (vertex instanceof PartialTriggerSequence) {
			val potentialSuccessors = triggerGraph.vertexSet.filter[v | !recIsAncestorOf(v, vertex)]
			if (potentialSuccessors.empty) {
				val edge = this.addEdge(vertex, bottom)
				Assert.isNotNull(edge) // Otherwise, this vertex has been expanded before, the solution found, and then the search problem got back here.
				this.setEdgeWeight(edge, 0.0) // No cost for the edge that reaches bottom
			} else {
				for (v : potentialSuccessors) {
					createNewEdge(vertex, v)
				}
			}
			
		}
		return super.outgoingEdgesOf(vertex)
	}
	
	private def createNewEdge(LazySearchNode vertex, CosimUnitInstance v) {
		val newV = new PartialTriggerSequence(v)
		val newEdge = this.addEdge(vertex, newV)
		this.setEdgeWeight(newEdge, costOfEdge(newV))
	}
	
	def boolean recIsAncestorOf(CosimUnitInstance ancestorUnit, PartialTriggerSequence vertex) {
		// Base case
		val predecessors = vertex.incomingEdgesOf
		Assert.isTrue(!predecessors.empty)
		if (predecessors.size == 1) {
			Assert.isTrue(predecessors.head.edgeSource instanceof EmptyTriggerSequence)
			return false
		}
		for (p : predecessors) {
			val partialP = p.edgeSource as PartialTriggerSequence
			if (partialP.unit == ancestorUnit) {
				return true
			}
			if (recIsAncestorOf(ancestorUnit, partialP)){
				return true
			}
		}
		return false
	}
	
	/*
	 * Defines the cost of an edge A->B. 
	 * This is given by the sum of the weights of incoming connections to B (in the triggerGraph) that are not ancestors of B in the search tree.
	 */
	def costOfEdge(PartialTriggerSequence B){
		val Bunit = B.unit
		val incommingEdges = triggerGraph.incomingEdgesOf(Bunit).filter[inc | recIsAncestorOf(triggerGraph.getEdgeSource(inc), B)]
		val cost = incommingEdges.map[edge|triggerGraph.getEdgeWeight(edge)].reduce[p1, p2|p1+p2]
		return cost
	}
}

abstract class LazySearchNode {
	
}

/*
 * Represents a partial trigger sequence of a graph.
 * 
 */
class PartialTriggerSequence extends LazySearchNode {
	@Accessors(PUBLIC_GETTER, PROTECTED_SETTER) CosimUnitInstance unit
	new (CosimUnitInstance u){
		unit = u	
	}
	override toString() {
		unit.toString
	}
}

/*
 * The following two classes are used to identify the start and end of the search
 */
class EmptyTriggerSequence extends LazySearchNode {}
class CompleteTriggerSequence extends LazySearchNode {}