/*******************************************************************************
* Copyright (c)                                                                *
*           2005   Tristan Allwood,                                            *
*           2005   Daniel Burke,                                               *
*           2005   Marc Hull,                                                  *
*           2005   Ekaterina Itskova,                                          *
*           2005   Steve Zymler                                                *
*                                                                              *
* Permission is hereby granted, free of charge, to any person obtaining a      *
* copy of this software and associated documentation files (the                *
* "Software"), to deal in the Software without restriction, including          *
* without limitation the rights to use, copy, modify, merge, publish,          *
* distribute, sublicense, and/or sell copies of the Software, and to           *
* permit persons to whom the Software is furnished to do so, subject to        *
* the following conditions:                                                    *
*                                                                              *
* The above copyright notice and this permission notice shall be included      *
* in all copies or substantial portions of the Software.                       *
*                                                                              *
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS      *
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF                   *
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.       *
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY         *
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,         *
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE            *
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                       *
*******************************************************************************/
/*
 * Created on 17-Nov-2004
 *
 */
package uk.ac.ic.doc.kevlar.publicUtil.strings;

/**
 * This class enables strings to be effeciently compared using the Needleman
 * Wunch algorithm.
 * 
 * @author Daniel Burke
 * 
 *  
 */
public class NeedlemanWunchStringComparison {

    // reuse arrays for grid and origins between calls for effeciency

    // store all the data generated by the algorithm temporairly as class
    // members
    // this will make testing simpler since the test can verify the algorithmic
    // data generated is correct
    private int[][] grid = new int[0][0];

    private WunchOrigin[][] origins = new WunchOrigin[0][0];

    private char[] lettersA;

    private char[] lettersB;

    private NeedlemanScoringScheme scorer;

    // This is a private class used as an enumeration for
    // indicating how a square's score was derived
    private static class WunchOrigin {
        // The first square in the dynamic programming grid is the root
        public static WunchOrigin Root = new WunchOrigin("R");

        // Used to indicate a square was calculated by inserting
        // a letter from the vertical string
        public static WunchOrigin N = new WunchOrigin("N");

        // Used to indicate a square was calculated by inserting
        // a letter from the horizontal string
        public static WunchOrigin W = new WunchOrigin("W");

        // Used to indicate a square was calculated by
        // Taking a letter from both strings and matching them
        public static WunchOrigin NW = new WunchOrigin("NW");

        private String name;

        private WunchOrigin(String name) {
            this.name = name;
        }

        public String toString() {
            return name;
        }
    }

    /**
     * Use to calculate the similarity of two strings according to the Needleman
     * Wunch algorithm
     * 
     * @param a
     *            the first string to compare
     * @param b
     *            the second string to compare
     * @param scorer
     *            the Needleman Wunch scoring scheme to use
     * @return a similarity score. As per the algorithm, higher means a stronger
     *         match.
     */
    public synchronized int computeSimilarity(String a, String b,
            NeedlemanScoringScheme scorer) {
        this.scorer = scorer;

        // handle corner cases when either string is empty
        if (a.length() == 0 || b.length() == 0) {
            if (a.length() == 0 && b.length() == 0) {
                return 0;
            }

            return (a.length() + b.length() - 1) * scorer.getGapExtendScore()
                    + scorer.getGapOpenScore();
        }

        // get the char arrays for string a and b
        lettersA = a.toCharArray(); // We will put A on the horizontal of the
        // grid
        lettersB = b.toCharArray(); // and b on the vertical side.

        // Get size of needlman wunch dynamic programming grid
        int width = lettersA.length + 1;
        int height = lettersB.length + 1;

        // Attempt to use the cached grid and origins if possible,
        // otherwise, reallocate
        if (grid.length < height || grid[0].length < width) {
            grid = new int[height][width];
        }

        if (origins.length < height || origins[0].length < width) {
            origins = new WunchOrigin[height][width];
        }

        // We need to fill out the first row and column manually
        // These values are defined by the algorithm
        grid[0][0] = 0;
        grid[1][0] = scorer.getGapOpenScore();
        grid[0][1] = scorer.getGapOpenScore();

        origins[0][0] = WunchOrigin.Root;
        origins[1][0] = WunchOrigin.N;
        origins[0][1] = WunchOrigin.W;

        // Fill out the rest of the first column
        for (int y = 2; y < height; y++) {
            grid[y][0] = grid[y - 1][0] + scorer.getGapExtendScore();
            origins[y][0] = WunchOrigin.N;
        }

        // Fill out the rest of the first row
        for (int x = 2; x < width; x++) {
            grid[0][x] = grid[0][x - 1] + scorer.getGapExtendScore();
            origins[0][x] = WunchOrigin.W;
        }

        // Fill out the rest of the grid
        // Start at square (1,1) and move diagonally
        // for each step = i, the row and column of (i, i)
        // must be filled in to the right and below
        int loops = Math.min(width, height);
        for (int step = 1; step < loops; step++) {
            // Fill out the row to the right starting at (step, step)
            for (int x = step; x < width; x++) {
                updateSquare(x, step);
            }

            // Fill out the column below starting at (step, step)
            for (int y = step + 1; y < height; y++) {
                updateSquare(step, y);
            }
        }

        // The optimal alignment score is the score in the bottom right
        // as per the Needleman wunch algorithm
        return grid[height - 1][width - 1];
    }

    /**
     * Update grid and origins with a derived score and origin according to the
     * rules of the Needleman Wunch algorithm
     * 
     * @param x
     *            The x position of the square to update
     * @param y
     *            The y position of the square to update
     */
    private void updateSquare(int x, int y) {

        // caclulate all possible scores
        int scoreN, scoreW, scoreNW;
        if (origins[y - 1][x] != WunchOrigin.N) {
            scoreN = grid[y - 1][x] + scorer.getGapOpenScore();
        } else {
            scoreN = grid[y - 1][x] + scorer.getGapExtendScore();
        }

        if (origins[y][x - 1] != WunchOrigin.W) {
            scoreW = grid[y][x - 1] + scorer.getGapOpenScore();
        } else {
            scoreW = grid[y][x - 1] + scorer.getGapExtendScore();
        }

        scoreNW = grid[y - 1][x - 1]
                + scorer.getScore(lettersA[x - 1], lettersB[y - 1]);

        // Use the highest score for this square
        if (scoreW >= scoreNW && scoreW >= scoreN) {
            grid[y][x] = scoreW;
            origins[y][x] = WunchOrigin.W;
        } else if (scoreN >= scoreNW) {
            grid[y][x] = scoreN;
            origins[y][x] = WunchOrigin.N;
        } else {
            grid[y][x] = scoreNW;
            origins[y][x] = WunchOrigin.NW;
        }
    }

    /**
     * Returns a string representation of the grid as of the end of the last time
     * computeSimilarity is called. This method should only be used for testing 
     * The format of the string may change so do not parse it.
     * @return the string representation of the grid and origins for the data from the last call to computeSimilarity()
     */
    public synchronized String toString() {
        StringBuffer buffer = new StringBuffer();
        buffer.append("\t");
        buffer.append(".\t");

        // Print out top row letters
        for (char l : lettersA) {
            buffer.append(l).append("\t");
        }
        buffer.append(StringUtil.NEWLINE);

        // print out each row of the grid
        for (int y = 0; y < grid.length; y++) {

            // first print out the letter
            // from the vertical string
            if (y == 0) {
                buffer.append("\t");
            } else {
                buffer.append(lettersB[y - 1]);
                buffer.append("\t");
            }

            // Then print out the scores and origins for the row
            for (int x = 0; x < grid[0].length; x++) {
                buffer.append(grid[y][x]);
                buffer.append(origins[y][x]);
                buffer.append("\t");
            }

            buffer.append(StringUtil.NEWLINE);
        }

        return buffer.toString();
    }

    public static void main(String[] args) {
        NeedlemanScoringScheme scheme = new NeedlemanScoringScheme(null, 5, -5,
                -5, -5);
        NeedlemanWunchStringComparison c = new NeedlemanWunchStringComparison();
        
        System.out.println("changing with change : " + c.computeSimilarity("change", "changing", scheme));
        
        for(int i = 0 ; i < 1000 * 1000 ; i++)
        {
            c.computeSimilarity("1234567", "1234567", scheme);
        }
        System.out.println("end");
    }
}
