package de.fhw.bi.txtsearch;

import java.util.Vector;

import java.util.Iterator;

public class PatternMatcher {

    public static final int MATCH = 0;

    public static final int NOMATCH = 1;

    public static final int UNBEARB = 2;

    private String text;

    private String pattern;

    private Vector listeners;

    public PatternMatcher() {

        listeners = new Vector();

    }

    public String getText() {

        return text;

    }

    public String getPattern() {

        return pattern;

    }

    public void setText(String text) {

        this.text = text;

    }

    public void setPattern(String pattern) {

        this.pattern = pattern;

    }

    private void setUnbearbeitet(int a, int k, int[] matches) {

        for (int j = 0; j < k; j++) {

            matches[a+j] = UNBEARB;

        }

    }

    public void naiveSearch() {

        // initialize matches arrays:

        int[] textMatches = new int[text.length()];

        for (int i = 0; i < textMatches.length; i++) {

            textMatches[i] = UNBEARB;

        }

        int[] patternMatches = new int[pattern.length()];

        for (int i = 0; i < patternMatches.length; i++) {

            patternMatches[i] = UNBEARB;

        }

        int tIndex = 0, pIndex;

        int tLength = text.length();

        int pLength = pattern.length();

        Vector found = new Vector();

        while (tIndex <= tLength - pLength) {

            pIndex = 0;

            //fireNewPosition();

            while (pIndex < pLength

                && pattern.charAt(pIndex) == text.charAt(tIndex + pIndex)) {

                textMatches[pIndex + tIndex] = MATCH;

                patternMatches[pIndex] = MATCH;

                fireNewPosition(textMatches, patternMatches, tIndex);

                pIndex++;

            }

            if (pIndex == pLength) { // full match

                found.add(new Integer(tIndex));

                setUnbearbeitet(0,pIndex, patternMatches);

                //for (int j = 0; j < pIndex; j++) {

                //    patternMatches[j] = UNBEARB;

                //}

            } else {

                textMatches[tIndex + pIndex] = NOMATCH;

                patternMatches[pIndex] = NOMATCH;

                fireNewPosition(textMatches, patternMatches, tIndex);

                //                matches must be corrected:

                setUnbearbeitet(tIndex,pIndex,textMatches);

                setUnbearbeitet(0,pIndex,patternMatches);

                /**for (int j = 0; j <= pIndex; j++) {

                    textMatches[tIndex + j] = UNBEARB;

                    patternMatches[j] = UNBEARB;

                }**/

            }

            setUnbearbeitet(0, text.length()-1, textMatches);

            for (int i = 0; i < found.size(); i++) {

                int start = ((Integer) found.get(i)).intValue();

                for (int j = 0; j < pLength; j++) {

                    textMatches[start + j] = MATCH;

                }

            }

            setUnbearbeitet(0,pattern.length()-1,patternMatches);

            //fireNewPosition();

            tIndex++;

        }

        tIndex--;

        fireNewPosition(textMatches, patternMatches, tIndex);

    }

    public void knuthMorrisPratt(String text, String pattern) {

        // Hilfsarray um den Text farbig anzuzeigen

        int[] tMatches = new int[text.length()];

        setUnbearbeitet(0,tMatches.length,tMatches);

        // Hilfsarray um das Muster farbig anzuzeigen

        int[] pMatches = new int[pattern.length()];

        setUnbearbeitet(0,pMatches.length,pMatches);

        /**

         * mit fireNewPosition(tMatches, pMatches, i);

         * wird die Anzeige erneuert, dabei werden die Buchstaben im Text nach den

         * Vorgaben von tMatches angezeigt und die Buchstaben im Muster nach den Vorgaben

         * von pMatches

         * Das Muster steht im Text an Position i.

        */

        int[] l = calcMargins(pattern);

        int tIndex = 0, pIndex = 0;

        int pLen = pattern.length(), tLen = text.length();

        Vector found = new Vector();

      // to do: restliche Implementierung

        // dabei auf die Anzeige achten

        while (tIndex-pIndex < 0){

            while ((pIndex <= pLen-1) && (text == pattern)){

                pIndex++;

                tIndex++;

            }

            if (pIndex == pLen-1)

                found.add(tIndex-pIndex, found);

            if (pIndex==0)

                tIndex++;

            else pIndex = l[pIndex];

            ;

        }

    }

    private int[] calcMargins(String p) {

        // to do: berechne die L\ufffdngen der gr\ufffd\ufffdten R\ufffdnder

        int[] rand = new int[p.length()+1];

        rand[0]=-1;

        String t = getText();

        int tIndex = 0, pIndex = -1;

        while ( tIndex < p.length()){

            if ((pIndex >= 0 )&& (p != t))

                rand[tIndex+1] = pIndex+1;

            else {while (pIndex >= 0 && p != t)

                pIndex = rand[pIndex];

            if (pIndex<0)

                rand[tIndex+1]=0;

            else rand[tIndex+1] = pIndex+1;}

            tIndex++;

            pIndex++;

        }

        return rand;

    }

    public static void main(String[] args) {

        PatternMatcher pm = new PatternMatcher();

        int[] a = pm.calcMargins("abxaby");

        for (int i = 0; i < a.length; i++) {

            System.out.println(i + " " + a[i] + ";");

        }

    }

    protected void fireNewPosition(int[] textM, int[] patternM, int textPos) {

        for (Iterator it = listeners.iterator(); it.hasNext();) {

            ((PatternMatcherListener) it.next()).newPosition(

                textM,

                patternM,

                textPos);

        }

    }

    public void addPatternMatcherListener(PatternMatcherListener l) {

        listeners.add(l);

    }

    private int[] calcOccurrence() {

        char a;

        int[] d = new int[256];

        for (int j = 0; j < 256; j++)

            d[j] = -1;

        for (int k = 0; k < pattern.length(); k++) {

            a = pattern.charAt(k);

            d[a] = k;

        }

        return d;

    }

    void goodEndPreprocess1(int[] f, int[] s) {

        int m = pattern.length(), i = m, j = m + 1;

        f[i] = j;

        for (int k = 0; k <= m; k++)

            s[k] = 0;

        while (i > 0) {

            while (j <= m && pattern.charAt(i - 1) != pattern.charAt(j - 1)) {

                if (s[j] == 0)

                    s[j] = j - 1;

                j = f[j];

            }

            i--;

            j--;

            f[i] = j;

        }

    }

    void goodEndPreprocess2(int[] f, int[] s) {

        int m = pattern.length();

        int i, j;

        j = f[0];

        for (i = 0; i <= m; i++) {

            if (s[i] == 0)

                s[i] = j;

            if (i == j)

                j = f[j];

        }

    }

    private int[] bmPreprocess(int[] f, int[] s) {

        int[] d = calcOccurrence();

        goodEndPreprocess1(f, s);

        goodEndPreprocess2(f, s);

        return d;

    }

    void boyerMoore() {

        //zur Darstellung

        int[] tMatches = new int[text.length()];

        for (int i = 0; i < tMatches.length; i++) {

            tMatches[i] = UNBEARB;

        }

        int[] pMatches = new int[pattern.length()];

        for (int i = 0; i < pMatches.length; i++) {

            pMatches[i] = UNBEARB;

        }

        int[] last = null;

        int[] s = new int[pattern.length() + 1];

        int[] f = new int[pattern.length() + 1];

        last = bmPreprocess(f, s);

        int n = text.length(), m = pattern.length(), i = 0, j;

        Vector found = new Vector();

        while (i <= n - m) {

            j = m - 1;

            while (j >= 0 && pattern.charAt(j) == text.charAt(i + j)) {

                tMatches[i + j] = MATCH;

                pMatches[j] = MATCH;

                fireNewPosition(tMatches, pMatches, i);

                j--;

            }

            if (j < 0) {

                found.add(new Integer(i));

                System.out.println("Position: " + i);

                for (int k = 0; k < m; k++) {

                    pMatches[k] = UNBEARB;

                }

                //report(i);

                i += s[0];

            } else {

                /**tMatches[i + j] = NOMATCH;

                pMatches[j] = NOMATCH;

                fireNewPosition(tMatches, pMatches, i);**/

                //                matches must be corrected:

                for (int k = 0; k < m; k++) {

                    tMatches[i + k] = UNBEARB;

                    pMatches[k] = UNBEARB;

                }

                i += Math.max(s[j + 1], j - last[text.charAt(i + j)]);

            }

        }

    }

    int matchLength(String p, int i, int j) {

        int k = 0, m = p.length();

        boolean match = true;

        while (match && i < m && j < m) {

            if (match = (p.charAt(i) == p.charAt(j))) {

                k++; i++; j++;

            }

        }

        return k;

    }

    int[] calcZ(String s) {

        int m = s.length(), r = 0, l = 0;

        int[] z = new int[m];

        z[0] = 0;

        for (int k = 1; k < m; k++) {

            if (k > r) {

                z[k] = matchLength(s, k, 0);

                if (z[k] > 0) {

                    r = k + z[k] - 1;

                    l = k;

                }

            } else {

                int ks = k - l, b = r - k + 1;

                if (z[ks] < b)

                    z[k] = z[ks];

                else {

                    int q = r + 1 + matchLength(s, r + 1, b);

                    z[k] = q - k;

                    r = q - 1;

                    l = k;

                }

            }

        }

        return z;

    }

    void zAlg() {

        int[] tMatches = new int[text.length()];

        for (int i = 0; i < tMatches.length; i++) {

            tMatches[i] = UNBEARB;

        }

        int[] pMatches = new int[pattern.length()];

        for (int i = 0; i < pMatches.length; i++) {

            pMatches[i] = UNBEARB;

        }

        StringBuffer b = new StringBuffer(pattern);

        b = b.append('$');

        b = b.append(text);

        int[] z = calcZ(b.toString());

        int m = pattern.length();

        for (int i = 0; i <= text.length(); i++) {

            if (z[i + m] == m) {

                for (int j = i; j < i+m; j++) {

                    tMatches[j-1] = MATCH;

                    pMatches[j-i] = MATCH;

                    fireNewPosition(tMatches, pMatches, i-1);

                }

            }

            for (int k = 0; k < m; k++) pMatches[k] = UNBEARB;

        }

    }

    static private int[] initShift(String pattern) {

        int m = pattern.length();

        int[] shift = new int[m + 1];

        int[] suffix = new int[m + 1];

        int i, j, h = 0;

        suffix[m - 1] = m;

        j = m - 1;

        for (i = m - 2; i >= 0; --i) {

            if (i > j && suffix[i + m - 1 - h] < i - j) {

                suffix[i] = suffix[i + m - 1 - h];

            } else {

                if (i < j) {

                    j = i;

                }

                h = i;

                while (j >= 0

                    && pattern.charAt(j) == pattern.charAt(j + m - 1 - h)) {

                    --j;

                }

                suffix[i] = h - j;

            }

        }

        for (i = 0; i < m; ++i) {

            shift[i] = m;

        }

        j = 0;

        for (i = m - 1; i >= -1; --i) {

            if (i == -1 || suffix[i] == i + 1) {

                while (j < m - 1 - i) {

                    if (shift[j] == m) {

                        shift[j] = m - 1 - i;

                    }

                    ++j;

                }

            }

        }

        for (i = 0; i < m - 1; ++i) {

            shift[m - 1 - suffix[i]] = m - i - 1;

        }

        for (i = 0; i < pattern.length(); ++i) {

            System.out.println("shift[" + i + "]=" + shift[i]);

        }

        return shift;

    }

    static protected int[] initLast(String pattern) {

        int[] last = new int[256];

        for (int i = 0; i < 256; ++i) {

            last[i] = -1;

        }

        for (int i = 0; i < pattern.length(); ++i) {

            last[pattern.charAt(i)] = i;

        }

        return last;

    }

    public void bmSearch() {

        final int last[] = initLast(pattern);

        final int shift[] = initShift(pattern);

        int[] textMatches = new int[text.length()];

        for (int i = 0; i < textMatches.length; i++) {

            textMatches[i] = UNBEARB;

        }

        int[] patternMatches = new int[pattern.length()];

        for (int i = 0; i < patternMatches.length; i++) {

            patternMatches[i] = UNBEARB;

        }

        int tIndex = 0, pIndex;

        int tLength = text.length();

        int pLength = pattern.length();

        Vector found = new Vector();

        while (tIndex <= tLength - pLength) {

            pIndex = pLength - 1;

            //fireNewPosition();

            while (pIndex >= 0

                && pattern.charAt(pIndex) == text.charAt(tIndex + pIndex)) {

                textMatches[pIndex + tIndex] = MATCH;

                patternMatches[pIndex] = MATCH;

                fireNewPosition(textMatches, patternMatches, tIndex);

                pIndex--;

            }

            if (pIndex < 0) { // full match

                found.add(new Integer(tIndex));

                tIndex +=shift[0];

            } else {

                textMatches[pIndex + tIndex] = NOMATCH;

                patternMatches[pIndex] = NOMATCH;

                fireNewPosition(textMatches, patternMatches, tIndex);

                for (int j = 0; j <= pIndex; j++) {

                    textMatches[tIndex + j] = UNBEARB;

                    patternMatches[j] = UNBEARB;

                }

                tIndex += Math.max(shift[pIndex], pIndex - last[text.charAt(tIndex + pIndex)]);

            }

            for (int i = 0; i < tLength; i++) {

                    textMatches[i] = UNBEARB;

            }

            for (int i = 0; i < found.size(); i++) {

                int start = ((Integer) found.get(i)).intValue();

                for (int j = 0; j < pLength; j++) {

                    textMatches[start + j] = MATCH;

                }

            }

            for (int i = 0; i < pLength; i++) {

                patternMatches[i] = UNBEARB;

            }

            fireNewPosition(textMatches, patternMatches, tIndex);

        }

    }



}