xref: /external/icu/icu4j/main/classes/core/src/com/ibm/icu/util/CharsTrie.java

/*
*******************************************************************************
*   Copyright (C) 2011-2014, International Business Machines
*   Corporation and others.  All Rights Reserved.
*******************************************************************************
*   created on: 2011jan06
*   created by: Markus W. Scherer
*   ported from ICU4C ucharstrie.h/.cpp
*/

package com.ibm.icu.util;

import java.io.IOException;
import java.util.ArrayList;
import java.util.NoSuchElementException;

import com.ibm.icu.text.UTF16;
import com.ibm.icu.util.BytesTrie.Result;

/**
 * Light-weight, non-const reader class for a CharsTrie.
 * Traverses a char-serialized data structure with minimal state,
 * for mapping strings (16-bit-unit sequences) to non-negative integer values.
 *
 * <p>This class is not intended for public subclassing.
 *
 * @stable ICU 4.8
 * @author Markus W. Scherer
 */
public final class CharsTrie implements Cloneable, Iterable<CharsTrie.Entry> {
    /**
     * Constructs a CharsTrie reader instance.
     *
     * <p>The CharSequence must contain a copy of a char sequence from the CharsTrieBuilder,
     * with the offset indicating the first char of that sequence.
     * The CharsTrie object will not read more chars than
     * the CharsTrieBuilder generated in the corresponding build() call.
     *
     * <p>The CharSequence is not copied/cloned and must not be modified while
     * the CharsTrie object is in use.
     *
     * @param trieChars CharSequence that contains the serialized trie.
     * @param offset Root offset of the trie in the CharSequence.
     * @stable ICU 4.8
     */
    public CharsTrie(CharSequence trieChars, int offset) {
        chars_=trieChars;
        pos_=root_=offset;
        remainingMatchLength_=-1;
    }

    /**
     * Clones this trie reader object and its state,
     * but not the char array which will be shared.
     * @return A shallow clone of this trie.
     * @stable ICU 4.8
     */
    @Override
    public Object clone() throws CloneNotSupportedException {
        return super.clone();  // A shallow copy is just what we need.
    }

    /**
     * Resets this trie to its initial state.
     * @return this
     * @stable ICU 4.8
     */
    public CharsTrie reset() {
        pos_=root_;
        remainingMatchLength_=-1;
        return this;
    }

    /**
     * CharsTrie state object, for saving a trie's current state
     * and resetting the trie back to this state later.
     * @stable ICU 4.8
     */
    public static final class State {
        /**
         * Constructs an empty State.
         * @stable ICU 4.8
         */
        public State() {}
        private CharSequence chars;
        private int root;
        private int pos;
        private int remainingMatchLength;
    }

    /**
     * Saves the state of this trie.
     * @param state The State object to hold the trie's state.
     * @return this
     * @see #resetToState
     * @stable ICU 4.8
     */
    public CharsTrie saveState(State state) /*const*/ {
        state.chars=chars_;
        state.root=root_;
        state.pos=pos_;
        state.remainingMatchLength=remainingMatchLength_;
        return this;
    }

    /**
     * Resets this trie to the saved state.
     * @param state The State object which holds a saved trie state.
     * @return this
     * @throws IllegalArgumentException if the state object contains no state,
     *         or the state of a different trie
     * @see #saveState
     * @see #reset
     * @stable ICU 4.8
     */
    public CharsTrie resetToState(State state) {
        if(chars_==state.chars && chars_!=null && root_==state.root) {
            pos_=state.pos;
            remainingMatchLength_=state.remainingMatchLength;
        } else {
            throw new IllegalArgumentException("incompatible trie state");
        }
        return this;
    }

    /**
     * Determines whether the string so far matches, whether it has a value,
     * and whether another input char can continue a matching string.
     * @return The match/value Result.
     * @stable ICU 4.8
     */
    public Result current() /*const*/ {
        int pos=pos_;
        if(pos<0) {
            return Result.NO_MATCH;
        } else {
            int node;
            return (remainingMatchLength_<0 && (node=chars_.charAt(pos))>=kMinValueLead) ?
                    valueResults_[node>>15] : Result.NO_VALUE;
        }
    }

    /**
     * Traverses the trie from the initial state for this input char.
     * Equivalent to reset().next(inUnit).
     * @param inUnit Input char value. Values below 0 and above 0xffff will never match.
     * @return The match/value Result.
     * @stable ICU 4.8
     */
    public Result first(int inUnit) {
        remainingMatchLength_=-1;
        return nextImpl(root_, inUnit);
    }

    /**
     * Traverses the trie from the initial state for the
     * one or two UTF-16 code units for this input code point.
     * Equivalent to reset().nextForCodePoint(cp).
     * @param cp A Unicode code point 0..0x10ffff.
     * @return The match/value Result.
     * @stable ICU 4.8
     */
    public Result firstForCodePoint(int cp) {
        return cp<=0xffff ?
            first(cp) :
            (first(UTF16.getLeadSurrogate(cp)).hasNext() ?
                next(UTF16.getTrailSurrogate(cp)) :
                Result.NO_MATCH);
    }

    /**
     * Traverses the trie from the current state for this input char.
     * @param inUnit Input char value. Values below 0 and above 0xffff will never match.
     * @return The match/value Result.
     * @stable ICU 4.8
     */
    public Result next(int inUnit) {
        int pos=pos_;
        if(pos<0) {
            return Result.NO_MATCH;
        }
        int length=remainingMatchLength_;  // Actual remaining match length minus 1.
        if(length>=0) {
            // Remaining part of a linear-match node.
            if(inUnit==chars_.charAt(pos++)) {
                remainingMatchLength_=--length;
                pos_=pos;
                int node;
                return (length<0 && (node=chars_.charAt(pos))>=kMinValueLead) ?
                        valueResults_[node>>15] : Result.NO_VALUE;
            } else {
                stop();
                return Result.NO_MATCH;
            }
        }
        return nextImpl(pos, inUnit);
    }

    /**
     * Traverses the trie from the current state for the
     * one or two UTF-16 code units for this input code point.
     * @param cp A Unicode code point 0..0x10ffff.
     * @return The match/value Result.
     * @stable ICU 4.8
     */
    public Result nextForCodePoint(int cp) {
        return cp<=0xffff ?
            next(cp) :
            (next(UTF16.getLeadSurrogate(cp)).hasNext() ?
                next(UTF16.getTrailSurrogate(cp)) :
                Result.NO_MATCH);
    }

    /**
     * Traverses the trie from the current state for this string.
     * Equivalent to
     * <pre>
     * Result result=current();
     * for(each c in s)
     *   if(!result.hasNext()) return Result.NO_MATCH;
     *   result=next(c);
     * return result;
     * </pre>
     * @param s Contains a string.
     * @param sIndex The start index of the string in s.
     * @param sLimit The (exclusive) end index of the string in s.
     * @return The match/value Result.
     * @stable ICU 4.8
     */
    public Result next(CharSequence s, int sIndex, int sLimit) {
        if(sIndex>=sLimit) {
            // Empty input.
            return current();
        }
        int pos=pos_;
        if(pos<0) {
            return Result.NO_MATCH;
        }
        int length=remainingMatchLength_;  // Actual remaining match length minus 1.
        for(;;) {
            // Fetch the next input unit, if there is one.
            // Continue a linear-match node.
            char inUnit;
            for(;;) {
                if(sIndex==sLimit) {
                    remainingMatchLength_=length;
                    pos_=pos;
                    int node;
                    return (length<0 && (node=chars_.charAt(pos))>=kMinValueLead) ?
                            valueResults_[node>>15] : Result.NO_VALUE;
                }
                inUnit=s.charAt(sIndex++);
                if(length<0) {
                    remainingMatchLength_=length;
                    break;
                }
                if(inUnit!=chars_.charAt(pos)) {
                    stop();
                    return Result.NO_MATCH;
                }
                ++pos;
                --length;
            }
            int node=chars_.charAt(pos++);
            for(;;) {
                if(node<kMinLinearMatch) {
                    Result result=branchNext(pos, node, inUnit);
                    if(result==Result.NO_MATCH) {
                        return Result.NO_MATCH;
                    }
                    // Fetch the next input unit, if there is one.
                    if(sIndex==sLimit) {
                        return result;
                    }
                    if(result==Result.FINAL_VALUE) {
                        // No further matching units.
                        stop();
                        return Result.NO_MATCH;
                    }
                    inUnit=s.charAt(sIndex++);
                    pos=pos_;  // branchNext() advanced pos and wrote it to pos_ .
                    node=chars_.charAt(pos++);
                } else if(node<kMinValueLead) {
                    // Match length+1 units.
                    length=node-kMinLinearMatch;  // Actual match length minus 1.
                    if(inUnit!=chars_.charAt(pos)) {
                        stop();
                        return Result.NO_MATCH;
                    }
                    ++pos;
                    --length;
                    break;
                } else if((node&kValueIsFinal)!=0) {
                    // No further matching units.
                    stop();
                    return Result.NO_MATCH;
                } else {
                    // Skip intermediate value.
                    pos=skipNodeValue(pos, node);
                    node&=kNodeTypeMask;
                }
            }
        }
    }

    /**
     * Returns a matching string's value if called immediately after
     * current()/first()/next() returned Result.INTERMEDIATE_VALUE or Result.FINAL_VALUE.
     * getValue() can be called multiple times.
     *
     * Do not call getValue() after Result.NO_MATCH or Result.NO_VALUE!
     * @return The value for the string so far.
     * @stable ICU 4.8
     */
    public int getValue() /*const*/ {
        int pos=pos_;
        int leadUnit=chars_.charAt(pos++);
        assert(leadUnit>=kMinValueLead);
        return (leadUnit&kValueIsFinal)!=0 ?
            readValue(chars_, pos, leadUnit&0x7fff) : readNodeValue(chars_, pos, leadUnit);
    }

    /**
     * Determines whether all strings reachable from the current state
     * map to the same value, and if so, returns that value.
     * @return The unique value in bits 32..1 with bit 0 set,
     *         if all strings reachable from the current state
     *         map to the same value; otherwise returns 0.
     * @stable ICU 4.8
     */
    public long getUniqueValue() /*const*/ {
        int pos=pos_;
        if(pos<0) {
            return 0;
        }
        // Skip the rest of a pending linear-match node.
        long uniqueValue=findUniqueValue(chars_, pos+remainingMatchLength_+1, 0);
        // Ignore internally used bits 63..33; extend the actual value's sign bit from bit 32.
        return (uniqueValue<<31)>>31;
    }

    /**
     * Finds each char which continues the string from the current state.
     * That is, each char c for which it would be next(c)!=Result.NO_MATCH now.
     * @param out Each next char is appended to this object.
     *            (Only uses the out.append(c) method.)
     * @return The number of chars which continue the string from here.
     * @stable ICU 4.8
     */
    public int getNextChars(Appendable out) /*const*/ {
        int pos=pos_;
        if(pos<0) {
            return 0;
        }
        if(remainingMatchLength_>=0) {
            append(out, chars_.charAt(pos));  // Next unit of a pending linear-match node.
            return 1;
        }
        int node=chars_.charAt(pos++);
        if(node>=kMinValueLead) {
            if((node&kValueIsFinal)!=0) {
                return 0;
            } else {
                pos=skipNodeValue(pos, node);
                node&=kNodeTypeMask;
            }
        }
        if(node<kMinLinearMatch) {
            if(node==0) {
                node=chars_.charAt(pos++);
            }
            getNextBranchChars(chars_, pos, ++node, out);
            return node;
        } else {
            // First unit of the linear-match node.
            append(out, chars_.charAt(pos));
            return 1;
        }
    }

    /**
     * Iterates from the current state of this trie.
     * @return A new CharsTrie.Iterator.
     * @stable ICU 4.8
     */
    public Iterator iterator() {
        return new Iterator(chars_, pos_, remainingMatchLength_, 0);
    }

    /**
     * Iterates from the current state of this trie.
     * @param maxStringLength If 0, the iterator returns full strings.
     *                        Otherwise, the iterator returns strings with this maximum length.
     * @return A new CharsTrie.Iterator.
     * @stable ICU 4.8
     */
    public Iterator iterator(int maxStringLength) {
        return new Iterator(chars_, pos_, remainingMatchLength_, maxStringLength);
    }

    /**
     * Iterates from the root of a char-serialized BytesTrie.
     * @param trieChars CharSequence that contains the serialized trie.
     * @param offset Root offset of the trie in the CharSequence.
     * @param maxStringLength If 0, the iterator returns full strings.
     *                        Otherwise, the iterator returns strings with this maximum length.
     * @return A new CharsTrie.Iterator.
     * @stable ICU 4.8
     */
    public static Iterator iterator(CharSequence trieChars, int offset, int maxStringLength) {
        return new Iterator(trieChars, offset, -1, maxStringLength);
    }

    /**
     * Return value type for the Iterator.
     * @stable ICU 4.8
     */
    public static final class Entry {
        /**
         * The string.
         * @stable ICU 4.8
         */
        public CharSequence chars;
        /**
         * The value associated with the string.
         * @stable ICU 4.8
         */
        public int value;

        private Entry() {
        }
    }

    /**
     * Iterator for all of the (string, value) pairs in a CharsTrie.
     * @stable ICU 4.8
     */
    public static final class Iterator implements java.util.Iterator<Entry> {
        private Iterator(CharSequence trieChars, int offset, int remainingMatchLength, int maxStringLength) {
            chars_=trieChars;
            pos_=initialPos_=offset;
            remainingMatchLength_=initialRemainingMatchLength_=remainingMatchLength;
            maxLength_=maxStringLength;
            int length=remainingMatchLength_;  // Actual remaining match length minus 1.
            if(length>=0) {
                // Pending linear-match node, append remaining bytes to str_.
                ++length;
                if(maxLength_>0 && length>maxLength_) {
                    length=maxLength_;  // This will leave remainingMatchLength>=0 as a signal.
                }
                str_.append(chars_, pos_, pos_+length);
                pos_+=length;
                remainingMatchLength_-=length;
            }
        }

        /**
         * Resets this iterator to its initial state.
         * @return this
         * @stable ICU 4.8
         */
        public Iterator reset() {
            pos_=initialPos_;
            remainingMatchLength_=initialRemainingMatchLength_;
            skipValue_=false;
            int length=remainingMatchLength_+1;  // Remaining match length.
            if(maxLength_>0 && length>maxLength_) {
                length=maxLength_;
            }
            str_.setLength(length);
            pos_+=length;
            remainingMatchLength_-=length;
            stack_.clear();
            return this;
        }

        /**
         * @return true if there are more elements.
         * @stable ICU 4.8
         */
        public boolean hasNext() /*const*/ { return pos_>=0 || !stack_.isEmpty(); }

        /**
         * Finds the next (string, value) pair if there is one.
         *
         * If the string is truncated to the maximum length and does not
         * have a real value, then the value is set to -1.
         * In this case, this "not a real value" is indistinguishable from
         * a real value of -1.
         * @return An Entry with the string and value of the next element.
         * @throws NoSuchElementException - iteration has no more elements.
         * @stable ICU 4.8
         */
        public Entry next() {
            int pos=pos_;
            if(pos<0) {
                if(stack_.isEmpty()) {
                    throw new NoSuchElementException();
                }
                // Pop the state off the stack and continue with the next outbound edge of
                // the branch node.
                long top=stack_.remove(stack_.size()-1);
                int length=(int)top;
                pos=(int)(top>>32);
                str_.setLength(length&0xffff);
                length>>>=16;
                if(length>1) {
                    pos=branchNext(pos, length);
                    if(pos<0) {
                        return entry_;  // Reached a final value.
                    }
                } else {
                    str_.append(chars_.charAt(pos++));
                }
            }
            if(remainingMatchLength_>=0) {
                // We only get here if we started in a pending linear-match node
                // with more than maxLength remaining units.
                return truncateAndStop();
            }
            for(;;) {
                int node=chars_.charAt(pos++);
                if(node>=kMinValueLead) {
                    if(skipValue_) {
                        pos=skipNodeValue(pos, node);
                        node&=kNodeTypeMask;
                        skipValue_=false;
                    } else {
                        // Deliver value for the string so far.
                        boolean isFinal=(node&kValueIsFinal)!=0;
                        if(isFinal) {
                            entry_.value=readValue(chars_, pos, node&0x7fff);
                        } else {
                            entry_.value=readNodeValue(chars_, pos, node);
                        }
                        if(isFinal || (maxLength_>0 && str_.length()==maxLength_)) {
                            pos_=-1;
                        } else {
                            // We cannot skip the value right here because it shares its
                            // lead unit with a match node which we have to evaluate
                            // next time.
                            // Instead, keep pos_ on the node lead unit itself.
                            pos_=pos-1;
                            skipValue_=true;
                        }
                        entry_.chars=str_;
                        return entry_;
                    }
                }
                if(maxLength_>0 && str_.length()==maxLength_) {
                    return truncateAndStop();
                }
                if(node<kMinLinearMatch) {
                    if(node==0) {
                        node=chars_.charAt(pos++);
                    }
                    pos=branchNext(pos, node+1);
                    if(pos<0) {
                        return entry_;  // Reached a final value.
                    }
                } else {
                    // Linear-match node, append length units to str_.
                    int length=node-kMinLinearMatch+1;
                    if(maxLength_>0 && str_.length()+length>maxLength_) {
                        str_.append(chars_, pos, pos+maxLength_-str_.length());
                        return truncateAndStop();
                    }
                    str_.append(chars_, pos, pos+length);
                    pos+=length;
                }
            }
        }

        /**
         * Iterator.remove() is not supported.
         * @throws UnsupportedOperationException (always)
         * @stable ICU 4.8
         */
        public void remove() {
            throw new UnsupportedOperationException();
        }

        private Entry truncateAndStop() {
            pos_=-1;
            // We reset entry_.chars every time we return entry_
            // just because the caller might have modified the Entry.
            entry_.chars=str_;
            entry_.value=-1;  // no real value for str
            return entry_;
        }

        private int branchNext(int pos, int length) {
            while(length>kMaxBranchLinearSubNodeLength) {
                ++pos;  // ignore the comparison unit
                // Push state for the greater-or-equal edge.
                stack_.add(((long)skipDelta(chars_, pos)<<32)|((length-(length>>1))<<16)|str_.length());
                // Follow the less-than edge.
                length>>=1;
                pos=jumpByDelta(chars_, pos);
            }
            // List of key-value pairs where values are either final values or jump deltas.
            // Read the first (key, value) pair.
            char trieUnit=chars_.charAt(pos++);
            int node=chars_.charAt(pos++);
            boolean isFinal=(node&kValueIsFinal)!=0;
            int value=readValue(chars_, pos, node&=0x7fff);
            pos=skipValue(pos, node);
            stack_.add(((long)pos<<32)|((length-1)<<16)|str_.length());
            str_.append(trieUnit);
            if(isFinal) {
                pos_=-1;
                entry_.chars=str_;
                entry_.value=value;
                return -1;
            } else {
                return pos+value;
            }
        }

        private CharSequence chars_;
        private int pos_;
        private int initialPos_;
        private int remainingMatchLength_;
        private int initialRemainingMatchLength_;
        private boolean skipValue_;  // Skip intermediate value which was already delivered.

        private StringBuilder str_=new StringBuilder();
        private int maxLength_;
        private Entry entry_=new Entry();

        // The stack stores longs for backtracking to another
        // outbound edge of a branch node.
        // Each long has the offset in chars_ in bits 62..32,
        // the str_.length() from before the node in bits 15..0,
        // and the remaining branch length in bits 31..16.
        // (We could store the remaining branch length minus 1 in bits 30..16 and not use bit 31,
        // but the code looks more confusing that way.)
        private ArrayList<Long> stack_=new ArrayList<Long>();
    }

    private void stop() {
        pos_=-1;
    }

    // Reads a compact 32-bit integer.
    // pos is already after the leadUnit, and the lead unit has bit 15 reset.
    private static int readValue(CharSequence chars, int pos, int leadUnit) {
        int value;
        if(leadUnit<kMinTwoUnitValueLead) {
            value=leadUnit;
        } else if(leadUnit<kThreeUnitValueLead) {
            value=((leadUnit-kMinTwoUnitValueLead)<<16)|chars.charAt(pos);
        } else {
            value=(chars.charAt(pos)<<16)|chars.charAt(pos+1);
        }
        return value;
    }
    private static int skipValue(int pos, int leadUnit) {
        if(leadUnit>=kMinTwoUnitValueLead) {
            if(leadUnit<kThreeUnitValueLead) {
                ++pos;
            } else {
                pos+=2;
            }
        }
        return pos;
    }
    private static int skipValue(CharSequence chars, int pos) {
        int leadUnit=chars.charAt(pos++);
        return skipValue(pos, leadUnit&0x7fff);
    }

    private static int readNodeValue(CharSequence chars, int pos, int leadUnit) {
        assert(kMinValueLead<=leadUnit && leadUnit<kValueIsFinal);
        int value;
        if(leadUnit<kMinTwoUnitNodeValueLead) {
            value=(leadUnit>>6)-1;
        } else if(leadUnit<kThreeUnitNodeValueLead) {
            value=(((leadUnit&0x7fc0)-kMinTwoUnitNodeValueLead)<<10)|chars.charAt(pos);
        } else {
            value=(chars.charAt(pos)<<16)|chars.charAt(pos+1);
        }
        return value;
    }
    private static int skipNodeValue(int pos, int leadUnit) {
        assert(kMinValueLead<=leadUnit && leadUnit<kValueIsFinal);
        if(leadUnit>=kMinTwoUnitNodeValueLead) {
            if(leadUnit<kThreeUnitNodeValueLead) {
                ++pos;
            } else {
                pos+=2;
            }
        }
        return pos;
    }

    private static int jumpByDelta(CharSequence chars, int pos) {
        int delta=chars.charAt(pos++);
        if(delta>=kMinTwoUnitDeltaLead) {
            if(delta==kThreeUnitDeltaLead) {
                delta=(chars.charAt(pos)<<16)|chars.charAt(pos+1);
                pos+=2;
            } else {
                delta=((delta-kMinTwoUnitDeltaLead)<<16)|chars.charAt(pos++);
            }
        }
        return pos+delta;
    }

    private static int skipDelta(CharSequence chars, int pos) {
        int delta=chars.charAt(pos++);
        if(delta>=kMinTwoUnitDeltaLead) {
            if(delta==kThreeUnitDeltaLead) {
                pos+=2;
            } else {
                ++pos;
            }
        }
        return pos;
    }

    private static Result[] valueResults_={ Result.INTERMEDIATE_VALUE, Result.FINAL_VALUE };

    // Handles a branch node for both next(unit) and next(string).
    private Result branchNext(int pos, int length, int inUnit) {
        // Branch according to the current unit.
        if(length==0) {
            length=chars_.charAt(pos++);
        }
        ++length;
        // The length of the branch is the number of units to select from.
        // The data structure encodes a binary search.
        while(length>kMaxBranchLinearSubNodeLength) {
            if(inUnit<chars_.charAt(pos++)) {
                length>>=1;
                pos=jumpByDelta(chars_, pos);
            } else {
                length=length-(length>>1);
                pos=skipDelta(chars_, pos);
            }
        }
        // Drop down to linear search for the last few units.
        // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3
        // and divides length by 2.
        do {
            if(inUnit==chars_.charAt(pos++)) {
                Result result;
                int node=chars_.charAt(pos);
                if((node&kValueIsFinal)!=0) {
                    // Leave the final value for getValue() to read.
                    result=Result.FINAL_VALUE;
                } else {
                    // Use the non-final value as the jump delta.
                    ++pos;
                    // int delta=readValue(pos, node);
                    int delta;
                    if(node<kMinTwoUnitValueLead) {
                        delta=node;
                    } else if(node<kThreeUnitValueLead) {
                        delta=((node-kMinTwoUnitValueLead)<<16)|chars_.charAt(pos++);
                    } else {
                        delta=(chars_.charAt(pos)<<16)|chars_.charAt(pos+1);
                        pos+=2;
                    }
                    // end readValue()
                    pos+=delta;
                    node=chars_.charAt(pos);
                    result= node>=kMinValueLead ? valueResults_[node>>15] : Result.NO_VALUE;
                }
                pos_=pos;
                return result;
            }
            --length;
            pos=skipValue(chars_, pos);
        } while(length>1);
        if(inUnit==chars_.charAt(pos++)) {
            pos_=pos;
            int node=chars_.charAt(pos);
            return node>=kMinValueLead ? valueResults_[node>>15] : Result.NO_VALUE;
        } else {
            stop();
            return Result.NO_MATCH;
        }
    }

    // Requires remainingLength_<0.
    private Result nextImpl(int pos, int inUnit) {
        int node=chars_.charAt(pos++);
        for(;;) {
            if(node<kMinLinearMatch) {
                return branchNext(pos, node, inUnit);
            } else if(node<kMinValueLead) {
                // Match the first of length+1 units.
                int length=node-kMinLinearMatch;  // Actual match length minus 1.
                if(inUnit==chars_.charAt(pos++)) {
                    remainingMatchLength_=--length;
                    pos_=pos;
                    return (length<0 && (node=chars_.charAt(pos))>=kMinValueLead) ?
                            valueResults_[node>>15] : Result.NO_VALUE;
                } else {
                    // No match.
                    break;
                }
            } else if((node&kValueIsFinal)!=0) {
                // No further matching units.
                break;
            } else {
                // Skip intermediate value.
                pos=skipNodeValue(pos, node);
                node&=kNodeTypeMask;
            }
        }
        stop();
        return Result.NO_MATCH;
    }

    // Helper functions for getUniqueValue().
    // Recursively finds a unique value (or whether there is not a unique one)
    // from a branch.
    // uniqueValue: On input, same as for getUniqueValue()/findUniqueValue().
    // On return, if not 0, then bits 63..33 contain the updated non-negative pos.
    private static long findUniqueValueFromBranch(CharSequence chars, int pos, int length,
                                                  long uniqueValue) {
        while(length>kMaxBranchLinearSubNodeLength) {
            ++pos;  // ignore the comparison unit
            uniqueValue=findUniqueValueFromBranch(chars, jumpByDelta(chars, pos), length>>1, uniqueValue);
            if(uniqueValue==0) {
                return 0;
            }
            length=length-(length>>1);
            pos=skipDelta(chars, pos);
        }
        do {
            ++pos;  // ignore a comparison unit
            // handle its value
            int node=chars.charAt(pos++);
            boolean isFinal=(node&kValueIsFinal)!=0;
            node&=0x7fff;
            int value=readValue(chars, pos, node);
            pos=skipValue(pos, node);
            if(isFinal) {
                if(uniqueValue!=0) {
                    if(value!=(int)(uniqueValue>>1)) {
                        return 0;
                    }
                } else {
                    uniqueValue=((long)value<<1)|1;
                }
            } else {
                uniqueValue=findUniqueValue(chars, pos+value, uniqueValue);
                if(uniqueValue==0) {
                    return 0;
                }
            }
        } while(--length>1);
        // ignore the last comparison byte
        return ((long)(pos+1)<<33)|(uniqueValue&0x1ffffffffL);
    }
    // Recursively finds a unique value (or whether there is not a unique one)
    // starting from a position on a node lead unit.
    // uniqueValue: If there is one, then bits 32..1 contain the value and bit 0 is set.
    // Otherwise, uniqueValue is 0. Bits 63..33 are ignored.
    private static long findUniqueValue(CharSequence chars, int pos, long uniqueValue) {
        int node=chars.charAt(pos++);
        for(;;) {
            if(node<kMinLinearMatch) {
                if(node==0) {
                    node=chars.charAt(pos++);
                }
                uniqueValue=findUniqueValueFromBranch(chars, pos, node+1, uniqueValue);
                if(uniqueValue==0) {
                    return 0;
                }
                pos=(int)(uniqueValue>>>33);
                node=chars.charAt(pos++);
            } else if(node<kMinValueLead) {
                // linear-match node
                pos+=node-kMinLinearMatch+1;  // Ignore the match units.
                node=chars.charAt(pos++);
            } else {
                boolean isFinal=(node&kValueIsFinal)!=0;
                int value;
                if(isFinal) {
                    value=readValue(chars, pos, node&0x7fff);
                } else {
                    value=readNodeValue(chars, pos, node);
                }
                if(uniqueValue!=0) {
                    if(value!=(int)(uniqueValue>>1)) {
                        return 0;
                    }
                } else {
                    uniqueValue=((long)value<<1)|1;
                }
                if(isFinal) {
                    return uniqueValue;
                }
                pos=skipNodeValue(pos, node);
                node&=kNodeTypeMask;
            }
        }
    }

    // Helper functions for getNextChars().
    // getNextChars() when pos is on a branch node.
    private static void getNextBranchChars(CharSequence chars, int pos, int length, Appendable out) {
        while(length>kMaxBranchLinearSubNodeLength) {
            ++pos;  // ignore the comparison unit
            getNextBranchChars(chars, jumpByDelta(chars, pos), length>>1, out);
            length=length-(length>>1);
            pos=skipDelta(chars, pos);
        }
        do {
            append(out, chars.charAt(pos++));
            pos=skipValue(chars, pos);
        } while(--length>1);
        append(out, chars.charAt(pos));
    }
    private static void append(Appendable out, int c) {
        try {
            out.append((char)c);
        } catch(IOException e) {
            throw new ICUUncheckedIOException(e);
        }
    }

    // CharsTrie data structure
    //
    // The trie consists of a series of char-serialized nodes for incremental
    // Unicode string/char sequence matching. (char=16-bit unsigned integer)
    // The root node is at the beginning of the trie data.
    //
    // Types of nodes are distinguished by their node lead unit ranges.
    // After each node, except a final-value node, another node follows to
    // encode match values or continue matching further units.
    //
    // Node types:
    //  - Final-value node: Stores a 32-bit integer in a compact, variable-length format.
    //    The value is for the string/char sequence so far.
    //  - Match node, optionally with an intermediate value in a different compact format.
    //    The value, if present, is for the string/char sequence so far.
    //
    //  Aside from the value, which uses the node lead unit's high bits:
    //
    //  - Linear-match node: Matches a number of units.
    //  - Branch node: Branches to other nodes according to the current input unit.
    //    The node unit is the length of the branch (number of units to select from)
    //    minus 1. It is followed by a sub-node:
    //    - If the length is at most kMaxBranchLinearSubNodeLength, then
    //      there are length-1 (key, value) pairs and then one more comparison unit.
    //      If one of the key units matches, then the value is either a final value for
    //      the string so far, or a "jump" delta to the next node.
    //      If the last unit matches, then matching continues with the next node.
    //      (Values have the same encoding as final-value nodes.)
    //    - If the length is greater than kMaxBranchLinearSubNodeLength, then
    //      there is one unit and one "jump" delta.
    //      If the input unit is less than the sub-node unit, then "jump" by delta to
    //      the next sub-node which will have a length of length/2.
    //      (The delta has its own compact encoding.)
    //      Otherwise, skip the "jump" delta to the next sub-node
    //      which will have a length of length-length/2.

    // Match-node lead unit values, after masking off intermediate-value bits:

    // 0000..002f: Branch node. If node!=0 then the length is node+1, otherwise
    // the length is one more than the next unit.

    // For a branch sub-node with at most this many entries, we drop down
    // to a linear search.
    /*package*/ static final int kMaxBranchLinearSubNodeLength=5;

    // 0030..003f: Linear-match node, match 1..16 units and continue reading the next node.
    /*package*/ static final int kMinLinearMatch=0x30;
    /*package*/ static final int kMaxLinearMatchLength=0x10;

    // Match-node lead unit bits 14..6 for the optional intermediate value.
    // If these bits are 0, then there is no intermediate value.
    // Otherwise, see the *NodeValue* constants below.
    /*package*/ static final int kMinValueLead=kMinLinearMatch+kMaxLinearMatchLength;  // 0x0040
    /*package*/ static final int kNodeTypeMask=kMinValueLead-1;  // 0x003f

    // A final-value node has bit 15 set.
    /*package*/ static final int kValueIsFinal=0x8000;

    // Compact value: After testing and masking off bit 15, use the following thresholds.
    /*package*/ static final int kMaxOneUnitValue=0x3fff;

    /*package*/ static final int kMinTwoUnitValueLead=kMaxOneUnitValue+1;  // 0x4000
    /*package*/ static final int kThreeUnitValueLead=0x7fff;

    /*package*/ static final int kMaxTwoUnitValue=((kThreeUnitValueLead-kMinTwoUnitValueLead)<<16)-1;  // 0x3ffeffff

    // Compact intermediate-value integer, lead unit shared with a branch or linear-match node.
    /*package*/ static final int kMaxOneUnitNodeValue=0xff;
    /*package*/ static final int kMinTwoUnitNodeValueLead=kMinValueLead+((kMaxOneUnitNodeValue+1)<<6);  // 0x4040
    /*package*/ static final int kThreeUnitNodeValueLead=0x7fc0;

    /*package*/ static final int kMaxTwoUnitNodeValue=
        ((kThreeUnitNodeValueLead-kMinTwoUnitNodeValueLead)<<10)-1;  // 0xfdffff

    // Compact delta integers.
    /*package*/ static final int kMaxOneUnitDelta=0xfbff;
    /*package*/ static final int kMinTwoUnitDeltaLead=kMaxOneUnitDelta+1;  // 0xfc00
    /*package*/ static final int kThreeUnitDeltaLead=0xffff;

    /*package*/ static final int kMaxTwoUnitDelta=((kThreeUnitDeltaLead-kMinTwoUnitDeltaLead)<<16)-1;  // 0x03feffff

    // Fixed value referencing the CharsTrie words.
    private CharSequence chars_;
    private int root_;

    // Iterator variables.

    // Pointer to next trie unit to read. NULL if no more matches.
    private int pos_;
    // Remaining length of a linear-match node, minus 1. Negative if not in such a node.
    private int remainingMatchLength_;
}