International Components for Unicode for Java (icu4j) 74.2 · com.ibm.icu.impl.TrieIterator

Class enabling iteration of the values in a Trie.

2015-sep-03 TODO: Only used in test code, move there.

Result of each iteration contains the interval of codepoints that have the same value type and the value type itself.

The comparison of each codepoint value is done via extract(), which the default implementation is to return the value as it is.

Method extract() can be overwritten to perform manipulations on codepoint values in order to perform specialized comparison.

TrieIterator is designed to be a generic iterator for the CharTrie and the IntTrie, hence to accommodate both types of data, the return result will be in terms of int (32 bit) values.

See com.ibm.icu.text.UCharacterTypeIterator for examples of use.

Notes

for porting utrie_enum from icu4c to icu4j:
Internally, icu4c's utrie_enum performs all iterations in its body. In Java sense, the caller will have to pass a object with a callback function UTrieEnumRange(const void *context, UChar32 start, UChar32 limit, uint32_t value) into utrie_enum. utrie_enum will then find ranges of codepoints with the same value as determined by UTrieEnumValue(const void *context, uint32_t value). for each range, utrie_enum calls the callback function to perform a task. In this way, icu4c performs the iteration within utrie_enum. To follow the JDK model, icu4j is slightly different from icu4c. Instead of requesting the caller to implement an object for a callback. The caller will have to implement a subclass of TrieIterator, fleshing out the method extract(int) (equivalent to UTrieEnumValue). Independent of icu4j, the caller will have to code his own iteration and flesh out the task (equivalent to UTrieEnumRange) to be performed in the iteration loop.

There are basically 3 usage scenarios for porting:

1) UTrieEnumValue is the only implemented callback then just implement a subclass of TrieIterator and override the extract(int) method. The extract(int) method is analogous to UTrieEnumValue callback.

2) UTrieEnumValue and UTrieEnumRange both are implemented then implement a subclass of TrieIterator, override the extract method and iterate, e.g

utrie_enum(&normTrie, _enumPropertyStartsValue, _enumPropertyStartsRange, set);
In Java :

class TrieIteratorImpl extends TrieIterator{
    public TrieIteratorImpl(Trie data){
        super(data);
    }
    public int extract(int value){
        // port the implementation of _enumPropertyStartsValue here
    }
}
....
TrieIterator fcdIter  = new TrieIteratorImpl(fcdTrieImpl.fcdTrie);
while(fcdIter.next(result)) {
    // port the implementation of _enumPropertyStartsRange
}

3) UTrieEnumRange is the only implemented callback then just implement the while loop, when utrie_enum is called

// utrie_enum(&fcdTrie, NULL, _enumPropertyStartsRange, set);
TrieIterator fcdIter  = new TrieIterator(fcdTrieImpl.fcdTrie);
while(fcdIter.next(result)){
    set.add(result.start);
}

Field Summary

Modifier and Type	Field and Description
private static final int	BMP_INDEX_LENGTH_ Size of the stage 1 BMP indexes
private static final int	DATA_BLOCK_LENGTH_ Number of data values in a stage 2 (data array) block.
private static final int	LEAD_SURROGATE_MIN_VALUE_ Lead surrogate minimum value
private int	m_currentCodepoint_ Next element results and data.
private int	m_initialValue_ Initial value for trie values
private int	m_nextBlock_
private int	m_nextBlockIndex_
private int	m_nextCodepoint_
private int	m_nextIndex_
private int	m_nextTrailIndexOffset_
private int	m_nextValue_
private Trie	m_trie_ Trie instance
private static final int	TRAIL_SURROGATE_COUNT_ Number of trail surrogate
private static final int	TRAIL_SURROGATE_INDEX_BLOCK_LENGTH_ Number of stage 1 indexes for supplementary calculations that maps to each lead surrogate character.
private static final int	TRAIL_SURROGATE_MIN_VALUE_ Trail surrogate minimum value

Constructor Summary

Access	Constructor and Description
public	TrieIterator(Trie to be used trie) TrieEnumeration constructor

Method Summary

Modifier and Type	Method and Description
private final boolean	Returns: true if the next range is found, false if we have to proceed to the supplementary range. calculateNextBMPElement(RangeValueIterator.Element return result object element) Finding the next element.
private final void	calculateNextSupplementaryElement(RangeValueIterator.Element return result object element) Finds the next supplementary element.
private final boolean	Returns: true if the whole block has the same value as currentValue or if the whole block has been calculated, false otherwise. checkBlock(int the value which other codepoints are tested against currentValue) Internal block value calculations Performs calculations on a data block to find codepoints in m_nextBlock_ that has the same value.
private final boolean	Returns: true if the whole block has the same value as currentValue or if the whole block has been calculated, false otherwise. checkBlockDetail(int the value which other codepoints are tested against currentValue) Internal block value calculations Performs calculations on a data block to find codepoints in m_nextBlock_ after the index m_nextBlockIndex_ that has the same value.
private final boolean	Returns: true if we are at the start of a initial block. checkNullNextTrailIndex() Checks if we are beginning at the start of a initial block.
private final boolean	Returns: true if the whole block has the same value as currentValue or if the whole block has been calculated, false otherwise. checkTrailBlock(int the value which other codepoints are tested against currentValue) Internal block value calculations Performs calculations on multiple data blocks for a set of trail surrogates to find codepoints in m_nextBlock_ that has the same value.
protected int	Returns: extracted value extract(int a value from the trie value) Called by next() to extracts a 32 bit value from a trie value used for comparison.
public final boolean	Returns: true if we are not at the end of the iteration, false otherwise. next(RangeValueIterator.Element return result element) Implements com.ibm.icu.util.RangeValueIterator.next. Returns true if we are not at the end of the iteration, false otherwise.
public final void	reset() Implements com.ibm.icu.util.RangeValueIterator.reset. Resets the iterator to the beginning of the iteration
private final void	setResult(RangeValueIterator.Element return result object element, int codepoint of range start, int (end + 1) codepoint of range limit, int common value of range value) Set the result values

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

Field Detail

BMP_INDEX_LENGTH_	back to summary
private static final int BMP_INDEX_LENGTH_ Size of the stage 1 BMP indexes

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

LEAD_SURROGATE_MIN_VALUE_	back to summary
private static final int LEAD_SURROGATE_MIN_VALUE_ Lead surrogate minimum value

m_currentCodepoint_	back to summary
private int m_currentCodepoint_ Next element results and data.

m_initialValue_	back to summary
private int m_initialValue_ Initial value for trie values

m_nextBlock_	back to summary
private int m_nextBlock_

m_nextBlockIndex_	back to summary
private int m_nextBlockIndex_

m_nextCodepoint_	back to summary
private int m_nextCodepoint_

m_nextIndex_	back to summary
private int m_nextIndex_

m_nextTrailIndexOffset_	back to summary
private int m_nextTrailIndexOffset_

m_nextValue_	back to summary
private int m_nextValue_

m_trie_	back to summary
private Trie m_trie_ Trie instance

TRAIL_SURROGATE_COUNT_	back to summary
private static final int TRAIL_SURROGATE_COUNT_ Number of trail surrogate

TRAIL_SURROGATE_INDEX_BLOCK_LENGTH_	back to summary
private static final int TRAIL_SURROGATE_INDEX_BLOCK_LENGTH_ Number of stage 1 indexes for supplementary calculations that maps to each lead surrogate character. See second pass into getRawOffset for the trail surrogate character. 10 for significant number of bits for trail surrogates, 5 for what we discard during shifting.

TRAIL_SURROGATE_MIN_VALUE_	back to summary
private static final int TRAIL_SURROGATE_MIN_VALUE_ Trail surrogate minimum value

Constructor Detail

TrieIterator	back to summary
public TrieIterator(Trie trie) TrieEnumeration constructor Parameters trie:Trie to be used Exceptions IllegalArgumentException: throw when argument is null.

TrieIterator

back to summary

public TrieIterator(Trie trie)

TrieEnumeration constructor

Parameters

trie:Trie: to be used

Exceptions

IllegalArgumentException:: throw when argument is null.

Method Detail

calculateNextBMPElement	back to summary
private final boolean calculateNextBMPElement(RangeValueIterator.Element element) Finding the next element. This method is called just before returning the result of next(). We always store the next element before it is requested. In the case that we have to continue calculations into the supplementary planes, a false will be returned. Parameters element:RangeValueIterator.Element return result object Returns:boolean true if the next range is found, false if we have to proceed to the supplementary range.

calculateNextBMPElement

back to summary

private final boolean calculateNextBMPElement(RangeValueIterator.Element element)

Finding the next element. This method is called just before returning the result of next(). We always store the next element before it is requested. In the case that we have to continue calculations into the supplementary planes, a false will be returned.

Parameters

element:RangeValueIterator.Element: return result object

Returns:boolean

true if the next range is found, false if we have to proceed to the supplementary range.

calculateNextSupplementaryElement	back to summary
private final void calculateNextSupplementaryElement(RangeValueIterator.Element element) Finds the next supplementary element. For each entry in the trie, the value to be delivered is passed through extract(). We always store the next element before it is requested. Called after calculateNextBMP() completes its round of BMP characters. There is a slight difference in the usage of m_currentCodepoint_ here as compared to calculateNextBMP(). Though both represents the lower bound of the next element, in calculateNextBMP() it gets set at the start of any loop, where-else, in calculateNextSupplementary() since m_currentCodepoint_ already contains the lower bound of the next element (passed down from calculateNextBMP()), we keep it till the end before resetting it to the new value. Note, if there are no more iterations, it will never get to here. Blocked out by next(). Parameters element:RangeValueIterator.Element return result object

calculateNextSupplementaryElement

back to summary

private final void calculateNextSupplementaryElement(RangeValueIterator.Element element)

Finds the next supplementary element. For each entry in the trie, the value to be delivered is passed through extract(). We always store the next element before it is requested. Called after calculateNextBMP() completes its round of BMP characters. There is a slight difference in the usage of m_currentCodepoint_ here as compared to calculateNextBMP(). Though both represents the lower bound of the next element, in calculateNextBMP() it gets set at the start of any loop, where-else, in calculateNextSupplementary() since m_currentCodepoint_ already contains the lower bound of the next element (passed down from calculateNextBMP()), we keep it till the end before resetting it to the new value. Note, if there are no more iterations, it will never get to here. Blocked out by next().

Parameters

element:RangeValueIterator.Element: return result object

checkBlock	back to summary
private final boolean checkBlock(int currentValue) Internal block value calculations Performs calculations on a data block to find codepoints in m_nextBlock_ that has the same value. Will call checkBlockDetail() if highlevel check fails. Note m_*_ variables at this point is the next codepoint whose value has not been calculated. Parameters currentValue:int the value which other codepoints are tested against Returns:boolean true if the whole block has the same value as currentValue or if the whole block has been calculated, false otherwise.

checkBlock

back to summary

private final boolean checkBlock(int currentValue)

Internal block value calculations Performs calculations on a data block to find codepoints in m_nextBlock_ that has the same value. Will call checkBlockDetail() if highlevel check fails. Note m_*_ variables at this point is the next codepoint whose value has not been calculated.

Parameters

currentValue:int: the value which other codepoints are tested against

Returns:boolean

true if the whole block has the same value as currentValue or if the whole block has been calculated, false otherwise.

checkBlockDetail	back to summary
private final boolean checkBlockDetail(int currentValue) Internal block value calculations Performs calculations on a data block to find codepoints in m_nextBlock_ after the index m_nextBlockIndex_ that has the same value. Note m_*_ variables at this point is the next codepoint whose value has not been calculated. But when returned with false, it will be the last codepoint whose value has been calculated. Parameters currentValue:int the value which other codepoints are tested against Returns:boolean true if the whole block has the same value as currentValue or if the whole block has been calculated, false otherwise.

checkBlockDetail

back to summary

private final boolean checkBlockDetail(int currentValue)

Internal block value calculations Performs calculations on a data block to find codepoints in m_nextBlock_ after the index m_nextBlockIndex_ that has the same value. Note m_*_ variables at this point is the next codepoint whose value has not been calculated. But when returned with false, it will be the last codepoint whose value has been calculated.

Parameters

currentValue:int: the value which other codepoints are tested against

Returns:boolean

true if the whole block has the same value as currentValue or if the whole block has been calculated, false otherwise.

checkNullNextTrailIndex	back to summary
private final boolean checkNullNextTrailIndex() Checks if we are beginning at the start of a initial block. If we are then the rest of the codepoints in this initial block has the same values. We increment m_nextCodepoint_ and relevant data members if so. This is used only in for the supplementary codepoints because the offset to the trail indexes could be 0. Returns:boolean true if we are at the start of a initial block.

checkNullNextTrailIndex

back to summary

private final boolean checkNullNextTrailIndex()

Checks if we are beginning at the start of a initial block. If we are then the rest of the codepoints in this initial block has the same values. We increment m_nextCodepoint_ and relevant data members if so. This is used only in for the supplementary codepoints because the offset to the trail indexes could be 0.

Returns:boolean: true if we are at the start of a initial block.

checkTrailBlock	back to summary
private final boolean checkTrailBlock(int currentValue) Internal block value calculations Performs calculations on multiple data blocks for a set of trail surrogates to find codepoints in m_nextBlock_ that has the same value. Will call checkBlock() for internal block checks. Note m_*_ variables at this point is the next codepoint whose value has not been calculated. Parameters currentValue:int the value which other codepoints are tested against Returns:boolean true if the whole block has the same value as currentValue or if the whole block has been calculated, false otherwise.

checkTrailBlock

back to summary

private final boolean checkTrailBlock(int currentValue)

Internal block value calculations Performs calculations on multiple data blocks for a set of trail surrogates to find codepoints in m_nextBlock_ that has the same value. Will call checkBlock() for internal block checks. Note m_*_ variables at this point is the next codepoint whose value has not been calculated.

Parameters

currentValue:int: the value which other codepoints are tested against

Returns:boolean

true if the whole block has the same value as currentValue or if the whole block has been calculated, false otherwise.

extract	back to summary
protected int extract(int value) Called by next() to extracts a 32 bit value from a trie value used for comparison. This method is to be overwritten if special manipulation is to be done to retrieve a relevant comparison. The default function is to return the value as it is. Parameters value:int a value from the trie Returns:int extracted value

extract

back to summary

protected int extract(int value)

Called by next() to extracts a 32 bit value from a trie value used for comparison. This method is to be overwritten if special manipulation is to be done to retrieve a relevant comparison. The default function is to return the value as it is.

Parameters

value:int: a value from the trie

Returns:int

extracted value

next back to summary

next	back to summary
public final boolean next(RangeValueIterator.Element element) Implements com.ibm.icu.util.RangeValueIterator.next. Returns true if we are not at the end of the iteration, false otherwise. The next set of codepoints with the same value type will be calculated during this call and returned in the argument element. Parameters element:RangeValueIterator.Element return result Returns:boolean true if we are not at the end of the iteration, false otherwise. Annotations @Override Exceptions NoSuchElementException: - if no more elements exist. See Also `com.ibm.icu.util.RangeValueIterator.Element`

public final boolean next(RangeValueIterator.Element element)

Implements com.ibm.icu.util.RangeValueIterator.next.

Returns true if we are not at the end of the iteration, false otherwise.

The next set of codepoints with the same value type will be calculated during this call and returned in the argument element.

Parameters

element:RangeValueIterator.Element: return result

Returns:boolean

true if we are not at the end of the iteration, false otherwise.

Annotations

@Override

Exceptions

NoSuchElementException:: - if no more elements exist.

reset	back to summary
public final void reset() Implements com.ibm.icu.util.RangeValueIterator.reset. Resets the iterator to the beginning of the iteration Annotations @Override

reset

back to summary

public final void reset()

Implements com.ibm.icu.util.RangeValueIterator.reset.

Resets the iterator to the beginning of the iteration

Annotations

@Override

setResult	back to summary
private final void setResult(RangeValueIterator.Element element, int start, int limit, int value) Set the result values Parameters element:RangeValueIterator.Element return result object start:int codepoint of range limit:int (end + 1) codepoint of range value:int common value of range

setResult

back to summary

private final void setResult(RangeValueIterator.Element element, int start, int limit, int value)

Set the result values

Parameters

element:RangeValueIterator.Element: return result object
start:int: codepoint of range
limit:int: (end + 1) codepoint of range
value:int: common value of range

public Class TrieIterator

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail