12d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert// © 2016 and later: Unicode, Inc. and others. 22d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert// License & terms of use: http://www.unicode.org/copyright.html#License 37935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert/* 47935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ******************************************************************************* 5f8a0c400bbd62a2ea4ee9b77641f79cb443d2187Neil Fuller * Copyright (C) 2009-2015, International Business Machines Corporation and 67935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * others. All Rights Reserved. 77935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ******************************************************************************* 87935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 97935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertpackage com.ibm.icu.impl; 117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertimport java.io.DataOutputStream; 137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertimport java.io.IOException; 147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertimport java.io.InputStream; 157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertimport java.nio.ByteBuffer; 167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertimport java.nio.ByteOrder; 177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertimport java.util.Iterator; 187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertimport java.util.NoSuchElementException; 197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert/** 227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * This is the interface and common implementation of a Unicode Trie2. 237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * It is a kind of compressed table that maps from Unicode code points (0..0x10ffff) 247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * to 16- or 32-bit integer values. It works best when there are ranges of 257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * characters with the same value, which is generally the case with Unicode 267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * character properties. 277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * This is the second common version of a Unicode trie (hence the name Trie2). 292d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubertpublic abstract class Trie2 implements Iterable<Trie2.Range> { 327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Create a Trie2 from its serialized form. Inverse of utrie2_serialize(). 367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Reads from the current position and leaves the buffer after the end of the trie. 387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The serialized format is identical between ICU4C and ICU4J, so this function 407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * will work with serialized Trie2s from either. 417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The actual type of the returned Trie2 will be either Trie2_16 or Trie2_32, depending 437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * on the width of the data. 447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * To obtain the width of the Trie2, check the actual class type of the returned Trie2. 467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Or use the createFromSerialized() function of Trie2_16 or Trie2_32, which will 477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * return only Tries of their specific type/size. 487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The serialized Trie2 on the stream may be in either little or big endian byte order. 507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * This allows using serialized Tries from ICU4C without needing to consider the 517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * byte order of the system that created them. 527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param bytes a byte buffer to the serialized form of a UTrie2. 547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return An unserialized Trie2, ready for use. 557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IllegalArgumentException if the stream does not contain a serialized Trie2. 567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IOException if a read error occurs in the buffer. 577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public static Trie2 createFromSerialized(ByteBuffer bytes) throws IOException { 607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // From ICU4C utrie2_impl.h 617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // * Trie2 data structure in serialized form: 627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // * 637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // * UTrie2Header header; 647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // * uint16_t index[header.index2Length]; 657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // * uint16_t data[header.shiftedDataLength<<2]; -- or uint32_t data[...] 667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // * @internal 677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // */ 687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // typedef struct UTrie2Header { 697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // /** "Tri2" in big-endian US-ASCII (0x54726932) */ 707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // uint32_t signature; 717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // /** 737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // * options bit field: 747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // * 15.. 4 reserved (0) 757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // * 3.. 0 UTrie2ValueBits valueBits 767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // */ 777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // uint16_t options; 787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH */ 807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // uint16_t indexLength; 817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT */ 837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // uint16_t shiftedDataLength; 847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // /** Null index and data blocks, not shifted. */ 867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // uint16_t index2NullOffset, dataNullOffset; 877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // /** 897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // * First code point of the single-value range ending with U+10ffff, 907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // * rounded up and then shifted right by UTRIE2_SHIFT_1. 917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // */ 927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // uint16_t shiftedHighStart; 937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // } UTrie2Header; 947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ByteOrder outerByteOrder = bytes.order(); 967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert try { 977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert UTrie2Header header = new UTrie2Header(); 987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* check the signature */ 1007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert header.signature = bytes.getInt(); 1017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert switch (header.signature) { 1027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert case 0x54726932: 1037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // The buffer is already set to the trie data byte order. 1047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 1057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert case 0x32697254: 1067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Temporarily reverse the byte order. 1077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert boolean isBigEndian = outerByteOrder == ByteOrder.BIG_ENDIAN; 1087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert bytes.order(isBigEndian ? ByteOrder.LITTLE_ENDIAN : ByteOrder.BIG_ENDIAN); 1097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert header.signature = 0x54726932; 1107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 1117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert default: 1127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalArgumentException("Buffer does not contain a serialized UTrie2"); 1137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert header.options = bytes.getChar(); 1167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert header.indexLength = bytes.getChar(); 1177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert header.shiftedDataLength = bytes.getChar(); 1187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert header.index2NullOffset = bytes.getChar(); 1197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert header.dataNullOffset = bytes.getChar(); 1207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert header.shiftedHighStart = bytes.getChar(); 1217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Trie2 data width - 0: 16 bits 1237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 1: 32 bits 1247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if ((header.options & UTRIE2_OPTIONS_VALUE_BITS_MASK) > 1) { 1257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalArgumentException("UTrie2 serialized format error."); 1267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ValueWidth width; 1287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert Trie2 This; 1297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if ((header.options & UTRIE2_OPTIONS_VALUE_BITS_MASK) == 0) { 1307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert width = ValueWidth.BITS_16; 1317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This = new Trie2_16(); 1327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 1337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert width = ValueWidth.BITS_32; 1347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This = new Trie2_32(); 1357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.header = header; 1377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* get the length values and offsets */ 1397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.indexLength = header.indexLength; 1407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.dataLength = header.shiftedDataLength << UTRIE2_INDEX_SHIFT; 1417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.index2NullOffset = header.index2NullOffset; 1427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.dataNullOffset = header.dataNullOffset; 1437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.highStart = header.shiftedHighStart << UTRIE2_SHIFT_1; 1447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.highValueIndex = This.dataLength - UTRIE2_DATA_GRANULARITY; 1457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (width == ValueWidth.BITS_16) { 1467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.highValueIndex += This.indexLength; 1477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Allocate the Trie2 index array. If the data width is 16 bits, the array also 1507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // includes the space for the data. 1517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int indexArraySize = This.indexLength; 1537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (width == ValueWidth.BITS_16) { 1547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert indexArraySize += This.dataLength; 1557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* Read in the index */ 158f8a0c400bbd62a2ea4ee9b77641f79cb443d2187Neil Fuller This.index = ICUBinary.getChars(bytes, indexArraySize, 0); 1597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* Read in the data. 16 bit data goes in the same array as the index. 1617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 32 bit data goes in its own separate data array. 1627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 1637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (width == ValueWidth.BITS_16) { 1647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.data16 = This.indexLength; 1657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 166f8a0c400bbd62a2ea4ee9b77641f79cb443d2187Neil Fuller This.data32 = ICUBinary.getInts(bytes, This.dataLength, 0); 1677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert switch(width) { 1707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert case BITS_16: 1717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.data32 = null; 1727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.initialValue = This.index[This.dataNullOffset]; 1737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.errorValue = This.index[This.data16+UTRIE2_BAD_UTF8_DATA_OFFSET]; 1747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 1757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert case BITS_32: 1767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.data16=0; 1777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.initialValue = This.data32[This.dataNullOffset]; 1787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert This.errorValue = This.data32[UTRIE2_BAD_UTF8_DATA_OFFSET]; 1797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 1807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert default: 1817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalArgumentException("UTrie2 serialized format error."); 1827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return This; 1857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } finally { 1867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert bytes.order(outerByteOrder); 1877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 1917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Get the UTrie version from an InputStream containing the serialized form 1927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * of either a Trie (version 1) or a Trie2 (version 2). 1937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 1947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param is an InputStream containing the serialized form 1957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * of a UTrie, version 1 or 2. The stream must support mark() and reset(). 1967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The position of the input stream will be left unchanged. 1977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param littleEndianOk If FALSE, only big-endian (Java native) serialized forms are recognized. 1987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * If TRUE, little-endian serialized forms are recognized as well. 1997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return the Trie version of the serialized form, or 0 if it is not 2007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * recognized as a serialized UTrie 2017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws IOException on errors in reading from the input stream. 2027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 2037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public static int getVersion(InputStream is, boolean littleEndianOk) throws IOException { 2047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (! is.markSupported()) { 2057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalArgumentException("Input stream must support mark()."); 2067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert is.mark(4); 2087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert byte sig[] = new byte[4]; 2097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int read = is.read(sig); 2107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert is.reset(); 2112d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 2127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (read != sig.length) { 2137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 0; 2147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2152d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 2167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (sig[0]=='T' && sig[1]=='r' && sig[2]=='i' && sig[3]=='e') { 2177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 1; 2187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (sig[0]=='T' && sig[1]=='r' && sig[2]=='i' && sig[3]=='2') { 2207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 2; 2217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (littleEndianOk) { 2237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (sig[0]=='e' && sig[1]=='i' && sig[2]=='r' && sig[3]=='T') { 2247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 1; 2257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (sig[0]=='2' && sig[1]=='i' && sig[2]=='r' && sig[3]=='T') { 2277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 2; 2287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 0; 2317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 2347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Get the value for a code point as stored in the Trie2. 2357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 2367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param codePoint the code point 2377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return the value 2387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 2397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert abstract public int get(int codePoint); 2407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2412d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 2427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 2437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Get the trie value for a UTF-16 code unit. 2447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 2457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * A Trie2 stores two distinct values for input in the lead surrogate 2467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * range, one for lead surrogates, which is the value that will be 2477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * returned by this function, and a second value that is returned 2487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * by Trie2.get(). 2492d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 2507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * For code units outside of the lead surrogate range, this function 2517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * returns the same result as Trie2.get(). 2522d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 2537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * This function, together with the alternate value for lead surrogates, 2547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * makes possible very efficient processing of UTF-16 strings without 2557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * first converting surrogate pairs to their corresponding 32 bit code point 2567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * values. 2572d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 2587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * At build-time, enumerate the contents of the Trie2 to see if there 2597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * is non-trivial (non-initialValue) data for any of the supplementary 2607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * code points associated with a lead surrogate. 2617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * If so, then set a special (application-specific) value for the 2627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * lead surrogate code _unit_, with Trie2Writable.setForLeadSurrogateCodeUnit(). 2637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 2647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * At runtime, use Trie2.getFromU16SingleLead(). If there is non-trivial 2657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * data and the code unit is a lead surrogate, then check if a trail surrogate 2662d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * follows. If so, assemble the supplementary code point and look up its value 2677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * with Trie2.get(); otherwise reset the lead 2687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * surrogate's value or do a code point lookup for it. 2697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 2707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * If there is only trivial data for lead and trail surrogates, then processing 2717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * can often skip them. For example, in normalization or case mapping 2727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * all characters that do not have any mappings are simply copied as is. 2732d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 2747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param c the code point or lead surrogate value. 2757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return the value 2767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 2777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert abstract public int getFromU16SingleLead(char c); 2782d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 2797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 2807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 2817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Equals function. Two Tries are equal if their contents are equal. 2822d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * The type need not be the same, so a Trie2Writable will be equal to 2837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * (read-only) Trie2_16 or Trie2_32 so long as they are storing the same values. 2842d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 2857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 2862d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 2877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public final boolean equals(Object other) { 2887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if(!(other instanceof Trie2)) { 2897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 2907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert Trie2 OtherTrie = (Trie2)other; 2927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert Range rangeFromOther; 2932d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 2947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert Iterator<Trie2.Range> otherIter = OtherTrie.iterator(); 2957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (Trie2.Range rangeFromThis: this) { 2967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (otherIter.hasNext() == false) { 2977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 2987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 2997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert rangeFromOther = otherIter.next(); 3007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (!rangeFromThis.equals(rangeFromOther)) { 3017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 3027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (otherIter.hasNext()) { 3057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 3067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3072d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (errorValue != OtherTrie.errorValue || 3097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert initialValue != OtherTrie.initialValue) { 3107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 3117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3122d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return true; 3147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3152d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3162d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3172d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 3187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int hashCode() { 3197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (fHash == 0) { 3207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int hash = initHash(); 3217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (Range r: this) { 3227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert hash = hashInt(hash, r.hashCode()); 3237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (hash == 0) { 3257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert hash = 1; 3267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert fHash = hash; 3287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return fHash; 3307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3312d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 3337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * When iterating over the contents of a Trie2, Elements of this type are produced. 3342d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * The iterator will return one item for each contiguous range of codepoints having the same value. 3352d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 3367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * When iterating, the same Trie2EnumRange object will be reused and returned for each range. 3377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * If you need to retain complete iteration results, clone each returned Trie2EnumRange, 3387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * or save the range in some other way, before advancing to the next iteration step. 3397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 3407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public static class Range { 3417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int startCodePoint; 3427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int endCodePoint; // Inclusive. 3437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int value; 3447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public boolean leadSurrogate; 3452d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3462d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 3477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public boolean equals(Object other) { 3487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (other == null || !(other.getClass().equals(getClass()))) { 3497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return false; 3507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert Range tother = (Range)other; 3527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return this.startCodePoint == tother.startCodePoint && 3537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert this.endCodePoint == tother.endCodePoint && 3542d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert this.value == tother.value && 3557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert this.leadSurrogate == tother.leadSurrogate; 3567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3572d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3582d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3592d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 3607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int hashCode() { 3617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int h = initHash(); 3627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = hashUChar32(h, startCodePoint); 3637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = hashUChar32(h, endCodePoint); 3647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = hashInt(h, value); 3657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = hashByte(h, leadSurrogate? 1: 0); 3667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return h; 3677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3692d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3702d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 3727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Create an iterator over the value ranges in this Trie2. 3737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Values from the Trie2 are not remapped or filtered, but are returned as they 3747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * are stored in the Trie2. 3752d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 3767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return an Iterator 3777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 3782d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 3797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public Iterator<Range> iterator() { 3807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return iterator(defaultValueMapper); 3817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3822d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static ValueMapper defaultValueMapper = new ValueMapper() { 3842d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 3852d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert public int map(int in) { 3867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return in; 3877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 3887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert }; 3892d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 3907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 3917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Create an iterator over the value ranges from this Trie2. 3927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Values from the Trie2 are passed through a caller-supplied remapping function, 3937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * and it is the remapped values that determine the ranges that 3947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * will be produced by the iterator. 3952d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 3962d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 3977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param mapper provides a function to remap values obtained from the Trie2. 3987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return an Iterator 3997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 4007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public Iterator<Range> iterator(ValueMapper mapper) { 4017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return new Trie2Iterator(mapper); 4027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4042d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 4057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 4067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Create an iterator over the Trie2 values for the 1024=0x400 code points 4077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * corresponding to a given lead surrogate. 4087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * For example, for the lead surrogate U+D87E it will enumerate the values 4097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * for [U+2F800..U+2FC00[. 4107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Used by data builder code that sets special lead surrogate code unit values 4117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * for optimized UTF-16 string processing. 4127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 4137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Do not modify the Trie2 during the iteration. 4147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 4157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Except for the limited code point range, this functions just like Trie2.iterator(). 4167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 4177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 4187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public Iterator<Range> iteratorForLeadSurrogate(char lead, ValueMapper mapper) { 4197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return new Trie2Iterator(lead, mapper); 4207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 4237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Create an iterator over the Trie2 values for the 1024=0x400 code points 4247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * corresponding to a given lead surrogate. 4257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * For example, for the lead surrogate U+D87E it will enumerate the values 4267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * for [U+2F800..U+2FC00[. 4277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Used by data builder code that sets special lead surrogate code unit values 4287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * for optimized UTF-16 string processing. 4297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 4307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Do not modify the Trie2 during the iteration. 4317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 4327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Except for the limited code point range, this functions just like Trie2.iterator(). 4337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 4347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 4357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public Iterator<Range> iteratorForLeadSurrogate(char lead) { 4367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return new Trie2Iterator(lead, defaultValueMapper); 4377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 4407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * When iterating over the contents of a Trie2, an instance of TrieValueMapper may 4417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * be used to remap the values from the Trie2. The remapped values will be used 4427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * both in determining the ranges of codepoints and as the value to be returned 4437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * for each range. 4442d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 4457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Example of use, with an anonymous subclass of TrieValueMapper: 4462d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 4472d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 4487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * ValueMapper m = new ValueMapper() { 4497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * int map(int in) {return in & 0x1f;}; 4507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * } 4517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * for (Iterator<Trie2EnumRange> iter = trie.iterator(m); i.hasNext(); ) { 4527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Trie2EnumRange r = i.next(); 4537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * ... // Do something with the range r. 4547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * } 4552d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 4567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 4577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public interface ValueMapper { 4587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int map(int originalVal); 4597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4602d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 4617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 4627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 4637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Serialize a trie2 Header and Index onto an OutputStream. This is 4647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * common code used for both the Trie2_16 and Trie2_32 serialize functions. 4657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param dos the stream to which the serialized Trie2 data will be written. 4667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return the number of bytes written. 4677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 4682d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert protected int serializeHeader(DataOutputStream dos) throws IOException { 4697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Write the header. It is already set and ready to use, having been 4707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // created when the Trie2 was unserialized or when it was frozen. 4717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int bytesWritten = 0; 4722d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 4732d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert dos.writeInt(header.signature); 4747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert dos.writeShort(header.options); 4757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert dos.writeShort(header.indexLength); 4767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert dos.writeShort(header.shiftedDataLength); 4777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert dos.writeShort(header.index2NullOffset); 4787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert dos.writeShort(header.dataNullOffset); 4797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert dos.writeShort(header.shiftedHighStart); 4807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert bytesWritten += 16; 4812d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 4827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Write the index 4837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int i; 4847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (i=0; i< header.indexLength; i++) { 4857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert dos.writeChar(index[i]); 4867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4872d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert bytesWritten += header.indexLength; 4882d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert return bytesWritten; 4897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 4902d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 4912d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 4927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 4937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Struct-like class for holding the results returned by a UTrie2 CharSequence iterator. 4947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The iteration walks over a CharSequence, and for each Unicode code point therein 4957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * returns the character and its associated Trie2 value. 4967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 4972d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert public static class CharSequenceValues { 4987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** string index of the current code point. */ 4992d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert public int index; 5007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** The code point at index. */ 5012d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert public int codePoint; 5027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** The Trie2 value for the current code point */ 5032d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert public int value; 5047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5052d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 5087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Create an iterator that will produce the values from the Trie2 for 5097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * the sequence of code points in an input text. 5102d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 5117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param text A text string to be iterated over. 5127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param index The starting iteration position within the input text. 5137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return the CharSequenceIterator 5147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 5157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public CharSequenceIterator charSequenceIterator(CharSequence text, int index) { 5167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return new CharSequenceIterator(text, index); 5177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5182d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // TODO: Survey usage of the equivalent of CharSequenceIterator in ICU4C 5207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // and if there is none, remove it from here. 5217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Don't waste time testing and maintaining unused code. 5222d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 5247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * An iterator that operates over an input CharSequence, and for each Unicode code point 5257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * in the input returns the associated value from the Trie2. 5262d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 5277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The iterator can move forwards or backwards, and can be reset to an arbitrary index. 5282d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 5297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Note that Trie2_16 and Trie2_32 subclass Trie2.CharSequenceIterator. This is done 5307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * only for performance reasons. It does require that any changes made here be propagated 5317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * into the corresponding code in the subclasses. 5327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 5337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public class CharSequenceIterator implements Iterator<CharSequenceValues> { 5347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 5357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Internal constructor. 5367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 5372d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert CharSequenceIterator(CharSequence t, int index) { 5387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert text = t; 5397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert textLength = text.length(); 5407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert set(index); 5417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5422d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private CharSequence text; 5447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int textLength; 5457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int index; 5467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private Trie2.CharSequenceValues fResults = new Trie2.CharSequenceValues(); 5472d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5482d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void set(int i) { 5507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (i < 0 || i > textLength) { 5517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IndexOutOfBoundsException(); 5527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index = i; 5547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5552d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5562d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5572d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 5587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public final boolean hasNext() { 5597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return index<textLength; 5607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5612d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5622d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public final boolean hasPrevious() { 5647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return index>0; 5657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5672d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5682d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 5697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public Trie2.CharSequenceValues next() { 5707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int c = Character.codePointAt(text, index); 5717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int val = get(c); 5727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert fResults.index = index; 5747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert fResults.codePoint = c; 5757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert fResults.value = val; 5767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index++; 5777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (c >= 0x10000) { 5787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index++; 5792d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert } 5807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return fResults; 5817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 5832d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public Trie2.CharSequenceValues previous() { 5857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int c = Character.codePointBefore(text, index); 5867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int val = get(c); 5877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index--; 5887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (c >= 0x10000) { 5897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert index--; 5907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert fResults.index = index; 5927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert fResults.codePoint = c; 5937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert fResults.value = val; 5947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return fResults; 5957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 5962d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 5972d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert /** 5987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Iterator.remove() is not supported by Trie2.CharSequenceIterator. 5997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @throws UnsupportedOperationException Always thrown because this operation is not supported 6007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @see java.util.Iterator#remove() 6017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 6022d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 6037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void remove() { 6042d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert throw new UnsupportedOperationException("Trie2.CharSequenceIterator does not support remove()."); 6057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 6067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 6072d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6082d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert //-------------------------------------------------------------------------------- 6107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 6117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Below this point are internal implementation items. No further public API. 6127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 6137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert //-------------------------------------------------------------------------------- 6142d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6152d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 6177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Selectors for the width of a UTrie2 data value. 6182d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert */ 6197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert enum ValueWidth { 6207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert BITS_16, 6217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert BITS_32 6227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 6232d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 6257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Trie2 data structure in serialized form: 6267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 6277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * UTrie2Header header; 6287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * uint16_t index[header.index2Length]; 6297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * uint16_t data[header.shiftedDataLength<<2]; -- or uint32_t data[...] 6302d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 6317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * For Java, this is read from the stream into an instance of UTrie2Header. 6327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * (The C version just places a struct over the raw serialized data.) 6332d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 6347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @internal 6357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 6367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static class UTrie2Header { 6377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** "Tri2" in big-endian US-ASCII (0x54726932) */ 6387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int signature; 6392d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 6417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * options bit field (uint16_t): 6427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 15.. 4 reserved (0) 6437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 3.. 0 UTrie2ValueBits valueBits 6447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 6457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int options; 6467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 6477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH (uint16_t) */ 6487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int indexLength; 6492d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT (uint16_t) */ 6517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int shiftedDataLength; 6527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 6537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** Null index and data blocks, not shifted. (uint16_t) */ 6547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int index2NullOffset, dataNullOffset; 6557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 6567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 6577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * First code point of the single-value range ending with U+10ffff, 6587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * rounded up and then shifted right by UTRIE2_SHIFT_1. (uint16_t) 6597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 6607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int shiftedHighStart; 6617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 6622d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 6647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Data members of UTrie2. 6657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 6667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert UTrie2Header header; 6677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert char index[]; // Index array. Includes data for 16 bit Tries. 6687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int data16; // Offset to data portion of the index array, if 16 bit data. 6697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // zero if 32 bit data. 6702d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert int data32[]; // NULL if 16b data is used via index 6717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 6727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int indexLength; 6737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int dataLength; 6747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int index2NullOffset; // 0xffff if there is no dedicated index-2 null block 6757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int initialValue; 6767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 6777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** Value returned for out-of-range code points and illegal UTF-8. */ 6787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int errorValue; 6797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 6807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* Start of the last range which ends at U+10ffff, and its value. */ 6817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int highStart; 6827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int highValueIndex; 6832d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int dataNullOffset; 6852d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int fHash; // Zero if not yet computed. 6877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Shared by Trie2Writable, Trie2_16, Trie2_32. 6887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Thread safety: if two racing threads compute 6897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // the same hash on a frozen Trie2, no damage is done. 6907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 6912d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 6937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Trie2 constants, defining shift widths, index array lengths, etc. 6947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 6957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * These are needed for the runtime macros but users can treat these as 6967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * implementation details and skip to the actual public API further below. 6977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 6982d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 6997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_OPTIONS_VALUE_BITS_MASK=0x000f; 7002d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7012d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** Shift size for getting the index-1 table offset. */ 7037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_SHIFT_1=6+5; 7047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 7057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** Shift size for getting the index-2 table offset. */ 7067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_SHIFT_2=5; 7077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 7087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 7097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Difference between the two shift sizes, 7107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * for getting an index-1 offset from an index-2 offset. 6=11-5 7117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 7127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_SHIFT_1_2=UTRIE2_SHIFT_1-UTRIE2_SHIFT_2; 7137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 7147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 7157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Number of index-1 entries for the BMP. 32=0x20 7167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * This part of the index-1 table is omitted from the serialized form. 7177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 7187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_OMITTED_BMP_INDEX_1_LENGTH=0x10000>>UTRIE2_SHIFT_1; 7197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 7207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** Number of code points per index-1 table entry. 2048=0x800 */ 7217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_CP_PER_INDEX_1_ENTRY=1<<UTRIE2_SHIFT_1; 7222d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** Number of entries in an index-2 block. 64=0x40 */ 7247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_INDEX_2_BLOCK_LENGTH=1<<UTRIE2_SHIFT_1_2; 7252d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** Mask for getting the lower bits for the in-index-2-block offset. */ 7277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_INDEX_2_MASK=UTRIE2_INDEX_2_BLOCK_LENGTH-1; 7282d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** Number of entries in a data block. 32=0x20 */ 7307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_DATA_BLOCK_LENGTH=1<<UTRIE2_SHIFT_2; 7312d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** Mask for getting the lower bits for the in-data-block offset. */ 7337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_DATA_MASK=UTRIE2_DATA_BLOCK_LENGTH-1; 7342d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 7367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Shift size for shifting left the index array values. 7377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Increases possible data size with 16-bit index values at the cost 7387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * of compactability. 7397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * This requires data blocks to be aligned by UTRIE2_DATA_GRANULARITY. 7407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 7417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_INDEX_SHIFT=2; 7422d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** The alignment size of a data block. Also the granularity for compaction. */ 7447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_DATA_GRANULARITY=1<<UTRIE2_INDEX_SHIFT; 7452d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* Fixed layout of the first part of the index array. ------------------- */ 7472d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 7497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The BMP part of the index-2 table is fixed and linear and starts at offset 0. 7507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Length=2048=0x800=0x10000>>UTRIE2_SHIFT_2. 7517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 7527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_INDEX_2_OFFSET=0; 7532d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 7557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The part of the index-2 table for U+D800..U+DBFF stores values for 7567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * lead surrogate code _units_ not code _points_. 7577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Values for lead surrogate code _points_ are indexed with this portion of the table. 7587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Length=32=0x20=0x400>>UTRIE2_SHIFT_2. (There are 1024=0x400 lead surrogates.) 7597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 7607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_LSCP_INDEX_2_OFFSET=0x10000>>UTRIE2_SHIFT_2; 7617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_LSCP_INDEX_2_LENGTH=0x400>>UTRIE2_SHIFT_2; 7622d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** Count the lengths of both BMP pieces. 2080=0x820 */ 7647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_INDEX_2_BMP_LENGTH=UTRIE2_LSCP_INDEX_2_OFFSET+UTRIE2_LSCP_INDEX_2_LENGTH; 7652d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 7677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The 2-byte UTF-8 version of the index-2 table follows at offset 2080=0x820. 7687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Length 32=0x20 for lead bytes C0..DF, regardless of UTRIE2_SHIFT_2. 7697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 7707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_UTF8_2B_INDEX_2_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH; 7717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_UTF8_2B_INDEX_2_LENGTH=0x800>>6; /* U+0800 is the first code point after 2-byte UTF-8 */ 7722d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 7747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The index-1 table, only used for supplementary code points, at offset 2112=0x840. 7757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Variable length, for code points up to highStart, where the last single-value range starts. 7767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Maximum length 512=0x200=0x100000>>UTRIE2_SHIFT_1. 7777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * (For 0x100000 supplementary code points U+10000..U+10ffff.) 7787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 7797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The part of the index-2 table for supplementary code points starts 7807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * after this index-1 table. 7817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * 7827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Both the index-1 table and the following part of the index-2 table 7837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * are omitted completely if there is only BMP data. 7847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 7857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_INDEX_1_OFFSET=UTRIE2_UTF8_2B_INDEX_2_OFFSET+UTRIE2_UTF8_2B_INDEX_2_LENGTH; 7867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_MAX_INDEX_1_LENGTH=0x100000>>UTRIE2_SHIFT_1; 7872d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 7897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Fixed layout of the first part of the data array. ----------------------- 7907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Starts with 4 blocks (128=0x80 entries) for ASCII. 7917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 7922d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 7937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 7947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The illegal-UTF-8 data block follows the ASCII block, at offset 128=0x80. 7957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Used with linear access for single bytes 0..0xbf for simple error handling. 7967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Length 64=0x40, not UTRIE2_DATA_BLOCK_LENGTH. 7977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 7987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_BAD_UTF8_DATA_OFFSET=0x80; 7992d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 8007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** The start of non-linear-ASCII data blocks, at offset 192=0xc0. */ 8017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UTRIE2_DATA_START_OFFSET=0xc0; 8022d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 8037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* Building a Trie2 ---------------------------------------------------------- */ 8047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 8057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 8067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * These definitions are mostly needed by utrie2_builder.c, but also by 8077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * utrie2_get32() and utrie2_enum(). 8087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 8097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 8107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /* 8117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * At build time, leave a gap in the index-2 table, 8127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * at least as long as the maximum lengths of the 2-byte UTF-8 index-2 table 8137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * and the supplementary index-1 table. 8147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Round up to UTRIE2_INDEX_2_BLOCK_LENGTH for proper compacting. 8157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 8167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UNEWTRIE2_INDEX_GAP_OFFSET = UTRIE2_INDEX_2_BMP_LENGTH; 8177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UNEWTRIE2_INDEX_GAP_LENGTH = 8187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ((UTRIE2_UTF8_2B_INDEX_2_LENGTH + UTRIE2_MAX_INDEX_1_LENGTH) + UTRIE2_INDEX_2_MASK) & 8197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert ~UTRIE2_INDEX_2_MASK; 8207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 8217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 8227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Maximum length of the build-time index-2 array. 8237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Maximum number of Unicode code points (0x110000) shifted right by UTRIE2_SHIFT_2, 8247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * plus the part of the index-2 table for lead surrogate code points, 8257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * plus the build-time index gap, 8267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * plus the null index-2 block. 8277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 8287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UNEWTRIE2_MAX_INDEX_2_LENGTH= 8297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert (0x110000>>UTRIE2_SHIFT_2)+ 8307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert UTRIE2_LSCP_INDEX_2_LENGTH+ 8317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert UNEWTRIE2_INDEX_GAP_LENGTH+ 8327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert UTRIE2_INDEX_2_BLOCK_LENGTH; 8337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 8347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UNEWTRIE2_INDEX_1_LENGTH = 0x110000>>UTRIE2_SHIFT_1; 8357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 8367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 8377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Maximum length of the build-time data array. 8387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * One entry per 0x110000 code points, plus the illegal-UTF-8 block and the null block, 8397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * plus values for the 0x400 surrogate code units. 8407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 8417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert static final int UNEWTRIE2_MAX_DATA_LENGTH = (0x110000+0x40+0x40+0x400); 8427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 8432d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 8442d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 8452d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert /** 8467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Implementation class for an iterator over a Trie2. 8472d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 8487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Iteration over a Trie2 first returns all of the ranges that are indexed by code points, 8497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * then returns the special alternate values for the lead surrogates 8502d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 8517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @internal 8527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 8537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert class Trie2Iterator implements Iterator<Range> { 8547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // The normal constructor that configures the iterator to cover the complete 8557935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // contents of the Trie2 8567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert Trie2Iterator(ValueMapper vm) { 8577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert mapper = vm; 8587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert nextStart = 0; 8597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert limitCP = 0x110000; 8607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert doLeadSurrogates = true; 8617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 8622d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 8637935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // An alternate constructor that configures the iterator to cover only the 8647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // code points corresponding to a particular Lead Surrogate value. 8657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert Trie2Iterator(char leadSurrogate, ValueMapper vm) { 8667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (leadSurrogate < 0xd800 || leadSurrogate > 0xdbff) { 8677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new IllegalArgumentException("Bad lead surrogate value."); 8687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 8697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert mapper = vm; 8707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert nextStart = (leadSurrogate - 0xd7c0) << 10; 8717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert limitCP = nextStart + 0x400; 8727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert doLeadSurrogates = false; // Do not iterate over lead the special lead surrogate 8737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // values after completing iteration over code points. 8747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 8752d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 8767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 8777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * The main next() function for Trie2 iterators 8782d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 8797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 8802d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 8817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public Range next() { 8827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (!hasNext()) { 8837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new NoSuchElementException(); 8847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 8857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (nextStart >= limitCP) { 8867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Switch over from iterating normal code point values to 8877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // doing the alternate lead-surrogate values. 8887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert doingCodePoints = false; 8897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert nextStart = 0xd800; 8907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 8917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int endOfRange = 0; 8927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int val = 0; 8937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int mappedVal = 0; 8942d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 8957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (doingCodePoints) { 8967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Iteration over code point values. 8977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert val = get(nextStart); 8987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert mappedVal = mapper.map(val); 8997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert endOfRange = rangeEnd(nextStart, limitCP, val); 9007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Loop once for each range in the Trie2 with the same raw (unmapped) value. 9017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Loop continues so long as the mapped values are the same. 9027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (;;) { 9037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (endOfRange >= limitCP-1) { 9047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 9057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert val = get(endOfRange+1); 9077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (mapper.map(val) != mappedVal) { 9087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 9097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert endOfRange = rangeEnd(endOfRange+1, limitCP, val); 9117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } else { 9137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Iteration over the alternate lead surrogate values. 9142d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert val = getFromU16SingleLead((char)nextStart); 9157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert mappedVal = mapper.map(val); 9167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert endOfRange = rangeEndLS((char)nextStart); 9177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Loop once for each range in the Trie2 with the same raw (unmapped) value. 9187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Loop continues so long as the mapped values are the same. 9197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (;;) { 9207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (endOfRange >= 0xdbff) { 9217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 9227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert val = getFromU16SingleLead((char)(endOfRange+1)); 9247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (mapper.map(val) != mappedVal) { 9257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 9267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert endOfRange = rangeEndLS((char)(endOfRange+1)); 9287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert returnValue.startCodePoint = nextStart; 9317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert returnValue.endCodePoint = endOfRange; 9327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert returnValue.value = mappedVal; 9337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert returnValue.leadSurrogate = !doingCodePoints; 9342d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert nextStart = endOfRange+1; 9357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return returnValue; 9367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9372d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 9387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 9392d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 9407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 9412d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 9427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public boolean hasNext() { 9437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return doingCodePoints && (doLeadSurrogates || nextStart < limitCP) || nextStart < 0xdc00; 9447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9452d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 9462d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert @Override 9477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void remove() { 9487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert throw new UnsupportedOperationException(); 9497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9502d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 9512d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 9527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 9537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Find the last lead surrogate in a contiguous range with the 9547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * same Trie2 value as the input character. 9552d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 9567935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Use the alternate Lead Surrogate values from the Trie2, 9577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * not the code-point values. 9582d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 9597935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Note: Trie2_16 and Trie2_32 override this implementation with optimized versions, 9607935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * meaning that the implementation here is only being used with 9617935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Trie2Writable. The code here is logically correct with any type 9627935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * of Trie2, however. 9632d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 9647935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param c The character to begin with. 9657935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return The last contiguous character with the same value. 9667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 9677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int rangeEndLS(char startingLS) { 9687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (startingLS >= 0xdbff) { 9697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 0xdbff; 9707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9712d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 9727935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int c; 9737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int val = getFromU16SingleLead(startingLS); 9747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (c = startingLS+1; c <= 0x0dbff; c++) { 9757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (getFromU16SingleLead((char)c) != val) { 9767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 9777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return c-1; 9807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 9812d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 9827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 9837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Iteration State Variables 9847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 9857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private ValueMapper mapper; 9867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private Range returnValue = new Range(); 9877935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // The starting code point for the next range to be returned. 9887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int nextStart; 9897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // The upper limit for the last normal range to be returned. Normally 0x110000, but 9907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // may be lower when iterating over the code points for a single lead surrogate. 9917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int limitCP; 9922d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 9937935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // True while iterating over the the Trie2 values for code points. 9947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // False while iterating over the alternate values for lead surrogates. 9957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private boolean doingCodePoints = true; 9962d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 9977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // True if the iterator should iterate the special values for lead surrogates in 9987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // addition to the normal values for code points. 9997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private boolean doLeadSurrogates = true; 10007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 10012d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 10027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 10037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * Find the last character in a contiguous range of characters with the 10047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * same Trie2 value as the input character. 10052d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 10067935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param c The character to begin with. 10077935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @return The last contiguous character with the same value. 10087935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 10097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int rangeEnd(int start, int limitp, int val) { 10107935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int c; 10117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int limit = Math.min(highStart, limitp); 10122d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 10137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (c = start+1; c < limit; c++) { 10147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (get(c) != val) { 10157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert break; 10167935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 10177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 10187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (c >= highStart) { 10197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert c = limitp; 10207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 10217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return c - 1; 10227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 10232d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 10242d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 10257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 10267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // Hashing implementation functions. FNV hash. Respected public domain algorithm. 10277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // 10287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static int initHash() { 10297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return 0x811c9DC5; // unsigned 2166136261 10307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 10312d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 10327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static int hashByte(int h, int b) { 10337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = h * 16777619; 10347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = h ^ b; 10357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return h; 10367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 10372d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 10387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static int hashUChar32(int h, int c) { 10397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = Trie2.hashByte(h, c & 255); 10407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = Trie2.hashByte(h, (c>>8) & 255); 10417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = Trie2.hashByte(h, c>>16); 10427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return h; 10437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 10442d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert 10457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private static int hashInt(int h, int i) { 10467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = Trie2.hashByte(h, i & 255); 10477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = Trie2.hashByte(h, (i>>8) & 255); 10487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = Trie2.hashByte(h, (i>>16) & 255); 10497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert h = Trie2.hashByte(h, (i>>24) & 255); 10507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return h; 10517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 10527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 10537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert} 1054