jars/icu4j-4_8_1_1/main/classes/core/src/com/ibm/icu/util/BytesTrie.java

   1 /*
   2 *******************************************************************************
   3 *   Copyright (C) 2010-2011, International Business Machines
   4 *   Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 *   created on: 2010nov23
   7 *   created by: Markus W. Scherer
   8 *   ported from ICU4C bytestrie.h/.cpp
   9 */
  10 package com.ibm.icu.util;
  11
  12 import java.io.IOException;
  13 import java.nio.ByteBuffer;
  14 import java.util.ArrayList;
  15 import java.util.NoSuchElementException;
  16
  17 /**
  18  * Light-weight, non-const reader class for a BytesTrie.
  19  * Traverses a byte-serialized data structure with minimal state,
  20  * for mapping byte sequences to non-negative integer values.
  21  *
  22  * <p>This class is not intended for public subclassing.
  23  *
  24  * @draft ICU 4.8
  25  * @provisional This API might change or be removed in a future release.
  26  * @author Markus W. Scherer
  27  */
  28 public final class BytesTrie implements Cloneable, Iterable<BytesTrie.Entry> {
  29     /**
  30      * Constructs a BytesTrie reader instance.
  31      *
  32      * <p>The array must contain a copy of a byte sequence from the BytesTrieBuilder,
  33      * with the offset indicating the first byte of that sequence.
  34      * The BytesTrie object will not read more bytes than
  35      * the BytesTrieBuilder generated in the corresponding build() call.
  36      *
  37      * <p>The array is not copied/cloned and must not be modified while
  38      * the BytesTrie object is in use.
  39      *
  40      * @param trieBytes Bytes array that contains the serialized trie.
  41      * @param offset Root offset of the trie in the array.
  42      * @draft ICU 4.8
  43      * @provisional This API might change or be removed in a future release.
  44      */
  45     public BytesTrie(byte[] trieBytes, int offset) {
  46         bytes_=trieBytes;
  47         pos_=root_=offset;
  48         remainingMatchLength_=-1;
  49     }
  50
  51     /**
  52      * Clones this trie reader object and its state,
  53      * but not the byte array which will be shared.
  54      * @return A shallow clone of this trie.
  55      * @draft ICU 4.8
  56      * @provisional This API might change or be removed in a future release.
  57      */
  58     @Override
  59     public Object clone() throws CloneNotSupportedException {
  60         return super.clone();  // A shallow copy is just what we need.
  61     }
  62
  63     /**
  64      * Resets this trie to its initial state.
  65      * @return this
  66      * @draft ICU 4.8
  67      * @provisional This API might change or be removed in a future release.
  68      */
  69     public BytesTrie reset() {
  70         pos_=root_;
  71         remainingMatchLength_=-1;
  72         return this;
  73     }
  74
  75     /**
  76      * BytesTrie state object, for saving a trie's current state
  77      * and resetting the trie back to this state later.
  78      * @draft ICU 4.8
  79      * @provisional This API might change or be removed in a future release.
  80      */
  81     public static final class State {
  82         /**
  83          * Constructs an empty State.
  84          * @draft ICU 4.8
  85          * @provisional This API might change or be removed in a future release.
  86          */
  87         public State() {}
  88         private byte[] bytes;
  89         private int root;
  90         private int pos;
  91         private int remainingMatchLength;
  92     }
  93
  94     /**
  95      * Saves the state of this trie.
  96      * @param state The State object to hold the trie's state.
  97      * @return this
  98      * @see #resetToState
  99      * @draft ICU 4.8
 100      * @provisional This API might change or be removed in a future release.
 101      */
 102     public BytesTrie saveState(State state) /*const*/ {
 103         state.bytes=bytes_;
 104         state.root=root_;
 105         state.pos=pos_;
 106         state.remainingMatchLength=remainingMatchLength_;
 107         return this;
 108     }
 109
 110     /**
 111      * Resets this trie to the saved state.
 112      * @param state The State object which holds a saved trie state.
 113      * @return this
 114      * @throws IllegalArgumentException if the state object contains no state,
 115      *         or the state of a different trie
 116      * @see #saveState
 117      * @see #reset
 118      * @draft ICU 4.8
 119      * @provisional This API might change or be removed in a future release.
 120      */
 121     public BytesTrie resetToState(State state) {
 122         if(bytes_==state.bytes && bytes_!=null && root_==state.root) {
 123             pos_=state.pos;
 124             remainingMatchLength_=state.remainingMatchLength;
 125         } else {
 126             throw new IllegalArgumentException("incompatible trie state");
 127         }
 128         return this;
 129     }
 130
 131     /**
 132      * Return values for BytesTrie.next(), CharsTrie.next() and similar methods.
 133      * @draft ICU 4.8
 134      * @provisional This API might change or be removed in a future release.
 135      */
 136     public enum Result {
 137         /**
 138          * The input unit(s) did not continue a matching string.
 139          * Once current()/next() return NO_MATCH,
 140          * all further calls to current()/next() will also return NO_MATCH,
 141          * until the trie is reset to its original state or to a saved state.
 142          * @draft ICU 4.8
 143          * @provisional This API might change or be removed in a future release.
 144          */
 145         NO_MATCH,
 146         /**
 147          * The input unit(s) continued a matching string
 148          * but there is no value for the string so far.
 149          * (It is a prefix of a longer string.)
 150          * @draft ICU 4.8
 151          * @provisional This API might change or be removed in a future release.
 152          */
 153         NO_VALUE,
 154         /**
 155          * The input unit(s) continued a matching string
 156          * and there is a value for the string so far.
 157          * This value will be returned by getValue().
 158          * No further input byte/unit can continue a matching string.
 159          * @draft ICU 4.8
 160          * @provisional This API might change or be removed in a future release.
 161          */
 162         FINAL_VALUE,
 163         /**
 164          * The input unit(s) continued a matching string
 165          * and there is a value for the string so far.
 166          * This value will be returned by getValue().
 167          * Another input byte/unit can continue a matching string.
 168          * @draft ICU 4.8
 169          * @provisional This API might change or be removed in a future release.
 170          */
 171         INTERMEDIATE_VALUE;
 172
 173         // Note: The following methods assume the particular order
 174         // of enum constants, treating the ordinal() values like bit sets.
 175         // Do not reorder the enum constants!
 176
 177         /**
 178          * Same as (result!=NO_MATCH).
 179          * @return true if the input bytes/units so far are part of a matching string/byte sequence.
 180          * @draft ICU 4.8
 181          * @provisional This API might change or be removed in a future release.
 182          */
 183         public boolean matches() { return this!=NO_MATCH; }
 184
 185         /**
 186          * Equivalent to (result==INTERMEDIATE_VALUE || result==FINAL_VALUE).
 187          * @return true if there is a value for the input bytes/units so far.
 188          * @see #getValue
 189          * @draft ICU 4.8
 190          * @provisional This API might change or be removed in a future release.
 191          */
 192         public boolean hasValue() { return ordinal()>=2; }
 193
 194         /**
 195          * Equivalent to (result==NO_VALUE || result==INTERMEDIATE_VALUE).
 196          * @return true if another input byte/unit can continue a matching string.
 197          * @draft ICU 4.8
 198          * @provisional This API might change or be removed in a future release.
 199          */
 200         public boolean hasNext() { return (ordinal()&1)!=0; }
 201     }
 202
 203     /**
 204      * Determines whether the byte sequence so far matches, whether it has a value,
 205      * and whether another input byte can continue a matching byte sequence.
 206      * @return The match/value Result.
 207      * @draft ICU 4.8
 208      * @provisional This API might change or be removed in a future release.
 209      */
 210     public Result current() /*const*/ {
 211         int pos=pos_;
 212         if(pos<0) {
 213             return Result.NO_MATCH;
 214         } else {
 215             int node;
 216             return (remainingMatchLength_<0 && (node=bytes_[pos]&0xff)>=kMinValueLead) ?
 217                     valueResults_[node&kValueIsFinal] : Result.NO_VALUE;
 218         }
 219     }
 220
 221     /**
 222      * Traverses the trie from the initial state for this input byte.
 223      * Equivalent to reset().next(inByte).
 224      * @param inByte Input byte value. Values -0x100..-1 are treated like 0..0xff.
 225      *               Values below -0x100 and above 0xff will never match.
 226      * @return The match/value Result.
 227      * @draft ICU 4.8
 228      * @provisional This API might change or be removed in a future release.
 229      */
 230     public Result first(int inByte) {
 231         remainingMatchLength_=-1;
 232         if(inByte<0) {
 233             inByte+=0x100;
 234         }
 235         return nextImpl(root_, inByte);
 236     }
 237
 238     /**
 239      * Traverses the trie from the current state for this input byte.
 240      * @param inByte Input byte value. Values -0x100..-1 are treated like 0..0xff.
 241      *               Values below -0x100 and above 0xff will never match.
 242      * @return The match/value Result.
 243      * @draft ICU 4.8
 244      * @provisional This API might change or be removed in a future release.
 245      */
 246     public Result next(int inByte) {
 247         int pos=pos_;
 248         if(pos<0) {
 249             return Result.NO_MATCH;
 250         }
 251         if(inByte<0) {
 252             inByte+=0x100;
 253         }
 254         int length=remainingMatchLength_;  // Actual remaining match length minus 1.
 255         if(length>=0) {
 256             // Remaining part of a linear-match node.
 257             if(inByte==(bytes_[pos++]&0xff)) {
 258                 remainingMatchLength_=--length;
 259                 pos_=pos;
 260                 int node;
 261                 return (length<0 && (node=bytes_[pos]&0xff)>=kMinValueLead) ?
 262                         valueResults_[node&kValueIsFinal] : Result.NO_VALUE;
 263             } else {
 264                 stop();
 265                 return Result.NO_MATCH;
 266             }
 267         }
 268         return nextImpl(pos, inByte);
 269     }
 270
 271     /**
 272      * Traverses the trie from the current state for this byte sequence.
 273      * Equivalent to
 274      * <pre>
 275      * Result result=current();
 276      * for(each c in s)
 277      *   if(!result.hasNext()) return Result.NO_MATCH;
 278      *   result=next(c);
 279      * return result;
 280      * </pre>
 281      * @param s Contains a string or byte sequence.
 282      * @param sIndex The start index of the byte sequence in s.
 283      * @param sLimit The (exclusive) end index of the byte sequence in s.
 284      * @return The match/value Result.
 285      * @draft ICU 4.8
 286      * @provisional This API might change or be removed in a future release.
 287      */
 288     public Result next(byte[] s, int sIndex, int sLimit) {
 289         if(sIndex>=sLimit) {
 290             // Empty input.
 291             return current();
 292         }
 293         int pos=pos_;
 294         if(pos<0) {
 295             return Result.NO_MATCH;
 296         }
 297         int length=remainingMatchLength_;  // Actual remaining match length minus 1.
 298         for(;;) {
 299             // Fetch the next input byte, if there is one.
 300             // Continue a linear-match node.
 301             byte inByte;
 302             for(;;) {
 303                 if(sIndex==sLimit) {
 304                     remainingMatchLength_=length;
 305                     pos_=pos;
 306                     int node;
 307                     return (length<0 && (node=(bytes_[pos]&0xff))>=kMinValueLead) ?
 308                             valueResults_[node&kValueIsFinal] : Result.NO_VALUE;
 309                 }
 310                 inByte=s[sIndex++];
 311                 if(length<0) {
 312                     remainingMatchLength_=length;
 313                     break;
 314                 }
 315                 if(inByte!=bytes_[pos]) {
 316                     stop();
 317                     return Result.NO_MATCH;
 318                 }
 319                 ++pos;
 320                 --length;
 321             }
 322             for(;;) {
 323                 int node=bytes_[pos++]&0xff;
 324                 if(node<kMinLinearMatch) {
 325                     Result result=branchNext(pos, node, inByte&0xff);
 326                     if(result==Result.NO_MATCH) {
 327                         return Result.NO_MATCH;
 328                     }
 329                     // Fetch the next input byte, if there is one.
 330                     if(sIndex==sLimit) {
 331                         return result;
 332                     }
 333                     if(result==Result.FINAL_VALUE) {
 334                         // No further matching bytes.
 335                         stop();
 336                         return Result.NO_MATCH;
 337                     }
 338                     inByte=s[sIndex++];
 339                     pos=pos_;  // branchNext() advanced pos and wrote it to pos_ .
 340                 } else if(node<kMinValueLead) {
 341                     // Match length+1 bytes.
 342                     length=node-kMinLinearMatch;  // Actual match length minus 1.
 343                     if(inByte!=bytes_[pos]) {
 344                         stop();
 345                         return Result.NO_MATCH;
 346                     }
 347                     ++pos;
 348                     --length;
 349                     break;
 350                 } else if((node&kValueIsFinal)!=0) {
 351                     // No further matching bytes.
 352                     stop();
 353                     return Result.NO_MATCH;
 354                 } else {
 355                     // Skip intermediate value.
 356                     pos=skipValue(pos, node);
 357                     // The next node must not also be a value node.
 358                     assert((bytes_[pos]&0xff)<kMinValueLead);
 359                 }
 360             }
 361         }
 362     }
 363
 364     /**
 365      * Returns a matching byte sequence's value if called immediately after
 366      * current()/first()/next() returned Result.INTERMEDIATE_VALUE or Result.FINAL_VALUE.
 367      * getValue() can be called multiple times.
 368      *
 369      * Do not call getValue() after Result.NO_MATCH or Result.NO_VALUE!
 370      * @return The value for the byte sequence so far.
 371      * @draft ICU 4.8
 372      * @provisional This API might change or be removed in a future release.
 373      */
 374     public int getValue() /*const*/ {
 375         int pos=pos_;
 376         int leadByte=bytes_[pos++]&0xff;
 377         assert(leadByte>=kMinValueLead);
 378         return readValue(bytes_, pos, leadByte>>1);
 379     }
 380
 381     /**
 382      * Determines whether all byte sequences reachable from the current state
 383      * map to the same value, and if so, returns that value.
 384      * @return The unique value in bits 32..1 with bit 0 set,
 385      *         if all byte sequences reachable from the current state
 386      *         map to the same value; otherwise returns 0.
 387      * @draft ICU 4.8
 388      * @provisional This API might change or be removed in a future release.
 389      */
 390     public long getUniqueValue() /*const*/ {
 391         int pos=pos_;
 392         if(pos<0) {
 393             return 0;
 394         }
 395         // Skip the rest of a pending linear-match node.
 396         long uniqueValue=findUniqueValue(bytes_, pos+remainingMatchLength_+1, 0);
 397         // Ignore internally used bits 63..33; extend the actual value's sign bit from bit 32.
 398         return (uniqueValue<<31)>>31;
 399     }
 400
 401     /**
 402      * Finds each byte which continues the byte sequence from the current state.
 403      * That is, each byte b for which it would be next(b)!=Result.NO_MATCH now.
 404      * @param out Each next byte is 0-extended to a char and appended to this object.
 405      *            (Only uses the out.append(c) method.)
 406      * @return The number of bytes which continue the byte sequence from here.
 407      * @draft ICU 4.8
 408      * @provisional This API might change or be removed in a future release.
 409      */
 410     public int getNextBytes(Appendable out) /*const*/ {
 411         int pos=pos_;
 412         if(pos<0) {
 413             return 0;
 414         }
 415         if(remainingMatchLength_>=0) {
 416             append(out, bytes_[pos]&0xff);  // Next byte of a pending linear-match node.
 417             return 1;
 418         }
 419         int node=bytes_[pos++]&0xff;
 420         if(node>=kMinValueLead) {
 421             if((node&kValueIsFinal)!=0) {
 422                 return 0;
 423             } else {
 424                 pos=skipValue(pos, node);
 425                 node=bytes_[pos++]&0xff;
 426                 assert(node<kMinValueLead);
 427             }
 428         }
 429         if(node<kMinLinearMatch) {
 430             if(node==0) {
 431                 node=bytes_[pos++]&0xff;
 432             }
 433             getNextBranchBytes(bytes_, pos, ++node, out);
 434             return node;
 435         } else {
 436             // First byte of the linear-match node.
 437             append(out, bytes_[pos]&0xff);
 438             return 1;
 439         }
 440     }
 441
 442     /**
 443      * Iterates from the current state of this trie.
 444      * @return A new BytesTrie.Iterator.
 445      * @draft ICU 4.8
 446      * @provisional This API might change or be removed in a future release.
 447      */
 448     public Iterator iterator() {
 449         return new Iterator(bytes_, pos_, remainingMatchLength_, 0);
 450     }
 451
 452     /**
 453      * Iterates from the current state of this trie.
 454      * @param maxStringLength If 0, the iterator returns full strings/byte sequences.
 455      *                        Otherwise, the iterator returns strings with this maximum length.
 456      * @return A new BytesTrie.Iterator.
 457      * @draft ICU 4.8
 458      * @provisional This API might change or be removed in a future release.
 459      */
 460     public Iterator iterator(int maxStringLength) {
 461         return new Iterator(bytes_, pos_, remainingMatchLength_, maxStringLength);
 462     }
 463
 464     /**
 465      * Iterates from the root of a byte-serialized BytesTrie.
 466      * @param trieBytes Bytes array that contains the serialized trie.
 467      * @param offset Root offset of the trie in the array.
 468      * @param maxStringLength If 0, the iterator returns full strings/byte sequences.
 469      *                        Otherwise, the iterator returns strings with this maximum length.
 470      * @return A new BytesTrie.Iterator.
 471      * @draft ICU 4.8
 472      * @provisional This API might change or be removed in a future release.
 473      */
 474     public static Iterator iterator(byte[] trieBytes, int offset, int maxStringLength) {
 475         return new Iterator(trieBytes, offset, -1, maxStringLength);
 476     }
 477
 478     /**
 479      * Return value type for the Iterator.
 480      * @draft ICU 4.8
 481      * @provisional This API might change or be removed in a future release.
 482      */
 483     public static final class Entry {
 484         private Entry(int capacity) {
 485             bytes=new byte[capacity];
 486         }
 487
 488         /**
 489          * @return The length of the byte sequence.
 490          * @draft ICU 4.8
 491          * @provisional This API might change or be removed in a future release.
 492          */
 493         public int bytesLength() { return length; }
 494         /**
 495          * Returns a byte of the byte sequence.
 496          * @param index An index into the byte sequence.
 497          * @return The index-th byte sequence byte.
 498          * @draft ICU 4.8
 499          * @provisional This API might change or be removed in a future release.
 500          */
 501         public byte byteAt(int index) { return bytes[index]; }
 502         /**
 503          * Copies the byte sequence into a byte array.
 504          * @param dest Destination byte array.
 505          * @param destOffset Starting offset to where in dest the byte sequence is copied.
 506          * @draft ICU 4.8
 507          * @provisional This API might change or be removed in a future release.
 508          */
 509         public void copyBytesTo(byte[] dest, int destOffset) {
 510             System.arraycopy(bytes, 0, dest, destOffset, length);
 511         }
 512         /**
 513          * @return The byte sequence as a read-only ByteBuffer.
 514          * @draft ICU 4.8
 515          * @provisional This API might change or be removed in a future release.
 516          */
 517         public ByteBuffer bytesAsByteBuffer() {
 518             return ByteBuffer.wrap(bytes, 0, length).asReadOnlyBuffer();
 519         }
 520
 521         /**
 522          * The value associated with the byte sequence.
 523          * @draft ICU 4.8
 524          * @provisional This API might change or be removed in a future release.
 525          */
 526         public int value;
 527
 528         private void ensureCapacity(int len) {
 529             if(bytes.length<len) {
 530                 byte[] newBytes=new byte[Math.min(2*bytes.length, 2*len)];
 531                 System.arraycopy(bytes, 0, newBytes, 0, length);
 532                 bytes=newBytes;
 533             }
 534         }
 535         private void append(byte b) {
 536             ensureCapacity(length+1);
 537             bytes[length++]=b;
 538         }
 539         private void append(byte[] b, int off, int len) {
 540             ensureCapacity(length+len);
 541             System.arraycopy(b, off, bytes, length, len);
 542             length+=len;
 543         }
 544         private void truncateString(int newLength) { length=newLength; }
 545
 546         private byte[] bytes;
 547         private int length;
 548     }
 549
 550     /**
 551      * Iterator for all of the (byte sequence, value) pairs in a BytesTrie.
 552      * @draft ICU 4.8
 553      * @provisional This API might change or be removed in a future release.
 554      */
 555     public static final class Iterator implements java.util.Iterator<Entry> {
 556         private Iterator(byte[] trieBytes, int offset, int remainingMatchLength, int maxStringLength) {
 557             bytes_=trieBytes;
 558             pos_=initialPos_=offset;
 559             remainingMatchLength_=initialRemainingMatchLength_=remainingMatchLength;
 560             maxLength_=maxStringLength;
 561             entry_=new Entry(maxLength_!=0 ? maxLength_ : 32);
 562             int length=remainingMatchLength_;  // Actual remaining match length minus 1.
 563             if(length>=0) {
 564                 // Pending linear-match node, append remaining bytes to entry_.
 565                 ++length;
 566                 if(maxLength_>0 && length>maxLength_) {
 567                     length=maxLength_;  // This will leave remainingMatchLength>=0 as a signal.
 568                 }
 569                 entry_.append(bytes_, pos_, length);
 570                 pos_+=length;
 571                 remainingMatchLength_-=length;
 572             }
 573         }
 574
 575         /**
 576          * Resets this iterator to its initial state.
 577          * @return this
 578          * @draft ICU 4.8
 579          * @provisional This API might change or be removed in a future release.
 580          */
 581         public Iterator reset() {
 582             pos_=initialPos_;
 583             remainingMatchLength_=initialRemainingMatchLength_;
 584             int length=remainingMatchLength_+1;  // Remaining match length.
 585             if(maxLength_>0 && length>maxLength_) {
 586                 length=maxLength_;
 587             }
 588             entry_.truncateString(length);
 589             pos_+=length;
 590             remainingMatchLength_-=length;
 591             stack_.clear();
 592             return this;
 593         }
 594
 595         /**
 596          * @return true if there are more elements.
 597          * @draft ICU 4.8
 598          * @provisional This API might change or be removed in a future release.
 599          */
 600         public boolean hasNext() /*const*/ { return pos_>=0 || !stack_.isEmpty(); }
 601
 602         /**
 603          * Finds the next (byte sequence, value) pair if there is one.
 604          *
 605          * If the byte sequence is truncated to the maximum length and does not
 606          * have a real value, then the value is set to -1.
 607          * In this case, this "not a real value" is indistinguishable from
 608          * a real value of -1.
 609          * @return An Entry with the string and value of the next element.
 610          * @throws NoSuchElementException - iteration has no more elements.
 611          * @draft ICU 4.8
 612          * @provisional This API might change or be removed in a future release.
 613          */
 614         public Entry next() {
 615             int pos=pos_;
 616             if(pos<0) {
 617                 if(stack_.isEmpty()) {
 618                     throw new NoSuchElementException();
 619                 }
 620                 // Pop the state off the stack and continue with the next outbound edge of
 621                 // the branch node.
 622                 long top=stack_.remove(stack_.size()-1);
 623                 int length=(int)top;
 624                 pos=(int)(top>>32);
 625                 entry_.truncateString(length&0xffff);
 626                 length>>>=16;
 627                 if(length>1) {
 628                     pos=branchNext(pos, length);
 629                     if(pos<0) {
 630                         return entry_;  // Reached a final value.
 631                     }
 632                 } else {
 633                     entry_.append(bytes_[pos++]);
 634                 }
 635             }
 636             if(remainingMatchLength_>=0) {
 637                 // We only get here if we started in a pending linear-match node
 638                 // with more than maxLength remaining bytes.
 639                 return truncateAndStop();
 640             }
 641             for(;;) {
 642                 int node=bytes_[pos++]&0xff;
 643                 if(node>=kMinValueLead) {
 644                     // Deliver value for the byte sequence so far.
 645                     boolean isFinal=(node&kValueIsFinal)!=0;
 646                     entry_.value=readValue(bytes_, pos, node>>1);
 647                     if(isFinal || (maxLength_>0 && entry_.length==maxLength_)) {
 648                         pos_=-1;
 649                     } else {
 650                         pos_=skipValue(pos, node);
 651                     }
 652                     return entry_;
 653                 }
 654                 if(maxLength_>0 && entry_.length==maxLength_) {
 655                     return truncateAndStop();
 656                 }
 657                 if(node<kMinLinearMatch) {
 658                     if(node==0) {
 659                         node=bytes_[pos++]&0xff;
 660                     }
 661                     pos=branchNext(pos, node+1);
 662                     if(pos<0) {
 663                         return entry_;  // Reached a final value.
 664                     }
 665                 } else {
 666                     // Linear-match node, append length bytes to entry_.
 667                     int length=node-kMinLinearMatch+1;
 668                     if(maxLength_>0 && entry_.length+length>maxLength_) {
 669                         entry_.append(bytes_, pos, maxLength_-entry_.length);
 670                         return truncateAndStop();
 671                     }
 672                     entry_.append(bytes_, pos, length);
 673                     pos+=length;
 674                 }
 675             }
 676         }
 677
 678         /**
 679          * Iterator.remove() is not supported.
 680          * @throws UnsupportedOperationException (always)
 681          * @draft ICU 4.8
 682          * @provisional This API might change or be removed in a future release.
 683          */
 684         public void remove() {
 685             throw new UnsupportedOperationException();
 686         }
 687
 688         private Entry truncateAndStop() {
 689             pos_=-1;
 690             entry_.value=-1;  // no real value for str
 691             return entry_;
 692         }
 693
 694         private int branchNext(int pos, int length) {
 695             while(length>kMaxBranchLinearSubNodeLength) {
 696                 ++pos;  // ignore the comparison byte
 697                 // Push state for the greater-or-equal edge.
 698                 stack_.add(((long)skipDelta(bytes_, pos)<<32)|((length-(length>>1))<<16)|entry_.length);
 699                 // Follow the less-than edge.
 700                 length>>=1;
 701                 pos=jumpByDelta(bytes_, pos);
 702             }
 703             // List of key-value pairs where values are either final values or jump deltas.
 704             // Read the first (key, value) pair.
 705             byte trieByte=bytes_[pos++];
 706             int node=bytes_[pos++]&0xff;
 707             boolean isFinal=(node&kValueIsFinal)!=0;
 708             int value=readValue(bytes_, pos, node>>1);
 709             pos=skipValue(pos, node);
 710             stack_.add(((long)pos<<32)|((length-1)<<16)|entry_.length);
 711             entry_.append(trieByte);
 712             if(isFinal) {
 713                 pos_=-1;
 714                 entry_.value=value;
 715                 return -1;
 716             } else {
 717                 return pos+value;
 718             }
 719         }
 720
 721         private byte[] bytes_;
 722         private int pos_;
 723         private int initialPos_;
 724         private int remainingMatchLength_;
 725         private int initialRemainingMatchLength_;
 726
 727         private int maxLength_;
 728         private Entry entry_;
 729
 730         // The stack stores longs for backtracking to another
 731         // outbound edge of a branch node.
 732         // Each long has the offset from bytes_ in bits 62..32,
 733         // the entry_.stringLength() from before the node in bits 15..0,
 734         // and the remaining branch length in bits 24..16. (Bits 31..25 are unused.)
 735         // (We could store the remaining branch length minus 1 in bits 23..16 and not use bits 31..24,
 736         // but the code looks more confusing that way.)
 737         private ArrayList<Long> stack_=new ArrayList<Long>();
 738     }
 739
 740     private void stop() {
 741         pos_=-1;
 742     }
 743
 744     // Reads a compact 32-bit integer.
 745     // pos is already after the leadByte, and the lead byte is already shifted right by 1.
 746     private static int readValue(byte[] bytes, int pos, int leadByte) {
 747         int value;
 748         if(leadByte<kMinTwoByteValueLead) {
 749             value=leadByte-kMinOneByteValueLead;
 750         } else if(leadByte<kMinThreeByteValueLead) {
 751             value=((leadByte-kMinTwoByteValueLead)<<8)|(bytes[pos]&0xff);
 752         } else if(leadByte<kFourByteValueLead) {
 753             value=((leadByte-kMinThreeByteValueLead)<<16)|((bytes[pos]&0xff)<<8)|(bytes[pos+1]&0xff);
 754         } else if(leadByte==kFourByteValueLead) {
 755             value=((bytes[pos]&0xff)<<16)|((bytes[pos+1]&0xff)<<8)|(bytes[pos+2]&0xff);
 756         } else {
 757             value=(bytes[pos]<<24)|((bytes[pos+1]&0xff)<<16)|((bytes[pos+2]&0xff)<<8)|(bytes[pos+3]&0xff);
 758         }
 759         return value;
 760     }
 761     private static int skipValue(int pos, int leadByte) {
 762         assert(leadByte>=kMinValueLead);
 763         if(leadByte>=(kMinTwoByteValueLead<<1)) {
 764             if(leadByte<(kMinThreeByteValueLead<<1)) {
 765                 ++pos;
 766             } else if(leadByte<(kFourByteValueLead<<1)) {
 767                 pos+=2;
 768             } else {
 769                 pos+=3+((leadByte>>1)&1);
 770             }
 771         }
 772         return pos;
 773     }
 774     private static int skipValue(byte[] bytes, int pos) {
 775         int leadByte=bytes[pos++]&0xff;
 776         return skipValue(pos, leadByte);
 777     }
 778
 779     // Reads a jump delta and jumps.
 780     private static int jumpByDelta(byte[] bytes, int pos) {
 781         int delta=bytes[pos++]&0xff;
 782         if(delta<kMinTwoByteDeltaLead) {
 783             // nothing to do
 784         } else if(delta<kMinThreeByteDeltaLead) {
 785             delta=((delta-kMinTwoByteDeltaLead)<<8)|(bytes[pos++]&0xff);
 786         } else if(delta<kFourByteDeltaLead) {
 787             delta=((delta-kMinThreeByteDeltaLead)<<16)|((bytes[pos]&0xff)<<8)|(bytes[pos+1]&0xff);
 788             pos+=2;
 789         } else if(delta==kFourByteDeltaLead) {
 790             delta=((bytes[pos]&0xff)<<16)|((bytes[pos+1]&0xff)<<8)|(bytes[pos+2]&0xff);
 791             pos+=3;
 792         } else {
 793             delta=(bytes[pos]<<24)|((bytes[pos+1]&0xff)<<16)|((bytes[pos+2]&0xff)<<8)|(bytes[pos+3]&0xff);
 794             pos+=4;
 795         }
 796         return pos+delta;
 797     }
 798
 799     private static int skipDelta(byte[] bytes, int pos) {
 800         int delta=bytes[pos++]&0xff;
 801         if(delta>=kMinTwoByteDeltaLead) {
 802             if(delta<kMinThreeByteDeltaLead) {
 803                 ++pos;
 804             } else if(delta<kFourByteDeltaLead) {
 805                 pos+=2;
 806             } else {
 807                 pos+=3+(delta&1);
 808             }
 809         }
 810         return pos;
 811     }
 812
 813     private static Result[] valueResults_={ Result.INTERMEDIATE_VALUE, Result.FINAL_VALUE };
 814
 815     // Handles a branch node for both next(byte) and next(string).
 816     private Result branchNext(int pos, int length, int inByte) {
 817         // Branch according to the current byte.
 818         if(length==0) {
 819             length=bytes_[pos++]&0xff;
 820         }
 821         ++length;
 822         // The length of the branch is the number of bytes to select from.
 823         // The data structure encodes a binary search.
 824         while(length>kMaxBranchLinearSubNodeLength) {
 825             if(inByte<(bytes_[pos++]&0xff)) {
 826                 length>>=1;
 827                 pos=jumpByDelta(bytes_, pos);
 828             } else {
 829                 length=length-(length>>1);
 830                 pos=skipDelta(bytes_, pos);
 831             }
 832         }
 833         // Drop down to linear search for the last few bytes.
 834         // length>=2 because the loop body above sees length>kMaxBranchLinearSubNodeLength>=3
 835         // and divides length by 2.
 836         do {
 837             if(inByte==(bytes_[pos++]&0xff)) {
 838                 Result result;
 839                 int node=bytes_[pos]&0xff;
 840                 assert(node>=kMinValueLead);
 841                 if((node&kValueIsFinal)!=0) {
 842                     // Leave the final value for getValue() to read.
 843                     result=Result.FINAL_VALUE;
 844                 } else {
 845                     // Use the non-final value as the jump delta.
 846                     ++pos;
 847                     // int delta=readValue(pos, node>>1);
 848                     node>>=1;
 849                     int delta;
 850                     if(node<kMinTwoByteValueLead) {
 851                         delta=node-kMinOneByteValueLead;
 852                     } else if(node<kMinThreeByteValueLead) {
 853                         delta=((node-kMinTwoByteValueLead)<<8)|(bytes_[pos++]&0xff);
 854                     } else if(node<kFourByteValueLead) {
 855                         delta=((node-kMinThreeByteValueLead)<<16)|((bytes_[pos]&0xff)<<8)|(bytes_[pos+1]&0xff);
 856                         pos+=2;
 857                     } else if(node==kFourByteValueLead) {
 858                         delta=((bytes_[pos]&0xff)<<16)|((bytes_[pos+1]&0xff)<<8)|(bytes_[pos+2]&0xff);
 859                         pos+=3;
 860                     } else {
 861                         delta=(bytes_[pos]<<24)|((bytes_[pos+1]&0xff)<<16)|((bytes_[pos+2]&0xff)<<8)|(bytes_[pos+3]&0xff);
 862                         pos+=4;
 863                     }
 864                     // end readValue()
 865                     pos+=delta;
 866                     node=bytes_[pos]&0xff;
 867                     result= node>=kMinValueLead ? valueResults_[node&kValueIsFinal] : Result.NO_VALUE;
 868                 }
 869                 pos_=pos;
 870                 return result;
 871             }
 872             --length;
 873             pos=skipValue(bytes_, pos);
 874         } while(length>1);
 875         if(inByte==(bytes_[pos++]&0xff)) {
 876             pos_=pos;
 877             int node=bytes_[pos]&0xff;
 878             return node>=kMinValueLead ? valueResults_[node&kValueIsFinal] : Result.NO_VALUE;
 879         } else {
 880             stop();
 881             return Result.NO_MATCH;
 882         }
 883     }
 884
 885     // Requires remainingLength_<0.
 886     private Result nextImpl(int pos, int inByte) {
 887         for(;;) {
 888             int node=bytes_[pos++]&0xff;
 889             if(node<kMinLinearMatch) {
 890                 return branchNext(pos, node, inByte);
 891             } else if(node<kMinValueLead) {
 892                 // Match the first of length+1 bytes.
 893                 int length=node-kMinLinearMatch;  // Actual match length minus 1.
 894                 if(inByte==(bytes_[pos++]&0xff)) {
 895                     remainingMatchLength_=--length;
 896                     pos_=pos;
 897                     return (length<0 && (node=bytes_[pos]&0xff)>=kMinValueLead) ?
 898                             valueResults_[node&kValueIsFinal] : Result.NO_VALUE;
 899                 } else {
 900                     // No match.
 901                     break;
 902                 }
 903             } else if((node&kValueIsFinal)!=0) {
 904                 // No further matching bytes.
 905                 break;
 906             } else {
 907                 // Skip intermediate value.
 908                 pos=skipValue(pos, node);
 909                 // The next node must not also be a value node.
 910                 assert((bytes_[pos]&0xff)<kMinValueLead);
 911             }
 912         }
 913         stop();
 914         return Result.NO_MATCH;
 915     }
 916
 917     // Helper functions for getUniqueValue().
 918     // Recursively finds a unique value (or whether there is not a unique one)
 919     // from a branch.
 920     // uniqueValue: On input, same as for getUniqueValue()/findUniqueValue().
 921     // On return, if not 0, then bits 63..33 contain the updated non-negative pos.
 922     private static long findUniqueValueFromBranch(byte[] bytes, int pos, int length,
 923                                                   long uniqueValue) {
 924         while(length>kMaxBranchLinearSubNodeLength) {
 925             ++pos;  // ignore the comparison byte
 926             uniqueValue=findUniqueValueFromBranch(bytes, jumpByDelta(bytes, pos), length>>1, uniqueValue);
 927             if(uniqueValue==0) {
 928                 return 0;
 929             }
 930             length=length-(length>>1);
 931             pos=skipDelta(bytes, pos);
 932         }
 933         do {
 934             ++pos;  // ignore a comparison byte
 935             // handle its value
 936             int node=bytes[pos++]&0xff;
 937             boolean isFinal=(node&kValueIsFinal)!=0;
 938             int value=readValue(bytes, pos, node>>1);
 939             pos=skipValue(pos, node);
 940             if(isFinal) {
 941                 if(uniqueValue!=0) {
 942                     if(value!=(int)(uniqueValue>>1)) {
 943                         return 0;
 944                     }
 945                 } else {
 946                     uniqueValue=((long)value<<1)|1;
 947                 }
 948             } else {
 949                 uniqueValue=findUniqueValue(bytes, pos+value, uniqueValue);
 950                 if(uniqueValue==0) {
 951                     return 0;
 952                 }
 953             }
 954         } while(--length>1);
 955         // ignore the last comparison byte
 956         return ((long)(pos+1)<<33)|(uniqueValue&0x1ffffffffL);
 957     }
 958     // Recursively finds a unique value (or whether there is not a unique one)
 959     // starting from a position on a node lead byte.
 960     // uniqueValue: If there is one, then bits 32..1 contain the value and bit 0 is set.
 961     // Otherwise, uniqueValue is 0. Bits 63..33 are ignored.
 962     private static long findUniqueValue(byte[] bytes, int pos, long uniqueValue) {
 963         for(;;) {
 964             int node=bytes[pos++]&0xff;
 965             if(node<kMinLinearMatch) {
 966                 if(node==0) {
 967                     node=bytes[pos++]&0xff;
 968                 }
 969                 uniqueValue=findUniqueValueFromBranch(bytes, pos, node+1, uniqueValue);
 970                 if(uniqueValue==0) {
 971                     return 0;
 972                 }
 973                 pos=(int)(uniqueValue>>>33);
 974             } else if(node<kMinValueLead) {
 975                 // linear-match node
 976                 pos+=node-kMinLinearMatch+1;  // Ignore the match bytes.
 977             } else {
 978                 boolean isFinal=(node&kValueIsFinal)!=0;
 979                 int value=readValue(bytes, pos, node>>1);
 980                 if(uniqueValue!=0) {
 981                     if(value!=(int)(uniqueValue>>1)) {
 982                         return 0;
 983                     }
 984                 } else {
 985                     uniqueValue=((long)value<<1)|1;
 986                 }
 987                 if(isFinal) {
 988                     return uniqueValue;
 989                 }
 990                 pos=skipValue(pos, node);
 991             }
 992         }
 993     }
 994
 995     // Helper functions for getNextBytes().
 996     // getNextBytes() when pos is on a branch node.
 997     private static void getNextBranchBytes(byte[] bytes, int pos, int length, Appendable out) {
 998         while(length>kMaxBranchLinearSubNodeLength) {
 999             ++pos;  // ignore the comparison byte
1000             getNextBranchBytes(bytes, jumpByDelta(bytes, pos), length>>1, out);
1001             length=length-(length>>1);
1002             pos=skipDelta(bytes, pos);
1003         }
1004         do {
1005             append(out, bytes[pos++]&0xff);
1006             pos=skipValue(bytes, pos);
1007         } while(--length>1);
1008         append(out, bytes[pos]&0xff);
1009     }
1010     private static void append(Appendable out, int c) {
1011         try {
1012             out.append((char)c);
1013         } catch(IOException e) {
1014             throw new RuntimeException(e);
1015         }
1016     }
1017
1018     // BytesTrie data structure
1019     //
1020     // The trie consists of a series of byte-serialized nodes for incremental
1021     // string/byte sequence matching. The root node is at the beginning of the trie data.
1022     //
1023     // Types of nodes are distinguished by their node lead byte ranges.
1024     // After each node, except a final-value node, another node follows to
1025     // encode match values or continue matching further bytes.
1026     //
1027     // Node types:
1028     //  - Value node: Stores a 32-bit integer in a compact, variable-length format.
1029     //    The value is for the string/byte sequence so far.
1030     //    One node bit indicates whether the value is final or whether
1031     //    matching continues with the next node.
1032     //  - Linear-match node: Matches a number of bytes.
1033     //  - Branch node: Branches to other nodes according to the current input byte.
1034     //    The node byte is the length of the branch (number of bytes to select from)
1035     //    minus 1. It is followed by a sub-node:
1036     //    - If the length is at most kMaxBranchLinearSubNodeLength, then
1037     //      there are length-1 (key, value) pairs and then one more comparison byte.
1038     //      If one of the key bytes matches, then the value is either a final value for
1039     //      the string/byte sequence so far, or a "jump" delta to the next node.
1040     //      If the last byte matches, then matching continues with the next node.
1041     //      (Values have the same encoding as value nodes.)
1042     //    - If the length is greater than kMaxBranchLinearSubNodeLength, then
1043     //      there is one byte and one "jump" delta.
1044     //      If the input byte is less than the sub-node byte, then "jump" by delta to
1045     //      the next sub-node which will have a length of length/2.
1046     //      (The delta has its own compact encoding.)
1047     //      Otherwise, skip the "jump" delta to the next sub-node
1048     //      which will have a length of length-length/2.
1049
1050     // Node lead byte values.
1051
1052     // 00..0f: Branch node. If node!=0 then the length is node+1, otherwise
1053     // the length is one more than the next byte.
1054
1055     // For a branch sub-node with at most this many entries, we drop down
1056     // to a linear search.
1057     /*package*/ static final int kMaxBranchLinearSubNodeLength=5;
1058
1059     // 10..1f: Linear-match node, match 1..16 bytes and continue reading the next node.
1060     /*package*/ static final int kMinLinearMatch=0x10;
1061     /*package*/ static final int kMaxLinearMatchLength=0x10;
1062
1063     // 20..ff: Variable-length value node.
1064     // If odd, the value is final. (Otherwise, intermediate value or jump delta.)
1065     // Then shift-right by 1 bit.
1066     // The remaining lead byte value indicates the number of following bytes (0..4)
1067     // and contains the value's top bits.
1068     /*package*/ static final int kMinValueLead=kMinLinearMatch+kMaxLinearMatchLength;  // 0x20
1069     // It is a final value if bit 0 is set.
1070     private static final int kValueIsFinal=1;
1071
1072     // Compact value: After testing bit 0, shift right by 1 and then use the following thresholds.
1073     /*package*/ static final int kMinOneByteValueLead=kMinValueLead/2;  // 0x10
1074     /*package*/ static final int kMaxOneByteValue=0x40;  // At least 6 bits in the first byte.
1075
1076     /*package*/ static final int kMinTwoByteValueLead=kMinOneByteValueLead+kMaxOneByteValue+1;  // 0x51
1077     /*package*/ static final int kMaxTwoByteValue=0x1aff;
1078
1079     /*package*/ static final int kMinThreeByteValueLead=kMinTwoByteValueLead+(kMaxTwoByteValue>>8)+1;  // 0x6c
1080     /*package*/ static final int kFourByteValueLead=0x7e;
1081
1082     // A little more than Unicode code points. (0x11ffff)
1083     /*package*/ static final int kMaxThreeByteValue=((kFourByteValueLead-kMinThreeByteValueLead)<<16)-1;
1084
1085     /*package*/ static final int kFiveByteValueLead=0x7f;
1086
1087     // Compact delta integers.
1088     /*package*/ static final int kMaxOneByteDelta=0xbf;
1089     /*package*/ static final int kMinTwoByteDeltaLead=kMaxOneByteDelta+1;  // 0xc0
1090     /*package*/ static final int kMinThreeByteDeltaLead=0xf0;
1091     /*package*/ static final int kFourByteDeltaLead=0xfe;
1092     /*package*/ static final int kFiveByteDeltaLead=0xff;
1093
1094     /*package*/ static final int kMaxTwoByteDelta=((kMinThreeByteDeltaLead-kMinTwoByteDeltaLead)<<8)-1;  // 0x2fff
1095     /*package*/ static final int kMaxThreeByteDelta=((kFourByteDeltaLead-kMinThreeByteDeltaLead)<<16)-1;  // 0xdffff
1096
1097     // Fixed value referencing the BytesTrie bytes.
1098     private byte[] bytes_;
1099     private int root_;
1100
1101     // Iterator variables.
1102
1103     // Index of next trie byte to read. Negative if no more matches.
1104     private int pos_;
1105     // Remaining length of a linear-match node, minus 1. Negative if not in such a node.
1106     private int remainingMatchLength_;
1107 };