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
11 package com.ibm.icu.dev.test.util;
13 import java.nio.ByteBuffer;
14 import java.util.NoSuchElementException;
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;
21 public class BytesTrieTest extends TestFmwk {
22 public static void main(String[] args) throws Exception {
23 new BytesTrieTest().run(args);
25 public BytesTrieTest() {}
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.
32 public void Test00Builder() {
35 builder_.build(StringTrieBuilder.Option.FAST);
36 errln("BytesTrieBuilder().build() did not throw IndexOutOfBoundsException");
38 } catch(IndexOutOfBoundsException e) {
42 byte[] equal=new byte[] { 0x3d }; // "="
43 builder_.add(equal, 1, 0).add(equal, 1, 1);
44 errln("BytesTrieBuilder.add() did not detect duplicates");
46 } catch(IllegalArgumentException e) {
51 private static final class StringAndValue {
52 public StringAndValue(String str, int val) {
54 bytes=new byte[s.length()];
55 for(int i=0; i<bytes.length; ++i) {
56 bytes[i]=(byte)s.charAt(i);
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)
70 public void Test10Empty() {
71 final StringAndValue[] data={
72 new StringAndValue("", 0)
77 public void Test11_a() {
78 final StringAndValue[] data={
79 new StringAndValue("a", 1)
84 public void Test12_a_ab() {
85 final StringAndValue[] data={
86 new StringAndValue("a", 1),
87 new StringAndValue("ab", 100)
92 public void Test20ShortestBranch() {
93 final StringAndValue[] data={
94 new StringAndValue("a", 1000),
95 new StringAndValue("b", 2000)
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)
117 for(int length=2; length<=data.length; ++length) {
118 logln("TestBranches length="+length);
119 checkData(data, length);
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
130 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"+
131 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"+
132 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"+
133 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"+
134 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"+
135 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", -3)
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)
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)
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)
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)
246 return buildTrie(data, data.length, buildOption);
249 public void Test40GetUniqueValue() {
250 BytesTrie trie=buildMonthsTrie(StringTrieBuilder.Option.FAST);
252 if((uniqueValue=trie.getUniqueValue())!=0) {
253 errln("unique value at root");
258 // getUniqueValue() directly after next()
259 if((uniqueValue=trie.getUniqueValue())!=((1<<1)|1)) {
260 errln("not unique value 1 after \"jan\": instead "+uniqueValue);
264 if((uniqueValue=trie.getUniqueValue())!=0) {
265 errln("unique value after \"ju\"");
267 if(trie.next('n')!=BytesTrie.Result.INTERMEDIATE_VALUE || 6!=trie.getValue()) {
268 errln("not normal value 6 after \"jun\"");
270 // getUniqueValue() after getValue()
271 if((uniqueValue=trie.getUniqueValue())!=((6<<1)|1)) {
272 errln("not unique value 6 after \"jun\"");
274 // getUniqueValue() from within a linear-match node
277 if((uniqueValue=trie.getUniqueValue())!=((8<<1)|1)) {
278 errln("not unique value 8 after \"au\"");
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");
292 // getNextBytes() directly after next()
294 count=trie.getNextBytes(buffer);
295 if(count!=20 || !".abcdefghijklmnopqru".contentEquals(buffer)) {
296 errln("months getNextBytes()!=[.abcdefghijklmnopqru] after \"jan\"");
298 // getNextBytes() after getValue()
299 trie.getValue(); // next() had returned BytesTrie.Result.INTERMEDIATE_VALUE.
301 count=trie.getNextBytes(buffer);
302 if(count!=20 || !".abcdefghijklmnopqru".contentEquals(buffer)) {
303 errln("months getNextBytes()!=[.abcdefghijklmnopqru] after \"jan\"+getValue()");
305 // getNextBytes() from a linear-match node
308 count=trie.getNextBytes(buffer);
309 if(count!=1 || !"a".contentEquals(buffer)) {
310 errln("months getNextBytes()!=[a] after \"janu\"");
314 count=trie.getNextBytes(buffer);
315 if(count!=1 || !"r".contentEquals(buffer)) {
316 errln("months getNextBytes()!=[r] after \"janua\"");
320 // getNextBytes() after a final match
322 count=trie.getNextBytes(buffer);
323 if(count!=0 || buffer.length()!=0) {
324 errln("months getNextBytes()!=[] after \"january\"");
328 public void Test50IteratorFromBranch() {
329 BytesTrie trie=buildMonthsTrie(StringTrieBuilder.Option.FAST);
330 // Go to a branch node.
334 BytesTrie.Iterator iter=trie.iterator();
335 // Expected data: Same as in buildMonthsTrie(), except only the suffixes
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)
364 checkIterator(iter, data);
365 // Reset, and we should get the same result.
366 logln("after iter.reset()");
367 checkIterator(iter.reset(), data);
370 public void Test51IteratorFromLinearMatch() {
371 BytesTrie trie=buildMonthsTrie(StringTrieBuilder.Option.SMALL);
372 // Go into a linear-match node.
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)
385 checkIterator(iter, data);
386 // Reset, and we should get the same result.
387 logln("after iter.reset()");
388 checkIterator(iter.reset(), data);
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)
424 checkIterator(iter, data);
425 // Reset, and we should get the same result.
426 logln("after iter.reset()");
427 checkIterator(iter.reset(), data);
430 public void Test53TruncatingIteratorFromLinearMatchShort() {
431 final StringAndValue[] data={
432 new StringAndValue("abcdef", 10),
433 new StringAndValue("abcdepq", 200),
434 new StringAndValue("abcdeyz", 3000)
436 BytesTrie trie=buildTrie(data, data.length, StringTrieBuilder.Option.FAST);
437 // Go into a linear-match node.
440 // Truncate within the linear-match node.
441 BytesTrie.Iterator iter=trie.iterator(2);
442 final StringAndValue[] expected={
443 new StringAndValue("cd", -1)
445 checkIterator(iter, expected);
446 // Reset, and we should get the same result.
447 logln("after iter.reset()");
448 checkIterator(iter.reset(), expected);
451 public void Test54TruncatingIteratorFromLinearMatchLong() {
452 final StringAndValue[] data={
453 new StringAndValue("abcdef", 10),
454 new StringAndValue("abcdepq", 200),
455 new StringAndValue("abcdeyz", 3000)
457 BytesTrie trie=buildTrie(data, data.length, StringTrieBuilder.Option.FAST);
458 // Go into a linear-match node.
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)
469 checkIterator(iter, expected);
470 // Reset, and we should get the same result.
471 logln("after iter.reset()");
472 checkIterator(iter.reset(), expected);
475 public void Test59IteratorFromBytes() {
476 final StringAndValue[] data={
477 new StringAndValue("mm", 3),
478 new StringAndValue("mmm", 33),
479 new StringAndValue("mmnop", 333)
482 for(StringAndValue item : data) {
483 builder_.add(item.bytes, item.bytes.length, item.value);
485 ByteBuffer trieBytes=builder_.buildByteBuffer(StringTrieBuilder.Option.FAST);
487 BytesTrie.iterator(trieBytes.array(), trieBytes.arrayOffset()+trieBytes.position(), 0),
491 private void checkData(StringAndValue data[]) {
492 checkData(data, data.length);
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);
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);
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.
515 if((dataLength&1)!=0) {
516 // Odd number of items.
519 } else if((dataLength%3)!=0) {
520 // Not a multiple of 3.
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;
532 BytesTrie trie=builder_.build(buildOption);
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) {
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) {
547 return new BytesTrie(trieBytes.array(), trieBytes.arrayOffset()+trieBytes.position());
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
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)
566 errln(String.format("trie.first(%c)!=trie.reset().next(same) for %s",
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()
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",
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()");
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)",
598 if(result==BytesTrie.Result.INTERMEDIATE_VALUE) {
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));
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));
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));
618 if(!result.hasValue()) {
619 errln("trie.next()!=hasValue at the end of "+data[i].s);
623 if(result!=trie.current()) {
624 errln("trie.current() != current()+getValue()+current() after end of "+
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()) {
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);
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) {
649 trie.resetToState(noState);
650 errln("trie.resetToState(noState) should throw an IllegalArgumentException");
651 } catch(IllegalArgumentException e) {
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);
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();
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);
675 if( resultAtState!=trie.resetToState(state).current() ||
676 (resultAtState.hasValue() && valueAtState!=trie.getValue())
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",
692 trie.getValue(), trie.getValue(),
693 data[i].value, data[i].value));
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);
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);
718 private void checkIterator(BytesTrie trie, StringAndValue data[], int dataLength) {
719 checkIterator(trie.iterator(), data, dataLength);
722 private void checkIterator(BytesTrie.Iterator iter, StringAndValue data[]) {
723 checkIterator(iter, data, data.length);
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);
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));
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));
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,
749 errln("trie iterator hasNext()=true after all items");
753 errln("trie iterator next() did not throw NoSuchElementException after all items");
754 } catch(NoSuchElementException e) {
759 private BytesTrieBuilder builder_=new BytesTrieBuilder();