/**
*******************************************************************************
* Copyright (C) 1996-2009, International Business Machines Corporation and    *
* others. All Rights Reserved.                                                *
*******************************************************************************
*/

package com.ibm.icu.impl;

/** VERY Basic Diff program. Compares two sequences of objects fed into it, and
 * lets you know where they are different.
 * @author Mark Davis
 * @version 1.0
 */

final public class Differ<T> {
//    public static final String copyright =
//      "Copyright (C) 2010, International Business Machines Corporation and others. All Rights Reserved.";

    /**
     * @param stackSize The size of the largest difference you expect.
     * @param matchCount The number of items that have to be the same to count as a match
     */
    @SuppressWarnings("unchecked")
    public Differ(int stackSize, int matchCount) {
        this.STACKSIZE = stackSize;
        this.EQUALSIZE = matchCount;
        a = (T[]) new Object[stackSize+matchCount];
        b = (T[]) new Object[stackSize+matchCount];
    }

    public void add (T aStr, T bStr) {
        addA(aStr);
        addB(bStr);
    }

    public void addA (T aStr) {
        flush();
        a[aCount++] = aStr;
    }

    public void addB (T bStr) {
        flush();
        b[bCount++] = bStr;
    }

    public int getALine(int offset) {
        return aLine + maxSame + offset;
    }

    public T getA(int offset) {
        if (offset < 0) return last;
        if (offset > aTop-maxSame) return next;
        return a[offset];
    }

    public int getACount() {
        return aTop-maxSame;
    }

    public int getBCount() {
        return bTop-maxSame;
    }

    public int getBLine(int offset) {
        return bLine + maxSame + offset;
    }

    public T getB(int offset) {
        if (offset < 0) return last;
        if (offset > bTop-maxSame) return next;
        return b[offset];
    }

    public void checkMatch(boolean finalPass) {
        // find the initial strings that are the same
        int max = aCount;
        if (max > bCount) max = bCount;
        int i;
        for (i = 0; i < max; ++i) {
            if (!a[i].equals(b[i])) break;
        }
        // at this point, all items up to i are equal
        maxSame = i;
        aTop = bTop = maxSame;
        if (maxSame > 0) last = a[maxSame-1];
        next = null;

        if (finalPass) {
            aTop = aCount;
            bTop = bCount;
            next = null;
            return;
        }

        if (aCount - maxSame < EQUALSIZE || bCount - maxSame < EQUALSIZE) return;

        // now see if the last few a's occur anywhere in the b's, or vice versa
        int match = find (a, aCount-EQUALSIZE, aCount, b, maxSame, bCount);
        if (match != -1) {
            aTop = aCount-EQUALSIZE;
            bTop = match;
            next = a[aTop];
            return;
        }
        match = find (b, bCount-EQUALSIZE, bCount, a, maxSame, aCount);
        if (match != -1) {
            bTop = bCount-EQUALSIZE;
            aTop = match;
            next = b[bTop];
            return;
        }
        if (aCount >= STACKSIZE || bCount >= STACKSIZE) {
            // flush some of them
            aCount = (aCount + maxSame) / 2;
            bCount = (bCount + maxSame) / 2;
            next = null;
        }
    }

    /** Convenient utility
     * finds a segment of the first array in the second array.
     * @return -1 if not found, otherwise start position in b
     */

    public int find (T[] aArr, int aStart, int aEnd, T[] bArr, int bStart, int bEnd) {
        int len = aEnd - aStart;
        int bEndMinus = bEnd - len;
        tryA:
        for (int i = bStart; i <= bEndMinus; ++i) {
            for (int j = 0; j < len; ++j) {
                if (!bArr[i + j].equals(aArr[aStart + j])) continue tryA;
            }
            return i; // we have a match!
        }
        return -1;
    }

    // ====================== PRIVATES ======================

    private void flush() {
        if (aTop != 0) {
            int newCount = aCount-aTop;
            System.arraycopy(a, aTop, a, 0, newCount);
            aCount = newCount;
            aLine += aTop;
            aTop = 0;
        }

        if (bTop != 0) {
            int newCount = bCount-bTop;
            System.arraycopy(b, bTop, b, 0, newCount);
            bCount = newCount;
            bLine += bTop;
            bTop = 0;
        }
    }

    private int STACKSIZE;
    private int EQUALSIZE;

    private T [] a;
    private T [] b;
    private T last = null;
    private T next = null;
    private int aCount = 0;
    private int bCount = 0;
    private int aLine = 1;
    private int bLine = 1;
    private int maxSame = 0, aTop = 0, bTop = 0;

}