1// © 2016 and later: Unicode, Inc. and others.
2// License & terms of use: http://www.unicode.org/copyright.html
3/*
4*******************************************************************************
5* Copyright (C) 2010-2014, International Business Machines
6* Corporation and others. All Rights Reserved.
7*******************************************************************************
8* collationiterator.h
9*
10* created on: 2010oct27
11* created by: Markus W. Scherer
12*/
13
14#ifndef __COLLATIONITERATOR_H__
15#define __COLLATIONITERATOR_H__
16
17#include "unicode/utypes.h"
18
19#if !UCONFIG_NO_COLLATION
20
21#include "cmemory.h"
22#include "collation.h"
23#include "collationdata.h"
24
25U_NAMESPACE_BEGIN
26
27class SkippedState;
28class UCharsTrie;
29class UVector32;
30
31/* Large enough for CEs of most short strings. */
32#define CEBUFFER_INITIAL_CAPACITY 40
33
34// Export an explicit template instantiation of the MaybeStackArray that
35// is used as a data member of CEBuffer.
36//
37// When building DLLs for Windows this is required even though
38// no direct access to the MaybeStackArray leaks out of the i18n library.
39//
40// See digitlst.h, pluralaffix.h, datefmt.h, and others for similar examples.
41//
42#if U_PF_WINDOWS <= U_PLATFORM && U_PLATFORM <= U_PF_CYGWIN
43template class U_I18N_API MaybeStackArray<int64_t, CEBUFFER_INITIAL_CAPACITY>;
44#endif
45
46/**
47 * Collation element iterator and abstract character iterator.
48 *
49 * When a method returns a code point value, it must be in 0..10FFFF,
50 * except it can be negative as a sentinel value.
51 */
52class U_I18N_API CollationIterator : public UObject {
53private:
54 class U_I18N_API CEBuffer {
55 private:
56 /** Large enough for CEs of most short strings. */
57 static const int32_t INITIAL_CAPACITY = CEBUFFER_INITIAL_CAPACITY;
58 public:
59 CEBuffer() : length(0) {}
60 ~CEBuffer();
61
62 inline void append(int64_t ce, UErrorCode &errorCode) {
63 if(length < INITIAL_CAPACITY || ensureAppendCapacity(1, errorCode)) {
64 buffer[length++] = ce;
65 }
66 }
67
68 inline void appendUnsafe(int64_t ce) {
69 buffer[length++] = ce;
70 }
71
72 UBool ensureAppendCapacity(int32_t appCap, UErrorCode &errorCode);
73
74 inline UBool incLength(UErrorCode &errorCode) {
75 // Use INITIAL_CAPACITY for a very simple fastpath.
76 // (Rather than buffer.getCapacity().)
77 if(length < INITIAL_CAPACITY || ensureAppendCapacity(1, errorCode)) {
78 ++length;
79 return TRUE;
80 } else {
81 return FALSE;
82 }
83 }
84
85 inline int64_t set(int32_t i, int64_t ce) {
86 return buffer[i] = ce;
87 }
88 inline int64_t get(int32_t i) const { return buffer[i]; }
89
90 const int64_t *getCEs() const { return buffer.getAlias(); }
91
92 int32_t length;
93
94 private:
95 CEBuffer(const CEBuffer &);
96 void operator=(const CEBuffer &);
97
98 MaybeStackArray<int64_t, INITIAL_CAPACITY> buffer;
99 };
100
101public:
102 CollationIterator(const CollationData *d, UBool numeric)
103 : trie(d->trie),
104 data(d),
105 cesIndex(0),
106 skipped(NULL),
107 numCpFwd(-1),
108 isNumeric(numeric) {}
109
110 virtual ~CollationIterator();
111
112 virtual UBool operator==(const CollationIterator &other) const;
113 inline UBool operator!=(const CollationIterator &other) const {
114 return !operator==(other);
115 }
116
117 /**
118 * Resets the iterator state and sets the position to the specified offset.
119 * Subclasses must implement, and must call the parent class method,
120 * or CollationIterator::reset().
121 */
122 virtual void resetToOffset(int32_t newOffset) = 0;
123
124 virtual int32_t getOffset() const = 0;
125
126 /**
127 * Returns the next collation element.
128 */
129 inline int64_t nextCE(UErrorCode &errorCode) {
130 if(cesIndex < ceBuffer.length) {
131 // Return the next buffered CE.
132 return ceBuffer.get(cesIndex++);
133 }
134 // assert cesIndex == ceBuffer.length;
135 if(!ceBuffer.incLength(errorCode)) {
136 return Collation::NO_CE;
137 }
138 UChar32 c;
139 uint32_t ce32 = handleNextCE32(c, errorCode);
140 uint32_t t = ce32 & 0xff;
141 if(t < Collation::SPECIAL_CE32_LOW_BYTE) { // Forced-inline of isSpecialCE32(ce32).
142 // Normal CE from the main data.
143 // Forced-inline of ceFromSimpleCE32(ce32).
144 return ceBuffer.set(cesIndex++,
145 ((int64_t)(ce32 & 0xffff0000) << 32) | ((ce32 & 0xff00) << 16) | (t << 8));
146 }
147 const CollationData *d;
148 // The compiler should be able to optimize the previous and the following
149 // comparisons of t with the same constant.
150 if(t == Collation::SPECIAL_CE32_LOW_BYTE) {
151 if(c < 0) {
152 return ceBuffer.set(cesIndex++, Collation::NO_CE);
153 }
154 d = data->base;
155 ce32 = d->getCE32(c);
156 t = ce32 & 0xff;
157 if(t < Collation::SPECIAL_CE32_LOW_BYTE) {
158 // Normal CE from the base data.
159 return ceBuffer.set(cesIndex++,
160 ((int64_t)(ce32 & 0xffff0000) << 32) | ((ce32 & 0xff00) << 16) | (t << 8));
161 }
162 } else {
163 d = data;
164 }
165 if(t == Collation::LONG_PRIMARY_CE32_LOW_BYTE) {
166 // Forced-inline of ceFromLongPrimaryCE32(ce32).
167 return ceBuffer.set(cesIndex++,
168 ((int64_t)(ce32 - t) << 32) | Collation::COMMON_SEC_AND_TER_CE);
169 }
170 return nextCEFromCE32(d, c, ce32, errorCode);
171 }
172
173 /**
174 * Fetches all CEs.
175 * @return getCEsLength()
176 */
177 int32_t fetchCEs(UErrorCode &errorCode);
178
179 /**
180 * Overwrites the current CE (the last one returned by nextCE()).
181 */
182 void setCurrentCE(int64_t ce) {
183 // assert cesIndex > 0;
184 ceBuffer.set(cesIndex - 1, ce);
185 }
186
187 /**
188 * Returns the previous collation element.
189 */
190 int64_t previousCE(UVector32 &offsets, UErrorCode &errorCode);
191
192 inline int32_t getCEsLength() const {
193 return ceBuffer.length;
194 }
195
196 inline int64_t getCE(int32_t i) const {
197 return ceBuffer.get(i);
198 }
199
200 const int64_t *getCEs() const {
201 return ceBuffer.getCEs();
202 }
203
204 void clearCEs() {
205 cesIndex = ceBuffer.length = 0;
206 }
207
208 void clearCEsIfNoneRemaining() {
209 if(cesIndex == ceBuffer.length) { clearCEs(); }
210 }
211
212 /**
213 * Returns the next code point (with post-increment).
214 * Public for identical-level comparison and for testing.
215 */
216 virtual UChar32 nextCodePoint(UErrorCode &errorCode) = 0;
217
218 /**
219 * Returns the previous code point (with pre-decrement).
220 * Public for identical-level comparison and for testing.
221 */
222 virtual UChar32 previousCodePoint(UErrorCode &errorCode) = 0;
223
224protected:
225 CollationIterator(const CollationIterator &other);
226
227 void reset();
228
229 /**
230 * Returns the next code point and its local CE32 value.
231 * Returns Collation::FALLBACK_CE32 at the end of the text (c<0)
232 * or when c's CE32 value is to be looked up in the base data (fallback).
233 *
234 * The code point is used for fallbacks, context and implicit weights.
235 * It is ignored when the returned CE32 is not special (e.g., FFFD_CE32).
236 */
237 virtual uint32_t handleNextCE32(UChar32 &c, UErrorCode &errorCode);
238
239 /**
240 * Called when handleNextCE32() returns a LEAD_SURROGATE_TAG for a lead surrogate code unit.
241 * Returns the trail surrogate in that case and advances past it,
242 * if a trail surrogate follows the lead surrogate.
243 * Otherwise returns any other code unit and does not advance.
244 */
245 virtual UChar handleGetTrailSurrogate();
246
247 /**
248 * Called when handleNextCE32() returns with c==0, to see whether it is a NUL terminator.
249 * (Not needed in Java.)
250 */
251 virtual UBool foundNULTerminator();
252
253 /**
254 * @return FALSE if surrogate code points U+D800..U+DFFF
255 * map to their own implicit primary weights (for UTF-16),
256 * or TRUE if they map to CE(U+FFFD) (for UTF-8)
257 */
258 virtual UBool forbidSurrogateCodePoints() const;
259
260 virtual void forwardNumCodePoints(int32_t num, UErrorCode &errorCode) = 0;
261
262 virtual void backwardNumCodePoints(int32_t num, UErrorCode &errorCode) = 0;
263
264 /**
265 * Returns the CE32 from the data trie.
266 * Normally the same as data->getCE32(), but overridden in the builder.
267 * Call this only when the faster data->getCE32() cannot be used.
268 */
269 virtual uint32_t getDataCE32(UChar32 c) const;
270
271 virtual uint32_t getCE32FromBuilderData(uint32_t ce32, UErrorCode &errorCode);
272
273 void appendCEsFromCE32(const CollationData *d, UChar32 c, uint32_t ce32,
274 UBool forward, UErrorCode &errorCode);
275
276 // Main lookup trie of the data object.
277 const UTrie2 *trie;
278 const CollationData *data;
279
280private:
281 int64_t nextCEFromCE32(const CollationData *d, UChar32 c, uint32_t ce32,
282 UErrorCode &errorCode);
283
284 uint32_t getCE32FromPrefix(const CollationData *d, uint32_t ce32,
285 UErrorCode &errorCode);
286
287 UChar32 nextSkippedCodePoint(UErrorCode &errorCode);
288
289 void backwardNumSkipped(int32_t n, UErrorCode &errorCode);
290
291 uint32_t nextCE32FromContraction(
292 const CollationData *d, uint32_t contractionCE32,
293 const UChar *p, uint32_t ce32, UChar32 c,
294 UErrorCode &errorCode);
295
296 uint32_t nextCE32FromDiscontiguousContraction(
297 const CollationData *d, UCharsTrie &suffixes, uint32_t ce32,
298 int32_t lookAhead, UChar32 c,
299 UErrorCode &errorCode);
300
301 /**
302 * Returns the previous CE when data->isUnsafeBackward(c, isNumeric).
303 */
304 int64_t previousCEUnsafe(UChar32 c, UVector32 &offsets, UErrorCode &errorCode);
305
306 /**
307 * Turns a string of digits (bytes 0..9)
308 * into a sequence of CEs that will sort in numeric order.
309 *
310 * Starts from this ce32's digit value and consumes the following/preceding digits.
311 * The digits string must not be empty and must not have leading zeros.
312 */
313 void appendNumericCEs(uint32_t ce32, UBool forward, UErrorCode &errorCode);
314
315 /**
316 * Turns 1..254 digits into a sequence of CEs.
317 * Called by appendNumericCEs() for each segment of at most 254 digits.
318 */
319 void appendNumericSegmentCEs(const char *digits, int32_t length, UErrorCode &errorCode);
320
321 CEBuffer ceBuffer;
322 int32_t cesIndex;
323
324 SkippedState *skipped;
325
326 // Number of code points to read forward, or -1.
327 // Used as a forward iteration limit in previousCEUnsafe().
328 int32_t numCpFwd;
329 // Numeric collation (CollationSettings::NUMERIC).
330 UBool isNumeric;
331};
332
333U_NAMESPACE_END
334
335#endif // !UCONFIG_NO_COLLATION
336#endif // __COLLATIONITERATOR_H__
337