source: trunk/src/org/apollo/meldex/DynamicProgrammingAlgorithm.java

package org.apollo.meldex;

/**
 * This abstract class implements all of the mechanics involved in performing a match using an
 * algorithm involving dynamic programming. Subclasses need to only implement a weighting
 * function for comparing two melody events. Subclasses can also easily implement special
 * functionality above the replacement/deletion/insertion that is standard.
 *
 * !! Can do matching at start better?? !!
 */

public abstract class DynamicProgrammingAlgorithm 
{
    public static final int MATCH_ANYWHERE = 1;
    public static final int MATCH_AT_START = 2;

    protected static final boolean debugOutput = true;


    public DynamicProgrammingAlgorithm()
    {
    }


    /**
     * Matches a melody against the query pattern and returns a distance measure.
     *
     * @param P The query pattern 
     * @param T The melody to match against the query pattern.
     * @param matchingMode How to match against the query pattern (start/anywhere etc.)
     *
     * @return A distance measure signifying the distance between the query and match patterns.
     */
    public int matchToPattern(Melody P, Melody T, int matchingMode)
    {
        // int maxk = options.getIntegerOptionValue("approximation");
        int maxk = Integer.MAX_VALUE;

        int m = P.getLength();
        int n = T.getLength();

        // For the comparison to be meaningful the pitch types must be the same
        if (P.getPitchType() != T.getPitchType())
            throw new Error("Internal Error: Pitch type of query and match differs.");

        // Check whether the algorithm has some special functionality
        boolean hasSpecialFunctionality = hasSpecialFunctionality();

        // Allocate distance matrix
        int[][] D = new int[n + 1][m + 1];
        D[0][0] = 0;

        // Initialise top row of matrix
        if (matchingMode == MATCH_AT_START) {
            // Match at start: have to pay to start further into the pattern
            for (int i = 1; i <= n; i++)
                D[i][0] = D[i-1][0] + weightFunction(null, T.getEvent(i-1));
        }
        if (matchingMode == MATCH_ANYWHERE) {
            // Match anywhere: free to start at any point in the pattern
            for (int i = 1; i <= n; i++)
                D[i][0] = 0;
        }

        // Initialise left column of matrix
        for (int j = 1; j <= m; j++)
            D[0][j] = D[0][j-1] + weightFunction(P.getEvent(j-1), null);

        // Fill the distance matrix
        for (int j = 1; j <= m; j++) {
            MelodyEvent queryEvent = P.getEvent(j-1);
            for (int i = 1; i <= n; i++) {
                MelodyEvent matchEvent = T.getEvent(i-1);

                // Case 1: The two events are the same or different (replacement)
                D[i][j] = D[i-1][j-1] + weightFunction(queryEvent, matchEvent);

                // Case 2: The two events are different (deletion)
                D[i][j] = Math.min(D[i][j], (D[i-1][j] + weightFunction(null, matchEvent)));

                // Case 3: The two events are different (insertion)
                D[i][j] = Math.min(D[i][j], (D[i][j-1] + weightFunction(queryEvent, null)));

                // If the algorithm has special functionality, give it a chance now
                if (hasSpecialFunctionality)
                    doAlgorithmSpecifics(D, i, j, P, T, queryEvent, matchEvent);
            }
        }

        // Display the distance matrix
        if (debugOutput)
             displayMatrix(D, m, P, n, T);

        // Find and return the minimum edit distance
        int minDist = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {  // Changed from i = 1 to i = 0 for McNab compatibility
            if (D[i][m] < minDist)
                minDist = D[i][m];
        }

        // Return -1 if the minimum distance is greater than the approximation value
        return ((minDist > maxk) ? -1 : minDist);
    }


    /**
     * Returns a distance measure signifying the distance between the query and match events.
     * This must be implemented by concrete subclasses.
     *
     * @param queryEvent The event to compare from the query pattern.
     * @param matchEvent The event to compare from the match pattern.
     *
     * @return a distance measure signifying the distance between the query and match events.
     */
    protected abstract int weightFunction(MelodyEvent queryEvent, MelodyEvent matchEvent);


    /**
     * Returns whether the algorithm has special functionality or not.
     * This should be overridden by concrete subclasses that have special functionality.
     *
     * @return true if the algorithm has special functionality, false otherwise.
     */
    protected boolean hasSpecialFunctionality()
    {
        return false;
    }


    /**
     * Gives an algorithm a chance to perform any special functionality that it has.
     * This should be overridden by concrete subclasses that have special functionality.
     *
     * @param D The distance matrix at the current point in time.
     * @param i The current x position in the distance matrix.
     * @param j The current y position in the distance matrix.
     * @param T The melody that is being matched to the query pattern.
     * @param queryEvent The melody event at position j-1 in the query pattern.
     * @param matchEvent The melody event at position i-1 in the match pattern.
     */
    protected void doAlgorithmSpecifics(int[][] D, int i, int j, Melody P, Melody T,
                                        MelodyEvent queryEvent, MelodyEvent matchEvent)
    {
        // Nothing to do
    }


    /**
     * Displays a completed distance matrix.
     *
     * @param matrix The distance matrix to display.
     * @param P The query pattern (displayed down the left).
     * @param T The match pattern (displayed along the top).
     */
    private void displayMatrix(int[][] matrix, int m, Melody P, int n, Melody T)
    {
        int width = 5;

        // Display the top line (match pattern)
        System.out.print(rightJustifyString("", width));
        System.out.print("  ");
        System.out.print(rightJustifyString("", width));
        for (int i = 1; i <= n; i++) {
            MelodyEvent matchEvent = T.getEvent(i-1);
            int matchPitch = matchEvent.getPitch();
            String pitchString;
            if (matchPitch == MelodyEvent.REST_EVENT)
                pitchString = "REST";
            else if (matchPitch == MelodyEvent.WILD_EVENT)
                pitchString = "WILD";
            else
                pitchString = String.valueOf(matchPitch);

            System.out.print(rightJustifyString(pitchString, width));
        }
        System.out.print("\n");

        // Display the second line
        System.out.print(rightJustifyString("", width));
        System.out.print(" -");
        for (int i = 0; i < ((n+1) * width); i++)
            System.out.print("-");
        System.out.print("\n");

        // Display the remaining lines
        for (int j = 0; j <= m; j++) {
            if (j == 0)
                System.out.print(rightJustifyString("", width));
            else {
                MelodyEvent queryEvent = P.getEvent(j-1);
                int queryPitch = queryEvent.getPitch();
                String pitchString;
                if (queryPitch == MelodyEvent.REST_EVENT)
                    pitchString = "REST";
                else if (queryPitch == MelodyEvent.WILD_EVENT)
                    pitchString = "WILD";
                else
                    pitchString = String.valueOf(queryPitch);

                System.out.print(rightJustifyString(pitchString, width));
            }
            System.out.print(" |");

            for (int i = 0; i <= n; i++)
                System.out.print(rightJustifyString(String.valueOf(matrix[i][j]), width));
            System.out.print("\n");
        }
    }


    /**
     * Right-justifies a string by adding spaces before it.
     *
     * @param source The string to right-justify.
     * @param width The number of characters that the right-justified string will take up.
     *
     * @return The right-justified string, or the original string if the width is too small.
     */
    private String rightJustifyString(String source, int width)
    {
        String result = source;

        // Add width - source.length spaces to the start of the string
        for (int i = 0; i < (width - source.length()); i++)
            result = " " + result;

        return result;
    }
}