StringSearch.java
/*
* StringSearch.java
*
* Created on 14.06.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;
/**
* The base class for String searching implementations. String searching
* implementations do not maintain the state and are thread-safe - one instance can
* be used by as many threads as required.
* <p>
* Most pattern-matching algorithms pre-process the pattern to search for in
* some way. Subclasses of StringSearch allow retrieving the pre-processed
* pattern to save the time required to build up character tables.
* <p>
* Some of the Objects returned from {@link #processBytes(byte[])},
* {@link #processChars(char[])}, might implement the
* {@link java.io.Serializable} interface and enable you to serialize
* pre-processed Objects to disk, see concrete implementations for details.
*
* @author <a href="mailto:jb@eaio.com">Johann Burkard</a>
* @version 1.2
*/
abstract class StringSearch {
/**
* Pre-processes a <code>byte</code> array.
*
* @param pattern the <code>byte</code> array containing the pattern, may not be
* <code>null</code>
* @return an Object
*/
public abstract Object processBytes(byte[] pattern);
/**
* Pre-processes a <code>char</code> array
*
* @param pattern a <code>char</code> array containing the pattern, may not be
* <code>null</code>
* @return an Object
*/
public abstract Object processChars(char[] pattern);
/* Byte searching methods */
/**
* 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>
* @return the position in the text or -1 if the pattern was not found
* @see #searchBytes(byte[], int, int, byte[], Object)
*/
public final int searchBytes(byte[] text, byte[] pattern) {
return searchBytes(text, 0, text.length, pattern, processBytes(pattern));
}
/**
* 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 pattern to search for, may not be <code>null</code>
* @param processed an Object as returned from {@link #processBytes(byte[])},
* may not be <code>null</code>
* @return the position in the text or -1 if the pattern was not found
* @see #searchBytes(byte[], int, int, byte[], Object)
*/
public final int searchBytes(byte[] text, byte[] pattern, Object processed) {
return searchBytes(text, 0, text.length, pattern, processed);
}
/**
* 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 textStart at which position in the text the comparing should start
* @param pattern the <code>byte</code> array containing the pattern, may not
* be <code>null</code>
* @return int the position in the text or -1 if the pattern was not found
* @see #searchBytes(byte[], int, int, byte[], Object)
*/
public final int searchBytes(byte[] text, int textStart, byte[] pattern) {
return searchBytes(text, textStart, text.length, pattern, processBytes(pattern));
}
/**
* 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 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 processed object
* @return the position in the text or -1 if the pattern was not found
* @see #searchBytes(byte[], int, int, byte[], Object)
*/
public final int searchBytes(byte[] text, int textStart, byte[] pattern, Object processed) {
return searchBytes(text, textStart, text.length, pattern, processed);
}
/**
* 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>
* @return the position in the text or -1 if the pattern was not found
* @see #searchBytes(byte[], int, int, byte[], Object)
*/
public final int searchBytes(byte[] text, int textStart, int textEnd, byte[] pattern) {
return searchBytes(text, textStart, textEnd, pattern, processBytes(pattern));
}
/**
* 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[])},
* may not be <code>null</code>
* @return the position in the text or -1 if the pattern was not found
* @see #processBytes(byte[])
*/
public abstract int searchBytes(byte[] text, int textStart, int textEnd, byte[] pattern, Object processed);
/* Char searching methods */
/**
* Returns the position in the text at which the pattern was found. Returns -1
* if the pattern was not found.
*
* @param text the character array containing the text, may not be
* <code>null</code>
* @param pattern the <code>char</code> array containing the pattern, may not be
* <code>null</code>
* @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, char[] pattern) {
return searchChars(text, 0, text.length, pattern, processChars(pattern));
}
/**
* Returns the index of the pattern in the text using the pre-processed Object.
* Returns -1 if the pattern was not found.
*
* @param text the character array containing the text, may not be
* <code>null</code>
* @param pattern the <code>char</code> array containing the pattern, may not
* be <code>null</code>
* @param processed an Object as returned from {@link #processChars(char[])},
* may not be <code>null</code>
* @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, char[] pattern, Object processed) {
return searchChars(text, 0, text.length, pattern, processed);
}
/**
* Returns the position in the text at which the pattern was found. Returns -1
* if the pattern was not found.
*
* @param text the character array containing the text, may not be
* <code>null</code>
* @param textStart at which position in the text the comparing should start
* @param pattern the <code>char</code> array containing the pattern, may not
* be <code>null</code>
* @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) {
return searchChars(text, textStart, text.length, pattern, processChars(pattern));
}
/**
* Returns the index of the pattern in the text using the pre-processed Object.
* Returns -1 if the pattern was not found.
*
* @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 <code>char</code> array containing the pattern, may not
* be <code>null</code>
* @param processed an Object as returned from {@link #processChars(char[])},
* may not be <code>null</code>
* @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, Object processed) {
return searchChars(text, textStart, text.length, pattern, processed);
}
/**
* Returns the position in the text at which the pattern was found. Returns -1
* if the pattern was not found.
*
* @param text the character 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>char</code> array containing the pattern, may not
* be <code>null</code>
* @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, int textEnd, char[] pattern) {
return searchChars(text, textStart, textEnd, pattern, processChars(pattern));
}
/**
* Returns the index of the pattern in the text using the pre-processed Object.
* Returns -1 if the pattern was not found.
*
* @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[])},
* may not be <code>null</code>
* @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);
/* String searching methods */
/**
* Returns if the Object's class name matches this Object's class name.
*
* @param obj the other Object
* @return if the Object is equal to this Object
* @see java.lang.Object#equals(Object)
*/
@Override
public final boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
return getClass().equals(obj.getClass());
}
/**
* Returns the hashCode of the Object's Class because all instances of this
* Class are equal.
*
* @return an int
* @see java.lang.Object#hashCode()
*/
@Override
public final int hashCode() {
return getClass().getName().hashCode();
}
/**
* Returns a String representation of this. Simply returns the name of the
* Class.
*
* @return a String
* @see java.lang.Object#toString()
*/
@Override
public final String toString() {
return toStringBuffer(null).toString();
}
/**
* Appends a String representation of this to the given {@link StringBuffer} or
* creates a new one if none is given. This method is not <code>final</code>
* because subclasses might want a different String format.
*
* @param in the StringBuffer to append to, may be <code>null</code>
* @return a StringBuffer
*/
public StringBuffer toStringBuffer(StringBuffer in) {
if (in == null) {
in = new StringBuffer();
}
in.append("{ ");
int idx = getClass().getName().lastIndexOf(".");
if (idx > -1) {
in.append(getClass().getName().substring(++idx));
} else {
in.append(getClass().getName());
}
in.append(" }");
return in;
}
/* Utility methods */
/**
* Returns a {@link CharIntMap} of the extent of the given pattern, using no
* default value.
*
* @param pattern the pattern
* @return a CharIntMap
* @see CharIntMap#CharIntMap(int, char)
*/
protected CharIntMap createCharIntMap(char[] pattern) {
return createCharIntMap(pattern, 0);
}
/**
* Returns a {@link CharIntMap} of the extent of the given pattern, using the
* specified default value.
*
* @param pattern the pattern
* @param defaultValue the default value
* @return a CharIntMap
* @see CharIntMap#CharIntMap(int, char, int)
*/
protected CharIntMap createCharIntMap(char[] pattern, int defaultValue) {
char min = Character.MAX_VALUE;
char max = Character.MIN_VALUE;
for (char element : pattern) {
max = max > element ? max : element;
min = min < element ? min : element;
}
return new CharIntMap(max - min + 1, min, defaultValue);
}
/**
* Converts the given <code>byte</code> to an <code>int</code>.
*
* @param idx the byte
* @return an int
*/
protected final int index(byte idx) {
return idx < 0 ? 256 + idx : idx;
}
/* Utility methods */
}