1/* 2******************************************************************************* 3* Copyright (C) 2011-2014, International Business Machines 4* Corporation and others. All Rights Reserved. 5******************************************************************************* 6* created on: 2011jan05 7* created by: Markus W. Scherer 8* ported from ICU4C bytestriebuilder.h/.cpp 9*/ 10 11package com.ibm.icu.util; 12 13import java.nio.ByteBuffer; 14 15/** 16 * Builder class for BytesTrie. 17 * 18 * <p>This class is not intended for public subclassing. 19 * 20 * @stable ICU 4.8 21 * @author Markus W. Scherer 22 */ 23public final class BytesTrieBuilder extends StringTrieBuilder { 24 /** 25 * Constructs an empty builder. 26 * @stable ICU 4.8 27 */ 28 public BytesTrieBuilder() {} 29 30 // Used in add() to wrap the bytes into a CharSequence for StringTrieBuilder.addImpl(). 31 private static final class BytesAsCharSequence implements CharSequence { 32 public BytesAsCharSequence(byte[] sequence, int length) { 33 s=sequence; 34 len=length; 35 } 36 public char charAt(int i) { return (char)(s[i]&0xff); } 37 public int length() { return len; } 38 public CharSequence subSequence(int start, int end) { return null; } 39 40 private byte[] s; 41 private int len; 42 } 43 44 /** 45 * Adds a (byte sequence, value) pair. 46 * The byte sequence must be unique. 47 * Bytes 0..length-1 will be copied; the builder does not keep 48 * a reference to the input array. 49 * @param sequence The array that contains the byte sequence, starting at index 0. 50 * @param length The length of the byte sequence. 51 * @param value The value associated with this byte sequence. 52 * @return this 53 * @stable ICU 4.8 54 */ 55 public BytesTrieBuilder add(byte[] sequence, int length, int value) { 56 addImpl(new BytesAsCharSequence(sequence, length), value); 57 return this; 58 } 59 60 /** 61 * Builds a BytesTrie for the add()ed data. 62 * Once built, no further data can be add()ed until clear() is called. 63 * 64 * <p>A BytesTrie cannot be empty. At least one (byte sequence, value) pair 65 * must have been add()ed. 66 * 67 * <p>Multiple calls to build() or buildByteBuffer() return tries or buffers 68 * which share the builder's byte array, without rebuilding. 69 * <em>The byte array must not be modified via the buildByteBuffer() result object.</em> 70 * After clear() has been called, a new array will be used. 71 * @param buildOption Build option, see StringTrieBuilder.Option. 72 * @return A new BytesTrie for the add()ed data. 73 * @stable ICU 4.8 74 */ 75 public BytesTrie build(StringTrieBuilder.Option buildOption) { 76 buildBytes(buildOption); 77 return new BytesTrie(bytes, bytes.length-bytesLength); 78 } 79 80 /** 81 * Builds a BytesTrie for the add()ed data and byte-serializes it. 82 * Once built, no further data can be add()ed until clear() is called. 83 * 84 * <p>A BytesTrie cannot be empty. At least one (byte sequence, value) pair 85 * must have been add()ed. 86 * 87 * <p>Multiple calls to build() or buildByteBuffer() return tries or buffers 88 * which share the builder's byte array, without rebuilding. 89 * <em>Do not modify the bytes in the buffer!</em> 90 * After clear() has been called, a new array will be used. 91 * 92 * <p>The serialized BytesTrie is accessible via the buffer's 93 * array()/arrayOffset()+position() or remaining()/get(byte[]) etc. 94 * @param buildOption Build option, see StringTrieBuilder.Option. 95 * @return A ByteBuffer with the byte-serialized BytesTrie for the add()ed data. 96 * The buffer is not read-only and array() can be called. 97 * @stable ICU 4.8 98 */ 99 public ByteBuffer buildByteBuffer(StringTrieBuilder.Option buildOption) { 100 buildBytes(buildOption); 101 return ByteBuffer.wrap(bytes, bytes.length-bytesLength, bytesLength); 102 } 103 104 private void buildBytes(StringTrieBuilder.Option buildOption) { 105 // Create and byte-serialize the trie for the elements. 106 if(bytes==null) { 107 bytes=new byte[1024]; 108 } 109 buildImpl(buildOption); 110 } 111 112 /** 113 * Removes all (byte sequence, value) pairs. 114 * New data can then be add()ed and a new trie can be built. 115 * @return this 116 * @stable ICU 4.8 117 */ 118 public BytesTrieBuilder clear() { 119 clearImpl(); 120 bytes=null; 121 bytesLength=0; 122 return this; 123 } 124 125 /** 126 * {@inheritDoc} 127 * @internal 128 * @deprecated This API is ICU internal only. 129 */ 130 @Deprecated 131 @Override 132 protected boolean matchNodesCanHaveValues() /*const*/ { return false; } 133 134 /** 135 * {@inheritDoc} 136 * @internal 137 * @deprecated This API is ICU internal only. 138 */ 139 @Deprecated 140 @Override 141 protected int getMaxBranchLinearSubNodeLength() /*const*/ { return BytesTrie.kMaxBranchLinearSubNodeLength; } 142 /** 143 * {@inheritDoc} 144 * @internal 145 * @deprecated This API is ICU internal only. 146 */ 147 @Deprecated 148 @Override 149 protected int getMinLinearMatch() /*const*/ { return BytesTrie.kMinLinearMatch; } 150 /** 151 * {@inheritDoc} 152 * @internal 153 * @deprecated This API is ICU internal only. 154 */ 155 @Deprecated 156 @Override 157 protected int getMaxLinearMatchLength() /*const*/ { return BytesTrie.kMaxLinearMatchLength; } 158 159 private void ensureCapacity(int length) { 160 if(length>bytes.length) { 161 int newCapacity=bytes.length; 162 do { 163 newCapacity*=2; 164 } while(newCapacity<=length); 165 byte[] newBytes=new byte[newCapacity]; 166 System.arraycopy(bytes, bytes.length-bytesLength, 167 newBytes, newBytes.length-bytesLength, bytesLength); 168 bytes=newBytes; 169 } 170 } 171 /** 172 * {@inheritDoc} 173 * @internal 174 * @deprecated This API is ICU internal only. 175 */ 176 @Deprecated 177 @Override 178 protected int write(int b) { 179 int newLength=bytesLength+1; 180 ensureCapacity(newLength); 181 bytesLength=newLength; 182 bytes[bytes.length-bytesLength]=(byte)b; 183 return bytesLength; 184 } 185 /** 186 * {@inheritDoc} 187 * @internal 188 * @deprecated This API is ICU internal only. 189 */ 190 @Deprecated 191 @Override 192 protected int write(int offset, int length) { 193 int newLength=bytesLength+length; 194 ensureCapacity(newLength); 195 bytesLength=newLength; 196 int bytesOffset=bytes.length-bytesLength; 197 while(length>0) { 198 bytes[bytesOffset++]=(byte)strings.charAt(offset++); 199 --length; 200 } 201 return bytesLength; 202 } 203 private int write(byte[] b, int length) { 204 int newLength=bytesLength+length; 205 ensureCapacity(newLength); 206 bytesLength=newLength; 207 System.arraycopy(b, 0, bytes, bytes.length-bytesLength, length); 208 return bytesLength; 209 } 210 211 // For writeValueAndFinal() and writeDeltaTo(). 212 private final byte[] intBytes=new byte[5]; 213 214 /** 215 * {@inheritDoc} 216 * @internal 217 * @deprecated This API is ICU internal only. 218 */ 219 @Deprecated 220 @Override 221 protected int writeValueAndFinal(int i, boolean isFinal) { 222 if(0<=i && i<=BytesTrie.kMaxOneByteValue) { 223 return write(((BytesTrie.kMinOneByteValueLead+i)<<1)|(isFinal?1:0)); 224 } 225 int length=1; 226 if(i<0 || i>0xffffff) { 227 intBytes[0]=(byte)BytesTrie.kFiveByteValueLead; 228 intBytes[1]=(byte)(i>>24); 229 intBytes[2]=(byte)(i>>16); 230 intBytes[3]=(byte)(i>>8); 231 intBytes[4]=(byte)i; 232 length=5; 233 // } else if(i<=BytesTrie.kMaxOneByteValue) { 234 // intBytes[0]=(byte)(BytesTrie.kMinOneByteValueLead+i); 235 } else { 236 if(i<=BytesTrie.kMaxTwoByteValue) { 237 intBytes[0]=(byte)(BytesTrie.kMinTwoByteValueLead+(i>>8)); 238 } else { 239 if(i<=BytesTrie.kMaxThreeByteValue) { 240 intBytes[0]=(byte)(BytesTrie.kMinThreeByteValueLead+(i>>16)); 241 } else { 242 intBytes[0]=(byte)BytesTrie.kFourByteValueLead; 243 intBytes[1]=(byte)(i>>16); 244 length=2; 245 } 246 intBytes[length++]=(byte)(i>>8); 247 } 248 intBytes[length++]=(byte)i; 249 } 250 intBytes[0]=(byte)((intBytes[0]<<1)|(isFinal?1:0)); 251 return write(intBytes, length); 252 } 253 /** 254 * {@inheritDoc} 255 * @internal 256 * @deprecated This API is ICU internal only. 257 */ 258 @Deprecated 259 @Override 260 protected int writeValueAndType(boolean hasValue, int value, int node) { 261 int offset=write(node); 262 if(hasValue) { 263 offset=writeValueAndFinal(value, false); 264 } 265 return offset; 266 } 267 /** 268 * {@inheritDoc} 269 * @internal 270 * @deprecated This API is ICU internal only. 271 */ 272 @Deprecated 273 @Override 274 protected int writeDeltaTo(int jumpTarget) { 275 int i=bytesLength-jumpTarget; 276 assert(i>=0); 277 if(i<=BytesTrie.kMaxOneByteDelta) { 278 return write(i); 279 } 280 int length; 281 if(i<=BytesTrie.kMaxTwoByteDelta) { 282 intBytes[0]=(byte)(BytesTrie.kMinTwoByteDeltaLead+(i>>8)); 283 length=1; 284 } else { 285 if(i<=BytesTrie.kMaxThreeByteDelta) { 286 intBytes[0]=(byte)(BytesTrie.kMinThreeByteDeltaLead+(i>>16)); 287 length=2; 288 } else { 289 if(i<=0xffffff) { 290 intBytes[0]=(byte)BytesTrie.kFourByteDeltaLead; 291 length=3; 292 } else { 293 intBytes[0]=(byte)BytesTrie.kFiveByteDeltaLead; 294 intBytes[1]=(byte)(i>>24); 295 length=4; 296 } 297 intBytes[1]=(byte)(i>>16); 298 } 299 intBytes[1]=(byte)(i>>8); 300 } 301 intBytes[length++]=(byte)i; 302 return write(intBytes, length); 303 } 304 305 // Byte serialization of the trie. 306 // Grows from the back: bytesLength measures from the end of the buffer! 307 private byte[] bytes; 308 private int bytesLength; 309} 310