MismatchSearch.java

/*
 * MismatchSearch.java
 *
 * Created on 12.11.2003.
 *
 * eaio: StringSearch - high-performance pattern matching algorithms in Java
 * Copyright (c) 2003, 2004 Johann Burkard (jb@eaio.com) http://eaio.com
 *
 * 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.
 *
 */
package libsidutils.stringsearch;

/**
 * Subclasses of MismatchSearch allow for searching with a fixed number of
 * possible errors. Subclasses of this class return a <code>int</code> array
 * with the first <code>int</code> being the position at which the hit occurred
 * and the second <code>int</code> being the number of mismatches at the
 * position. <br>
 * <br>
 * Example:
 *
 * <pre>
 * int[] positions = new ShiftOrMismatches().searchString(&quot;this is null&quot; &quot;nall&quot; 1);
 * </pre>
 * <p>
 * positions[0] would be 8, positions[1] (the number of mismatches) would be 1.
 *
 * @author <a href="mailto:jb@eaio.com">Johann Burkard</a>
 * @version 1.2
 */
abstract class MismatchSearch extends StringSearch {
    /*
     * Pre-processing methods
     */

    /**
     * Pre-process the pattern, allowing <b>zero</b> errors. <br>
     * <br>
     * Identical to <code>process(pattern, 0)</code>
     *
     * @param pattern the <code>byte</code> array containing the pattern, may not be
     *                <code>null</code>
     * @see StringSearch#processBytes(byte[])
     * @see #processBytes(byte[], int)
     */
    @Override
    public final Object processBytes(byte[] pattern) {
        return processBytes(pattern, 0);
    }

    /**
     * Pre-processes the pattern, allowing k errors.
     *
     * @param pattern the <code>byte</code> array containing the pattern, may not be
     *                <code>null</code>
     * @param k       the editing distance
     * @return an Object
     */
    public abstract Object processBytes(byte[] pattern, int k);

    /**
     * Pre-processes the pattern, allowing <b>zero</b> errors. <br>
     * <br>
     * Identical to <code>process(pattern, 0)</code>.
     *
     * @param pattern a <code>char</code> array containing the pattern, may not be
     *                <code>null</code>
     * @return an Object
     * @see #processChars(char[], int)
     * @see StringSearch#processChars(char[])
     */
    @Override
    public final Object processChars(char[] pattern) {
        return processChars(pattern, 0);
    }

    /**
     * Pre-processes a <code>char</code> array, allowing k errors.
     *
     * @param pattern a <code>char</code> array containing the pattern, may not be
     *                <code>null</code>
     * @param k       the editing distance
     * @return an Object
     */
    public abstract Object processChars(char[] pattern, int k);

    /**
     * Pre-processes a String, allowing k errors. This method should not be used
     * directly because it is implicitly called in the
     * {@link #searchChars(char[], char[])} methods.
     *
     * @param pattern the String containing the pattern, may not be
     *                <code>null</code>
     * @param k       the editing distance
     * @return an Object
     */
    public final Object processString(String pattern, int k) {
        return processChars(pattern.toCharArray(), k);
    }

    /*
     * Byte searching methods
     */

    /**
     * @see StringSearch#searchBytes(byte[], int, int, byte[], Object)
     * @see #searchBytes(byte[], int, int, byte[], Object, int)
     */
    @Override
    public final int searchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, Object processed) {

        return searchBytes(text, textStart, textEnd, pattern, processed, 0)[0];
    }

    /**
     * Returns the position in the text at which the pattern was found. Returns -1
     * if the pattern was not found.
     *
     * @param text    the <code>byte</code> array containing the text, may not be
     *                <code>null</code>
     * @param pattern the <code>byte</code> array containing the pattern, may not be
     *                <code>null</code>
     * @param k       the editing distance
     * @return the position in the text or -1 if the pattern was not found
     * @see #searchBytes(byte[], int, int, byte[], Object, int)
     */
    public final int[] searchBytes(byte[] text, byte[] pattern, int k) {
        return searchBytes(text, 0, text.length, pattern, processBytes(pattern, k), k);
    }

    /**
     * Returns the position in the text at which the pattern was found. Returns -1
     * if the pattern was not found.
     *
     * @param text      the <code>byte</code> array containing the text, may not be
     *                  <code>null</code>
     * @param pattern   the <code>byte</code> array containing the pattern, may not
     *                  be <code>null</code>
     * @param processed an Object as returned from
     *                  {@link #processBytes(byte[], int)}, may not be
     *                  <code>null</code>
     * @param k         the editing distance
     * @return the position in the text or -1 if the pattern was not found
     * @see #searchBytes(byte[], int, int, byte[], Object, int)
     */
    public final int[] searchBytes(byte[] text, byte[] pattern, Object processed, int k) {

        return searchBytes(text, 0, text.length, pattern, processed, k);
    }

    /**
     * Returns the position in the text at which the pattern was found. Returns -1
     * if the pattern was not found.
     *
     * @param text    the <code>byte</code> array containing the text, may not be
     *                <code>null</code>
     * @param textEnd at which position in the text the comparing should end
     * @param pattern the <code>byte</code> array containing the pattern, may not be
     *                <code>null</code>
     * @param k       the editing distance
     * @return int the position in the text or -1 if the pattern was not found
     * @see #searchBytes(byte[], int, int, byte[], Object, int)
     */
    public final int[] searchBytes(byte[] text, int textEnd, byte[] pattern, int k) {

        return searchBytes(text, 0, textEnd, pattern, processBytes(pattern, k), k);

    }

    /**
     * Returns the position in the text at which the pattern was found. Returns -1
     * if the pattern was not found.
     *
     * @param text      the <code>byte</code> array containing the text, may not be
     *                  <code>null</code>
     * @param textEnd   at which position in the text the comparing should end
     * @param pattern   the pattern to search for, may not be <code>null</code>
     * @param processed processed object
     * @param k         the editing distance
     * @return the position in the text or -1 if the pattern was not found
     * @see #searchBytes(byte[], int, int, byte[], Object, int)
     */
    public final int[] searchBytes(byte[] text, int textEnd, byte[] pattern, Object processed, int k) {

        return searchBytes(text, 0, textEnd, pattern, processed, k);

    }

    /**
     * Returns the position in the text at which the pattern was found. Returns -1
     * if the pattern was not found.
     *
     * @param text      text the <code>byte</code> array containing the text, may
     *                  not be <code>null</code>
     * @param textStart at which position in the text the comparing should start
     * @param textEnd   at which position in the text comparing should stop
     * @param pattern   the <code>byte</code> array containing the pattern, may not
     *                  be <code>null</code>
     * @param k         the editing distance
     * @return the position in the text or -1 if the pattern was not found
     * @see #searchBytes(byte[], int, int, byte[], Object, int)
     */
    public final int[] searchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, int k) {

        return searchBytes(text, textStart, textEnd, pattern, processBytes(pattern, k), k);

    }

    /**
     * Returns the position in the text at which the pattern was found. Returns -1
     * if the pattern was not found.
     *
     * @param text      text the <code>byte</code> array containing the text, may
     *                  not be <code>null</code>
     * @param textStart at which position in the text the comparing should start
     * @param textEnd   at which position in the text comparing should stop
     * @param pattern   the pattern to search for, may not be <code>null</code>
     * @param processed an Object as returned from
     *                  {@link #processBytes(byte[], int)}, may not be
     *                  <code>null</code>
     * @param k         the editing distance
     * @return the position in the text or -1 if the pattern was not found
     * @see #processBytes(byte[], int)
     */
    public abstract int[] searchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, Object processed, int k);

    /*
     * Char searching methods
     */

    /**
     * Finder for the given pattern in the text, starting at textStart and comparing
     * to at most textEnd, allowing zero errors.
     *
     * @see StringSearch#searchChars(char[], int, int, char[], Object)
     * @see #processChars(char[], int)
     */
    @Override
    public final int searchChars(char[] text, int textStart, int textEnd, char[] pattern, Object processed) {

        return searchChars(text, textStart, textEnd, pattern, processed, 0)[0];
    }

    /**
     * Finder for the given pattern in the text, allowing k errors.
     *
     * @param text    the String containing the text, may not be <code>null</code>
     * @param pattern the pattern to search for, may not be <code>null</code>
     * @param k       the maximum number of mismatches (the editing distance)
     * @return the position in the text or -1 if the pattern was not found
     * @see #searchChars(char[], int, int, char[], Object, int)
     */
    public final int[] searchChars(char[] text, char[] pattern, int k) {
        return searchChars(text, 0, text.length, pattern, processChars(pattern, k), k);
    }

    /**
     * Finder for the given pattern in the text, allowing k errors.
     *
     * @param text      the String containing the text, may not be <code>null</code>
     * @param pattern   the pattern to search for, may not be <code>null</code>
     * @param processed an Object as returned from
     *                  {@link #processChars(char[], int)} or
     *                  {@link #processString(String, int)}, may not be
     *                  <code>null</code>
     * @param k         the maximum number of mismatches (the editing distance)
     * @return the position in the text or -1 if the pattern was not found
     * @see #searchChars(char[], int, int, char[], Object, int)
     */
    public final int[] searchChars(char[] text, char[] pattern, Object processed, int k) {

        return searchChars(text, 0, text.length, pattern, processed, k);

    }

    /**
     * Finder for the given pattern in the text, starting at textStart, allowing k
     * errors.
     *
     * @param text      the String containing the text, may not be <code>null</code>
     * @param textStart at which position in the text the comparing should start
     * @param pattern   the pattern to search for, may not be <code>null</code>
     * @param k         the maximum number of mismatches (the editing distance)
     * @return the position in the text or -1 if the pattern was not found
     * @see #searchChars(char[], int, int, char[], Object)
     */
    public final int[] searchChars(char[] text, int textStart, char[] pattern, int k) {

        return searchChars(text, textStart, text.length, pattern, processChars(pattern, k), k);

    }

    /**
     * Finder for the given pattern in the text, starting at textStart, allowing k
     * errors.
     *
     * @param text      the String containing the text, may not be <code>null</code>
     * @param textStart at which position in the text the comparing should start
     * @param pattern   the pattern to search for, may not be <code>null</code>
     * @param processed an Object as returned from
     *                  {@link #processChars(char[], int)} or
     *                  {@link #processString(String, int)}, may not be
     *                  <code>null</code>
     * @param k         the maximum number of mismatches (the editing distance)
     * @return the position in the text or -1 if the pattern was not found
     * @see #searchChars(char[], int, int, char[], Object, int)
     */
    public final int[] searchChars(char[] text, int textStart, char[] pattern, Object processed, int k) {

        return searchChars(text, textStart, text.length, pattern, processed, k);

    }

    /**
     * Finder for the given pattern in the text, starting at textStart and comparing
     * to at most textEnd, allowing k errors.
     *
     * @param text      the String containing the text, may not be <code>null</code>
     * @param textStart at which position in the text the comparing should start
     * @param textEnd   at which position in the text comparing should stop
     * @param pattern   the pattern to search for, may not be <code>null</code>
     * @param k         the maximum number of mismatches (the editing distance)
     * @return the position in the text or -1 if the pattern was not found
     */
    public final int[] searchChars(char[] text, int textStart, int textEnd, char[] pattern, int k) {

        return searchChars(text, textStart, textEnd, pattern, processChars(pattern, k), k);
    }

    /**
     * Finder for the given pattern in the text, starting at textStart and comparing
     * to at most textEnd, allowing k errors.
     *
     * @param text      the String containing the text, may not be <code>null</code>
     * @param textStart at which position in the text the comparing should start
     * @param textEnd   at which position in the text comparing should stop
     * @param pattern   the pattern to search for, may not be <code>null</code>
     * @param processed an Object as returned from
     *                  {@link #processChars(char[], int)} or
     *                  {@link #processString(String, int)}, may not be
     *                  <code>null</code>
     * @param k         the maximum number of mismatches (the editing distance)
     * @return the position in the text or -1 if the pattern was not found
     */
    public abstract int[] searchChars(char[] text, int textStart, int textEnd, char[] pattern, Object processed, int k);
}