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.
| Modifier and Type | Class and Description |
|---|---|
| private static class | |
| private static class |
| Modifier and Type | Field 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 |
| Access | Constructor 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. |
| Modifier and Type | Method and Description |
|---|---|
| private int | |
| private static boolean | |
| private CodePointTrie | |
| public CodePointTrie | buildImmutable(CodePointTrie.
selects the trie type type,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 valueWidthCompacts the data and builds an immutable |
| private void | |
| public MutableCodePointTrie | |
| private int | compactData(int fastILimit, int[] newData, int dataNullIndex, MutableCodePointTrie.
Compacts a build-time trie. |
| private int | |
| private int | |
| private int | |
| private void | |
| private static boolean | |
| private static boolean | |
| private static boolean | |
| private void | |
| private static int | |
| private int | |
| 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 triethe source map or trie map)Creates a mutable trie with the same contents as the |
| public int | get(int
the code point c)Implements abstract com. |
| private static int | |
| private int | |
| 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 | |
| private static int | |
| public boolean | getRange(int
range start start, CodePointMap.an object that may modify the map data value,
or null if the values from the map are to be used unmodified filter,the range object that will be set to the code point range and value rangeImplements abstract com. |
| private static boolean | |
| private void | |
| private static final int | |
| public void | |
| 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 |
| ALL_SAME | back to summary |
|---|---|
| private static final byte ALL_SAME | |
| ASCII_I_LIMIT | back to summary |
|---|---|
| private static final int ASCII_I_LIMIT | |
| ASCII_LIMIT | back to summary |
|---|---|
| private static final int ASCII_LIMIT | |
| BMP_I_LIMIT | back to summary |
|---|---|
| private static final int BMP_I_LIMIT | |
| BMP_LIMIT | back to summary |
|---|---|
| private static final int BMP_LIMIT | |
| data | back to summary |
|---|---|
| private int[] data | |
| dataLength | back to summary |
|---|---|
| private int dataLength | |
| dataNullOffset | back to summary |
|---|---|
| private int dataNullOffset | |
| errorValue | back to summary |
|---|---|
| private int errorValue | |
| flags | back to summary |
|---|---|
| private byte[] flags | |
| highStart | back to summary |
|---|---|
| private int highStart | |
| highValue | back to summary |
|---|---|
| private int highValue | |
| I3_16 | back to summary |
|---|---|
| private static final byte I3_16 | |
| I3_18 | back to summary |
|---|---|
| private static final byte I3_18 | |
| I3_BMP | back to summary |
|---|---|
| private static final byte I3_BMP | |
| I3_NULL | back to summary |
|---|---|
| private static final byte I3_NULL | |
| I_LIMIT | back to summary |
|---|---|
| private static final int I_LIMIT | |
| index | back to summary |
|---|---|
| private int[] index | |
| index16 | back to summary |
|---|---|
| private char[] index16 Temporary array while building the final data. | |
| index3NullOffset | back to summary |
|---|---|
| private int index3NullOffset | |
| INDEX_3_18BIT_BLOCK_LENGTH | back to summary |
|---|---|
| private static final int INDEX_3_18BIT_BLOCK_LENGTH | |
| INITIAL_DATA_LENGTH | back to summary |
|---|---|
| private static final int INITIAL_DATA_LENGTH Start with allocation of 16k data entries. | |
| initialValue | back to summary |
|---|---|
| private int initialValue | |
| MAX_DATA_LENGTH | back to summary |
|---|---|
| private static final int MAX_DATA_LENGTH Maximum length of the build-time data array. One entry per 0x110000 code points. | |
| MAX_UNICODE | back to summary |
|---|---|
| private static final int MAX_UNICODE | |
| MEDIUM_DATA_LENGTH | back to summary |
|---|---|
| private static final int MEDIUM_DATA_LENGTH Grow about 8x each time. | |
| MIXED | back to summary |
|---|---|
| private static final byte MIXED | |
| origInitialValue | back to summary |
|---|---|
| private int origInitialValue | |
| SAME_AS | back to summary |
|---|---|
| private static final byte SAME_AS | |
| SMALL_DATA_BLOCKS_PER_BMP_BLOCK | back to summary |
|---|---|
| private static final int SMALL_DATA_BLOCKS_PER_BMP_BLOCK | |
| UNICODE_LIMIT | back to summary |
|---|---|
| private static final int UNICODE_LIMIT | |
| MutableCodePointTrie | back 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
| |
| allocDataBlock | back to summary |
|---|---|
| private int allocDataBlock(int blockLength) | |
| allValuesSameAs | back to summary |
|---|---|
| private static boolean allValuesSameAs(int[] p, int pi, int length, int value) | |
| build | back to summary |
|---|---|
| private CodePointTrie build(CodePointTrie. | |
| buildImmutable | back to summary |
|---|---|
| public CodePointTrie buildImmutable(CodePointTrie. Compacts the data and builds an immutable 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.
| |
| clear | back to summary |
|---|---|
| private void clear() | |
| clone | back to summary |
|---|---|
| public MutableCodePointTrie clone() Overrides java. Clones this mutable trie.
| |
| compactData | back to summary |
|---|---|
| private int compactData(int fastILimit, int[] newData, int dataNullIndex, MutableCodePointTrie. 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. | |
| compactIndex | back to summary |
|---|---|
| private int compactIndex(int fastILimit, MutableCodePointTrie. | |
| compactTrie | back to summary |
|---|---|
| private int compactTrie(int fastILimit) | |
| compactWholeDataBlocks | back to summary |
|---|---|
| private int compactWholeDataBlocks(int fastILimit, MutableCodePointTrie. | |
| ensureHighStart | back to summary |
|---|---|
| private void ensureHighStart(int c) | |
| equalBlocks | back to summary |
|---|---|
| private static boolean equalBlocks(int[] s, int si, int[] t, int ti, int length) | |
| equalBlocks | back to summary |
|---|---|
| private static boolean equalBlocks(char[] s, int si, int[] t, int ti, int length) | |
| equalBlocks | back to summary |
|---|---|
| private static boolean equalBlocks(char[] s, int si, char[] t, int ti, int length) | |
| fillBlock | back to summary |
|---|---|
| private void fillBlock(int block, int start, int limit, int value) | |
| findAllSameBlock | back to summary |
|---|---|
| private static int findAllSameBlock(int[] p, int start, int limit, int value, int blockLength) | |
| findHighStart | back 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. | |
| findSameBlock | back to summary |
|---|---|
| private static int findSameBlock(char[] p, int pStart, int length, char[] q, int qStart, int blockLength) Search for an identical block. | |
| fromCodePointMap | back to summary |
|---|---|
| public static MutableCodePointTrie fromCodePointMap(CodePointMap map) Creates a mutable trie with the same contents as the
| |
| get | back to summary |
|---|---|
| public int get(int c) Implements abstract com. Doc from com. 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. | |
| getAllSameOverlap | back to summary |
|---|---|
| private static int getAllSameOverlap(int[] p, int length, int value, int blockLength) | |
| getDataBlock | back to summary |
|---|---|
| private int getDataBlock(int i) No error checking for illegal arguments. The Java version always returns non-negative values. | |
| getOverlap | back 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. | |
| getOverlap | back to summary |
|---|---|
| private static int getOverlap(char[] p, int length, int[] q, int qStart, int blockLength) | |
| getOverlap | back to summary |
|---|---|
| private static int getOverlap(char[] p, int length, char[] q, int qStart, int blockLength) | |
| getRange | back to summary |
|---|---|
| public boolean getRange(int start, CodePointMap. Implements abstract com. Doc from com. 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 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.
| |
| isStartOfSomeFastBlock | back to summary |
|---|---|
| private static boolean isStartOfSomeFastBlock(int dataOffset, int[] index, int fastILimit) | |
| maskValues | back to summary |
|---|---|
| private void maskValues(int mask) | |
| maybeFilterValue | back to summary |
|---|---|
| private static final int maybeFilterValue(int value, int initialValue, int nullValue, CodePointMap. | |
| set | back to summary |
|---|---|
| public void set(int c, int value) Sets a value for a code point.
| |
| setRange | back 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.
| |
| writeBlock | back to summary |
|---|---|
| private void writeBlock(int block, int value) | |
| Modifier and Type | Field 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[] |
| Access | Constructor and Description |
|---|---|
| pack-priv |
| Modifier and Type | Method and Description |
|---|---|
| pack-priv void | |
| pack-priv int | |
| pack-priv int |
| CAPACITY | back to summary |
|---|---|
| private static final int CAPACITY | |
| indexes | back to summary |
|---|---|
| private int[] indexes | |
| length | back to summary |
|---|---|
| private int length | |
| mostRecent | back to summary |
|---|---|
| private int mostRecent | |
| NEW_UNIQUE | back to summary |
|---|---|
| pack-priv static final int NEW_UNIQUE | |
| OVERFLOW | back to summary |
|---|---|
| pack-priv static final int OVERFLOW | |
| refCounts | back to summary |
|---|---|
| private int[] refCounts | |
| values | back to summary |
|---|---|
| private int[] values | |
| AllSameBlocks | back to summary |
|---|---|
| pack-priv AllSameBlocks() | |
| add | back to summary |
|---|---|
| pack-priv void add(int index, int count, int value) Replaces the block which has the lowest reference count. | |
| findMostUsed | back to summary |
|---|---|
| pack-priv int findMostUsed() | |
| findOrAdd | back to summary |
|---|---|
| pack-priv int findOrAdd(int index, int count, int value) | |
| Modifier and Type | Field and Description |
|---|---|
| private int | |
| private int | |
| private int | |
| private int | |
| private int[] |
| Access | Constructor and Description |
|---|---|
| private |
| Modifier and Type | Method and Description |
|---|---|
| private void | |
| pack-priv void | |
| pack-priv void | |
| pack-priv int | |
| pack-priv int | |
| pack-priv int | |
| pack-priv int | |
| private int | findEntry(int[] data32, char[] data16, int[] blockData32, char[] blockData16, int blockStart, int hashCode)
|
| private int | |
| pack-priv void | |
| private int | |
| private int | |
| private int | |
| private int | |
| private int |
| blockLength | back to summary |
|---|---|
| private int blockLength | |
| length | back to summary |
|---|---|
| private int length | |
| mask | back to summary |
|---|---|
| private int mask | |
| shift | back to summary |
|---|---|
| private int shift | |
| table | back to summary |
|---|---|
| private int[] table | |
| MixedBlocks | back to summary |
|---|---|
| private MixedBlocks() | |
| addEntry | back to summary |
|---|---|
| private void addEntry(int[] data32, char[] data16, int blockStart, int hashCode, int dataIndex) | |
| extend | back to summary |
|---|---|
| pack-priv void extend(int[] data, int minStart, int prevDataLength, int newDataLength) | |
| extend | back to summary |
|---|---|
| pack-priv void extend(char[] data, int minStart, int prevDataLength, int newDataLength) | |
| findAllSameBlock | back to summary |
|---|---|
| pack-priv int findAllSameBlock(int[] data, int blockValue) | |
| findBlock | back to summary |
|---|---|
| pack-priv int findBlock(int[] data, int[] blockData, int blockStart) | |
| findBlock | back to summary |
|---|---|
| pack-priv int findBlock(char[] data, int[] blockData, int blockStart) | |
| findBlock | back to summary |
|---|---|
| pack-priv int findBlock(char[] data, char[] blockData, int blockStart) | |
| findEntry | back to summary |
|---|---|
| private int findEntry(int[] data32, char[] data16, int[] blockData32, char[] blockData16, int blockStart, int hashCode) | |
| findEntry | back to summary |
|---|---|
| private int findEntry(int[] data, int blockValue, int hashCode) | |
| init | back to summary |
|---|---|
| pack-priv void init(int maxLength, int newBlockLength) | |
| makeHashCode | back to summary |
|---|---|
| private int makeHashCode(int[] blockData, int blockStart) | |
| makeHashCode | back to summary |
|---|---|
| private int makeHashCode(char[] blockData, int blockStart) | |
| makeHashCode | back to summary |
|---|---|
| private int makeHashCode(int blockValue) | |
| modulo | back to summary |
|---|---|
| private int modulo(int n, int m) Ensures non-negative n % m (that is 0..m-1). | |
| nextIndex | back to summary |
|---|---|
| private int nextIndex(int initialEntryIndex, int entryIndex) | |