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

package org.unicode.cldr.util;

/**
 * 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> {
    /**
     * @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[maxSame + 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[maxSame + offset];
    }

    /**
     * Checks for initial & final match.
     * To be called after addA() and addB().
     * Middle segments that are different are returned via get*Count() and get*().
     *
     * @param finalPass true if no more input
     */
    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;
        }
    }

    /**
     * Finds a segment of the first array in the second array.
     * @return -1 if not found, otherwise start position in bArr
     */
    private 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 ======================

    /** Removes equal prefixes of both arrays. */
    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;

    // a[] and b[] are equal at 0 to before maxSame.
    // maxSame to before *Top are different.
    // *Top to *Count are equal again.
    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;
}
