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

public final Class MutableCodePointTrie

extends CodePointMap
implements Cloneable
Class Inheritance
All Implemented Interfaces
java.lang.Cloneable
Imports
java.util.Arrays

Mutable Unicode code point trie. Fast map from Unicode code points (U+0000..U+10FFFF) to 32-bit integer values. For details see https://icu.unicode.org/design/struct/utrie

Setting values (especially ranges) and lookup is fast. The mutable trie is only somewhat space-efficient. It builds a compacted, immutable CodePointTrie.

This trie can be modified while iterating over its contents. For example, it is possible to merge its values with those from another set of ranges (e.g., another @{link CodePointMap}): Iterate over those source ranges; for each of them iterate over this trie; add the source value into the value of each trie range.

ICU Status
Stable since ICU 63.

Nested and Inner Type Summary

Modifier and TypeClass and Description
private static class
private static class

Field Summary

Modifier and TypeField and Description
private static final byte
private static final int
private static final int
private static final int
private static final int
private int[]
private int
private int
private int
private byte[]
private int
private int
private static final byte
private static final byte
private static final byte
private static final byte
private static final int
private int[]
private char[]
index16

Temporary array while building the final data.

private int
private static final int
private static final int
INITIAL_DATA_LENGTH

Start with allocation of 16k data entries.

private int
private static final int
MAX_DATA_LENGTH

Maximum length of the build-time data array.

private static final int
private static final int
MEDIUM_DATA_LENGTH

Grow about 8x each time.

private static final byte
private int
private static final byte
private static final int
private static final int

Constructor Summary

AccessConstructor and Description
public
MutableCodePointTrie(int
the initial value that is set for all code points
initialValue
,
int
the value for out-of-range code points and ill-formed UTF-8/16
errorValue
)

Constructs a mutable trie that initially maps each Unicode code point to the same value.

Method Summary

Modifier and TypeMethod and Description
private int
allocDataBlock(int blockLength)

private static boolean
allValuesSameAs(int[] p, int pi, int length, int value)

private CodePointTrie
public CodePointTrie
buildImmutable(CodePointTrie.Type
selects the trie type
type
,
CodePointTrie.ValueWidth
selects the number of bits in a trie data value; if smaller than 32 bits, then the values stored in the trie will be truncated first
valueWidth
)

Compacts the data and builds an immutable CodePointTrie according to the parameters.

private void
public MutableCodePointTrie

Returns:

the clone
clone
()

Overrides java.lang.Object.clone.

Clones this mutable trie.
private int
compactData(int fastILimit, int[] newData, int dataNullIndex, MutableCodePointTrie.MixedBlocks mixedBlocks)

Compacts a build-time trie.

private int
compactIndex(int fastILimit, MutableCodePointTrie.MixedBlocks mixedBlocks)

private int
compactTrie(int fastILimit)

private int
private void
private static boolean
equalBlocks(int[] s, int si, int[] t, int ti, int length)

private static boolean
equalBlocks(char[] s, int si, int[] t, int ti, int length)

private static boolean
equalBlocks(char[] s, int si, char[] t, int ti, int length)

private void
fillBlock(int block, int start, int limit, int value)

private static int
findAllSameBlock(int[] p, int start, int limit, int value, int blockLength)

private int
findHighStart()

Finds the start of the last range in the trie by enumerating backward.

private static int
findSameBlock(char[] p, int pStart, int length, char[] q, int qStart, int blockLength)

Search for an identical block.

public static MutableCodePointTrie

Returns:

the mutable trie
fromCodePointMap
(CodePointMap
the source map or trie
map
)

Creates a mutable trie with the same contents as the CodePointMap.

public int
get(int
the code point
c
)

Implements abstract com.ibm.icu.util.CodePointMap.get.

Returns the value for a code point as stored in the map, with range checking.
private static int
getAllSameOverlap(int[] p, int length, int value, int blockLength)

private int
getDataBlock(int i)

No error checking for illegal arguments.

private static int
getOverlap(int[] p, int length, int[] q, int qStart, int blockLength)

Look for maximum overlap of the beginning of the other block with the previous, adjacent block.

private static int
getOverlap(char[] p, int length, int[] q, int qStart, int blockLength)

private static int
getOverlap(char[] p, int length, char[] q, int qStart, int blockLength)

public boolean
getRange(int
range start
start
,
CodePointMap.ValueFilter
an object that may modify the map data value, or null if the values from the map are to be used unmodified
filter
,
CodePointMap.Range
the range object that will be set to the code point range and value
range
)

Implements abstract com.ibm.icu.util.CodePointMap.getRange.

Sets the range object to a range of code points beginning with the start parameter.
private static boolean
isStartOfSomeFastBlock(int dataOffset, int[] index, int fastILimit)

private void
maskValues(int mask)

private static final int
maybeFilterValue(int value, int initialValue, int nullValue, CodePointMap.ValueFilter filter)

public void
set(int
the code point
c
,
int
the value
value
)

Sets a value for a code point.

public void
setRange(int
the first code point to get the value
start
,
int
the last code point to get the value (inclusive)
end
,
int
the value
value
)

Sets a value for each code point [start..end].

private void
writeBlock(int block, int value)

Inherited from com.ibm.icu.util.CodePointMap:
getRangeiteratorstringIterator

Field Detail

ALL_SAMEback to summary
private static final byte ALL_SAME
ASCII_I_LIMITback to summary
private static final int ASCII_I_LIMIT
ASCII_LIMITback to summary
private static final int ASCII_LIMIT
BMP_I_LIMITback to summary
private static final int BMP_I_LIMIT
BMP_LIMITback to summary
private static final int BMP_LIMIT
databack to summary
private int[] data
dataLengthback to summary
private int dataLength
dataNullOffsetback to summary
private int dataNullOffset
errorValueback to summary
private int errorValue
flagsback to summary
private byte[] flags
highStartback to summary
private int highStart
highValueback to summary
private int highValue
I3_16back to summary
private static final byte I3_16
I3_18back to summary
private static final byte I3_18
I3_BMPback to summary
private static final byte I3_BMP
I3_NULLback to summary
private static final byte I3_NULL
I_LIMITback to summary
private static final int I_LIMIT
indexback to summary
private int[] index
index16back to summary
private char[] index16

Temporary array while building the final data.

index3NullOffsetback to summary
private int index3NullOffset
INDEX_3_18BIT_BLOCK_LENGTHback to summary
private static final int INDEX_3_18BIT_BLOCK_LENGTH
INITIAL_DATA_LENGTHback to summary
private static final int INITIAL_DATA_LENGTH

Start with allocation of 16k data entries.

initialValueback to summary
private int initialValue
MAX_DATA_LENGTHback to summary
private static final int MAX_DATA_LENGTH

Maximum length of the build-time data array. One entry per 0x110000 code points.

MAX_UNICODEback to summary
private static final int MAX_UNICODE
MEDIUM_DATA_LENGTHback to summary
private static final int MEDIUM_DATA_LENGTH

Grow about 8x each time.

MIXEDback to summary
private static final byte MIXED
origInitialValueback to summary
private int origInitialValue
SAME_ASback to summary
private static final byte SAME_AS
SMALL_DATA_BLOCKS_PER_BMP_BLOCKback to summary
private static final int SMALL_DATA_BLOCKS_PER_BMP_BLOCK
UNICODE_LIMITback to summary
private static final int UNICODE_LIMIT

Constructor Detail

MutableCodePointTrieback to summary
public MutableCodePointTrie(int initialValue, int errorValue)

Constructs a mutable trie that initially maps each Unicode code point to the same value. It uses 32-bit data values until buildImmutable(com.ibm.icu.util.CodePointTrie.Type, com.ibm.icu.util.CodePointTrie.ValueWidth) is called. buildImmutable() takes a valueWidth parameter which determines the number of bits in the data value in the resulting CodePointTrie.

Parameters
initialValue:int

the initial value that is set for all code points

errorValue:int

the value for out-of-range code points and ill-formed UTF-8/16

ICU Status
Stable since ICU 63.

Method Detail

allocDataBlockback to summary
private int allocDataBlock(int blockLength)
allValuesSameAsback to summary
private static boolean allValuesSameAs(int[] p, int pi, int length, int value)
buildback to summary
private CodePointTrie build(CodePointTrie.Type type, CodePointTrie.ValueWidth valueWidth)
buildImmutableback to summary
public CodePointTrie buildImmutable(CodePointTrie.Type type, CodePointTrie.ValueWidth valueWidth)

Compacts the data and builds an immutable CodePointTrie according to the parameters. After this, the mutable trie will be empty.

The mutable trie stores 32-bit values until buildImmutable() is called. If values shorter than 32 bits are to be stored in the immutable trie, then the upper bits are discarded. For example, when the mutable trie contains values 0x81, -0x7f, and 0xa581, and the value width is 8 bits, then each of these is stored as 0x81 and the immutable trie will return that as an unsigned value. (Some implementations may want to make productive temporary use of the upper bits until buildImmutable() discards them.)

Not every possible set of mappings can be built into a CodePointTrie, because of limitations resulting from speed and space optimizations. Every Unicode assigned character can be mapped to a unique value. Typical data yields data structures far smaller than the limitations.

It is possible to construct extremely unusual mappings that exceed the data structure limits. In such a case this function will throw an exception.

Parameters
type:CodePointTrie.Type

selects the trie type

valueWidth:CodePointTrie.ValueWidth

selects the number of bits in a trie data value; if smaller than 32 bits, then the values stored in the trie will be truncated first

ICU Status
Stable since ICU 63.
See Also
fromCodePointMap(CodePointMap)
clearback to summary
private void clear()
cloneback to summary
public MutableCodePointTrie clone()

Overrides java.lang.Object.clone.

Clones this mutable trie.

Returns:MutableCodePointTrie

the clone

Annotations
@Override
ICU Status
Stable since ICU 63.
compactDataback to summary
private int compactData(int fastILimit, int[] newData, int dataNullIndex, MutableCodePointTrie.MixedBlocks mixedBlocks)

Compacts a build-time trie. The compaction - removes blocks that are identical with earlier ones - overlaps each new non-duplicate block as much as possible with the previously-written one - works with fast-range data blocks whose length is a multiple of that of higher-code-point data blocks It does not try to find an optimal order of writing, deduplicating, and overlapping blocks.

compactIndexback to summary
private int compactIndex(int fastILimit, MutableCodePointTrie.MixedBlocks mixedBlocks)
compactTrieback to summary
private int compactTrie(int fastILimit)
compactWholeDataBlocksback to summary
private int compactWholeDataBlocks(int fastILimit, MutableCodePointTrie.AllSameBlocks allSameBlocks)
ensureHighStartback to summary
private void ensureHighStart(int c)
equalBlocksback to summary
private static boolean equalBlocks(int[] s, int si, int[] t, int ti, int length)
equalBlocksback to summary
private static boolean equalBlocks(char[] s, int si, int[] t, int ti, int length)
equalBlocksback to summary
private static boolean equalBlocks(char[] s, int si, char[] t, int ti, int length)
fillBlockback to summary
private void fillBlock(int block, int start, int limit, int value)
findAllSameBlockback to summary
private static int findAllSameBlock(int[] p, int start, int limit, int value, int blockLength)
findHighStartback to summary
private int findHighStart()

Finds the start of the last range in the trie by enumerating backward. Indexes for code points higher than this will be omitted.

findSameBlockback to summary
private static int findSameBlock(char[] p, int pStart, int length, char[] q, int qStart, int blockLength)

Search for an identical block.

fromCodePointMapback to summary
public static MutableCodePointTrie fromCodePointMap(CodePointMap map)

Creates a mutable trie with the same contents as the CodePointMap.

Parameters
map:CodePointMap

the source map or trie

Returns:MutableCodePointTrie

the mutable trie

ICU Status
Stable since ICU 63.
getback to summary
public int get(int c)

Implements abstract com.ibm.icu.util.CodePointMap.get.

Doc from com.ibm.icu.util.CodePointMap.get.

Returns the value for a code point as stored in the map, with range checking. Returns an implementation-defined error value if c is not in the range 0..U+10FFFF.

Parameters
c:int

the code point

Returns:int

the map value, or an implementation-defined error value if the code point is not in the range 0..U+10FFFF

Annotations
@Override
ICU Status
Stable since ICU 63.
getAllSameOverlapback to summary
private static int getAllSameOverlap(int[] p, int length, int value, int blockLength)
getDataBlockback to summary
private int getDataBlock(int i)

No error checking for illegal arguments. The Java version always returns non-negative values.

getOverlapback to summary
private static int getOverlap(int[] p, int length, int[] q, int qStart, int blockLength)

Look for maximum overlap of the beginning of the other block with the previous, adjacent block.

getOverlapback to summary
private static int getOverlap(char[] p, int length, int[] q, int qStart, int blockLength)
getOverlapback to summary
private static int getOverlap(char[] p, int length, char[] q, int qStart, int blockLength)
getRangeback to summary
public boolean getRange(int start, CodePointMap.ValueFilter filter, CodePointMap.Range range)

Implements abstract com.ibm.icu.util.CodePointMap.getRange.

Doc from com.ibm.icu.util.CodePointMap.getRange.

Sets the range object to a range of code points beginning with the start parameter. The range start is the same as the start input parameter (even if there are preceding code points that have the same value). The range end is the last code point such that all those from start to there have the same value. Returns false if start is not 0..U+10FFFF. Can be used to efficiently iterate over all same-value ranges in a map. (This is normally faster than iterating over code points and get()ting each value, but may be much slower than a data structure that stores ranges directly.)

If the ValueFilter parameter is not null, then the value to be delivered is passed through that filter, and the return value is the end of the range where all values are modified to the same actual value. The value is unchanged if that parameter is null.

Example:

int start = 0;
CodePointMap.Range range = new CodePointMap.Range();
while (map.getRange(start, null, range)) {
    int end = range.getEnd();
    int value = range.getValue();
    // Work with the range start..end and its value.
    start = end + 1;
}

The trie can be modified between calls to this function.

Parameters
start:int

range start

filter:CodePointMap.ValueFilter

an object that may modify the map data value, or null if the values from the map are to be used unmodified

range:CodePointMap.Range

the range object that will be set to the code point range and value

Returns:boolean

true if start is 0..U+10FFFF; otherwise no new range is fetched

Annotations
@Override
ICU Status
Stable since ICU 63.
isStartOfSomeFastBlockback to summary
private static boolean isStartOfSomeFastBlock(int dataOffset, int[] index, int fastILimit)
maskValuesback to summary
private void maskValues(int mask)
maybeFilterValueback to summary
private static final int maybeFilterValue(int value, int initialValue, int nullValue, CodePointMap.ValueFilter filter)
setback to summary
public void set(int c, int value)

Sets a value for a code point.

Parameters
c:int

the code point

value:int

the value

ICU Status
Stable since ICU 63.
setRangeback to summary
public void setRange(int start, int end, int value)

Sets a value for each code point [start..end]. Faster and more space-efficient than setting the value for each code point separately.

Parameters
start:int

the first code point to get the value

end:int

the last code point to get the value (inclusive)

value:int

the value

ICU Status
Stable since ICU 63.
writeBlockback to summary
private void writeBlock(int block, int value)
com.ibm.icu.util back to summary

private final Class MutableCodePointTrie.AllSameBlocks

extends Object
Class Inheritance

Field Summary

Modifier and TypeField and Description
private static final int
private int[]
private int
private int
pack-priv static final int
pack-priv static final int
private int[]
private int[]

Constructor Summary

AccessConstructor and Description
pack-priv

Method Summary

Modifier and TypeMethod and Description
pack-priv void
add(int index, int count, int value)

Replaces the block which has the lowest reference count.

pack-priv int
pack-priv int
findOrAdd(int index, int count, int value)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

CAPACITYback to summary
private static final int CAPACITY
indexesback to summary
private int[] indexes
lengthback to summary
private int length
mostRecentback to summary
private int mostRecent
NEW_UNIQUEback to summary
pack-priv static final int NEW_UNIQUE
OVERFLOWback to summary
pack-priv static final int OVERFLOW
refCountsback to summary
private int[] refCounts
valuesback to summary
private int[] values

Constructor Detail

AllSameBlocksback to summary
pack-priv AllSameBlocks()

Method Detail

addback to summary
pack-priv void add(int index, int count, int value)

Replaces the block which has the lowest reference count.

findMostUsedback to summary
pack-priv int findMostUsed()
findOrAddback to summary
pack-priv int findOrAdd(int index, int count, int value)
com.ibm.icu.util back to summary

private final Class MutableCodePointTrie.MixedBlocks

extends Object
Class Inheritance

Field Summary

Modifier and TypeField and Description
private int
private int
private int
private int
private int[]

Constructor Summary

AccessConstructor and Description
private

Method Summary

Modifier and TypeMethod and Description
private void
addEntry(int[] data32, char[] data16, int blockStart, int hashCode, int dataIndex)

pack-priv void
extend(int[] data, int minStart, int prevDataLength, int newDataLength)

pack-priv void
extend(char[] data, int minStart, int prevDataLength, int newDataLength)

pack-priv int
findAllSameBlock(int[] data, int blockValue)

pack-priv int
findBlock(int[] data, int[] blockData, int blockStart)

pack-priv int
findBlock(char[] data, int[] blockData, int blockStart)

pack-priv int
findBlock(char[] data, char[] blockData, int blockStart)

private int
findEntry(int[] data32, char[] data16, int[] blockData32, char[] blockData16, int blockStart, int hashCode)

private int
findEntry(int[] data, int blockValue, int hashCode)

pack-priv void
init(int maxLength, int newBlockLength)

private int
makeHashCode(int[] blockData, int blockStart)

private int
makeHashCode(char[] blockData, int blockStart)

private int
makeHashCode(int blockValue)

private int
modulo(int n, int m)

Ensures non-negative n % m (that is 0..m-1).

private int
nextIndex(int initialEntryIndex, int entryIndex)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

blockLengthback to summary
private int blockLength
lengthback to summary
private int length
maskback to summary
private int mask
shiftback to summary
private int shift
tableback to summary
private int[] table

Constructor Detail

MixedBlocksback to summary
private MixedBlocks()

Method Detail

addEntryback to summary
private void addEntry(int[] data32, char[] data16, int blockStart, int hashCode, int dataIndex)
extendback to summary
pack-priv void extend(int[] data, int minStart, int prevDataLength, int newDataLength)
extendback to summary
pack-priv void extend(char[] data, int minStart, int prevDataLength, int newDataLength)
findAllSameBlockback to summary
pack-priv int findAllSameBlock(int[] data, int blockValue)
findBlockback to summary
pack-priv int findBlock(int[] data, int[] blockData, int blockStart)
findBlockback to summary
pack-priv int findBlock(char[] data, int[] blockData, int blockStart)
findBlockback to summary
pack-priv int findBlock(char[] data, char[] blockData, int blockStart)
findEntryback to summary
private int findEntry(int[] data32, char[] data16, int[] blockData32, char[] blockData16, int blockStart, int hashCode)
findEntryback to summary
private int findEntry(int[] data, int blockValue, int hashCode)
initback to summary
pack-priv void init(int maxLength, int newBlockLength)
makeHashCodeback to summary
private int makeHashCode(int[] blockData, int blockStart)
makeHashCodeback to summary
private int makeHashCode(char[] blockData, int blockStart)
makeHashCodeback to summary
private int makeHashCode(int blockValue)
moduloback to summary
private int modulo(int n, int m)

Ensures non-negative n % m (that is 0..m-1).

nextIndexback to summary
private int nextIndex(int initialEntryIndex, int entryIndex)