jars/icu4j-52_1/main/classes/core/src/com/ibm/icu/util/StringTrieBuilder.java

   1 /*
   2 *******************************************************************************
   3 *   Copyright (C) 2011-2012, International Business Machines
   4 *   Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 *   created on: 2011jan05
   7 *   created by: Markus W. Scherer
   8 *   ported from ICU4C stringtriebuilder.h/.cpp
   9 */
  10 package com.ibm.icu.util;
  11
  12 import java.util.ArrayList;
  13 import java.util.HashMap;
  14
  15 /**
  16  * Base class for string trie builder classes.
  17  *
  18  * <p>This class is not intended for public subclassing.
  19  *
  20  * @author Markus W. Scherer
  21  * @stable ICU 4.8
  22  */
  23 public abstract class StringTrieBuilder {
  24     /**
  25      * Build options for BytesTrieBuilder and CharsTrieBuilder.
  26      * @stable ICU 4.8
  27      */
  28     public enum Option {
  29         /**
  30          * Builds a trie quickly.
  31          * @stable ICU 4.8
  32          */
  33         FAST,
  34         /**
  35          * Builds a trie more slowly, attempting to generate
  36          * a shorter but equivalent serialization.
  37          * This build option also uses more memory.
  38          *
  39          * <p>This option can be effective when many integer values are the same
  40          * and string/byte sequence suffixes can be shared.
  41          * Runtime speed is not expected to improve.
  42          * @stable ICU 4.8
  43          */
  44         SMALL
  45     }
  46
  47     /**
  48      * @internal
  49      * @deprecated This API is ICU internal only.
  50      */
  51     protected StringTrieBuilder() {}
  52
  53     /**
  54      * @internal
  55      * @deprecated This API is ICU internal only.
  56      */
  57     protected void addImpl(CharSequence s, int value) {
  58         if(state!=State.ADDING) {
  59             // Cannot add elements after building.
  60             throw new IllegalStateException("Cannot add (string, value) pairs after build().");
  61         }
  62         if(s.length()>0xffff) {
  63             // Too long: Limited by iterator internals, and by builder recursion depth.
  64             throw new IndexOutOfBoundsException("The maximum string length is 0xffff.");
  65         }
  66         if(root==null) {
  67             root=createSuffixNode(s, 0, value);
  68         } else {
  69             root=root.add(this, s, 0, value);
  70         }
  71     }
  72
  73     /**
  74      * @internal
  75      * @deprecated This API is ICU internal only.
  76      */
  77     protected final void buildImpl(Option buildOption) {
  78         switch(state) {
  79         case ADDING:
  80             if(root==null) {
  81                 throw new IndexOutOfBoundsException("No (string, value) pairs were added.");
  82             }
  83             if(buildOption==Option.FAST) {
  84                 state=State.BUILDING_FAST;
  85                 // Building "fast" is somewhat faster (25..50% in some test)
  86                 // because it makes registerNode() return the input node
  87                 // rather than checking for duplicates.
  88                 // As a result, we sometimes write larger trie serializations.
  89                 //
  90                 // In either case we need to fix-up linear-match nodes (for their maximum length)
  91                 // and branch nodes (turning dynamic branch nodes into trees of
  92                 // runtime-equivalent nodes), but the HashMap/hashCode()/equals() are omitted for
  93                 // nodes other than final values.
  94             } else {
  95                 state=State.BUILDING_SMALL;
  96             }
  97             break;
  98         case BUILDING_FAST:
  99         case BUILDING_SMALL:
 100             // Building must have failed.
 101             throw new IllegalStateException("Builder failed and must be clear()ed.");
 102         case BUILT:
 103             return;  // Nothing more to do.
 104         }
 105         // Implementation note:
 106         // We really build three versions of the trie.
 107         // The first is a fully dynamic trie, built successively by addImpl().
 108         // Then we call root.register() to turn it into a tree of nodes
 109         // which is 1:1 equivalent to the runtime data structure.
 110         // Finally, root.markRightEdgesFirst() and root.write() write that serialized form.
 111         root=root.register(this);
 112         root.markRightEdgesFirst(-1);
 113         root.write(this);
 114         state=State.BUILT;
 115     }
 116
 117     /**
 118      * @internal
 119      * @deprecated This API is ICU internal only.
 120      */
 121     protected void clearImpl() {
 122         strings.setLength(0);
 123         nodes.clear();
 124         root=null;
 125         state=State.ADDING;
 126     }
 127
 128     /**
 129      * Makes sure that there is only one unique node registered that is
 130      * equivalent to newNode, unless BUILDING_FAST.
 131      * @param newNode Input node. The builder takes ownership.
 132      * @return newNode if it is the first of its kind, or
 133      *         an equivalent node if newNode is a duplicate.
 134      */
 135     private final Node registerNode(Node newNode) {
 136         if(state==State.BUILDING_FAST) {
 137             return newNode;
 138         }
 139         // BUILDING_SMALL
 140         Node oldNode=nodes.get(newNode);
 141         if(oldNode!=null) {
 142             return oldNode;
 143         }
 144         // If put() returns a non-null value from an equivalent, previously
 145         // registered node, then get() failed to find that and we will leak newNode.
 146         oldNode=nodes.put(newNode, newNode);
 147         assert(oldNode==null);
 148         return newNode;
 149     }
 150
 151     /**
 152      * Makes sure that there is only one unique FinalValueNode registered
 153      * with this value.
 154      * Avoids creating a node if the value is a duplicate.
 155      * @param value A final value.
 156      * @return A FinalValueNode with the given value.
 157      */
 158     private final ValueNode registerFinalValue(int value) {
 159         // We always register final values because while ADDING
 160         // we do not know yet whether we will build fast or small.
 161         lookupFinalValueNode.setFinalValue(value);
 162         Node oldNode=nodes.get(lookupFinalValueNode);
 163         if(oldNode!=null) {
 164             return (ValueNode)oldNode;
 165         }
 166         ValueNode newNode=new ValueNode(value);
 167         // If put() returns a non-null value from an equivalent, previously
 168         // registered node, then get() failed to find that and we will leak newNode.
 169         oldNode=nodes.put(newNode, newNode);
 170         assert(oldNode==null);
 171         return newNode;
 172     }
 173
 174     private static abstract class Node {
 175         public Node() {
 176             offset=0;
 177         }
 178         // hashCode() and equals() for use with registerNode() and the nodes hash.
 179         @Override
 180         public abstract int hashCode() /*const*/;
 181         // Base class equals() compares the actual class types.
 182         @Override
 183         public boolean equals(Object other) {
 184             return this==other || this.getClass()==other.getClass();
 185         }
 186         /**
 187          * Recursive method for adding a new (string, value) pair.
 188          * Matches the remaining part of s from start,
 189          * and adds a new node where there is a mismatch.
 190          * @return this or a replacement Node
 191          */
 192         public Node add(StringTrieBuilder builder, CharSequence s, int start, int sValue) {
 193             return this;
 194         }
 195         /**
 196          * Recursive method for registering unique nodes,
 197          * after all (string, value) pairs have been added.
 198          * Final-value nodes are pre-registered while add()ing (string, value) pairs.
 199          * Other nodes created while add()ing registerNode() themselves later
 200          * and might replace themselves with new types of nodes for write()ing.
 201          * @return The registered version of this node which implements write().
 202          */
 203         public Node register(StringTrieBuilder builder) { return this; }
 204         /**
 205          * Traverses the Node graph and numbers branch edges, with rightmost edges first.
 206          * This is to avoid writing a duplicate node twice.
 207          *
 208          * Branch nodes in this trie data structure are not symmetric.
 209          * Most branch edges "jump" to other nodes but the rightmost branch edges
 210          * just continue without a jump.
 211          * Therefore, write() must write the rightmost branch edge last
 212          * (trie units are written backwards), and must write it at that point even if
 213          * it is a duplicate of a node previously written elsewhere.
 214          *
 215          * This function visits and marks right branch edges first.
 216          * Edges are numbered with increasingly negative values because we share the
 217          * offset field which gets positive values when nodes are written.
 218          * A branch edge also remembers the first number for any of its edges.
 219          *
 220          * When a further-left branch edge has a number in the range of the rightmost
 221          * edge's numbers, then it will be written as part of the required right edge
 222          * and we can avoid writing it first.
 223          *
 224          * After root.markRightEdgesFirst(-1) the offsets of all nodes are negative
 225          * edge numbers.
 226          *
 227          * @param edgeNumber The first edge number for this node and its sub-nodes.
 228          * @return An edge number that is at least the maximum-negative
 229          *         of the input edge number and the numbers of this node and all of its sub-nodes.
 230          */
 231         public int markRightEdgesFirst(int edgeNumber) {
 232             if(offset==0) {
 233                 offset=edgeNumber;
 234             }
 235             return edgeNumber;
 236         }
 237         // write() must set the offset to a positive value.
 238         public abstract void write(StringTrieBuilder builder);
 239         // See markRightEdgesFirst.
 240         public final void writeUnlessInsideRightEdge(int firstRight, int lastRight,
 241                                                StringTrieBuilder builder) {
 242             // Note: Edge numbers are negative, lastRight<=firstRight.
 243             // If offset>0 then this node and its sub-nodes have been written already
 244             // and we need not write them again.
 245             // If this node is part of the unwritten right branch edge,
 246             // then we wait until that is written.
 247             if(offset<0 && (offset<lastRight || firstRight<offset)) {
 248                 write(builder);
 249             }
 250         }
 251         public final int getOffset() /*const*/ { return offset; }
 252
 253         protected int offset;
 254     }
 255
 256     // Used directly for final values, and as as a superclass for
 257     // match nodes with intermediate values.
 258     private static class ValueNode extends Node {
 259         public ValueNode() {}
 260         public ValueNode(int v) {
 261             hasValue=true;
 262             value=v;
 263         }
 264         public final void setValue(int v) {
 265             assert(!hasValue);
 266             hasValue=true;
 267             value=v;
 268         }
 269         private void setFinalValue(int v) {
 270             hasValue=true;
 271             value=v;
 272         }
 273         @Override
 274         public int hashCode() /*const*/ {
 275             int hash=0x111111;
 276             if(hasValue) {
 277                 hash=hash*37+value;
 278             }
 279             return hash;
 280         }
 281         @Override
 282         public boolean equals(Object other) {
 283             if(this==other) {
 284                 return true;
 285             }
 286             if(!super.equals(other)) {
 287                 return false;
 288             }
 289             ValueNode o=(ValueNode)other;
 290             return hasValue==o.hasValue && (!hasValue || value==o.value);
 291         }
 292         @Override
 293         public Node add(StringTrieBuilder builder, CharSequence s, int start, int sValue) {
 294             if(start==s.length()) {
 295                 throw new IllegalArgumentException("Duplicate string.");
 296             }
 297             // Replace self with a node for the remaining string suffix and value.
 298             ValueNode node=builder.createSuffixNode(s, start, sValue);
 299             node.setValue(value);
 300             return node;
 301         }
 302         @Override
 303         public void write(StringTrieBuilder builder) {
 304             offset=builder.writeValueAndFinal(value, true);
 305         }
 306
 307         protected boolean hasValue;
 308         protected int value;
 309     }
 310
 311     private static final class IntermediateValueNode extends ValueNode {
 312         public IntermediateValueNode(int v, Node nextNode) {
 313             next=nextNode;
 314             setValue(v);
 315         }
 316         @Override
 317         public int hashCode() /*const*/ {
 318             return (0x222222*37+value)*37+next.hashCode();
 319         }
 320         @Override
 321         public boolean equals(Object other) {
 322             if(this==other) {
 323                 return true;
 324             }
 325             if(!super.equals(other)) {
 326                 return false;
 327             }
 328             IntermediateValueNode o=(IntermediateValueNode)other;
 329             return next==o.next;
 330         }
 331         @Override
 332         public int markRightEdgesFirst(int edgeNumber) {
 333             if(offset==0) {
 334                 offset=edgeNumber=next.markRightEdgesFirst(edgeNumber);
 335             }
 336             return edgeNumber;
 337         }
 338         @Override
 339         public void write(StringTrieBuilder builder) {
 340             next.write(builder);
 341             offset=builder.writeValueAndFinal(value, false);
 342         }
 343
 344         private Node next;
 345     }
 346
 347     private static final class LinearMatchNode extends ValueNode {
 348         public LinearMatchNode(CharSequence builderStrings, int sOffset, int len, Node nextNode) {
 349             strings=builderStrings;
 350             stringOffset=sOffset;
 351             length=len;
 352             next=nextNode;
 353         }
 354         @Override
 355         public int hashCode() /*const*/ { return hash; }
 356         @Override
 357         public boolean equals(Object other) {
 358             if(this==other) {
 359                 return true;
 360             }
 361             if(!super.equals(other)) {
 362                 return false;
 363             }
 364             LinearMatchNode o=(LinearMatchNode)other;
 365             if(length!=o.length || next!=o.next) {
 366                 return false;
 367             }
 368             for(int i=stringOffset, j=o.stringOffset, limit=stringOffset+length; i<limit; ++i, ++j) {
 369                 if(strings.charAt(i)!=strings.charAt(j)) {
 370                     return false;
 371                 }
 372             }
 373             return true;
 374         }
 375         @Override
 376         public Node add(StringTrieBuilder builder, CharSequence s, int start, int sValue) {
 377             if(start==s.length()) {
 378                 if(hasValue) {
 379                     throw new IllegalArgumentException("Duplicate string.");
 380                 } else {
 381                     setValue(sValue);
 382                     return this;
 383                 }
 384             }
 385             int limit=stringOffset+length;
 386             for(int i=stringOffset; i<limit; ++i, ++start) {
 387                 if(start==s.length()) {
 388                     // s is a prefix with a new value. Split self into two linear-match nodes.
 389                     int prefixLength=i-stringOffset;
 390                     LinearMatchNode suffixNode=new LinearMatchNode(strings, i, length-prefixLength, next);
 391                     suffixNode.setValue(sValue);
 392                     length=prefixLength;
 393                     next=suffixNode;
 394                     return this;
 395                 }
 396                 char thisChar=strings.charAt(i);
 397                 char newChar=s.charAt(start);
 398                 if(thisChar!=newChar) {
 399                     // Mismatch, insert a branch node.
 400                     DynamicBranchNode branchNode=new DynamicBranchNode();
 401                     // Reuse this node for one of the remaining substrings, if any.
 402                     Node result, thisSuffixNode;
 403                     if(i==stringOffset) {
 404                         // Mismatch on first character, turn this node into a suffix.
 405                         if(hasValue) {
 406                             // Move the value for prefix length "start" to the new node.
 407                             branchNode.setValue(value);
 408                             value=0;
 409                             hasValue=false;
 410                         }
 411                         ++stringOffset;
 412                         --length;
 413                         thisSuffixNode= length>0 ? this : next;
 414                         // C++: if(length==0) { delete this; }
 415                         result=branchNode;
 416                     } else if(i==limit-1) {
 417                         // Mismatch on last character, keep this node for the prefix.
 418                         --length;
 419                         thisSuffixNode=next;
 420                         next=branchNode;
 421                         result=this;
 422                     } else {
 423                         // Mismatch on intermediate character, keep this node for the prefix.
 424                         int prefixLength=i-stringOffset;
 425                         ++i;  // Suffix start offset (after thisChar).
 426                         thisSuffixNode=new LinearMatchNode(
 427                                 strings, i, length-(prefixLength+1), next);
 428                         length=prefixLength;
 429                         next=branchNode;
 430                         result=this;
 431                     }
 432                     ValueNode newSuffixNode=builder.createSuffixNode(s, start+1, sValue);
 433                     branchNode.add(thisChar, thisSuffixNode);
 434                     branchNode.add(newChar, newSuffixNode);
 435                     return result;
 436                 }
 437             }
 438             // s matches all of this node's characters.
 439             next=next.add(builder, s, start, sValue);
 440             return this;
 441         }
 442         @Override
 443         public Node register(StringTrieBuilder builder) {
 444             next=next.register(builder);
 445             // Break the linear-match sequence into chunks of at most kMaxLinearMatchLength.
 446             int maxLinearMatchLength=builder.getMaxLinearMatchLength();
 447             while(length>maxLinearMatchLength) {
 448                 int nextOffset=stringOffset+length-maxLinearMatchLength;
 449                 length-=maxLinearMatchLength;
 450                 LinearMatchNode suffixNode=
 451                     new LinearMatchNode(strings, nextOffset, maxLinearMatchLength, next);
 452                 suffixNode.setHashCode();
 453                 next=builder.registerNode(suffixNode);
 454             }
 455             Node result;
 456             if(hasValue && !builder.matchNodesCanHaveValues()) {
 457                 int intermediateValue=value;
 458                 value=0;
 459                 hasValue=false;
 460                 setHashCode();
 461                 result=new IntermediateValueNode(intermediateValue, builder.registerNode(this));
 462             } else {
 463                 setHashCode();
 464                 result=this;
 465             }
 466             return builder.registerNode(result);
 467         }
 468         @Override
 469         public int markRightEdgesFirst(int edgeNumber) {
 470             if(offset==0) {
 471                 offset=edgeNumber=next.markRightEdgesFirst(edgeNumber);
 472             }
 473             return edgeNumber;
 474         }
 475         @Override
 476         public void write(StringTrieBuilder builder) {
 477             next.write(builder);
 478             builder.write(stringOffset, length);
 479             offset=builder.writeValueAndType(hasValue, value, builder.getMinLinearMatch()+length-1);
 480         }
 481
 482         // Must be called just before registerNode(this).
 483         private void setHashCode() /*const*/ {
 484             hash=(0x333333*37+length)*37+next.hashCode();
 485             if(hasValue) {
 486                 hash=hash*37+value;
 487             }
 488             for(int i=stringOffset, limit=stringOffset+length; i<limit; ++i) {
 489                 hash=hash*37+strings.charAt(i);
 490             }
 491         }
 492
 493         private CharSequence strings;
 494         private int stringOffset;
 495         private int length;
 496         private Node next;
 497         private int hash;
 498     }
 499
 500     private static final class DynamicBranchNode extends ValueNode {
 501         public DynamicBranchNode() {}
 502         // c must not be in chars yet.
 503         public void add(char c, Node node) {
 504             int i=find(c);
 505             chars.insert(i, c);
 506             equal.add(i, node);
 507         }
 508         @Override
 509         public Node add(StringTrieBuilder builder, CharSequence s, int start, int sValue) {
 510             if(start==s.length()) {
 511                 if(hasValue) {
 512                     throw new IllegalArgumentException("Duplicate string.");
 513                 } else {
 514                     setValue(sValue);
 515                     return this;
 516                 }
 517             }
 518             char c=s.charAt(start++);
 519             int i=find(c);
 520             if(i<chars.length() && c==chars.charAt(i)) {
 521                 equal.set(i, equal.get(i).add(builder, s, start, sValue));
 522             } else {
 523                 chars.insert(i, c);
 524                 equal.add(i, builder.createSuffixNode(s, start, sValue));
 525             }
 526             return this;
 527         }
 528         @Override
 529         public Node register(StringTrieBuilder builder) {
 530             Node subNode=register(builder, 0, chars.length());
 531             BranchHeadNode head=new BranchHeadNode(chars.length(), subNode);
 532             Node result=head;
 533             if(hasValue) {
 534                 if(builder.matchNodesCanHaveValues()) {
 535                     head.setValue(value);
 536                 } else {
 537                     result=new IntermediateValueNode(value, builder.registerNode(head));
 538                 }
 539             }
 540             return builder.registerNode(result);
 541         }
 542         private Node register(StringTrieBuilder builder, int start, int limit) {
 543             int length=limit-start;
 544             if(length>builder.getMaxBranchLinearSubNodeLength()) {
 545                 // Branch on the middle unit.
 546                 int middle=start+length/2;
 547                 return builder.registerNode(
 548                         new SplitBranchNode(
 549                                 chars.charAt(middle),
 550                                 register(builder, start, middle),
 551                                 register(builder, middle, limit)));
 552             }
 553             ListBranchNode listNode=new ListBranchNode(length);
 554             do {
 555                 char c=chars.charAt(start);
 556                 Node node=equal.get(start);
 557                 if(node.getClass()==ValueNode.class) {
 558                     // Final value.
 559                     listNode.add(c, ((ValueNode)node).value);
 560                 } else {
 561                     listNode.add(c, node.register(builder));
 562                 }
 563             } while(++start<limit);
 564             return builder.registerNode(listNode);
 565         }
 566
 567         private int find(char c) {
 568             int start=0;
 569             int limit=chars.length();
 570             while(start<limit) {
 571                 int i=(start+limit)/2;
 572                 char middleChar=chars.charAt(i);
 573                 if(c<middleChar) {
 574                     limit=i;
 575                 } else if(c==middleChar) {
 576                     return i;
 577                 } else {
 578                     start=i+1;
 579                 }
 580             }
 581             return start;
 582         }
 583
 584         private StringBuilder chars=new StringBuilder();
 585         private ArrayList<Node> equal=new ArrayList<Node>();
 586     }
 587
 588     private static abstract class BranchNode extends Node {
 589         public BranchNode() {}
 590         @Override
 591         public int hashCode() /*const*/ { return hash; }
 592
 593         protected int hash;
 594         protected int firstEdgeNumber;
 595     }
 596
 597     private static final class ListBranchNode extends BranchNode {
 598         public ListBranchNode(int capacity) {
 599             hash=0x444444*37+capacity;
 600             equal=new Node[capacity];
 601             values=new int[capacity];
 602             units=new char[capacity];
 603         }
 604         @Override
 605         public boolean equals(Object other) {
 606             if(this==other) {
 607                 return true;
 608             }
 609             if(!super.equals(other)) {
 610                 return false;
 611             }
 612             ListBranchNode o=(ListBranchNode)other;
 613             for(int i=0; i<length; ++i) {
 614                 if(units[i]!=o.units[i] || values[i]!=o.values[i] || equal[i]!=o.equal[i]) {
 615                     return false;
 616                 }
 617             }
 618             return true;
 619         }
 620         @Override
 621         public int hashCode() {
 622             return super.hashCode();
 623         }
 624         @Override
 625         public int markRightEdgesFirst(int edgeNumber) {
 626             if(offset==0) {
 627                 firstEdgeNumber=edgeNumber;
 628                 int step=0;
 629                 int i=length;
 630                 do {
 631                     Node edge=equal[--i];
 632                     if(edge!=null) {
 633                         edgeNumber=edge.markRightEdgesFirst(edgeNumber-step);
 634                     }
 635                     // For all but the rightmost edge, decrement the edge number.
 636                     step=1;
 637                 } while(i>0);
 638                 offset=edgeNumber;
 639             }
 640             return edgeNumber;
 641         }
 642         @Override
 643         public void write(StringTrieBuilder builder) {
 644             // Write the sub-nodes in reverse order: The jump lengths are deltas from
 645             // after their own positions, so if we wrote the minUnit sub-node first,
 646             // then its jump delta would be larger.
 647             // Instead we write the minUnit sub-node last, for a shorter delta.
 648             int unitNumber=length-1;
 649             Node rightEdge=equal[unitNumber];
 650             int rightEdgeNumber= rightEdge==null ? firstEdgeNumber : rightEdge.getOffset();
 651             do {
 652                 --unitNumber;
 653                 if(equal[unitNumber]!=null) {
 654                     equal[unitNumber].writeUnlessInsideRightEdge(firstEdgeNumber, rightEdgeNumber, builder);
 655                 }
 656             } while(unitNumber>0);
 657             // The maxUnit sub-node is written as the very last one because we do
 658             // not jump for it at all.
 659             unitNumber=length-1;
 660             if(rightEdge==null) {
 661                 builder.writeValueAndFinal(values[unitNumber], true);
 662             } else {
 663                 rightEdge.write(builder);
 664             }
 665             offset=builder.write(units[unitNumber]);
 666             // Write the rest of this node's unit-value pairs.
 667             while(--unitNumber>=0) {
 668                 int value;
 669                 boolean isFinal;
 670                 if(equal[unitNumber]==null) {
 671                     // Write the final value for the one string ending with this unit.
 672                     value=values[unitNumber];
 673                     isFinal=true;
 674                 } else {
 675                     // Write the delta to the start position of the sub-node.
 676                     assert(equal[unitNumber].getOffset()>0);
 677                     value=offset-equal[unitNumber].getOffset();
 678                     isFinal=false;
 679                 }
 680                 builder.writeValueAndFinal(value, isFinal);
 681                 offset=builder.write(units[unitNumber]);
 682             }
 683         }
 684         // Adds a unit with a final value.
 685         public void add(int c, int value) {
 686             units[length]=(char)c;
 687             equal[length]=null;
 688             values[length]=value;
 689             ++length;
 690             hash=(hash*37+c)*37+value;
 691         }
 692         // Adds a unit which leads to another match node.
 693         public void add(int c, Node node) {
 694             units[length]=(char)c;
 695             equal[length]=node;
 696             values[length]=0;
 697             ++length;
 698             hash=(hash*37+c)*37+node.hashCode();
 699         }
 700
 701         // Note: We could try to reduce memory allocations
 702         // by replacing these per-node arrays with per-builder ArrayLists and
 703         // (for units) a StringBuilder (or even use its strings for the units too).
 704         // It remains to be seen whether that would improve performance.
 705         private Node[] equal;  // null means "has final value".
 706         private int length;
 707         private int[] values;
 708         private char[] units;
 709     }
 710
 711     private static final class SplitBranchNode extends BranchNode {
 712         public SplitBranchNode(char middleUnit, Node lessThanNode, Node greaterOrEqualNode) {
 713             hash=((0x555555*37+middleUnit)*37+
 714                     lessThanNode.hashCode())*37+greaterOrEqualNode.hashCode();
 715             unit=middleUnit;
 716             lessThan=lessThanNode;
 717             greaterOrEqual=greaterOrEqualNode;
 718         }
 719         @Override
 720         public boolean equals(Object other) {
 721             if(this==other) {
 722                 return true;
 723             }
 724             if(!super.equals(other)) {
 725                 return false;
 726             }
 727             SplitBranchNode o=(SplitBranchNode)other;
 728             return unit==o.unit && lessThan==o.lessThan && greaterOrEqual==o.greaterOrEqual;
 729         }
 730         @Override
 731         public int hashCode() {
 732             return super.hashCode();
 733         }
 734         @Override
 735         public int markRightEdgesFirst(int edgeNumber) {
 736             if(offset==0) {
 737                 firstEdgeNumber=edgeNumber;
 738                 edgeNumber=greaterOrEqual.markRightEdgesFirst(edgeNumber);
 739                 offset=edgeNumber=lessThan.markRightEdgesFirst(edgeNumber-1);
 740             }
 741             return edgeNumber;
 742         }
 743         @Override
 744         public void write(StringTrieBuilder builder) {
 745             // Encode the less-than branch first.
 746             lessThan.writeUnlessInsideRightEdge(firstEdgeNumber, greaterOrEqual.getOffset(), builder);
 747             // Encode the greater-or-equal branch last because we do not jump for it at all.
 748             greaterOrEqual.write(builder);
 749             // Write this node.
 750             assert(lessThan.getOffset()>0);
 751             builder.writeDeltaTo(lessThan.getOffset());  // less-than
 752             offset=builder.write(unit);
 753         }
 754
 755         private char unit;
 756         private Node lessThan;
 757         private Node greaterOrEqual;
 758     }
 759
 760     // Branch head node, for writing the actual node lead unit.
 761     private static final class BranchHeadNode extends ValueNode {
 762         public BranchHeadNode(int len, Node subNode) {
 763             length=len;
 764             next=subNode;
 765         }
 766         @Override
 767         public int hashCode() /*const*/ {
 768             return (0x666666*37+length)*37+next.hashCode();
 769         }
 770         @Override
 771         public boolean equals(Object other) {
 772             if(this==other) {
 773                 return true;
 774             }
 775             if(!super.equals(other)) {
 776                 return false;
 777             }
 778             BranchHeadNode o=(BranchHeadNode)other;
 779             return length==o.length && next==o.next;
 780         }
 781         @Override
 782         public int markRightEdgesFirst(int edgeNumber) {
 783             if(offset==0) {
 784                 offset=edgeNumber=next.markRightEdgesFirst(edgeNumber);
 785             }
 786             return edgeNumber;
 787         }
 788         @Override
 789         public void write(StringTrieBuilder builder) {
 790             next.write(builder);
 791             if(length<=builder.getMinLinearMatch()) {
 792                 offset=builder.writeValueAndType(hasValue, value, length-1);
 793             } else {
 794                 builder.write(length-1);
 795                 offset=builder.writeValueAndType(hasValue, value, 0);
 796             }
 797         }
 798
 799         private int length;
 800         private Node next;  // A branch sub-node.
 801     }
 802
 803     private ValueNode createSuffixNode(CharSequence s, int start, int sValue) {
 804         ValueNode node=registerFinalValue(sValue);
 805         if(start<s.length()) {
 806             int offset=strings.length();
 807             strings.append(s, start, s.length());
 808             node=new LinearMatchNode(strings, offset, s.length()-start, node);
 809         }
 810         return node;
 811     }
 812
 813     /**
 814      * @internal
 815      * @deprecated This API is ICU internal only.
 816      */
 817     protected abstract boolean matchNodesCanHaveValues() /*const*/;
 818
 819     /**
 820      * @internal
 821      * @deprecated This API is ICU internal only.
 822      */
 823     protected abstract int getMaxBranchLinearSubNodeLength() /*const*/;
 824     /**
 825      * @internal
 826      * @deprecated This API is ICU internal only.
 827      */
 828     protected abstract int getMinLinearMatch() /*const*/;
 829     /**
 830      * @internal
 831      * @deprecated This API is ICU internal only.
 832      */
 833     protected abstract int getMaxLinearMatchLength() /*const*/;
 834
 835     /**
 836      * @internal
 837      * @deprecated This API is ICU internal only.
 838      */
 839     protected abstract int write(int unit);
 840     /**
 841      * @internal
 842      * @deprecated This API is ICU internal only.
 843      */
 844     protected abstract int write(int offset, int length);
 845     /**
 846      * @internal
 847      * @deprecated This API is ICU internal only.
 848      */
 849     protected abstract int writeValueAndFinal(int i, boolean isFinal);
 850     /**
 851      * @internal
 852      * @deprecated This API is ICU internal only.
 853      */
 854     protected abstract int writeValueAndType(boolean hasValue, int value, int node);
 855     /**
 856      * @internal
 857      * @deprecated This API is ICU internal only.
 858      */
 859     protected abstract int writeDeltaTo(int jumpTarget);
 860
 861     private enum State {
 862         ADDING, BUILDING_FAST, BUILDING_SMALL, BUILT
 863     }
 864     private State state=State.ADDING;
 865
 866     // Strings and sub-strings for linear-match nodes.
 867     /**
 868      * @internal
 869      * @deprecated This API is ICU internal only.
 870      */
 871     protected StringBuilder strings=new StringBuilder();
 872     private Node root;
 873
 874     // Hash set of nodes, maps from nodes to integer 1.
 875     private HashMap<Node, Node> nodes=new HashMap<Node, Node>();
 876     private ValueNode lookupFinalValueNode=new ValueNode();
 877 }