icuSources/test/intltest/ucharstrietest.cpp

   1 /*
   2 *******************************************************************************
   3 *   Copyright (C) 2010-2012, International Business Machines
   4 *   Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 *   file name:  ucharstrietest.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/appendable.h"
  19 #include "unicode/localpointer.h"
  20 #include "unicode/ucharstrie.h"
  21 #include "unicode/ucharstriebuilder.h"
  22 #include "unicode/uniset.h"
  23 #include "unicode/unistr.h"
  24 #include "intltest.h"
  25
  26 #define LENGTHOF(array) (int32_t)(sizeof(array)/sizeof((array)[0]))
  27
  28 struct StringAndValue {
  29     const char *s;
  30     int32_t value;
  31 };
  32
  33 class UCharsTrieTest : public IntlTest {
  34 public:
  35     UCharsTrieTest();
  36     virtual ~UCharsTrieTest();
  37
  38     void runIndexedTest(int32_t index, UBool exec, const char *&name, char *par=NULL);
  39     void TestBuilder();
  40     void TestEmpty();
  41     void Test_a();
  42     void Test_a_ab();
  43     void TestShortestBranch();
  44     void TestBranches();
  45     void TestLongSequence();
  46     void TestLongBranch();
  47     void TestValuesForState();
  48     void TestCompact();
  49     void TestFirstForCodePoint();
  50     void TestNextForCodePoint();
  51
  52     UCharsTrie *buildLargeTrie(int32_t numUniqueFirst);
  53     void TestLargeTrie();
  54
  55     UCharsTrie *buildMonthsTrie(UStringTrieBuildOption buildOption);
  56     void TestHasUniqueValue();
  57     void TestGetNextUChars();
  58     void TestIteratorFromBranch();
  59     void TestIteratorFromLinearMatch();
  60     void TestTruncatingIteratorFromRoot();
  61     void TestTruncatingIteratorFromLinearMatchShort();
  62     void TestTruncatingIteratorFromLinearMatchLong();
  63     void TestIteratorFromUChars();
  64
  65     void checkData(const StringAndValue data[], int32_t dataLength);
  66     void checkData(const StringAndValue data[], int32_t dataLength, UStringTrieBuildOption buildOption);
  67     UCharsTrie *buildTrie(const StringAndValue data[], int32_t dataLength,
  68                           UStringTrieBuildOption buildOption);
  69     void checkFirst(UCharsTrie &trie, const StringAndValue data[], int32_t dataLength);
  70     void checkNext(UCharsTrie &trie, const StringAndValue data[], int32_t dataLength);
  71     void checkNextWithState(UCharsTrie &trie, const StringAndValue data[], int32_t dataLength);
  72     void checkNextString(UCharsTrie &trie, const StringAndValue data[], int32_t dataLength);
  73     void checkIterator(UCharsTrie &trie, const StringAndValue data[], int32_t dataLength);
  74     void checkIterator(UCharsTrie::Iterator &iter, const StringAndValue data[], int32_t dataLength);
  75
  76 private:
  77     UCharsTrieBuilder *builder_;
  78 };
  79
  80 extern IntlTest *createUCharsTrieTest() {
  81     return new UCharsTrieTest();
  82 }
  83
  84 UCharsTrieTest::UCharsTrieTest() : builder_(NULL) {
  85     IcuTestErrorCode errorCode(*this, "UCharsTrieTest()");
  86     builder_=new UCharsTrieBuilder(errorCode);
  87 }
  88
  89 UCharsTrieTest::~UCharsTrieTest() {
  90     delete builder_;
  91 }
  92
  93 void UCharsTrieTest::runIndexedTest(int32_t index, UBool exec, const char *&name, char * /*par*/) {
  94     if(exec) {
  95         logln("TestSuite UCharsTrieTest: ");
  96     }
  97     TESTCASE_AUTO_BEGIN;
  98     TESTCASE_AUTO(TestBuilder);
  99     TESTCASE_AUTO(TestEmpty);
 100     TESTCASE_AUTO(Test_a);
 101     TESTCASE_AUTO(Test_a_ab);
 102     TESTCASE_AUTO(TestShortestBranch);
 103     TESTCASE_AUTO(TestBranches);
 104     TESTCASE_AUTO(TestLongSequence);
 105     TESTCASE_AUTO(TestLongBranch);
 106     TESTCASE_AUTO(TestValuesForState);
 107     TESTCASE_AUTO(TestCompact);
 108     TESTCASE_AUTO(TestFirstForCodePoint);
 109     TESTCASE_AUTO(TestNextForCodePoint);
 110     TESTCASE_AUTO(TestLargeTrie);
 111     TESTCASE_AUTO(TestHasUniqueValue);
 112     TESTCASE_AUTO(TestGetNextUChars);
 113     TESTCASE_AUTO(TestIteratorFromBranch);
 114     TESTCASE_AUTO(TestIteratorFromLinearMatch);
 115     TESTCASE_AUTO(TestTruncatingIteratorFromRoot);
 116     TESTCASE_AUTO(TestTruncatingIteratorFromLinearMatchShort);
 117     TESTCASE_AUTO(TestTruncatingIteratorFromLinearMatchLong);
 118     TESTCASE_AUTO(TestIteratorFromUChars);
 119     TESTCASE_AUTO_END;
 120 }
 121
 122 void UCharsTrieTest::TestBuilder() {
 123     IcuTestErrorCode errorCode(*this, "TestBuilder()");
 124     delete builder_->build(USTRINGTRIE_BUILD_FAST, errorCode);
 125     if(errorCode.reset()!=U_INDEX_OUTOFBOUNDS_ERROR) {
 126         errln("UCharsTrieBuilder().build() did not set U_INDEX_OUTOFBOUNDS_ERROR");
 127         return;
 128     }
 129     // TODO: remove .build(...) once add() checks for duplicates.
 130     builder_->add("=", 0, errorCode).add("=", 1, errorCode).build(USTRINGTRIE_BUILD_FAST, errorCode);
 131     if(errorCode.reset()!=U_ILLEGAL_ARGUMENT_ERROR) {
 132         errln("UCharsTrieBuilder.add() did not detect duplicates");
 133         return;
 134     }
 135 }
 136
 137 void UCharsTrieTest::TestEmpty() {
 138     static const StringAndValue data[]={
 139         { "", 0 }
 140     };
 141     checkData(data, LENGTHOF(data));
 142 }
 143
 144 void UCharsTrieTest::Test_a() {
 145     static const StringAndValue data[]={
 146         { "a", 1 }
 147     };
 148     checkData(data, LENGTHOF(data));
 149 }
 150
 151 void UCharsTrieTest::Test_a_ab() {
 152     static const StringAndValue data[]={
 153         { "a", 1 },
 154         { "ab", 100 }
 155     };
 156     checkData(data, LENGTHOF(data));
 157 }
 158
 159 void UCharsTrieTest::TestShortestBranch() {
 160     static const StringAndValue data[]={
 161         { "a", 1000 },
 162         { "b", 2000 }
 163     };
 164     checkData(data, LENGTHOF(data));
 165 }
 166
 167 void UCharsTrieTest::TestBranches() {
 168     static const StringAndValue data[]={
 169         { "a", 0x10 },
 170         { "cc", 0x40 },
 171         { "e", 0x100 },
 172         { "ggg", 0x400 },
 173         { "i", 0x1000 },
 174         { "kkkk", 0x4000 },
 175         { "n", 0x10000 },
 176         { "ppppp", 0x40000 },
 177         { "r", 0x100000 },
 178         { "sss", 0x200000 },
 179         { "t", 0x400000 },
 180         { "uu", 0x800000 },
 181         { "vv", 0x7fffffff },
 182         { "zz", (int32_t)0x80000000 }
 183     };
 184     for(int32_t length=2; length<=LENGTHOF(data); ++length) {
 185         infoln("TestBranches length=%d", (int)length);
 186         checkData(data, length);
 187     }
 188 }
 189
 190 void UCharsTrieTest::TestLongSequence() {
 191     static const StringAndValue data[]={
 192         { "a", -1 },
 193         // sequence of linear-match nodes
 194         { "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", -2 },
 195         // more than 256 units
 196         { "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 197           "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 198           "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 199           "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 200           "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 201           "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", -3 }
 202     };
 203     checkData(data, LENGTHOF(data));
 204 }
 205
 206 void UCharsTrieTest::TestLongBranch() {
 207     // Split-branch and interesting compact-integer values.
 208     static const StringAndValue data[]={
 209         { "a", -2 },
 210         { "b", -1 },
 211         { "c", 0 },
 212         { "d2", 1 },
 213         { "f", 0x3f },
 214         { "g", 0x40 },
 215         { "h", 0x41 },
 216         { "j23", 0x1900 },
 217         { "j24", 0x19ff },
 218         { "j25", 0x1a00 },
 219         { "k2", 0x1a80 },
 220         { "k3", 0x1aff },
 221         { "l234567890", 0x1b00 },
 222         { "l234567890123", 0x1b01 },
 223         { "nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn", 0x10ffff },
 224         { "oooooooooooooooooooooooooooooooooooooooooooooooooooooo", 0x110000 },
 225         { "pppppppppppppppppppppppppppppppppppppppppppppppppppppp", 0x120000 },
 226         { "r", 0x333333 },
 227         { "s2345", 0x4444444 },
 228         { "t234567890", 0x77777777 },
 229         { "z", (int32_t)0x80000001 }
 230     };
 231     checkData(data, LENGTHOF(data));
 232 }
 233
 234 void UCharsTrieTest::TestValuesForState() {
 235     // Check that saveState() and resetToState() interact properly
 236     // with next() and current().
 237     static const StringAndValue data[]={
 238         { "a", -1 },
 239         { "ab", -2 },
 240         { "abc", -3 },
 241         { "abcd", -4 },
 242         { "abcde", -5 },
 243         { "abcdef", -6 }
 244     };
 245     checkData(data, LENGTHOF(data));
 246 }
 247
 248 void UCharsTrieTest::TestCompact() {
 249     // Duplicate trailing strings and values provide opportunities for compacting.
 250     static const StringAndValue data[]={
 251         { "+", 0 },
 252         { "+august", 8 },
 253         { "+december", 12 },
 254         { "+july", 7 },
 255         { "+june", 6 },
 256         { "+november", 11 },
 257         { "+october", 10 },
 258         { "+september", 9 },
 259         { "-", 0 },
 260         { "-august", 8 },
 261         { "-december", 12 },
 262         { "-july", 7 },
 263         { "-june", 6 },
 264         { "-november", 11 },
 265         { "-october", 10 },
 266         { "-september", 9 },
 267         // The l+n branch (with its sub-nodes) is a duplicate but will be written
 268         // both times because each time it follows a different linear-match node.
 269         { "xjuly", 7 },
 270         { "xjune", 6 }
 271     };
 272     checkData(data, LENGTHOF(data));
 273 }
 274
 275 void UCharsTrieTest::TestFirstForCodePoint() {
 276     static const StringAndValue data[]={
 277         { "a", 1 },
 278         { "a\\ud800", 2 },
 279         { "a\\U00010000", 3 },
 280         { "\\ud840", 4 },
 281         { "\\U00020000\\udbff", 5 },
 282         { "\\U00020000\\U0010ffff", 6 },
 283         { "\\U00020000\\U0010ffffz", 7 },
 284         { "\\U00050000xy", 8 },
 285         { "\\U00050000xyz", 9 }
 286     };
 287     checkData(data, LENGTHOF(data));
 288 }
 289
 290 void UCharsTrieTest::TestNextForCodePoint() {
 291     static const StringAndValue data[]={
 292         { "\\u4dff\\U00010000\\u9999\\U00020000\\udfff\\U0010ffff", 2000000000 },
 293         { "\\u4dff\\U00010000\\u9999\\U00020002", 44444 },
 294         { "\\u4dff\\U000103ff", 99999 }
 295     };
 296     LocalPointer<UCharsTrie> trie(buildTrie(data, LENGTHOF(data), USTRINGTRIE_BUILD_FAST));
 297     if(trie.isNull()) {
 298         return;  // buildTrie() reported an error
 299     }
 300     UStringTrieResult result;
 301     if( (result=trie->nextForCodePoint(0x4dff))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 302         (result=trie->nextForCodePoint(0x10000))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 303         (result=trie->nextForCodePoint(0x9999))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 304         (result=trie->nextForCodePoint(0x20000))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 305         (result=trie->nextForCodePoint(0xdfff))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 306         (result=trie->nextForCodePoint(0x10ffff))!=USTRINGTRIE_FINAL_VALUE || result!=trie->current() ||
 307         trie->getValue()!=2000000000
 308     ) {
 309         errln("UCharsTrie.nextForCodePoint() fails for %s", data[0].s);
 310     }
 311     if( (result=trie->firstForCodePoint(0x4dff))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 312         (result=trie->nextForCodePoint(0x10000))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 313         (result=trie->nextForCodePoint(0x9999))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 314         (result=trie->nextForCodePoint(0x20002))!=USTRINGTRIE_FINAL_VALUE || result!=trie->current() ||
 315         trie->getValue()!=44444
 316     ) {
 317         errln("UCharsTrie.nextForCodePoint() fails for %s", data[1].s);
 318     }
 319     if( (result=trie->reset().nextForCodePoint(0x4dff))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 320         (result=trie->nextForCodePoint(0x10000))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 321         (result=trie->nextForCodePoint(0x9999))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 322         (result=trie->nextForCodePoint(0x20222))!=USTRINGTRIE_NO_MATCH || result!=trie->current()  // no match for trail surrogate
 323     ) {
 324         errln("UCharsTrie.nextForCodePoint() fails for \\u4dff\\U00010000\\u9999\\U00020222");
 325     }
 326     if( (result=trie->reset().nextForCodePoint(0x4dff))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 327         (result=trie->nextForCodePoint(0x103ff))!=USTRINGTRIE_FINAL_VALUE || result!=trie->current() ||
 328         trie->getValue()!=99999
 329     ) {
 330         errln("UCharsTrie.nextForCodePoint() fails for %s", data[2].s);
 331     }
 332 }
 333
 334 // Definitions in the anonymous namespace are invisible outside this file.
 335 namespace {
 336
 337 // Generate (string, value) pairs.
 338 // The first string (before next()) will be empty.
 339 class Generator {
 340 public:
 341     Generator() : value(4711), num(0) {}
 342     void next() {
 343         UChar c;
 344         s.truncate(0);
 345         s.append(c=(UChar)(value>>16));
 346         s.append((UChar)(value>>4));
 347         if(value&1) {
 348             s.append((UChar)value);
 349         }
 350         set.add(c);
 351         value+=((value>>5)&0x7ff)*3+1;
 352         ++num;
 353     }
 354     const UnicodeString &getString() const { return s; }
 355     int32_t getValue() const { return value; }
 356     int32_t countUniqueFirstChars() const { return set.size(); }
 357     int32_t getIndex() const { return num; }
 358
 359 private:
 360     UnicodeString s;
 361     UnicodeSet set;
 362     int32_t value;
 363     int32_t num;
 364 };
 365
 366 }  // end namespace
 367
 368 UCharsTrie *UCharsTrieTest::buildLargeTrie(int32_t numUniqueFirst) {
 369     IcuTestErrorCode errorCode(*this, "buildLargeTrie()");
 370     Generator gen;
 371     builder_->clear();
 372     while(gen.countUniqueFirstChars()<numUniqueFirst) {
 373         builder_->add(gen.getString(), gen.getValue(), errorCode);
 374         gen.next();
 375     }
 376     infoln("buildLargeTrie(%ld) added %ld strings", (long)numUniqueFirst, (long)gen.getIndex());
 377     UnicodeString trieUChars;
 378     builder_->buildUnicodeString(USTRINGTRIE_BUILD_FAST, trieUChars, errorCode);
 379     logln("serialized trie size: %ld UChars\n", (long)trieUChars.length());
 380     return new UCharsTrie(trieUChars.getBuffer());
 381 }
 382
 383 // Exercise a large branch node.
 384 void UCharsTrieTest::TestLargeTrie() {
 385     LocalPointer<UCharsTrie> trie(buildLargeTrie(1111));
 386     if(trie.isNull()) {
 387         return;  // buildTrie() reported an error
 388     }
 389     Generator gen;
 390     while(gen.countUniqueFirstChars()<1111) {
 391         UnicodeString x(gen.getString());
 392         int32_t value=gen.getValue();
 393         if(!x.isEmpty()) {
 394             if(trie->first(x[0])==USTRINGTRIE_NO_MATCH) {
 395                 errln("first(first char U+%04X)=USTRINGTRIE_NO_MATCH for string %ld\n",
 396                       x[0], (long)gen.getIndex());
 397                 break;
 398             }
 399             x.remove(0, 1);
 400         }
 401         UStringTrieResult result=trie->next(x.getBuffer(), x.length());
 402         if(!USTRINGTRIE_HAS_VALUE(result) || result!=trie->current() || value!=trie->getValue()) {
 403             errln("next(%d chars U+%04X U+%04X)!=hasValue or "
 404                   "next()!=current() or getValue() wrong "
 405                   "for string %ld\n", (int)x.length(), x[0], x[1], (long)gen.getIndex());
 406             break;
 407         }
 408         gen.next();
 409     }
 410 }
 411
 412 enum {
 413     u_a=0x61,
 414     u_b=0x62,
 415     u_c=0x63,
 416     u_j=0x6a,
 417     u_n=0x6e,
 418     u_r=0x72,
 419     u_u=0x75,
 420     u_y=0x79
 421 };
 422
 423 UCharsTrie *UCharsTrieTest::buildMonthsTrie(UStringTrieBuildOption buildOption) {
 424     // All types of nodes leading to the same value,
 425     // for code coverage of recursive functions.
 426     // In particular, we need a lot of branches on some single level
 427     // to exercise a split-branch node.
 428     static const StringAndValue data[]={
 429         { "august", 8 },
 430         { "jan", 1 },
 431         { "jan.", 1 },
 432         { "jana", 1 },
 433         { "janbb", 1 },
 434         { "janc", 1 },
 435         { "janddd", 1 },
 436         { "janee", 1 },
 437         { "janef", 1 },
 438         { "janf", 1 },
 439         { "jangg", 1 },
 440         { "janh", 1 },
 441         { "janiiii", 1 },
 442         { "janj", 1 },
 443         { "jankk", 1 },
 444         { "jankl", 1 },
 445         { "jankmm", 1 },
 446         { "janl", 1 },
 447         { "janm", 1 },
 448         { "jannnnnnnnnnnnnnnnnnnnnnnnnnnnn", 1 },
 449         { "jano", 1 },
 450         { "janpp", 1 },
 451         { "janqqq", 1 },
 452         { "janr", 1 },
 453         { "januar", 1 },
 454         { "january", 1 },
 455         { "july", 7 },
 456         { "jun", 6 },
 457         { "jun.", 6 },
 458         { "june", 6 }
 459     };
 460     return buildTrie(data, LENGTHOF(data), buildOption);
 461 }
 462
 463 void UCharsTrieTest::TestHasUniqueValue() {
 464     LocalPointer<UCharsTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_FAST));
 465     if(trie.isNull()) {
 466         return;  // buildTrie() reported an error
 467     }
 468     int32_t uniqueValue;
 469     if(trie->hasUniqueValue(uniqueValue)) {
 470         errln("unique value at root");
 471     }
 472     trie->next(u_j);
 473     trie->next(u_a);
 474     trie->next(u_n);
 475     // hasUniqueValue() directly after next()
 476     if(!trie->hasUniqueValue(uniqueValue) || uniqueValue!=1) {
 477         errln("not unique value 1 after \"jan\"");
 478     }
 479     trie->first(u_j);
 480     trie->next(u_u);
 481     if(trie->hasUniqueValue(uniqueValue)) {
 482         errln("unique value after \"ju\"");
 483     }
 484     if(trie->next(u_n)!=USTRINGTRIE_INTERMEDIATE_VALUE || 6!=trie->getValue()) {
 485         errln("not normal value 6 after \"jun\"");
 486     }
 487     // hasUniqueValue() after getValue()
 488     if(!trie->hasUniqueValue(uniqueValue) || uniqueValue!=6) {
 489         errln("not unique value 6 after \"jun\"");
 490     }
 491     // hasUniqueValue() from within a linear-match node
 492     trie->first(u_a);
 493     trie->next(u_u);
 494     if(!trie->hasUniqueValue(uniqueValue) || uniqueValue!=8) {
 495         errln("not unique value 8 after \"au\"");
 496     }
 497 }
 498
 499 void UCharsTrieTest::TestGetNextUChars() {
 500     LocalPointer<UCharsTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_SMALL));
 501     if(trie.isNull()) {
 502         return;  // buildTrie() reported an error
 503     }
 504     UnicodeString buffer;
 505     UnicodeStringAppendable app(buffer);
 506     int32_t count=trie->getNextUChars(app);
 507     if(count!=2 || buffer.length()!=2 || buffer[0]!=u_a || buffer[1]!=u_j) {
 508         errln("months getNextUChars()!=[aj] at root");
 509     }
 510     trie->next(u_j);
 511     trie->next(u_a);
 512     trie->next(u_n);
 513     // getNextUChars() directly after next()
 514     buffer.remove();
 515     count=trie->getNextUChars(app);
 516     if(count!=20 || buffer!=UNICODE_STRING_SIMPLE(".abcdefghijklmnopqru")) {
 517         errln("months getNextUChars()!=[.abcdefghijklmnopqru] after \"jan\"");
 518     }
 519     // getNextUChars() after getValue()
 520     trie->getValue();  // next() had returned USTRINGTRIE_INTERMEDIATE_VALUE.
 521     buffer.remove();
 522     count=trie->getNextUChars(app);
 523     if(count!=20 || buffer!=UNICODE_STRING_SIMPLE(".abcdefghijklmnopqru")) {
 524         errln("months getNextUChars()!=[.abcdefghijklmnopqru] after \"jan\"+getValue()");
 525     }
 526     // getNextUChars() from a linear-match node
 527     trie->next(u_u);
 528     buffer.remove();
 529     count=trie->getNextUChars(app);
 530     if(count!=1 || buffer.length()!=1 || buffer[0]!=u_a) {
 531         errln("months getNextUChars()!=[a] after \"janu\"");
 532     }
 533     trie->next(u_a);
 534     buffer.remove();
 535     count=trie->getNextUChars(app);
 536     if(count!=1 || buffer.length()!=1 || buffer[0]!=u_r) {
 537         errln("months getNextUChars()!=[r] after \"janua\"");
 538     }
 539     trie->next(u_r);
 540     trie->next(u_y);
 541     // getNextUChars() after a final match
 542     buffer.remove();
 543     count=trie->getNextUChars(app);
 544     if(count!=0 || buffer.length()!=0) {
 545         errln("months getNextUChars()!=[] after \"january\"");
 546     }
 547 }
 548
 549 void UCharsTrieTest::TestIteratorFromBranch() {
 550     LocalPointer<UCharsTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_FAST));
 551     if(trie.isNull()) {
 552         return;  // buildTrie() reported an error
 553     }
 554     // Go to a branch node.
 555     trie->next(u_j);
 556     trie->next(u_a);
 557     trie->next(u_n);
 558     IcuTestErrorCode errorCode(*this, "TestIteratorFromBranch()");
 559     UCharsTrie::Iterator iter(*trie, 0, errorCode);
 560     if(errorCode.logIfFailureAndReset("UCharsTrie::Iterator(trie) constructor")) {
 561         return;
 562     }
 563     // Expected data: Same as in buildMonthsTrie(), except only the suffixes
 564     // following "jan".
 565     static const StringAndValue data[]={
 566         { "", 1 },
 567         { ".", 1 },
 568         { "a", 1 },
 569         { "bb", 1 },
 570         { "c", 1 },
 571         { "ddd", 1 },
 572         { "ee", 1 },
 573         { "ef", 1 },
 574         { "f", 1 },
 575         { "gg", 1 },
 576         { "h", 1 },
 577         { "iiii", 1 },
 578         { "j", 1 },
 579         { "kk", 1 },
 580         { "kl", 1 },
 581         { "kmm", 1 },
 582         { "l", 1 },
 583         { "m", 1 },
 584         { "nnnnnnnnnnnnnnnnnnnnnnnnnnnn", 1 },
 585         { "o", 1 },
 586         { "pp", 1 },
 587         { "qqq", 1 },
 588         { "r", 1 },
 589         { "uar", 1 },
 590         { "uary", 1 }
 591     };
 592     checkIterator(iter, data, LENGTHOF(data));
 593     // Reset, and we should get the same result.
 594     logln("after iter.reset()");
 595     checkIterator(iter.reset(), data, LENGTHOF(data));
 596 }
 597
 598 void UCharsTrieTest::TestIteratorFromLinearMatch() {
 599     LocalPointer<UCharsTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_SMALL));
 600     if(trie.isNull()) {
 601         return;  // buildTrie() reported an error
 602     }
 603     // Go into a linear-match node.
 604     trie->next(u_j);
 605     trie->next(u_a);
 606     trie->next(u_n);
 607     trie->next(u_u);
 608     trie->next(u_a);
 609     IcuTestErrorCode errorCode(*this, "TestIteratorFromLinearMatch()");
 610     UCharsTrie::Iterator iter(*trie, 0, errorCode);
 611     if(errorCode.logIfFailureAndReset("UCharsTrie::Iterator(trie) constructor")) {
 612         return;
 613     }
 614     // Expected data: Same as in buildMonthsTrie(), except only the suffixes
 615     // following "janua".
 616     static const StringAndValue data[]={
 617         { "r", 1 },
 618         { "ry", 1 }
 619     };
 620     checkIterator(iter, data, LENGTHOF(data));
 621     // Reset, and we should get the same result.
 622     logln("after iter.reset()");
 623     checkIterator(iter.reset(), data, LENGTHOF(data));
 624 }
 625
 626 void UCharsTrieTest::TestTruncatingIteratorFromRoot() {
 627     LocalPointer<UCharsTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_FAST));
 628     if(trie.isNull()) {
 629         return;  // buildTrie() reported an error
 630     }
 631     IcuTestErrorCode errorCode(*this, "TestTruncatingIteratorFromRoot()");
 632     UCharsTrie::Iterator iter(*trie, 4, errorCode);
 633     if(errorCode.logIfFailureAndReset("UCharsTrie::Iterator(trie) constructor")) {
 634         return;
 635     }
 636     // Expected data: Same as in buildMonthsTrie(), except only the first 4 characters
 637     // of each string, and no string duplicates from the truncation.
 638     static const StringAndValue data[]={
 639         { "augu", -1 },
 640         { "jan", 1 },
 641         { "jan.", 1 },
 642         { "jana", 1 },
 643         { "janb", -1 },
 644         { "janc", 1 },
 645         { "jand", -1 },
 646         { "jane", -1 },
 647         { "janf", 1 },
 648         { "jang", -1 },
 649         { "janh", 1 },
 650         { "jani", -1 },
 651         { "janj", 1 },
 652         { "jank", -1 },
 653         { "janl", 1 },
 654         { "janm", 1 },
 655         { "jann", -1 },
 656         { "jano", 1 },
 657         { "janp", -1 },
 658         { "janq", -1 },
 659         { "janr", 1 },
 660         { "janu", -1 },
 661         { "july", 7 },
 662         { "jun", 6 },
 663         { "jun.", 6 },
 664         { "june", 6 }
 665     };
 666     checkIterator(iter, data, LENGTHOF(data));
 667     // Reset, and we should get the same result.
 668     logln("after iter.reset()");
 669     checkIterator(iter.reset(), data, LENGTHOF(data));
 670 }
 671
 672 void UCharsTrieTest::TestTruncatingIteratorFromLinearMatchShort() {
 673     static const StringAndValue data[]={
 674         { "abcdef", 10 },
 675         { "abcdepq", 200 },
 676         { "abcdeyz", 3000 }
 677     };
 678     LocalPointer<UCharsTrie> trie(buildTrie(data, LENGTHOF(data), USTRINGTRIE_BUILD_FAST));
 679     if(trie.isNull()) {
 680         return;  // buildTrie() reported an error
 681     }
 682     // Go into a linear-match node.
 683     trie->next(u_a);
 684     trie->next(u_b);
 685     IcuTestErrorCode errorCode(*this, "TestTruncatingIteratorFromLinearMatchShort()");
 686     // Truncate within the linear-match node.
 687     UCharsTrie::Iterator iter(*trie, 2, errorCode);
 688     if(errorCode.logIfFailureAndReset("UCharsTrie::Iterator(trie) constructor")) {
 689         return;
 690     }
 691     static const StringAndValue expected[]={
 692         { "cd", -1 }
 693     };
 694     checkIterator(iter, expected, LENGTHOF(expected));
 695     // Reset, and we should get the same result.
 696     logln("after iter.reset()");
 697     checkIterator(iter.reset(), expected, LENGTHOF(expected));
 698 }
 699
 700 void UCharsTrieTest::TestTruncatingIteratorFromLinearMatchLong() {
 701     static const StringAndValue data[]={
 702         { "abcdef", 10 },
 703         { "abcdepq", 200 },
 704         { "abcdeyz", 3000 }
 705     };
 706     LocalPointer<UCharsTrie> trie(buildTrie(data, LENGTHOF(data), USTRINGTRIE_BUILD_FAST));
 707     if(trie.isNull()) {
 708         return;  // buildTrie() reported an error
 709     }
 710     // Go into a linear-match node.
 711     trie->next(u_a);
 712     trie->next(u_b);
 713     trie->next(u_c);
 714     IcuTestErrorCode errorCode(*this, "TestTruncatingIteratorFromLinearMatchLong()");
 715     // Truncate after the linear-match node.
 716     UCharsTrie::Iterator iter(*trie, 3, errorCode);
 717     if(errorCode.logIfFailureAndReset("UCharsTrie::Iterator(trie) constructor")) {
 718         return;
 719     }
 720     static const StringAndValue expected[]={
 721         { "def", 10 },
 722         { "dep", -1 },
 723         { "dey", -1 }
 724     };
 725     checkIterator(iter, expected, LENGTHOF(expected));
 726     // Reset, and we should get the same result.
 727     logln("after iter.reset()");
 728     checkIterator(iter.reset(), expected, LENGTHOF(expected));
 729 }
 730
 731 void UCharsTrieTest::TestIteratorFromUChars() {
 732     static const StringAndValue data[]={
 733         { "mm", 3 },
 734         { "mmm", 33 },
 735         { "mmnop", 333 }
 736     };
 737     builder_->clear();
 738     IcuTestErrorCode errorCode(*this, "TestIteratorFromUChars()");
 739     for(int32_t i=0; i<LENGTHOF(data); ++i) {
 740         builder_->add(data[i].s, data[i].value, errorCode);
 741     }
 742     UnicodeString trieUChars;
 743     builder_->buildUnicodeString(USTRINGTRIE_BUILD_FAST, trieUChars, errorCode);
 744     UCharsTrie::Iterator iter(trieUChars.getBuffer(), 0, errorCode);
 745     checkIterator(iter, data, LENGTHOF(data));
 746 }
 747
 748 void UCharsTrieTest::checkData(const StringAndValue data[], int32_t dataLength) {
 749     logln("checkData(dataLength=%d, fast)", (int)dataLength);
 750     checkData(data, dataLength, USTRINGTRIE_BUILD_FAST);
 751     logln("checkData(dataLength=%d, small)", (int)dataLength);
 752     checkData(data, dataLength, USTRINGTRIE_BUILD_SMALL);
 753 }
 754
 755 void UCharsTrieTest::checkData(const StringAndValue data[], int32_t dataLength, UStringTrieBuildOption buildOption) {
 756     LocalPointer<UCharsTrie> trie(buildTrie(data, dataLength, buildOption));
 757     if(trie.isNull()) {
 758         return;  // buildTrie() reported an error
 759     }
 760     checkFirst(*trie, data, dataLength);
 761     checkNext(*trie, data, dataLength);
 762     checkNextWithState(*trie, data, dataLength);
 763     checkNextString(*trie, data, dataLength);
 764     checkIterator(*trie, data, dataLength);
 765 }
 766
 767 UCharsTrie *UCharsTrieTest::buildTrie(const StringAndValue data[], int32_t dataLength,
 768                                       UStringTrieBuildOption buildOption) {
 769     IcuTestErrorCode errorCode(*this, "buildTrie()");
 770     // Add the items to the trie builder in an interesting (not trivial, not random) order.
 771     int32_t index, step;
 772     if(dataLength&1) {
 773         // Odd number of items.
 774         index=dataLength/2;
 775         step=2;
 776     } else if((dataLength%3)!=0) {
 777         // Not a multiple of 3.
 778         index=dataLength/5;
 779         step=3;
 780     } else {
 781         index=dataLength-1;
 782         step=-1;
 783     }
 784     builder_->clear();
 785     for(int32_t i=0; i<dataLength; ++i) {
 786         builder_->add(UnicodeString(data[index].s, -1, US_INV).unescape(),
 787                       data[index].value, errorCode);
 788         index=(index+step)%dataLength;
 789     }
 790     UnicodeString trieUChars;
 791     builder_->buildUnicodeString(buildOption, trieUChars, errorCode);
 792     LocalPointer<UCharsTrie> trie(builder_->build(buildOption, errorCode));
 793     if(!errorCode.logIfFailureAndReset("add()/build()")) {
 794         builder_->add("zzz", 999, errorCode);
 795         if(errorCode.reset()!=U_NO_WRITE_PERMISSION) {
 796             errln("builder.build().add(zzz) did not set U_NO_WRITE_PERMISSION");
 797         }
 798     }
 799     logln("serialized trie size: %ld UChars\n", (long)trieUChars.length());
 800     UnicodeString trieUChars2;
 801     builder_->buildUnicodeString(buildOption, trieUChars2, errorCode);
 802     if(trieUChars.getBuffer()==trieUChars2.getBuffer()) {
 803         errln("builder.buildUnicodeString() before & after build() returned same array");
 804     }
 805     if(errorCode.isFailure()) {
 806         return NULL;
 807     }
 808     // Tries from either build() method should be identical but
 809     // UCharsTrie does not implement equals().
 810     // We just return either one.
 811     if((dataLength&1)!=0) {
 812         return trie.orphan();
 813     } else {
 814         return new UCharsTrie(trieUChars2.getBuffer());
 815     }
 816 }
 817
 818 void UCharsTrieTest::checkFirst(UCharsTrie &trie,
 819                                 const StringAndValue data[], int32_t dataLength) {
 820     for(int32_t i=0; i<dataLength; ++i) {
 821         if(*data[i].s==0) {
 822             continue;  // skip empty string
 823         }
 824         UnicodeString expectedString=UnicodeString(data[i].s, -1, US_INV).unescape();
 825         UChar32 c=expectedString[0];
 826         UChar32 nextCp=expectedString.length()>1 ? expectedString[1] : 0;
 827         UStringTrieResult firstResult=trie.first(c);
 828         int32_t firstValue=USTRINGTRIE_HAS_VALUE(firstResult) ? trie.getValue() : -1;
 829         UStringTrieResult nextResult=trie.next(nextCp);
 830         if(firstResult!=trie.reset().next(c) ||
 831            firstResult!=trie.current() ||
 832            firstValue!=(USTRINGTRIE_HAS_VALUE(firstResult) ? trie.getValue() : -1) ||
 833            nextResult!=trie.next(nextCp)
 834         ) {
 835             errln("trie.first(U+%04X)!=trie.reset().next(same) for %s",
 836                   c, data[i].s);
 837         }
 838         c=expectedString.char32At(0);
 839         int32_t cLength=U16_LENGTH(c);
 840         nextCp=expectedString.length()>cLength ? expectedString.char32At(cLength) : 0;
 841         firstResult=trie.firstForCodePoint(c);
 842         firstValue=USTRINGTRIE_HAS_VALUE(firstResult) ? trie.getValue() : -1;
 843         nextResult=trie.nextForCodePoint(nextCp);
 844         if(firstResult!=trie.reset().nextForCodePoint(c) ||
 845            firstResult!=trie.current() ||
 846            firstValue!=(USTRINGTRIE_HAS_VALUE(firstResult) ? trie.getValue() : -1) ||
 847            nextResult!=trie.nextForCodePoint(nextCp)
 848         ) {
 849             errln("trie.firstForCodePoint(U+%04X)!=trie.reset().nextForCodePoint(same) for %s",
 850                   c, data[i].s);
 851         }
 852     }
 853     trie.reset();
 854 }
 855
 856 void UCharsTrieTest::checkNext(UCharsTrie &trie,
 857                                const StringAndValue data[], int32_t dataLength) {
 858     UCharsTrie::State state;
 859     for(int32_t i=0; i<dataLength; ++i) {
 860         UnicodeString expectedString=UnicodeString(data[i].s, -1, US_INV).unescape();
 861         int32_t stringLength= (i&1) ? -1 : expectedString.length();
 862         UStringTrieResult result;
 863         if( !USTRINGTRIE_HAS_VALUE(
 864                 result=trie.next(expectedString.getTerminatedBuffer(), stringLength)) ||
 865             result!=trie.current()
 866         ) {
 867             errln("trie does not seem to contain %s", data[i].s);
 868         } else if(trie.getValue()!=data[i].value) {
 869             errln("trie value for %s is %ld=0x%lx instead of expected %ld=0x%lx",
 870                   data[i].s,
 871                   (long)trie.getValue(), (long)trie.getValue(),
 872                   (long)data[i].value, (long)data[i].value);
 873         } else if(result!=trie.current() || trie.getValue()!=data[i].value) {
 874             errln("trie value for %s changes when repeating current()/getValue()", data[i].s);
 875         }
 876         trie.reset();
 877         stringLength=expectedString.length();
 878         result=trie.current();
 879         for(int32_t j=0; j<stringLength; ++j) {
 880             if(!USTRINGTRIE_HAS_NEXT(result)) {
 881                 errln("trie.current()!=hasNext before end of %s (at index %d)", data[i].s, j);
 882                 break;
 883             }
 884             if(result==USTRINGTRIE_INTERMEDIATE_VALUE) {
 885                 trie.getValue();
 886                 if(trie.current()!=USTRINGTRIE_INTERMEDIATE_VALUE) {
 887                     errln("trie.getValue().current()!=USTRINGTRIE_INTERMEDIATE_VALUE before end of %s (at index %d)", data[i].s, j);
 888                     break;
 889                 }
 890             }
 891             result=trie.next(expectedString[j]);
 892             if(!USTRINGTRIE_MATCHES(result)) {
 893                 errln("trie.next()=USTRINGTRIE_NO_MATCH before end of %s (at index %d)", data[i].s, j);
 894                 break;
 895             }
 896             if(result!=trie.current()) {
 897                 errln("trie.next()!=following current() before end of %s (at index %d)", data[i].s, j);
 898                 break;
 899             }
 900         }
 901         if(!USTRINGTRIE_HAS_VALUE(result)) {
 902             errln("trie.next()!=hasValue at the end of %s", data[i].s);
 903             continue;
 904         }
 905         trie.getValue();
 906         if(result!=trie.current()) {
 907             errln("trie.current() != current()+getValue()+current() after end of %s",
 908                   data[i].s);
 909         }
 910         // Compare the final current() with whether next() can actually continue.
 911         trie.saveState(state);
 912         UBool nextContinues=FALSE;
 913         for(int32_t c=0x20; c<0xe000; ++c) {
 914             if(c==0x80) {
 915                 c=0xd800;  // Check for ASCII and surrogates but not all of the BMP.
 916             }
 917             if(trie.resetToState(state).next(c)) {
 918                 nextContinues=TRUE;
 919                 break;
 920             }
 921         }
 922         if((result==USTRINGTRIE_INTERMEDIATE_VALUE)!=nextContinues) {
 923             errln("(trie.current()==USTRINGTRIE_INTERMEDIATE_VALUE) contradicts "
 924                   "(trie.next(some UChar)!=USTRINGTRIE_NO_MATCH) after end of %s", data[i].s);
 925         }
 926         trie.reset();
 927     }
 928 }
 929
 930 void UCharsTrieTest::checkNextWithState(UCharsTrie &trie,
 931                                         const StringAndValue data[], int32_t dataLength) {
 932     UCharsTrie::State noState, state;
 933     for(int32_t i=0; i<dataLength; ++i) {
 934         if((i&1)==0) {
 935             // This should have no effect.
 936             trie.resetToState(noState);
 937         }
 938         UnicodeString expectedString=UnicodeString(data[i].s, -1, US_INV).unescape();
 939         int32_t stringLength=expectedString.length();
 940         int32_t partialLength=stringLength/3;
 941         for(int32_t j=0; j<partialLength; ++j) {
 942             if(!USTRINGTRIE_MATCHES(trie.next(expectedString[j]))) {
 943                 errln("trie.next()=USTRINGTRIE_NO_MATCH for a prefix of %s", data[i].s);
 944                 return;
 945             }
 946         }
 947         trie.saveState(state);
 948         UStringTrieResult resultAtState=trie.current();
 949         UStringTrieResult result;
 950         int32_t valueAtState=-99;
 951         if(USTRINGTRIE_HAS_VALUE(resultAtState)) {
 952             valueAtState=trie.getValue();
 953         }
 954         result=trie.next(0);  // mismatch
 955         if(result!=USTRINGTRIE_NO_MATCH || result!=trie.current()) {
 956             errln("trie.next(0) matched after part of %s", data[i].s);
 957         }
 958         if( resultAtState!=trie.resetToState(state).current() ||
 959             (USTRINGTRIE_HAS_VALUE(resultAtState) && valueAtState!=trie.getValue())
 960         ) {
 961             errln("trie.next(part of %s) changes current()/getValue() after "
 962                   "saveState/next(0)/resetToState",
 963                   data[i].s);
 964         } else if(!USTRINGTRIE_HAS_VALUE(
 965                       result=trie.next(expectedString.getTerminatedBuffer()+partialLength,
 966                                        stringLength-partialLength)) ||
 967                   result!=trie.current()) {
 968             errln("trie.next(rest of %s) does not seem to contain %s after "
 969                   "saveState/next(0)/resetToState",
 970                   data[i].s, data[i].s);
 971         } else if(!USTRINGTRIE_HAS_VALUE(
 972                       result=trie.resetToState(state).
 973                                   next(expectedString.getTerminatedBuffer()+partialLength,
 974                                        stringLength-partialLength)) ||
 975                   result!=trie.current()) {
 976             errln("trie does not seem to contain %s after saveState/next(rest)/resetToState",
 977                   data[i].s);
 978         } else if(trie.getValue()!=data[i].value) {
 979             errln("trie value for %s is %ld=0x%lx instead of expected %ld=0x%lx",
 980                   data[i].s,
 981                   (long)trie.getValue(), (long)trie.getValue(),
 982                   (long)data[i].value, (long)data[i].value);
 983         }
 984         trie.reset();
 985     }
 986 }
 987
 988 // next(string) is also tested in other functions,
 989 // but here we try to go partway through the string, and then beyond it.
 990 void UCharsTrieTest::checkNextString(UCharsTrie &trie,
 991                                      const StringAndValue data[], int32_t dataLength) {
 992     for(int32_t i=0; i<dataLength; ++i) {
 993         UnicodeString expectedString=UnicodeString(data[i].s, -1, US_INV).unescape();
 994         int32_t stringLength=expectedString.length();
 995         if(!trie.next(expectedString.getTerminatedBuffer(), stringLength/2)) {
 996             errln("trie.next(up to middle of string)=USTRINGTRIE_NO_MATCH for %s", data[i].s);
 997             continue;
 998         }
 999         // Test that we stop properly at the end of the string.
1000         if(trie.next(expectedString.getTerminatedBuffer()+stringLength/2,
1001                      stringLength+1-stringLength/2)) {
1002             errln("trie.next(string+NUL)!=USTRINGTRIE_NO_MATCH for %s", data[i].s);
1003         }
1004         trie.reset();
1005     }
1006 }
1007
1008 void UCharsTrieTest::checkIterator(UCharsTrie &trie,
1009                                    const StringAndValue data[], int32_t dataLength) {
1010     IcuTestErrorCode errorCode(*this, "checkIterator()");
1011     UCharsTrie::Iterator iter(trie, 0, errorCode);
1012     if(errorCode.logIfFailureAndReset("UCharsTrie::Iterator(trieUChars) constructor")) {
1013         return;
1014     }
1015     checkIterator(iter, data, dataLength);
1016 }
1017
1018 void UCharsTrieTest::checkIterator(UCharsTrie::Iterator &iter,
1019                                    const StringAndValue data[], int32_t dataLength) {
1020     IcuTestErrorCode errorCode(*this, "checkIterator()");
1021     for(int32_t i=0; i<dataLength; ++i) {
1022         if(!iter.hasNext()) {
1023             errln("trie iterator hasNext()=FALSE for item %d: %s", (int)i, data[i].s);
1024             break;
1025         }
1026         UBool hasNext=iter.next(errorCode);
1027         if(errorCode.logIfFailureAndReset("trie iterator next() for item %d: %s", (int)i, data[i].s)) {
1028             break;
1029         }
1030         if(!hasNext) {
1031             errln("trie iterator next()=FALSE for item %d: %s", (int)i, data[i].s);
1032             break;
1033         }
1034         UnicodeString expectedString=UnicodeString(data[i].s, -1, US_INV).unescape();
1035         if(iter.getString()!=expectedString) {
1036             char buffer[1000];
1037             UnicodeString invString(prettify(iter.getString()));
1038             invString.extract(0, invString.length(), buffer, LENGTHOF(buffer), US_INV);
1039             errln("trie iterator next().getString()=%s but expected %s for item %d",
1040                   buffer, data[i].s, (int)i);
1041         }
1042         if(iter.getValue()!=data[i].value) {
1043             errln("trie iterator next().getValue()=%ld=0x%lx but expected %ld=0x%lx for item %d: %s",
1044                   (long)iter.getValue(), (long)iter.getValue(),
1045                   (long)data[i].value, (long)data[i].value,
1046                   (int)i, data[i].s);
1047         }
1048     }
1049     if(iter.hasNext()) {
1050         errln("trie iterator hasNext()=TRUE after all items");
1051     }
1052     UBool hasNext=iter.next(errorCode);
1053     errorCode.logIfFailureAndReset("trie iterator next() after all items");
1054     if(hasNext) {
1055         errln("trie iterator next()=TRUE after all items");
1056     }
1057 }