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("this is null" "nall" 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);
}