J. Duke | 319a3b9 | 2007-12-01 00:00:00 +0000 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved. |
| 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 | * |
| 5 | * This code is free software; you can redistribute it and/or modify it |
| 6 | * under the terms of the GNU General Public License version 2 only, as |
| 7 | * published by the Free Software Foundation. Sun designates this |
| 8 | * particular file as subject to the "Classpath" exception as provided |
| 9 | * by Sun in the LICENSE file that accompanied this code. |
| 10 | * |
| 11 | * This code is distributed in the hope that it will be useful, but WITHOUT |
| 12 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 13 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| 14 | * version 2 for more details (a copy is included in the LICENSE file that |
| 15 | * accompanied this code). |
| 16 | * |
| 17 | * You should have received a copy of the GNU General Public License version |
| 18 | * 2 along with this work; if not, write to the Free Software Foundation, |
| 19 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| 20 | * |
| 21 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| 22 | * CA 95054 USA or visit www.sun.com if you need additional information or |
| 23 | * have any questions. |
| 24 | */ |
| 25 | |
| 26 | /* |
| 27 | * (C) Copyright Taligent, Inc. 1996, 1997 - All Rights Reserved |
| 28 | * (C) Copyright IBM Corp. 1996-1998 - All Rights Reserved |
| 29 | * |
| 30 | * The original version of this source code and documentation is copyrighted |
| 31 | * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These |
| 32 | * materials are provided under terms of a License Agreement between Taligent |
| 33 | * and Sun. This technology is protected by multiple US and International |
| 34 | * patents. This notice and attribution to Taligent may not be removed. |
| 35 | * Taligent is a registered trademark of Taligent, Inc. |
| 36 | * |
| 37 | */ |
| 38 | |
| 39 | package java.text; |
| 40 | |
| 41 | import java.text.Normalizer; |
| 42 | import java.util.Vector; |
| 43 | import java.util.Locale; |
| 44 | |
| 45 | /** |
| 46 | * The <code>RuleBasedCollator</code> class is a concrete subclass of |
| 47 | * <code>Collator</code> that provides a simple, data-driven, table |
| 48 | * collator. With this class you can create a customized table-based |
| 49 | * <code>Collator</code>. <code>RuleBasedCollator</code> maps |
| 50 | * characters to sort keys. |
| 51 | * |
| 52 | * <p> |
| 53 | * <code>RuleBasedCollator</code> has the following restrictions |
| 54 | * for efficiency (other subclasses may be used for more complex languages) : |
| 55 | * <ol> |
| 56 | * <li>If a special collation rule controlled by a <modifier> is |
| 57 | specified it applies to the whole collator object. |
| 58 | * <li>All non-mentioned characters are at the end of the |
| 59 | * collation order. |
| 60 | * </ol> |
| 61 | * |
| 62 | * <p> |
| 63 | * The collation table is composed of a list of collation rules, where each |
| 64 | * rule is of one of three forms: |
| 65 | * <pre> |
| 66 | * <modifier> |
| 67 | * <relation> <text-argument> |
| 68 | * <reset> <text-argument> |
| 69 | * </pre> |
| 70 | * The definitions of the rule elements is as follows: |
| 71 | * <UL Type=disc> |
| 72 | * <LI><strong>Text-Argument</strong>: A text-argument is any sequence of |
| 73 | * characters, excluding special characters (that is, common |
| 74 | * whitespace characters [0009-000D, 0020] and rule syntax characters |
| 75 | * [0021-002F, 003A-0040, 005B-0060, 007B-007E]). If those |
| 76 | * characters are desired, you can put them in single quotes |
| 77 | * (e.g. ampersand => '&'). Note that unquoted white space characters |
| 78 | * are ignored; e.g. <code>b c</code> is treated as <code>bc</code>. |
| 79 | * <LI><strong>Modifier</strong>: There are currently two modifiers that |
| 80 | * turn on special collation rules. |
| 81 | * <UL Type=square> |
| 82 | * <LI>'@' : Turns on backwards sorting of accents (secondary |
| 83 | * differences), as in French. |
| 84 | * <LI>'!' : Turns on Thai/Lao vowel-consonant swapping. If this |
| 85 | * rule is in force when a Thai vowel of the range |
| 86 | * \U0E40-\U0E44 precedes a Thai consonant of the range |
| 87 | * \U0E01-\U0E2E OR a Lao vowel of the range \U0EC0-\U0EC4 |
| 88 | * precedes a Lao consonant of the range \U0E81-\U0EAE then |
| 89 | * the vowel is placed after the consonant for collation |
| 90 | * purposes. |
| 91 | * </UL> |
| 92 | * <p>'@' : Indicates that accents are sorted backwards, as in French. |
| 93 | * <LI><strong>Relation</strong>: The relations are the following: |
| 94 | * <UL Type=square> |
| 95 | * <LI>'<' : Greater, as a letter difference (primary) |
| 96 | * <LI>';' : Greater, as an accent difference (secondary) |
| 97 | * <LI>',' : Greater, as a case difference (tertiary) |
| 98 | * <LI>'=' : Equal |
| 99 | * </UL> |
| 100 | * <LI><strong>Reset</strong>: There is a single reset |
| 101 | * which is used primarily for contractions and expansions, but which |
| 102 | * can also be used to add a modification at the end of a set of rules. |
| 103 | * <p>'&' : Indicates that the next rule follows the position to where |
| 104 | * the reset text-argument would be sorted. |
| 105 | * </UL> |
| 106 | * |
| 107 | * <p> |
| 108 | * This sounds more complicated than it is in practice. For example, the |
| 109 | * following are equivalent ways of expressing the same thing: |
| 110 | * <blockquote> |
| 111 | * <pre> |
| 112 | * a < b < c |
| 113 | * a < b & b < c |
| 114 | * a < c & a < b |
| 115 | * </pre> |
| 116 | * </blockquote> |
| 117 | * Notice that the order is important, as the subsequent item goes immediately |
| 118 | * after the text-argument. The following are not equivalent: |
| 119 | * <blockquote> |
| 120 | * <pre> |
| 121 | * a < b & a < c |
| 122 | * a < c & a < b |
| 123 | * </pre> |
| 124 | * </blockquote> |
| 125 | * Either the text-argument must already be present in the sequence, or some |
| 126 | * initial substring of the text-argument must be present. (e.g. "a < b & ae < |
| 127 | * e" is valid since "a" is present in the sequence before "ae" is reset). In |
| 128 | * this latter case, "ae" is not entered and treated as a single character; |
| 129 | * instead, "e" is sorted as if it were expanded to two characters: "a" |
| 130 | * followed by an "e". This difference appears in natural languages: in |
| 131 | * traditional Spanish "ch" is treated as though it contracts to a single |
| 132 | * character (expressed as "c < ch < d"), while in traditional German |
| 133 | * a-umlaut is treated as though it expanded to two characters |
| 134 | * (expressed as "a,A < b,B ... &ae;\u00e3&AE;\u00c3"). |
| 135 | * [\u00e3 and \u00c3 are, of course, the escape sequences for a-umlaut.] |
| 136 | * <p> |
| 137 | * <strong>Ignorable Characters</strong> |
| 138 | * <p> |
| 139 | * For ignorable characters, the first rule must start with a relation (the |
| 140 | * examples we have used above are really fragments; "a < b" really should be |
| 141 | * "< a < b"). If, however, the first relation is not "<", then all the all |
| 142 | * text-arguments up to the first "<" are ignorable. For example, ", - < a < b" |
| 143 | * makes "-" an ignorable character, as we saw earlier in the word |
| 144 | * "black-birds". In the samples for different languages, you see that most |
| 145 | * accents are ignorable. |
| 146 | * |
| 147 | * <p><strong>Normalization and Accents</strong> |
| 148 | * <p> |
| 149 | * <code>RuleBasedCollator</code> automatically processes its rule table to |
| 150 | * include both pre-composed and combining-character versions of |
| 151 | * accented characters. Even if the provided rule string contains only |
| 152 | * base characters and separate combining accent characters, the pre-composed |
| 153 | * accented characters matching all canonical combinations of characters from |
| 154 | * the rule string will be entered in the table. |
| 155 | * <p> |
| 156 | * This allows you to use a RuleBasedCollator to compare accented strings |
| 157 | * even when the collator is set to NO_DECOMPOSITION. There are two caveats, |
| 158 | * however. First, if the strings to be collated contain combining |
| 159 | * sequences that may not be in canonical order, you should set the collator to |
| 160 | * CANONICAL_DECOMPOSITION or FULL_DECOMPOSITION to enable sorting of |
| 161 | * combining sequences. Second, if the strings contain characters with |
| 162 | * compatibility decompositions (such as full-width and half-width forms), |
| 163 | * you must use FULL_DECOMPOSITION, since the rule tables only include |
| 164 | * canonical mappings. |
| 165 | * |
| 166 | * <p><strong>Errors</strong> |
| 167 | * <p> |
| 168 | * The following are errors: |
| 169 | * <UL Type=disc> |
| 170 | * <LI>A text-argument contains unquoted punctuation symbols |
| 171 | * (e.g. "a < b-c < d"). |
| 172 | * <LI>A relation or reset character not followed by a text-argument |
| 173 | * (e.g. "a < ,b"). |
| 174 | * <LI>A reset where the text-argument (or an initial substring of the |
| 175 | * text-argument) is not already in the sequence. |
| 176 | * (e.g. "a < b & e < f") |
| 177 | * </UL> |
| 178 | * If you produce one of these errors, a <code>RuleBasedCollator</code> throws |
| 179 | * a <code>ParseException</code>. |
| 180 | * |
| 181 | * <p><strong>Examples</strong> |
| 182 | * <p>Simple: "< a < b < c < d" |
| 183 | * <p>Norwegian: "< a,A< b,B< c,C< d,D< e,E< f,F< g,G< h,H< i,I< j,J |
| 184 | * < k,K< l,L< m,M< n,N< o,O< p,P< q,Q< r,R< s,S< t,T |
| 185 | * < u,U< v,V< w,W< x,X< y,Y< z,Z |
| 186 | * < \u00E5=a\u030A,\u00C5=A\u030A |
| 187 | * ;aa,AA< \u00E6,\u00C6< \u00F8,\u00D8" |
| 188 | * |
| 189 | * <p> |
| 190 | * To create a <code>RuleBasedCollator</code> object with specialized |
| 191 | * rules tailored to your needs, you construct the <code>RuleBasedCollator</code> |
| 192 | * with the rules contained in a <code>String</code> object. For example: |
| 193 | * <blockquote> |
| 194 | * <pre> |
| 195 | * String simple = "< a< b< c< d"; |
| 196 | * RuleBasedCollator mySimple = new RuleBasedCollator(simple); |
| 197 | * </pre> |
| 198 | * </blockquote> |
| 199 | * Or: |
| 200 | * <blockquote> |
| 201 | * <pre> |
| 202 | * String Norwegian = "< a,A< b,B< c,C< d,D< e,E< f,F< g,G< h,H< i,I< j,J" + |
| 203 | * "< k,K< l,L< m,M< n,N< o,O< p,P< q,Q< r,R< s,S< t,T" + |
| 204 | * "< u,U< v,V< w,W< x,X< y,Y< z,Z" + |
| 205 | * "< \u00E5=a\u030A,\u00C5=A\u030A" + |
| 206 | * ";aa,AA< \u00E6,\u00C6< \u00F8,\u00D8"; |
| 207 | * RuleBasedCollator myNorwegian = new RuleBasedCollator(Norwegian); |
| 208 | * </pre> |
| 209 | * </blockquote> |
| 210 | * |
| 211 | * <p> |
| 212 | * A new collation rules string can be created by concatenating rules |
| 213 | * strings. For example, the rules returned by {@link #getRules()} could |
| 214 | * be concatenated to combine multiple <code>RuleBasedCollator</code>s. |
| 215 | * |
| 216 | * <p> |
| 217 | * The following example demonstrates how to change the order of |
| 218 | * non-spacing accents, |
| 219 | * <blockquote> |
| 220 | * <pre> |
| 221 | * // old rule |
| 222 | * String oldRules = "=\u0301;\u0300;\u0302;\u0308" // main accents |
| 223 | * + ";\u0327;\u0303;\u0304;\u0305" // main accents |
| 224 | * + ";\u0306;\u0307;\u0309;\u030A" // main accents |
| 225 | * + ";\u030B;\u030C;\u030D;\u030E" // main accents |
| 226 | * + ";\u030F;\u0310;\u0311;\u0312" // main accents |
| 227 | * + "< a , A ; ae, AE ; \u00e6 , \u00c6" |
| 228 | * + "< b , B < c, C < e, E & C < d, D"; |
| 229 | * // change the order of accent characters |
| 230 | * String addOn = "& \u0300 ; \u0308 ; \u0302"; |
| 231 | * RuleBasedCollator myCollator = new RuleBasedCollator(oldRules + addOn); |
| 232 | * </pre> |
| 233 | * </blockquote> |
| 234 | * |
| 235 | * @see Collator |
| 236 | * @see CollationElementIterator |
| 237 | * @author Helena Shih, Laura Werner, Richard Gillam |
| 238 | */ |
| 239 | public class RuleBasedCollator extends Collator{ |
| 240 | // IMPLEMENTATION NOTES: The implementation of the collation algorithm is |
| 241 | // divided across three classes: RuleBasedCollator, RBCollationTables, and |
| 242 | // CollationElementIterator. RuleBasedCollator contains the collator's |
| 243 | // transient state and includes the code that uses the other classes to |
| 244 | // implement comparison and sort-key building. RuleBasedCollator also |
| 245 | // contains the logic to handle French secondary accent sorting. |
| 246 | // A RuleBasedCollator has two CollationElementIterators. State doesn't |
| 247 | // need to be preserved in these objects between calls to compare() or |
| 248 | // getCollationKey(), but the objects persist anyway to avoid wasting extra |
| 249 | // creation time. compare() and getCollationKey() are synchronized to ensure |
| 250 | // thread safety with this scheme. The CollationElementIterator is responsible |
| 251 | // for generating collation elements from strings and returning one element at |
| 252 | // a time (sometimes there's a one-to-many or many-to-one mapping between |
| 253 | // characters and collation elements-- this class handles that). |
| 254 | // CollationElementIterator depends on RBCollationTables, which contains the |
| 255 | // collator's static state. RBCollationTables contains the actual data |
| 256 | // tables specifying the collation order of characters for a particular locale |
| 257 | // or use. It also contains the base logic that CollationElementIterator |
| 258 | // uses to map from characters to collation elements. A single RBCollationTables |
| 259 | // object is shared among all RuleBasedCollators for the same locale, and |
| 260 | // thus by all the CollationElementIterators they create. |
| 261 | |
| 262 | /** |
| 263 | * RuleBasedCollator constructor. This takes the table rules and builds |
| 264 | * a collation table out of them. Please see RuleBasedCollator class |
| 265 | * description for more details on the collation rule syntax. |
| 266 | * @see java.util.Locale |
| 267 | * @param rules the collation rules to build the collation table from. |
| 268 | * @exception ParseException A format exception |
| 269 | * will be thrown if the build process of the rules fails. For |
| 270 | * example, build rule "a < ? < d" will cause the constructor to |
| 271 | * throw the ParseException because the '?' is not quoted. |
| 272 | */ |
| 273 | public RuleBasedCollator(String rules) throws ParseException { |
| 274 | this(rules, Collator.CANONICAL_DECOMPOSITION); |
| 275 | } |
| 276 | |
| 277 | /** |
| 278 | * RuleBasedCollator constructor. This takes the table rules and builds |
| 279 | * a collation table out of them. Please see RuleBasedCollator class |
| 280 | * description for more details on the collation rule syntax. |
| 281 | * @see java.util.Locale |
| 282 | * @param rules the collation rules to build the collation table from. |
| 283 | * @param decomp the decomposition strength used to build the |
| 284 | * collation table and to perform comparisons. |
| 285 | * @exception ParseException A format exception |
| 286 | * will be thrown if the build process of the rules fails. For |
| 287 | * example, build rule "a < ? < d" will cause the constructor to |
| 288 | * throw the ParseException because the '?' is not quoted. |
| 289 | */ |
| 290 | RuleBasedCollator(String rules, int decomp) throws ParseException { |
| 291 | setStrength(Collator.TERTIARY); |
| 292 | setDecomposition(decomp); |
| 293 | tables = new RBCollationTables(rules, decomp); |
| 294 | } |
| 295 | |
| 296 | /** |
| 297 | * "Copy constructor." Used in clone() for performance. |
| 298 | */ |
| 299 | private RuleBasedCollator(RuleBasedCollator that) { |
| 300 | setStrength(that.getStrength()); |
| 301 | setDecomposition(that.getDecomposition()); |
| 302 | tables = that.tables; |
| 303 | } |
| 304 | |
| 305 | /** |
| 306 | * Gets the table-based rules for the collation object. |
| 307 | * @return returns the collation rules that the table collation object |
| 308 | * was created from. |
| 309 | */ |
| 310 | public String getRules() |
| 311 | { |
| 312 | return tables.getRules(); |
| 313 | } |
| 314 | |
| 315 | /** |
| 316 | * Return a CollationElementIterator for the given String. |
| 317 | * @see java.text.CollationElementIterator |
| 318 | */ |
| 319 | public CollationElementIterator getCollationElementIterator(String source) { |
| 320 | return new CollationElementIterator( source, this ); |
| 321 | } |
| 322 | |
| 323 | /** |
| 324 | * Return a CollationElementIterator for the given String. |
| 325 | * @see java.text.CollationElementIterator |
| 326 | * @since 1.2 |
| 327 | */ |
| 328 | public CollationElementIterator getCollationElementIterator( |
| 329 | CharacterIterator source) { |
| 330 | return new CollationElementIterator( source, this ); |
| 331 | } |
| 332 | |
| 333 | /** |
| 334 | * Compares the character data stored in two different strings based on the |
| 335 | * collation rules. Returns information about whether a string is less |
| 336 | * than, greater than or equal to another string in a language. |
| 337 | * This can be overriden in a subclass. |
| 338 | */ |
| 339 | public synchronized int compare(String source, String target) |
| 340 | { |
| 341 | // The basic algorithm here is that we use CollationElementIterators |
| 342 | // to step through both the source and target strings. We compare each |
| 343 | // collation element in the source string against the corresponding one |
| 344 | // in the target, checking for differences. |
| 345 | // |
| 346 | // If a difference is found, we set <result> to LESS or GREATER to |
| 347 | // indicate whether the source string is less or greater than the target. |
| 348 | // |
| 349 | // However, it's not that simple. If we find a tertiary difference |
| 350 | // (e.g. 'A' vs. 'a') near the beginning of a string, it can be |
| 351 | // overridden by a primary difference (e.g. "A" vs. "B") later in |
| 352 | // the string. For example, "AA" < "aB", even though 'A' > 'a'. |
| 353 | // |
| 354 | // To keep track of this, we use strengthResult to keep track of the |
| 355 | // strength of the most significant difference that has been found |
| 356 | // so far. When we find a difference whose strength is greater than |
| 357 | // strengthResult, it overrides the last difference (if any) that |
| 358 | // was found. |
| 359 | |
| 360 | int result = Collator.EQUAL; |
| 361 | |
| 362 | if (sourceCursor == null) { |
| 363 | sourceCursor = getCollationElementIterator(source); |
| 364 | } else { |
| 365 | sourceCursor.setText(source); |
| 366 | } |
| 367 | if (targetCursor == null) { |
| 368 | targetCursor = getCollationElementIterator(target); |
| 369 | } else { |
| 370 | targetCursor.setText(target); |
| 371 | } |
| 372 | |
| 373 | int sOrder = 0, tOrder = 0; |
| 374 | |
| 375 | boolean initialCheckSecTer = getStrength() >= Collator.SECONDARY; |
| 376 | boolean checkSecTer = initialCheckSecTer; |
| 377 | boolean checkTertiary = getStrength() >= Collator.TERTIARY; |
| 378 | |
| 379 | boolean gets = true, gett = true; |
| 380 | |
| 381 | while(true) { |
| 382 | // Get the next collation element in each of the strings, unless |
| 383 | // we've been requested to skip it. |
| 384 | if (gets) sOrder = sourceCursor.next(); else gets = true; |
| 385 | if (gett) tOrder = targetCursor.next(); else gett = true; |
| 386 | |
| 387 | // If we've hit the end of one of the strings, jump out of the loop |
| 388 | if ((sOrder == CollationElementIterator.NULLORDER)|| |
| 389 | (tOrder == CollationElementIterator.NULLORDER)) |
| 390 | break; |
| 391 | |
| 392 | int pSOrder = CollationElementIterator.primaryOrder(sOrder); |
| 393 | int pTOrder = CollationElementIterator.primaryOrder(tOrder); |
| 394 | |
| 395 | // If there's no difference at this position, we can skip it |
| 396 | if (sOrder == tOrder) { |
| 397 | if (tables.isFrenchSec() && pSOrder != 0) { |
| 398 | if (!checkSecTer) { |
| 399 | // in french, a secondary difference more to the right is stronger, |
| 400 | // so accents have to be checked with each base element |
| 401 | checkSecTer = initialCheckSecTer; |
| 402 | // but tertiary differences are less important than the first |
| 403 | // secondary difference, so checking tertiary remains disabled |
| 404 | checkTertiary = false; |
| 405 | } |
| 406 | } |
| 407 | continue; |
| 408 | } |
| 409 | |
| 410 | // Compare primary differences first. |
| 411 | if ( pSOrder != pTOrder ) |
| 412 | { |
| 413 | if (sOrder == 0) { |
| 414 | // The entire source element is ignorable. |
| 415 | // Skip to the next source element, but don't fetch another target element. |
| 416 | gett = false; |
| 417 | continue; |
| 418 | } |
| 419 | if (tOrder == 0) { |
| 420 | gets = false; |
| 421 | continue; |
| 422 | } |
| 423 | |
| 424 | // The source and target elements aren't ignorable, but it's still possible |
| 425 | // for the primary component of one of the elements to be ignorable.... |
| 426 | |
| 427 | if (pSOrder == 0) // primary order in source is ignorable |
| 428 | { |
| 429 | // The source's primary is ignorable, but the target's isn't. We treat ignorables |
| 430 | // as a secondary difference, so remember that we found one. |
| 431 | if (checkSecTer) { |
| 432 | result = Collator.GREATER; // (strength is SECONDARY) |
| 433 | checkSecTer = false; |
| 434 | } |
| 435 | // Skip to the next source element, but don't fetch another target element. |
| 436 | gett = false; |
| 437 | } |
| 438 | else if (pTOrder == 0) |
| 439 | { |
| 440 | // record differences - see the comment above. |
| 441 | if (checkSecTer) { |
| 442 | result = Collator.LESS; // (strength is SECONDARY) |
| 443 | checkSecTer = false; |
| 444 | } |
| 445 | // Skip to the next source element, but don't fetch another target element. |
| 446 | gets = false; |
| 447 | } else { |
| 448 | // Neither of the orders is ignorable, and we already know that the primary |
| 449 | // orders are different because of the (pSOrder != pTOrder) test above. |
| 450 | // Record the difference and stop the comparison. |
| 451 | if (pSOrder < pTOrder) { |
| 452 | return Collator.LESS; // (strength is PRIMARY) |
| 453 | } else { |
| 454 | return Collator.GREATER; // (strength is PRIMARY) |
| 455 | } |
| 456 | } |
| 457 | } else { // else of if ( pSOrder != pTOrder ) |
| 458 | // primary order is the same, but complete order is different. So there |
| 459 | // are no base elements at this point, only ignorables (Since the strings are |
| 460 | // normalized) |
| 461 | |
| 462 | if (checkSecTer) { |
| 463 | // a secondary or tertiary difference may still matter |
| 464 | short secSOrder = CollationElementIterator.secondaryOrder(sOrder); |
| 465 | short secTOrder = CollationElementIterator.secondaryOrder(tOrder); |
| 466 | if (secSOrder != secTOrder) { |
| 467 | // there is a secondary difference |
| 468 | result = (secSOrder < secTOrder) ? Collator.LESS : Collator.GREATER; |
| 469 | // (strength is SECONDARY) |
| 470 | checkSecTer = false; |
| 471 | // (even in french, only the first secondary difference within |
| 472 | // a base character matters) |
| 473 | } else { |
| 474 | if (checkTertiary) { |
| 475 | // a tertiary difference may still matter |
| 476 | short terSOrder = CollationElementIterator.tertiaryOrder(sOrder); |
| 477 | short terTOrder = CollationElementIterator.tertiaryOrder(tOrder); |
| 478 | if (terSOrder != terTOrder) { |
| 479 | // there is a tertiary difference |
| 480 | result = (terSOrder < terTOrder) ? Collator.LESS : Collator.GREATER; |
| 481 | // (strength is TERTIARY) |
| 482 | checkTertiary = false; |
| 483 | } |
| 484 | } |
| 485 | } |
| 486 | } // if (checkSecTer) |
| 487 | |
| 488 | } // if ( pSOrder != pTOrder ) |
| 489 | } // while() |
| 490 | |
| 491 | if (sOrder != CollationElementIterator.NULLORDER) { |
| 492 | // (tOrder must be CollationElementIterator::NULLORDER, |
| 493 | // since this point is only reached when sOrder or tOrder is NULLORDER.) |
| 494 | // The source string has more elements, but the target string hasn't. |
| 495 | do { |
| 496 | if (CollationElementIterator.primaryOrder(sOrder) != 0) { |
| 497 | // We found an additional non-ignorable base character in the source string. |
| 498 | // This is a primary difference, so the source is greater |
| 499 | return Collator.GREATER; // (strength is PRIMARY) |
| 500 | } |
| 501 | else if (CollationElementIterator.secondaryOrder(sOrder) != 0) { |
| 502 | // Additional secondary elements mean the source string is greater |
| 503 | if (checkSecTer) { |
| 504 | result = Collator.GREATER; // (strength is SECONDARY) |
| 505 | checkSecTer = false; |
| 506 | } |
| 507 | } |
| 508 | } while ((sOrder = sourceCursor.next()) != CollationElementIterator.NULLORDER); |
| 509 | } |
| 510 | else if (tOrder != CollationElementIterator.NULLORDER) { |
| 511 | // The target string has more elements, but the source string hasn't. |
| 512 | do { |
| 513 | if (CollationElementIterator.primaryOrder(tOrder) != 0) |
| 514 | // We found an additional non-ignorable base character in the target string. |
| 515 | // This is a primary difference, so the source is less |
| 516 | return Collator.LESS; // (strength is PRIMARY) |
| 517 | else if (CollationElementIterator.secondaryOrder(tOrder) != 0) { |
| 518 | // Additional secondary elements in the target mean the source string is less |
| 519 | if (checkSecTer) { |
| 520 | result = Collator.LESS; // (strength is SECONDARY) |
| 521 | checkSecTer = false; |
| 522 | } |
| 523 | } |
| 524 | } while ((tOrder = targetCursor.next()) != CollationElementIterator.NULLORDER); |
| 525 | } |
| 526 | |
| 527 | // For IDENTICAL comparisons, we use a bitwise character comparison |
| 528 | // as a tiebreaker if all else is equal |
| 529 | if (result == 0 && getStrength() == IDENTICAL) { |
| 530 | int mode = getDecomposition(); |
| 531 | Normalizer.Form form; |
| 532 | if (mode == CANONICAL_DECOMPOSITION) { |
| 533 | form = Normalizer.Form.NFD; |
| 534 | } else if (mode == FULL_DECOMPOSITION) { |
| 535 | form = Normalizer.Form.NFKD; |
| 536 | } else { |
| 537 | return source.compareTo(target); |
| 538 | } |
| 539 | |
| 540 | String sourceDecomposition = Normalizer.normalize(source, form); |
| 541 | String targetDecomposition = Normalizer.normalize(target, form); |
| 542 | return sourceDecomposition.compareTo(targetDecomposition); |
| 543 | } |
| 544 | return result; |
| 545 | } |
| 546 | |
| 547 | /** |
| 548 | * Transforms the string into a series of characters that can be compared |
| 549 | * with CollationKey.compareTo. This overrides java.text.Collator.getCollationKey. |
| 550 | * It can be overriden in a subclass. |
| 551 | */ |
| 552 | public synchronized CollationKey getCollationKey(String source) |
| 553 | { |
| 554 | // |
| 555 | // The basic algorithm here is to find all of the collation elements for each |
| 556 | // character in the source string, convert them to a char representation, |
| 557 | // and put them into the collation key. But it's trickier than that. |
| 558 | // Each collation element in a string has three components: primary (A vs B), |
| 559 | // secondary (A vs A-acute), and tertiary (A' vs a); and a primary difference |
| 560 | // at the end of a string takes precedence over a secondary or tertiary |
| 561 | // difference earlier in the string. |
| 562 | // |
| 563 | // To account for this, we put all of the primary orders at the beginning of the |
| 564 | // string, followed by the secondary and tertiary orders, separated by nulls. |
| 565 | // |
| 566 | // Here's a hypothetical example, with the collation element represented as |
| 567 | // a three-digit number, one digit for primary, one for secondary, etc. |
| 568 | // |
| 569 | // String: A a B \u00e9 <--(e-acute) |
| 570 | // Collation Elements: 101 100 201 510 |
| 571 | // |
| 572 | // Collation Key: 1125<null>0001<null>1010 |
| 573 | // |
| 574 | // To make things even trickier, secondary differences (accent marks) are compared |
| 575 | // starting at the *end* of the string in languages with French secondary ordering. |
| 576 | // But when comparing the accent marks on a single base character, they are compared |
| 577 | // from the beginning. To handle this, we reverse all of the accents that belong |
| 578 | // to each base character, then we reverse the entire string of secondary orderings |
| 579 | // at the end. Taking the same example above, a French collator might return |
| 580 | // this instead: |
| 581 | // |
| 582 | // Collation Key: 1125<null>1000<null>1010 |
| 583 | // |
| 584 | if (source == null) |
| 585 | return null; |
| 586 | |
| 587 | if (primResult == null) { |
| 588 | primResult = new StringBuffer(); |
| 589 | secResult = new StringBuffer(); |
| 590 | terResult = new StringBuffer(); |
| 591 | } else { |
| 592 | primResult.setLength(0); |
| 593 | secResult.setLength(0); |
| 594 | terResult.setLength(0); |
| 595 | } |
| 596 | int order = 0; |
| 597 | boolean compareSec = (getStrength() >= Collator.SECONDARY); |
| 598 | boolean compareTer = (getStrength() >= Collator.TERTIARY); |
| 599 | int secOrder = CollationElementIterator.NULLORDER; |
| 600 | int terOrder = CollationElementIterator.NULLORDER; |
| 601 | int preSecIgnore = 0; |
| 602 | |
| 603 | if (sourceCursor == null) { |
| 604 | sourceCursor = getCollationElementIterator(source); |
| 605 | } else { |
| 606 | sourceCursor.setText(source); |
| 607 | } |
| 608 | |
| 609 | // walk through each character |
| 610 | while ((order = sourceCursor.next()) != |
| 611 | CollationElementIterator.NULLORDER) |
| 612 | { |
| 613 | secOrder = CollationElementIterator.secondaryOrder(order); |
| 614 | terOrder = CollationElementIterator.tertiaryOrder(order); |
| 615 | if (!CollationElementIterator.isIgnorable(order)) |
| 616 | { |
| 617 | primResult.append((char) (CollationElementIterator.primaryOrder(order) |
| 618 | + COLLATIONKEYOFFSET)); |
| 619 | |
| 620 | if (compareSec) { |
| 621 | // |
| 622 | // accumulate all of the ignorable/secondary characters attached |
| 623 | // to a given base character |
| 624 | // |
| 625 | if (tables.isFrenchSec() && preSecIgnore < secResult.length()) { |
| 626 | // |
| 627 | // We're doing reversed secondary ordering and we've hit a base |
| 628 | // (non-ignorable) character. Reverse any secondary orderings |
| 629 | // that applied to the last base character. (see block comment above.) |
| 630 | // |
| 631 | RBCollationTables.reverse(secResult, preSecIgnore, secResult.length()); |
| 632 | } |
| 633 | // Remember where we are in the secondary orderings - this is how far |
| 634 | // back to go if we need to reverse them later. |
| 635 | secResult.append((char)(secOrder+ COLLATIONKEYOFFSET)); |
| 636 | preSecIgnore = secResult.length(); |
| 637 | } |
| 638 | if (compareTer) { |
| 639 | terResult.append((char)(terOrder+ COLLATIONKEYOFFSET)); |
| 640 | } |
| 641 | } |
| 642 | else |
| 643 | { |
| 644 | if (compareSec && secOrder != 0) |
| 645 | secResult.append((char) |
| 646 | (secOrder + tables.getMaxSecOrder() + COLLATIONKEYOFFSET)); |
| 647 | if (compareTer && terOrder != 0) |
| 648 | terResult.append((char) |
| 649 | (terOrder + tables.getMaxTerOrder() + COLLATIONKEYOFFSET)); |
| 650 | } |
| 651 | } |
| 652 | if (tables.isFrenchSec()) |
| 653 | { |
| 654 | if (preSecIgnore < secResult.length()) { |
| 655 | // If we've accumlated any secondary characters after the last base character, |
| 656 | // reverse them. |
| 657 | RBCollationTables.reverse(secResult, preSecIgnore, secResult.length()); |
| 658 | } |
| 659 | // And now reverse the entire secResult to get French secondary ordering. |
| 660 | RBCollationTables.reverse(secResult, 0, secResult.length()); |
| 661 | } |
| 662 | primResult.append((char)0); |
| 663 | secResult.append((char)0); |
| 664 | secResult.append(terResult.toString()); |
| 665 | primResult.append(secResult.toString()); |
| 666 | |
| 667 | if (getStrength() == IDENTICAL) { |
| 668 | primResult.append((char)0); |
| 669 | int mode = getDecomposition(); |
| 670 | if (mode == CANONICAL_DECOMPOSITION) { |
| 671 | primResult.append(Normalizer.normalize(source, Normalizer.Form.NFD)); |
| 672 | } else if (mode == FULL_DECOMPOSITION) { |
| 673 | primResult.append(Normalizer.normalize(source, Normalizer.Form.NFKD)); |
| 674 | } else { |
| 675 | primResult.append(source); |
| 676 | } |
| 677 | } |
| 678 | return new RuleBasedCollationKey(source, primResult.toString()); |
| 679 | } |
| 680 | |
| 681 | /** |
| 682 | * Standard override; no change in semantics. |
| 683 | */ |
| 684 | public Object clone() { |
| 685 | // if we know we're not actually a subclass of RuleBasedCollator |
| 686 | // (this class really should have been made final), bypass |
| 687 | // Object.clone() and use our "copy constructor". This is faster. |
| 688 | if (getClass() == RuleBasedCollator.class) { |
| 689 | return new RuleBasedCollator(this); |
| 690 | } |
| 691 | else { |
| 692 | RuleBasedCollator result = (RuleBasedCollator) super.clone(); |
| 693 | result.primResult = null; |
| 694 | result.secResult = null; |
| 695 | result.terResult = null; |
| 696 | result.sourceCursor = null; |
| 697 | result.targetCursor = null; |
| 698 | return result; |
| 699 | } |
| 700 | } |
| 701 | |
| 702 | /** |
| 703 | * Compares the equality of two collation objects. |
| 704 | * @param obj the table-based collation object to be compared with this. |
| 705 | * @return true if the current table-based collation object is the same |
| 706 | * as the table-based collation object obj; false otherwise. |
| 707 | */ |
| 708 | public boolean equals(Object obj) { |
| 709 | if (obj == null) return false; |
| 710 | if (!super.equals(obj)) return false; // super does class check |
| 711 | RuleBasedCollator other = (RuleBasedCollator) obj; |
| 712 | // all other non-transient information is also contained in rules. |
| 713 | return (getRules().equals(other.getRules())); |
| 714 | } |
| 715 | |
| 716 | /** |
| 717 | * Generates the hash code for the table-based collation object |
| 718 | */ |
| 719 | public int hashCode() { |
| 720 | return getRules().hashCode(); |
| 721 | } |
| 722 | |
| 723 | /** |
| 724 | * Allows CollationElementIterator access to the tables object |
| 725 | */ |
| 726 | RBCollationTables getTables() { |
| 727 | return tables; |
| 728 | } |
| 729 | |
| 730 | // ============================================================== |
| 731 | // private |
| 732 | // ============================================================== |
| 733 | |
| 734 | final static int CHARINDEX = 0x70000000; // need look up in .commit() |
| 735 | final static int EXPANDCHARINDEX = 0x7E000000; // Expand index follows |
| 736 | final static int CONTRACTCHARINDEX = 0x7F000000; // contract indexes follow |
| 737 | final static int UNMAPPED = 0xFFFFFFFF; |
| 738 | |
| 739 | private final static int COLLATIONKEYOFFSET = 1; |
| 740 | |
| 741 | private RBCollationTables tables = null; |
| 742 | |
| 743 | // Internal objects that are cached across calls so that they don't have to |
| 744 | // be created/destroyed on every call to compare() and getCollationKey() |
| 745 | private StringBuffer primResult = null; |
| 746 | private StringBuffer secResult = null; |
| 747 | private StringBuffer terResult = null; |
| 748 | private CollationElementIterator sourceCursor = null; |
| 749 | private CollationElementIterator targetCursor = null; |
| 750 | } |