/*
 * Copyright 2009 Wishnu Prasetya.
 *
 * This file is part of T2.
 * T2 is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License (GPL) as published by the
 * Free Software Foundation; either version 3 of the License, or any
 * later version.
 * 
 * T2 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 General Public License
 * for more details.
 *
 * A copy of the GNU General Public License can be found in T2 distribution.
 * If it is missing, see http://www.gnu.org/licenses.
 */
package Sequenic.T2ext.Analyzer;

import java.util.*;

/**
 * Provides methods to measure how 'close' a given execution path is to
 * a target path. This is expressed in terms of an integer 'distance'.
 * 
 * Two notions of distance are given, one is based on direct coverage, and
 * the other is based on coverage-with-detour.
 * 
 * Coverage by side-trip is currently not supported (strength-wise this is
 * between direct and detour coverage). 
 *
 * @author Wishnu Prasetya
 * @author Original algorithm and code by Maaike Gerritsen
 */
public class PathDistanceCalculator {

	/**
	 * True if the path is cyclic. The path should be prime; it is then
	 * sufficient to check if its first and last nodes are equal.
	 * 
	 * Path should not be empty, and should be prime.
	 */
	private boolean isCyclic(LinkedList<Integer> path){
		return path.getFirst() == path.getLast() ;
	}

	/**
	 * Let t be the target path to cover and p be the execution path
	 * we observe. The *direct* coverage of p on t is defined as the maximum
	 * consecutive prefix s1 of t which forms a (consecutive) segment
	 * of p. So:
	 * 
	 *     t = s1 ++ s2
	 *     s1 is a segment of p
	 *     s1 is the longest of such prefix
	 *     
	 * The *direct* distance of p to t is defined as the length of the part
	 * of t which is still uncovered. So, it is the length of s2.     
	 *  
	 * This definition works for both straight or cyclic target path t.
	 * 
	 * This method does no side effect. 
	 */
	public int directCoveragePathDistance(LinkedList<Integer> executionpath,
			LinkedList<Integer> targetpath
			){
		// We'll make copies first, so that we don't screw the input
		// lists:
		LinkedList<Integer> execP = new LinkedList<Integer>(executionpath) ;
		LinkedList<Integer> targetP = new LinkedList<Integer>(targetpath) ;
		
		int minimumDistanceFound = Integer.MAX_VALUE ;
		
		while (!execP.isEmpty()) {
			// Find common starting point first:
			int targetStart = targetP.getFirst() ;
			while (!execP.isEmpty()) {
				if (targetStart == execP.getFirst()) break ;
				execP.removeFirst() ;
			}
		
			// Now find maximal common prefix:
			/*
			while ((! execP.isEmpty()) && (! targetP.isEmpty())) {
				if (((int) execP.getFirst()) != ((int) targetP.getFirst())) break ;
				execP.removeFirst() ;
				targetP.removeFirst() ;
			}
			*/
			int k = 0 ;
			while (k < execP.size() && k < targetP.size()) {
				if ((int) execP.get(k) != (int) targetP.get(k)) break ;
				k++ ;
			}
			// The distance is now just the length of the remaining part of target path
			// return targetP.size() ;
			minimumDistanceFound = Math.min(minimumDistanceFound, targetP.size() - k) ;
			
			if (! execP.isEmpty()) execP.removeFirst() ;
			
		}
	
		return minimumDistanceFound ;
	}
	
	/**
	 * Let t be the target path to cover and p be the execution path
	 * we observe. The *detour* coverage of p on t is defined as the maximum
	 * consecutive prefix s1 of t which forms an innitial subpath of p. So:
	 * 
	 *     t = s1 ++ s2
	 *     s1 is a subpath of p
	 *     s1 is the longest of such prefix
	 * 
	 * s1 is an innitial subpath of p if it starts in the same node, and
	 * s1 can be obtained from p by removing some elements in p.
	 *       
	 * The *detour* distance of p to t is defined as the length of the part
	 * of t which is still uncovered. So, it is the length of s2.     
	 *  
	 * This definition works for both straight or cyclic target path t.
	 * 
	 * This method does no side effect. 
	 */
	public int detourCoveragePathDistance(LinkedList<Integer> executionpath,
			LinkedList<Integer> targetpath
			){
		// We'll make copies first, so that we don't screw the input
		// lists:
		LinkedList<Integer> execP = new LinkedList<Integer>(executionpath) ;
		LinkedList<Integer> targetP = new LinkedList<Integer>(targetpath) ;
		
		// Find common starting point first:
		int targetStart = targetP.getFirst() ;
		while (!execP.isEmpty()) {
			if (targetStart == execP.getFirst()) break ;
			execP.removeFirst() ;
		}
		
		// Remove the longest prefix of target-path which is a subpath
		// of the execution path:
		while ((! execP.isEmpty()) && (! targetP.isEmpty())) {
			if (((int) execP.getFirst()) == ((int) targetP.getFirst())) {
				execP.removeFirst() ;
				targetP.removeFirst() ;
			}
			else execP.removeFirst() ;
		}
		
		// The distance is now just the length of the remaining part of target path
		return targetP.size() ;
	}
}