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