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

public Class TrieBuilder

extends Object
Class Inheritance
Known Direct Subclasses
com.ibm.icu.impl.IntTrieBuilder
Imports
java.util.Arrays, com.ibm.icu.lang.UCharacter
Builder class to manipulate and generate a trie. This is useful for ICU data in primitive types. Provides a compact way to store information that is indexed by Unicode values, such as character properties, types, keyboard values, etc. This is very useful when you have a block of Unicode data that contains significant values while the rest of the Unicode data is unused in the application or when you have a lot of redundance, such as where all 21,000 Han ideographs have the same value. However, lookup is much faster than a hash table. A trie of any primitive data type serves two purposes: This is a direct port from the ICU4C version
Author
Syn Wee Quek

Nested and Inner Type Summary

Modifier and TypeClass and Description
public static interface
TrieBuilder.DataManipulate

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

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.

public static final int
DATA_BLOCK_LENGTH

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

protected static final int
DATA_GRANULARITY_

The alignment size of a stage 2 data block.

protected static final int
INDEX_SHIFT_

Shift size for shifting left the index array values.

protected int
m_dataCapacity_

protected int
m_dataLength_

protected int[]
m_index_

Index values at build-time are 32 bits wide for easier processing.

protected int
m_indexLength_

protected boolean
m_isCompacted_

protected boolean
m_isLatin1Linear_

protected int[]
m_map_

Map of adjusted indexes, used in utrie_compact().

protected static final int
MASK_

Mask for getting the lower bits from the input index.

private static final int
MAX_BUILD_TIME_DATA_LENGTH_

Maximum length of the build-time data (stage 2) array.

protected static final int
MAX_DATA_LENGTH_

Maximum length of the runtime data (stage 2) array.

protected static final int
MAX_INDEX_LENGTH_

Length of the index (stage 1) array before folding.

protected static final int
OPTIONS_DATA_IS_32_BIT_

If set, then the data (stage 2) array is 32 bits wide.

protected static final int
OPTIONS_INDEX_SHIFT_

Shifting to position the index value in options

protected static final int
OPTIONS_LATIN1_IS_LINEAR_

If set, then Latin-1 data (for U+0000..U+00ff) is stored in the data (stage 2) array as a simple, linear array at data + DATA_BLOCK_LENGTH.

protected static final int
SHIFT_

Shift size for shifting right the input index.

protected static final int
SURROGATE_BLOCK_COUNT_

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

Constructor Summary

AccessConstructor and Description
protected
TrieBuilder()

protected
TrieBuilder(TrieBuilder table)

Method Summary

Modifier and TypeMethod and Description
protected static final boolean
equal_int(int[] array, int start1, int start2, int length)

Compare two sections of an array for equality.

protected static final int

Returns:

same index block
findSameIndexBlock(int[]
array
index, int
size of index
indexLength, int otherBlock)

Finds the same index block as the otherBlock

protected void
findUnusedBlocks()

Set a value in the trie index map to indicate which data block is referenced and which one is not.

public boolean

Returns:

true if ch is in the zero block
isInZeroBlock(int
codepoint which data is to be retrieved
ch)

Checks if the character belongs to a zero block in the trie

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

BMP_INDEX_LENGTH_back 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
public static final int DATA_BLOCK_LENGTH

Number of data values in a stage 2 (data array) block. 2, 4, 8, .., 0x200

DATA_GRANULARITY_back to summary
protected static final int DATA_GRANULARITY_

The alignment size of a stage 2 data block. Also the granularity for compaction.

INDEX_SHIFT_back to summary
protected static final int INDEX_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 UTRIE_DATA_GRANULARITY. 0..UTRIE_SHIFT

m_dataCapacity_back to summary
protected int m_dataCapacity_
m_dataLength_back to summary
protected int m_dataLength_
m_index_back to summary
protected int[] m_index_

Index values at build-time are 32 bits wide for easier processing. Bit 31 is set if the data block is used by multiple index values (from setRange()).

m_indexLength_back to summary
protected int m_indexLength_
m_isCompacted_back to summary
protected boolean m_isCompacted_
m_isLatin1Linear_back to summary
protected boolean m_isLatin1Linear_
m_map_back to summary
protected int[] m_map_

Map of adjusted indexes, used in utrie_compact(). Maps from original indexes to new ones.

MASK_back to summary
protected static final int MASK_

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

MAX_BUILD_TIME_DATA_LENGTH_back to summary
private static final int MAX_BUILD_TIME_DATA_LENGTH_

Maximum length of the build-time data (stage 2) array. The maximum length is 0x110000 + DATA_BLOCK_LENGTH + 0x400. (Number of Unicode code points + one all-initial-value block + possible duplicate entries for 1024 lead surrogates.)

MAX_DATA_LENGTH_back to summary
protected static final int MAX_DATA_LENGTH_

Maximum length of the runtime data (stage 2) array. Limited by 16-bit index values that are left-shifted by INDEX_SHIFT_.

MAX_INDEX_LENGTH_back to summary
protected static final int MAX_INDEX_LENGTH_

Length of the index (stage 1) array before folding. Maximum number of Unicode code points (0x110000) shifted right by SHIFT.

OPTIONS_DATA_IS_32_BIT_back to summary
protected static final int OPTIONS_DATA_IS_32_BIT_

If set, then the data (stage 2) array is 32 bits wide.

OPTIONS_INDEX_SHIFT_back to summary
protected static final int OPTIONS_INDEX_SHIFT_

Shifting to position the index value in options

OPTIONS_LATIN1_IS_LINEAR_back to summary
protected static final int OPTIONS_LATIN1_IS_LINEAR_

If set, then Latin-1 data (for U+0000..U+00ff) is stored in the data (stage 2) array as a simple, linear array at data + DATA_BLOCK_LENGTH.

SHIFT_back to summary
protected static final int SHIFT_

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

SURROGATE_BLOCK_COUNT_back to summary
protected static final int SURROGATE_BLOCK_COUNT_

Number of index (stage 1) entries per lead surrogate. Same as number of indexe entries for 1024 trail surrogates, ==0x400>>UTRIE_SHIFT 10 - SHIFT == Number of bits of a trail surrogate that are used in index table lookups.

Constructor Detail

TrieBuilderback to summary
protected TrieBuilder()
TrieBuilderback to summary
protected TrieBuilder(TrieBuilder table)

Method Detail

equal_intback to summary
protected static final boolean equal_int(int[] array, int start1, int start2, int length)

Compare two sections of an array for equality.

findSameIndexBlockback to summary
protected static final int findSameIndexBlock(int[] index, int indexLength, int otherBlock)

Finds the same index block as the otherBlock

Parameters
index:int[]

array

indexLength:int

size of index

Returns:int

same index block

findUnusedBlocksback to summary
protected void findUnusedBlocks()

Set a value in the trie index map to indicate which data block is referenced and which one is not. utrie_compact() will remove data blocks that are not used at all. Set - 0 if it is used - -1 if it is not used

isInZeroBlockback to summary
public boolean isInZeroBlock(int ch)

Checks if the character belongs to a zero block in the trie

Parameters
ch:int

codepoint which data is to be retrieved

Returns:boolean

true if ch is in the zero block

com.ibm.icu.impl back to summary

public Interface TrieBuilder.DataManipulate

Known Direct Implementers
com.ibm.icu.impl.PropsVectors.DefaultGetFoldedValue
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:

a folded value, or 0 if there is no relevant data for the lead surrogate.
getFoldedValue(int start, int offset)

Build-time trie callback function, used with serialize().

Method Detail

getFoldedValueback to summary
public int getFoldedValue(int start, int offset)

Build-time trie callback function, used with serialize(). This function calculates a lead surrogate's value including a folding offset from the 1024 supplementary code points [start..start+1024[ . It is U+10000 <= start <= U+10fc00 and (start&0x3ff)==0. The folding offset is provided by the caller. It is offset=UTRIE_BMP_INDEX_LENGTH+n*UTRIE_SURROGATE_BLOCK_COUNT with n=0..1023. Instead of the offset itself, n can be stored in 10 bits - or fewer if it can be assumed that few lead surrogates have associated data. The returned value must be - not zero if and only if there is relevant data for the corresponding 1024 supplementary code points - such that UTrie.getFoldingOffset(UNewTrieGetFoldedValue(..., offset))==offset

Returns:int

a folded value, or 0 if there is no relevant data for the lead surrogate.