Top Description Inners Fields Constructors Methods
com.ibm.icu.impl

public abstract Class Trie

extends Object
Class Inheritance
Known Direct Subclasses
com.ibm.icu.impl.CharTrie, com.ibm.icu.impl.IntTrie
Imports
java.nio.ByteBuffer, java.util.Arrays, com.ibm.icu.lang.UCharacter, com.ibm.icu.text.UTF16

A trie is a kind of compressed, serializable table of values associated with Unicode code points (0..0x10ffff).

This class defines the basic structure of a trie and provides methods to retrieve the offsets to the actual data.

Data will be the form of an array of basic types, char or int.

The actual data format will have to be specified by the user in the inner static interface com.ibm.icu.impl.Trie.DataManipulate.

This trie implementation is optimized for getting offset while walking forward through a UTF-16 string. Therefore, the simplest and fastest access macros are the fromLead() and fromOffsetTrail() methods. The fromBMP() method are a little more complicated; they get offsets even for lead surrogate codepoints, while the fromLead() method get special "folded" offsets for lead surrogate code units if there is relevant data associated with them. From such a folded offsets, an offset needs to be extracted to supply to the fromOffsetTrail() methods. To handle such supplementary codepoints, some offset information are kept in the data.

Methods in com.ibm.icu.impl.Trie.DataManipulate are called to retrieve that offset from the folded value for the lead surrogate unit.

For examples of use, see com.ibm.icu.impl.CharTrie or com.ibm.icu.impl.IntTrie.

Author
synwee
Since
release 2.1, Jan 01 2002
See Also
com.ibm.icu.impl.CharTrie, com.ibm.icu.impl.IntTrie

Nested and Inner Type Summary

Modifier and TypeClass and Description
public static interface
Trie.DataManipulate

Character data in com.ibm.impl.Trie have different user-specified format for different purposes.

private static class
Trie.DefaultGetFoldingOffset

Field Summary

Modifier and TypeField and Description
protected static final int
BMP_INDEX_LENGTH

Length of the BMP portion of the index (stage 1) array.

protected static final int
DATA_BLOCK_LENGTH

Number of data values in a stage 2 (data array) block.

protected static final int
HEADER_LENGTH_

Size of Trie header in bytes

protected static final int
HEADER_OPTIONS_DATA_IS_32_BIT_

protected static final int
HEADER_OPTIONS_INDEX_SHIFT_

protected static final int
HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_

Latin 1 option mask

private static final int
HEADER_OPTIONS_SHIFT_MASK_

Header option formatting

protected static final int
HEADER_SIGNATURE_

Constant number to authenticate the byte block

protected static final int
INDEX_STAGE_1_SHIFT_

Shift size for shifting right the input index.

protected static final int
INDEX_STAGE_2_SHIFT_

Shift size for shifting left the index array values.

protected static final int
INDEX_STAGE_3_MASK_

Mask for getting the lower bits from the input index.

protected static final int
LEAD_INDEX_OFFSET_

Lead surrogate code points' index displacement in the index array.

protected int
m_dataLength_

Length of the data array

protected Trie.DataManipulate
m_dataManipulate_

Internal TrieValue which handles the parsing of the data value.

protected int
m_dataOffset_

Start index of the data portion of the trie.

protected char[]
m_index_

Index or UTF16 characters

private boolean
m_isLatin1Linear_

Flag indicator for Latin quick access data block

private int
m_options_

Trie options field.

protected static final int
SURROGATE_BLOCK_BITS

Number of bits of a trail surrogate that are used in index table lookups.

protected static final int
SURROGATE_BLOCK_COUNT

Number of index (stage 1) entries per lead surrogate.

protected static final int
SURROGATE_MASK_

Surrogate mask to use when shifting offset to retrieve supplementary values

Constructor Summary

AccessConstructor and Description
protected
Trie(ByteBuffer
data of an ICU data file, containing the trie
bytes, Trie.DataManipulate
object containing the information to parse the trie data
dataManipulate)

Trie constructor for CharTrie use.

protected
Trie(char[]
array to be used for index
index, int
used by the trie
options, Trie.DataManipulate
object containing the information to parse the trie data
dataManipulate)

Trie constructor

Method Summary

Modifier and TypeMethod and Description
private final boolean

Returns:

true if the header is authenticated valid
checkHeader(int
This contains the options and type of a Trie
signature)

Authenticates raw data header.

public boolean

Returns:

true if the argument Trie has the same data as this Trie, false otherwise
equals(Object
Trie to check
other)

Overrides java.lang.Object.equals.

Checks if the argument Trie has the same data as this Trie.
protected final int

Returns:

offset to data
getBMPOffset(char
BMP character
ch)

Gets the offset to data which the BMP character points to Treats a lead surrogate as a normal code point.

protected final int

Returns:

offset to data
getCodePointOffset(int
codepoint
ch)

Internal trie getter from a code point.

protected abstract int

Returns:

32 bit value
getInitialValue()

Gets the default initial value

protected final int

Returns:

offset to data
getLeadOffset(char
lead surrogate character
ch)

Gets the offset to the data which this lead surrogate character points to.

protected final int

Returns:

offset to the data
getRawOffset(int
index offset which ch is to start from
offset, char
index to be used after offset
ch)

Gets the offset to the data which the index ch after variable offset points to.

public int

Returns:

size size of serialized trie data file in terms of the number of bytes
getSerializedDataSize()

Gets the serialized data file size of the Trie.

protected abstract int

Returns:

offset to data
getSurrogateOffset(char
lead surrogate
lead, char
trailing surrogate
trail)

Gets the offset to the data which the surrogate pair points to.

protected abstract int

Returns:

32 bit value
getValue(int
value at index will be retrieved
index)

Gets the value at the argument index

public int
hashCode()

Overrides java.lang.Object.hashCode.

Returns a hash code value for the object.
protected final boolean

Returns:

true if this is a 16 bit trie
isCharTrie()

Determines if this is a 16 bit trie

protected final boolean

Returns:

true if options specifies this is a 32 bit trie
isIntTrie()

Determines if this is a 32 bit trie

public final boolean

Returns:

true if this trie has a linear latin 1 array, false otherwise
isLatin1Linear()

Determines if this trie has a linear latin 1 array

protected void
unserialize(ByteBuffer
buffer containing trie data
bytes)

Parses the byte buffer and creates the trie index with it.

Inherited from java.lang.Object:
clonefinalizegetClassnotifynotifyAlltoStringwaitwaitwait

Field Detail

BMP_INDEX_LENGTHback to summary
protected static final int BMP_INDEX_LENGTH

Length of the BMP portion of the index (stage 1) array.

DATA_BLOCK_LENGTHback to summary
protected static final int DATA_BLOCK_LENGTH

Number of data values in a stage 2 (data array) block.

HEADER_LENGTH_back to summary
protected static final int HEADER_LENGTH_

Size of Trie header in bytes

HEADER_OPTIONS_DATA_IS_32_BIT_back to summary
protected static final int HEADER_OPTIONS_DATA_IS_32_BIT_
HEADER_OPTIONS_INDEX_SHIFT_back to summary
protected static final int HEADER_OPTIONS_INDEX_SHIFT_
HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_back to summary
protected static final int HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_

Latin 1 option mask

HEADER_OPTIONS_SHIFT_MASK_back to summary
private static final int HEADER_OPTIONS_SHIFT_MASK_

Header option formatting

HEADER_SIGNATURE_back to summary
protected static final int HEADER_SIGNATURE_

Constant number to authenticate the byte block

INDEX_STAGE_1_SHIFT_back to summary
protected static final int INDEX_STAGE_1_SHIFT_

Shift size for shifting right the input index. 1..9

INDEX_STAGE_2_SHIFT_back to summary
protected static final int INDEX_STAGE_2_SHIFT_

Shift size for shifting left the index array values. Increases possible data size with 16-bit index values at the cost of compactability. This requires blocks of stage 2 data to be aligned by DATA_GRANULARITY. 0..INDEX_STAGE_1_SHIFT

INDEX_STAGE_3_MASK_back to summary
protected static final int INDEX_STAGE_3_MASK_

Mask for getting the lower bits from the input index. DATA_BLOCK_LENGTH - 1.

LEAD_INDEX_OFFSET_back to summary
protected static final int LEAD_INDEX_OFFSET_

Lead surrogate code points' index displacement in the index array. 0x10000-0xd800=0x2800 0x2800 >> INDEX_STAGE_1_SHIFT_

m_dataLength_back to summary
protected int m_dataLength_

Length of the data array

m_dataManipulate_back to summary
protected Trie.DataManipulate m_dataManipulate_

Internal TrieValue which handles the parsing of the data value. This class is to be implemented by the user

m_dataOffset_back to summary
protected int m_dataOffset_

Start index of the data portion of the trie. CharTrie combines index and data into a char array, so this is used to indicate the initial offset to the data portion. Note this index always points to the initial value.

m_index_back to summary
protected char[] m_index_

Index or UTF16 characters

m_isLatin1Linear_back to summary
private boolean m_isLatin1Linear_

Flag indicator for Latin quick access data block

m_options_back to summary
private int m_options_

Trie options field.

options bit field:
9 1 = Latin-1 data is stored linearly at data + DATA_BLOCK_LENGTH
8 0 = 16-bit data, 1=32-bit data
7..4 INDEX_STAGE_1_SHIFT // 0..INDEX_STAGE_2_SHIFT
3..0 INDEX_STAGE_2_SHIFT // 1..9

SURROGATE_BLOCK_BITSback to summary
protected static final int SURROGATE_BLOCK_BITS

Number of bits of a trail surrogate that are used in index table lookups.

SURROGATE_BLOCK_COUNTback to summary
protected static final int SURROGATE_BLOCK_COUNT

Number of index (stage 1) entries per lead surrogate. Same as number of index entries for 1024 trail surrogates, ==0x400>>INDEX_STAGE_1_SHIFT_

SURROGATE_MASK_back to summary
protected static final int SURROGATE_MASK_

Surrogate mask to use when shifting offset to retrieve supplementary values

Constructor Detail

Trieback to summary
protected Trie(ByteBuffer bytes, Trie.DataManipulate dataManipulate)

Trie constructor for CharTrie use.

Parameters
bytes:ByteBuffer

data of an ICU data file, containing the trie

dataManipulate:Trie.DataManipulate

object containing the information to parse the trie data

Trieback to summary
protected Trie(char[] index, int options, Trie.DataManipulate dataManipulate)

Trie constructor

Parameters
index:char[]

array to be used for index

options:int

used by the trie

dataManipulate:Trie.DataManipulate

object containing the information to parse the trie data

Method Detail

checkHeaderback to summary
private final boolean checkHeader(int signature)

Authenticates raw data header. Checking the header information, signature and options.

Parameters
signature:int

This contains the options and type of a Trie

Returns:boolean

true if the header is authenticated valid

equalsback to summary
public boolean equals(Object other)

Overrides java.lang.Object.equals.

Checks if the argument Trie has the same data as this Trie. Attributes are checked but not the index data.

Parameters
other:Object

Trie to check

Returns:boolean

true if the argument Trie has the same data as this Trie, false otherwise

Annotations
@Override
getBMPOffsetback to summary
protected final int getBMPOffset(char ch)

Gets the offset to data which the BMP character points to Treats a lead surrogate as a normal code point.

Parameters
ch:char

BMP character

Returns:int

offset to data

getCodePointOffsetback to summary
protected final int getCodePointOffset(int ch)

Internal trie getter from a code point. Could be faster(?) but longer with if((c32)<=0xd7ff) { (result)=_TRIE_GET_RAW(trie, data, 0, c32); } Gets the offset to data which the codepoint points to

Parameters
ch:int

codepoint

Returns:int

offset to data

getInitialValueback to summary
protected abstract int getInitialValue()

Gets the default initial value

Returns:int

32 bit value

getLeadOffsetback to summary
protected final int getLeadOffset(char ch)

Gets the offset to the data which this lead surrogate character points to. Data at the returned offset may contain folding offset information for the next trailing surrogate character.

Parameters
ch:char

lead surrogate character

Returns:int

offset to data

getRawOffsetback to summary
protected final int getRawOffset(int offset, char ch)

Gets the offset to the data which the index ch after variable offset points to. Note for locating a non-supplementary character data offset, calling

getRawOffset(0, ch);

will do. Otherwise if it is a supplementary character formed by surrogates lead and trail. Then we would have to call getRawOffset() with getFoldingIndexOffset(). See getSurrogateOffset().
Parameters
offset:int

index offset which ch is to start from

ch:char

index to be used after offset

Returns:int

offset to the data

getSerializedDataSizeback to summary
public int getSerializedDataSize()

Gets the serialized data file size of the Trie. This is used during trie data reading for size checking purposes.

Returns:int

size size of serialized trie data file in terms of the number of bytes

getSurrogateOffsetback to summary
protected abstract int getSurrogateOffset(char lead, char trail)

Gets the offset to the data which the surrogate pair points to.

Parameters
lead:char

lead surrogate

trail:char

trailing surrogate

Returns:int

offset to data

getValueback to summary
protected abstract int getValue(int index)

Gets the value at the argument index

Parameters
index:int

value at index will be retrieved

Returns:int

32 bit value

hashCodeback to summary
public int hashCode()

Overrides java.lang.Object.hashCode.

Doc from java.lang.Object.hashCode.

Returns a hash code value for the object. This method is supported for the benefit of hash tables such as those provided by java.util.HashMap.

The general contract of hashCode is:

  • Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
  • If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result.
  • It is not required that if two objects are unequal according to the equals method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
Returns:int

a hash code value for this object.

Annotations
@Override
isCharTrieback to summary
protected final boolean isCharTrie()

Determines if this is a 16 bit trie

Returns:boolean

true if this is a 16 bit trie

isIntTrieback to summary
protected final boolean isIntTrie()

Determines if this is a 32 bit trie

Returns:boolean

true if options specifies this is a 32 bit trie

isLatin1Linearback to summary
public final boolean isLatin1Linear()

Determines if this trie has a linear latin 1 array

Returns:boolean

true if this trie has a linear latin 1 array, false otherwise

unserializeback to summary
protected void unserialize(ByteBuffer bytes)

Parses the byte buffer and creates the trie index with it.

The position of the input ByteBuffer must be right after the trie header.

This is overwritten by the child classes.

Parameters
bytes:ByteBuffer

buffer containing trie data

com.ibm.icu.impl back to summary

public Interface Trie.DataManipulate

Known Direct Implementers
com.ibm.icu.impl.Trie.DefaultGetFoldingOffset, com.ibm.icu.impl.PropsVectors.DefaultGetFoldingOffset
Character data in com.ibm.impl.Trie have different user-specified format for different purposes. This interface specifies methods to be implemented in order for com.ibm.impl.Trie, to surrogate offset information encapsulated within the data.

Method Summary

Modifier and TypeMethod and Description
public int

Returns:

data offset or 0 if there is no data for the lead surrogate
getFoldingOffset(int
data value for a surrogate from the trie, including the folding offset
value)

Called by com.ibm.icu.impl.Trie to extract from a lead surrogate's data the index array offset of the indexes for that lead surrogate.

Method Detail

getFoldingOffsetback to summary
public int getFoldingOffset(int value)

Called by com.ibm.icu.impl.Trie to extract from a lead surrogate's data the index array offset of the indexes for that lead surrogate.

Parameters
value:int

data value for a surrogate from the trie, including the folding offset

Returns:int

data offset or 0 if there is no data for the lead surrogate

com.ibm.icu.impl back to summary

private Class Trie.DefaultGetFoldingOffset

extends Object
implements DataManipulate
Class Inheritance
All Implemented Interfaces
com.ibm.icu.impl.Trie.DataManipulate

Constructor Summary

AccessConstructor and Description
private
DefaultGetFoldingOffset()

Method Summary

Modifier and TypeMethod and Description
public int
getFoldingOffset(int
data value for a surrogate from the trie, including the folding offset
value)

Implements com.ibm.icu.impl.Trie.DataManipulate.getFoldingOffset.

Called by com.ibm.icu.impl.Trie to extract from a lead surrogate's data the index array offset of the indexes for that lead surrogate.
Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Constructor Detail

DefaultGetFoldingOffsetback to summary
private DefaultGetFoldingOffset()

Method Detail

getFoldingOffsetback to summary
public int getFoldingOffset(int value)

Implements com.ibm.icu.impl.Trie.DataManipulate.getFoldingOffset.

Doc from com.ibm.icu.impl.Trie.DataManipulate.getFoldingOffset.

Called by com.ibm.icu.impl.Trie to extract from a lead surrogate's data the index array offset of the indexes for that lead surrogate.

Parameters
value:int

data value for a surrogate from the trie, including the folding offset

Returns:int

data offset or 0 if there is no data for the lead surrogate

Annotations
@Override