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

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