CharIntMap.java

/*
 * CharIntMap.java
 *
 * Created on 13.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;

import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.util.Arrays;

/**
 * The CharIntMap is a collection to save <code>char</code> to <code>int</code>
 * mappings in. The CharIntMap is destined to provide fast access to skip tables
 * while being both Unicode-safe and more RAM-effective than a naive
 * <code>int</code> array. <br>
 * <br>
 * The CharIntMap is initialized by specifying the extent between the lowest and
 * the highest occuring character and the lowest occuring character. Only an
 * array of size <code>highest - lowest + 1</code> is constructed. <br>
 * <br>
 * There's usually no need to construct a CharIntMap yourself, it is done
 * automatically for you in the pre-processing methods.
 *
 * @author <a href="mailto:jb@eaio.com">Johann Burkard</a>
 * @version 1.2
 */
class CharIntMap implements Externalizable, Cloneable {
    private static final long serialVersionUID = 1L;

    private int[] array;
    private char lowest;
    private int defaultValue;

    /**
     * Constructor for CharIntMap. Required for Serialization.
     */
    public CharIntMap() {
    }

    /**
     * Constructor for CharIntMap.
     *
     * @param extent the extent of the text
     * @param lowest the lowest occuring character
     */
    public CharIntMap(final int extent, final char lowest) {
        this(extent, lowest, 0);
    }

    /**
     * Constructor for CharIntMap.
     *
     * @param extent       the extent of the text
     * @param lowest       the lowest occuring character
     * @param defaultValue a default value to initialize the underlying
     *                     <code>int</code> array with
     */

    public CharIntMap(final int extent, final char lowest, final int defaultValue) {
        array = new int[extent];
        this.lowest = lowest;
        if (defaultValue != 0) {
            Arrays.fill(array, defaultValue);
            this.defaultValue = defaultValue;
        }
    }

    /**
     * Returns a deep clone of this CharIntMap.
     *
     * @return an CharIntMap containing the same mappings
     */
    @Override
    public Object clone() {
        final CharIntMap out = new CharIntMap();
        out.lowest = lowest;
        out.defaultValue = defaultValue;
        if (array != null) {
            out.array = new int[array.length];
            System.arraycopy(array, 0, out.array, 0, array.length);
        }
        return out;
    }

    /**
     * Returns the stored value for the given <code>char</code>.
     *
     * @param c the <code>char</code>
     * @return the stored value
     */
    public int get(final char c) {

        /*
         * For the Sun VM, the char version speeds up some algorithms by 5 to 10 %; in
         * the IBM VM, there is no difference.
         */

        // int x = c - lowest;
        // if (x < 0 || x >= array.length) {
        // return defaultValue;
        // }

        final char x = (char) (c - lowest);
        if (x >= array.length) {
            return defaultValue;
        }
        return array[x];
    }

    /**
     * Sets the stored value for the given <code>char</code>.
     *
     * @param c   the <code>char</code>
     * @param val the new value
     */
    public void set(final char c, final int val) {

        /*
         * For the Sun VM, the char version speeds up some algorithms by 5 to 10 %; in
         * the IBM VM, there is no difference.
         */

        // int x = c - lowest;
        // if (x < 0 || x >= array.length) {
        // return;
        // }

        final char x = (char) (c - lowest);
        if (x >= array.length) {
            return;
        }
        array[x] = val;
    }

    /**
     * Returns the extent of the actual <code>char</code> array.
     *
     * @return the extent
     */
    public int getExtent() {
        return array.length;
    }

    /**
     * Returns the lowest char that mappings can be saved for.
     *
     * @return a <code>char</code>
     */
    public char getLowest() {
        return lowest;
    }

    /**
     * Returns the highest char that mappings can be saved for.
     *
     * @return char
     */
    public char getHighest() {
        return (char) (lowest + array.length);
    }

    /**
     * Returns if this Object is equal to another Object.
     *
     * @param obj the other Object
     * @return if this Object is equal
     * @see java.lang.Object#equals(Object)
     */
    @Override
    public boolean equals(final Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof CharIntMap)) {
            return false;
        }
        final CharIntMap m = (CharIntMap) obj;
        if (lowest != m.lowest) {
            return false;
        }
        if (defaultValue != m.defaultValue) {
            return false;
        }
        if (array == null && m.array == null) {
            return true;
        } else if (array != null && m.array == null) {
            return false;
        } else if (array == null) {
            return false;
        } else {
            for (int i = 0; i < array.length; i++) {
                if (array[i] != m.array[i]) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Returns the hashCode of this Object.
     *
     * @return the hashCode
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode() {
        int out = getClass().getName().hashCode();
        out ^= lowest;
        out ^= defaultValue;
        if (array != null) {
            for (final int element : array) {
                out ^= element;
            }
        }
        return out;
    }

    /**
     * Returns a String representation of this Object.
     *
     * @return a String
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        final StringBuilder out = new StringBuilder(128);
        out.append("{ CharIntMap: lowest = ");
        out.append(lowest);
        out.append(", defaultValue = ");
        out.append(defaultValue);
        if (array != null) {
            out.append(", array = ");
            for (int i = 0; i < array.length; i++) {
                if (array[i] != 0) {
                    out.append(i);
                    out.append(": ");
                    out.append(array[i]);
                }
            }
        }
        out.append(" }");
        return out.toString();
    }

    /**
     * @see java.io.Externalizable#writeExternal(java.io.ObjectOutput)
     */
    @Override
    public void writeExternal(final ObjectOutput out) throws IOException {
        if (array == null) {
            out.writeInt(0);
        } else {
            out.writeInt(array.length);
            for (final int element : array) {
                out.writeInt(element);
            }
        }
        out.writeChar(lowest);
        out.writeInt(defaultValue);
    }

    /**
     * @see java.io.Externalizable#readExternal(java.io.ObjectInput)
     */
    @Override
    public void readExternal(final ObjectInput in) throws IOException {
        final int l = in.readInt();
        if (l > 0) {
            array = new int[l];
            for (int i = 0; i < array.length; i++) {
                array[i] = in.readInt();
            }
        }
        lowest = in.readChar();
        defaultValue = in.readInt();
    }

}