jars/icu4j-52_1/main/tests/core/src/com/ibm/icu/dev/test/util/CharsTrieTest.java

   1 /*
   2 *******************************************************************************
   3 *   Copyright (C) 2011, International Business Machines
   4 *   Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 *   created on: 2011jan10
   7 *   created by: Markus W. Scherer
   8 *   ported from ICU4C ucharstrietest.h/.cpp
   9 */
  10
  11 package com.ibm.icu.dev.test.util;
  12
  13 import java.util.NoSuchElementException;
  14
  15 import com.ibm.icu.dev.test.TestFmwk;
  16 import com.ibm.icu.text.UnicodeSet;
  17 import com.ibm.icu.util.BytesTrie;
  18 import com.ibm.icu.util.CharsTrie;
  19 import com.ibm.icu.util.CharsTrieBuilder;
  20 import com.ibm.icu.util.StringTrieBuilder;
  21
  22 public class CharsTrieTest extends TestFmwk {
  23     public static void main(String[] args) throws Exception {
  24         new CharsTrieTest().run(args);
  25     }
  26     public CharsTrieTest() {}
  27
  28     // All test functions have a TestNN prefix where NN is a double-digit number.
  29     // This is so that when tests are run in sorted order
  30     // the simpler ones are run first.
  31     // If there is a problem, the simpler ones are easier to step through.
  32
  33     public void Test00Builder() {
  34         builder_.clear();
  35         try {
  36             builder_.build(StringTrieBuilder.Option.FAST);
  37             errln("CharsTrieBuilder().build() did not throw IndexOutOfBoundsException");
  38             return;
  39         } catch(IndexOutOfBoundsException e) {
  40             // good
  41         }
  42         try {
  43             builder_.add("=", 0).add("=", 1);
  44             errln("CharsTrieBuilder.add() did not detect duplicates");
  45             return;
  46         } catch(IllegalArgumentException e) {
  47             // good
  48         }
  49     }
  50
  51     private static final class StringAndValue {
  52         public StringAndValue(String str, int val) {
  53             s=str;
  54             value=val;
  55         }
  56
  57         public String s;
  58         public int value;
  59     }
  60     // Note: C++ StringAndValue initializers converted to Java syntax
  61     // with Eclipse Find/Replace regular expressions:
  62     // Find:            \{ (".*", [-0-9xa-fA-F]+) \}
  63     // Replace with:    new StringAndValue($1)
  64
  65     public void Test10Empty() {
  66         final StringAndValue[] data={
  67             new StringAndValue("", 0)
  68         };
  69         checkData(data);
  70     }
  71
  72     public void Test11_a() {
  73         final StringAndValue[] data={
  74             new StringAndValue("a", 1)
  75         };
  76         checkData(data);
  77     }
  78
  79     public void Test12_a_ab() {
  80         final StringAndValue[] data={
  81             new StringAndValue("a", 1),
  82             new StringAndValue("ab", 100)
  83         };
  84         checkData(data);
  85     }
  86
  87     public void Test20ShortestBranch() {
  88         final StringAndValue[] data={
  89             new StringAndValue("a", 1000),
  90             new StringAndValue("b", 2000)
  91         };
  92         checkData(data);
  93     }
  94
  95     public void Test21Branches() {
  96         final StringAndValue[] data={
  97             new StringAndValue("a", 0x10),
  98             new StringAndValue("cc", 0x40),
  99             new StringAndValue("e", 0x100),
 100             new StringAndValue("ggg", 0x400),
 101             new StringAndValue("i", 0x1000),
 102             new StringAndValue("kkkk", 0x4000),
 103             new StringAndValue("n", 0x10000),
 104             new StringAndValue("ppppp", 0x40000),
 105             new StringAndValue("r", 0x100000),
 106             new StringAndValue("sss", 0x200000),
 107             new StringAndValue("t", 0x400000),
 108             new StringAndValue("uu", 0x800000),
 109             new StringAndValue("vv", 0x7fffffff),
 110             new StringAndValue("zz", 0x80000000)
 111         };
 112         for(int length=2; length<=data.length; ++length) {
 113             logln("TestBranches length="+length);
 114             checkData(data, length);
 115         }
 116     }
 117
 118     public void Test22LongSequence() {
 119         final StringAndValue[] data={
 120             new StringAndValue("a", -1),
 121             // sequence of linear-match nodes
 122             new StringAndValue("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", -2),
 123             // more than 256 units
 124             new StringAndValue(
 125                 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"+
 126                 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"+
 127                 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"+
 128                 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"+
 129                 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"+
 130                 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", -3)
 131         };
 132         checkData(data);
 133     }
 134
 135     public void Test23LongBranch() {
 136         // Split-branch and interesting compact-integer values.
 137         final StringAndValue[] data={
 138             new StringAndValue("a", -2),
 139             new StringAndValue("b", -1),
 140             new StringAndValue("c", 0),
 141             new StringAndValue("d2", 1),
 142             new StringAndValue("f", 0x3f),
 143             new StringAndValue("g", 0x40),
 144             new StringAndValue("h", 0x41),
 145             new StringAndValue("j23", 0x1900),
 146             new StringAndValue("j24", 0x19ff),
 147             new StringAndValue("j25", 0x1a00),
 148             new StringAndValue("k2", 0x1a80),
 149             new StringAndValue("k3", 0x1aff),
 150             new StringAndValue("l234567890", 0x1b00),
 151             new StringAndValue("l234567890123", 0x1b01),
 152             new StringAndValue("nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn", 0x10ffff),
 153             new StringAndValue("oooooooooooooooooooooooooooooooooooooooooooooooooooooo", 0x110000),
 154             new StringAndValue("pppppppppppppppppppppppppppppppppppppppppppppppppppppp", 0x120000),
 155             new StringAndValue("r", 0x333333),
 156             new StringAndValue("s2345", 0x4444444),
 157             new StringAndValue("t234567890", 0x77777777),
 158             new StringAndValue("z", 0x80000001)
 159         };
 160         checkData(data);
 161     }
 162
 163     public void Test24ValuesForState() {
 164         // Check that saveState() and resetToState() interact properly
 165         // with next() and current().
 166         final StringAndValue[] data={
 167             new StringAndValue("a", -1),
 168             new StringAndValue("ab", -2),
 169             new StringAndValue("abc", -3),
 170             new StringAndValue("abcd", -4),
 171             new StringAndValue("abcde", -5),
 172             new StringAndValue("abcdef", -6)
 173         };
 174         checkData(data);
 175     }
 176
 177     public void Test30Compact() {
 178         // Duplicate trailing strings and values provide opportunities for compacting.
 179         final StringAndValue[] data={
 180             new StringAndValue("+", 0),
 181             new StringAndValue("+august", 8),
 182             new StringAndValue("+december", 12),
 183             new StringAndValue("+july", 7),
 184             new StringAndValue("+june", 6),
 185             new StringAndValue("+november", 11),
 186             new StringAndValue("+october", 10),
 187             new StringAndValue("+september", 9),
 188             new StringAndValue("-", 0),
 189             new StringAndValue("-august", 8),
 190             new StringAndValue("-december", 12),
 191             new StringAndValue("-july", 7),
 192             new StringAndValue("-june", 6),
 193             new StringAndValue("-november", 11),
 194             new StringAndValue("-october", 10),
 195             new StringAndValue("-september", 9),
 196             // The l+n branch (with its sub-nodes) is a duplicate but will be written
 197             // both times because each time it follows a different linear-match node.
 198             new StringAndValue("xjuly", 7),
 199             new StringAndValue("xjune", 6)
 200         };
 201         checkData(data);
 202     }
 203
 204     public void Test31FirstForCodePoint() {
 205         final StringAndValue[] data={
 206             new StringAndValue("a", 1),
 207             new StringAndValue("a\ud800", 2),
 208             new StringAndValue("a\ud800\udc00", 3),  // "a\\U00010000"
 209             new StringAndValue("\ud840", 4),
 210             new StringAndValue("\ud840\udc00\udbff", 5),  // "\\U00020000\udbff"
 211             new StringAndValue("\ud840\udc00\udbff\udfff", 6),  // "\\U00020000\\U0010ffff"
 212             new StringAndValue("\ud840\udc00\udbff\udfffz", 7),  // "\\U00020000\\U0010ffffz"
 213             new StringAndValue("\ud900\udc00xy", 8),  // "\\U00050000xy"
 214             new StringAndValue("\ud900\udc00xyz", 9)  // "\\U00050000xyz"
 215         };
 216         checkData(data);
 217     }
 218
 219     public void Test32NextForCodePoint() {
 220         final StringAndValue[] data={
 221             // "\u4dff\\U00010000\u9999\\U00020000\udfff\\U0010ffff"
 222             new StringAndValue("\u4dff\ud800\udc00\u9999\ud840\udc00\udfff\udbff\udfff", 2000000000),
 223             // "\u4dff\\U00010000\u9999\\U00020002"
 224             new StringAndValue("\u4dff\ud800\udc00\u9999\ud840\udc02", 44444),
 225             // "\u4dff\\U000103ff"
 226             new StringAndValue("\u4dff\ud800\udfff", 99999)
 227         };
 228         CharsTrie trie=buildTrie(data, data.length, StringTrieBuilder.Option.FAST);
 229         BytesTrie.Result result;
 230         if( (result=trie.nextForCodePoint(0x4dff))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 231             (result=trie.nextForCodePoint(0x10000))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 232             (result=trie.nextForCodePoint(0x9999))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 233             (result=trie.nextForCodePoint(0x20000))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 234             (result=trie.nextForCodePoint(0xdfff))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 235             (result=trie.nextForCodePoint(0x10ffff))!=BytesTrie.Result.FINAL_VALUE || result!=trie.current() ||
 236             trie.getValue()!=2000000000
 237         ) {
 238             errln("CharsTrie.nextForCodePoint() fails for "+data[0].s);
 239         }
 240         if( (result=trie.firstForCodePoint(0x4dff))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 241             (result=trie.nextForCodePoint(0x10000))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 242             (result=trie.nextForCodePoint(0x9999))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 243             (result=trie.nextForCodePoint(0x20002))!=BytesTrie.Result.FINAL_VALUE || result!=trie.current() ||
 244             trie.getValue()!=44444
 245         ) {
 246             errln("CharsTrie.nextForCodePoint() fails for "+data[1].s);
 247         }
 248         if( (result=trie.reset().nextForCodePoint(0x4dff))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 249             (result=trie.nextForCodePoint(0x10000))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 250             (result=trie.nextForCodePoint(0x9999))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 251             (result=trie.nextForCodePoint(0x20222))!=BytesTrie.Result.NO_MATCH || result!=trie.current()  // no match for trail surrogate
 252         ) {
 253             errln("CharsTrie.nextForCodePoint() fails for \u4dff\\U00010000\u9999\\U00020222");
 254         }
 255         if( (result=trie.reset().nextForCodePoint(0x4dff))!=BytesTrie.Result.NO_VALUE || result!=trie.current() ||
 256             (result=trie.nextForCodePoint(0x103ff))!=BytesTrie.Result.FINAL_VALUE || result!=trie.current() ||
 257             trie.getValue()!=99999
 258         ) {
 259             errln("CharsTrie.nextForCodePoint() fails for "+data[2].s);
 260         }
 261     }
 262
 263     // Generate (string, value) pairs.
 264     // The first string (before next()) will be empty.
 265     private static final class Generator {
 266         public Generator() {
 267             value=4711;
 268             num=0;
 269         }
 270         public void next() {
 271             char c;
 272             s.setLength(0);
 273             s.append(c=(char)(value>>16));
 274             s.append((char)(value>>4));
 275             if((value&1)!=0) {
 276                 s.append((char)value);
 277             }
 278             set.add(c);
 279             value+=((value>>5)&0x7ff)*3+1;
 280             ++num;
 281         }
 282         public CharSequence getString() { return s; }
 283         public int getValue() { return value; }
 284         public int countUniqueFirstChars() { return set.size(); }
 285         public int getIndex() { return num; }
 286
 287         private StringBuilder s=new StringBuilder();
 288         private UnicodeSet set=new UnicodeSet();
 289         private int value;
 290         private int num;
 291     };
 292
 293     private CharsTrie buildLargeTrie(int numUniqueFirst) {
 294         Generator gen=new Generator();
 295         builder_.clear();
 296         while(gen.countUniqueFirstChars()<numUniqueFirst) {
 297             builder_.add(gen.getString(), gen.getValue());
 298             gen.next();
 299         }
 300         logln("buildLargeTrie("+numUniqueFirst+") added "+gen.getIndex()+" strings");
 301         CharSequence trieChars=builder_.buildCharSequence(StringTrieBuilder.Option.FAST);
 302         logln("serialized trie size: "+trieChars.length()+" chars\n");
 303         return new CharsTrie(trieChars, 0);
 304     }
 305
 306     // Exercise a large branch node.
 307     public void Test37LargeTrie() {
 308         CharsTrie trie=buildLargeTrie(1111);
 309         Generator gen=new Generator();
 310         while(gen.countUniqueFirstChars()<1111) {
 311             CharSequence x=gen.getString();
 312             int value=gen.getValue();
 313             int index;
 314             if(x.length()==0) {
 315                 index=0;
 316             } else {
 317                 if(trie.first(x.charAt(0))==BytesTrie.Result.NO_MATCH) {
 318                     errln(String.format("first(first char U+%04X)=BytesTrie.Result.NO_MATCH for string %d\n",
 319                                         x.charAt(0), gen.getIndex()));
 320                     break;
 321                 }
 322                 index=1;
 323             }
 324             BytesTrie.Result result=trie.next(x, index, x.length());
 325             if(!result.hasValue() || result!=trie.current() || value!=trie.getValue()) {
 326                 errln(String.format("next("+prettify(x)+")!=hasValue or "+
 327                                     "next()!=current() or getValue() wrong "+
 328                                     "for string "+gen.getIndex()));
 329                 break;
 330             }
 331             gen.next();
 332         }
 333     }
 334
 335     private CharsTrie buildMonthsTrie(StringTrieBuilder.Option buildOption) {
 336         // All types of nodes leading to the same value,
 337         // for code coverage of recursive functions.
 338         // In particular, we need a lot of branches on some single level
 339         // to exercise a split-branch node.
 340         final StringAndValue[] data={
 341             new StringAndValue("august", 8),
 342             new StringAndValue("jan", 1),
 343             new StringAndValue("jan.", 1),
 344             new StringAndValue("jana", 1),
 345             new StringAndValue("janbb", 1),
 346             new StringAndValue("janc", 1),
 347             new StringAndValue("janddd", 1),
 348             new StringAndValue("janee", 1),
 349             new StringAndValue("janef", 1),
 350             new StringAndValue("janf", 1),
 351             new StringAndValue("jangg", 1),
 352             new StringAndValue("janh", 1),
 353             new StringAndValue("janiiii", 1),
 354             new StringAndValue("janj", 1),
 355             new StringAndValue("jankk", 1),
 356             new StringAndValue("jankl", 1),
 357             new StringAndValue("jankmm", 1),
 358             new StringAndValue("janl", 1),
 359             new StringAndValue("janm", 1),
 360             new StringAndValue("jannnnnnnnnnnnnnnnnnnnnnnnnnnnn", 1),
 361             new StringAndValue("jano", 1),
 362             new StringAndValue("janpp", 1),
 363             new StringAndValue("janqqq", 1),
 364             new StringAndValue("janr", 1),
 365             new StringAndValue("januar", 1),
 366             new StringAndValue("january", 1),
 367             new StringAndValue("july", 7),
 368             new StringAndValue("jun", 6),
 369             new StringAndValue("jun.", 6),
 370             new StringAndValue("june", 6)
 371         };
 372         return buildTrie(data, data.length, buildOption);
 373     }
 374
 375     public void Test40GetUniqueValue() {
 376         CharsTrie trie=buildMonthsTrie(StringTrieBuilder.Option.FAST);
 377         long uniqueValue;
 378         if((uniqueValue=trie.getUniqueValue())!=0) {
 379             errln("unique value at root");
 380         }
 381         trie.next('j');
 382         trie.next('a');
 383         trie.next('n');
 384         // getUniqueValue() directly after next()
 385         if((uniqueValue=trie.getUniqueValue())!=((1<<1)|1)) {
 386             errln("not unique value 1 after \"jan\": instead "+uniqueValue);
 387         }
 388         trie.first('j');
 389         trie.next('u');
 390         if((uniqueValue=trie.getUniqueValue())!=0) {
 391             errln("unique value after \"ju\"");
 392         }
 393         if(trie.next('n')!=BytesTrie.Result.INTERMEDIATE_VALUE || 6!=trie.getValue()) {
 394             errln("not normal value 6 after \"jun\"");
 395         }
 396         // getUniqueValue() after getValue()
 397         if((uniqueValue=trie.getUniqueValue())!=((6<<1)|1)) {
 398             errln("not unique value 6 after \"jun\"");
 399         }
 400         // getUniqueValue() from within a linear-match node
 401         trie.first('a');
 402         trie.next('u');
 403         if((uniqueValue=trie.getUniqueValue())!=((8<<1)|1)) {
 404             errln("not unique value 8 after \"au\"");
 405         }
 406     }
 407
 408     public void Test41GetNextChars() {
 409         CharsTrie trie=buildMonthsTrie(StringTrieBuilder.Option.SMALL);
 410         StringBuilder buffer=new StringBuilder();
 411         int count=trie.getNextChars(buffer);
 412         if(count!=2 || !"aj".contentEquals(buffer)) {
 413             errln("months getNextChars()!=[aj] at root");
 414         }
 415         trie.next('j');
 416         trie.next('a');
 417         trie.next('n');
 418         // getNextChars() directly after next()
 419         buffer.setLength(0);
 420         count=trie.getNextChars(buffer);
 421         if(count!=20 || !".abcdefghijklmnopqru".contentEquals(buffer)) {
 422             errln("months getNextChars()!=[.abcdefghijklmnopqru] after \"jan\"");
 423         }
 424         // getNextChars() after getValue()
 425         trie.getValue();  // next() had returned BytesTrie.Result.INTERMEDIATE_VALUE.
 426         buffer.setLength(0);
 427         count=trie.getNextChars(buffer);
 428         if(count!=20 || !".abcdefghijklmnopqru".contentEquals(buffer)) {
 429             errln("months getNextChars()!=[.abcdefghijklmnopqru] after \"jan\"+getValue()");
 430         }
 431         // getNextChars() from a linear-match node
 432         trie.next('u');
 433         buffer.setLength(0);
 434         count=trie.getNextChars(buffer);
 435         if(count!=1 || !"a".contentEquals(buffer)) {
 436             errln("months getNextChars()!=[a] after \"janu\"");
 437         }
 438         trie.next('a');
 439         buffer.setLength(0);
 440         count=trie.getNextChars(buffer);
 441         if(count!=1 || !"r".contentEquals(buffer)) {
 442             errln("months getNextChars()!=[r] after \"janua\"");
 443         }
 444         trie.next('r');
 445         trie.next('y');
 446         // getNextChars() after a final match
 447         buffer.setLength(0);
 448         count=trie.getNextChars(buffer);
 449         if(count!=0 || buffer.length()!=0) {
 450             errln("months getNextChars()!=[] after \"january\"");
 451         }
 452     }
 453
 454     public void Test50IteratorFromBranch() {
 455         CharsTrie trie=buildMonthsTrie(StringTrieBuilder.Option.FAST);
 456         // Go to a branch node.
 457         trie.next('j');
 458         trie.next('a');
 459         trie.next('n');
 460         CharsTrie.Iterator iter=trie.iterator();
 461         // Expected data: Same as in buildMonthsTrie(), except only the suffixes
 462         // following "jan".
 463         final StringAndValue[] data={
 464             new StringAndValue("", 1),
 465             new StringAndValue(".", 1),
 466             new StringAndValue("a", 1),
 467             new StringAndValue("bb", 1),
 468             new StringAndValue("c", 1),
 469             new StringAndValue("ddd", 1),
 470             new StringAndValue("ee", 1),
 471             new StringAndValue("ef", 1),
 472             new StringAndValue("f", 1),
 473             new StringAndValue("gg", 1),
 474             new StringAndValue("h", 1),
 475             new StringAndValue("iiii", 1),
 476             new StringAndValue("j", 1),
 477             new StringAndValue("kk", 1),
 478             new StringAndValue("kl", 1),
 479             new StringAndValue("kmm", 1),
 480             new StringAndValue("l", 1),
 481             new StringAndValue("m", 1),
 482             new StringAndValue("nnnnnnnnnnnnnnnnnnnnnnnnnnnn", 1),
 483             new StringAndValue("o", 1),
 484             new StringAndValue("pp", 1),
 485             new StringAndValue("qqq", 1),
 486             new StringAndValue("r", 1),
 487             new StringAndValue("uar", 1),
 488             new StringAndValue("uary", 1)
 489         };
 490         checkIterator(iter, data);
 491         // Reset, and we should get the same result.
 492         logln("after iter.reset()");
 493         checkIterator(iter.reset(), data);
 494     }
 495
 496     public void Test51IteratorFromLinearMatch() {
 497         CharsTrie trie=buildMonthsTrie(StringTrieBuilder.Option.SMALL);
 498         // Go into a linear-match node.
 499         trie.next('j');
 500         trie.next('a');
 501         trie.next('n');
 502         trie.next('u');
 503         trie.next('a');
 504         CharsTrie.Iterator iter=trie.iterator();
 505         // Expected data: Same as in buildMonthsTrie(), except only the suffixes
 506         // following "janua".
 507         final StringAndValue[] data={
 508             new StringAndValue("r", 1),
 509             new StringAndValue("ry", 1)
 510         };
 511         checkIterator(iter, data);
 512         // Reset, and we should get the same result.
 513         logln("after iter.reset()");
 514         checkIterator(iter.reset(), data);
 515     }
 516
 517     public void Test52TruncatingIteratorFromRoot() {
 518         CharsTrie trie=buildMonthsTrie(StringTrieBuilder.Option.FAST);
 519         CharsTrie.Iterator iter=trie.iterator(4);
 520         // Expected data: Same as in buildMonthsTrie(), except only the first 4 characters
 521         // of each string, and no string duplicates from the truncation.
 522         final StringAndValue[] data={
 523             new StringAndValue("augu", -1),
 524             new StringAndValue("jan", 1),
 525             new StringAndValue("jan.", 1),
 526             new StringAndValue("jana", 1),
 527             new StringAndValue("janb", -1),
 528             new StringAndValue("janc", 1),
 529             new StringAndValue("jand", -1),
 530             new StringAndValue("jane", -1),
 531             new StringAndValue("janf", 1),
 532             new StringAndValue("jang", -1),
 533             new StringAndValue("janh", 1),
 534             new StringAndValue("jani", -1),
 535             new StringAndValue("janj", 1),
 536             new StringAndValue("jank", -1),
 537             new StringAndValue("janl", 1),
 538             new StringAndValue("janm", 1),
 539             new StringAndValue("jann", -1),
 540             new StringAndValue("jano", 1),
 541             new StringAndValue("janp", -1),
 542             new StringAndValue("janq", -1),
 543             new StringAndValue("janr", 1),
 544             new StringAndValue("janu", -1),
 545             new StringAndValue("july", 7),
 546             new StringAndValue("jun", 6),
 547             new StringAndValue("jun.", 6),
 548             new StringAndValue("june", 6)
 549         };
 550         checkIterator(iter, data);
 551         // Reset, and we should get the same result.
 552         logln("after iter.reset()");
 553         checkIterator(iter.reset(), data);
 554     }
 555
 556     public void Test53TruncatingIteratorFromLinearMatchShort() {
 557         final StringAndValue[] data={
 558             new StringAndValue("abcdef", 10),
 559             new StringAndValue("abcdepq", 200),
 560             new StringAndValue("abcdeyz", 3000)
 561         };
 562         CharsTrie trie=buildTrie(data, data.length, StringTrieBuilder.Option.FAST);
 563         // Go into a linear-match node.
 564         trie.next('a');
 565         trie.next('b');
 566         // Truncate within the linear-match node.
 567         CharsTrie.Iterator iter=trie.iterator(2);
 568         final StringAndValue[] expected={
 569             new StringAndValue("cd", -1)
 570         };
 571         checkIterator(iter, expected);
 572         // Reset, and we should get the same result.
 573         logln("after iter.reset()");
 574         checkIterator(iter.reset(), expected);
 575     }
 576
 577     public void Test54TruncatingIteratorFromLinearMatchLong() {
 578         final StringAndValue[] data={
 579             new StringAndValue("abcdef", 10),
 580             new StringAndValue("abcdepq", 200),
 581             new StringAndValue("abcdeyz", 3000)
 582         };
 583         CharsTrie trie=buildTrie(data, data.length, StringTrieBuilder.Option.FAST);
 584         // Go into a linear-match node.
 585         trie.next('a');
 586         trie.next('b');
 587         trie.next('c');
 588         // Truncate after the linear-match node.
 589         CharsTrie.Iterator iter=trie.iterator(3);
 590         final StringAndValue[] expected={
 591             new StringAndValue("def", 10),
 592             new StringAndValue("dep", -1),
 593             new StringAndValue("dey", -1)
 594         };
 595         checkIterator(iter, expected);
 596         // Reset, and we should get the same result.
 597         logln("after iter.reset()");
 598         checkIterator(iter.reset(), expected);
 599     }
 600
 601     public void Test59IteratorFromChars() {
 602         final StringAndValue[] data={
 603             new StringAndValue("mm", 3),
 604             new StringAndValue("mmm", 33),
 605             new StringAndValue("mmnop", 333)
 606         };
 607         builder_.clear();
 608         for(StringAndValue item : data) {
 609             builder_.add(item.s, item.value);
 610         }
 611         CharSequence trieChars=builder_.buildCharSequence(StringTrieBuilder.Option.FAST);
 612         checkIterator(CharsTrie.iterator(trieChars, 0, 0), data);
 613     }
 614
 615     private void checkData(StringAndValue data[]) {
 616         checkData(data, data.length);
 617     }
 618
 619     private void checkData(StringAndValue data[], int dataLength) {
 620         logln("checkData(dataLength="+dataLength+", fast)");
 621         checkData(data, dataLength, StringTrieBuilder.Option.FAST);
 622         logln("checkData(dataLength="+dataLength+", small)");
 623         checkData(data, dataLength, StringTrieBuilder.Option.SMALL);
 624     }
 625
 626     private void checkData(StringAndValue[] data, int dataLength, StringTrieBuilder.Option buildOption) {
 627         CharsTrie trie=buildTrie(data, dataLength, buildOption);
 628         checkFirst(trie, data, dataLength);
 629         checkNext(trie, data, dataLength);
 630         checkNextWithState(trie, data, dataLength);
 631         checkNextString(trie, data, dataLength);
 632         checkIterator(trie, data, dataLength);
 633     }
 634
 635     private CharsTrie buildTrie(StringAndValue data[], int dataLength,
 636                                 StringTrieBuilder.Option buildOption) {
 637         // Add the items to the trie builder in an interesting (not trivial, not random) order.
 638         int index, step;
 639         if((dataLength&1)!=0) {
 640             // Odd number of items.
 641             index=dataLength/2;
 642             step=2;
 643         } else if((dataLength%3)!=0) {
 644             // Not a multiple of 3.
 645             index=dataLength/5;
 646             step=3;
 647         } else {
 648             index=dataLength-1;
 649             step=-1;
 650         }
 651         builder_.clear();
 652         for(int i=0; i<dataLength; ++i) {
 653             builder_.add(data[index].s, data[index].value);
 654             index=(index+step)%dataLength;
 655         }
 656         CharsTrie trie=builder_.build(buildOption);
 657         try {
 658             builder_.add("zzz", 999);
 659             errln("builder.build().add(zzz) did not throw IllegalStateException");
 660         } catch(IllegalStateException e) {
 661             // good
 662         }
 663         CharSequence trieChars=builder_.buildCharSequence(buildOption);
 664         logln("serialized trie size: "+trieChars.length()+" chars");
 665         // Tries from either build() method should be identical but
 666         // CharsTrie does not implement equals().
 667         // We just return either one.
 668         if((dataLength&1)!=0) {
 669             return trie;
 670         } else {
 671             return new CharsTrie(trieChars, 0);
 672         }
 673     }
 674
 675     private void checkFirst(CharsTrie trie, StringAndValue[] data, int dataLength) {
 676         for(int i=0; i<dataLength; ++i) {
 677             if(data[i].s.length()==0) {
 678                 continue;  // skip empty string
 679             }
 680             String expectedString=data[i].s;
 681             int c=expectedString.charAt(0);
 682             int nextCp=expectedString.length()>1 ? expectedString.charAt(1) : 0;
 683             BytesTrie.Result firstResult=trie.first(c);
 684             int firstValue=firstResult.hasValue() ? trie.getValue() : -1;
 685             BytesTrie.Result nextResult=trie.next(nextCp);
 686             if(firstResult!=trie.reset().next(c) ||
 687                firstResult!=trie.current() ||
 688                firstValue!=(firstResult.hasValue() ? trie.getValue() : -1) ||
 689                nextResult!=trie.next(nextCp)
 690             ) {
 691                 errln(String.format("trie.first(U+%04X)!=trie.reset().next(same) for %s",
 692                                     c, data[i].s));
 693             }
 694             c=expectedString.codePointAt(0);
 695             int cLength=Character.charCount(c);
 696             nextCp=expectedString.length()>cLength ? expectedString.codePointAt(cLength) : 0;
 697             firstResult=trie.firstForCodePoint(c);
 698             firstValue=firstResult.hasValue() ? trie.getValue() : -1;
 699             nextResult=trie.nextForCodePoint(nextCp);
 700             if(firstResult!=trie.reset().nextForCodePoint(c) ||
 701                firstResult!=trie.current() ||
 702                firstValue!=(firstResult.hasValue() ? trie.getValue() : -1) ||
 703                nextResult!=trie.nextForCodePoint(nextCp)
 704             ) {
 705                 errln(String.format("trie.firstForCodePoint(U+%04X)!=trie.reset().nextForCodePoint(same) for %s",
 706                                     c, data[i].s));
 707             }
 708         }
 709         trie.reset();
 710     }
 711
 712     private void checkNext(CharsTrie trie, StringAndValue[] data, int dataLength) {
 713         CharsTrie.State state=new CharsTrie.State();
 714         for(int i=0; i<dataLength; ++i) {
 715             String expectedString=data[i].s;
 716             int stringLength=expectedString.length();
 717             BytesTrie.Result result;
 718             if( !(result=trie.next(expectedString, 0, stringLength)).hasValue() ||
 719                 result!=trie.current()
 720             ) {
 721                 errln("trie does not seem to contain "+data[i].s);
 722             } else if(trie.getValue()!=data[i].value) {
 723                 errln(String.format("trie value for %s is %d=0x%x instead of expected %d=0x%x",
 724                                     data[i].s,
 725                                     trie.getValue(), trie.getValue(),
 726                                     data[i].value, data[i].value));
 727             } else if(result!=trie.current() || trie.getValue()!=data[i].value) {
 728                 errln("trie value for "+data[i].s+" changes when repeating current()/getValue()");
 729             }
 730             trie.reset();
 731             result=trie.current();
 732             for(int j=0; j<stringLength; ++j) {
 733                 if(!result.hasNext()) {
 734                     errln(String.format("trie.current()!=hasNext before end of %s (at index %d)",
 735                                         data[i].s, j));
 736                     break;
 737                 }
 738                 if(result==BytesTrie.Result.INTERMEDIATE_VALUE) {
 739                     trie.getValue();
 740                     if(trie.current()!=BytesTrie.Result.INTERMEDIATE_VALUE) {
 741                         errln(String.format("trie.getValue().current()!=BytesTrie.Result.INTERMEDIATE_VALUE "+
 742                                             "before end of %s (at index %d)", data[i].s, j));
 743                         break;
 744                     }
 745                 }
 746                 result=trie.next(expectedString.charAt(j));
 747                 if(!result.matches()) {
 748                     errln(String.format("trie.next()=BytesTrie.Result.NO_MATCH "+
 749                                         "before end of %s (at index %d)", data[i].s, j));
 750                     break;
 751                 }
 752                 if(result!=trie.current()) {
 753                     errln(String.format("trie.next()!=following current() "+
 754                                         "before end of %s (at index %d)", data[i].s, j));
 755                     break;
 756                 }
 757             }
 758             if(!result.hasValue()) {
 759                 errln("trie.next()!=hasValue at the end of "+data[i].s);
 760                 continue;
 761             }
 762             trie.getValue();
 763             if(result!=trie.current()) {
 764                 errln("trie.current() != current()+getValue()+current() after end of "+
 765                       data[i].s);
 766             }
 767             // Compare the final current() with whether next() can actually continue.
 768             trie.saveState(state);
 769             boolean nextContinues=false;
 770             for(int c=0x20; c<0xe000; ++c) {
 771                 if(c==0x80) {
 772                     c=0xd800;  // Check for ASCII and surrogates but not all of the BMP.
 773                 }
 774                 if(trie.resetToState(state).next(c).matches()) {
 775                     nextContinues=true;
 776                     break;
 777                 }
 778             }
 779             if((result==BytesTrie.Result.INTERMEDIATE_VALUE)!=nextContinues) {
 780                 errln("(trie.current()==BytesTrie.Result.INTERMEDIATE_VALUE) contradicts "+
 781                       "(trie.next(some char)!=BytesTrie.Result.NO_MATCH) after end of "+data[i].s);
 782             }
 783             trie.reset();
 784         }
 785     }
 786
 787     private void checkNextWithState(CharsTrie trie, StringAndValue[] data, int dataLength) {
 788         CharsTrie.State noState=new CharsTrie.State(), state=new CharsTrie.State();
 789         for(int i=0; i<dataLength; ++i) {
 790             if((i&1)==0) {
 791                 try {
 792                     trie.resetToState(noState);
 793                     errln("trie.resetToState(noState) should throw an IllegalArgumentException");
 794                 } catch(IllegalArgumentException e) {
 795                     // good
 796                 }
 797             }
 798             String expectedString=data[i].s;
 799             int stringLength=expectedString.length();
 800             int partialLength=stringLength/3;
 801             for(int j=0; j<partialLength; ++j) {
 802                 if(!trie.next(expectedString.charAt(j)).matches()) {
 803                     errln("trie.next()=BytesTrie.Result.NO_MATCH for a prefix of "+data[i].s);
 804                     return;
 805                 }
 806             }
 807             trie.saveState(state);
 808             BytesTrie.Result resultAtState=trie.current();
 809             BytesTrie.Result result;
 810             int valueAtState=-99;
 811             if(resultAtState.hasValue()) {
 812                 valueAtState=trie.getValue();
 813             }
 814             result=trie.next(0);  // mismatch
 815             if(result!=BytesTrie.Result.NO_MATCH || result!=trie.current()) {
 816                 errln("trie.next(0) matched after part of "+data[i].s);
 817             }
 818             if( resultAtState!=trie.resetToState(state).current() ||
 819                 (resultAtState.hasValue() && valueAtState!=trie.getValue())
 820             ) {
 821                 errln("trie.next(part of "+data[i].s+") changes current()/getValue() after "+
 822                       "saveState/next(0)/resetToState");
 823             } else if(!(result=trie.next(expectedString, partialLength, stringLength)).hasValue() ||
 824                       result!=trie.current()) {
 825                 errln("trie.next(rest of "+data[i].s+") does not seem to contain "+data[i].s+" after "+
 826                       "saveState/next(0)/resetToState");
 827             } else if(!(result=trie.resetToState(state).
 828                                 next(expectedString, partialLength, stringLength)).hasValue() ||
 829                       result!=trie.current()) {
 830                 errln("trie does not seem to contain "+data[i].s+
 831                       " after saveState/next(rest)/resetToState");
 832             } else if(trie.getValue()!=data[i].value) {
 833                 errln(String.format("trie value for %s is %d=0x%x instead of expected %d=0x%x",
 834                                     data[i].s,
 835                                     trie.getValue(), trie.getValue(),
 836                                     data[i].value, data[i].value));
 837             }
 838             trie.reset();
 839         }
 840     }
 841
 842     // next(string) is also tested in other functions,
 843     // but here we try to go partway through the string, and then beyond it.
 844     private void checkNextString(CharsTrie trie, StringAndValue[] data, int dataLength) {
 845         for(int i=0; i<dataLength; ++i) {
 846             String expectedString=data[i].s;
 847             int stringLength=expectedString.length();
 848             if(!trie.next(expectedString, 0, stringLength/2).matches()) {
 849                 errln("trie.next(up to middle of string)=BytesTrie.Result.NO_MATCH for "+data[i].s);
 850                 continue;
 851             }
 852             // Test that we stop properly at the end of the string.
 853             trie.next(expectedString, stringLength/2, stringLength);
 854             if(trie.next(0).matches()) {
 855                 errln("trie.next(string+NUL)!=BytesTrie.Result.NO_MATCH for "+data[i].s);
 856             }
 857             trie.reset();
 858         }
 859     }
 860
 861     private void checkIterator(CharsTrie trie, StringAndValue[] data, int dataLength) {
 862         checkIterator(trie.iterator(), data, dataLength);
 863     }
 864
 865     private void checkIterator(CharsTrie.Iterator iter, StringAndValue data[]) {
 866         checkIterator(iter, data, data.length);
 867     }
 868
 869     private void checkIterator(CharsTrie.Iterator iter, StringAndValue[] data, int dataLength) {
 870         for(int i=0; i<dataLength; ++i) {
 871             if(!iter.hasNext()) {
 872                 errln("trie iterator hasNext()=false for item "+i+": "+data[i].s);
 873                 break;
 874             }
 875             CharsTrie.Entry entry=iter.next();
 876             String expectedString=data[i].s;
 877             if(!expectedString.contentEquals(entry.chars)) {
 878                 errln(String.format("trie iterator next().getString()=%s but expected %s for item %d",
 879                                     entry.chars, data[i].s, i));
 880             }
 881             if(entry.value!=data[i].value) {
 882                 errln(String.format("trie iterator next().getValue()=%d=0x%x but expected %d=0x%x for item %d: %s",
 883                                     entry.value, entry.value,
 884                                     data[i].value, data[i].value,
 885                                     i, data[i].s));
 886             }
 887         }
 888         if(iter.hasNext()) {
 889             errln("trie iterator hasNext()=true after all items");
 890         }
 891         try {
 892             iter.next();
 893             errln("trie iterator next() did not throw NoSuchElementException after all items");
 894         } catch(NoSuchElementException e) {
 895             // good
 896         }
 897     }
 898
 899     private CharsTrieBuilder builder_=new CharsTrieBuilder();
 900 }