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, Google, International Business Machines Corporation and 7aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * others. All Rights Reserved. 8aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin ******************************************************************************* 9aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin */ 10aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinpackage android.icu.dev.test.util; 11aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 12aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport java.util.ArrayList; 13aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport java.util.HashMap; 14aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport java.util.Iterator; 15aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport java.util.List; 16aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport java.util.Map; 17aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport java.util.Map.Entry; 18aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 19aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport android.icu.impl.Utility; 20aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport android.icu.util.BytesTrie; 21aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport android.icu.util.BytesTrie.Result; 22aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport android.icu.util.BytesTrieBuilder; 23aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport android.icu.util.CharsTrie; 24aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport android.icu.util.CharsTrieBuilder; 25aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinimport android.icu.util.StringTrieBuilder.Option; 26aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 27aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin// would be nice to have a BytesTrieBuilder.add(aByte); 28aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin// question: can bytetrie store <"",x>? 29aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin// can you store the same string twice, eg add(bytes1, value), add(bytes1, value)? What happens? If an error, 30aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin// should happen on add, not on build. 31aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin// the BytesTrieBuilder.build should create a BytesTrie, not a raw array. For the latter, use buildArray or something. 32aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin// need class description; examples of usage; which method can/should be called after which others. 33aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 34aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffinpublic abstract class TrieMap<V> implements Iterable<Entry<CharSequence, V>> { 35aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 36aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public enum Style { 37aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin BYTES, CHARS 38aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 39aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 40aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private static final boolean DEBUG = true; 41aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 42aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin protected final V[] intToValue; 43aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin protected final int size; 44aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 45aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin protected TrieMap(V[] intToValue, int size) { 46aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin this.intToValue = intToValue; 47aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin this.size = size; 48aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 49aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 50aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public int keyByteSize() { 51aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return size; 52aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 53aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 54aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public static abstract class Builder<V> { 55aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin Option option; 56aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin protected List<V> intToValueTemp = new ArrayList<V>(); 57aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin protected Map<V, Integer> valueToIntegerTemp = new HashMap<V, Integer>(); 58aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 59aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin static public <K extends CharSequence, V> Builder<V> with(Style style, Map<K, V> keyValuePairs) { 60aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return with(style, Option.SMALL, keyValuePairs); 61aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 62aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 63aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin static public <K extends CharSequence, V> Builder<V> with(Style style, Option option, Map<K, V> keyValuePairs) { 64aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin Builder<V> result = style == Style.BYTES ? new BytesTrieMap.BytesBuilder<V>() 65aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin : new CharsTrieMap.CharsBuilder<V>(); 66aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin result.option = option; 67aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return result.addAll(keyValuePairs); 68aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 69aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 70aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin static public <K extends CharSequence, V> Builder<V> with(Style style, K key, V value) { 71aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return with(style, Option.SMALL, key, value); 72aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 73aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 74aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin static public <K extends CharSequence, V> Builder<V> with(Style style, Option option, K key, V value) { 75aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin Builder<V> result = style == Style.BYTES ? new BytesTrieMap.BytesBuilder<V>() 76aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin : new CharsTrieMap.CharsBuilder<V>(); 77aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin result.option = option; 78aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return result.add(key, value); 79aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 80aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 81aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public abstract Builder<V> add(CharSequence key, V value); 82aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 83aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public abstract <K extends CharSequence> Builder<V> addAll(Map<K, V> keyValuePairs); 84aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 85aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public abstract TrieMap<V> build(); 86aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 87aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 88aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin abstract public V get(CharSequence test); 89aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 90aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin /** 91aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * Warning: the entry contents are only valid until the next next() call!! 92aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin */ 93aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin abstract public Iterator<Entry<CharSequence, V>> iterator(); 94aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 95aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin abstract public Matcher<V> getMatcher(); 96aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 97aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public abstract static class Matcher<V> { 98aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin protected CharSequence text = ""; 99aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin protected int start = 0; 100aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin protected int current = 0; 101aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 102aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin abstract void set(CharSequence string, int i); 103aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 104aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin abstract boolean next(); 105aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 106aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin abstract V getValue(); 107aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 108aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin abstract int getStart(); 109aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 110aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin abstract int getEnd(); 111aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 112aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin abstract boolean nextStart(); 113aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 114aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 115aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private static class BytesTrieMap<V> extends TrieMap<V> { 116aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private final BytesTrie bytesTrie; 117aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private byte[] bytes = new byte[3]; 118aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 119aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private BytesTrieMap(BytesTrie bytesTrie, V[] intToValue, int size) { 120aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin super(intToValue, size); 121aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin this.bytesTrie = bytesTrie; 122aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 123aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 124aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public V get(CharSequence test) { 125aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int length = test.length(); 126aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin bytesTrie.reset(); 127aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (length == 0) { 128aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return bytesTrie.current().hasValue() ? intToValue[bytesTrie.getValue()] : null; 129aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 130aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin Result result = Result.NO_VALUE; 131aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin for (int i = 0; i < length; ++i) { 132aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (!result.hasNext()) { 133aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return null; 134aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 135aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin char c = test.charAt(i); 136aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int limit = ByteConverter.getBytes(c, bytes, 0); 137aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin result = limit == 1 ? bytesTrie.next(bytes[0]) : bytesTrie.next(bytes, 0, limit); 138aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 139aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return result.hasValue() ? intToValue[bytesTrie.getValue()] : null; 140aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 141aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // int length = test.length(); 142aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // if (length == 0) { 143aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // return null; 144aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // } 145aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // bytesTrie.reset(); 146aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // Result result = null; 147aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // byte[] bytes = new byte[3]; 148aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // for (int i = 0; i < length; ++i) { 149aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // char c = test.charAt(i); 150aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // int limit = ByteConverter.getBytes(c, bytes, 0); 151aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // for (int j = 0; j < limit; ++j) { 152aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // result = bytesTrie.next(bytes[j]&0xFF); 153aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // if (!result.matches()) { 154aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // return null; 155aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // } 156aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // } 157aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // } 158aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // return result.hasValue() ? intToValue[bytesTrie.getValue()] : null; 159aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 160aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 161aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public String toString() { 162aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return toString(bytesTrie, " : ", "\n"); 163aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 164aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 165aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin /** 166aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * Warning: the entry contents are only valid until the next next() call!! 167aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin */ 168aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public Iterator<Entry<CharSequence, V>> iterator() { 169aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // TODO Auto-generated method stub 170aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return new BytesIterator(); 171aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 172aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 173aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public TrieMap.Matcher<V> getMatcher() { 174aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return new BytesMatcher(); 175aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 176aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 177aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private class BytesIterator implements Iterator<Entry<CharSequence, V>> { 178aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin BytesTrie.Iterator iterator = bytesTrie.iterator(); 179aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin BytesEntry entry = new BytesEntry(); 180aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 181aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public boolean hasNext() { 182aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return iterator.hasNext(); 183aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 184aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 185aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public Entry<CharSequence, V> next() { 186aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin entry.bytesEntry = iterator.next(); 187aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return entry; 188aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 189aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 190aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public void remove() { 191aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin throw new UnsupportedOperationException(); 192aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 193aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 194aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 195aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private class BytesEntry implements Entry<CharSequence, V> { 196aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public BytesTrie.Entry bytesEntry; 197aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin StringBuilder buffer = new StringBuilder(); 198aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 199aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public CharSequence getKey() { 200aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin buffer.setLength(0); 201aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin ByteConverter.getChars(bytesEntry, buffer); 202aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return buffer; 203aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 204aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 205aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public V getValue() { 206aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return intToValue[bytesEntry.value]; 207aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 208aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 209aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public V setValue(V value) { 210aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin throw new UnsupportedOperationException(); 211aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 212aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 213aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 214aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public class BytesMatcher extends Matcher<V> { 215aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private byte[] bytes = new byte[3]; 216aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private V value = null; 217aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 218aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public void set(CharSequence text, int start) { 219aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin this.text = text; 220aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin this.start = start; 221aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin this.current = start; 222aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 223aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 224aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public int getStart() { 225aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return start; 226aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 227aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 228aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public int getEnd() { 229aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return current; 230aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 231aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 232aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin /** 233aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * Finds the next match. Returns false when there are no possible further matches from the current start 234aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * point. Once that happens, call nextStart(); Call getValue to get the current value. 235aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * 236aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * @return false when done. There may be a value, however. 237aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin */ 238aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public boolean next() { 239aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin while (current < text.length()) { 240aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin char c = text.charAt(current++); 241aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int limit = ByteConverter.getBytes(c, bytes, 0); 242aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin for (int j = 0; j < limit; ++j) { 243aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin Result result = bytesTrie.next(bytes[j]); 244aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (result.hasValue()) { 245aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (j < limit - 1) { 246aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin throw new IllegalArgumentException("Data corrupt"); 247aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 248aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin value = intToValue[bytesTrie.getValue()]; 249aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return result.hasNext(); 250aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } else if (!result.matches()) { 251aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin value = null; 252aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return false; 253aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 254aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 255aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 256aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin value = null; 257aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return false; 258aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 259aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 260aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public boolean nextStart() { 261aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (start >= text.length()) { 262aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return false; 263aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 264aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin ++start; 265aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin current = start; 266aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin bytesTrie.reset(); 267aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return true; 268aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 269aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 270aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public V getValue() { 271aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return value; 272aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 273aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 274aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 275aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 276aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public static class BytesBuilder<V> extends Builder<V> { 277aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin BytesTrieBuilder builder = new BytesTrieBuilder(); 278aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin byte[] bytes = new byte[200]; 279aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin List<String> debugBytes = DEBUG ? new ArrayList<String>() : null; 280aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 281aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public BytesBuilder<V> add(CharSequence key, V value) { 282aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // traverse the values, and get a mapping of a byte string to list of 283aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // integers, and a mapping from those integers to a set of values 284aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin Integer index; 285aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (option == Option.SMALL) { 286aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin index = valueToIntegerTemp.get(value); 287aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (index == null) { 288aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin index = intToValueTemp.size(); 289aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin intToValueTemp.add(value); 290aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin valueToIntegerTemp.put(value, index); 291aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 292aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } else { 293aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin index = intToValueTemp.size(); 294aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin intToValueTemp.add(value); 295aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 296aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // dumb implementation for now 297aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // the buffer size is at most 3 * number_of_chars 298aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (bytes.length < key.length() * 3) { 299aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin bytes = new byte[64 + key.length() * 3]; 300aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 301aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int limit = 0; 302aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin for (int i = 0; i < key.length(); ++i) { 303aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin char c = key.charAt(i); 304aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin limit = ByteConverter.getBytes(c, bytes, limit); 305aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 306aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin try { 307aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin builder.add(bytes, limit, index); 308aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return this; 309aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } catch (Exception e) { 310aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin ArrayList<String> list = new ArrayList<String>(); 311aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin for (int i = 0; i < limit; ++i) { 312aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin list.add(Utility.hex(bytes[i])); 313aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 314aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin throw new IllegalArgumentException("Failed to add " + value + ", " + key + "=" + list, e); 315aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 316aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 317aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 318aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public <K extends CharSequence> BytesBuilder<V> addAll(Map<K, V> keyValuePairs) { 319aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin for (Entry<K, V> entry : keyValuePairs.entrySet()) { 320aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin add(entry.getKey(), entry.getValue()); 321aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 322aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return this; 323aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 324aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 325aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public TrieMap<V> build() { 326aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int size = builder.buildByteBuffer(option).remaining(); 327aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin BytesTrie bytesTrie = builder.build(option); 328aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin @SuppressWarnings("unchecked") 329aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin V[] intToValueArray = intToValueTemp.toArray((V[]) (new Object[intToValueTemp.size()])); 330aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return new BytesTrieMap<V>(bytesTrie, intToValueArray, size); 331aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 332aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 333aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 334aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private static class CharsTrieMap<V> extends TrieMap<V> { 335aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private final CharsTrie charsTrie; 336aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 337aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private CharsTrieMap(CharsTrie charsTrie, V[] intToValue, int size) { 338aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin super(intToValue, size); 339aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin this.charsTrie = charsTrie; 340aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 341aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 342aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public V get(CharSequence test) { 343aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin Result result = charsTrie.reset().next(test, 0, test.length()); 344aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return result.hasValue() ? intToValue[charsTrie.getValue()] : null; 345aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 346aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 347aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public String toString() { 348aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return toString(charsTrie, " : ", "\n"); 349aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 350aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 351aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin /** 352aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * Warning: the entry contents are only valid until the next next() call!! 353aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin */ 354aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public Iterator<Entry<CharSequence, V>> iterator() { 355aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // TODO Auto-generated method stub 356aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return new CharsIterator(); 357aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 358aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 359aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public TrieMap.Matcher<V> getMatcher() { 360aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return new CharsMatcher(); 361aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 362aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 363aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private class CharsIterator implements Iterator<Entry<CharSequence, V>> { 364aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin CharsTrie.Iterator iterator = charsTrie.iterator(); 365aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin CharsEntry entry = new CharsEntry(); 366aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 367aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public boolean hasNext() { 368aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return iterator.hasNext(); 369aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 370aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 371aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public Entry<CharSequence, V> next() { 372aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin entry.charsEntry = iterator.next(); 373aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return entry; 374aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 375aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 376aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public void remove() { 377aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin throw new UnsupportedOperationException(); 378aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 379aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 380aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 381aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 382aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private class CharsEntry implements Entry<CharSequence, V> { 383aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public CharsTrie.Entry charsEntry; 384aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 385aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public CharSequence getKey() { 386aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return charsEntry.chars; 387aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 388aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 389aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public V getValue() { 390aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return intToValue[charsEntry.value]; 391aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 392aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 393aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public V setValue(V value) { 394aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin throw new UnsupportedOperationException(); 395aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 396aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 397aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 398aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public class CharsMatcher extends Matcher<V> { 399aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private V value = null; 400aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 401aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public void set(CharSequence text, int start) { 402aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin this.text = text; 403aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin this.start = start; 404aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin this.current = start; 405aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 406aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 407aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public int getStart() { 408aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return start; 409aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 410aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 411aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public int getEnd() { 412aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return current; 413aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 414aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 415aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin /** 416aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * Finds the next match. Returns false when there are no possible further matches from the current start 417aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * point. Once that happens, call nextStart(); Call getValue to get the current value. 418aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * 419aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * @return false when done. There may be a value, however. 420aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin */ 421aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public boolean next() { 422aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin while (current < text.length()) { 423aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin char c = text.charAt(current++); 424aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin Result result = charsTrie.next(c); 425aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (result.hasValue()) { 426aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin value = intToValue[charsTrie.getValue()]; 427aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return result.hasNext(); 428aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } else if (!result.matches()) { 429aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin value = null; 430aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return false; 431aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 432aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 433aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 434aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin value = null; 435aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return false; 436aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 437aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 438aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public boolean nextStart() { 439aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (start >= text.length()) { 440aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return false; 441aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 442aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin ++start; 443aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin current = start; 444aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin charsTrie.reset(); 445aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return true; 446aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 447aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 448aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public V getValue() { 449aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return value; 450aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 451aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 452aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 453aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 454aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public static class CharsBuilder<V> extends Builder<V> { 455aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin CharsTrieBuilder builder = new CharsTrieBuilder(); 456aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 457aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public CharsBuilder<V> add(CharSequence key, V value) { 458aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // traverse the values, and get a mapping of a byte string to list of 459aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // integers, and a mapping from those integers to a set of values 460aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin Integer index; 461aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (option == Option.SMALL) { 462aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin index = valueToIntegerTemp.get(value); 463aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (index == null) { 464aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin index = intToValueTemp.size(); 465aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin intToValueTemp.add(value); 466aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin valueToIntegerTemp.put(value, index); 467aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 468aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } else { 469aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin index = intToValueTemp.size(); 470aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin intToValueTemp.add(value); 471aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 472aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin try { 473aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin builder.add(key.toString(), index); 474aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return this; 475aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } catch (Exception e) { 476aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin throw new IllegalArgumentException("Failed to add " + value + ", " + key + "=" + Utility.hex(key), e); 477aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 478aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 479aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 480aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public <K extends CharSequence> CharsBuilder<V> addAll(Map<K, V> keyValuePairs) { 481aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin for (Entry<K, V> entry : keyValuePairs.entrySet()) { 482aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin add(entry.getKey(), entry.getValue()); 483aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 484aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return this; 485aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 486aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 487aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public TrieMap<V> build() { 488aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin CharSequence buildCharSequence = builder.buildCharSequence(option); 489aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int size = 2 * buildCharSequence.length(); 490aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin // CharsTrie charsTrie = builder.build(option); 491aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin CharsTrie charsTrie = new CharsTrie(buildCharSequence, 0); 492aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin @SuppressWarnings("unchecked") 493aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin V[] intToValueArray = intToValueTemp.toArray((V[]) (new Object[intToValueTemp.size()])); 494aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return new CharsTrieMap<V>(charsTrie, intToValueArray, size); 495aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 496aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 497aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 498aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin /** 499aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * Supports the following format for encoding chars (Unicode 16-bit code units). The format is slightly simpler and 500aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * more compact than UTF8, but also maintains ordering. It is not, however self-synchronizing, and is not intended 501aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * for general usage 502aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * 503aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * <pre> 504aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * 0000..007F - 0xxx xxxx 505aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * 0000..7EFF - 1yyy yyyy xxxx xxxx 506aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * 7F00..FFFF - 1111 1111 yyyy yyyy xxxx xxxx 507aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * </pre> 508aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin */ 509aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin static class ByteConverter { 510aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public static int getBytes(char source, byte[] bytes, int limit) { 511aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (source < 0x80) { 512aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin bytes[limit++] = (byte) source; 513aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } else if (source < 0x7F00) { 514aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin bytes[limit++] = (byte) (0x80 | (source >> 8)); 515aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin bytes[limit++] = (byte) source; 516aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } else { 517aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin bytes[limit++] = (byte) -1; 518aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin bytes[limit++] = (byte) (source >> 8); 519aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin bytes[limit++] = (byte) source; 520aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 521aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return limit; 522aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 523aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 524aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin /** 525aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * Transform the string into a sequence of bytes, appending them after start, and return the new limit. 526aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin */ 527aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public static int getBytes(CharSequence source, byte[] bytes, int limit) { 528aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin for (int i = 0; i < source.length(); ++i) { 529aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin limit = getBytes(source.charAt(i), bytes, limit); 530aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 531aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return limit; 532aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 533aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 534aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin /** 535aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin * Transform a sequence of bytes into a string, according to the format in getBytes. No error checking. 536aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin */ 537aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public static String getChars(byte[] bytes, int start, int limit) { 538aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin StringBuilder buffer = new StringBuilder(); 539aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin char[] output = new char[1]; 540aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin for (int i = start; i < limit;) { 541aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin i = getChar(bytes, i, output); 542aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin buffer.append(output[0]); 543aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 544aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return buffer.toString(); 545aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 546aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 547aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public static int getChar(byte[] bytes, int start, char[] output) { 548aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin byte b = bytes[start++]; 549aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (b >= 0) { 550aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin output[0] = (char) b; 551aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } else if (b != (byte) -1) { // 2 bytes 552aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int b1 = 0x7F & b; 553aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int b2 = 0xFF & bytes[start++]; 554aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin output[0] = (char) ((b1 << 8) | b2); 555aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } else { 556aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int b2 = bytes[start++]; 557aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int b3 = 0xFF & bytes[start++]; 558aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin output[0] = (char) ((b2 << 8) | b3); 559aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 560aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return start; 561aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 562aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 563aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin private static void getChars(BytesTrie.Entry entry, StringBuilder stringBuilder) { 564aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int len = entry.bytesLength(); 565aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin for (int i = 0; i < len;) { 566aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin byte b = entry.byteAt(i++); 567aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin if (b >= 0) { 568aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin stringBuilder.append((char) b); 569aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } else if (b != (byte) -1) { // 2 bytes 570aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int b1 = 0x7F & b; 571aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int b2 = 0xFF & entry.byteAt(i++); 572aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin stringBuilder.append((char) ((b1 << 8) | b2)); 573aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } else { 574aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int b2 = entry.byteAt(i++); 575aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int b3 = 0xFF & entry.byteAt(i++); 576aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin stringBuilder.append((char) ((b2 << 8) | b3)); 577aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 578aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 579aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 580aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 581aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 582aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public static String toString(BytesTrie bytesTrie2) { 583aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return toString(bytesTrie2, " : ", "\n"); 584aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 585aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 586aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public static String toString(BytesTrie bytesTrie2, String keyValueSeparator, String itemSeparator) { 587aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin StringBuilder buffer = new StringBuilder(); 588aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin BytesTrie.Iterator iterator = bytesTrie2.iterator(); 589aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin while (iterator.hasNext()) { 590aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin BytesTrie.Entry bytesEntry = iterator.next(); 591aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin int len = bytesEntry.bytesLength(); 592aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin byte[] bytes = new byte[len]; 593aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin bytesEntry.copyBytesTo(bytes, 0); 594aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin buffer.append(Utility.hex(bytes, 0, len, " ")) 595aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin .append(keyValueSeparator) 596aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin .append(bytesEntry.value) 597aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin .append(itemSeparator); 598aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 599aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return buffer.toString(); 600aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 601aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 602aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin public static String toString(CharsTrie bytesTrie2, String keyValueSeparator, String itemSeparator) { 603aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin StringBuilder buffer = new StringBuilder(); 604aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin CharsTrie.Iterator iterator = bytesTrie2.iterator(); 605aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin while (iterator.hasNext()) { 606aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin CharsTrie.Entry bytesEntry = iterator.next(); 607aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin buffer.append(Utility.hex(bytesEntry.chars)) 608aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin .append(keyValueSeparator) 609aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin .append(bytesEntry.value) 610aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin .append(itemSeparator); 611aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 612aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin return buffer.toString(); 613aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin } 614aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin 615aefe4d1f8f1773ead1a52f7a5d2c9e0009353600Paul Duffin} 616