2 *******************************************************************************
3 * Copyright (C) 2009-2011, International Business Machines Corporation and
4 * others. All Rights Reserved.
5 *******************************************************************************
7 package com.ibm.icu.impl;
9 import java.io.DataInputStream;
10 import java.io.DataOutputStream;
11 import java.io.IOException;
12 import java.io.InputStream;
13 import java.util.Iterator;
14 import java.util.NoSuchElementException;
18 * This is the interface and common implementation of a Unicode Trie2.
19 * It is a kind of compressed table that maps from Unicode code points (0..0x10ffff)
20 * to 16- or 32-bit integer values. It works best when there are ranges of
21 * characters with the same value, which is generally the case with Unicode
22 * character properties.
24 * This is the second common version of a Unicode trie (hence the name Trie2).
27 public abstract class Trie2 implements Iterable<Trie2.Range> {
31 * Create a Trie2 from its serialized form. Inverse of utrie2_serialize().
32 * The serialized format is identical between ICU4C and ICU4J, so this function
33 * will work with serialized Trie2s from either.
35 * The actual type of the returned Trie2 will be either Trie2_16 or Trie2_32, depending
36 * on the width of the data.
38 * To obtain the width of the Trie2, check the actual class type of the returned Trie2.
39 * Or use the createFromSerialized() function of Trie2_16 or Trie2_32, which will
40 * return only Tries of their specific type/size.
42 * The serialized Trie2 on the stream may be in either little or big endian byte order.
43 * This allows using serialized Tries from ICU4C without needing to consider the
44 * byte order of the system that created them.
46 * @param is an input stream to the serialized form of a UTrie2.
47 * @return An unserialized Trie2, ready for use.
48 * @throws IllegalArgumentException if the stream does not contain a serialized Trie2.
49 * @throws IOException if a read error occurs on the InputStream.
52 public static Trie2 createFromSerialized(InputStream is) throws IOException {
53 // From ICU4C utrie2_impl.h
54 // * Trie2 data structure in serialized form:
56 // * UTrie2Header header;
57 // * uint16_t index[header.index2Length];
58 // * uint16_t data[header.shiftedDataLength<<2]; -- or uint32_t data[...]
61 // typedef struct UTrie2Header {
62 // /** "Tri2" in big-endian US-ASCII (0x54726932) */
63 // uint32_t signature;
66 // * options bit field:
67 // * 15.. 4 reserved (0)
68 // * 3.. 0 UTrie2ValueBits valueBits
72 // /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH */
73 // uint16_t indexLength;
75 // /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT */
76 // uint16_t shiftedDataLength;
78 // /** Null index and data blocks, not shifted. */
79 // uint16_t index2NullOffset, dataNullOffset;
82 // * First code point of the single-value range ending with U+10ffff,
83 // * rounded up and then shifted right by UTRIE2_SHIFT_1.
85 // uint16_t shiftedHighStart;
88 DataInputStream dis = new DataInputStream(is);
89 boolean needByteSwap = false;
91 UTrie2Header header = new UTrie2Header();
93 /* check the signature */
94 header.signature = dis.readInt();
95 switch (header.signature) {
101 header.signature = Integer.reverseBytes(header.signature);
104 throw new IllegalArgumentException("Stream does not contain a serialized UTrie2");
107 header.options = swapShort(needByteSwap, dis.readUnsignedShort());
108 header.indexLength = swapShort(needByteSwap, dis.readUnsignedShort());
109 header.shiftedDataLength = swapShort(needByteSwap, dis.readUnsignedShort());
110 header.index2NullOffset = swapShort(needByteSwap, dis.readUnsignedShort());
111 header.dataNullOffset = swapShort(needByteSwap, dis.readUnsignedShort());
112 header.shiftedHighStart = swapShort(needByteSwap, dis.readUnsignedShort());
114 // Trie2 data width - 0: 16 bits
116 if ((header.options & UTRIE2_OPTIONS_VALUE_BITS_MASK) > 1) {
117 throw new IllegalArgumentException("UTrie2 serialized format error.");
121 if ((header.options & UTRIE2_OPTIONS_VALUE_BITS_MASK) == 0) {
122 width = ValueWidth.BITS_16;
123 This = new Trie2_16();
125 width = ValueWidth.BITS_32;
126 This = new Trie2_32();
128 This.header = header;
130 /* get the length values and offsets */
131 This.indexLength = header.indexLength;
132 This.dataLength = header.shiftedDataLength << UTRIE2_INDEX_SHIFT;
133 This.index2NullOffset = header.index2NullOffset;
134 This.dataNullOffset = header.dataNullOffset;
135 This.highStart = header.shiftedHighStart << UTRIE2_SHIFT_1;
136 This.highValueIndex = This.dataLength - UTRIE2_DATA_GRANULARITY;
137 if (width == ValueWidth.BITS_16) {
138 This.highValueIndex += This.indexLength;
141 // Allocate the Trie2 index array. If the data width is 16 bits, the array also
142 // includes the space for the data.
144 int indexArraySize = This.indexLength;
145 if (width == ValueWidth.BITS_16) {
146 indexArraySize += This.dataLength;
148 This.index = new char[indexArraySize];
150 /* Read in the index */
152 for (i=0; i<This.indexLength; i++) {
153 This.index[i] = swapChar(needByteSwap, dis.readChar());
156 /* Read in the data. 16 bit data goes in the same array as the index.
157 * 32 bit data goes in its own separate data array.
159 if (width == ValueWidth.BITS_16) {
160 This.data16 = This.indexLength;
161 for (i=0; i<This.dataLength; i++) {
162 This.index[This.data16 + i] = swapChar(needByteSwap, dis.readChar());
165 This.data32 = new int[This.dataLength];
166 for (i=0; i<This.dataLength; i++) {
167 This.data32[i] = swapInt(needByteSwap, dis.readInt());
174 This.initialValue = This.index[This.dataNullOffset];
175 This.errorValue = This.index[This.data16+UTRIE2_BAD_UTF8_DATA_OFFSET];
179 This.initialValue = This.data32[This.dataNullOffset];
180 This.errorValue = This.data32[UTRIE2_BAD_UTF8_DATA_OFFSET];
183 throw new IllegalArgumentException("UTrie2 serialized format error.");
190 private static int swapShort(boolean needSwap, int value) {
191 return needSwap? ((int)Short.reverseBytes((short)value)) & 0x0000ffff : value;
194 private static char swapChar(boolean needSwap, char value) {
195 return needSwap? (char)Short.reverseBytes((short)value) : value;
198 private static int swapInt(boolean needSwap, int value) {
199 return needSwap? Integer.reverseBytes(value) : value;
204 * Get the UTrie version from an InputStream containing the serialized form
205 * of either a Trie (version 1) or a Trie2 (version 2).
207 * @param is an InputStream containing the serialized form
208 * of a UTrie, version 1 or 2. The stream must support mark() and reset().
209 * The position of the input stream will be left unchanged.
210 * @param littleEndianOk If FALSE, only big-endian (Java native) serialized forms are recognized.
211 * If TRUE, little-endian serialized forms are recognized as well.
212 * @return the Trie version of the serialized form, or 0 if it is not
213 * recognized as a serialized UTrie
214 * @throws IOException on errors in reading from the input stream.
216 public static int getVersion(InputStream is, boolean littleEndianOk) throws IOException {
217 if (! is.markSupported()) {
218 throw new IllegalArgumentException("Input stream must support mark().");
221 byte sig[] = new byte[4];
222 int read = is.read(sig);
225 if (read != sig.length) {
229 if (sig[0]=='T' && sig[1]=='r' && sig[2]=='i' && sig[3]=='e') {
232 if (sig[0]=='T' && sig[1]=='r' && sig[2]=='i' && sig[3]=='2') {
235 if (littleEndianOk) {
236 if (sig[0]=='e' && sig[1]=='i' && sig[2]=='r' && sig[3]=='T') {
239 if (sig[0]=='2' && sig[1]=='i' && sig[2]=='r' && sig[3]=='T') {
248 * Get the value for a code point as stored in the Trie2.
250 * @param codePoint the code point
253 abstract public int get(int codePoint);
257 * Get the trie value for a UTF-16 code unit.
259 * A Trie2 stores two distinct values for input in the lead surrogate
260 * range, one for lead surrogates, which is the value that will be
261 * returned by this function, and a second value that is returned
264 * For code units outside of the lead surrogate range, this function
265 * returns the same result as Trie2.get().
267 * This function, together with the alternate value for lead surrogates,
268 * makes possible very efficient processing of UTF-16 strings without
269 * first converting surrogate pairs to their corresponding 32 bit code point
272 * At build-time, enumerate the contents of the Trie2 to see if there
273 * is non-trivial (non-initialValue) data for any of the supplementary
274 * code points associated with a lead surrogate.
275 * If so, then set a special (application-specific) value for the
276 * lead surrogate code _unit_, with Trie2Writable.setForLeadSurrogateCodeUnit().
278 * At runtime, use Trie2.getFromU16SingleLead(). If there is non-trivial
279 * data and the code unit is a lead surrogate, then check if a trail surrogate
280 * follows. If so, assemble the supplementary code point and look up its value
281 * with Trie2.get(); otherwise reset the lead
282 * surrogate's value or do a code point lookup for it.
284 * If there is only trivial data for lead and trail surrogates, then processing
285 * can often skip them. For example, in normalization or case mapping
286 * all characters that do not have any mappings are simply copied as is.
288 * @param c the code point or lead surrogate value.
291 abstract public int getFromU16SingleLead(char c);
295 * Equals function. Two Tries are equal if their contents are equal.
296 * The type need not be the same, so a Trie2Writable will be equal to
297 * (read-only) Trie2_16 or Trie2_32 so long as they are storing the same values.
300 public final boolean equals(Object other) {
301 if(!(other instanceof Trie2)) {
304 Trie2 OtherTrie = (Trie2)other;
305 Range rangeFromOther;
307 Iterator<Trie2.Range> otherIter = OtherTrie.iterator();
308 for (Trie2.Range rangeFromThis: this) {
309 if (otherIter.hasNext() == false) {
312 rangeFromOther = otherIter.next();
313 if (!rangeFromThis.equals(rangeFromOther)) {
317 if (otherIter.hasNext()) {
321 if (errorValue != OtherTrie.errorValue ||
322 initialValue != OtherTrie.initialValue) {
330 public int hashCode() {
332 int hash = initHash();
333 for (Range r: this) {
334 hash = hashInt(hash, r.hashCode());
345 * When iterating over the contents of a Trie2, Elements of this type are produced.
346 * The iterator will return one item for each contiguous range of codepoints having the same value.
348 * When iterating, the same Trie2EnumRange object will be reused and returned for each range.
349 * If you need to retain complete iteration results, clone each returned Trie2EnumRange,
350 * or save the range in some other way, before advancing to the next iteration step.
352 public static class Range {
353 public int startCodePoint;
354 public int endCodePoint; // Inclusive.
356 public boolean leadSurrogate;
358 public boolean equals(Object other) {
359 if (other == null || !(other.getClass().equals(getClass()))) {
362 Range tother = (Range)other;
363 return this.startCodePoint == tother.startCodePoint &&
364 this.endCodePoint == tother.endCodePoint &&
365 this.value == tother.value &&
366 this.leadSurrogate == tother.leadSurrogate;
370 public int hashCode() {
372 h = hashUChar32(h, startCodePoint);
373 h = hashUChar32(h, endCodePoint);
374 h = hashInt(h, value);
375 h = hashByte(h, leadSurrogate? 1: 0);
382 * Create an iterator over the value ranges in this Trie2.
383 * Values from the Trie2 are not remapped or filtered, but are returned as they
384 * are stored in the Trie2.
386 * @return an Iterator
388 public Iterator<Range> iterator() {
389 return iterator(defaultValueMapper);
392 private static ValueMapper defaultValueMapper = new ValueMapper() {
393 public int map(int in) {
399 * Create an iterator over the value ranges from this Trie2.
400 * Values from the Trie2 are passed through a caller-supplied remapping function,
401 * and it is the remapped values that determine the ranges that
402 * will be produced by the iterator.
405 * @param mapper provides a function to remap values obtained from the Trie2.
406 * @return an Iterator
408 public Iterator<Range> iterator(ValueMapper mapper) {
409 return new Trie2Iterator(mapper);
414 * Create an iterator over the Trie2 values for the 1024=0x400 code points
415 * corresponding to a given lead surrogate.
416 * For example, for the lead surrogate U+D87E it will enumerate the values
417 * for [U+2F800..U+2FC00[.
418 * Used by data builder code that sets special lead surrogate code unit values
419 * for optimized UTF-16 string processing.
421 * Do not modify the Trie2 during the iteration.
423 * Except for the limited code point range, this functions just like Trie2.iterator().
426 public Iterator<Range> iteratorForLeadSurrogate(char lead, ValueMapper mapper) {
427 return new Trie2Iterator(lead, mapper);
431 * Create an iterator over the Trie2 values for the 1024=0x400 code points
432 * corresponding to a given lead surrogate.
433 * For example, for the lead surrogate U+D87E it will enumerate the values
434 * for [U+2F800..U+2FC00[.
435 * Used by data builder code that sets special lead surrogate code unit values
436 * for optimized UTF-16 string processing.
438 * Do not modify the Trie2 during the iteration.
440 * Except for the limited code point range, this functions just like Trie2.iterator().
443 public Iterator<Range> iteratorForLeadSurrogate(char lead) {
444 return new Trie2Iterator(lead, defaultValueMapper);
448 * When iterating over the contents of a Trie2, an instance of TrieValueMapper may
449 * be used to remap the values from the Trie2. The remapped values will be used
450 * both in determining the ranges of codepoints and as the value to be returned
453 * Example of use, with an anonymous subclass of TrieValueMapper:
456 * ValueMapper m = new ValueMapper() {
457 * int map(int in) {return in & 0x1f;};
459 * for (Iterator<Trie2EnumRange> iter = trie.iterator(m); i.hasNext(); ) {
460 * Trie2EnumRange r = i.next();
461 * ... // Do something with the range r.
465 public interface ValueMapper {
466 public int map(int originalVal);
471 * Serialize a trie2 Header and Index onto an OutputStream. This is
472 * common code used for both the Trie2_16 and Trie2_32 serialize functions.
473 * @param dos the stream to which the serialized Trie2 data will be written.
474 * @return the number of bytes written.
476 protected int serializeHeader(DataOutputStream dos) throws IOException {
477 // Write the header. It is already set and ready to use, having been
478 // created when the Trie2 was unserialized or when it was frozen.
479 int bytesWritten = 0;
481 dos.writeInt(header.signature);
482 dos.writeShort(header.options);
483 dos.writeShort(header.indexLength);
484 dos.writeShort(header.shiftedDataLength);
485 dos.writeShort(header.index2NullOffset);
486 dos.writeShort(header.dataNullOffset);
487 dos.writeShort(header.shiftedHighStart);
492 for (i=0; i< header.indexLength; i++) {
493 dos.writeChar(index[i]);
495 bytesWritten += header.indexLength;
501 * Struct-like class for holding the results returned by a UTrie2 CharSequence iterator.
502 * The iteration walks over a CharSequence, and for each Unicode code point therein
503 * returns the character and its associated Trie2 value.
505 public static class CharSequenceValues {
506 /** string index of the current code point. */
508 /** The code point at index. */
509 public int codePoint;
510 /** The Trie2 value for the current code point */
516 * Create an iterator that will produce the values from the Trie2 for
517 * the sequence of code points in an input text.
519 * @param text A text string to be iterated over.
520 * @param index The starting iteration position within the input text.
521 * @return the CharSequenceIterator
523 public CharSequenceIterator charSequenceIterator(CharSequence text, int index) {
524 return new CharSequenceIterator(text, index);
527 // TODO: Survey usage of the equivalent of CharSequenceIterator in ICU4C
528 // and if there is none, remove it from here.
529 // Don't waste time testing and maintaining unused code.
532 * An iterator that operates over an input CharSequence, and for each Unicode code point
533 * in the input returns the associated value from the Trie2.
535 * The iterator can move forwards or backwards, and can be reset to an arbitrary index.
537 * Note that Trie2_16 and Trie2_32 subclass Trie2.CharSequenceIterator. This is done
538 * only for performance reasons. It does require that any changes made here be propagated
539 * into the corresponding code in the subclasses.
541 public class CharSequenceIterator implements Iterator<CharSequenceValues> {
543 * Internal constructor.
545 CharSequenceIterator(CharSequence t, int index) {
547 textLength = text.length();
551 private CharSequence text;
552 private int textLength;
554 private Trie2.CharSequenceValues fResults = new Trie2.CharSequenceValues();
557 public void set(int i) {
558 if (i < 0 || i > textLength) {
559 throw new IndexOutOfBoundsException();
565 public final boolean hasNext() {
566 return index<textLength;
570 public final boolean hasPrevious() {
575 public Trie2.CharSequenceValues next() {
576 int c = Character.codePointAt(text, index);
579 fResults.index = index;
580 fResults.codePoint = c;
581 fResults.value = val;
590 public Trie2.CharSequenceValues previous() {
591 int c = Character.codePointBefore(text, index);
597 fResults.index = index;
598 fResults.codePoint = c;
599 fResults.value = val;
604 * Iterator.remove() is not supported by Trie2.CharSequenceIterator.
605 * @throws UnsupportedOperationException Always thrown because this operation is not supported
606 * @see java.util.Iterator#remove()
608 public void remove() {
609 throw new UnsupportedOperationException("Trie2.CharSequenceIterator does not support remove().");
614 //--------------------------------------------------------------------------------
616 // Below this point are internal implementation items. No further public API.
618 //--------------------------------------------------------------------------------
622 * Selectors for the width of a UTrie2 data value.
630 * Trie2 data structure in serialized form:
632 * UTrie2Header header;
633 * uint16_t index[header.index2Length];
634 * uint16_t data[header.shiftedDataLength<<2]; -- or uint32_t data[...]
636 * For Java, this is read from the stream into an instance of UTrie2Header.
637 * (The C version just places a struct over the raw serialized data.)
641 static class UTrie2Header {
642 /** "Tri2" in big-endian US-ASCII (0x54726932) */
646 * options bit field (uint16_t):
647 * 15.. 4 reserved (0)
648 * 3.. 0 UTrie2ValueBits valueBits
652 /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH (uint16_t) */
655 /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT (uint16_t) */
656 int shiftedDataLength;
658 /** Null index and data blocks, not shifted. (uint16_t) */
659 int index2NullOffset, dataNullOffset;
662 * First code point of the single-value range ending with U+10ffff,
663 * rounded up and then shifted right by UTRIE2_SHIFT_1. (uint16_t)
665 int shiftedHighStart;
669 // Data members of UTrie2.
672 char index[]; // Index array. Includes data for 16 bit Tries.
673 int data16; // Offset to data portion of the index array, if 16 bit data.
674 // zero if 32 bit data.
675 int data32[]; // NULL if 16b data is used via index
679 int index2NullOffset; // 0xffff if there is no dedicated index-2 null block
682 /** Value returned for out-of-range code points and illegal UTF-8. */
685 /* Start of the last range which ends at U+10ffff, and its value. */
691 int fHash; // Zero if not yet computed.
692 // Shared by Trie2Writable, Trie2_16, Trie2_32.
693 // Thread safety: if two racing threads compute
694 // the same hash on a frozen Trie2, no damage is done.
698 * Trie2 constants, defining shift widths, index array lengths, etc.
700 * These are needed for the runtime macros but users can treat these as
701 * implementation details and skip to the actual public API further below.
704 static final int UTRIE2_OPTIONS_VALUE_BITS_MASK=0x000f;
707 /** Shift size for getting the index-1 table offset. */
708 static final int UTRIE2_SHIFT_1=6+5;
710 /** Shift size for getting the index-2 table offset. */
711 static final int UTRIE2_SHIFT_2=5;
714 * Difference between the two shift sizes,
715 * for getting an index-1 offset from an index-2 offset. 6=11-5
717 static final int UTRIE2_SHIFT_1_2=UTRIE2_SHIFT_1-UTRIE2_SHIFT_2;
720 * Number of index-1 entries for the BMP. 32=0x20
721 * This part of the index-1 table is omitted from the serialized form.
723 static final int UTRIE2_OMITTED_BMP_INDEX_1_LENGTH=0x10000>>UTRIE2_SHIFT_1;
725 /** Number of code points per index-1 table entry. 2048=0x800 */
726 static final int UTRIE2_CP_PER_INDEX_1_ENTRY=1<<UTRIE2_SHIFT_1;
728 /** Number of entries in an index-2 block. 64=0x40 */
729 static final int UTRIE2_INDEX_2_BLOCK_LENGTH=1<<UTRIE2_SHIFT_1_2;
731 /** Mask for getting the lower bits for the in-index-2-block offset. */
732 static final int UTRIE2_INDEX_2_MASK=UTRIE2_INDEX_2_BLOCK_LENGTH-1;
734 /** Number of entries in a data block. 32=0x20 */
735 static final int UTRIE2_DATA_BLOCK_LENGTH=1<<UTRIE2_SHIFT_2;
737 /** Mask for getting the lower bits for the in-data-block offset. */
738 static final int UTRIE2_DATA_MASK=UTRIE2_DATA_BLOCK_LENGTH-1;
741 * Shift size for shifting left the index array values.
742 * Increases possible data size with 16-bit index values at the cost
744 * This requires data blocks to be aligned by UTRIE2_DATA_GRANULARITY.
746 static final int UTRIE2_INDEX_SHIFT=2;
748 /** The alignment size of a data block. Also the granularity for compaction. */
749 static final int UTRIE2_DATA_GRANULARITY=1<<UTRIE2_INDEX_SHIFT;
751 /* Fixed layout of the first part of the index array. ------------------- */
754 * The BMP part of the index-2 table is fixed and linear and starts at offset 0.
755 * Length=2048=0x800=0x10000>>UTRIE2_SHIFT_2.
757 static final int UTRIE2_INDEX_2_OFFSET=0;
760 * The part of the index-2 table for U+D800..U+DBFF stores values for
761 * lead surrogate code _units_ not code _points_.
762 * Values for lead surrogate code _points_ are indexed with this portion of the table.
763 * Length=32=0x20=0x400>>UTRIE2_SHIFT_2. (There are 1024=0x400 lead surrogates.)
765 static final int UTRIE2_LSCP_INDEX_2_OFFSET=0x10000>>UTRIE2_SHIFT_2;
766 static final int UTRIE2_LSCP_INDEX_2_LENGTH=0x400>>UTRIE2_SHIFT_2;
768 /** Count the lengths of both BMP pieces. 2080=0x820 */
769 static final int UTRIE2_INDEX_2_BMP_LENGTH=UTRIE2_LSCP_INDEX_2_OFFSET+UTRIE2_LSCP_INDEX_2_LENGTH;
772 * The 2-byte UTF-8 version of the index-2 table follows at offset 2080=0x820.
773 * Length 32=0x20 for lead bytes C0..DF, regardless of UTRIE2_SHIFT_2.
775 static final int UTRIE2_UTF8_2B_INDEX_2_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH;
776 static final int UTRIE2_UTF8_2B_INDEX_2_LENGTH=0x800>>6; /* U+0800 is the first code point after 2-byte UTF-8 */
779 * The index-1 table, only used for supplementary code points, at offset 2112=0x840.
780 * Variable length, for code points up to highStart, where the last single-value range starts.
781 * Maximum length 512=0x200=0x100000>>UTRIE2_SHIFT_1.
782 * (For 0x100000 supplementary code points U+10000..U+10ffff.)
784 * The part of the index-2 table for supplementary code points starts
785 * after this index-1 table.
787 * Both the index-1 table and the following part of the index-2 table
788 * are omitted completely if there is only BMP data.
790 static final int UTRIE2_INDEX_1_OFFSET=UTRIE2_UTF8_2B_INDEX_2_OFFSET+UTRIE2_UTF8_2B_INDEX_2_LENGTH;
791 static final int UTRIE2_MAX_INDEX_1_LENGTH=0x100000>>UTRIE2_SHIFT_1;
794 * Fixed layout of the first part of the data array. -----------------------
795 * Starts with 4 blocks (128=0x80 entries) for ASCII.
799 * The illegal-UTF-8 data block follows the ASCII block, at offset 128=0x80.
800 * Used with linear access for single bytes 0..0xbf for simple error handling.
801 * Length 64=0x40, not UTRIE2_DATA_BLOCK_LENGTH.
803 static final int UTRIE2_BAD_UTF8_DATA_OFFSET=0x80;
805 /** The start of non-linear-ASCII data blocks, at offset 192=0xc0. */
806 static final int UTRIE2_DATA_START_OFFSET=0xc0;
808 /* Building a Trie2 ---------------------------------------------------------- */
811 * These definitions are mostly needed by utrie2_builder.c, but also by
812 * utrie2_get32() and utrie2_enum().
816 * At build time, leave a gap in the index-2 table,
817 * at least as long as the maximum lengths of the 2-byte UTF-8 index-2 table
818 * and the supplementary index-1 table.
819 * Round up to UTRIE2_INDEX_2_BLOCK_LENGTH for proper compacting.
821 static final int UNEWTRIE2_INDEX_GAP_OFFSET = UTRIE2_INDEX_2_BMP_LENGTH;
822 static final int UNEWTRIE2_INDEX_GAP_LENGTH =
823 ((UTRIE2_UTF8_2B_INDEX_2_LENGTH + UTRIE2_MAX_INDEX_1_LENGTH) + UTRIE2_INDEX_2_MASK) &
824 ~UTRIE2_INDEX_2_MASK;
827 * Maximum length of the build-time index-2 array.
828 * Maximum number of Unicode code points (0x110000) shifted right by UTRIE2_SHIFT_2,
829 * plus the part of the index-2 table for lead surrogate code points,
830 * plus the build-time index gap,
831 * plus the null index-2 block.
833 static final int UNEWTRIE2_MAX_INDEX_2_LENGTH=
834 (0x110000>>UTRIE2_SHIFT_2)+
835 UTRIE2_LSCP_INDEX_2_LENGTH+
836 UNEWTRIE2_INDEX_GAP_LENGTH+
837 UTRIE2_INDEX_2_BLOCK_LENGTH;
839 static final int UNEWTRIE2_INDEX_1_LENGTH = 0x110000>>UTRIE2_SHIFT_1;
842 * Maximum length of the build-time data array.
843 * One entry per 0x110000 code points, plus the illegal-UTF-8 block and the null block,
844 * plus values for the 0x400 surrogate code units.
846 static final int UNEWTRIE2_MAX_DATA_LENGTH = (0x110000+0x40+0x40+0x400);
851 * Implementation class for an iterator over a Trie2.
853 * Iteration over a Trie2 first returns all of the ranges that are indexed by code points,
854 * then returns the special alternate values for the lead surrogates
858 class Trie2Iterator implements Iterator<Range> {
859 // The normal constructor that configures the iterator to cover the complete
860 // contents of the Trie2
861 Trie2Iterator(ValueMapper vm) {
865 doLeadSurrogates = true;
868 // An alternate constructor that configures the iterator to cover only the
869 // code points corresponding to a particular Lead Surrogate value.
870 Trie2Iterator(char leadSurrogate, ValueMapper vm) {
871 if (leadSurrogate < 0xd800 || leadSurrogate > 0xdbff) {
872 throw new IllegalArgumentException("Bad lead surrogate value.");
875 nextStart = (leadSurrogate - 0xd7c0) << 10;
876 limitCP = nextStart + 0x400;
877 doLeadSurrogates = false; // Do not iterate over lead the special lead surrogate
878 // values after completing iteration over code points.
882 * The main next() function for Trie2 iterators
885 public Range next() {
887 throw new NoSuchElementException();
889 if (nextStart >= limitCP) {
890 // Switch over from iterating normal code point values to
891 // doing the alternate lead-surrogate values.
892 doingCodePoints = false;
899 if (doingCodePoints) {
900 // Iteration over code point values.
901 val = get(nextStart);
902 mappedVal = mapper.map(val);
903 endOfRange = rangeEnd(nextStart, limitCP, val);
904 // Loop once for each range in the Trie2 with the same raw (unmapped) value.
905 // Loop continues so long as the mapped values are the same.
907 if (endOfRange >= limitCP-1) {
910 val = get(endOfRange+1);
911 if (mapper.map(val) != mappedVal) {
914 endOfRange = rangeEnd(endOfRange+1, limitCP, val);
917 // Iteration over the alternate lead surrogate values.
918 val = getFromU16SingleLead((char)nextStart);
919 mappedVal = mapper.map(val);
920 endOfRange = rangeEndLS((char)nextStart);
921 // Loop once for each range in the Trie2 with the same raw (unmapped) value.
922 // Loop continues so long as the mapped values are the same.
924 if (endOfRange >= 0xdbff) {
927 val = getFromU16SingleLead((char)(endOfRange+1));
928 if (mapper.map(val) != mappedVal) {
931 endOfRange = rangeEndLS((char)(endOfRange+1));
934 returnValue.startCodePoint = nextStart;
935 returnValue.endCodePoint = endOfRange;
936 returnValue.value = mappedVal;
937 returnValue.leadSurrogate = !doingCodePoints;
938 nextStart = endOfRange+1;
945 public boolean hasNext() {
946 return doingCodePoints && (doLeadSurrogates || nextStart < limitCP) || nextStart < 0xdc00;
949 public void remove() {
950 throw new UnsupportedOperationException();
955 * Find the last lead surrogate in a contiguous range with the
956 * same Trie2 value as the input character.
958 * Use the alternate Lead Surrogate values from the Trie2,
959 * not the code-point values.
961 * Note: Trie2_16 and Trie2_32 override this implementation with optimized versions,
962 * meaning that the implementation here is only being used with
963 * Trie2Writable. The code here is logically correct with any type
966 * @param c The character to begin with.
967 * @return The last contiguous character with the same value.
969 private int rangeEndLS(char startingLS) {
970 if (startingLS >= 0xdbff) {
975 int val = getFromU16SingleLead(startingLS);
976 for (c = startingLS+1; c <= 0x0dbff; c++) {
977 if (getFromU16SingleLead((char)c) != val) {
985 // Iteration State Variables
987 private ValueMapper mapper;
988 private Range returnValue = new Range();
989 // The starting code point for the next range to be returned.
990 private int nextStart;
991 // The upper limit for the last normal range to be returned. Normally 0x110000, but
992 // may be lower when iterating over the code points for a single lead surrogate.
995 // True while iterating over the the Trie2 values for code points.
996 // False while iterating over the alternate values for lead surrogates.
997 private boolean doingCodePoints = true;
999 // True if the iterator should iterate the special values for lead surrogates in
1000 // addition to the normal values for code points.
1001 private boolean doLeadSurrogates = true;
1005 * Find the last character in a contiguous range of characters with the
1006 * same Trie2 value as the input character.
1008 * @param c The character to begin with.
1009 * @return The last contiguous character with the same value.
1011 int rangeEnd(int start, int limitp, int val) {
1013 int limit = Math.min(highStart, limitp);
1015 for (c = start+1; c < limit; c++) {
1016 if (get(c) != val) {
1020 if (c >= highStart) {
1028 // Hashing implementation functions. FNV hash. Respected public domain algorithm.
1030 private static int initHash() {
1031 return 0x811c9DC5; // unsigned 2166136261
1034 private static int hashByte(int h, int b) {
1040 private static int hashUChar32(int h, int c) {
1041 h = Trie2.hashByte(h, c & 255);
1042 h = Trie2.hashByte(h, (c>>8) & 255);
1043 h = Trie2.hashByte(h, c>>16);
1047 private static int hashInt(int h, int i) {
1048 h = Trie2.hashByte(h, i & 255);
1049 h = Trie2.hashByte(h, (i>>8) & 255);
1050 h = Trie2.hashByte(h, (i>>16) & 255);
1051 h = Trie2.hashByte(h, (i>>24) & 255);