class TimeWarpEditDistance implements ITimeseriesDistanceMetric {

	@Override
	public double distance(final double[] a, final double[] tA, final double[] b, final double[] tB) {
		int n = a.length;
		int m = b.length;

		// DP[0..n, 0..m]
		double[][] dp = new double[n + 1][m + 1];

		// declare A[0] := 0, tA[0] := 0
		// declare B[0] := 0, tB[0] := 0
		// Note: Zero pad A and B, i.e. when referencing A[i] use A[i-1], when
		// referencing A[i-1] use A[i-2]

		// Dynamic Programming initialization.
		for (int i = 1; i <= n; i++) {
			dp[i][0] = Double.MAX_VALUE;
		}
		for (int i = 1; i <= m; i++) {
			dp[0][i] = Double.MAX_VALUE;
		}
		dp[0][0] = 0d;

		// Dynamic programming.
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {

				// Cost for Deletion in A.
				double c1;
				// Cost for Deletion in B.
				double c2;
				// Cost for a match.
				double c3;

				if (i == 1 && j == 1) {
					// Substitute A[i-2] with 0 and B[j-2] with 0.
					c1 = dp[i - 1][j] + this.d.distance(0, a[i - 1]) + this.nu * tA[i - 1] + this.lambda;
					c2 = dp[i][j - 1] + this.d.distance(0, b[j - 1]) + this.nu * tB[j - 1] + this.lambda;
					c3 = dp[i - 1][j - 1] + this.d.distance(a[i - 1], b[i - 1]) + this.nu * Math.abs(tA[i - 1] - tB[j - 1]);
				} else if (i == 1) {
					// Substitute A[i-2] with 0.
					c1 = dp[i - 1][j] + this.d.distance(0, a[i - 1]) + this.nu * tA[i - 1] + this.lambda;
					c2 = dp[i][j - 1] + this.d.distance(b[j - 2], b[j - 1]) + this.nu * (tB[j - 1] - tB[j - 2]) + this.lambda;
					c3 = dp[i - 1][j - 1] + this.d.distance(a[i - 1], b[i - 1]) + this.d.distance(0, b[j - 2]) + this.nu * (Math.abs(tA[i - 1] - tB[j - 1]) + tB[j - 2]);
				} else if (j == 1) {
					// Substitute B[j-2] with 0.
					c1 = dp[i - 1][j] + this.d.distance(a[i - 2], a[i - 1]) + this.nu * (tA[i - 1] - tA[i - 2]) + this.lambda;
					c2 = dp[i][j - 1] + this.d.distance(0, b[j - 1]) + this.nu * tB[j - 1] + this.lambda;
					c3 = dp[i - 1][j - 1] + this.d.distance(a[i - 1], b[i - 1]) + this.d.distance(a[i - 2], 0) + this.nu * (Math.abs(tA[i - 1] - tB[j - 1]) + tA[i - 2]);
				} else {
					// No substitution.
					c1 = dp[i - 1][j] + this.d.distance(a[i - 2], a[i - 1]) + this.nu * (tA[i - 1] - tA[i - 2]) + this.lambda;
					c2 = dp[i][j - 1] + this.d.distance(b[j - 2], b[j - 1]) + this.nu * (tB[j - 1] - tB[j - 2]) + this.lambda;
					c3 = dp[i - 1][j - 1] + this.d.distance(a[i - 1], b[i - 1]) + this.d.distance(a[i - 2], b[j - 2]) + this.nu * (Math.abs(tA[i - 1] - tB[j - 1]) + Math.abs(tA[i - 2] - tB[j - 2]));
				}

				// Minimum cost.
				double minimum = Math.min(c1, Math.min(c2, c3));
				dp[i][j] = minimum;
			}
		}

		return dp[n][m];
	}

	public  TimeWarpEditDistance(final double lambda, final double nu, final IScalarDistance d);
	public  TimeWarpEditDistance(final double lambda, final double nu);

}