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

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