icuSources/i18n/collationiterator.h

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