1 /*
   2  * Copyright (c) 1996, 2010, Oracle and/or its affiliates. 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.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * 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.lang.Character;
  42 import java.util.Vector;
  43 import sun.text.CollatorUtilities;
  44 import sun.text.normalizer.NormalizerBase;
  45 
  46 /**
  47  * The <code>CollationElementIterator</code> class is used as an iterator
  48  * to walk through each character of an international string. Use the iterator
  49  * to return the ordering priority of the positioned character. The ordering
  50  * priority of a character, which we refer to as a key, defines how a character
  51  * is collated in the given collation object.
  52  *
  53  * <p>
  54  * For example, consider the following in Spanish:
  55  * <blockquote>
  56  * <pre>
  57  * "ca" -> the first key is key('c') and second key is key('a').
  58  * "cha" -> the first key is key('ch') and second key is key('a').
  59  * </pre>
  60  * </blockquote>
  61  * And in German,
  62  * <blockquote>
  63  * <pre>
  64  * "\u00e4b"-> the first key is key('a'), the second key is key('e'), and
  65  * the third key is key('b').
  66  * </pre>
  67  * </blockquote>
  68  * The key of a character is an integer composed of primary order(short),
  69  * secondary order(byte), and tertiary order(byte). Java strictly defines
  70  * the size and signedness of its primitive data types. Therefore, the static
  71  * functions <code>primaryOrder</code>, <code>secondaryOrder</code>, and
  72  * <code>tertiaryOrder</code> return <code>int</code>, <code>short</code>,
  73  * and <code>short</code> respectively to ensure the correctness of the key
  74  * value.
  75  *
  76  * <p>
  77  * Example of the iterator usage,
  78  * <blockquote>
  79  * <pre>
  80  *
  81  *  String testString = "This is a test";
  82  *  Collator col = Collator.getInstance();
  83  *  if (col instanceof RuleBasedCollator) {
  84  *      RuleBasedCollator ruleBasedCollator = (RuleBasedCollator)col;
  85  *      CollationElementIterator collationElementIterator = ruleBasedCollator.getCollationElementIterator(testString);
  86  *      int primaryOrder = CollationElementIterator.primaryOrder(collationElementIterator.next());
  87  *          :
  88  *  }
  89  * </pre>
  90  * </blockquote>
  91  *
  92  * <p>
  93  * <code>CollationElementIterator.next</code> returns the collation order
  94  * of the next character. A collation order consists of primary order,
  95  * secondary order and tertiary order. The data type of the collation
  96  * order is <strong>int</strong>. The first 16 bits of a collation order
  97  * is its primary order; the next 8 bits is the secondary order and the
  98  * last 8 bits is the tertiary order.
  99  *
 100  * <p><b>Note:</b> <code>CollationElementIterator</code> is a part of
 101  * <code>RuleBasedCollator</code> implementation. It is only usable
 102  * with <code>RuleBasedCollator</code> instances.
 103  *
 104  * @see                Collator
 105  * @see                RuleBasedCollator
 106  * @author             Helena Shih, Laura Werner, Richard Gillam
 107  */
 108 public final class CollationElementIterator
 109 {
 110     /**
 111      * Null order which indicates the end of string is reached by the
 112      * cursor.
 113      */
 114     public final static int NULLORDER = 0xffffffff;
 115 
 116     /**
 117      * CollationElementIterator constructor.  This takes the source string and
 118      * the collation object.  The cursor will walk thru the source string based
 119      * on the predefined collation rules.  If the source string is empty,
 120      * NULLORDER will be returned on the calls to next().
 121      * @param sourceText the source string.
 122      * @param order the collation object.
 123      */
 124     CollationElementIterator(String sourceText, RuleBasedCollator owner) {
 125         this.owner = owner;
 126         ordering = owner.getTables();
 127         if ( sourceText.length() != 0 ) {
 128             NormalizerBase.Mode mode =
 129                 CollatorUtilities.toNormalizerMode(owner.getDecomposition());
 130             text = new NormalizerBase(sourceText, mode);
 131         }
 132     }
 133 
 134     /**
 135      * CollationElementIterator constructor.  This takes the source string and
 136      * the collation object.  The cursor will walk thru the source string based
 137      * on the predefined collation rules.  If the source string is empty,
 138      * NULLORDER will be returned on the calls to next().
 139      * @param sourceText the source string.
 140      * @param order the collation object.
 141      */
 142     CollationElementIterator(CharacterIterator sourceText, RuleBasedCollator owner) {
 143         this.owner = owner;
 144         ordering = owner.getTables();
 145         NormalizerBase.Mode mode =
 146             CollatorUtilities.toNormalizerMode(owner.getDecomposition());
 147         text = new NormalizerBase(sourceText, mode);
 148     }
 149 
 150     /**
 151      * Resets the cursor to the beginning of the string.  The next call
 152      * to next() will return the first collation element in the string.
 153      */
 154     public void reset()
 155     {
 156         if (text != null) {
 157             text.reset();
 158             NormalizerBase.Mode mode =
 159                 CollatorUtilities.toNormalizerMode(owner.getDecomposition());
 160             text.setMode(mode);
 161         }
 162         buffer = null;
 163         expIndex = 0;
 164         swapOrder = 0;
 165     }
 166 
 167     /**
 168      * Get the next collation element in the string.  <p>This iterator iterates
 169      * over a sequence of collation elements that were built from the string.
 170      * Because there isn't necessarily a one-to-one mapping from characters to
 171      * collation elements, this doesn't mean the same thing as "return the
 172      * collation element [or ordering priority] of the next character in the
 173      * string".</p>
 174      * <p>This function returns the collation element that the iterator is currently
 175      * pointing to and then updates the internal pointer to point to the next element.
 176      * previous() updates the pointer first and then returns the element.  This
 177      * means that when you change direction while iterating (i.e., call next() and
 178      * then call previous(), or call previous() and then call next()), you'll get
 179      * back the same element twice.</p>
 180      */
 181     public int next()
 182     {
 183         if (text == null) {
 184             return NULLORDER;
 185         }
 186         NormalizerBase.Mode textMode = text.getMode();
 187         // convert the owner's mode to something the Normalizer understands
 188         NormalizerBase.Mode ownerMode =
 189             CollatorUtilities.toNormalizerMode(owner.getDecomposition());
 190         if (textMode != ownerMode) {
 191             text.setMode(ownerMode);
 192         }
 193 
 194         // if buffer contains any decomposed char values
 195         // return their strength orders before continuing in
 196         // the Normalizer's CharacterIterator.
 197         if (buffer != null) {
 198             if (expIndex < buffer.length) {
 199                 return strengthOrder(buffer[expIndex++]);
 200             } else {
 201                 buffer = null;
 202                 expIndex = 0;
 203             }
 204         } else if (swapOrder != 0) {
 205             if (Character.isSupplementaryCodePoint(swapOrder)) {
 206                 char[] chars = Character.toChars(swapOrder);
 207                 swapOrder = chars[1];
 208                 return chars[0] << 16;
 209             }
 210             int order = swapOrder << 16;
 211             swapOrder = 0;
 212             return order;
 213         }
 214         int ch  = text.next();
 215 
 216         // are we at the end of Normalizer's text?
 217         if (ch == NormalizerBase.DONE) {
 218             return NULLORDER;
 219         }
 220 
 221         int value = ordering.getUnicodeOrder(ch);
 222         if (value == RuleBasedCollator.UNMAPPED) {
 223             swapOrder = ch;
 224             return UNMAPPEDCHARVALUE;
 225         }
 226         else if (value >= RuleBasedCollator.CONTRACTCHARINDEX) {
 227             value = nextContractChar(ch);
 228         }
 229         if (value >= RuleBasedCollator.EXPANDCHARINDEX) {
 230             buffer = ordering.getExpandValueList(value);
 231             expIndex = 0;
 232             value = buffer[expIndex++];
 233         }
 234 
 235         if (ordering.isSEAsianSwapping()) {
 236             int consonant;
 237             if (isThaiPreVowel(ch)) {
 238                 consonant = text.next();
 239                 if (isThaiBaseConsonant(consonant)) {
 240                     buffer = makeReorderedBuffer(consonant, value, buffer, true);
 241                     value = buffer[0];
 242                     expIndex = 1;
 243                 } else if (consonant != NormalizerBase.DONE) {
 244                     text.previous();
 245                 }
 246             }
 247             if (isLaoPreVowel(ch)) {
 248                 consonant = text.next();
 249                 if (isLaoBaseConsonant(consonant)) {
 250                     buffer = makeReorderedBuffer(consonant, value, buffer, true);
 251                     value = buffer[0];
 252                     expIndex = 1;
 253                 } else if (consonant != NormalizerBase.DONE) {
 254                     text.previous();
 255                 }
 256             }
 257         }
 258 
 259         return strengthOrder(value);
 260     }
 261 
 262     /**
 263      * Get the previous collation element in the string.  <p>This iterator iterates
 264      * over a sequence of collation elements that were built from the string.
 265      * Because there isn't necessarily a one-to-one mapping from characters to
 266      * collation elements, this doesn't mean the same thing as "return the
 267      * collation element [or ordering priority] of the previous character in the
 268      * string".</p>
 269      * <p>This function updates the iterator's internal pointer to point to the
 270      * collation element preceding the one it's currently pointing to and then
 271      * returns that element, while next() returns the current element and then
 272      * updates the pointer.  This means that when you change direction while
 273      * iterating (i.e., call next() and then call previous(), or call previous()
 274      * and then call next()), you'll get back the same element twice.</p>
 275      * @since 1.2
 276      */
 277     public int previous()
 278     {
 279         if (text == null) {
 280             return NULLORDER;
 281         }
 282         NormalizerBase.Mode textMode = text.getMode();
 283         // convert the owner's mode to something the Normalizer understands
 284         NormalizerBase.Mode ownerMode =
 285             CollatorUtilities.toNormalizerMode(owner.getDecomposition());
 286         if (textMode != ownerMode) {
 287             text.setMode(ownerMode);
 288         }
 289         if (buffer != null) {
 290             if (expIndex > 0) {
 291                 return strengthOrder(buffer[--expIndex]);
 292             } else {
 293                 buffer = null;
 294                 expIndex = 0;
 295             }
 296         } else if (swapOrder != 0) {
 297             if (Character.isSupplementaryCodePoint(swapOrder)) {
 298                 char[] chars = Character.toChars(swapOrder);
 299                 swapOrder = chars[1];
 300                 return chars[0] << 16;
 301             }
 302             int order = swapOrder << 16;
 303             swapOrder = 0;
 304             return order;
 305         }
 306         int ch = text.previous();
 307         if (ch == NormalizerBase.DONE) {
 308             return NULLORDER;
 309         }
 310 
 311         int value = ordering.getUnicodeOrder(ch);
 312 
 313         if (value == RuleBasedCollator.UNMAPPED) {
 314             swapOrder = UNMAPPEDCHARVALUE;
 315             return ch;
 316         } else if (value >= RuleBasedCollator.CONTRACTCHARINDEX) {
 317             value = prevContractChar(ch);
 318         }
 319         if (value >= RuleBasedCollator.EXPANDCHARINDEX) {
 320             buffer = ordering.getExpandValueList(value);
 321             expIndex = buffer.length;
 322             value = buffer[--expIndex];
 323         }
 324 
 325         if (ordering.isSEAsianSwapping()) {
 326             int vowel;
 327             if (isThaiBaseConsonant(ch)) {
 328                 vowel = text.previous();
 329                 if (isThaiPreVowel(vowel)) {
 330                     buffer = makeReorderedBuffer(vowel, value, buffer, false);
 331                     expIndex = buffer.length - 1;
 332                     value = buffer[expIndex];
 333                 } else {
 334                     text.next();
 335                 }
 336             }
 337             if (isLaoBaseConsonant(ch)) {
 338                 vowel = text.previous();
 339                 if (isLaoPreVowel(vowel)) {
 340                     buffer = makeReorderedBuffer(vowel, value, buffer, false);
 341                     expIndex = buffer.length - 1;
 342                     value = buffer[expIndex];
 343                 } else {
 344                     text.next();
 345                 }
 346             }
 347         }
 348 
 349         return strengthOrder(value);
 350     }
 351 
 352     /**
 353      * Return the primary component of a collation element.
 354      * @param order the collation element
 355      * @return the element's primary component
 356      */
 357     public final static int primaryOrder(int order)
 358     {
 359         order &= RBCollationTables.PRIMARYORDERMASK;
 360         return (order >>> RBCollationTables.PRIMARYORDERSHIFT);
 361     }
 362     /**
 363      * Return the secondary component of a collation element.
 364      * @param order the collation element
 365      * @return the element's secondary component
 366      */
 367     public final static short secondaryOrder(int order)
 368     {
 369         order = order & RBCollationTables.SECONDARYORDERMASK;
 370         return ((short)(order >> RBCollationTables.SECONDARYORDERSHIFT));
 371     }
 372     /**
 373      * Return the tertiary component of a collation element.
 374      * @param order the collation element
 375      * @return the element's tertiary component
 376      */
 377     public final static short tertiaryOrder(int order)
 378     {
 379         return ((short)(order &= RBCollationTables.TERTIARYORDERMASK));
 380     }
 381 
 382     /**
 383      *  Get the comparison order in the desired strength.  Ignore the other
 384      *  differences.
 385      *  @param order The order value
 386      */
 387     final int strengthOrder(int order)
 388     {
 389         int s = owner.getStrength();
 390         if (s == Collator.PRIMARY)
 391         {
 392             order &= RBCollationTables.PRIMARYDIFFERENCEONLY;
 393         } else if (s == Collator.SECONDARY)
 394         {
 395             order &= RBCollationTables.SECONDARYDIFFERENCEONLY;
 396         }
 397         return order;
 398     }
 399 
 400     /**
 401      * Sets the iterator to point to the collation element corresponding to
 402      * the specified character (the parameter is a CHARACTER offset in the
 403      * original string, not an offset into its corresponding sequence of
 404      * collation elements).  The value returned by the next call to next()
 405      * will be the collation element corresponding to the specified position
 406      * in the text.  If that position is in the middle of a contracting
 407      * character sequence, the result of the next call to next() is the
 408      * collation element for that sequence.  This means that getOffset()
 409      * is not guaranteed to return the same value as was passed to a preceding
 410      * call to setOffset().
 411      *
 412      * @param newOffset The new character offset into the original text.
 413      * @since 1.2
 414      */
 415     public void setOffset(int newOffset)
 416     {
 417         if (text != null) {
 418             if (newOffset < text.getBeginIndex()
 419                 || newOffset >= text.getEndIndex()) {
 420                     text.setIndexOnly(newOffset);
 421             } else {
 422                 int c = text.setIndex(newOffset);
 423 
 424                 // if the desired character isn't used in a contracting character
 425                 // sequence, bypass all the backing-up logic-- we're sitting on
 426                 // the right character already
 427                 if (ordering.usedInContractSeq(c)) {
 428                     // walk backwards through the string until we see a character
 429                     // that DOESN'T participate in a contracting character sequence
 430                     while (ordering.usedInContractSeq(c)) {
 431                         c = text.previous();
 432                     }
 433                     // now walk forward using this object's next() method until
 434                     // we pass the starting point and set our current position
 435                     // to the beginning of the last "character" before or at
 436                     // our starting position
 437                     int last = text.getIndex();
 438                     while (text.getIndex() <= newOffset) {
 439                         last = text.getIndex();
 440                         next();
 441                     }
 442                     text.setIndexOnly(last);
 443                     // we don't need this, since last is the last index
 444                     // that is the starting of the contraction which encompass
 445                     // newOffset
 446                     // text.previous();
 447                 }
 448             }
 449         }
 450         buffer = null;
 451         expIndex = 0;
 452         swapOrder = 0;
 453     }
 454 
 455     /**
 456      * Returns the character offset in the original text corresponding to the next
 457      * collation element.  (That is, getOffset() returns the position in the text
 458      * corresponding to the collation element that will be returned by the next
 459      * call to next().)  This value will always be the index of the FIRST character
 460      * corresponding to the collation element (a contracting character sequence is
 461      * when two or more characters all correspond to the same collation element).
 462      * This means if you do setOffset(x) followed immediately by getOffset(), getOffset()
 463      * won't necessarily return x.
 464      *
 465      * @return The character offset in the original text corresponding to the collation
 466      * element that will be returned by the next call to next().
 467      * @since 1.2
 468      */
 469     public int getOffset()
 470     {
 471         return (text != null) ? text.getIndex() : 0;
 472     }
 473 
 474 
 475     /**
 476      * Return the maximum length of any expansion sequences that end
 477      * with the specified comparison order.
 478      * @param order a collation order returned by previous or next.
 479      * @return the maximum length of any expansion sequences ending
 480      *         with the specified order.
 481      * @since 1.2
 482      */
 483     public int getMaxExpansion(int order)
 484     {
 485         return ordering.getMaxExpansion(order);
 486     }
 487 
 488     /**
 489      * Set a new string over which to iterate.
 490      *
 491      * @param source  the new source text
 492      * @since 1.2
 493      */
 494     public void setText(String source)
 495     {
 496         buffer = null;
 497         swapOrder = 0;
 498         expIndex = 0;
 499         NormalizerBase.Mode mode =
 500             CollatorUtilities.toNormalizerMode(owner.getDecomposition());
 501         if (text == null) {
 502             text = new NormalizerBase(source, mode);
 503         } else {
 504             text.setMode(mode);
 505             text.setText(source);
 506         }
 507     }
 508 
 509     /**
 510      * Set a new string over which to iterate.
 511      *
 512      * @param source  the new source text.
 513      * @since 1.2
 514      */
 515     public void setText(CharacterIterator source)
 516     {
 517         buffer = null;
 518         swapOrder = 0;
 519         expIndex = 0;
 520         NormalizerBase.Mode mode =
 521             CollatorUtilities.toNormalizerMode(owner.getDecomposition());
 522         if (text == null) {
 523             text = new NormalizerBase(source, mode);
 524         } else {
 525             text.setMode(mode);
 526             text.setText(source);
 527         }
 528     }
 529 
 530     //============================================================
 531     // privates
 532     //============================================================
 533 
 534     /**
 535      * Determine if a character is a Thai vowel (which sorts after
 536      * its base consonant).
 537      */
 538     private final static boolean isThaiPreVowel(int ch) {
 539         return (ch >= 0x0e40) && (ch <= 0x0e44);
 540     }
 541 
 542     /**
 543      * Determine if a character is a Thai base consonant
 544      */
 545     private final static boolean isThaiBaseConsonant(int ch) {
 546         return (ch >= 0x0e01) && (ch <= 0x0e2e);
 547     }
 548 
 549     /**
 550      * Determine if a character is a Lao vowel (which sorts after
 551      * its base consonant).
 552      */
 553     private final static boolean isLaoPreVowel(int ch) {
 554         return (ch >= 0x0ec0) && (ch <= 0x0ec4);
 555     }
 556 
 557     /**
 558      * Determine if a character is a Lao base consonant
 559      */
 560     private final static boolean isLaoBaseConsonant(int ch) {
 561         return (ch >= 0x0e81) && (ch <= 0x0eae);
 562     }
 563 
 564     /**
 565      * This method produces a buffer which contains the collation
 566      * elements for the two characters, with colFirst's values preceding
 567      * another character's.  Presumably, the other character precedes colFirst
 568      * in logical order (otherwise you wouldn't need this method would you?).
 569      * The assumption is that the other char's value(s) have already been
 570      * computed.  If this char has a single element it is passed to this
 571      * method as lastValue, and lastExpansion is null.  If it has an
 572      * expansion it is passed in lastExpansion, and colLastValue is ignored.
 573      */
 574     private int[] makeReorderedBuffer(int colFirst,
 575                                       int lastValue,
 576                                       int[] lastExpansion,
 577                                       boolean forward) {
 578 
 579         int[] result;
 580 
 581         int firstValue = ordering.getUnicodeOrder(colFirst);
 582         if (firstValue >= RuleBasedCollator.CONTRACTCHARINDEX) {
 583             firstValue = forward? nextContractChar(colFirst) : prevContractChar(colFirst);
 584         }
 585 
 586         int[] firstExpansion = null;
 587         if (firstValue >= RuleBasedCollator.EXPANDCHARINDEX) {
 588             firstExpansion = ordering.getExpandValueList(firstValue);
 589         }
 590 
 591         if (!forward) {
 592             int temp1 = firstValue;
 593             firstValue = lastValue;
 594             lastValue = temp1;
 595             int[] temp2 = firstExpansion;
 596             firstExpansion = lastExpansion;
 597             lastExpansion = temp2;
 598         }
 599 
 600         if (firstExpansion == null && lastExpansion == null) {
 601             result = new int [2];
 602             result[0] = firstValue;
 603             result[1] = lastValue;
 604         }
 605         else {
 606             int firstLength = firstExpansion==null? 1 : firstExpansion.length;
 607             int lastLength = lastExpansion==null? 1 : lastExpansion.length;
 608             result = new int[firstLength + lastLength];
 609 
 610             if (firstExpansion == null) {
 611                 result[0] = firstValue;
 612             }
 613             else {
 614                 System.arraycopy(firstExpansion, 0, result, 0, firstLength);
 615             }
 616 
 617             if (lastExpansion == null) {
 618                 result[firstLength] = lastValue;
 619             }
 620             else {
 621                 System.arraycopy(lastExpansion, 0, result, firstLength, lastLength);
 622             }
 623         }
 624 
 625         return result;
 626     }
 627 
 628     /**
 629      *  Check if a comparison order is ignorable.
 630      *  @return true if a character is ignorable, false otherwise.
 631      */
 632     final static boolean isIgnorable(int order)
 633     {
 634         return ((primaryOrder(order) == 0) ? true : false);
 635     }
 636 
 637     /**
 638      * Get the ordering priority of the next contracting character in the
 639      * string.
 640      * @param ch the starting character of a contracting character token
 641      * @return the next contracting character's ordering.  Returns NULLORDER
 642      * if the end of string is reached.
 643      */
 644     private int nextContractChar(int ch)
 645     {
 646         // First get the ordering of this single character,
 647         // which is always the first element in the list
 648         Vector list = ordering.getContractValues(ch);
 649         EntryPair pair = (EntryPair)list.firstElement();
 650         int order = pair.value;
 651 
 652         // find out the length of the longest contracting character sequence in the list.
 653         // There's logic in the builder code to make sure the longest sequence is always
 654         // the last.
 655         pair = (EntryPair)list.lastElement();
 656         int maxLength = pair.entryName.length();
 657 
 658         // (the Normalizer is cloned here so that the seeking we do in the next loop
 659         // won't affect our real position in the text)
 660         NormalizerBase tempText = (NormalizerBase)text.clone();
 661 
 662         // extract the next maxLength characters in the string (we have to do this using the
 663         // Normalizer to ensure that our offsets correspond to those the rest of the
 664         // iterator is using) and store it in "fragment".
 665         tempText.previous();
 666         key.setLength(0);
 667         int c = tempText.next();
 668         while (maxLength > 0 && c != NormalizerBase.DONE) {
 669             if (Character.isSupplementaryCodePoint(c)) {
 670                 key.append(Character.toChars(c));
 671                 maxLength -= 2;
 672             } else {
 673                 key.append((char)c);
 674                 --maxLength;
 675             }
 676             c = tempText.next();
 677         }
 678         String fragment = key.toString();
 679         // now that we have that fragment, iterate through this list looking for the
 680         // longest sequence that matches the characters in the actual text.  (maxLength
 681         // is used here to keep track of the length of the longest sequence)
 682         // Upon exit from this loop, maxLength will contain the length of the matching
 683         // sequence and order will contain the collation-element value corresponding
 684         // to this sequence
 685         maxLength = 1;
 686         for (int i = list.size() - 1; i > 0; i--) {
 687             pair = (EntryPair)list.elementAt(i);
 688             if (!pair.fwd)
 689                 continue;
 690 
 691             if (fragment.startsWith(pair.entryName) && pair.entryName.length()
 692                     > maxLength) {
 693                 maxLength = pair.entryName.length();
 694                 order = pair.value;
 695             }
 696         }
 697 
 698         // seek our current iteration position to the end of the matching sequence
 699         // and return the appropriate collation-element value (if there was no matching
 700         // sequence, we're already seeked to the right position and order already contains
 701         // the correct collation-element value for the single character)
 702         while (maxLength > 1) {
 703             c = text.next();
 704             maxLength -= Character.charCount(c);
 705         }
 706         return order;
 707     }
 708 
 709     /**
 710      * Get the ordering priority of the previous contracting character in the
 711      * string.
 712      * @param ch the starting character of a contracting character token
 713      * @return the next contracting character's ordering.  Returns NULLORDER
 714      * if the end of string is reached.
 715      */
 716     private int prevContractChar(int ch)
 717     {
 718         // This function is identical to nextContractChar(), except that we've
 719         // switched things so that the next() and previous() calls on the Normalizer
 720         // are switched and so that we skip entry pairs with the fwd flag turned on
 721         // rather than off.  Notice that we still use append() and startsWith() when
 722         // working on the fragment.  This is because the entry pairs that are used
 723         // in reverse iteration have their names reversed already.
 724         Vector list = ordering.getContractValues(ch);
 725         EntryPair pair = (EntryPair)list.firstElement();
 726         int order = pair.value;
 727 
 728         pair = (EntryPair)list.lastElement();
 729         int maxLength = pair.entryName.length();
 730 
 731         NormalizerBase tempText = (NormalizerBase)text.clone();
 732 
 733         tempText.next();
 734         key.setLength(0);
 735         int c = tempText.previous();
 736         while (maxLength > 0 && c != NormalizerBase.DONE) {
 737             if (Character.isSupplementaryCodePoint(c)) {
 738                 key.append(Character.toChars(c));
 739                 maxLength -= 2;
 740             } else {
 741                 key.append((char)c);
 742                 --maxLength;
 743             }
 744             c = tempText.previous();
 745         }
 746         String fragment = key.toString();
 747 
 748         maxLength = 1;
 749         for (int i = list.size() - 1; i > 0; i--) {
 750             pair = (EntryPair)list.elementAt(i);
 751             if (pair.fwd)
 752                 continue;
 753 
 754             if (fragment.startsWith(pair.entryName) && pair.entryName.length()
 755                     > maxLength) {
 756                 maxLength = pair.entryName.length();
 757                 order = pair.value;
 758             }
 759         }
 760 
 761         while (maxLength > 1) {
 762             c = text.previous();
 763             maxLength -= Character.charCount(c);
 764         }
 765         return order;
 766     }
 767 
 768     final static int UNMAPPEDCHARVALUE = 0x7FFF0000;
 769 
 770     private NormalizerBase text = null;
 771     private int[] buffer = null;
 772     private int expIndex = 0;
 773     private StringBuffer key = new StringBuffer(5);
 774     private int swapOrder = 0;
 775     private RBCollationTables ordering;
 776     private RuleBasedCollator owner;
 777 }