home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1998 July & August / Pcwk78a98.iso / Internet / Javadraw / DATA.Z / RuleBasedCollator.java < prev    next >
Text File  |  1997-08-30  |  38KB  |  988 lines
  1. /*
  2.  * @(#)RuleBasedCollator.java    1.9 97/03/03
  3.  *
  4.  * (C) Copyright Taligent, Inc. 1996, 1997 - All Rights Reserved
  5.  * (C) Copyright IBM Corp. 1996, 1997 - All Rights Reserved
  6.  *
  7.  * Portions copyright (c) 1996 Sun Microsystems, Inc. All Rights Reserved.
  8.  *
  9.  *   The original version of this source code and documentation is copyrighted
  10.  * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
  11.  * materials are provided under terms of a License Agreement between Taligent
  12.  * and Sun. This technology is protected by multiple US and International
  13.  * patents. This notice and attribution to Taligent may not be removed.
  14.  *   Taligent is a registered trademark of Taligent, Inc.
  15.  *
  16.  * Permission to use, copy, modify, and distribute this software
  17.  * and its documentation for NON-COMMERCIAL purposes and without
  18.  * fee is hereby granted provided that this copyright notice
  19.  * appears in all copies. Please refer to the file "copyright.html"
  20.  * for further important copyright and licensing information.
  21.  *
  22.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  23.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  24.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  25.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  26.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  27.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  28.  *
  29.  */
  30.  
  31. package java.text;
  32.  
  33. import java.lang.Character;
  34. import java.util.Vector;
  35. import java.util.Date;
  36.  
  37. /**
  38.  * The <code>RuleBasedCollator</code> class is a concrete subclass of
  39.  * <code>Collator</code> that provides a simple, data-driven, table collator.
  40.  * With this class you can create a customized table-based <code>Collator</code>.
  41.  * <code>RuleBasedCollator</code> maps characters to sort keys.
  42.  *
  43.  * <p>
  44.  * <code>RuleBasedCollator</code> has the following restrictions
  45.  * for efficiency (other subclasses may be used for more complex languages) :
  46.  * <ol>
  47.  * <li>The French secondary ordering is applied to the whole collator
  48.  *     object.
  49.  * <li>All non-mentioned Unicode characters are at the end of the
  50.  *     collation order.
  51.  * <li>Private use characters are treated as identical.  The private
  52.  *     use area in Unicode is <code>0xE800</code>-<code>0xF8FF</code>.
  53.  * </ol>
  54.  *
  55.  * <p>
  56.  * The collation table is composed of a list of collation rules, where each
  57.  * rule is of three forms:
  58.  * <pre>
  59.  *    < modifier >
  60.  *    < relation > < text-argument >
  61.  *    < reset > < text-argument >
  62.  * </pre>
  63.  * The following demonstrates how to create your own collation rules:
  64.  * <UL Type=round>
  65.  *    <LI><strong>Text-Argument</strong>: A text-argument is any sequence of
  66.  *        characters, excluding special characters (that is, whitespace
  67.  *        characters and the characters used in modifier, relation and reset).
  68.  *        If those characters are desired, you can put them in single quotes
  69.  *        (e.g. ampersand => '&').
  70.  *    <LI><strong>Modifier</strong>: There is a single modifier
  71.  *        which is used to specify that all accents (secondary differences) are
  72.  *        backwards.
  73.  *        <p>'@' : Indicates that accents are sorted backwards, as in French.
  74.  *    <LI><strong>Relation</strong>: The relations are the following:
  75.  *        <UL Type=square>
  76.  *            <LI>'<' : Greater, as a letter difference (primary)
  77.  *            <LI>';' : Greater, as an accent difference (secondary)
  78.  *            <LI>',' : Greater, as a case difference (tertiary)
  79.  *            <LI>'=' : Equal
  80.  *        </UL>
  81.  *    <LI><strong>Reset</strong>: There is a single reset
  82.  *        which is used primarily for contractions and expansions, but which
  83.  *        can also be used to add a modification at the end of a set of rules.
  84.  *        <p>'&' : Indicates that the next rule follows the position to where
  85.  *            the reset text-argument would be sorted.
  86.  * </UL>
  87.  *
  88.  * <p>
  89.  * This sounds more complicated than it is in practice. For example, the
  90.  * following are equivalent ways of expressing the same thing:
  91.  * <blockquote>
  92.  * <pre>
  93.  * a < b < c
  94.  * a < b & b < c
  95.  * a < c & a < b
  96.  * </pre>
  97.  * </blockquote>
  98.  * Notice that the order is important, as the subsequent item goes immediately
  99.  * after the text-argument. The following are not equivalent:
  100.  * <blockquote>
  101.  * <pre>
  102.  * a < b & a < c
  103.  * a < c & a < b
  104.  * </pre>
  105.  * </blockquote>
  106.  * Either the text-argument must already be present in the sequence, or some
  107.  * initial substring of the text-argument must be present. (e.g. "a < b & ae <
  108.  * e" is valid since "a" is present in the sequence before "ae" is reset). In
  109.  * this latter case, "ae" is not entered and treated as a single character;
  110.  * instead, "e" is sorted as if it were expanded to two characters: "a"
  111.  * followed by an "e". This difference appears in natural languages: in
  112.  * traditional Spanish "ch" is treated as though it contracts to a single
  113.  * character (expressed as "c < ch < d"), while in traditional German "Σ"
  114.  * (a-umlaut) is treated as though it expands to two characters (expressed as
  115.  * "a & ae ; Σ < b").
  116.  *
  117.  * <p>
  118.  * <strong>Ignorable Characters</strong>
  119.  * <p>
  120.  * For ignorable characters, the first rule must start with a relation (the
  121.  * examples we have used above are really fragments; "a < b" really should be
  122.  * "< a < b"). If, however, the first relation is not "<", then all the all
  123.  * text-arguments up to the first "<" are ignorable. For example, ", - < a < b"
  124.  * makes "-" an ignorable character, as we saw earlier in the word
  125.  * "black-birds". In the samples for different languages, you see that most
  126.  * accents are ignorable.
  127.  *
  128.  * <p><strong>Normalization and Accents</strong>
  129.  * <p> 
  130.  * The <code>Collator</code> object automatically normalizes text internally
  131.  * to separate accents from base characters where possible. This is done both when
  132.  * processing the rules, and when comparing two strings. <code>Collator</code>
  133.  * also uses the Unicode canonical mapping to ensure that combining sequences
  134.  * are sorted properly (for more information, see
  135.  * <A HREF="http://www.aw.com/devpress">The Unicode Standard, Version 2.0</A>.)</P>
  136.  *
  137.  * <p><strong>Errors</strong>
  138.  * <p>
  139.  * The following are errors:
  140.  * <UL Type=round>
  141.  *     <LI>A text-argument not preceded by either a reset or relation character
  142.  *        (e.g. "a < b c < d").
  143.  *     <LI>A relation or reset character not followed by a text-argument
  144.  *        (e.g. "a < , b").
  145.  *     <LI>A reset where the text-argument (or an initial substring of the
  146.  *         text-argument) is not already in the sequence.
  147.  *         (e.g. "a < b & e < f")
  148.  * </UL>
  149.  * If you produce one of these errors, a <code>RuleBasedCollator</code> throws
  150.  * a <code>ParseException</code>.
  151.  *
  152.  * <p><strong>Examples</strong>
  153.  * <p>Simple:     "< a < b < c < d"
  154.  * <p>Norwegian:  "< a,A< b,B< c,C< d,D< e,E< f,F< g,G< h,H< i,I< j,J
  155.  *                 < k,K< l,L< m,M< n,N< o,O< p,P< q,Q< r,R< s,S< t,T
  156.  *                 < u,U< v,V< w,W< x,X< y,Y< z,Z
  157.  *                 < \u00E5=a\u030A,\u00C5=A\u030A
  158.  *                 ;aa,AA< \u00E6,\u00C6< \u00F8,\u00D8"
  159.  *
  160.  * <p>
  161.  * Normally, to create a rule-based Collator object, you will use
  162.  * <code>Collator</code>'s factory method <code>getInstance</code>.
  163.  * However, to create a rule-based Collator object with specialized
  164.  * rules tailored to your needs, you construct the <code>RuleBasedCollator</code>
  165.  * with the rules contained in a <code>String</code> object. For example:
  166.  * <blockquote>
  167.  * <pre>
  168.  * String Simple = "< a < b < c < d";
  169.  * RuleBasedCollator mySimple = new RuleBasedCollator(Simple);
  170.  * </pre>
  171.  * </blockquote>
  172.  * Or:
  173.  * <blockquote>
  174.  * <pre>
  175.  * String Norwegian = "< a,A< b,B< c,C< d,D< e,E< f,F< g,G< h,H< i,I< j,J" +
  176.  *                 "< k,K< l,L< m,M< n,N< o,O< p,P< q,Q< r,R< s,S< t,T" +
  177.  *                 "< u,U< v,V< w,W< x,X< y,Y< z,Z" +
  178.  *                 "< \u00E5=a\u030A,\u00C5=A\u030A" +
  179.  *                 ";aa,AA< \u00E6,\u00C6< \u00F8,\u00D8";
  180.  * RuleBasedCollator myNorwegian = new RuleBasedCollator(Norwegian);
  181.  * </pre>
  182.  * </blockquote>
  183.  *
  184.  * <p>
  185.  * Combining <code>Collator</code>s is as simple as concatenating strings.
  186.  * Here's an example that combines two <code>Collator</code>s from two
  187.  * different locales:
  188.  * <blockquote>
  189.  * <pre>
  190.  * // Create an en_US Collator object
  191.  * RuleBasedCollator en_USCollator = (RuleBasedCollator)
  192.  *     Collator.getInstance(new Locale("en", "US", ""));
  193.  * // Create a da_DK Collator object
  194.  * RuleBasedCollator da_DKCollator = (RuleBasedCollator)
  195.  *     Collator.getInstance(new Locale("da", "DK", ""));
  196.  * // Combine the two
  197.  * // First, get the collation rules from en_USCollator
  198.  * String en_USRules = en_USCollator.getRules();
  199.  * // Second, get the collation rules from da_DKCollator
  200.  * String da_DKRules = da_DKCollator.getRules();
  201.  * RuleBasedCollator newCollator =
  202.  *     new RuleBasedCollator(en_USRules + da_DKRules);
  203.  * // newCollator has the combined rules
  204.  * </pre>
  205.  * </blockquote>
  206.  *
  207.  * <p>
  208.  * Another more interesting example would be to make changes on an existing
  209.  * table to create a new <code>Collator</code> object.  For example, add
  210.  * "& C < ch, cH, Ch, CH" to the <code>en_USCollator</code> object to create
  211.  * your own:
  212.  * <blockquote>
  213.  * <pre>
  214.  * // Create a new Collator object with additional rules
  215.  * String addRules = "& C < ch, cH, Ch, CH";
  216.  * RuleBasedCollator myCollator =
  217.  *     new RuleBasedCollator(en_USCollator + addRules);
  218.  * // myCollator contains the new rules
  219.  * </pre>
  220.  * </blockquote>
  221.  *
  222.  * <p>
  223.  * The following example demonstrates how to change the order of
  224.  * non-spacing accents,
  225.  * <blockquote>
  226.  * <pre>
  227.  * // old rule
  228.  * String oldRules = "=\u0301;\u0300;\u0302;\u0308"    // main accents
  229.  *                 + ";\u0327;\u0303;\u0304;\u0305"    // main accents
  230.  *                 + ";\u0306;\u0307;\u0309;\u030A"    // main accents
  231.  *                 + ";\u030B;\u030C;\u030D;\u030E"    // main accents
  232.  *                 + ";\u030F;\u0310;\u0311;\u0312"    // main accents
  233.  *                 + "< a , A ; ae, AE ; \u00e6 , \u00c6"
  234.  *                 + "< b , B < c, C < e, E & C < d, D";
  235.  * // change the order of accent characters
  236.  * String addOn = "& \u0300 ; \u0308 ; \u0302";
  237.  * RuleBasedCollator myCollator = new RuleBasedCollator(oldRules + addOn);
  238.  * </pre>
  239.  * </blockquote>
  240.  *
  241.  * <p>
  242.  * The last example shows how to put new primary ordering in before the
  243.  * default setting. For example, in Japanese <code>Collator</code>, you
  244.  * can either sort English characters before or after Japanese characters,
  245.  * <blockquote>
  246.  * <pre>
  247.  * // get en_US Collator rules
  248.  * RuleBasedCollator en_USCollator = (RuleBasedCollator)Collator.getInstance(Locale.US);
  249.  * // add a few Japanese character to sort before English characters
  250.  * // suppose the last character before the first base letter 'a' in
  251.  * // the English collation rule is \u2212
  252.  * String jaString = "& \u2212 < \u3041, \u3042 < \u3043, \u3044";
  253.  * RuleBasedCollator myJapaneseCollator = new
  254.  *     RuleBasedCollator(en_USCollator.getRules() + jaString);
  255.  * </pre>
  256.  * </blockquote>
  257.  *
  258.  * @see        Collator
  259.  * @see        CollationElementIterator
  260.  * @version    1.9 03/03/97
  261.  * @author     Helena Shih
  262.  */
  263. public class RuleBasedCollator extends Collator{
  264.  
  265.     /**
  266.      * RuleBasedCollator constructor.  This takes the table rules and builds
  267.      * a collation table out of them.  Please see RuleBasedCollator class
  268.      * description for more details on the collation rule syntax.
  269.      * @see java.util.Locale
  270.      * @param rules the collation rules to build the collation table from.
  271.      * @exception ParseException A format exception
  272.      * will be thrown if the build process of the rules fails. For
  273.      * example, build rule "a < b c < d" will cause the constructor to
  274.      * throw the ParseException.
  275.      */
  276.     public RuleBasedCollator(String rules) throws ParseException {
  277.         setStrength(Collator.TERTIARY);
  278.         build(rules);
  279.     }
  280.  
  281.     /**
  282.      * Gets the table-based rules for the collation object.
  283.      * @return returns the collation rules that the table collation object
  284.      * was created from.
  285.      */
  286.     public String getRules()
  287.     {
  288.         if (ruleTable == null) {
  289.             ruleTable = mPattern.getPattern();
  290.             mPattern = null;
  291.         }
  292.         return ruleTable;
  293.     }
  294.  
  295.  
  296.     /**
  297.      * Return a CollationElementIterator for the given String.
  298.      * @see java.text.CollationElementIterator
  299.      */
  300.     public CollationElementIterator getCollationElementIterator(String source) {
  301.         return new CollationElementIterator( source, this );
  302.     }
  303.  
  304.     /**
  305.      * Compares the character data stored in two different strings based on the
  306.      * collation rules.  Returns information about whether a string is less
  307.      * than, greater than or equal to another string in a language.
  308.      * This can be overriden in a subclass.
  309.      */
  310.     public int compare(String source, String target)
  311.     {
  312.         int result = Collator.EQUAL;
  313.         CollationElementIterator targetCursor
  314.             = new CollationElementIterator(target, this);
  315.         CollationElementIterator sourceCursor
  316.             = new CollationElementIterator(source, this);
  317.         int sOrder = 0;
  318.         int tOrder = 0;
  319.         boolean gets = true, gett = true;
  320.         boolean checks = true, checkt = true;
  321.         while(true) {
  322.             if (gets) sOrder = sourceCursor.next(); else gets = true;
  323.             if (gett) tOrder = targetCursor.next(); else gett = true;
  324.             if ((sOrder == CollationElementIterator.NULLORDER)||
  325.                 (tOrder == CollationElementIterator.NULLORDER))
  326.                 break;
  327.             if (checks) sOrder = strengthOrder(sOrder);
  328.             if (checkt) tOrder = strengthOrder(tOrder);
  329.             checks = true;
  330.             checkt = true;
  331.             if (sOrder == CollationElementIterator.UNMAPPEDCHARVALUE)
  332.                 checks = false;
  333.             if (tOrder == CollationElementIterator.UNMAPPEDCHARVALUE)
  334.                 checkt = false;
  335.             if (sOrder == tOrder)
  336.                 continue;
  337.             if (CollationElementIterator.primaryOrder(sOrder) !=
  338.                 CollationElementIterator.primaryOrder(tOrder))
  339.             {
  340.                 if (sOrder == 0) {
  341.                     gett = false;
  342.                     continue;
  343.                 }
  344.                 if (tOrder == 0) {
  345.                     gets = false;
  346.                     continue;
  347.                 }
  348.                 if (sOrder < MAXIGNORABLE)  // sk is ignorable
  349.                 {
  350.                     if (tOrder < MAXIGNORABLE)  // tk is ignorable
  351.                     {
  352.                         result = checkSecTerDiff(sOrder, tOrder, result);
  353.                         continue;                   // both advances
  354.                     }
  355.                     else
  356.                     {
  357.                         if (isFrenchSec ||
  358.                             ((result == Collator.EQUAL) ||
  359.                              (strengthResult != Collator.SECONDARY)))
  360.                         {
  361.                             strengthResult = Collator.SECONDARY;
  362.                             result = Collator.GREATER;
  363.                         }
  364.                         gett = false;
  365.                         continue;
  366.                     }
  367.                 }
  368.                 else if (tOrder < MAXIGNORABLE)
  369.                 {
  370.                     // record differences
  371.                     if (isFrenchSec ||
  372.                         ((result == Collator.EQUAL) ||
  373.                          (strengthResult != Collator.SECONDARY)))
  374.                     {
  375.                         result = Collator.LESS;
  376.                         strengthResult = Collator.SECONDARY;
  377.                     }
  378.                     gets = false;
  379.                     continue;
  380.                 }
  381.                 if (CollationElementIterator.primaryOrder(sOrder) <
  382.                     CollationElementIterator.primaryOrder(tOrder))
  383.                     result = Collator.LESS;
  384.                 else
  385.                     result = Collator.GREATER;
  386.                 break;
  387.             }
  388.             else
  389.                 result = checkSecTerDiff(sOrder, tOrder, result);
  390.         } // while()
  391.         if (sOrder != CollationElementIterator.NULLORDER) {
  392.             if (tOrder == CollationElementIterator.NULLORDER) {
  393.                 // later check if ignorable, secondary or tertiary difference
  394.                 if (isIgnorable(sOrder) && !isFrenchSec)
  395.                     return result;
  396.                 if (strengthOrder(sOrder) != 0)
  397.                     result = Collator.GREATER;
  398.             }
  399.         }
  400.         if (tOrder != CollationElementIterator.NULLORDER) {
  401.             if (sOrder == CollationElementIterator.NULLORDER) {
  402.                 if (isIgnorable(tOrder) && !isFrenchSec)
  403.                     return result;
  404.                 if (strengthOrder(tOrder) != 0)
  405.                     result = Collator.LESS;
  406.             }
  407.         }
  408.         return result;
  409.     }
  410.     /**
  411.      * Transforms the string into a series of characters that can be compared
  412.      * with CollationKey.compareTo. This overrides java.text.Collator.getCollationKey.
  413.      * It can be overriden in a subclass.
  414.      */
  415.     public CollationKey getCollationKey(String source)
  416.     {
  417.         if (source == null)
  418.             return null;
  419.         primResult.setLength(0);
  420.         secResult.setLength(0);
  421.         terResult.setLength(0);
  422.         int order = 0;
  423.         boolean compareSec = (getStrength() >= Collator.SECONDARY);
  424.         boolean compareTer = (getStrength() >= Collator.TERTIARY);
  425.         int secOrder = CollationElementIterator.NULLORDER;
  426.         int terOrder = CollationElementIterator.NULLORDER;
  427.         CollationElementIterator sourceCursor = new
  428.             CollationElementIterator(source, this);
  429.         while ((order = sourceCursor.next()) !=
  430.                CollationElementIterator.NULLORDER)
  431.         {
  432.             secOrder = CollationElementIterator.secondaryOrder(order);
  433.             terOrder = CollationElementIterator.tertiaryOrder(order);
  434.             if (!isIgnorable(order))
  435.             {
  436.                 primResult.append((char)
  437.                      (CollationElementIterator.primaryOrder(order)
  438.                       + COLLATIONKEYOFFSET));
  439.                 if (compareSec)
  440.                     secResult.append((char)(secOrder+ COLLATIONKEYOFFSET));
  441.                 if (compareTer)
  442.                     terResult.append((char)(terOrder+ COLLATIONKEYOFFSET));
  443.             }
  444.             else
  445.             {
  446.                 if (compareSec)
  447.                     secResult.append((char)
  448.                         (secOrder+maxSecOrder+ COLLATIONKEYOFFSET));
  449.                 if (compareTer)
  450.                     terResult.append((char)
  451.                         (terOrder+maxTerOrder+ COLLATIONKEYOFFSET));
  452.             }
  453.         }
  454.         if (isFrenchSec)
  455.         {
  456.             // reverse the secondary and tertiary portion
  457.             reverse(secResult);
  458.             reverse(terResult);
  459.         }
  460.         primResult.append((char)0);
  461.         secResult.append((char)0);
  462.         secResult.append(terResult.toString());
  463.         primResult.append(secResult.toString());
  464.         return new CollationKey(source, primResult.toString());
  465.     }
  466.     /**
  467.      * Standard override; no change in semantics.
  468.      */
  469.     public Object clone() {
  470.         RuleBasedCollator other = (RuleBasedCollator) super.clone();
  471.         other.primResult = new StringBuffer(MAXTOKENLEN);
  472.         other.secResult = new StringBuffer(MAXTOKENLEN);
  473.         other.terResult = new StringBuffer(MAXTOKENLEN);
  474.         other.key = new StringBuffer(MAXKEYSIZE);
  475.         return other;
  476.     }
  477.  
  478.     /**
  479.      * Compares the equality of two collation objects.
  480.      * @param obj the table-based collation object to be compared with this.
  481.      * @return true if the current table-based collation object is the same
  482.      * as the table-based collation object obj; false otherwise.
  483.      */
  484.     public boolean equals(Object obj) {
  485.         if (!super.equals(obj)) return false;  // super does class check
  486.         RuleBasedCollator other = (RuleBasedCollator) obj;
  487.         // all other non-transient information is also contained in rules.
  488.         return (getRules().equals(other.getRules()));
  489.     }
  490.     /**
  491.      * Generates the hash code for the table-based collation object
  492.      */
  493.     public int hashCode() {
  494.         return getRules().hashCode();
  495.     }
  496.  
  497.     // ==============================================================
  498.     // private
  499.     // ==============================================================
  500.  
  501.     /**
  502.      * Create a table-based collation object with the given rules.
  503.      * @see java.util.RuleBasedCollator#RuleBasedCollator
  504.      * @exception ParseException If the rules format is incorrect.
  505.      */
  506.     private void build(String pattern) throws ParseException
  507.     {
  508.         mapping = new CompactIntArray((int)UNMAPPED);
  509.         int aStrength = Collator.IDENTICAL;
  510.         boolean isSource = true;
  511.         int i = 0;
  512.         String expChars;
  513.         String groupChars;
  514.         if (pattern.length() == 0)
  515.             throw new ParseException("Build rules empty.", 0);
  516.         /* Normalize the build rules.  Find occurances of all
  517.          *  decomposed characters and normalize the rules before
  518.          *  feeding into the builder.
  519.          */
  520.         pattern = DecompositionIterator.decompose(pattern, getDecomposition());
  521.         mPattern = new MergeCollation(pattern);
  522.         for (i = 0; i < mPattern.getCount(); ++i)
  523.         {
  524.             PatternEntry entry = mPattern.getItemAt(i);
  525.             if (entry != null) {
  526.                 groupChars = entry.getChars();
  527.                 if ((groupChars.length() > 1) &&
  528.                     (groupChars.charAt(groupChars.length()-1) == '@')) {
  529.                     isFrenchSec = true;
  530.                     groupChars = groupChars.substring(0, groupChars.length()-1);
  531.                 }
  532.                 expChars = entry.getExtension();
  533.                 if (expChars.length() != 0) {
  534.                     addExpandOrder(groupChars, expChars, entry.getStrength());
  535.                 } else if (groupChars.length() > 1) {
  536.                     addContractOrder(groupChars, entry.getStrength());
  537.                     lastChar = groupChars.charAt(0);
  538.                 } else {
  539.                     char ch = groupChars.charAt(0);
  540.                     addOrder(ch, entry.getStrength());
  541.                     lastChar = ch;
  542.                 }
  543.             }
  544.         }
  545.         commit();
  546.         mapping.compact();
  547.     }
  548.     /**
  549.      * Look up for unmapped values in the expanded character table.
  550.      */
  551.     private final void commit()
  552.     {
  553.         if (expandTable != null)
  554.         {
  555.             for (int i = 0; i < expandTable.size(); i++)
  556.             {
  557.                 int[] valueList = (int [])expandTable.elementAt(i);
  558.                 for (int j = 0; j < valueList.length; j++)
  559.                 {
  560.                     if ((valueList[j] < EXPANDCHARINDEX) &&
  561.                              (valueList[j] > CHARINDEX))
  562.                     {
  563.                         char ch = (char)(valueList[j] - CHARINDEX);
  564.                         int realValue = mapping.elementAt(ch);
  565.                         if (realValue == UNMAPPED)  // ignorable?
  566.                         {
  567.                             valueList[j] = IGNORABLEMASK & valueList[j-1];
  568.                         }
  569.                         else if (realValue >= CONTRACTCHARINDEX)
  570.                         {
  571.                             EntryPair pair = null;
  572.                             Vector groupList = (Vector)
  573.                                 contractTable.elementAt(realValue
  574.                                                         - CONTRACTCHARINDEX);
  575.                             pair = (EntryPair)groupList.lastElement();
  576.                             valueList[j] = pair.value;
  577.                         }
  578.                         else
  579.                         {
  580.                             valueList[j] = realValue;
  581.                         }
  582.                     }
  583.                 }
  584.             }
  585.         }
  586.     }
  587.     /**
  588.      *  Returns true if a character is a seperator.
  589.      */
  590.     private final boolean isSpecialChar(char c)
  591.     {
  592.         return (c=='/' || c==',' || c==';' || c=='<' ||
  593.                 c=='@' || c=='=');
  594.     }
  595.     /**
  596.      *  Increment of the last order based on the comparison level.
  597.      */
  598.     private final int increment(int aStrength, int lastValue)
  599.     {
  600.         switch(aStrength)
  601.         {
  602.         case Collator.PRIMARY:
  603.             lastValue += PRIMARYORDERINCREMENT;
  604.             lastValue &= PRIMARYORDERMASK;
  605.             break;
  606.         case Collator.SECONDARY:
  607.             lastValue += SECONDARYORDERINCREMENT;
  608.             lastValue &= SECONDARYDIFFERENCEONLY;
  609.             if (isOverIgnore)
  610.                 maxSecOrder++;
  611.             break;
  612.         case Collator.TERTIARY:
  613.             lastValue += TERTIARYORDERINCREMENT;
  614.             if (isOverIgnore)
  615.                 maxTerOrder++;
  616.             break;
  617.         }
  618.         return lastValue;
  619.     }
  620.     /**
  621.      *  Adds a character and its designated order into the collation table.
  622.      */
  623.     private final void addOrder(char ch,
  624.                                 int aStrength)
  625.     {
  626.         int order = mapping.elementAt(ch);
  627.         if (order == UNMAPPED)
  628.         {
  629.             currentOrder = increment(aStrength, currentOrder);
  630.             mapping.setElementAt(ch, currentOrder);
  631.         } else if (order < 0) {
  632.             int entry = order & SECONDARYRESETMASK;
  633.             int value = CONTRACTCHARINDEX + entry;
  634.             key.setLength(0);
  635.             key.append(ch);
  636.             Vector list = getContractValues(entry);
  637.             EntryPair pair = new EntryPair();
  638.             pair.entryName = key.toString();
  639.             currentOrder = increment(aStrength, currentOrder);
  640.             pair.value = currentOrder;
  641.             mapping.setElementAt(ch, value);
  642.             list.insertElementAt(pair, 0);
  643.         } else if (order > CONTRACTCHARINDEX) {
  644.             key.setLength(0);
  645.             key.append(ch);
  646.             addContractOrder(key.toString(), aStrength);
  647.         }
  648.     }
  649.     /**
  650.      *  Adds the contracting string into the collation table.
  651.      */
  652.     private final void addContractOrder(String groupChars,
  653.                                   int   aStrength)
  654.     {
  655.         if (contractTable == null)
  656.         {
  657.             contractTable = new Vector(INITIALTABLESIZE);
  658.         }
  659.         // Look for the entry, for example c as in ch entry
  660.         key.setLength(0);
  661.         key.append(groupChars.charAt(0));
  662.         int entry = UNMAPPED;
  663.         Vector tableEntry = null;
  664.         EntryPair pair = new EntryPair();
  665.         int i;
  666.         for (i = 0; i < contractTable.size(); i++)
  667.         {
  668.             tableEntry = (Vector)contractTable.elementAt(i);
  669.             if ((entry = getEntry(tableEntry, key.toString())) != UNMAPPED)
  670.                 break;
  671.         }
  672.         int lastValue = 0;
  673.         if (aStrength != IDENTICAL)
  674.             lastValue = increment(aStrength, currentOrder);
  675.         else
  676.         {
  677.             lastValue = mapping.elementAt(groupChars.charAt(0));
  678.             if (lastValue == UNMAPPED) {
  679.                 currentOrder = mapping.elementAt(lastChar);
  680.                 lastValue = increment(aStrength, currentOrder);
  681.             }
  682.         }
  683.         if (entry != UNMAPPED) // found one
  684.         {
  685.             pair.entryName = groupChars;
  686.             pair.value = lastValue;
  687.             tableEntry.insertElementAt(pair, 0);
  688.         }
  689.         else
  690.         {
  691.             Vector valueTable = new Vector(INITIALTABLESIZE);
  692.             int tmpValue = CONTRACTCHARINDEX + contractTable.size();
  693.             // put last char in the subdict
  694.             int order = mapping.elementAt(groupChars.charAt(0));
  695.             if (order == UNMAPPED) {
  696.                 pair = null;
  697.                 mapping.setElementAt(groupChars.charAt(0),
  698.                              PRIMARYORDERMASK + contractTable.size());
  699.             } else {
  700.                 pair.entryName = key.toString();
  701.                 mapping.setElementAt(groupChars.charAt(0), tmpValue);
  702.                 pair.value = order;
  703.                 valueTable.insertElementAt(pair, 0);
  704.             }
  705.             EntryPair swapPair = new EntryPair();
  706.             swapPair.entryName = groupChars;
  707.             swapPair.value = lastValue;
  708.             valueTable.insertElementAt(swapPair, 0);
  709.             contractTable.insertElementAt(valueTable, contractTable.size());
  710.         }
  711.         if (aStrength != IDENTICAL)
  712.             currentOrder = lastValue;
  713.     }
  714.  
  715.     private final int getEntry(Vector list, String name) {
  716.         for (int i = 0; i < list.size(); i++) {
  717.             EntryPair pair = (EntryPair)list.elementAt(i);
  718.             if (pair.entryName.equals(name)) {
  719.                 return i;
  720.             }
  721.         }
  722.         return UNMAPPED;
  723.     }
  724.     /**
  725.      *  Get the entry of hash table of the contracting string in the collation
  726.      *  table.
  727.      *  @param ch the starting character of the contracting string
  728.      */
  729.     Vector getContractValues(char ch)
  730.     {
  731.         int index = mapping.elementAt(ch);
  732.         return getContractValues(index - CONTRACTCHARINDEX);
  733.     }
  734.  
  735.     Vector getContractValues(int index)
  736.     {
  737.         if (index >= 0)
  738.         {
  739.             return (Vector)contractTable.elementAt(index);
  740.         }
  741.         else // not found
  742.         {
  743.             return null;
  744.         }
  745.     }
  746.  
  747.     /**
  748.      *  Adds the expanding string into the collation table.
  749.      */
  750.     private final void addExpandOrder(String contractChars,
  751.                                 String expandChars,
  752.                                 int   aStrength) throws ParseException
  753.     {
  754.         EntryPair pair = new EntryPair();
  755.         // INITIALTABLESIZE is an estimated number
  756.         if (expandTable == null)
  757.         {
  758.             expandTable = new Vector(INITIALTABLESIZE);
  759.         }
  760.         int[] valueList = new int[expandChars.length()+1];
  761.         // Expand flag + index
  762.         int tmpValue = EXPANDCHARINDEX + expandTable.size();
  763.         // need to check if the entry is key or not later
  764.         key.setLength(0);
  765.         int keyValue = UNMAPPED;
  766.         if (contractChars.length() > 1)
  767.         {
  768.             addContractOrder(contractChars, aStrength);
  769.             lastChar = contractChars.charAt(0);
  770.             Vector list = getContractValues(contractChars.charAt(0));
  771.             int entry = UNMAPPED;
  772.             entry = getEntry(list, contractChars);
  773.             if (entry != UNMAPPED) {
  774.                 pair = (EntryPair)list.elementAt(entry);
  775.                 keyValue = pair.value;
  776.             }
  777.             pair.entryName = contractChars;
  778.             pair.value = tmpValue;
  779.         }
  780.         else
  781.         {
  782.             char ch = contractChars.charAt(0);
  783.             if (mapping.elementAt(ch) == UNMAPPED) {
  784.                 addOrder(ch, aStrength);
  785.                 lastChar = ch;
  786.             }
  787.             keyValue = mapping.elementAt(lastChar);
  788.             mapping.setElementAt(lastChar, tmpValue);
  789.         }
  790.         valueList[0] = keyValue;
  791.         for (int i = 0; i < expandChars.length(); i++)
  792.         {
  793.             int mapValue = mapping.elementAt(expandChars.charAt(i));
  794.             if (mapValue >= CONTRACTCHARINDEX)
  795.             {
  796.                 key.append(expandChars.charAt(i));
  797.                 int foundValue = CHARINDEX + expandChars.charAt(i);
  798.                 Vector list = getContractValues(expandChars.charAt(i));
  799.                 if (list != null) {
  800.                     int entry = UNMAPPED;
  801.                     entry = getEntry(list, key.toString());
  802.                     if (entry != UNMAPPED) {
  803.                         pair = (EntryPair)list.elementAt(entry);
  804.                         foundValue = pair.value;
  805.                     }
  806.                 }
  807.                 key.setLength(0);
  808.                 valueList[i+1] = foundValue;
  809.             }
  810.             else if (mapValue != UNMAPPED)
  811.             {
  812.                 valueList[i+1] = mapValue;
  813.             }
  814.             else
  815.             {
  816.                 valueList[i+1] = CHARINDEX + (int)(expandChars.charAt(i));
  817.             }
  818.         }
  819.         expandTable.insertElementAt(valueList, expandTable.size());
  820.     }
  821.  
  822.     /**
  823.      *  Get the entry of hash table of the expanding string in the collation
  824.      *  table.
  825.      *  @param ch the starting character of the expanding string
  826.      */
  827.     final int[] getExpandValueList(char ch)
  828.     {
  829.         int expIndex = mapping.elementAt(ch);
  830.         if ((expIndex >= EXPANDCHARINDEX) &&
  831.             (expIndex < CONTRACTCHARINDEX))
  832.         {
  833.             int tmpIndex = expIndex - EXPANDCHARINDEX;
  834.             return (int[])expandTable.elementAt(tmpIndex);
  835.         }
  836.         else
  837.         {
  838.             return null;
  839.         }
  840.     }
  841.     /**
  842.      *  Get the entry of hash table of the expanding string in the collation
  843.      *  table.
  844.      *  @param idx the index of the expanding string value list
  845.      */
  846.     final int[] getExpandValueList(int idx)
  847.     {
  848.         if (idx < expandTable.size())
  849.         {
  850.             return (int[])expandTable.elementAt(idx);
  851.         }
  852.         else
  853.         {
  854.             return null;
  855.         }
  856.     }
  857.     /**
  858.      *  Get the comparison order in the desired strength.  Ignore the other
  859.      *  differences.
  860.      *  @param order The order value
  861.      */
  862.     private final int strengthOrder(int order)
  863.     {
  864.         if (getStrength() == Collator.PRIMARY)
  865.         {
  866.             order &= PRIMARYDIFFERENCEONLY;
  867.         } else if (getStrength() == Collator.SECONDARY)
  868.         {
  869.             order &= SECONDARYDIFFERENCEONLY;
  870.         }
  871.         return order;
  872.     }
  873.     /**
  874.      *  Check if a comparison order is ignorable.
  875.      *  @return true if a character is ignorable, false otherwise.
  876.      */
  877.     final boolean isIgnorable(int order)
  878.     {
  879.         return (((int)CollationElementIterator.primaryOrder(order) == 0) ?
  880.                 true : false);
  881.     }
  882.     /**
  883.      *  Get the comarison order of a character from the collation table.
  884.      *  @return the comparison order of a character.
  885.      */
  886.     final int getUnicodeOrder(char ch)
  887.     {
  888.         return mapping.elementAt(ch);
  889.     }
  890.  
  891.     /**
  892.      * Check for the secondary and tertiary differences of source and
  893.      * target comparison orders.
  894.      * @return Collator.LESS if sOrder < tOrder; EQUAL if sOrder == tOrder;
  895.      * Collator.GREATER if sOrder > tOrder.
  896.      */
  897.     private final int checkSecTerDiff(int sOrder,
  898.                                       int tOrder,
  899.                                       int result)
  900.     {
  901.         int endResult = result;
  902.         if (CollationElementIterator.secondaryOrder(sOrder) !=
  903.             CollationElementIterator.secondaryOrder(tOrder))
  904.         {
  905.             if (isFrenchSec ||
  906.                 ((endResult == Collator.EQUAL) ||
  907.                  (strengthResult != Collator.SECONDARY)))
  908.             {
  909.                 strengthResult = Collator.SECONDARY;
  910.                 if (CollationElementIterator.secondaryOrder(sOrder) <
  911.                     CollationElementIterator.secondaryOrder(tOrder))
  912.                     endResult = Collator.LESS;
  913.                 else
  914.                     endResult = Collator.GREATER;
  915.             }
  916.         }
  917.         else if ((CollationElementIterator.tertiaryOrder(sOrder) !=
  918.                   CollationElementIterator.tertiaryOrder(tOrder)) &&
  919.          ((endResult == Collator.EQUAL) || isFrenchSec))
  920.         {
  921.             strengthResult = Collator.TERTIARY;
  922.             if (CollationElementIterator.tertiaryOrder(sOrder) <
  923.                 CollationElementIterator.tertiaryOrder(tOrder))
  924.                 endResult = Collator.LESS;
  925.             else
  926.                 endResult = Collator.GREATER;
  927.         }
  928.         return endResult;
  929.     }
  930.     /**
  931.      * Reverse a string.
  932.      */
  933.     private final void reverse (StringBuffer result)
  934.     {
  935.         String store = result.toString();
  936.         result.setLength(0);
  937.         for (int i = store.length() - 1; i >= 0; i--) {
  938.             result.append(store.charAt(i));
  939.         }
  940.     }
  941.  
  942.     static int CHARINDEX = 0x70000000;  // need look up in .commit()
  943.     static int EXPANDCHARINDEX = 0x7E000000; // Expand index follows
  944.     static int CONTRACTCHARINDEX = 0x7F000000;  // contract indexes follow
  945.     static int UNMAPPED = 0xFFFFFFFF;
  946.  
  947.     private final static int SHORT_MAX_VALUE = 32767;
  948.     private final static int PRIMARYORDERINCREMENT = 0x00010000;
  949.     private final static int MAXIGNORABLE = 0x00010000;
  950.     private final static int SECONDARYORDERINCREMENT = 0x00000100;
  951.     private final static int TERTIARYORDERINCREMENT = 0x00000001;
  952.     final static int PRIMARYORDERMASK = 0xffff0000;
  953.     final static int SECONDARYORDERMASK = 0x0000ff00;
  954.     final static int TERTIARYORDERMASK = 0x000000ff;
  955.     private final static int SECONDARYRESETMASK = 0x0000ffff;
  956.     private final static int IGNORABLEMASK = 0x0000ffff;
  957.     private final static int PRIMARYDIFFERENCEONLY = 0xffff0000;
  958.     private final static int SECONDARYDIFFERENCEONLY = 0xffffff00;
  959.     private final static int INITIALTABLESIZE = 20;
  960.     private final static int MAXKEYSIZE = 5;
  961.     static int PRIMARYORDERSHIFT = 16;
  962.     static int SECONDARYORDERSHIFT = 8;
  963.     private final static int MAXTOKENLEN = 256;
  964.     private final static int MAXRULELEN = 512;
  965.     private final static int COLLATIONKEYOFFSET = 1;
  966.  
  967.     private boolean isFrenchSec = false;
  968.     private String ruleTable = null;
  969.  
  970.     private CompactIntArray mapping = null;
  971.     private Vector   contractTable = null;
  972.     private Vector   expandTable = null;
  973.  
  974.     // transients, only used in build or processing
  975.     private transient MergeCollation mPattern = null;
  976.     private transient boolean isOverIgnore = false;
  977.     private transient int currentOrder = 0;
  978.     private transient short maxSecOrder = 0;
  979.     private transient short maxTerOrder = 0;
  980.     private transient char lastChar;
  981.     private transient StringBuffer key = new StringBuffer(MAXKEYSIZE);
  982.     private transient int strengthResult = Collator.IDENTICAL;
  983.     private transient StringBuffer primResult = new StringBuffer(MAXTOKENLEN);
  984.     private transient StringBuffer secResult = new StringBuffer(MAXTOKENLEN);
  985.     private transient StringBuffer terResult = new StringBuffer(MAXTOKENLEN);
  986. }
  987.  
  988.