1/*
2*******************************************************************************
3* Copyright (C) 2013-2014, International Business Machines
4* Corporation and others.  All Rights Reserved.
5*******************************************************************************
6* collationrootelements.h
7*
8* created on: 2013mar01
9* created by: Markus W. Scherer
10*/
11
12#ifndef __COLLATIONROOTELEMENTS_H__
13#define __COLLATIONROOTELEMENTS_H__
14
15#include "unicode/utypes.h"
16
17#if !UCONFIG_NO_COLLATION
18
19#include "unicode/uobject.h"
20#include "collation.h"
21
22U_NAMESPACE_BEGIN
23
24/**
25 * Container and access methods for collation elements and weights
26 * that occur in the root collator.
27 * Needed for finding boundaries for building a tailoring.
28 *
29 * This class takes and returns 16-bit secondary and tertiary weights.
30 */
31class U_I18N_API CollationRootElements : public UMemory {
32public:
33    CollationRootElements(const uint32_t *rootElements, int32_t rootElementsLength)
34            : elements(rootElements), length(rootElementsLength) {}
35
36    /**
37     * Higher than any root primary.
38     */
39    static const uint32_t PRIMARY_SENTINEL = 0xffffff00;
40
41    /**
42     * Flag in a root element, set if the element contains secondary & tertiary weights,
43     * rather than a primary.
44     */
45    static const uint32_t SEC_TER_DELTA_FLAG = 0x80;
46    /**
47     * Mask for getting the primary range step value from a primary-range-end element.
48     */
49    static const uint8_t PRIMARY_STEP_MASK = 0x7f;
50
51    enum {
52        /**
53         * Index of the first CE with a non-zero tertiary weight.
54         * Same as the start of the compact root elements table.
55         */
56        IX_FIRST_TERTIARY_INDEX,
57        /**
58         * Index of the first CE with a non-zero secondary weight.
59         */
60        IX_FIRST_SECONDARY_INDEX,
61        /**
62         * Index of the first CE with a non-zero primary weight.
63         */
64        IX_FIRST_PRIMARY_INDEX,
65        /**
66         * Must match Collation::COMMON_SEC_AND_TER_CE.
67         */
68        IX_COMMON_SEC_AND_TER_CE,
69        /**
70         * Secondary & tertiary boundaries.
71         * Bits 31..24: [fixed last secondary common byte 45]
72         * Bits 23..16: [fixed first ignorable secondary byte 80]
73         * Bits 15.. 8: reserved, 0
74         * Bits  7.. 0: [fixed first ignorable tertiary byte 3C]
75         */
76        IX_SEC_TER_BOUNDARIES,
77        /**
78         * The current number of indexes.
79         * Currently the same as elements[IX_FIRST_TERTIARY_INDEX].
80         */
81        IX_COUNT
82    };
83
84    /**
85     * Returns the boundary between tertiary weights of primary/secondary CEs
86     * and those of tertiary CEs.
87     * This is the upper limit for tertiaries of primary/secondary CEs.
88     * This minus one is the lower limit for tertiaries of tertiary CEs.
89     */
90    uint32_t getTertiaryBoundary() const {
91        return (elements[IX_SEC_TER_BOUNDARIES] << 8) & 0xff00;
92    }
93
94    /**
95     * Returns the first assigned tertiary CE.
96     */
97    uint32_t getFirstTertiaryCE() const {
98        return elements[elements[IX_FIRST_TERTIARY_INDEX]] & ~SEC_TER_DELTA_FLAG;
99    }
100
101    /**
102     * Returns the last assigned tertiary CE.
103     */
104    uint32_t getLastTertiaryCE() const {
105        return elements[elements[IX_FIRST_SECONDARY_INDEX] - 1] & ~SEC_TER_DELTA_FLAG;
106    }
107
108    /**
109     * Returns the last common secondary weight.
110     * This is the lower limit for secondaries of primary CEs.
111     */
112    uint32_t getLastCommonSecondary() const {
113        return (elements[IX_SEC_TER_BOUNDARIES] >> 16) & 0xff00;
114    }
115
116    /**
117     * Returns the boundary between secondary weights of primary CEs
118     * and those of secondary CEs.
119     * This is the upper limit for secondaries of primary CEs.
120     * This minus one is the lower limit for secondaries of secondary CEs.
121     */
122    uint32_t getSecondaryBoundary() const {
123        return (elements[IX_SEC_TER_BOUNDARIES] >> 8) & 0xff00;
124    }
125
126    /**
127     * Returns the first assigned secondary CE.
128     */
129    uint32_t getFirstSecondaryCE() const {
130        return elements[elements[IX_FIRST_SECONDARY_INDEX]] & ~SEC_TER_DELTA_FLAG;
131    }
132
133    /**
134     * Returns the last assigned secondary CE.
135     */
136    uint32_t getLastSecondaryCE() const {
137        return elements[elements[IX_FIRST_PRIMARY_INDEX] - 1] & ~SEC_TER_DELTA_FLAG;
138    }
139
140    /**
141     * Returns the first assigned primary weight.
142     */
143    uint32_t getFirstPrimary() const {
144        return elements[elements[IX_FIRST_PRIMARY_INDEX]];  // step=0: cannot be a range end
145    }
146
147    /**
148     * Returns the first assigned primary CE.
149     */
150    int64_t getFirstPrimaryCE() const {
151        return Collation::makeCE(getFirstPrimary());
152    }
153
154    /**
155     * Returns the last root CE with a primary weight before p.
156     * Intended only for reordering group boundaries.
157     */
158    int64_t lastCEWithPrimaryBefore(uint32_t p) const;
159
160    /**
161     * Returns the first root CE with a primary weight of at least p.
162     * Intended only for reordering group boundaries.
163     */
164    int64_t firstCEWithPrimaryAtLeast(uint32_t p) const;
165
166    /**
167     * Returns the primary weight before p.
168     * p must be greater than the first root primary.
169     */
170    uint32_t getPrimaryBefore(uint32_t p, UBool isCompressible) const;
171
172    /** Returns the secondary weight before [p, s]. */
173    uint32_t getSecondaryBefore(uint32_t p, uint32_t s) const;
174
175    /** Returns the tertiary weight before [p, s, t]. */
176    uint32_t getTertiaryBefore(uint32_t p, uint32_t s, uint32_t t) const;
177
178    /**
179     * Finds the index of the input primary.
180     * p must occur as a root primary, and must not be 0.
181     */
182    int32_t findPrimary(uint32_t p) const;
183
184    /**
185     * Returns the primary weight after p where index=findPrimary(p).
186     * p must be at least the first root primary.
187     */
188    uint32_t getPrimaryAfter(uint32_t p, int32_t index, UBool isCompressible) const;
189    /**
190     * Returns the secondary weight after [p, s] where index=findPrimary(p)
191     * except use index=0 for p=0.
192     */
193    uint32_t getSecondaryAfter(int32_t index, uint32_t s) const;
194    /**
195     * Returns the tertiary weight after [p, s, t] where index=findPrimary(p)
196     * except use index=0 for p=0.
197     */
198    uint32_t getTertiaryAfter(int32_t index, uint32_t s, uint32_t t) const;
199
200private:
201    /**
202     * Finds the largest index i where elements[i]<=p.
203     * Requires first primary<=p<0xffffff00 (PRIMARY_SENTINEL).
204     * Does not require that p is a root collator primary.
205     */
206    int32_t findP(uint32_t p) const;
207
208    static inline UBool isEndOfPrimaryRange(uint32_t q) {
209        return (q & SEC_TER_DELTA_FLAG) == 0 && (q & PRIMARY_STEP_MASK) != 0;
210    }
211
212    /**
213     * Data structure:
214     *
215     * The first few entries are indexes, up to elements[IX_FIRST_TERTIARY_INDEX].
216     * See the comments on the IX_ constants.
217     *
218     * All other elements are a compact form of the root collator CEs
219     * in collation order.
220     *
221     * Primary weights have the SEC_TER_DELTA_FLAG flag not set.
222     * A primary-weight element by itself represents a root CE
223     * with Collation::COMMON_SEC_AND_TER_CE.
224     *
225     * If there are root CEs with the same primary but other secondary/tertiary weights,
226     * then for each such CE there is an element with those secondary and tertiary weights,
227     * and with the SEC_TER_DELTA_FLAG flag set.
228     *
229     * A range of only-primary CEs with a consistent "step" increment
230     * from each primary to the next may be stored as a range.
231     * Only the first and last primary are stored, and the last has the step
232     * value in the low bits (PRIMARY_STEP_MASK).
233     *
234     * An range-end element may also either start a new range or be followed by
235     * elements with secondary/tertiary deltas.
236     *
237     * A primary element that is not a range end has zero step bits.
238     *
239     * There is no element for the completely ignorable CE (all weights 0).
240     *
241     * Before elements[IX_FIRST_PRIMARY_INDEX], all elements are secondary/tertiary deltas,
242     * for all of the ignorable root CEs.
243     *
244     * There are no elements for unassigned-implicit primary CEs.
245     * All primaries stored here are at most 3 bytes long.
246     */
247    const uint32_t *elements;
248    int32_t length;
249};
250
251U_NAMESPACE_END
252
253#endif  // !UCONFIG_NO_COLLATION
254#endif  // __COLLATIONROOTELEMENTS_H__
255