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.

Nested and Inner Type Summary

Modifier and Type	Class 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 Type	Field and Description
protected static final int	DATA_BLOCK_LENGTH Number of data values in a stage 2 (data array) block.
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_MASK_ Surrogate mask to use when shifting offset to retrieve supplementary values

Constructor Summary

Access	Constructor and Description
protected	Trie(InputStream ICU data file input stream which contains the trie inputStream, Trie.DataManipulate object containing the information to parse the trie data dataManipulate) Trie constructor for CharTrie use.

Method Summary

Modifier and Type	Method 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.
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 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.
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 final boolean	Returns: true if this is a 16 bit trie isCharTrie() Determines if this is a 16 bit trie
protected void	unserialize(InputStream input stream containing the trie information inputStream) Parses the inputstream and creates the trie index with it.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

DATA_BLOCK_LENGTH	back to summary
protected static final int DATA_BLOCK_LENGTH Number of data values in a stage 2 (data array) block.

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

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_`

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

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_MASK_	back to summary
protected static final int SURROGATE_MASK_ Surrogate mask to use when shifting offset to retrieve supplementary values

Constructor Detail

Trie	back to summary
protected Trie(InputStream inputStream, Trie.DataManipulate dataManipulate) throws IOException Trie constructor for CharTrie use. Parameters inputStream:InputStream ICU data file input stream which contains the trie dataManipulate:Trie.DataManipulate object containing the information to parse the trie data Exceptions IOException: thrown when input stream does not have the right header.

Trie

back to summary

protected Trie(InputStream inputStream, Trie.DataManipulate dataManipulate) throws IOException

Trie constructor for CharTrie use.

Parameters

inputStream:InputStream: ICU data file input stream which contains the trie
dataManipulate:Trie.DataManipulate: object containing the information to parse the trie data

Exceptions

IOException:: thrown when input stream does not have the right header.

Method Detail

checkHeader	back 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

checkHeader

back 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

getBMPOffset	back 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

getBMPOffset

back 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

getCodePointOffset back to summary

getCodePointOffset	back 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

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

getLeadOffset	back 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

getLeadOffset

back 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

getRawOffset	back 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

getRawOffset

back 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

getSurrogateOffset	back 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

getSurrogateOffset

back 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

isCharTrie	back to summary
protected final boolean isCharTrie() Determines if this is a 16 bit trie Returns:boolean true if this is a 16 bit trie

isCharTrie

back to summary

protected final boolean isCharTrie()

Determines if this is a 16 bit trie

Returns:boolean: true if this is a 16 bit trie

unserialize	back to summary
protected void unserialize(InputStream inputStream) throws IOException Parses the inputstream and creates the trie index with it. This is overwritten by the child classes. Parameters inputStream:InputStream input stream containing the trie information Exceptions IOException: thrown when data reading fails.

unserialize

back to summary

protected void unserialize(InputStream inputStream) throws IOException

Parses the inputstream and creates the trie index with it.

This is overwritten by the child classes.

Parameters

inputStream:InputStream: input stream containing the trie information

Exceptions

IOException:: thrown when data reading fails.

jdk.internal.icu.impl back to summary

public Interface Trie.DataManipulate

Known Direct Implementers: jdk.internal.icu.impl.Trie.DefaultGetFoldingOffset, jdk.internal.icu.text.StringPrep.StringPrepTrieImpl

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 Type	Method 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

getFoldingOffset	back 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

getFoldingOffset

back 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

jdk.internal.icu.impl back to summary

private Class Trie.DefaultGetFoldingOffset

Class Inheritance

extends Object
implements DataManipulate

java.lang.Object
jdk.internal.icu.impl.Trie.DefaultGetFoldingOffset

All Implemented Interfaces

jdk.internal.icu.impl.Trie.DataManipulate

Constructor Summary

Access	Constructor and Description
private	DefaultGetFoldingOffset()

Method Summary

Modifier and Type	Method and Description
public int	getFoldingOffset(int value) Implements jdk.internal.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:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Constructor Detail

DefaultGetFoldingOffset	back to summary
private DefaultGetFoldingOffset()

Method Detail

getFoldingOffset	back to summary
public int getFoldingOffset(int value) Implements jdk.internal.icu.impl.Trie.DataManipulate.getFoldingOffset. Doc from jdk.internal.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.

getFoldingOffset

back to summary

public int getFoldingOffset(int value)

Implements jdk.internal.icu.impl.Trie.DataManipulate.getFoldingOffset.

Doc from jdk.internal.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.

public abstract Class Trie

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

public Interface Trie.DataManipulate

Method Summary

Method Detail

private Class Trie.DefaultGetFoldingOffset

Constructor Summary

Method Summary

Constructor Detail

Method Detail