1 /*
2 * Copyright (c) 2005, 2009, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 /*
26 *******************************************************************************
27 * (C) Copyright IBM Corp. and others, 1996-2009 - All Rights Reserved *
28 * *
29 * The original version of this source code and documentation is copyrighted *
30 * and owned by IBM, These materials are provided under terms of a License *
31 * Agreement between IBM and Sun. This technology is protected by multiple *
32 * US and International patents. This notice and attribution to IBM may not *
33 * to removed. *
34 *******************************************************************************
35 */
36
37 package sun.text.normalizer;
38
39 /**
40 * Class enabling iteration of the values in a Trie.
41 * <p>Result of each iteration contains the interval of codepoints that have
42 * the same value type and the value type itself.
43 * <p>The comparison of each codepoint value is done via extract(), which the
44 * default implementation is to return the value as it is.
45 * <p>Method extract() can be overwritten to perform manipulations on
46 * codepoint values in order to perform specialized comparison.
47 * <p>TrieIterator is designed to be a generic iterator for the CharTrie
48 * and the IntTrie, hence to accommodate both types of data, the return
49 * result will be in terms of int (32 bit) values.
50 * <p>See com.ibm.icu.text.UCharacterTypeIterator for examples of use.
51 * <p>Notes for porting utrie_enum from icu4c to icu4j:<br>
52 * Internally, icu4c's utrie_enum performs all iterations in its body. In Java
53 * sense, the caller will have to pass a object with a callback function
54 * UTrieEnumRange(const void *context, UChar32 start, UChar32 limit,
55 * uint32_t value) into utrie_enum. utrie_enum will then find ranges of
56 * codepoints with the same value as determined by
57 * UTrieEnumValue(const void *context, uint32_t value). for each range,
58 * utrie_enum calls the callback function to perform a task. In this way,
59 * icu4c performs the iteration within utrie_enum.
60 * To follow the JDK model, icu4j is slightly different from icu4c.
61 * Instead of requesting the caller to implement an object for a callback.
62 * The caller will have to implement a subclass of TrieIterator, fleshing out
63 * the method extract(int) (equivalent to UTrieEnumValue). Independent of icu4j,
64 * the caller will have to code his own iteration and flesh out the task
65 * (equivalent to UTrieEnumRange) to be performed in the iteration loop.
66 *
67 * <p>There are basically 3 usage scenarios for porting:
68 * <p>1) UTrieEnumValue is the only implemented callback then just implement a
69 * subclass of TrieIterator and override the extract(int) method. The
70 * extract(int) method is analogus to UTrieEnumValue callback.
71 *
72 * <p>2) UTrieEnumValue and UTrieEnumRange both are implemented then implement
73 * a subclass of TrieIterator, override the extract method and iterate, e.g.<br>
74 * {@code utrie_enum(&normTrie, _enumPropertyStartsValue, _enumPropertyStartsRange,
75 * set);}<br>
76 * In Java:<br>
77 * <pre>
78 * class TrieIteratorImpl extends TrieIterator{
79 * public TrieIteratorImpl(Trie data){
80 * super(data);
81 * }
82 * public int extract(int value){
83 * // port the implementation of _enumPropertyStartsValue here
84 * }
85 * }
86 * ....
87 * TrieIterator fcdIter = new TrieIteratorImpl(fcdTrieImpl.fcdTrie);
88 * while(fcdIter.next(result)) {
89 * // port the implementation of _enumPropertyStartsRange
90 * }
91 * </pre>
92 *
93 * <p>3) UTrieEnumRange is the only implemented callback then just implement
94 * the while loop, when utrie_enum is called
95 * <pre>{@code
96 * // utrie_enum(&fcdTrie, NULL, _enumPropertyStartsRange, set);
97 * TrieIterator fcdIter = new TrieIterator(fcdTrieImpl.fcdTrie);
98 * while(fcdIter.next(result)){
99 * set.add(result.start);
100 * }
101 * }</pre>
102 *
103 * @author synwee
104 * @see com.ibm.icu.impl.Trie
105 * @see com.ibm.icu.lang.UCharacterTypeIterator
106 * @since release 2.1, Jan 17 2002
107 */
108 public class TrieIterator implements RangeValueIterator
109 {
110
111 // public constructor ---------------------------------------------
112
113 /**
114 * TrieEnumeration constructor
115 * @param trie to be used
116 * @exception IllegalArgumentException throw when argument is null.
117 */
118 public TrieIterator(Trie trie)
119 {
120 if (trie == null) {
121 throw new IllegalArgumentException(
122 "Argument trie cannot be null");
123 }
124 m_trie_ = trie;
125 // synwee: check that extract belongs to the child class
126 m_initialValue_ = extract(m_trie_.getInitialValue());
127 reset();
128 }
129
130 // public methods -------------------------------------------------
131
132 /**
133 * <p>Returns true if we are not at the end of the iteration, false
134 * otherwise.</p>
135 * <p>The next set of codepoints with the same value type will be
136 * calculated during this call and returned in the arguement element.</p>
137 * @param element return result
138 * @return true if we are not at the end of the iteration, false otherwise.
139 * @exception NoSuchElementException - if no more elements exist.
140 * @see com.ibm.icu.util.RangeValueIterator.Element
141 */
142 public final boolean next(Element element)
143 {
144 if (m_nextCodepoint_ > UCharacter.MAX_VALUE) {
145 return false;
146 }
147 if (m_nextCodepoint_ < UCharacter.SUPPLEMENTARY_MIN_VALUE &&
148 calculateNextBMPElement(element)) {
149 return true;
150 }
151 calculateNextSupplementaryElement(element);
152 return true;
153 }
154
155 /**
156 * Resets the iterator to the beginning of the iteration
157 */
158 public final void reset()
159 {
160 m_currentCodepoint_ = 0;
161 m_nextCodepoint_ = 0;
162 m_nextIndex_ = 0;
163 m_nextBlock_ = m_trie_.m_index_[0] << Trie.INDEX_STAGE_2_SHIFT_;
164 if (m_nextBlock_ == 0) {
165 m_nextValue_ = m_initialValue_;
166 }
167 else {
168 m_nextValue_ = extract(m_trie_.getValue(m_nextBlock_));
169 }
170 m_nextBlockIndex_ = 0;
171 m_nextTrailIndexOffset_ = TRAIL_SURROGATE_INDEX_BLOCK_LENGTH_;
172 }
173
174 // protected methods ----------------------------------------------
175
176 /**
177 * Called by next() to extracts a 32 bit value from a trie value
178 * used for comparison.
179 * This method is to be overwritten if special manipulation is to be done
180 * to retrieve a relevant comparison.
181 * The default function is to return the value as it is.
182 * @param value a value from the trie
183 * @return extracted value
184 */
185 protected int extract(int value)
186 {
187 return value;
188 }
189
190 // private methods ------------------------------------------------
191
192 /**
193 * Set the result values
194 * @param element return result object
195 * @param start codepoint of range
196 * @param limit (end + 1) codepoint of range
197 * @param value common value of range
198 */
199 private final void setResult(Element element, int start, int limit,
200 int value)
201 {
202 element.start = start;
203 element.limit = limit;
204 element.value = value;
205 }
206
207 /**
208 * Finding the next element.
209 * This method is called just before returning the result of
210 * next().
211 * We always store the next element before it is requested.
212 * In the case that we have to continue calculations into the
213 * supplementary planes, a false will be returned.
214 * @param element return result object
215 * @return true if the next range is found, false if we have to proceed to
216 * the supplementary range.
217 */
218 private final boolean calculateNextBMPElement(Element element)
219 {
220 int currentBlock = m_nextBlock_;
221 int currentValue = m_nextValue_;
222 m_currentCodepoint_ = m_nextCodepoint_;
223 m_nextCodepoint_ ++;
224 m_nextBlockIndex_ ++;
225 if (!checkBlockDetail(currentValue)) {
226 setResult(element, m_currentCodepoint_, m_nextCodepoint_,
227 currentValue);
228 return true;
229 }
230 // synwee check that next block index == 0 here
231 // enumerate BMP - the main loop enumerates data blocks
232 while (m_nextCodepoint_ < UCharacter.SUPPLEMENTARY_MIN_VALUE) {
233 m_nextIndex_ ++;
234 // because of the way the character is split to form the index
235 // the lead surrogate and trail surrogate can not be in the
236 // mid of a block
237 if (m_nextCodepoint_ == LEAD_SURROGATE_MIN_VALUE_) {
238 // skip lead surrogate code units,
239 // go to lead surrogate codepoints
240 m_nextIndex_ = BMP_INDEX_LENGTH_;
241 }
242 else if (m_nextCodepoint_ == TRAIL_SURROGATE_MIN_VALUE_) {
243 // go back to regular BMP code points
244 m_nextIndex_ = m_nextCodepoint_ >> Trie.INDEX_STAGE_1_SHIFT_;
245 }
246
247 m_nextBlockIndex_ = 0;
248 if (!checkBlock(currentBlock, currentValue)) {
249 setResult(element, m_currentCodepoint_, m_nextCodepoint_,
250 currentValue);
251 return true;
252 }
253 }
254 m_nextCodepoint_ --; // step one back since this value has not been
255 m_nextBlockIndex_ --; // retrieved yet.
256 return false;
257 }
258
259 /**
260 * Finds the next supplementary element.
261 * For each entry in the trie, the value to be delivered is passed through
262 * extract().
263 * We always store the next element before it is requested.
264 * Called after calculateNextBMP() completes its round of BMP characters.
265 * There is a slight difference in the usage of m_currentCodepoint_
266 * here as compared to calculateNextBMP(). Though both represents the
267 * lower bound of the next element, in calculateNextBMP() it gets set
268 * at the start of any loop, where-else, in calculateNextSupplementary()
269 * since m_currentCodepoint_ already contains the lower bound of the
270 * next element (passed down from calculateNextBMP()), we keep it till
271 * the end before resetting it to the new value.
272 * Note, if there are no more iterations, it will never get to here.
273 * Blocked out by next().
274 * @param element return result object
275 */
276 private final void calculateNextSupplementaryElement(Element element)
277 {
278 int currentValue = m_nextValue_;
279 int currentBlock = m_nextBlock_;
280 m_nextCodepoint_ ++;
281 m_nextBlockIndex_ ++;
282
283 if (UTF16.getTrailSurrogate(m_nextCodepoint_)
284 != UTF16.TRAIL_SURROGATE_MIN_VALUE) {
285 // this piece is only called when we are in the middle of a lead
286 // surrogate block
287 if (!checkNullNextTrailIndex() && !checkBlockDetail(currentValue)) {
288 setResult(element, m_currentCodepoint_, m_nextCodepoint_,
289 currentValue);
290 m_currentCodepoint_ = m_nextCodepoint_;
291 return;
292 }
293 // we have cleared one block
294 m_nextIndex_ ++;
295 m_nextTrailIndexOffset_ ++;
296 if (!checkTrailBlock(currentBlock, currentValue)) {
297 setResult(element, m_currentCodepoint_, m_nextCodepoint_,
298 currentValue);
299 m_currentCodepoint_ = m_nextCodepoint_;
300 return;
301 }
302 }
303 int nextLead = UTF16.getLeadSurrogate(m_nextCodepoint_);
304 // enumerate supplementary code points
305 while (nextLead < TRAIL_SURROGATE_MIN_VALUE_) {
306 // lead surrogate access
307 int leadBlock =
308 m_trie_.m_index_[nextLead >> Trie.INDEX_STAGE_1_SHIFT_] <<
309 Trie.INDEX_STAGE_2_SHIFT_;
310 if (leadBlock == m_trie_.m_dataOffset_) {
311 // no entries for a whole block of lead surrogates
312 if (currentValue != m_initialValue_) {
313 m_nextValue_ = m_initialValue_;
314 m_nextBlock_ = 0;
315 m_nextBlockIndex_ = 0;
316 setResult(element, m_currentCodepoint_, m_nextCodepoint_,
317 currentValue);
318 m_currentCodepoint_ = m_nextCodepoint_;
319 return;
320 }
321
322 nextLead += DATA_BLOCK_LENGTH_;
323 // number of total affected supplementary codepoints in one
324 // block
325 // this is not a simple addition of
326 // DATA_BLOCK_SUPPLEMENTARY_LENGTH since we need to consider
327 // that we might have moved some of the codepoints
328 m_nextCodepoint_ = UCharacterProperty.getRawSupplementary(
329 (char)nextLead,
330 (char)UTF16.TRAIL_SURROGATE_MIN_VALUE);
331 continue;
332 }
333 if (m_trie_.m_dataManipulate_ == null) {
334 throw new NullPointerException(
335 "The field DataManipulate in this Trie is null");
336 }
337 // enumerate trail surrogates for this lead surrogate
338 m_nextIndex_ = m_trie_.m_dataManipulate_.getFoldingOffset(
339 m_trie_.getValue(leadBlock +
340 (nextLead & Trie.INDEX_STAGE_3_MASK_)));
341 if (m_nextIndex_ <= 0) {
342 // no data for this lead surrogate
343 if (currentValue != m_initialValue_) {
344 m_nextValue_ = m_initialValue_;
345 m_nextBlock_ = 0;
346 m_nextBlockIndex_ = 0;
347 setResult(element, m_currentCodepoint_, m_nextCodepoint_,
348 currentValue);
349 m_currentCodepoint_ = m_nextCodepoint_;
350 return;
351 }
352 m_nextCodepoint_ += TRAIL_SURROGATE_COUNT_;
353 } else {
354 m_nextTrailIndexOffset_ = 0;
355 if (!checkTrailBlock(currentBlock, currentValue)) {
356 setResult(element, m_currentCodepoint_, m_nextCodepoint_,
357 currentValue);
358 m_currentCodepoint_ = m_nextCodepoint_;
359 return;
360 }
361 }
362 nextLead ++;
363 }
364
365 // deliver last range
366 setResult(element, m_currentCodepoint_, UCharacter.MAX_VALUE + 1,
367 currentValue);
368 }
369
370 /**
371 * Internal block value calculations
372 * Performs calculations on a data block to find codepoints in m_nextBlock_
373 * after the index m_nextBlockIndex_ that has the same value.
374 * Note m_*_ variables at this point is the next codepoint whose value
375 * has not been calculated.
376 * But when returned with false, it will be the last codepoint whose
377 * value has been calculated.
378 * @param currentValue the value which other codepoints are tested against
379 * @return true if the whole block has the same value as currentValue or if
380 * the whole block has been calculated, false otherwise.
381 */
382 private final boolean checkBlockDetail(int currentValue)
383 {
384 while (m_nextBlockIndex_ < DATA_BLOCK_LENGTH_) {
385 m_nextValue_ = extract(m_trie_.getValue(m_nextBlock_ +
386 m_nextBlockIndex_));
387 if (m_nextValue_ != currentValue) {
388 return false;
389 }
390 ++ m_nextBlockIndex_;
391 ++ m_nextCodepoint_;
392 }
393 return true;
394 }
395
396 /**
397 * Internal block value calculations
398 * Performs calculations on a data block to find codepoints in m_nextBlock_
399 * that has the same value.
400 * Will call checkBlockDetail() if highlevel check fails.
401 * Note m_*_ variables at this point is the next codepoint whose value
402 * has not been calculated.
403 * @param currentBlock the initial block containing all currentValue
404 * @param currentValue the value which other codepoints are tested against
405 * @return true if the whole block has the same value as currentValue or if
406 * the whole block has been calculated, false otherwise.
407 */
408 private final boolean checkBlock(int currentBlock, int currentValue)
409 {
410 m_nextBlock_ = m_trie_.m_index_[m_nextIndex_] <<
411 Trie.INDEX_STAGE_2_SHIFT_;
412 if (m_nextBlock_ == currentBlock &&
413 (m_nextCodepoint_ - m_currentCodepoint_) >= DATA_BLOCK_LENGTH_) {
414 // the block is the same as the previous one, filled with
415 // currentValue
416 m_nextCodepoint_ += DATA_BLOCK_LENGTH_;
417 }
418 else if (m_nextBlock_ == 0) {
419 // this is the all-initial-value block
420 if (currentValue != m_initialValue_) {
421 m_nextValue_ = m_initialValue_;
422 m_nextBlockIndex_ = 0;
423 return false;
424 }
425 m_nextCodepoint_ += DATA_BLOCK_LENGTH_;
426 }
427 else {
428 if (!checkBlockDetail(currentValue)) {
429 return false;
430 }
431 }
432 return true;
433 }
434
435 /**
436 * Internal block value calculations
437 * Performs calculations on multiple data blocks for a set of trail
438 * surrogates to find codepoints in m_nextBlock_ that has the same value.
439 * Will call checkBlock() for internal block checks.
440 * Note m_*_ variables at this point is the next codepoint whose value
441 * has not been calculated.
442 * @param currentBlock the initial block containing all currentValue
443 * @param currentValue the value which other codepoints are tested against
444 * @return true if the whole block has the same value as currentValue or if
445 * the whole block has been calculated, false otherwise.
446 */
447 private final boolean checkTrailBlock(int currentBlock,
448 int currentValue)
449 {
450 // enumerate code points for this lead surrogate
451 while (m_nextTrailIndexOffset_ < TRAIL_SURROGATE_INDEX_BLOCK_LENGTH_)
452 {
453 // if we ever reach here, we are at the start of a new block
454 m_nextBlockIndex_ = 0;
455 // copy of most of the body of the BMP loop
456 if (!checkBlock(currentBlock, currentValue)) {
457 return false;
458 }
459 m_nextTrailIndexOffset_ ++;
460 m_nextIndex_ ++;
461 }
462 return true;
463 }
464
465 /**
466 * Checks if we are beginning at the start of a initial block.
467 * If we are then the rest of the codepoints in this initial block
468 * has the same values.
469 * We increment m_nextCodepoint_ and relevant data members if so.
470 * This is used only in for the supplementary codepoints because
471 * the offset to the trail indexes could be 0.
472 * @return true if we are at the start of a initial block.
473 */
474 private final boolean checkNullNextTrailIndex()
475 {
476 if (m_nextIndex_ <= 0) {
477 m_nextCodepoint_ += TRAIL_SURROGATE_COUNT_ - 1;
478 int nextLead = UTF16.getLeadSurrogate(m_nextCodepoint_);
479 int leadBlock =
480 m_trie_.m_index_[nextLead >> Trie.INDEX_STAGE_1_SHIFT_] <<
481 Trie.INDEX_STAGE_2_SHIFT_;
482 if (m_trie_.m_dataManipulate_ == null) {
483 throw new NullPointerException(
484 "The field DataManipulate in this Trie is null");
485 }
486 m_nextIndex_ = m_trie_.m_dataManipulate_.getFoldingOffset(
487 m_trie_.getValue(leadBlock +
488 (nextLead & Trie.INDEX_STAGE_3_MASK_)));
489 m_nextIndex_ --;
490 m_nextBlockIndex_ = DATA_BLOCK_LENGTH_;
491 return true;
492 }
493 return false;
494 }
495
496 // private data members --------------------------------------------
497
498 /**
499 * Size of the stage 1 BMP indexes
500 */
501 private static final int BMP_INDEX_LENGTH_ =
502 0x10000 >> Trie.INDEX_STAGE_1_SHIFT_;
503 /**
504 * Lead surrogate minimum value
505 */
506 private static final int LEAD_SURROGATE_MIN_VALUE_ = 0xD800;
507 /**
508 * Trail surrogate minimum value
509 */
510 private static final int TRAIL_SURROGATE_MIN_VALUE_ = 0xDC00;
511 /**
512 * Number of trail surrogate
513 */
514 private static final int TRAIL_SURROGATE_COUNT_ = 0x400;
515 /**
516 * Number of stage 1 indexes for supplementary calculations that maps to
517 * each lead surrogate character.
518 * See second pass into getRawOffset for the trail surrogate character.
519 * 10 for significant number of bits for trail surrogates, 5 for what we
520 * discard during shifting.
521 */
522 private static final int TRAIL_SURROGATE_INDEX_BLOCK_LENGTH_ =
523 1 << (10 - Trie.INDEX_STAGE_1_SHIFT_);
524 /**
525 * Number of data values in a stage 2 (data array) block.
526 */
527 private static final int DATA_BLOCK_LENGTH_ =
528 1 << Trie.INDEX_STAGE_1_SHIFT_;
529 /**
530 * Trie instance
531 */
532 private Trie m_trie_;
533 /**
534 * Initial value for trie values
535 */
536 private int m_initialValue_;
537 /**
538 * Next element results and data.
539 */
540 private int m_currentCodepoint_;
541 private int m_nextCodepoint_;
542 private int m_nextValue_;
543 private int m_nextIndex_;
544 private int m_nextBlock_;
545 private int m_nextBlockIndex_;
546 private int m_nextTrailIndexOffset_;
547 }