/*

**********************************************************************

*   Copyright (C) 1999-2004 IBM and others. All rights reserved.

**********************************************************************

*   Date        Name        Description

*   12/1/99     rtg         Ported from Java

*   01/13/2000  helena      Added UErrorCode to ctors.

**********************************************************************

*/

#ifndef BRKDICT_H

#define BRKDICT_H

#include "unicode/utypes.h"

#include "unicode/uobject.h"

#include "ucmp8.h"

U_NAMESPACE_BEGIN

/**

 * 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 : public UMemory {

    //=================================================================================

    // data members

    //=================================================================================

private:

    /**

     * Maps from characters to column numbers.  The main use of this is to

     * avoid making room in the array for empty columns.

     */

    CompactByteArray* columnMap;

    /**

     * The number of actual columns in the table

     */

    int32_t 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.)

     */

    int32_t 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.

     */

    int16_t* table;

    /**

     * This index maps logical row numbers to physical row numbers

     */

    int16_t* rowIndex;

    /**

     * 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.

     */

    int32_t* rowIndexFlags;

    /**

     * 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.

     */

    int16_t* rowIndexFlagsIndex;

    /**

     * For each logical row, this index contains a constant that is added to

     * the logical column number to get the physical column number

     */

    int8_t* rowIndexShifts;

    //=================================================================================

    // deserialization

    //=================================================================================

public:

    /**

     * Constructor.  Creates the BreakDictionary by using readDictionaryFile() to

     * load the dictionary tables from the disk.

     * @param dictionaryFilename The name of the dictionary file

     * @param status for errors if it occurs

     */

    BreakDictionary(const char* dictionaryFilename, UErrorCode& status);

    /**

     * Destructor.

     */

    ~BreakDictionary();

    /**

     * Reads the dictionary file on the disk and constructs the appropriate in-memory

     * representation.

     * @param in The given memory stream

     */

    void readDictionaryFile(const uint8_t * in);

    //=================================================================================

    // access to the words

    //=================================================================================

    /**

     * Uses the column map to map the character to a column number, then

     * passes the row and column number to the other version of at()

     * @param row The current state

     * @param ch The character whose column we're interested in

     * @return The new state to transition to

     */

    int16_t at(int32_t row, UChar ch) const;

    /**

     * 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

     */

    int16_t at(int32_t row, int32_t col) const;

private:

    /**

     * Given (logical) row and column numbers, returns true if the

     * cell in that position is populated

     * @param row The LOGICAL row number of the cell

     * @param col The PHYSICAL row number of the cell

     * @return true if the cell in that position is populated

     */

    UBool cellIsPopulated(int32_t row, int32_t col) const;

    /**

     * Implementation of at() 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

     */

    int16_t internalAt(int32_t row, int32_t col) const;

    // the following methods are never meant to be called and so are not defined

    // (if you don't declare them, you get default implementations)

    BreakDictionary(const BreakDictionary& that);

    BreakDictionary& operator=(const BreakDictionary& that);

};

U_NAMESPACE_END

#endif