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