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