jars/icu4j-4_4_2-src/main/classes/core/src/com/ibm/icu/text/NFRuleSet.java

   1 /*\r
   2  *******************************************************************************\r
   3  * Copyright (C) 1996-2010, International Business Machines Corporation and    *\r
   4  * others. All Rights Reserved.                                                *\r
   5  *******************************************************************************\r
   6  */\r
   7 package com.ibm.icu.text;\r
   8 \r
   9 import java.text.ParsePosition;\r
  10 import java.util.Vector;\r
  11 \r
  12 import com.ibm.icu.impl.UCharacterProperty;\r
  13 import com.ibm.icu.impl.Utility;\r
  14 \r
  15 /**\r
  16  * A collection of rules used by a RuleBasedNumberFormat to format and\r
  17  * parse numbers.  It is the responsibility of a RuleSet to select an\r
  18  * appropriate rule for formatting a particular number and dispatch\r
  19  * control to it, and to arbitrate between different rules when parsing\r
  20  * a number.\r
  21  */\r
  22 \r
  23 final class NFRuleSet {\r
  24     //-----------------------------------------------------------------------\r
  25     // data members\r
  26     //-----------------------------------------------------------------------\r
  27 \r
  28     /**\r
  29      * The rule set's name\r
  30      */\r
  31     private String name;\r
  32 \r
  33     /**\r
  34      * The rule set's regular rules\r
  35      */\r
  36     private NFRule[] rules;\r
  37 \r
  38     /**\r
  39      * The rule set's negative-number rule\r
  40      */\r
  41     private NFRule negativeNumberRule = null;\r
  42 \r
  43     /**\r
  44      * The rule set's fraction rules: element 0 is the proper fraction\r
  45      * (0.x) rule, element 1 is the improper fraction (x.x) rule, and\r
  46      * element 2 is the master (x.0) rule.\r
  47      */\r
  48     private NFRule[] fractionRules = new NFRule[3];\r
  49 \r
  50     /**\r
  51      * True if the rule set is a fraction rule set.  A fraction rule set\r
  52      * is a rule set that is used to format the fractional part of a\r
  53      * number.  It is called from a >> substitution in another rule set's\r
  54      * fraction rule, and is only called upon to format values between\r
  55      * 0 and 1.  A fraction rule set has different rule-selection\r
  56      * behavior than a regular rule set.\r
  57      */\r
  58     private boolean isFractionRuleSet = false;\r
  59     \r
  60     /**\r
  61      * Used to limit recursion for bad rule sets.\r
  62      */\r
  63     private int recursionCount = 0;\r
  64 \r
  65     /**\r
  66       * Limit of recursion.\r
  67       */\r
  68     private static final int RECURSION_LIMIT = 50;\r
  69 \r
  70     //-----------------------------------------------------------------------\r
  71     // construction\r
  72     //-----------------------------------------------------------------------\r
  73 \r
  74     /*\r
  75      * Constructs a rule set.\r
  76      * @param descriptions An array of Strings representing rule set\r
  77      * descriptions.  On exit, this rule set's entry in the array will\r
  78      * have been stripped of its rule set name and any trailing whitespace.\r
  79      * @param index The index into "descriptions" of the description\r
  80      * for the rule to be constructed\r
  81      */\r
  82     public NFRuleSet(String[] descriptions, int index) throws IllegalArgumentException {\r
  83         String description = descriptions[index];\r
  84 \r
  85     if (description.length() == 0) {\r
  86       throw new IllegalArgumentException("Empty rule set description");\r
  87     }\r
  88 \r
  89         // if the description begins with a rule set name (the rule set\r
  90         // name can be omitted in formatter descriptions that consist\r
  91         // of only one rule set), copy it out into our "name" member\r
  92         // and delete it from the description\r
  93         if (description.charAt(0) == '%') {\r
  94             int pos = description.indexOf(':');\r
  95             if (pos == -1) {\r
  96                 throw new IllegalArgumentException("Rule set name doesn't end in colon");\r
  97             } else {\r
  98                 name = description.substring(0, pos);\r
  99                 while (pos < description.length() && UCharacterProperty.isRuleWhiteSpace(description.\r
 100                                 charAt(++pos))) {\r
 101                 }\r
 102                 description = description.substring(pos);\r
 103                 descriptions[index] = description;\r
 104             }\r
 105 \r
 106         // if the description doesn't begin with a rule set name, its\r
 107         // name is "%default"\r
 108         } else {\r
 109             name = "%default";\r
 110         }\r
 111 \r
 112         if (description.length() == 0) {\r
 113             throw new IllegalArgumentException("Empty rule set description");\r
 114         }\r
 115 \r
 116         // all of the other members of NFRuleSet are initialized\r
 117         // by parseRules()\r
 118     }\r
 119 \r
 120     /**\r
 121      * Construct the subordinate data structures used by this object.\r
 122      * This function is called by the RuleBasedNumberFormat constructor\r
 123      * after all the rule sets have been created to actually parse\r
 124      * the description and build rules from it.  Since any rule set\r
 125      * can refer to any other rule set, we have to have created all of\r
 126      * them before we can create anything else.\r
 127      * @param description The textual description of this rule set\r
 128      * @param owner The formatter that owns this rule set\r
 129      */\r
 130     public void parseRules(String                description,\r
 131                            RuleBasedNumberFormat owner) {\r
 132         // start by creating a Vector whose elements are Strings containing\r
 133         // the descriptions of the rules (one rule per element).  The rules\r
 134         // are separated by semicolons (there's no escape facility: ALL\r
 135         // semicolons are rule delimiters)\r
 136         Vector<String> ruleDescriptions = new Vector<String>();\r
 137 \r
 138         int oldP = 0;\r
 139         int p = description.indexOf(';');\r
 140         while (oldP != -1) {\r
 141             if (p != -1) {\r
 142                 ruleDescriptions.addElement(description.substring(oldP, p));\r
 143                 oldP = p + 1;\r
 144             } else {\r
 145                 if (oldP < description.length()) {\r
 146                     ruleDescriptions.addElement(description.substring(oldP));\r
 147                 }\r
 148                 oldP = p;\r
 149             }\r
 150             p = description.indexOf(';', p + 1);\r
 151         }\r
 152 \r
 153         // now go back through and build a vector of the rules themselves\r
 154         // (the number of elements in the description list isn't necessarily\r
 155         // the number of rules-- some descriptions may expend into two rules)\r
 156         Vector<NFRule> tempRules = new Vector<NFRule>();\r
 157 \r
 158         // we keep track of the rule before the one we're currently working\r
 159         // on solely to support >>> substitutions\r
 160         NFRule predecessor = null;\r
 161         for (int i = 0; i < ruleDescriptions.size(); i++) {\r
 162             // makeRules (a factory method on NFRule) will return either\r
 163             // a single rule or an array of rules.  Either way, add them\r
 164             // to our rule vector\r
 165             Object temp = NFRule.makeRules(ruleDescriptions.elementAt(i),\r
 166                             this, predecessor, owner);\r
 167 \r
 168             if (temp instanceof NFRule) {\r
 169                 tempRules.addElement((NFRule)temp);\r
 170                 predecessor = (NFRule)temp;\r
 171             }\r
 172             else if (temp instanceof NFRule[]) {\r
 173                 NFRule[] rulesToAdd = (NFRule[])temp;\r
 174 \r
 175                 for (int j = 0; j < rulesToAdd.length; j++) {\r
 176                     tempRules.addElement(rulesToAdd[j]);\r
 177                     predecessor = rulesToAdd[j];\r
 178                 }\r
 179             }\r
 180         }\r
 181         // now we can bag the description list\r
 182         ruleDescriptions = null;\r
 183 \r
 184         // for rules that didn't specify a base value, their base values\r
 185         // were initialized to 0.  Make another pass through the list and\r
 186         // set all those rules' base values.  We also remove any special\r
 187         // rules from the list and put them into their own member variables\r
 188         long defaultBaseValue = 0;\r
 189 \r
 190         // (this isn't a for loop because we might be deleting items from\r
 191         // the vector-- we want to make sure we only increment i when\r
 192         // we _didn't_ delete aything from the vector)\r
 193         int i = 0;\r
 194         while (i < tempRules.size()) {\r
 195             NFRule rule = tempRules.elementAt(i);\r
 196 \r
 197             switch ((int)rule.getBaseValue()) {\r
 198                 // if the rule's base value is 0, fill in a default\r
 199                 // base value (this will be 1 plus the preceding\r
 200                 // rule's base value for regular rule sets, and the\r
 201                 // same as the preceding rule's base value in fraction\r
 202                 // rule sets)\r
 203                 case 0:\r
 204                     rule.setBaseValue(defaultBaseValue);\r
 205                     if (!isFractionRuleSet) {\r
 206                         ++defaultBaseValue;\r
 207                     }\r
 208                     ++i;\r
 209                     break;\r
 210 \r
 211                 // if it's the negative-number rule, copy it into its own\r
 212                 // data member and delete it from the list\r
 213                 case NFRule.NEGATIVE_NUMBER_RULE:\r
 214                     negativeNumberRule = rule;\r
 215                     tempRules.removeElementAt(i);\r
 216                     break;\r
 217 \r
 218                 // if it's the improper fraction rule, copy it into the\r
 219                 // correct element of fractionRules\r
 220                 case NFRule.IMPROPER_FRACTION_RULE:\r
 221                     fractionRules[0] = rule;\r
 222                     tempRules.removeElementAt(i);\r
 223                     break;\r
 224 \r
 225                 // if it's the proper fraction rule, copy it into the\r
 226                 // correct element of fractionRules\r
 227                 case NFRule.PROPER_FRACTION_RULE:\r
 228                     fractionRules[1] = rule;\r
 229                     tempRules.removeElementAt(i);\r
 230                     break;\r
 231 \r
 232                 // if it's the master rule, copy it into the\r
 233                 // correct element of fractionRules\r
 234                 case NFRule.MASTER_RULE:\r
 235                     fractionRules[2] = rule;\r
 236                     tempRules.removeElementAt(i);\r
 237                     break;\r
 238 \r
 239                 // if it's a regular rule that already knows its base value,\r
 240                 // check to make sure the rules are in order, and update\r
 241                 // the default base value for the next rule\r
 242                 default:\r
 243                     if (rule.getBaseValue() < defaultBaseValue) {\r
 244                         throw new IllegalArgumentException("Rules are not in order, base: " + \r
 245                                rule.getBaseValue() + " < " + defaultBaseValue);\r
 246                     }\r
 247                     defaultBaseValue = rule.getBaseValue();\r
 248                     if (!isFractionRuleSet) {\r
 249                         ++defaultBaseValue;\r
 250                     }\r
 251                     ++i;\r
 252                     break;\r
 253             }\r
 254         }\r
 255 \r
 256         // finally, we can copy the rules from the vector into a\r
 257         // fixed-length array\r
 258         rules = new NFRule[tempRules.size()];\r
 259         tempRules.copyInto((Object[])rules);\r
 260     }\r
 261 \r
 262     /**\r
 263      * Flags this rule set as a fraction rule set.  This function is\r
 264      * called during the construction process once we know this rule\r
 265      * set is a fraction rule set.  We don't know a rule set is a\r
 266      * fraction rule set until we see it used somewhere.  This function\r
 267      * is not ad must not be called at any time other than during\r
 268      * construction of a RuleBasedNumberFormat.\r
 269      */\r
 270     public void makeIntoFractionRuleSet() {\r
 271         isFractionRuleSet = true;\r
 272     }\r
 273 \r
 274     //-----------------------------------------------------------------------\r
 275     // boilerplate\r
 276     //-----------------------------------------------------------------------\r
 277 \r
 278     /**\r
 279      * Compares two rule sets for equality.\r
 280      * @param that The other rule set\r
 281      * @return true if the two rule sets are functionally equivalent.\r
 282      */\r
 283     public boolean equals(Object that) {\r
 284         // if different classes, they're not equal\r
 285         if (!(that instanceof NFRuleSet)) {\r
 286             return false;\r
 287         } else {\r
 288             // otherwise, compare the members one by one...\r
 289             NFRuleSet that2 = (NFRuleSet)that;\r
 290 \r
 291             if (!name.equals(that2.name)\r
 292         || !Utility.objectEquals(negativeNumberRule, that2.negativeNumberRule)\r
 293         || !Utility.objectEquals(fractionRules[0], that2.fractionRules[0])\r
 294         || !Utility.objectEquals(fractionRules[1], that2.fractionRules[1])\r
 295         || !Utility.objectEquals(fractionRules[2], that2.fractionRules[2])\r
 296         || rules.length != that2.rules.length\r
 297                 || isFractionRuleSet != that2.isFractionRuleSet) {\r
 298 \r
 299                 return false;\r
 300             }\r
 301 \r
 302             // ...then compare the rule lists...\r
 303             for (int i = 0; i < rules.length; i++) {\r
 304                 if (!rules[i].equals(that2.rules[i])) {\r
 305                     return false;\r
 306                 }\r
 307             }\r
 308 \r
 309             // ...and if we make it here, tney're equal\r
 310             return true;\r
 311         }\r
 312     }\r
 313 \r
 314 \r
 315     /**\r
 316      * Builds a textual representation of a rule set.\r
 317      * @return A textual representation of a rule set.  This won't\r
 318      * necessarily be the same description that the rule set was\r
 319      * constructed with, but it will produce the same results.\r
 320      */\r
 321     public String toString() {\r
 322         StringBuilder result = new StringBuilder();\r
 323 \r
 324         // the rule set name goes first...\r
 325         result.append(name + ":\n");\r
 326 \r
 327         // followed by the regular rules...\r
 328         for (int i = 0; i < rules.length; i++) {\r
 329             result.append("    " + rules[i].toString() + "\n");\r
 330         }\r
 331 \r
 332         // followed by the special rules (if they exist)\r
 333         if (negativeNumberRule != null) {\r
 334             result.append("    " + negativeNumberRule.toString() + "\n");\r
 335         }\r
 336         if (fractionRules[0] != null) {\r
 337             result.append("    " + fractionRules[0].toString() + "\n");\r
 338         }\r
 339         if (fractionRules[1] != null) {\r
 340             result.append("    " + fractionRules[1].toString() + "\n");\r
 341         }\r
 342         if (fractionRules[2] != null) {\r
 343             result.append("    " + fractionRules[2].toString() + "\n");\r
 344         }\r
 345 \r
 346         return result.toString();\r
 347     }\r
 348 \r
 349     //-----------------------------------------------------------------------\r
 350     // simple accessors\r
 351     //-----------------------------------------------------------------------\r
 352 \r
 353     /**\r
 354      * Says whether this rule set is a fraction rule set.\r
 355      * @return true if this rule is a fraction rule set; false if it isn't\r
 356      */\r
 357     public boolean isFractionSet() {\r
 358         return isFractionRuleSet;\r
 359     }\r
 360 \r
 361     /**\r
 362      * Returns the rule set's name\r
 363      * @return The rule set's name\r
 364      */\r
 365     public String getName() {\r
 366         return name;\r
 367     }\r
 368 \r
 369     /**\r
 370      * Return true if the rule set is public.\r
 371      * @return true if the rule set is public\r
 372      */\r
 373     public boolean isPublic() {\r
 374         return !name.startsWith("%%");\r
 375     }\r
 376 \r
 377     /**\r
 378      * Return true if the rule set can be used for parsing.\r
 379      * @return true if the rule set can be used for parsing.\r
 380      */\r
 381     public boolean isParseable() {\r
 382         //TODO:\r
 383         //  In CLDR 1.7, we have no distinction between\r
 384         //  parseable/unparseable.  Rules which have one of\r
 385         //  3 suffixes below are know as unparseable for now.\r
 386         //  We should add the information in CLDR data.\r
 387         return !(name.endsWith("-prefixpart")\r
 388                 || name.endsWith("-postfixpart")\r
 389                 || name.endsWith("-postfx"));\r
 390     }\r
 391 \r
 392     //-----------------------------------------------------------------------\r
 393     // formatting\r
 394     //-----------------------------------------------------------------------\r
 395 \r
 396     /**\r
 397      * Formats a long.  Selects an appropriate rule and dispatches\r
 398      * control to it.\r
 399      * @param number The number being formatted\r
 400      * @param toInsertInto The string where the result is to be placed\r
 401      * @param pos The position in toInsertInto where the result of\r
 402      * this operation is to be inserted\r
 403      */\r
 404     public void format(long number, StringBuffer toInsertInto, int pos) {\r
 405         NFRule applicableRule = findNormalRule(number);\r
 406 \r
 407         if (++recursionCount >= RECURSION_LIMIT) {\r
 408             recursionCount = 0;\r
 409             throw new IllegalStateException("Recursion limit exceeded when applying ruleSet " + name);\r
 410         }\r
 411         applicableRule.doFormat(number, toInsertInto, pos);\r
 412         --recursionCount;\r
 413     }\r
 414 \r
 415     /**\r
 416      * Formats a double.  Selects an appropriate rule and dispatches\r
 417      * control to it.\r
 418      * @param number The number being formatted\r
 419      * @param toInsertInto The string where the result is to be placed\r
 420      * @param pos The position in toInsertInto where the result of\r
 421      * this operation is to be inserted\r
 422      */\r
 423     public void format(double number, StringBuffer toInsertInto, int pos) {\r
 424         NFRule applicableRule = findRule(number);\r
 425 \r
 426         if (++recursionCount >= RECURSION_LIMIT) {\r
 427             recursionCount = 0;\r
 428             throw new IllegalStateException("Recursion limit exceeded when applying ruleSet " + name);\r
 429         }\r
 430         applicableRule.doFormat(number, toInsertInto, pos);\r
 431         --recursionCount;\r
 432     }\r
 433 \r
 434     /**\r
 435      * Selects an apropriate rule for formatting the number.\r
 436      * @param number The number being formatted.\r
 437      * @return The rule that should be used to format it\r
 438      */\r
 439     private NFRule findRule(double number) {\r
 440         // if this is a fraction rule set, use findFractionRuleSetRule()\r
 441         if (isFractionRuleSet) {\r
 442             return findFractionRuleSetRule(number);\r
 443         }\r
 444 \r
 445         // if the number is negative, return the negative number rule\r
 446         // (if there isn't a negative-number rule, we pretend it's a\r
 447         // positive number)\r
 448         if (number < 0) {\r
 449             if (negativeNumberRule != null) {\r
 450                 return negativeNumberRule;\r
 451             } else {\r
 452                 number = -number;\r
 453             }\r
 454         }\r
 455 \r
 456         // if the number isn't an integer, we use one f the fraction rules...\r
 457         if (number != Math.floor(number)) {\r
 458             // if the number is between 0 and 1, return the proper\r
 459             // fraction rule\r
 460             if (number < 1 && fractionRules[1] != null) {\r
 461                 return fractionRules[1];\r
 462             }\r
 463 \r
 464             // otherwise, return the improper fraction rule\r
 465             else if (fractionRules[0] != null) {\r
 466                 return fractionRules[0];\r
 467             }\r
 468         }\r
 469 \r
 470         // if there's a master rule, use it to format the number\r
 471         if (fractionRules[2] != null) {\r
 472             return fractionRules[2];\r
 473 \r
 474         // and if we haven't yet returned a rule, use findNormalRule()\r
 475         // to find the applicable rule\r
 476         } else {\r
 477             return findNormalRule(Math.round(number));\r
 478         }\r
 479     }\r
 480 \r
 481     /**\r
 482      * If the value passed to findRule() is a positive integer, findRule()\r
 483      * uses this function to select the appropriate rule.  The result will\r
 484      * generally be the rule with the highest base value less than or equal\r
 485      * to the number.  There is one exception to this: If that rule has\r
 486      * two substitutions and a base value that is not an even multiple of\r
 487      * its divisor, and the number itself IS an even multiple of the rule's\r
 488      * divisor, then the result will be the rule that preceded the original\r
 489      * result in the rule list.  (This behavior is known as the "rollback\r
 490      * rule", and is used to handle optional text: a rule with optional\r
 491      * text is represented internally as two rules, and the rollback rule\r
 492      * selects appropriate between them.  This avoids things like "two\r
 493      * hundred zero".)\r
 494      * @param number The number being formatted\r
 495      * @return The rule to use to format this number\r
 496      */\r
 497     private NFRule findNormalRule(long number) {\r
 498         // if this is a fraction rule set, use findFractionRuleSetRule()\r
 499         // to find the rule (we should only go into this clause if the\r
 500         // value is 0)\r
 501         if (isFractionRuleSet) {\r
 502             return findFractionRuleSetRule(number);\r
 503         }\r
 504 \r
 505         // if the number is negative, return the negative-number rule\r
 506         // (if there isn't one, pretend the number is positive)\r
 507         if (number < 0) {\r
 508             if (negativeNumberRule != null) {\r
 509                 return negativeNumberRule;\r
 510             } else {\r
 511                 number = -number;\r
 512             }\r
 513         }\r
 514 \r
 515         // we have to repeat the preceding two checks, even though we\r
 516         // do them in findRule(), because the version of format() that\r
 517         // takes a long bypasses findRule() and goes straight to this\r
 518         // function.  This function does skip the fraction rules since\r
 519         // we know the value is an integer (it also skips the master\r
 520         // rule, since it's considered a fraction rule.  Skipping the\r
 521         // master rule in this function is also how we avoid infinite\r
 522         // recursion)\r
 523 \r
 524         // binary-search the rule list for the applicable rule\r
 525         // (a rule is used for all values from its base value to\r
 526         // the next rule's base value)\r
 527         int lo = 0;\r
 528         int hi = rules.length;\r
 529     if (hi > 0) {\r
 530         while (lo < hi) {\r
 531         int mid = (lo + hi) / 2;\r
 532         if (rules[mid].getBaseValue() == number) {\r
 533             return rules[mid];\r
 534         }\r
 535         else if (rules[mid].getBaseValue() > number) {\r
 536             hi = mid;\r
 537         }\r
 538         else {\r
 539             lo = mid + 1;\r
 540         }\r
 541         }\r
 542         if (hi == 0) { // bad rule set\r
 543         throw new IllegalStateException("The rule set " + name + " cannot format the value " + number);\r
 544         }\r
 545         NFRule result = rules[hi - 1];\r
 546 \r
 547         // use shouldRollBack() to see whether we need to invoke the\r
 548         // rollback rule (see shouldRollBack()'s documentation for\r
 549         // an explanation of the rollback rule).  If we do, roll back\r
 550         // one rule and return that one instead of the one we'd normally\r
 551         // return\r
 552         if (result.shouldRollBack(number)) {\r
 553         if (hi == 1) { // bad rule set\r
 554             throw new IllegalStateException("The rule set " + name + " cannot roll back from the rule '" +\r
 555                             result + "'");\r
 556         }\r
 557         result = rules[hi - 2];\r
 558         }\r
 559         return result;\r
 560     }\r
 561     // else use the master rule\r
 562     return fractionRules[2];\r
 563     }\r
 564 \r
 565     /**\r
 566      * If this rule is a fraction rule set, this function is used by\r
 567      * findRule() to select the most appropriate rule for formatting\r
 568      * the number.  Basically, the base value of each rule in the rule\r
 569      * set is treated as the denominator of a fraction.  Whichever\r
 570      * denominator can produce the fraction closest in value to the\r
 571      * number passed in is the result.  If there's a tie, the earlier\r
 572      * one in the list wins.  (If there are two rules in a row with the\r
 573      * same base value, the first one is used when the numerator of the\r
 574      * fraction would be 1, and the second rule is used the rest of the\r
 575      * time.\r
 576      * @param number The number being formatted (which will always be\r
 577      * a number between 0 and 1)\r
 578      * @return The rule to use to format this number\r
 579      */\r
 580     private NFRule findFractionRuleSetRule(double number) {\r
 581         // the obvious way to do this (multiply the value being formatted\r
 582         // by each rule's base value until you get an integral result)\r
 583         // doesn't work because of rounding error.  This method is more\r
 584         // accurate\r
 585 \r
 586         // find the least common multiple of the rules' base values\r
 587         // and multiply this by the number being formatted.  This is\r
 588         // all the precision we need, and we can do all of the rest\r
 589         // of the math using integer arithmetic\r
 590         long leastCommonMultiple = rules[0].getBaseValue();\r
 591         for (int i = 1; i < rules.length; i++) {\r
 592             leastCommonMultiple = lcm(leastCommonMultiple, rules[i].getBaseValue());\r
 593         }\r
 594         long numerator = Math.round(number * leastCommonMultiple);\r
 595 \r
 596         // for each rule, do the following...\r
 597         long tempDifference;\r
 598         long difference = Long.MAX_VALUE;\r
 599         int winner = 0;\r
 600         for (int i = 0; i < rules.length; i++) {\r
 601             // "numerator" is the numerator of the fraction is the\r
 602             // denominator is the LCD.  The numerator if the the rule's\r
 603             // base value is the denomiator is "numerator" times the\r
 604             // base value divided bythe LCD.  Here we check to see if\r
 605             // that's an integer, and if not, how close it is to being\r
 606             // an integer.\r
 607             tempDifference = numerator * rules[i].getBaseValue() % leastCommonMultiple;\r
 608 \r
 609             // normalize the result of the above calculation: we want\r
 610             // the numerator's distance from the CLOSEST multiple\r
 611             // of the LCD\r
 612             if (leastCommonMultiple - tempDifference < tempDifference) {\r
 613                 tempDifference = leastCommonMultiple - tempDifference;\r
 614             }\r
 615 \r
 616             // if this is as close as we've come, keep track of how close\r
 617             // that is, and the line number of the rule that did it.  If\r
 618             // we've scored a direct hit, we don't have to look at any more\r
 619             // rules\r
 620             if (tempDifference < difference) {\r
 621                 difference = tempDifference;\r
 622                 winner = i;\r
 623                 if (difference == 0) {\r
 624                     break;\r
 625                 }\r
 626             }\r
 627         }\r
 628 \r
 629         // if we have two successive rules that both have the winning base\r
 630         // value, then the first one (the one we found above) is used if\r
 631         // the numerator of the fraction is 1 and the second one is used if\r
 632         // the numerator of the fraction is anything else (this lets us\r
 633         // do things like "one third"/"two thirds" without haveing to define\r
 634         // a whole bunch of extra rule sets)\r
 635         if (winner + 1 < rules.length\r
 636                 && rules[winner + 1].getBaseValue() == rules[winner].getBaseValue()) {\r
 637             if (Math.round(number * rules[winner].getBaseValue()) < 1\r
 638                     || Math.round(number * rules[winner].getBaseValue()) >= 2) {\r
 639                 ++winner;\r
 640             }\r
 641         }\r
 642 \r
 643         // finally, return the winning rule\r
 644         return rules[winner];\r
 645     }\r
 646 \r
 647     /**\r
 648      * Calculates the least common multiple of x and y.\r
 649      */\r
 650     private static long lcm(long x, long y) {\r
 651         // binary gcd algorithm from Knuth, "The Art of Computer Programming,"\r
 652         // vol. 2, 1st ed., pp. 298-299\r
 653         long x1 = x;\r
 654         long y1 = y;\r
 655 \r
 656         int p2 = 0;\r
 657         while ((x1 & 1) == 0 && (y1 & 1) == 0) {\r
 658             ++p2;\r
 659             x1 >>= 1;\r
 660             y1 >>= 1;\r
 661         }\r
 662 \r
 663         long t;\r
 664         if ((x1 & 1) == 1) {\r
 665             t = -y1;\r
 666         } else {\r
 667             t = x1;\r
 668         }\r
 669 \r
 670         while (t != 0) {\r
 671             while ((t & 1) == 0) {\r
 672                 t >>= 1;\r
 673             }\r
 674             if (t > 0) {\r
 675                 x1 = t;\r
 676             } else {\r
 677                 y1 = -t;\r
 678             }\r
 679             t = x1 - y1;\r
 680         }\r
 681         long gcd = x1 << p2;\r
 682 \r
 683         // x * y == gcd(x, y) * lcm(x, y)\r
 684         return x / gcd * y;\r
 685     }\r
 686 \r
 687     //-----------------------------------------------------------------------\r
 688     // parsing\r
 689     //-----------------------------------------------------------------------\r
 690 \r
 691     /**\r
 692      * Parses a string.  Matches the string to be parsed against each\r
 693      * of its rules (with a base value less than upperBound) and returns\r
 694      * the value produced by the rule that matched the most charcters\r
 695      * in the source string.\r
 696      * @param text The string to parse\r
 697      * @param parsePosition The initial position is ignored and assumed\r
 698      * to be 0.  On exit, this object has been updated to point to the\r
 699      * first character position this rule set didn't consume.\r
 700      * @param upperBound Limits the rules that can be allowed to match.\r
 701      * Only rules whose base values are strictly less than upperBound\r
 702      * are considered.\r
 703      * @return The numerical result of parsing this string.  This will\r
 704      * be the matching rule's base value, composed appropriately with\r
 705      * the results of matching any of its substitutions.  The object\r
 706      * will be an instance of Long if it's an integral value; otherwise,\r
 707      * it will be an instance of Double.  This function always returns\r
 708      * a valid object: If nothing matched the input string at all,\r
 709      * this function returns new Long(0), and the parse position is\r
 710      * left unchanged.\r
 711      */\r
 712     public Number parse(String text, ParsePosition parsePosition, double upperBound) {\r
 713         // try matching each rule in the rule set against the text being\r
 714         // parsed.  Whichever one matches the most characters is the one\r
 715         // that determines the value we return.\r
 716 \r
 717         ParsePosition highWaterMark = new ParsePosition(0);\r
 718         Number result = new Long(0);\r
 719         Number tempResult = null;\r
 720 \r
 721         // dump out if there's no text to parse\r
 722         if (text.length() == 0) {\r
 723             return result;\r
 724         }\r
 725 \r
 726         // start by trying the nehative number rule (if there is one)\r
 727         if (negativeNumberRule != null) {\r
 728             tempResult = negativeNumberRule.doParse(text, parsePosition, false, upperBound);\r
 729             if (parsePosition.getIndex() > highWaterMark.getIndex()) {\r
 730                 result = tempResult;\r
 731                 highWaterMark.setIndex(parsePosition.getIndex());\r
 732             }\r
 733 // commented out because the error-index API on ParsePosition isn't there in 1.1.x\r
 734 //            if (parsePosition.getErrorIndex() > highWaterMark.getErrorIndex()) {\r
 735 //                highWaterMark.setErrorIndex(parsePosition.getErrorIndex());\r
 736 //            }\r
 737             parsePosition.setIndex(0);\r
 738         }\r
 739 \r
 740         // then try each of the fraction rules\r
 741         for (int i = 0; i < 3; i++) {\r
 742             if (fractionRules[i] != null) {\r
 743                 tempResult = fractionRules[i].doParse(text, parsePosition, false, upperBound);\r
 744                 if (parsePosition.getIndex() > highWaterMark.getIndex()) {\r
 745                     result = tempResult;\r
 746                     highWaterMark.setIndex(parsePosition.getIndex());\r
 747                 }\r
 748 // commented out because the error-index API on ParsePosition isn't there in 1.1.x\r
 749 //            if (parsePosition.getErrorIndex() > highWaterMark.getErrorIndex()) {\r
 750 //                highWaterMark.setErrorIndex(parsePosition.getErrorIndex());\r
 751 //            }\r
 752                 parsePosition.setIndex(0);\r
 753             }\r
 754         }\r
 755 \r
 756         // finally, go through the regular rules one at a time.  We start\r
 757         // at the end of the list because we want to try matching the most\r
 758         // sigificant rule first (this helps ensure that we parse\r
 759         // "five thousand three hundred six" as\r
 760         // "(five thousand) (three hundred) (six)" rather than\r
 761         // "((five thousand three) hundred) (six)").  Skip rules whose\r
 762         // base values are higher than the upper bound (again, this helps\r
 763         // limit ambiguity by making sure the rules that match a rule's\r
 764         // are less significant than the rule containing the substitutions)/\r
 765         for (int i = rules.length - 1; i >= 0 && highWaterMark.getIndex() < text.length(); i--) {\r
 766             if (!isFractionRuleSet && rules[i].getBaseValue() >= upperBound) {\r
 767                 continue;\r
 768             }\r
 769 \r
 770             tempResult = rules[i].doParse(text, parsePosition, isFractionRuleSet, upperBound);\r
 771             if (parsePosition.getIndex() > highWaterMark.getIndex()) {\r
 772                 result = tempResult;\r
 773                 highWaterMark.setIndex(parsePosition.getIndex());\r
 774             }\r
 775 // commented out because the error-index API on ParsePosition isn't there in 1.1.x\r
 776 //            if (parsePosition.getErrorIndex() > highWaterMark.getErrorIndex()) {\r
 777 //                highWaterMark.setErrorIndex(parsePosition.getErrorIndex());\r
 778 //            }\r
 779             parsePosition.setIndex(0);\r
 780         }\r
 781 \r
 782         // finally, update the parse postion we were passed to point to the\r
 783         // first character we didn't use, and return the result that\r
 784         // cporresponds to that string of characters\r
 785         parsePosition.setIndex(highWaterMark.getIndex());\r
 786 // commented out because the error-index API on ParsePosition isn't there in 1.1.x\r
 787 //        if (parsePosition.getIndex() == 0) {\r
 788 //            parsePosition.setErrorIndex(highWaterMark.getErrorIndex());\r
 789 //        }\r
 790 \r
 791         return result;\r
 792     }\r
 793 }\r