package com.walker.web.agent.impl;

import java.util.BitSet;
import java.util.concurrent.atomic.AtomicInteger;

public class SearchableString {

    private static final int[] EMPTY = new int[0];
    private static final int[][] SINGLE_VALUES = getSingleValues();

    private final char[] myChars;
    private final int[][] myIndices;
    private final Cache myPrefixCache = new Cache();
    private final Cache myPostfixCache = new Cache();

    // Reusable buffer for findIndices
    private final int[] myBuffer;

    /**
     * Creates a new instance for the specified string value.
     * @param stringValue The user agent string
     * @param maxIndex The number of unique literals
     */
    SearchableString(final String stringValue, final int maxIndex) {
        myChars = stringValue.toCharArray();
        myIndices = new int[maxIndex][];
        myBuffer = new int[myChars.length];
    }

    /**
     * Returns the size of this instance.
     * @return The size
     */
    int getSize() {
        return myChars.length;
    }

    /**
     * Indicates whether this instance starts with the specified prefix.
     * @param literal The prefix that should be tested
     * @return <code>true</code> if the argument represents the prefix of this instance, <code>false</code> otherwise.
     */
    boolean startsWith(final Literal literal) {

        // Check whether the answer is already in the cache
        final int index = literal.getIndex();
        final Boolean cached = myPrefixCache.get(index);
        if (cached != null) {
            return cached.booleanValue();
        }

        // Get the answer and cache the result
        final boolean result = literal.matches(myChars, 0);
        myPrefixCache.set(index, result);
        return result;
    }

    /**
     * Indicates whether this instance ends with the specified postfix.
     * @param literal The postfix that should be tested
     * @return <code>true</code> if the argument represents the postfix of this instance, <code>false</code> otherwise.
     */
    boolean endsWith(final Literal literal) {

        // Check whether the answer is already in the cache
        final int index = literal.getIndex();
        final Boolean cached = myPostfixCache.get(index);
        if (cached != null) {
            return cached.booleanValue();
        }

        // Get the answer and cache the result
        final boolean result = literal.matches(myChars, myChars.length - literal.getLength());
        myPostfixCache.set(index, result);
        return result;
    }

    /**
     * Returns all indices where the literal argument can be found in this String. Results are cached for better
     * performance.
     * @param literal The string that should be found
     * @return all indices where the literal argument can be found in this String.
     */
    int[] getIndices(final Literal literal) {

        // Check whether the answer is already in the cache
        final int index = literal.getIndex();
        final int[] cached = myIndices[index];
        if (cached != null) {
            return cached;
        }

        // Find all indices
        final int[] values = findIndices(literal);
        myIndices[index] = values;
        return values;
    }

    /**
     * Returns all indices where the literal argument can be found in this String.
     * @param literal The string that should be found
     * @return all indices where the literal argument can be found in this String.
     */
    private int[] findIndices(final Literal literal) {

        int count = 0;
        final char s = literal.getFirstChar();
        for (int i = 0; i < myChars.length; i++) {

            // Check the first char for better performance and check the complete string
            if ((myChars[i] == s || s == '?') && literal.matches(myChars, i)) {

                // This index matches
                myBuffer[count] = i;
                count++;
            }
        }

        // Check whether any match has been found
        if (count == 0) {
            return EMPTY;
        }

        // Use an existing array
        if (count == 1 && myBuffer[0] < SINGLE_VALUES.length) {
            final int index = myBuffer[0];
            return SINGLE_VALUES[index];
        }

        // Copy the values
        final int[] values = new int[count];
        for (int i = 0; i < count; i++) {
            values[i] = myBuffer[i];
        }
        return values;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public String toString() {
        return new String(myChars);
    }

    private static final int[][] getSingleValues() {
        final int[][] result = new int[1024][];
        for (int i = 0; i < result.length; i++) {
            result[i] = new int[]{i};
        }
        return result;
    }

    /** Compact cache for boolean values. */
    static class Cache {

        // The boolean values
        private final BitSet myValues = new BitSet();

        // Indicates whether a value has been stored for an index
        private final BitSet myIsKnown = new BitSet();

        /**
         * Gets the cached value for the specified index.
         * @param index The index of the requested value
         * @return The cached boolean value, or <code>null</code> if no value is present in the cache.
         */
        Boolean get(final int index) {

            // Check whether a true value has been set
            if (myValues.get(index)) {
                return Boolean.TRUE;
            }

            // Check whether any value has been stored
            if (myIsKnown.get(index)) {
                return Boolean.FALSE;
            }

            // No value found
            return null;
        }

        /**
         * Set the value in the cache.
         * @param index The index for the stored value
         * @param flag The actual value
         */
        void set(final int index, final boolean flag) {

            // Store the value
            myValues.set(index, flag);

            // Store the fact the value has been stored
            myIsKnown.set(index, true);
        }
    }
}

/**
 * This combines a String value with a unique int value. The int value is used for caching of results.
 */
class Literal {

    // The actual string data
    private final char[] myCharacters;

    // The unique index for this instance
    private final int myIndex;

    /**
     * Creates a new instance with the specified non-empty value.
     * @param value The String value
     * @param index The unique index for this instance
     */
    Literal(final String value, final int index) {
        myCharacters = value.toCharArray();
        myIndex = index;
    }

    /**
     * Returns the first character for quick checks.
     * @return the first character
     */
    char getFirstChar() {
        return myCharacters[0];
    }

    /**
     * Returns the size of this instance.
     * @return The size of this instance
     */
    int getLength() {
        return myCharacters.length;
    }

    /**
     * Checks whether the value represents a complete substring from the from index.
     * @param from The start index of the potential substring
     * @return <code>true</code> If the arguments represent a valid substring, <code>false</code> otherwise.
     */
    boolean matches(final char[] value, final int from) {

        // Check the bounds
        final int len = myCharacters.length;
        if (len + from > value.length || from < 0) {
            return false;
        }

        // Bounds are ok, check all characters.
        // Allow question marks to match any character
        for (int i = 0; i < len; i++) {
            if (myCharacters[i] != value[i + from] && myCharacters[i] != '?') {
                return false;
            }
        }

        // All characters match
        return true;
    }

    /**
     * Returns the unique index of this instance.
     * @return the unique index of this instance.
     */
    final int getIndex() {
        return myIndex;
    }

    private static boolean contains(final char[] characters, final char value) {

        for (final char c : characters) {
            if (c == value) {
                return true;
            }
        }
        return false;
    }

    boolean requires(final String value) {
        final int len = value.length();
        if (len == 1) {
            return contains(myCharacters, value.charAt(0));
        }

        if (len > myCharacters.length) {
            return false;
        }

        return toString().contains(value);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public String toString() {
        return new String(myCharacters);
    }
}

class LiteralDomain {

    // Keep track of the total number of instances
    private final AtomicInteger myNrOfInstances = new AtomicInteger();

    Literal createLiteral(final String contents) {
        return new Literal(contents, myNrOfInstances.getAndAdd(1));
    }

    SearchableString getSearchableString(final String contents) {
        final int maxIndex = myNrOfInstances.get() + 1;

        return new SearchableString(contents, maxIndex);
    }
}