[apple/icu.git] / icuSources / i18n / collationrootelements.cpp

/*
*******************************************************************************
* Copyright (C) 2013-2014, International Business Machines
* Corporation and others.  All Rights Reserved.
*******************************************************************************
* collationrootelements.cpp
*
* created on: 2013mar05
* created by: Markus W. Scherer
*/

#include "unicode/utypes.h"

#if !UCONFIG_NO_COLLATION

#include "collation.h"
#include "collationrootelements.h"
#include "uassert.h"

U_NAMESPACE_BEGIN

int64_t
CollationRootElements::lastCEWithPrimaryBefore(uint32_t p) const {
    if(p == 0) { return 0; }
    U_ASSERT(p > elements[elements[IX_FIRST_PRIMARY_INDEX]]);
    int32_t index = findP(p);
    uint32_t q = elements[index];
    uint32_t secTer;
    if(p == (q & 0xffffff00)) {
        // p == elements[index] is a root primary. Find the CE before it.
        // We must not be in a primary range.
        U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
        secTer = elements[index - 1];
        if((secTer & SEC_TER_DELTA_FLAG) == 0) {
            // Primary CE just before p.
            p = secTer & 0xffffff00;
            secTer = Collation::COMMON_SEC_AND_TER_CE;
        } else {
            // secTer = last secondary & tertiary for the previous primary
            index -= 2;
            for(;;) {
                p = elements[index];
                if((p & SEC_TER_DELTA_FLAG) == 0) {
                    p &= 0xffffff00;
                    break;
                }
                --index;
            }
        }
    } else {
        // p > elements[index] which is the previous primary.
        // Find the last secondary & tertiary weights for it.
        p = q & 0xffffff00;
        secTer = Collation::COMMON_SEC_AND_TER_CE;
        for(;;) {
            q = elements[++index];
            if((q & SEC_TER_DELTA_FLAG) == 0) {
                // We must not be in a primary range.
                U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
                break;
            }
            secTer = q;
        }
    }
    return ((int64_t)p << 32) | (secTer & ~SEC_TER_DELTA_FLAG);
}

int64_t
CollationRootElements::firstCEWithPrimaryAtLeast(uint32_t p) const {
    if(p == 0) { return 0; }
    int32_t index = findP(p);
    if(p != (elements[index] & 0xffffff00)) {
        for(;;) {
            p = elements[++index];
            if((p & SEC_TER_DELTA_FLAG) == 0) {
                // First primary after p. We must not be in a primary range.
                U_ASSERT((p & PRIMARY_STEP_MASK) == 0);
                break;
            }
        }
    }
    // The code above guarantees that p has at most 3 bytes: (p & 0xff) == 0.
    return ((int64_t)p << 32) | Collation::COMMON_SEC_AND_TER_CE;
}

uint32_t
CollationRootElements::getPrimaryBefore(uint32_t p, UBool isCompressible) const {
    int32_t index = findPrimary(p);
    int32_t step;
    uint32_t q = elements[index];
    if(p == (q & 0xffffff00)) {
        // Found p itself. Return the previous primary.
        // See if p is at the end of a previous range.
        step = (int32_t)q & PRIMARY_STEP_MASK;
        if(step == 0) {
            // p is not at the end of a range. Look for the previous primary.
            do {
                p = elements[--index];
            } while((p & SEC_TER_DELTA_FLAG) != 0);
            return p & 0xffffff00;
        }
    } else {
        // p is in a range, and not at the start.
        uint32_t nextElement = elements[index + 1];
        U_ASSERT(isEndOfPrimaryRange(nextElement));
        step = (int32_t)nextElement & PRIMARY_STEP_MASK;
    }
    // Return the previous range primary.
    if((p & 0xffff) == 0) {
        return Collation::decTwoBytePrimaryByOneStep(p, isCompressible, step);
    } else {
        return Collation::decThreeBytePrimaryByOneStep(p, isCompressible, step);
    }
}

uint32_t
CollationRootElements::getSecondaryBefore(uint32_t p, uint32_t s) const {
    int32_t index;
    uint32_t previousSec, sec;
    if(p == 0) {
        index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
        // Gap at the beginning of the secondary CE range.
        previousSec = 0;
        sec = elements[index] >> 16;
    } else {
        index = findPrimary(p) + 1;
        previousSec = Collation::MERGE_SEPARATOR_WEIGHT16;
        sec = Collation::COMMON_WEIGHT16;
    }
    U_ASSERT(s >= sec);
    while(s > sec) {
        previousSec = sec;
        U_ASSERT((elements[index] & SEC_TER_DELTA_FLAG) != 0);
        sec = elements[index++] >> 16;
    }
    U_ASSERT(sec == s);
    return previousSec;
}

uint32_t
CollationRootElements::getTertiaryBefore(uint32_t p, uint32_t s, uint32_t t) const {
    U_ASSERT((t & ~Collation::ONLY_TERTIARY_MASK) == 0);
    int32_t index;
    uint32_t previousTer, secTer;
    if(p == 0) {
        if(s == 0) {
            index = (int32_t)elements[IX_FIRST_TERTIARY_INDEX];
            // Gap at the beginning of the tertiary CE range.
            previousTer = 0;
        } else {
            index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
            previousTer = Collation::MERGE_SEPARATOR_WEIGHT16;
        }
        secTer = elements[index] & ~SEC_TER_DELTA_FLAG;
    } else {
        index = findPrimary(p) + 1;
        previousTer = Collation::MERGE_SEPARATOR_WEIGHT16;
        secTer = Collation::COMMON_SEC_AND_TER_CE;
    }
    uint32_t st = (s << 16) | t;
    while(st > secTer) {
        if((secTer >> 16) == s) { previousTer = secTer; }
        U_ASSERT((elements[index] & SEC_TER_DELTA_FLAG) != 0);
        secTer = elements[index++] & ~SEC_TER_DELTA_FLAG;
    }
    U_ASSERT(secTer == st);
    return previousTer & 0xffff;
}

uint32_t
CollationRootElements::getPrimaryAfter(uint32_t p, int32_t index, UBool isCompressible) const {
    U_ASSERT(p == (elements[index] & 0xffffff00) || isEndOfPrimaryRange(elements[index + 1]));
    uint32_t q = elements[++index];
    int32_t step;
    if((q & SEC_TER_DELTA_FLAG) == 0 && (step = (int32_t)q & PRIMARY_STEP_MASK) != 0) {
        // Return the next primary in this range.
        if((p & 0xffff) == 0) {
            return Collation::incTwoBytePrimaryByOffset(p, isCompressible, step);
        } else {
            return Collation::incThreeBytePrimaryByOffset(p, isCompressible, step);
        }
    } else {
        // Return the next primary in the list.
        while((q & SEC_TER_DELTA_FLAG) != 0) {
            q = elements[++index];
        }
        U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
        return q;
    }
}

uint32_t
CollationRootElements::getSecondaryAfter(int32_t index, uint32_t s) const {
    uint32_t secLimit;
    if(index == 0) {
        // primary = 0
        index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
        // Gap at the end of the secondary CE range.
        secLimit = 0x10000;
    } else {
        U_ASSERT(index >= (int32_t)elements[IX_FIRST_PRIMARY_INDEX]);
        ++index;
        // Gap for secondaries of primary CEs.
        secLimit = getSecondaryBoundary();
    }
    for(;;) {
        uint32_t secTer = elements[index];
        if((secTer & SEC_TER_DELTA_FLAG) == 0) { return secLimit; }
        uint32_t sec = secTer >> 16;
        if(sec > s) { return sec; }
        ++index;
    }
}

uint32_t
CollationRootElements::getTertiaryAfter(int32_t index, uint32_t s, uint32_t t) const {
    uint32_t terLimit;
    if(index == 0) {
        // primary = 0
        if(s == 0) {
            index = (int32_t)elements[IX_FIRST_TERTIARY_INDEX];
            // Gap at the end of the tertiary CE range.
            terLimit = 0x4000;
        } else {
            index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
            // Gap for tertiaries of primary/secondary CEs.
            terLimit = getTertiaryBoundary();
        }
    } else {
        U_ASSERT(index >= (int32_t)elements[IX_FIRST_PRIMARY_INDEX]);
        ++index;
        terLimit = getTertiaryBoundary();
    }
    uint32_t st = (s << 16) | t;
    for(;;) {
        uint32_t secTer = elements[index];
        // No tertiary greater than t for this primary+secondary.
        if((secTer & SEC_TER_DELTA_FLAG) == 0 || (secTer >> 16) > s) { return terLimit; }
        secTer &= ~SEC_TER_DELTA_FLAG;
        if(secTer > st) { return secTer & 0xffff; }
        ++index;
    }
}

int32_t
CollationRootElements::findPrimary(uint32_t p) const {
    // Requirement: p must occur as a root primary.
    U_ASSERT((p & 0xff) == 0);  // at most a 3-byte primary
    int32_t index = findP(p);
    // If p is in a range, then we just assume that p is an actual primary in this range.
    // (Too cumbersome/expensive to check.)
    // Otherwise, it must be an exact match.
    U_ASSERT(isEndOfPrimaryRange(elements[index + 1]) || p == (elements[index] & 0xffffff00));
    return index;
}

int32_t
CollationRootElements::findP(uint32_t p) const {
    // p need not occur as a root primary.
    // For example, it might be a reordering group boundary.
    U_ASSERT((p >> 24) != Collation::UNASSIGNED_IMPLICIT_BYTE);
    // modified binary search
    int32_t start = (int32_t)elements[IX_FIRST_PRIMARY_INDEX];
    U_ASSERT(p >= elements[start]);
    int32_t limit = length - 1;
    U_ASSERT(elements[limit] >= PRIMARY_SENTINEL);
    U_ASSERT(p < elements[limit]);
    while((start + 1) < limit) {
        // Invariant: elements[start] and elements[limit] are primaries,
        // and elements[start]<=p<=elements[limit].
        int32_t i = (start + limit) / 2;
        uint32_t q = elements[i];
        if((q & SEC_TER_DELTA_FLAG) != 0) {
            // Find the next primary.
            int32_t j = i + 1;
            for(;;) {
                if(j == limit) { break; }
                q = elements[j];
                if((q & SEC_TER_DELTA_FLAG) == 0) {
                    i = j;
                    break;
                }
                ++j;
            }
            if((q & SEC_TER_DELTA_FLAG) != 0) {
                // Find the preceding primary.
                j = i - 1;
                for(;;) {
                    if(j == start) { break; }
                    q = elements[j];
                    if((q & SEC_TER_DELTA_FLAG) == 0) {
                        i = j;
                        break;
                    }
                    --j;
                }
                if((q & SEC_TER_DELTA_FLAG) != 0) {
                    // No primary between start and limit.
                    break;
                }
            }
        }
        if(p < (q & 0xffffff00)) {  // Reset the "step" bits of a range end primary.
            limit = i;
        } else {
            start = i;
        }
    }
    return start;
}

U_NAMESPACE_END

#endif  // !UCONFIG_NO_COLLATION
Commit	Line	Data
57a6839d A	1	/*
	2	*******************************************************************************
	3	* Copyright (C) 2013-2014, International Business Machines
	4	* Corporation and others. All Rights Reserved.
	5	*******************************************************************************
	6	* collationrootelements.cpp
	7	*
	8	* created on: 2013mar05
	9	* created by: Markus W. Scherer
	10	*/
	11
	12	#include "unicode/utypes.h"
	13
	14	#if !UCONFIG_NO_COLLATION
	15
	16	#include "collation.h"
	17	#include "collationrootelements.h"
	18	#include "uassert.h"
	19
	20	U_NAMESPACE_BEGIN
	21
	22	int64_t
	23	CollationRootElements::lastCEWithPrimaryBefore(uint32_t p) const {
	24	if(p == 0) { return 0; }
	25	U_ASSERT(p > elements[elements[IX_FIRST_PRIMARY_INDEX]]);
	26	int32_t index = findP(p);
	27	uint32_t q = elements[index];
	28	uint32_t secTer;
	29	if(p == (q & 0xffffff00)) {
	30	// p == elements[index] is a root primary. Find the CE before it.
	31	// We must not be in a primary range.
	32	U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
	33	secTer = elements[index - 1];
	34	if((secTer & SEC_TER_DELTA_FLAG) == 0) {
	35	// Primary CE just before p.
	36	p = secTer & 0xffffff00;
	37	secTer = Collation::COMMON_SEC_AND_TER_CE;
	38	} else {
	39	// secTer = last secondary & tertiary for the previous primary
	40	index -= 2;
	41	for(;;) {
	42	p = elements[index];
	43	if((p & SEC_TER_DELTA_FLAG) == 0) {
	44	p &= 0xffffff00;
	45	break;
	46	}
	47	--index;
	48	}
	49	}
	50	} else {
	51	// p > elements[index] which is the previous primary.
	52	// Find the last secondary & tertiary weights for it.
	53	p = q & 0xffffff00;
	54	secTer = Collation::COMMON_SEC_AND_TER_CE;
	55	for(;;) {
	56	q = elements[++index];
	57	if((q & SEC_TER_DELTA_FLAG) == 0) {
	58	// We must not be in a primary range.
	59	U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
	60	break;
	61	}
	62	secTer = q;
	63	}
	64	}
65	return ((int64_t)p << 32) \| (secTer & ~SEC_TER_DELTA_FLAG);
66	}
67
68	int64_t
69	CollationRootElements::firstCEWithPrimaryAtLeast(uint32_t p) const {
70	if(p == 0) { return 0; }
71	int32_t index = findP(p);
72	if(p != (elements[index] & 0xffffff00)) {
73	for(;;) {
74	p = elements[++index];
75	if((p & SEC_TER_DELTA_FLAG) == 0) {
76	// First primary after p. We must not be in a primary range.
77	U_ASSERT((p & PRIMARY_STEP_MASK) == 0);
78	break;
79	}
80	}
81	}
82	// The code above guarantees that p has at most 3 bytes: (p & 0xff) == 0.
83	return ((int64_t)p << 32) \| Collation::COMMON_SEC_AND_TER_CE;
84	}
85
86	uint32_t
87	CollationRootElements::getPrimaryBefore(uint32_t p, UBool isCompressible) const {
88	int32_t index = findPrimary(p);
89	int32_t step;
90	uint32_t q = elements[index];
91	if(p == (q & 0xffffff00)) {
92	// Found p itself. Return the previous primary.
93	// See if p is at the end of a previous range.
94	step = (int32_t)q & PRIMARY_STEP_MASK;
95	if(step == 0) {
96	// p is not at the end of a range. Look for the previous primary.
97	do {
98	p = elements[--index];
99	} while((p & SEC_TER_DELTA_FLAG) != 0);
100	return p & 0xffffff00;
101	}
102	} else {
103	// p is in a range, and not at the start.
104	uint32_t nextElement = elements[index + 1];
105	U_ASSERT(isEndOfPrimaryRange(nextElement));
106	step = (int32_t)nextElement & PRIMARY_STEP_MASK;
107	}
108	// Return the previous range primary.
109	if((p & 0xffff) == 0) {
110	return Collation::decTwoBytePrimaryByOneStep(p, isCompressible, step);
111	} else {
112	return Collation::decThreeBytePrimaryByOneStep(p, isCompressible, step);
113	}
114	}
115
116	uint32_t
117	CollationRootElements::getSecondaryBefore(uint32_t p, uint32_t s) const {
118	int32_t index;
119	uint32_t previousSec, sec;
120	if(p == 0) {
121	index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
122	// Gap at the beginning of the secondary CE range.
123	previousSec = 0;
124	sec = elements[index] >> 16;
125	} else {
126	index = findPrimary(p) + 1;
127	previousSec = Collation::MERGE_SEPARATOR_WEIGHT16;
128	sec = Collation::COMMON_WEIGHT16;
129	}
130	U_ASSERT(s >= sec);
131	while(s > sec) {
132	previousSec = sec;
133	U_ASSERT((elements[index] & SEC_TER_DELTA_FLAG) != 0);
134	sec = elements[index++] >> 16;
135	}
136	U_ASSERT(sec == s);
137	return previousSec;
138	}
139
140	uint32_t
141	CollationRootElements::getTertiaryBefore(uint32_t p, uint32_t s, uint32_t t) const {
142	U_ASSERT((t & ~Collation::ONLY_TERTIARY_MASK) == 0);
143	int32_t index;
144	uint32_t previousTer, secTer;
145	if(p == 0) {
146	if(s == 0) {
147	index = (int32_t)elements[IX_FIRST_TERTIARY_INDEX];
148	// Gap at the beginning of the tertiary CE range.
149	previousTer = 0;
150	} else {
151	index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
152	previousTer = Collation::MERGE_SEPARATOR_WEIGHT16;
153	}
154	secTer = elements[index] & ~SEC_TER_DELTA_FLAG;
155	} else {
156	index = findPrimary(p) + 1;
157	previousTer = Collation::MERGE_SEPARATOR_WEIGHT16;
158	secTer = Collation::COMMON_SEC_AND_TER_CE;
159	}
160	uint32_t st = (s << 16) \| t;
161	while(st > secTer) {
162	if((secTer >> 16) == s) { previousTer = secTer; }
163	U_ASSERT((elements[index] & SEC_TER_DELTA_FLAG) != 0);
164	secTer = elements[index++] & ~SEC_TER_DELTA_FLAG;
165	}
166	U_ASSERT(secTer == st);
167	return previousTer & 0xffff;
168	}
169
170	uint32_t
171	CollationRootElements::getPrimaryAfter(uint32_t p, int32_t index, UBool isCompressible) const {
172	U_ASSERT(p == (elements[index] & 0xffffff00) \|\| isEndOfPrimaryRange(elements[index + 1]));
173	uint32_t q = elements[++index];
174	int32_t step;
175	if((q & SEC_TER_DELTA_FLAG) == 0 && (step = (int32_t)q & PRIMARY_STEP_MASK) != 0) {
176	// Return the next primary in this range.
177	if((p & 0xffff) == 0) {
178	return Collation::incTwoBytePrimaryByOffset(p, isCompressible, step);
179	} else {
180	return Collation::incThreeBytePrimaryByOffset(p, isCompressible, step);
181	}
182	} else {
183	// Return the next primary in the list.
184	while((q & SEC_TER_DELTA_FLAG) != 0) {
185	q = elements[++index];
186	}
187	U_ASSERT((q & PRIMARY_STEP_MASK) == 0);
188	return q;
189	}
190	}
191
192	uint32_t
193	CollationRootElements::getSecondaryAfter(int32_t index, uint32_t s) const {
194	uint32_t secLimit;
195	if(index == 0) {
196	// primary = 0
197	index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
198	// Gap at the end of the secondary CE range.
199	secLimit = 0x10000;
200	} else {
201	U_ASSERT(index >= (int32_t)elements[IX_FIRST_PRIMARY_INDEX]);
202	++index;
203	// Gap for secondaries of primary CEs.
204	secLimit = getSecondaryBoundary();
205	}
206	for(;;) {
207	uint32_t secTer = elements[index];
208	if((secTer & SEC_TER_DELTA_FLAG) == 0) { return secLimit; }
209	uint32_t sec = secTer >> 16;
210	if(sec > s) { return sec; }
211	++index;
212	}
213	}
214
215	uint32_t
216	CollationRootElements::getTertiaryAfter(int32_t index, uint32_t s, uint32_t t) const {
217	uint32_t terLimit;
218	if(index == 0) {
219	// primary = 0
220	if(s == 0) {
221	index = (int32_t)elements[IX_FIRST_TERTIARY_INDEX];
222	// Gap at the end of the tertiary CE range.
223	terLimit = 0x4000;
224	} else {
225	index = (int32_t)elements[IX_FIRST_SECONDARY_INDEX];
226	// Gap for tertiaries of primary/secondary CEs.
227	terLimit = getTertiaryBoundary();
228	}
229	} else {
230	U_ASSERT(index >= (int32_t)elements[IX_FIRST_PRIMARY_INDEX]);
231	++index;
232	terLimit = getTertiaryBoundary();
233	}
234	uint32_t st = (s << 16) \| t;
235	for(;;) {
236	uint32_t secTer = elements[index];
237	// No tertiary greater than t for this primary+secondary.
238	if((secTer & SEC_TER_DELTA_FLAG) == 0 \|\| (secTer >> 16) > s) { return terLimit; }
239	secTer &= ~SEC_TER_DELTA_FLAG;
240	if(secTer > st) { return secTer & 0xffff; }
241	++index;
242	}
243	}
244
245	int32_t
246	CollationRootElements::findPrimary(uint32_t p) const {
247	// Requirement: p must occur as a root primary.
248	U_ASSERT((p & 0xff) == 0); // at most a 3-byte primary
249	int32_t index = findP(p);
250	// If p is in a range, then we just assume that p is an actual primary in this range.
251	// (Too cumbersome/expensive to check.)
252	// Otherwise, it must be an exact match.
253	U_ASSERT(isEndOfPrimaryRange(elements[index + 1]) \|\| p == (elements[index] & 0xffffff00));
254	return index;
255	}
256
257	int32_t
258	CollationRootElements::findP(uint32_t p) const {
259	// p need not occur as a root primary.
260	// For example, it might be a reordering group boundary.
261	U_ASSERT((p >> 24) != Collation::UNASSIGNED_IMPLICIT_BYTE);
262	// modified binary search
263	int32_t start = (int32_t)elements[IX_FIRST_PRIMARY_INDEX];
264	U_ASSERT(p >= elements[start]);
265	int32_t limit = length - 1;
266	U_ASSERT(elements[limit] >= PRIMARY_SENTINEL);
267	U_ASSERT(p < elements[limit]);
268	while((start + 1) < limit) {
269	// Invariant: elements[start] and elements[limit] are primaries,
270	// and elements[start]<=p<=elements[limit].
271	int32_t i = (start + limit) / 2;
272	uint32_t q = elements[i];
273	if((q & SEC_TER_DELTA_FLAG) != 0) {
274	// Find the next primary.
275	int32_t j = i + 1;
276	for(;;) {
277	if(j == limit) { break; }
278	q = elements[j];
279	if((q & SEC_TER_DELTA_FLAG) == 0) {
280	i = j;
281	break;
282	}
283	++j;
284	}
285	if((q & SEC_TER_DELTA_FLAG) != 0) {
286	// Find the preceding primary.
287	j = i - 1;
288	for(;;) {
289	if(j == start) { break; }
290	q = elements[j];
291	if((q & SEC_TER_DELTA_FLAG) == 0) {
292	i = j;
293	break;
294	}
295	--j;
296	}
297	if((q & SEC_TER_DELTA_FLAG) != 0) {
298	// No primary between start and limit.
299	break;
300	}
301	}
302	}
303	if(p < (q & 0xffffff00)) { // Reset the "step" bits of a range end primary.
304	limit = i;
305	} else {
306	start = i;
307	}
308	}
309	return start;
310	}
311
312	U_NAMESPACE_END
313
314	#endif // !UCONFIG_NO_COLLATION