Back to index...

	/*
	* 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.
	*/
	class BreakDictionary {

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

	/**
	* 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.
	*/
	private CompactByteArray columnMap = null;
	private SupplementaryCharacterData supplementaryCharColumnMap = null;

	/**
	* 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.)
	*/
	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.
	*/
	private short[] table = null;

	/**
	* 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.
	*/
	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.
	*/
	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
	*/
	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()
	* @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)
	* @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
	*/
	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.
	* @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];
	}
	}

Back to index...