| /* |
| ******************************************************************************* |
| * Copyright (C) 2010-2014, International Business Machines |
| * Corporation and others. All Rights Reserved. |
| ******************************************************************************* |
| * created on: 2010nov23 |
| * created by: Markus W. Scherer |
| * ported from ICU4C bytestrie.h/.cpp |
| */ |
| package com.ibm.icu.util; |
| |
| import java.io.IOException; |
| import java.nio.ByteBuffer; |
| import java.util.ArrayList; |
| import java.util.NoSuchElementException; |
| |
| /** |
| * Light-weight, non-const reader class for a BytesTrie. |
| * Traverses a byte-serialized data structure with minimal state, |
| * for mapping byte 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 BytesTrie implements Cloneable, Iterable<BytesTrie.Entry> { |
| /** |
| * Constructs a BytesTrie reader instance. |
| * |
| * <p>The array must contain a copy of a byte sequence from the BytesTrieBuilder, |
| * with the offset indicating the first byte of that sequence. |
| * The BytesTrie object will not read more bytes than |
| * the BytesTrieBuilder generated in the corresponding build() call. |
| * |
| * <p>The array is not copied/cloned and must not be modified while |
| * the BytesTrie object is in use. |
| * |
| * @param trieBytes Bytes array that contains the serialized trie. |
| * @param offset Root offset of the trie in the array. |
| * @stable ICU 4.8 |
| */ |
| public BytesTrie(byte[] trieBytes, int offset) { |
| bytes_=trieBytes; |
| pos_=root_=offset; |
| remainingMatchLength_=-1; |
| } |
| |
| /** |
| * Clones this trie reader object and its state, |
| * but not the byte 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 BytesTrie reset() { |
| pos_=root_; |
| remainingMatchLength_=-1; |
| return this; |
| } |
| |
| /** |
| * BytesTrie 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 byte[] bytes; |
| 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 BytesTrie saveState(State state) /*const*/ { |
| state.bytes=bytes_; |
| 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 BytesTrie resetToState(State state) { |
| if(bytes_==state.bytes && bytes_!=null && root_==state.root) { |
| pos_=state.pos; |
| remainingMatchLength_=state.remainingMatchLength; |
| } else { |
| throw new IllegalArgumentException("incompatible trie state"); |
| } |
| return this; |
| } |
| |
| /** |
| * Return values for BytesTrie.next(), CharsTrie.next() and similar methods. |
| * @stable ICU 4.8 |
| */ |
| public enum Result { |
| /** |
| * The input unit(s) did not continue a matching string. |
| * Once current()/next() return NO_MATCH, |
| * all further calls to current()/next() will also return NO_MATCH, |
| * until the trie is reset to its original state or to a saved state. |
| * @stable ICU 4.8 |
| */ |
| NO_MATCH, |
| /** |
| * The input unit(s) continued a matching string |
| * but there is no value for the string so far. |
| * (It is a prefix of a longer string.) |
| * @stable ICU 4.8 |
| */ |
| NO_VALUE, |
| /** |
| * The input unit(s) continued a matching string |
| * and there is a value for the string so far. |
| * This value will be returned by getValue(). |
| * No further input byte/unit can continue a matching string. |
| * @stable ICU 4.8 |
| */ |
| FINAL_VALUE, |
| /** |
| * The input unit(s) continued a matching string |
| * and there is a value for the string so far. |
| * This value will be returned by getValue(). |
| * Another input byte/unit can continue a matching string. |
| * @stable ICU 4.8 |
| */ |
| INTERMEDIATE_VALUE; |
| |
| // Note: The following methods assume the particular order |
| // of enum constants, treating the ordinal() values like bit sets. |
| // Do not reorder the enum constants! |
| |
| /** |
| * Same as (result!=NO_MATCH). |
| * @return true if the input bytes/units so far are part of a matching string/byte sequence. |
| * @stable ICU 4.8 |
| */ |
| public boolean matches() { return this!=NO_MATCH; } |
| |
| /** |
| * Equivalent to (result==INTERMEDIATE_VALUE || result==FINAL_VALUE). |
| * @return true if there is a value for the input bytes/units so far. |
| * @see #getValue |
| * @stable ICU 4.8 |
| */ |
| public boolean hasValue() { return ordinal()>=2; } |
| |
| /** |
| * Equivalent to (result==NO_VALUE || result==INTERMEDIATE_VALUE). |
| * @return true if another input byte/unit can continue a matching string. |
| * @stable ICU 4.8 |
| */ |
| public boolean hasNext() { return (ordinal()&1)!=0; } |
| } |
| |
| /** |
| * Determines whether the byte sequence so far matches, whether it has a value, |
| * and whether another input byte can continue a matching byte sequence. |
| * @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=bytes_[pos]&0xff)>=kMinValueLead) ? |
| valueResults_[node&kValueIsFinal] : Result.NO_VALUE; |
| } |
| } |
| |
| /** |
| * Traverses the trie from the initial state for this input byte. |
| * Equivalent to reset().next(inByte). |
| * @param inByte Input byte value. Values -0x100..-1 are treated like 0..0xff. |
| * Values below -0x100 and above 0xff will never match. |
| * @return The match/value Result. |
| * @stable ICU 4.8 |
| */ |
| public Result first(int inByte) { |
| remainingMatchLength_=-1; |
| if(inByte<0) { |
| inByte+=0x100; |
| } |
| return nextImpl(root_, inByte); |
| } |
| |
| /** |
| * Traverses the trie from the current state for this input byte. |
| * @param inByte Input byte value. Values -0x100..-1 are treated like 0..0xff. |
| * Values below -0x100 and above 0xff will never match. |
| * @return The match/value Result. |
| * @stable ICU 4.8 |
| */ |
| public Result next(int inByte) { |
| int pos=pos_; |
| if(pos<0) { |
| return Result.NO_MATCH; |
| } |
| if(inByte<0) { |
| inByte+=0x100; |
| } |
| int length=remainingMatchLength_; // Actual remaining match length minus 1. |
| if(length>=0) { |
| // Remaining part of a linear-match node. |
| if(inByte==(bytes_[pos++]&0xff)) { |
| remainingMatchLength_=--length; |
| pos_=pos; |
| int node; |
| return (length<0 && (node=bytes_[pos]&0xff)>=kMinValueLead) ? |
| valueResults_[node&kValueIsFinal] : Result.NO_VALUE; |
| } else { |
| stop(); |
| return Result.NO_MATCH; |
| } |
| } |
| return nextImpl(pos, inByte); |
| } |
| |
| /** |
| * Traverses the trie from the current state for this byte sequence. |
| * 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 or byte sequence. |
| * @param sIndex The start index of the byte sequence in s. |
| * @param sLimit The (exclusive) end index of the byte sequence in s. |
| * @return The match/value Result. |
| * @stable ICU 4.8 |
| */ |
| public Result next(byte[] 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 byte, if there is one. |
| // Continue a linear-match node. |
| byte inByte; |
| for(;;) { |
| if(sIndex==sLimit) { |
| remainingMatchLength_=length; |
| pos_=pos; |
| int node; |
| return (length<0 && (node=(bytes_[pos]&0xff))>=kMinValueLead) ? |
| valueResults_[node&kValueIsFinal] : Result.NO_VALUE; |
| } |
| inByte=s[sIndex++]; |
| if(length<0) { |
| remainingMatchLength_=length; |
| break; |
| } |
| if(inByte!=bytes_[pos]) { |
| stop(); |
| return Result.NO_MATCH; |
| } |
| ++pos; |
| --length; |
| } |
| for(;;) { |
| int node=bytes_[pos++]&0xff; |
| if(node<kMinLinearMatch) { |
| Result result=branchNext(pos, node, inByte&0xff); |
| if(result==Result.NO_MATCH) { |
| return Result.NO_MATCH; |
| } |
| // Fetch the next input byte, if there is one. |
| if(sIndex==sLimit) { |
| return result; |
| } |
| if(result==Result.FINAL_VALUE) { |
| // No further matching bytes. |
| stop(); |
| return Result.NO_MATCH; |
| } |
| inByte=s[sIndex++]; |
| pos=pos_; // branchNext() advanced pos and wrote it to pos_ . |
| } else if(node<kMinValueLead) { |
| // Match length+1 bytes. |
| length=node-kMinLinearMatch; // Actual match length minus 1. |
| if(inByte!=bytes_[pos]) { |
| stop(); |
| return Result.NO_MATCH; |
| } |
| ++pos; |
| --length; |
| break; |
| } else if((node&kValueIsFinal)!=0) { |
| // No further matching bytes. |
| stop(); |
| return Result.NO_MATCH; |
| } else { |
| // Skip intermediate value. |
| pos=skipValue(pos, node); |
| // The next node must not also be a value node. |
| assert((bytes_[pos]&0xff)<kMinValueLead); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Returns a matching byte sequence'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 byte sequence so far. |
| * @stable ICU 4.8 |
| */ |
| public int getValue() /*const*/ { |
| int pos=pos_; |
| int leadByte=bytes_[pos++]&0xff; |
| assert(leadByte>=kMinValueLead); |
| return readValue(bytes_, pos, leadByte>>1); |
| } |
| |
| /** |
| * Determines whether all byte sequences 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 byte sequences 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(bytes_, 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 byte which continues the byte sequence from the current state. |
| * That is, each byte b for which it would be next(b)!=Result.NO_MATCH now. |
| * @param out Each next byte is 0-extended to a char and appended to this object. |
| * (Only uses the out.append(c) method.) |
| * @return The number of bytes which continue the byte sequence from here. |
| * @stable ICU 4.8 |
| */ |
| public int getNextBytes(Appendable out) /*const*/ { |
| int pos=pos_; |
| if(pos<0) { |
| return 0; |
| } |
| if(remainingMatchLength_>=0) { |
| append(out, bytes_[pos]&0xff); // Next byte of a pending linear-match node. |
| return 1; |
| } |
| int node=bytes_[pos++]&0xff; |
| if(node>=kMinValueLead) { |
| if((node&kValueIsFinal)!=0) { |
| return 0; |
| } else { |
| pos=skipValue(pos, node); |
| node=bytes_[pos++]&0xff; |
| assert(node<kMinValueLead); |
| } |
| } |
| if(node<kMinLinearMatch) { |
| if(node==0) { |
| node=bytes_[pos++]&0xff; |
| } |
| getNextBranchBytes(bytes_, pos, ++node, out); |
| return node; |
| } else { |
| // First byte of the linear-match node. |
| append(out, bytes_[pos]&0xff); |
| return 1; |
| } |
| } |
| |
| /** |
| * Iterates from the current state of this trie. |
| * @return A new BytesTrie.Iterator. |
| * @stable ICU 4.8 |
| */ |
| public Iterator iterator() { |
| return new Iterator(bytes_, pos_, remainingMatchLength_, 0); |
| } |
| |
| /** |
| * Iterates from the current state of this trie. |
| * @param maxStringLength If 0, the iterator returns full strings/byte sequences. |
| * Otherwise, the iterator returns strings with this maximum length. |
| * @return A new BytesTrie.Iterator. |
| * @stable ICU 4.8 |
| */ |
| public Iterator iterator(int maxStringLength) { |
| return new Iterator(bytes_, pos_, remainingMatchLength_, maxStringLength); |
| } |
| |
| /** |
| * Iterates from the root of a byte-serialized BytesTrie. |
| * @param trieBytes Bytes array that contains the serialized trie. |
| * @param offset Root offset of the trie in the array. |
| * @param maxStringLength If 0, the iterator returns full strings/byte sequences. |
| * Otherwise, the iterator returns strings with this maximum length. |
| * @return A new BytesTrie.Iterator. |
| * @stable ICU 4.8 |
| */ |
| public static Iterator iterator(byte[] trieBytes, int offset, int maxStringLength) { |
| return new Iterator(trieBytes, offset, -1, maxStringLength); |
| } |
| |
| /** |
| * Return value type for the Iterator. |
| * @stable ICU 4.8 |
| */ |
| public static final class Entry { |
| private Entry(int capacity) { |
| bytes=new byte[capacity]; |
| } |
| |
| /** |
| * @return The length of the byte sequence. |
| * @stable ICU 4.8 |
| */ |
| public int bytesLength() { return length; } |
| /** |
| * Returns a byte of the byte sequence. |
| * @param index An index into the byte sequence. |
| * @return The index-th byte sequence byte. |
| * @stable ICU 4.8 |
| */ |
| public byte byteAt(int index) { return bytes[index]; } |
| /** |
| * Copies the byte sequence into a byte array. |
| * @param dest Destination byte array. |
| * @param destOffset Starting offset to where in dest the byte sequence is copied. |
| * @stable ICU 4.8 |
| */ |
| public void copyBytesTo(byte[] dest, int destOffset) { |
| System.arraycopy(bytes, 0, dest, destOffset, length); |
| } |
| /** |
| * @return The byte sequence as a read-only ByteBuffer. |
| * @stable ICU 4.8 |
| */ |
| public ByteBuffer bytesAsByteBuffer() { |
| return ByteBuffer.wrap(bytes, 0, length).asReadOnlyBuffer(); |
| } |
| |
| /** |
| * The value associated with the byte sequence. |
| * @stable ICU 4.8 |
| */ |
| public int value; |
| |
| private void ensureCapacity(int len) { |
| if(bytes.length<len) { |
| byte[] newBytes=new byte[Math.min(2*bytes.length, 2*len)]; |
| System.arraycopy(bytes, 0, newBytes, 0, length); |
| bytes=newBytes; |
| } |
| } |
| private void append(byte b) { |
| ensureCapacity(length+1); |
| bytes[length++]=b; |
| } |
| private void append(byte[] b, int off, int len) { |
| ensureCapacity(length+len); |
| System.arraycopy(b, off, bytes, length, len); |
| length+=len; |
| } |
| private void truncateString(int newLength) { length=newLength; } |
| |
| private byte[] bytes; |
| private int length; |
| } |
| |
| /** |
| * Iterator for all of the (byte sequence, value) pairs in a BytesTrie. |
| * @stable ICU 4.8 |
| */ |
| public static final class Iterator implements java.util.Iterator<Entry> { |
| private Iterator(byte[] trieBytes, int offset, int remainingMatchLength, int maxStringLength) { |
| bytes_=trieBytes; |
| pos_=initialPos_=offset; |
| remainingMatchLength_=initialRemainingMatchLength_=remainingMatchLength; |
| maxLength_=maxStringLength; |
| entry_=new Entry(maxLength_!=0 ? maxLength_ : 32); |
| int length=remainingMatchLength_; // Actual remaining match length minus 1. |
| if(length>=0) { |
| // Pending linear-match node, append remaining bytes to entry_. |
| ++length; |
| if(maxLength_>0 && length>maxLength_) { |
| length=maxLength_; // This will leave remainingMatchLength>=0 as a signal. |
| } |
| entry_.append(bytes_, 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_; |
| int length=remainingMatchLength_+1; // Remaining match length. |
| if(maxLength_>0 && length>maxLength_) { |
| length=maxLength_; |
| } |
| entry_.truncateString(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 (byte sequence, value) pair if there is one. |
| * |
| * If the byte sequence 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); |
| entry_.truncateString(length&0xffff); |
| length>>>=16; |
| if(length>1) { |
| pos=branchNext(pos, length); |
| if(pos<0) { |
| return entry_; // Reached a final value. |
| } |
| } else { |
| entry_.append(bytes_[pos++]); |
| } |
| } |
| if(remainingMatchLength_>=0) { |
| // We only get here if we started in a pending linear-match node |
| // with more than maxLength remaining bytes. |
| return truncateAndStop(); |
| } |
| for(;;) { |
| int node=bytes_[pos++]&0xff; |
| if(node>=kMinValueLead) { |
| // Deliver value for the byte sequence so far. |
| boolean isFinal=(node&kValueIsFinal)!=0; |
| entry_.value=readValue(bytes_, pos, node>>1); |
| if(isFinal || (maxLength_>0 && entry_.length==maxLength_)) { |
| pos_=-1; |
| } else { |
| pos_=skipValue(pos, node); |
| } |
| return entry_; |
| } |
| if(maxLength_>0 && entry_.length==maxLength_) { |
| return truncateAndStop(); |
| } |
| if(node<kMinLinearMatch) { |
| if(node==0) { |
| node=bytes_[pos++]&0xff; |
| } |
| pos=branchNext(pos, node+1); |
| if(pos<0) { |
| return entry_; // Reached a final value. |
| } |
| } else { |
| // Linear-match node, append length bytes to entry_. |
| int length=node-kMinLinearMatch+1; |
| if(maxLength_>0 && entry_.length+length>maxLength_) { |
| entry_.append(bytes_, pos, maxLength_-entry_.length); |
| return truncateAndStop(); |
| } |
| entry_.append(bytes_, 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; |
| entry_.value=-1; // no real value for str |
| return entry_; |
| } |
| |
| private int branchNext(int pos, int length) { |
| while(length>kMaxBranchLinearSubNodeLength) { |
| ++pos; // ignore the comparison byte |
| // Push state for the greater-or-equal edge. |
| stack_.add(((long)skipDelta(bytes_, pos)<<32)|((length-(length>>1))<<16)|entry_.length); |
| // Follow the less-than edge. |
| length>>=1; |
| pos=jumpByDelta(bytes_, pos); |
| } |
| // List of key-value pairs where values are either final values or jump deltas. |
| // Read the first (key, value) pair. |
| byte trieByte=bytes_[pos++]; |
| int node=bytes_[pos++]&0xff; |
| boolean isFinal=(node&kValueIsFinal)!=0; |
| int value=readValue(bytes_, pos, node>>1); |
| pos=skipValue(pos, node); |
| stack_.add(((long)pos<<32)|((length-1)<<16)|entry_.length); |
| entry_.append(trieByte); |
| if(isFinal) { |
| pos_=-1; |
| entry_.value=value; |
| return -1; |
| } else { |
| return pos+value; |
| } |
| } |
| |
| private byte[] bytes_; |
| private int pos_; |
| private int initialPos_; |
| private int remainingMatchLength_; |
| private int initialRemainingMatchLength_; |
| |
| private int maxLength_; |
| private Entry entry_; |
| |
| // The stack stores longs for backtracking to another |
| // outbound edge of a branch node. |
| // Each long has the offset from bytes_ in bits 62..32, |
| // the entry_.stringLength() from before the node in bits 15..0, |
| // and the remaining branch length in bits 24..16. (Bits 31..25 are unused.) |
| // (We could store the remaining branch length minus 1 in bits 23..16 and not use bits 31..24, |
| // 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 leadByte, and the lead byte is already shifted right by 1. |
| private static int readValue(byte[] bytes, int pos, int leadByte) { |
| int value; |
| if(leadByte<kMinTwoByteValueLead) { |
| value=leadByte-kMinOneByteValueLead; |
| } else if(leadByte<kMinThreeByteValueLead) { |
| value=((leadByte-kMinTwoByteValueLead)<<8)|(bytes[pos]&0xff); |
| } else if(leadByte<kFourByteValueLead) { |
| value=((leadByte-kMinThreeByteValueLead)<<16)|((bytes[pos]&0xff)<<8)|(bytes[pos+1]&0xff); |
| } else if(leadByte==kFourByteValueLead) { |
| value=((bytes[pos]&0xff)<<16)|((bytes[pos+1]&0xff)<<8)|(bytes[pos+2]&0xff); |
| } else { |
| value=(bytes[pos]<<24)|((bytes[pos+1]&0xff)<<16)|((bytes[pos+2]&0xff)<<8)|(bytes[pos+3]&0xff); |
| } |
| return value; |
| } |
| private static int skipValue(int pos, int leadByte) { |
| assert(leadByte>=kMinValueLead); |
| if(leadByte>=(kMinTwoByteValueLead<<1)) { |
| if(leadByte<(kMinThreeByteValueLead<<1)) { |
| ++pos; |
| } else if(leadByte<(kFourByteValueLead<<1)) { |
| pos+=2; |
| } else { |
| pos+=3+((leadByte>>1)&1); |
| } |
| } |
| return pos; |
| } |
| private static int skipValue(byte[] bytes, int pos) { |
| int leadByte=bytes[pos++]&0xff; |
| return skipValue(pos, leadByte); |
| } |
| |
| // Reads a jump delta and jumps. |
| private static int jumpByDelta(byte[] bytes, int pos) { |
| int delta=bytes[pos++]&0xff; |
| if(delta<kMinTwoByteDeltaLead) { |
| // nothing to do |
| } else if(delta<kMinThreeByteDeltaLead) { |
| delta=((delta-kMinTwoByteDeltaLead)<<8)|(bytes[pos++]&0xff); |
| } else if(delta<kFourByteDeltaLead) { |
| delta=((delta-kMinThreeByteDeltaLead)<<16)|((bytes[pos]&0xff)<<8)|(bytes[pos+1]&0xff); |
| pos+=2; |
| } else if(delta==kFourByteDeltaLead) { |
| delta=((bytes[pos]&0xff)<<16)|((bytes[pos+1]&0xff)<<8)|(bytes[pos+2]&0xff); |
| pos+=3; |
| } else { |
| delta=(bytes[pos]<<24)|((bytes[pos+1]&0xff)<<16)|((bytes[pos+2]&0xff)<<8)|(bytes[pos+3]&0xff); |
| pos+=4; |
| } |
| return pos+delta; |
| } |
| |
| private static int skipDelta(byte[] bytes, int pos) { |
| int delta=bytes[pos++]&0xff; |
| if(delta>=kMinTwoByteDeltaLead) { |
| if(delta<kMinThreeByteDeltaLead) { |
| ++pos; |
| } else if(delta<kFourByteDeltaLead) { |
| pos+=2; |
| } else { |
| pos+=3+(delta&1); |
| } |
| } |
| return pos; |
| } |
| |
| private static Result[] valueResults_={ Result.INTERMEDIATE_VALUE, Result.FINAL_VALUE }; |
| |
| // Handles a branch node for both next(byte) and next(string). |
| private Result branchNext(int pos, int length, int inByte) { |
| // Branch according to the current byte. |
| if(length==0) { |
| length=bytes_[pos++]&0xff; |
| } |
| ++length; |
| // The length of the branch is the number of bytes to select from. |
| // The data structure encodes a binary search. |
| while(length>kMaxBranchLinearSubNodeLength) { |
| if(inByte<(bytes_[pos++]&0xff)) { |
| length>>=1; |
| pos=jumpByDelta(bytes_, pos); |
| } else { |
| length=length-(length>>1); |
| pos=skipDelta(bytes_, pos); |
| } |
| } |
| // Drop down to linear search for the last few bytes. |
| // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3 |
| // and divides length by 2. |
| do { |
| if(inByte==(bytes_[pos++]&0xff)) { |
| Result result; |
| int node=bytes_[pos]&0xff; |
| assert(node>=kMinValueLead); |
| 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>>1); |
| node>>=1; |
| int delta; |
| if(node<kMinTwoByteValueLead) { |
| delta=node-kMinOneByteValueLead; |
| } else if(node<kMinThreeByteValueLead) { |
| delta=((node-kMinTwoByteValueLead)<<8)|(bytes_[pos++]&0xff); |
| } else if(node<kFourByteValueLead) { |
| delta=((node-kMinThreeByteValueLead)<<16)|((bytes_[pos]&0xff)<<8)|(bytes_[pos+1]&0xff); |
| pos+=2; |
| } else if(node==kFourByteValueLead) { |
| delta=((bytes_[pos]&0xff)<<16)|((bytes_[pos+1]&0xff)<<8)|(bytes_[pos+2]&0xff); |
| pos+=3; |
| } else { |
| delta=(bytes_[pos]<<24)|((bytes_[pos+1]&0xff)<<16)|((bytes_[pos+2]&0xff)<<8)|(bytes_[pos+3]&0xff); |
| pos+=4; |
| } |
| // end readValue() |
| pos+=delta; |
| node=bytes_[pos]&0xff; |
| result= node>=kMinValueLead ? valueResults_[node&kValueIsFinal] : Result.NO_VALUE; |
| } |
| pos_=pos; |
| return result; |
| } |
| --length; |
| pos=skipValue(bytes_, pos); |
| } while(length>1); |
| if(inByte==(bytes_[pos++]&0xff)) { |
| pos_=pos; |
| int node=bytes_[pos]&0xff; |
| return node>=kMinValueLead ? valueResults_[node&kValueIsFinal] : Result.NO_VALUE; |
| } else { |
| stop(); |
| return Result.NO_MATCH; |
| } |
| } |
| |
| // Requires remainingLength_<0. |
| private Result nextImpl(int pos, int inByte) { |
| for(;;) { |
| int node=bytes_[pos++]&0xff; |
| if(node<kMinLinearMatch) { |
| return branchNext(pos, node, inByte); |
| } else if(node<kMinValueLead) { |
| // Match the first of length+1 bytes. |
| int length=node-kMinLinearMatch; // Actual match length minus 1. |
| if(inByte==(bytes_[pos++]&0xff)) { |
| remainingMatchLength_=--length; |
| pos_=pos; |
| return (length<0 && (node=bytes_[pos]&0xff)>=kMinValueLead) ? |
| valueResults_[node&kValueIsFinal] : Result.NO_VALUE; |
| } else { |
| // No match. |
| break; |
| } |
| } else if((node&kValueIsFinal)!=0) { |
| // No further matching bytes. |
| break; |
| } else { |
| // Skip intermediate value. |
| pos=skipValue(pos, node); |
| // The next node must not also be a value node. |
| assert((bytes_[pos]&0xff)<kMinValueLead); |
| } |
| } |
| 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(byte[] bytes, int pos, int length, |
| long uniqueValue) { |
| while(length>kMaxBranchLinearSubNodeLength) { |
| ++pos; // ignore the comparison byte |
| uniqueValue=findUniqueValueFromBranch(bytes, jumpByDelta(bytes, pos), length>>1, uniqueValue); |
| if(uniqueValue==0) { |
| return 0; |
| } |
| length=length-(length>>1); |
| pos=skipDelta(bytes, pos); |
| } |
| do { |
| ++pos; // ignore a comparison byte |
| // handle its value |
| int node=bytes[pos++]&0xff; |
| boolean isFinal=(node&kValueIsFinal)!=0; |
| int value=readValue(bytes, pos, node>>1); |
| 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(bytes, 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 byte. |
| // 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(byte[] bytes, int pos, long uniqueValue) { |
| for(;;) { |
| int node=bytes[pos++]&0xff; |
| if(node<kMinLinearMatch) { |
| if(node==0) { |
| node=bytes[pos++]&0xff; |
| } |
| uniqueValue=findUniqueValueFromBranch(bytes, pos, node+1, uniqueValue); |
| if(uniqueValue==0) { |
| return 0; |
| } |
| pos=(int)(uniqueValue>>>33); |
| } else if(node<kMinValueLead) { |
| // linear-match node |
| pos+=node-kMinLinearMatch+1; // Ignore the match bytes. |
| } else { |
| boolean isFinal=(node&kValueIsFinal)!=0; |
| int value=readValue(bytes, pos, node>>1); |
| if(uniqueValue!=0) { |
| if(value!=(int)(uniqueValue>>1)) { |
| return 0; |
| } |
| } else { |
| uniqueValue=((long)value<<1)|1; |
| } |
| if(isFinal) { |
| return uniqueValue; |
| } |
| pos=skipValue(pos, node); |
| } |
| } |
| } |
| |
| // Helper functions for getNextBytes(). |
| // getNextBytes() when pos is on a branch node. |
| private static void getNextBranchBytes(byte[] bytes, int pos, int length, Appendable out) { |
| while(length>kMaxBranchLinearSubNodeLength) { |
| ++pos; // ignore the comparison byte |
| getNextBranchBytes(bytes, jumpByDelta(bytes, pos), length>>1, out); |
| length=length-(length>>1); |
| pos=skipDelta(bytes, pos); |
| } |
| do { |
| append(out, bytes[pos++]&0xff); |
| pos=skipValue(bytes, pos); |
| } while(--length>1); |
| append(out, bytes[pos]&0xff); |
| } |
| private static void append(Appendable out, int c) { |
| try { |
| out.append((char)c); |
| } catch(IOException e) { |
| throw new ICUUncheckedIOException(e); |
| } |
| } |
| |
| // BytesTrie data structure |
| // |
| // The trie consists of a series of byte-serialized nodes for incremental |
| // string/byte sequence matching. The root node is at the beginning of the trie data. |
| // |
| // Types of nodes are distinguished by their node lead byte ranges. |
| // After each node, except a final-value node, another node follows to |
| // encode match values or continue matching further bytes. |
| // |
| // Node types: |
| // - Value node: Stores a 32-bit integer in a compact, variable-length format. |
| // The value is for the string/byte sequence so far. |
| // One node bit indicates whether the value is final or whether |
| // matching continues with the next node. |
| // - Linear-match node: Matches a number of bytes. |
| // - Branch node: Branches to other nodes according to the current input byte. |
| // The node byte is the length of the branch (number of bytes 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 byte. |
| // If one of the key bytes matches, then the value is either a final value for |
| // the string/byte sequence so far, or a "jump" delta to the next node. |
| // If the last byte matches, then matching continues with the next node. |
| // (Values have the same encoding as value nodes.) |
| // - If the length is greater than kMaxBranchLinearSubNodeLength, then |
| // there is one byte and one "jump" delta. |
| // If the input byte is less than the sub-node byte, 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. |
| |
| // Node lead byte values. |
| |
| // 00..0f: Branch node. If node!=0 then the length is node+1, otherwise |
| // the length is one more than the next byte. |
| |
| // For a branch sub-node with at most this many entries, we drop down |
| // to a linear search. |
| /*package*/ static final int kMaxBranchLinearSubNodeLength=5; |
| |
| // 10..1f: Linear-match node, match 1..16 bytes and continue reading the next node. |
| /*package*/ static final int kMinLinearMatch=0x10; |
| /*package*/ static final int kMaxLinearMatchLength=0x10; |
| |
| // 20..ff: Variable-length value node. |
| // If odd, the value is final. (Otherwise, intermediate value or jump delta.) |
| // Then shift-right by 1 bit. |
| // The remaining lead byte value indicates the number of following bytes (0..4) |
| // and contains the value's top bits. |
| /*package*/ static final int kMinValueLead=kMinLinearMatch+kMaxLinearMatchLength; // 0x20 |
| // It is a final value if bit 0 is set. |
| private static final int kValueIsFinal=1; |
| |
| // Compact value: After testing bit 0, shift right by 1 and then use the following thresholds. |
| /*package*/ static final int kMinOneByteValueLead=kMinValueLead/2; // 0x10 |
| /*package*/ static final int kMaxOneByteValue=0x40; // At least 6 bits in the first byte. |
| |
| /*package*/ static final int kMinTwoByteValueLead=kMinOneByteValueLead+kMaxOneByteValue+1; // 0x51 |
| /*package*/ static final int kMaxTwoByteValue=0x1aff; |
| |
| /*package*/ static final int kMinThreeByteValueLead=kMinTwoByteValueLead+(kMaxTwoByteValue>>8)+1; // 0x6c |
| /*package*/ static final int kFourByteValueLead=0x7e; |
| |
| // A little more than Unicode code points. (0x11ffff) |
| /*package*/ static final int kMaxThreeByteValue=((kFourByteValueLead-kMinThreeByteValueLead)<<16)-1; |
| |
| /*package*/ static final int kFiveByteValueLead=0x7f; |
| |
| // Compact delta integers. |
| /*package*/ static final int kMaxOneByteDelta=0xbf; |
| /*package*/ static final int kMinTwoByteDeltaLead=kMaxOneByteDelta+1; // 0xc0 |
| /*package*/ static final int kMinThreeByteDeltaLead=0xf0; |
| /*package*/ static final int kFourByteDeltaLead=0xfe; |
| /*package*/ static final int kFiveByteDeltaLead=0xff; |
| |
| /*package*/ static final int kMaxTwoByteDelta=((kMinThreeByteDeltaLead-kMinTwoByteDeltaLead)<<8)-1; // 0x2fff |
| /*package*/ static final int kMaxThreeByteDelta=((kFourByteDeltaLead-kMinThreeByteDeltaLead)<<16)-1; // 0xdffff |
| |
| // Fixed value referencing the BytesTrie bytes. |
| private byte[] bytes_; |
| private int root_; |
| |
| // Iterator variables. |
| |
| // Index of next trie byte to read. Negative 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_; |
| }; |
