icuSources/test/intltest/bytestrietest.cpp

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