icuSources/i18n/collationiterator.h

   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
  25 U_NAMESPACE_BEGIN
  26
  27 class SkippedState;
  28 class UCharsTrie;
  29 class 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
  43 template 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  */
  52 class U_I18N_API CollationIterator : public UObject {
  53 private:
  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
 101 public:
 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
 224 protected:
 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
 280 private:
 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
 333 U_NAMESPACE_END
 334
 335 #endif  // !UCONFIG_NO_COLLATION
 336 #endif  // __COLLATIONITERATOR_H__