package com.wrox.algorithms.ssearch;

public class BoyerMooreStringSearcher implements StringSearcher {
    /** liczebność wykorzystywanego zestawu znaków */
    private static final int CHARSET_SIZE = 256;

    /** poszukiwany wzorzec */
    private final CharSequence _pattern;

    /** Pozycje ostatnich wystapień poszczególnych znaków we wzorcu */
    private final short[] _lastOccurrence;

    public BoyerMooreStringSearcher(CharSequence pattern) {
        assert pattern != null : "nie określono wzorca";
        assert pattern.length() > 0 : "wzorzec nie może być pusty";

        _pattern = pattern;
        _lastOccurrence = computeLastOccurrence(pattern);
    }


    private static short[] computeLastOccurrence(CharSequence pattern) {
        short[] lastOccurrence = new short[CHARSET_SIZE];

        for (int i = 0; i < lastOccurrence.length; ++i) {
            lastOccurrence[i] = -1;
        }

        for (int i = 0; i < pattern.length(); ++i) {
            lastOccurrence[pattern.charAt(i)] = (short) i;
        }

        return lastOccurrence;
    }

    public StringMatch search(CharSequence text, int from) {
        assert text != null : "nie określono tekstu";
        assert from >= 0 : "pozycja startowa nie może być ujemna";

        int s = from;

        while (s <= text.length() - _pattern.length()) {
            int i = _pattern.length() - 1;

            char c = 0;
            while (i >= 0 && _pattern.charAt(i) == (c = text.charAt(s + i))) {
                --i;
            }

            if (i < 0) {
                return new StringMatch(_pattern, text, s);
            }

            s += Math.max(i - _lastOccurrence[c], 1);
        }

        return null;
    }



}
