/*
 * Copyright (c) 1999, 2016, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

/*
 *
 * (C) Copyright Taligent, Inc. 1996, 1997 - All Rights Reserved
 * (C) Copyright IBM Corp. 1996 - 2002 - All Rights Reserved
 *
 * The original version of this source code and documentation
 * is copyrighted and owned by Taligent, Inc., a wholly-owned
 * subsidiary of IBM. These materials are provided under terms
 * of a License Agreement between Taligent and Sun. This technology
 * is protected by multiple US and International patents.
 *
 * This notice and attribution to Taligent may not be removed.
 * Taligent is a registered trademark of Taligent, Inc.
 */
package sun.text;

import java.nio.BufferUnderflowException;
import java.nio.ByteBuffer;
import java.util.MissingResourceException;
import sun.text.CompactByteArray;
import sun.text.SupplementaryCharacterData;

This is the class that represents the list of known words used by
DictionaryBasedBreakIterator.  The conceptual data structure used
here is a trie: there is a node hanging off the root node for every
letter that can start a word.  Each of these nodes has a node hanging
off of it for every letter that can be the second letter of a word
if this node is the first letter, and so on.  The trie is represented
as a two-dimensional array that can be treated as a table of state
transitions.  Indexes are used to compress this array, taking
advantage of the fact that this array will always be very sparse.
/**
 * This is the class that represents the list of known words used by
 * DictionaryBasedBreakIterator.  The conceptual data structure used
 * here is a trie: there is a node hanging off the root node for every
 * letter that can start a word.  Each of these nodes has a node hanging
 * off of it for every letter that can be the second letter of a word
 * if this node is the first letter, and so on.  The trie is represented
 * as a two-dimensional array that can be treated as a table of state
 * transitions.  Indexes are used to compress this array, taking
 * advantage of the fact that this array will always be very sparse.
 */
class BreakDictionary {

    //=========================================================================
    // data members
    //=========================================================================

    
The version of the dictionary that was read in.
/**
      * The version of the dictionary that was read in.
      */
    private static int supportedVersion = 1;

    
Maps from characters to column numbers.  The main use of this is to
avoid making room in the array for empty columns.
/**
     * Maps from characters to column numbers.  The main use of this is to
     * avoid making room in the array for empty columns.
     */
    private CompactByteArray columnMap = null;
    private SupplementaryCharacterData supplementaryCharColumnMap = null;

    
The number of actual columns in the table
/**
     * The number of actual columns in the table
     */
    private int numCols;

    
Columns are organized into groups of 32.  This says how many
column groups.  (We could calculate this, but we store the
value to avoid having to repeatedly calculate it.)
/**
     * Columns are organized into groups of 32.  This says how many
     * column groups.  (We could calculate this, but we store the
     * value to avoid having to repeatedly calculate it.)
     */
    private int numColGroups;

    
The actual compressed state table.  Each conceptual row represents
a state, and the cells in it contain the row numbers of the states
to transition to for each possible letter.  0 is used to indicate
an illegal combination of letters (i.e., the error state).  The
table is compressed by eliminating all the unpopulated (i.e., zero)
cells.  Multiple conceptual rows can then be doubled up in a single
physical row by sliding them up and possibly shifting them to one
side or the other so the populated cells don't collide.  Indexes
are used to identify unpopulated cells and to locate populated cells.
/**
     * The actual compressed state table.  Each conceptual row represents
     * a state, and the cells in it contain the row numbers of the states
     * to transition to for each possible letter.  0 is used to indicate
     * an illegal combination of letters (i.e., the error state).  The
     * table is compressed by eliminating all the unpopulated (i.e., zero)
     * cells.  Multiple conceptual rows can then be doubled up in a single
     * physical row by sliding them up and possibly shifting them to one
     * side or the other so the populated cells don't collide.  Indexes
     * are used to identify unpopulated cells and to locate populated cells.
     */
    private short[] table = null;

    
This index maps logical row numbers to physical row numbers
/**
     * This index maps logical row numbers to physical row numbers
     */
    private short[] rowIndex = null;

    
A bitmap is used to tell which cells in the comceptual table are
populated.  This array contains all the unique bit combinations
in that bitmap.  If the table is more than 32 columns wide,
successive entries in this array are used for a single row.
/**
     * A bitmap is used to tell which cells in the comceptual table are
     * populated.  This array contains all the unique bit combinations
     * in that bitmap.  If the table is more than 32 columns wide,
     * successive entries in this array are used for a single row.
     */
    private int[] rowIndexFlags = null;

    
This index maps from a logical row number into the bitmap table above.
(This keeps us from storing duplicate bitmap combinations.)  Since there
are a lot of rows with only one populated cell, instead of wasting space
in the bitmap table, we just store a negative number in this index for
rows with one populated cell.  The absolute value of that number is
the column number of the populated cell.
/**
     * This index maps from a logical row number into the bitmap table above.
     * (This keeps us from storing duplicate bitmap combinations.)  Since there
     * are a lot of rows with only one populated cell, instead of wasting space
     * in the bitmap table, we just store a negative number in this index for
     * rows with one populated cell.  The absolute value of that number is
     * the column number of the populated cell.
     */
    private short[] rowIndexFlagsIndex = null;

    
For each logical row, this index contains a constant that is added to
the logical column number to get the physical column number
/**
     * For each logical row, this index contains a constant that is added to
     * the logical column number to get the physical column number
     */
    private byte[] rowIndexShifts = null;

    //=========================================================================
    // deserialization
    //=========================================================================

    BreakDictionary(String dictionaryName, byte[] dictionaryData) {
        try {
            setupDictionary(dictionaryName, dictionaryData);
        } catch (BufferUnderflowException bue) {
            MissingResourceException e;
            e = new MissingResourceException("Corrupted dictionary data",
                                             dictionaryName, "");
            e.initCause(bue);
            throw e;
        }
    }

    private void setupDictionary(String dictionaryName, byte[] dictionaryData) {
        ByteBuffer bb = ByteBuffer.wrap(dictionaryData);

        // check version
        int version = bb.getInt();
        if (version != supportedVersion) {
            throw new MissingResourceException("Dictionary version(" + version + ") is unsupported",
                                               dictionaryName, "");
        }

        // Check data size
        int len = bb.getInt();
        if (bb.position() + len != bb.limit()) {
            throw new MissingResourceException("Dictionary size is wrong: " + bb.limit(),
                                               dictionaryName, "");
        }

        // read in the column map for BMP characteres (this is serialized in
        // its internal form: an index array followed by a data array)
        len = bb.getInt();
        short[] temp = new short[len];
        for (int i = 0; i < len; i++) {
            temp[i] = bb.getShort();
        }
        len = bb.getInt();
        byte[] temp2 = new byte[len];
        bb.get(temp2);
        columnMap = new CompactByteArray(temp, temp2);

        // read in numCols and numColGroups
        numCols = bb.getInt();
        numColGroups = bb.getInt();

        // read in the row-number index
        len = bb.getInt();
        rowIndex = new short[len];
        for (int i = 0; i < len; i++) {
            rowIndex[i] = bb.getShort();
        }

        // load in the populated-cells bitmap: index first, then bitmap list
        len = bb.getInt();
        rowIndexFlagsIndex = new short[len];
        for (int i = 0; i < len; i++) {
            rowIndexFlagsIndex[i] = bb.getShort();
        }
        len = bb.getInt();
        rowIndexFlags = new int[len];
        for (int i = 0; i < len; i++) {
            rowIndexFlags[i] = bb.getInt();
        }

        // load in the row-shift index
        len = bb.getInt();
        rowIndexShifts = new byte[len];
        bb.get(rowIndexShifts);

        // load in the actual state table
        len = bb.getInt();
        table = new short[len];
        for (int i = 0; i < len; i++) {
            table[i] = bb.getShort();
        }

        // finally, prepare the column map for supplementary characters
        len = bb.getInt();
        int[] temp3 = new int[len];
        for (int i = 0; i < len; i++) {
            temp3[i] = bb.getInt();
        }
        assert bb.position() == bb.limit();

        supplementaryCharColumnMap = new SupplementaryCharacterData(temp3);
    }

    //=========================================================================
    // access to the words
    //=========================================================================

    
Uses the column map to map the character to a column number, then
passes the row and column number to getNextState()
Params:
row – The current state
ch – The character whose column we're interested in
Returns:
The new state to transition to/**
     * Uses the column map to map the character to a column number, then
     * passes the row and column number to getNextState()
     * @param row The current state
     * @param ch The character whose column we're interested in
     * @return The new state to transition to
     */
    public final short getNextStateFromCharacter(int row, int ch) {
        int col;
        if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
            col = columnMap.elementAt((char)ch);
        } else {
            col = supplementaryCharColumnMap.getValue(ch);
        }
        return getNextState(row, col);
    }

    
Returns the value in the cell with the specified (logical) row and
column numbers.  In DictionaryBasedBreakIterator, the row number is
a state number, the column number is an input, and the return value
is the row number of the new state to transition to.  (0 is the
"error" state, and -1 is the "end of word" state in a dictionary)
Params:
row – The row number of the current state
col – The column number of the input character (0 means "not a
dictionary character")
Returns:
The row number of the new state to transition to/**
     * Returns the value in the cell with the specified (logical) row and
     * column numbers.  In DictionaryBasedBreakIterator, the row number is
     * a state number, the column number is an input, and the return value
     * is the row number of the new state to transition to.  (0 is the
     * "error" state, and -1 is the "end of word" state in a dictionary)
     * @param row The row number of the current state
     * @param col The column number of the input character (0 means "not a
     * dictionary character")
     * @return The row number of the new state to transition to
     */
    public final short getNextState(int row, int col) {
        if (cellIsPopulated(row, col)) {
            // we map from logical to physical row number by looking up the
            // mapping in rowIndex; we map from logical column number to
            // physical column number by looking up a shift value for this
            // logical row and offsetting the logical column number by
            // the shift amount.  Then we can use internalAt() to actually
            // get the value out of the table.
            return internalAt(rowIndex[row], col + rowIndexShifts[row]);
        }
        else {
            return 0;
        }
    }

    
Given (logical) row and column numbers, returns true if the
cell in that position is populated
/**
     * Given (logical) row and column numbers, returns true if the
     * cell in that position is populated
     */
    private boolean cellIsPopulated(int row, int col) {
        // look up the entry in the bitmap index for the specified row.
        // If it's a negative number, it's the column number of the only
        // populated cell in the row
        if (rowIndexFlagsIndex[row] < 0) {
            return col == -rowIndexFlagsIndex[row];
        }

        // if it's a positive number, it's the offset of an entry in the bitmap
        // list.  If the table is more than 32 columns wide, the bitmap is stored
        // successive entries in the bitmap list, so we have to divide the column
        // number by 32 and offset the number we got out of the index by the result.
        // Once we have the appropriate piece of the bitmap, test the appropriate
        // bit and return the result.
        else {
            int flags = rowIndexFlags[rowIndexFlagsIndex[row] + (col >> 5)];
            return (flags & (1 << (col & 0x1f))) != 0;
        }
    }

    
Implementation of getNextState() when we know the specified cell is
populated.
Params:
row – The PHYSICAL row number of the cell
col – The PHYSICAL column number of the cell
Returns:
The value stored in the cell/**
     * Implementation of getNextState() when we know the specified cell is
     * populated.
     * @param row The PHYSICAL row number of the cell
     * @param col The PHYSICAL column number of the cell
     * @return The value stored in the cell
     */
    private short internalAt(int row, int col) {
        // the table is a one-dimensional array, so this just does the math necessary
        // to treat it as a two-dimensional array (we don't just use a two-dimensional
        // array because two-dimensional arrays are inefficient in Java)
        return table[row * numCols + col];
    }
}