/* Copyright (c) 2001-2024, The HSQL Development Group
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the HSQL Development Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


package org.hsqldb.lib;

import java.io.IOException;
import java.io.InputStream;
import java.io.Reader;

/**
 * Implements the Knuth-Morris-Pratt string search algorithm for searching
 * streams or arrays of octets or characters. <p>
 *
 * This algorithm is a good choice for searching large, forward-only access
 * streams for repeated search using pre-processed small to medium-sized
 * patterns.  <p>
 *
 * This is because in addition to the facts that it:
 *
 * <ul>
 * <li>does not require pre-processing the searched data (only the pattern)
 * <li>scans strictly left-to-right
 * <li>does not need to perform back tracking
 * <li>does not need to employ reverse scan order
 * <li>does not need to perform effectively random access lookups against
 *     the searched data or pattern
 * </ul>
 *
 * it also has:
 *
 * <ul>
 * <li>a very simple, highly predictable behavior
 * <li>an O(n) complexity once the a search pattern is preprocessed
 * <li>an O(m) complexity for pre-processing search patterns
 * <li>a worst case performance characteristic of only 2n
 * <li>an average case performance characteristic that is deemed to be
 *     2-3 times better than the naive search algorithm employed by
 *     {@link String#indexOf(java.lang.String,int)}.
 * </ul>
 *
 * Note that the Boyer-Moore algorithm is generally considered to be the better
 * practical, all-round exact sub-string search algorithm, but due to its
 * reverse pattern scan order, performance considerations dictate that it
 * requires more space and that is somewhat more complex to implement
 * efficiently for searching forward-only access streams. <p>
 *
 * In particular, its higher average performance is biased toward larger
 * search patterns, due to its ability to skip ahead further and with fewer
 * tests under reverse pattern scan. But when searching forward-only access
 * streams, overall performance considerations require the use a circular buffer
 * of the same size as the search pattern to hold data from the searched stream
 * as it is being compared in reverse order to the search pattern. Hence,
 * Boyer-Moore requires at minimum twice the memory required by
 * Knuth-Morris-Pratt to search for the same pattern and that factor has the
 * greatest impact precisely on the same class of patterns (larger) for which it
 * is most outperforms Knuth-Morris-Pratt.
 *
 * @author Campbell Burnet (campbell-burnet@users dot sourceforge.net)
 * @version 2.7.x
 * @since 2.1
 * @see
 * <a href="http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm">
 * Knuth-Morris-Pratt algorithm</a>
 */
public class KMPSearchAlgorithm {

    // @todo 2.7.x - performance optimizations for backend use

    /**
     * computes the table used to optimize octet pattern search
     *
     * @param pattern for which to compute the table.
     * @return the table computed from the octet pattern.
     * @throws IllegalArgumentException if {@code pattern == null
     *                                               || pattern.length < 2}.
     */
    public static int[] computeTable(final byte[] pattern) {

        if (pattern == null) {
            throw new IllegalArgumentException("pattern must not be null.");
        } else if (pattern.length < 2) {
            throw new IllegalArgumentException("pattern.length must be > 1.");
        }

        //
        final int[] table = new int[pattern.length];
        int         i     = 2;
        int         j     = 0;

        //
        table[0] = -1;
        table[1] = 0;

        //
        while (i < pattern.length) {
            if (pattern[i - 1] == pattern[j]) {
                table[i] = j + 1;

                j++;
                i++;
            } else if (j > 0) {
                j = table[j];
            } else {
                table[i] = 0;

                i++;

                j = 0;
            }
        }

        //
        return table;
    }

    /**
     * computes the table used to optimize octet pattern search
     *
     * @param pattern for which to compute the table.
     * @return the table computed from the character pattern.
     * @throws IllegalArgumentException if {@code pattern == null
     *                                               || pattern.length < 2}.
     */
    public static int[] computeTable(final char[] pattern) {

        if (pattern == null) {
            throw new IllegalArgumentException("pattern must  not be null.");
        } else if (pattern.length < 2) {
            throw new IllegalArgumentException("pattern.length must be > 1.");
        }

        int[] table = new int[pattern.length];
        int   i     = 2;
        int   j     = 0;

        table[0] = -1;
        table[1] = 0;

        while (i < pattern.length) {
            if (pattern[i - 1] == pattern[j]) {
                table[i] = j + 1;

                j++;
                i++;
            } else if (j > 0) {
                j = table[j];
            } else {
                table[i] = 0;

                i++;

                j = 0;
            }
        }

        return table;
    }

    /**
     * computes the table used to optimize octet pattern search
     *
     * @param pattern for which to compute the table.
     * @return the table computed from the String pattern.
     * @throws IllegalArgumentException if {@code pattern == null
     *                                               || pattern.length < 2}.
     */
    public static int[] computeTable(final String pattern) {

        if (pattern == null) {
            throw new IllegalArgumentException("Pattern must  not be null.");
        } else if (pattern.length() < 2) {
            throw new IllegalArgumentException("Pattern length must be > 1.");
        }

        final int patternLength = pattern.length();

        //
        int[] table = new int[patternLength];
        int   i     = 2;
        int   j     = 0;

        table[0] = -1;
        table[1] = 0;

        while (i < patternLength) {
            if (pattern.charAt(i - 1) == pattern.charAt(j)) {
                table[i] = j + 1;

                j++;
                i++;
            } else if (j > 0) {
                j = table[j];
            } else {
                table[i] = 0;

                i++;

                j = 0;
            }
        }

        return table;
    }

    /**
     * Searches the given octet stream for the given octet pattern
     * returning the zero-based offset from the initial stream position
     * at which the first match is detected.
     * <p>
     *
     * Note that the signature includes a slot for the table so that
     * searches for a pattern can be performed multiple times without
     * incurring the overhead of computing the table each time.
     *
     * @param inputStream in which to search
     * @param pattern     for which to search
     * @param table       computed from the pattern that optimizes the search.
     *                    If null, automatically computed.
   * @return zero-based offset of first match; -1 if {@code inputStream == null
     *          || pattern == null} or no match found, ; zero (0) if
     *         {@code pattern.length == 0}.
     * @throws IOException when an error occurs accessing the input stream.
     */
    public static long search(
            final InputStream inputStream,
            final byte[] pattern,
            int[] table)
            throws IOException {

        if (inputStream == null || pattern == null) {
            return -1;
        }

        //
        final int patternLength = pattern.length;

        // as per SQL LOCATE, INSTR, POSITION( IN )
        if (patternLength == 0) {
            return 0;
        }

        //
        long streamIndex = -1;
        int  currentByte;

        if (patternLength == 1) {
            final int byteToFind = pattern[0];

            currentByte = inputStream.read();

            while (-1 != currentByte) {
                streamIndex++;

                if (currentByte == byteToFind) {
                    return streamIndex;
                }

                currentByte = inputStream.read();
            }

            return -1;
        }

        int         patternIndex = 0;
        final int[] localTable   = table == null
                                   ? computeTable(pattern)
                                   : table;

        currentByte = inputStream.read();

        while (-1 != currentByte) {
            streamIndex++;

            if (currentByte == pattern[patternIndex]) {
                patternIndex++;
            } else if (patternIndex > 0) {
                patternIndex = localTable[patternIndex];

                patternIndex++;
            }

            if (patternIndex == patternLength) {
                return streamIndex - (patternLength - 1);
            }

            currentByte = inputStream.read();
        }

        return -1;
    }

    /**
     * Searches the given character stream for the given character pattern
     * returning the zero-based offset from the initial stream position
     * at which the first match is detected. <p>
     *
     * Note that the signature includes a slot for the table so that
     * searches for a pattern can be performed multiple times without
     * incurring the overhead of computing the table each time.
     *
     * @param reader in which to search
     * @param pattern for which to search
     * @param table   computed from the pattern that optimizes the search
     *                If null, automatically computed.
    * @return zero-based offset of first match; -1 if {@code reader == null
     *          || pattern == null} or no match found, ; zero (0) if
     *         {@code pattern.length == 0}.
     * @throws IOException when an error occurs accessing the input stream.
     */
    @SuppressWarnings({ "NestedAssignment", "AssignmentToMethodParameter" })
    public static long search(
            final Reader reader,
            final char[] pattern,
            int[] table)
            throws IOException {

        if (reader == null || pattern == null) {
            return -1;
        }

        //
        final int patternLength = pattern.length;

        // as per SQL LOCATE, INSTR, POSITION( IN )
        if (patternLength == 0) {
            return 0;
        }

        //
        long streamIndex = -1;
        int  currentCharacter;

        if (patternLength == 1) {
            final int characterToFind = pattern[0];

            currentCharacter = reader.read();

            while (-1 != currentCharacter) {
                streamIndex++;

                if (currentCharacter == characterToFind) {
                    return streamIndex;
                }

                currentCharacter = reader.read();
            }

            return -1;
        }

        final int[] localTable = table == null
                                 ? computeTable(pattern)
                                 : table;

        //
        int patternIndex = 0;

        currentCharacter = reader.read();

        while (-1 != currentCharacter) {
            streamIndex++;

            if (currentCharacter == pattern[patternIndex]) {
                patternIndex++;
            } else if (patternIndex > 0) {
                patternIndex = localTable[patternIndex];

                patternIndex++;
            }

            if (patternIndex == patternLength) {
                return streamIndex - (patternLength - 1);
            }

            currentCharacter = reader.read();
        }

        return -1;
    }

    /**
     * Searches the given character stream for the given character pattern
     * returning the zero-based offset from the initial stream position
     * at which the first match is detected.
     * <p>
     *
     * Note that the signature includes a slot for the table so that
     * searches for a pattern can be performed multiple times without
     * incurring the overhead of computing the table each time.
     *
     * @param reader  in which to search
     * @param pattern for which to search
     * @param table   computed from the pattern that optimizes the search
     *                If null, automatically computed.
     * @return zero-based offset of first match; -1 if {@code reader == null
     *          || pattern == null} or no match found, ; zero (0) if
     *         {@code pattern.length() == 0}.
     * @throws IOException when an error occurs accessing the input stream.
     */
    @SuppressWarnings({ "NestedAssignment", "AssignmentToMethodParameter" })
    public static long search(
            final Reader reader,
            final String pattern,
            int[] table)
            throws IOException {

        if (reader == null || pattern == null) {
            return -1;
        }

        //
        final int patternLength = pattern.length();

        // as per SQL LOCATE, INSTR, POSITION( IN )
        if (patternLength == 0) {
            return 0;
        }

        //
        long streamIndex = -1;
        int  currentCharacter;

        if (patternLength == 1) {
            final int characterToFind = pattern.charAt(0);

            currentCharacter = reader.read();

            while (-1 != currentCharacter) {
                streamIndex++;

                if (currentCharacter == characterToFind) {
                    return streamIndex;
                }

                currentCharacter = reader.read();
            }

            return -1;
        }

        final int[] localTable = table == null
                                 ? computeTable(pattern)
                                 : table;

        //
        int patternIndex = 0;

        currentCharacter = reader.read();

        while (-1 != currentCharacter) {
            streamIndex++;

            if (currentCharacter == pattern.charAt(patternIndex)) {
                patternIndex++;
            } else if (patternIndex > 0) {
                patternIndex = localTable[patternIndex];

                patternIndex++;
            }

            if (patternIndex == patternLength) {
                return streamIndex - (patternLength - 1);
            }

            currentCharacter = reader.read();
        }

        return -1;
    }

    /**
     * Searches the given octet string for the given octet pattern
     * returning the zero-based offset from given start position
     * at which the first match is detected. <p>
     *
     * Note that the signature includes a slot for the table so that
     * searches for a pattern can be performed multiple times without
     * incurring the overhead of computing the table each time.
     *
     * @param source array in which to search
     * @param pattern to be matched
     * @param table   computed from the pattern that optimizes the search
     *                If null, automatically computed.
     * @param start   position in source at which to start the search
     * @return zero-based offset of first match; -1 if {@code source == null
     *          || pattern == null} or no match found, ; start if
     *         {@code pattern.length == 0 and start <= source.length}.
     */
    public static int search(
            final byte[] source,
            final byte[] pattern,
            int[] table,
            final int start) {

        if (source == null || pattern == null) {
            return -1;
        }

        //
        final int sourceLength  = source.length;
        final int patternLength = pattern.length;

        // as per SQL LOCATE, INSTR, POSITION( IN )
        if (patternLength == 0) {
            return start > sourceLength
                   ? -1
                   : start;
        }

        //
        int sourceIndex = start;

        if (patternLength == 1) {
            final int byteToFind = pattern[0];

            for (; sourceIndex < sourceLength; sourceIndex++) {
                if (source[sourceIndex] == byteToFind) {
                    return sourceIndex;
                }
            }

            return -1;
        }

        //
        int matchStart   = start;
        int patternIndex = 0;

        //
        final int[] localTable = table == null
                                 ? computeTable(pattern)
                                 : table;

        //
        while ((sourceIndex < sourceLength) && (patternIndex < patternLength)) {
            if (source[sourceIndex] == pattern[patternIndex]) {
                patternIndex++;
            } else {
                final int tableValue = localTable[patternIndex];

                matchStart += (patternIndex - tableValue);

                if (patternIndex > 0) {
                    patternIndex = tableValue;
                }

                patternIndex++;
            }

            sourceIndex = (matchStart + patternIndex);
        }

        if (patternIndex == patternLength) {
            return matchStart;
        } else {
            return -1;
        }
    }

    /**
     * Searches the given character array for the given character pattern
     * returning the zero-based offset from given start position
     * at which the first match is detected.
     *
     * @param source array in which to search
     * @param pattern to be matched
     * @param table   computed from the pattern that optimizes the search
     *                If null, automatically computed.
     * @param start   position in source at which to start the search
     * @return zero-based offset of first match; -1 if {@code source == null
     *          || pattern == null} or no match found, ; start if
     *         {@code pattern.length == 0 and start <= source.length}.
     */
    public static int search(
            final char[] source,
            final char[] pattern,
            int[] table,
            final int start) {

        if (source == null || pattern == null) {
            return -1;
        }

        final int sourceLength  = source.length;
        final int patternLength = pattern.length;

        // as per SQL LOCATE, INSTR, POSITION( IN )
        if (patternLength == 0) {
            return start > sourceLength
                   ? -1
                   : start;
        }

        int sourceIndex = start;

        if (patternLength == 1) {
            final int characterToFind = pattern[0];

            for (; sourceIndex < sourceLength; sourceIndex++) {
                if (source[sourceIndex] == characterToFind) {
                    return sourceIndex;
                }
            }

            return -1;
        }

        //
        int matchStart   = start;
        int patternIndex = 0;

        //
        final int[] localTable = table == null
                                 ? computeTable(pattern)
                                 : table;

        //
        while ((sourceIndex < sourceLength) && (patternIndex < patternLength)) {
            if (source[sourceIndex] == pattern[patternIndex]) {
                patternIndex++;
            } else {
                final int tableValue = localTable[patternIndex];

                matchStart += (patternIndex - tableValue);

                if (patternIndex > 0) {
                    patternIndex = tableValue;
                }

                patternIndex++;
            }

            sourceIndex = (matchStart + patternIndex);
        }

        if (patternIndex == patternLength) {
            return matchStart;
        } else {
            return -1;
        }
    }

    /**
     * Searches the given String object for the given character pattern
     * returning the zero-based offset from given start position
     * at which the first match is detected.
     *
     * @param source array to be searched
     * @param pattern to be matched
     * @param table   computed from the pattern that optimizes the search
     * @param start   position in source at which to start the search
     * @return zero-based offset of first match; -1 if {@code source == null
     *          || pattern == null} or no match found, ; start if
     *         {@code pattern.length == 0 and start <= source.length}.
     */
    public static int search(
            final String source,
            final String pattern,
            int[] table,
            final int start) {

        if (source == null || pattern == null) {
            return -1;
        }

        final int patternLength = pattern.length();
        final int sourceLength  = source.length();

        // as per SQL LOCATE, INSTR, POSITION( IN )
        if (patternLength == 0) {
            return start > sourceLength
                   ? -1
                   : start;
        }

        if (patternLength == 1) {
            return source.indexOf(pattern, start);
        }

        //
        int matchStart   = start;
        int sourceIndex  = start;
        int patternIndex = 0;

        //
        final int[] localTable = table == null
                                 ? computeTable(pattern)
                                 : table;

        //
        while ((sourceIndex < sourceLength) && (patternIndex < patternLength)) {
            if (source.charAt(sourceIndex) == pattern.charAt(patternIndex)) {
                patternIndex++;
            } else {
                final int tableValue = localTable[patternIndex];

                matchStart += (patternIndex - tableValue);

                if (patternIndex > 0) {
                    patternIndex = tableValue;
                }

                patternIndex++;
            }

            sourceIndex = matchStart + patternIndex;
        }

        if (patternIndex == patternLength) {
            return matchStart;
        } else {
            return -1;
        }
    }

    private KMPSearchAlgorithm() {
        assert false: "Pure Utility Class";
    }
}
