libjava/java/text/RuleBasedCollator.java

   1 // RuleBasedCollator.java - Concrete class for locale-based string compare.
   2
   3 /* Copyright (C) 1999  Cygnus Solutions
   4
   5    This file is part of libgcj.
   6
   7 This software is copyrighted work licensed under the terms of the
   8 Libgcj License.  Please consult the file "LIBGCJ_LICENSE" for
   9 details.  */
  10
  11 package java.text;
  12
  13 import java.util.Enumeration;
  14 import java.util.Hashtable;
  15 import java.util.Vector;
  16
  17 /**
  18  * @author Tom Tromey <tromey@cygnus.com>
  19  * @date March 25, 1999
  20  */
  21 /* Written using "Java Class Libraries", 2nd edition, plus online
  22  * API docs for JDK 1.2 from http://www.javasoft.com.
  23  * Status: Believed complete and correct
  24  */
  25
  26 class RBCElement
  27 {
  28   String key;
  29   char relation;
  30
  31   RBCElement (String key, char relation)
  32   {
  33     this.key = key;
  34     this.relation = relation;
  35   }
  36 }
  37
  38 public class RuleBasedCollator extends Collator
  39 {
  40   public Object clone ()
  41   {
  42     return new RuleBasedCollator (this);
  43   }
  44
  45   // A helper for CollationElementIterator.next().
  46   static int ceiNext (CollationElementIterator cei)
  47   {
  48     if (cei.lookahead_set)
  49       {
  50         cei.lookahead_set = false;
  51         return cei.lookahead;
  52       }
  53
  54     int save = cei.index;
  55     int max = cei.text.length();
  56     String s = null;
  57
  58     // It is possible to have a case where `abc' has a mapping, but
  59     // neither `ab' nor `abd' do.  In this case we must treat `abd' as
  60     // nothing special.
  61     boolean found = false;
  62
  63     int i;
  64     for (i = save; i < max; ++i)
  65       {
  66         s = cei.text.substring(save, i);
  67         if (prefixes.get(s) == null)
  68           break;
  69         found = true;
  70       }
  71     // Assume s != null.
  72
  73     Object obj = map.get(s);
  74     // The special case.
  75     while (found && obj == null && s.length() > 1)
  76       {
  77         --i;
  78         s = cei.text.substring(save, i);
  79         obj = map.get(s);
  80       }
  81
  82     // Update state.
  83     cei.index = i;
  84
  85     if (obj == null)
  86       {
  87         // This idea, and the values, come from JDK.
  88         // assert (s.length() == 1)
  89         cei.lookahead_set = true;
  90         cei.lookahead = s.charAt(0) << 8;
  91         return 0x7fff << 16;
  92       }
  93
  94     return ((Integer) obj).intValue();
  95   }
  96
  97   // A helper for compareTo() that returns the next character that has
  98   // a nonzero ordering at the indicated strength.  This is also used
  99   // in CollationKey.
 100   static final int next (CollationElementIterator iter, int strength)
 101   {
 102     while (true)
 103       {
 104         int os = iter.next();
 105         if (os == CollationElementIterator.NULLORDER)
 106           return os;
 107         int c = 0;
 108         switch (strength)
 109           {
 110           case PRIMARY:
 111             c |= CollationElementIterator.primaryOrder(os);
 112             /* Fall through.  */
 113           case SECONDARY:
 114             c |= CollationElementIterator.secondaryOrder(os);
 115             /* Fall through.  */
 116           case TERTIARY:
 117             c |= CollationElementIterator.tertiaryOrder(os);
 118             break;
 119           case IDENTICAL:
 120             c = os;
 121           }
 122         if (c != 0)
 123           return c;
 124       }
 125   }
 126
 127   public int compare (String source, String target)
 128   {
 129     CollationElementIterator cs, ct;
 130
 131     cs = new CollationElementIterator (source);
 132     ct = new CollationElementIterator (target);
 133
 134     while (true)
 135       {
 136         int os = next (cs, strength);
 137         int ot = next (ct, strength);
 138
 139         if (os == CollationElementIterator.NULLORDER
 140             && ot == CollationElementIterator.NULLORDER)
 141           break;
 142         else if (os == CollationElementIterator.NULLORDER)
 143           return 1;
 144         else if (ot == CollationElementIterator.NULLORDER)
 145           return -1;
 146
 147         if (os != ot)
 148           return os - ot;
 149       }
 150
 151     return 0;
 152   }
 153
 154   public boolean equals (Object obj)
 155   {
 156     if (! (obj instanceof RuleBasedCollator) || ! super.equals(obj))
 157       return false;
 158     RuleBasedCollator rbc = (RuleBasedCollator) obj;
 159     // FIXME: this is probably wrong.  Instead we should compare maps
 160     // directly.
 161     return (frenchAccents == rbc.frenchAccents
 162             && rules.equals(rbc.rules));
 163   }
 164
 165   public CollationElementIterator getCollationElementIterator (String source)
 166   {
 167     StringBuffer expand = new StringBuffer (source.length());
 168     int max = source.length();
 169     for (int i = 0; i < max; ++i)
 170       decomposeCharacter (source.charAt(i), expand);
 171     return new CollationElementIterator (expand.toString());
 172   }
 173
 174   public CollationKey getCollationKey (String source)
 175   {
 176     return new CollationKey (getCollationElementIterator (source), source,
 177                              strength);
 178   }
 179
 180   public String getRules ()
 181   {
 182     return rules;
 183   }
 184
 185   public int hashCode ()
 186   {
 187     return (frenchAccents ? 1231 : 1237
 188             ^ rules.hashCode()
 189             ^ map.hashCode()
 190             ^ prefixes.hashCode());
 191   }
 192
 193   private final boolean is_special (char c)
 194   {
 195     // Rules from JCL book.
 196     return ((c >= 0x0009 && c <= 0x000d)
 197             || (c >= 0x0020 && c <= 0x002f)
 198             || (c >= 0x003a && c <= 0x0040)
 199             || (c >= 0x005b && c <= 0x0060)
 200             || (c >= 0x007b && c <= 0x007e));
 201   }
 202
 203   private final int text_argument (String rules, int index,
 204                                    StringBuffer result)
 205   {
 206     result.setLength(0);
 207     int len = rules.length();
 208     while (index < len)
 209       {
 210         char c = rules.charAt(index);
 211         if (c == '\'' && index + 2 < len
 212             && rules.charAt(index + 2) == '\''
 213             && is_special (rules.charAt(index + 1)))
 214           index += 2;
 215         else if (is_special (c) || Character.isWhitespace(c))
 216           return index;
 217         result.append(c);
 218         ++index;
 219       }
 220     return index;
 221   }
 222
 223   public RuleBasedCollator (String rules) throws ParseException
 224   {
 225     this.rules = rules;
 226     this.frenchAccents = false;
 227
 228     // We keep each rule in order in a vector.  At the end we traverse
 229     // the vector and compute collation values from it.
 230     int insertion_index = 0;
 231     Vector vec = new Vector ();
 232
 233     StringBuffer argument = new StringBuffer ();
 234
 235     int len = rules.length();
 236     for (int index = 0; index < len; ++index)
 237       {
 238         char c = rules.charAt(index);
 239
 240         // Just skip whitespace.
 241         if (Character.isWhitespace(c))
 242           continue;
 243
 244         // Modifier.
 245         if (c == '@')
 246           {
 247             frenchAccents = true;
 248             continue;
 249           }
 250
 251         // Check for relation or reset operator.
 252         if (! (c == '<' || c == ';' || c == ',' || c == '=' || c == '&'))
 253           throw new ParseException ("invalid character", index);
 254
 255         ++index;
 256         while (index < len)
 257           {
 258             if (! Character.isWhitespace(rules.charAt(index)))
 259               break;
 260             ++index;
 261           }
 262         if (index == len)
 263           throw new ParseException ("missing argument", index);
 264
 265         int save = index;
 266         index = text_argument (rules, index, argument);
 267         if (argument.length() == 0)
 268           throw new ParseException ("invalid character", save);
 269         String arg = argument.toString();
 270         int item_index = vec.indexOf(arg);
 271         if (c != '&')
 272           {
 273             // If the argument already appears in the vector, then we
 274             // must remove it in order to re-order.
 275             if (item_index != -1)
 276               {
 277                 vec.removeElementAt(item_index);
 278                 if (insertion_index >= item_index)
 279                   --insertion_index;
 280               }
 281             RBCElement r = new RBCElement (arg, c);
 282             vec.insertElementAt(r, insertion_index);
 283             ++insertion_index;
 284           }
 285         else
 286           {
 287             // Reset.
 288             if (item_index == -1)
 289               throw
 290                 new ParseException ("argument to reset not previously seen",
 291                                     save);
 292             insertion_index = item_index + 1;
 293           }
 294
 295         // Ugly: in this case the resulting INDEX comes from
 296         // text_argument, which returns the index of the next
 297         // character we should examine.
 298         --index;
 299       }
 300
 301     // Now construct a hash table that maps strings onto their
 302     // collation values.
 303     int primary = 0;
 304     int secondary = 0;
 305     int tertiary = 0;
 306     this.map = new Hashtable ();
 307     this.prefixes = new Hashtable ();
 308     Enumeration e = vec.elements();
 309     while (e.hasMoreElements())
 310       {
 311         RBCElement r = (RBCElement) e.nextElement();
 312         switch (r.relation)
 313           {
 314           case '<':
 315             ++primary;
 316             secondary = 0;
 317             tertiary = 0;
 318             break;
 319           case ';':
 320             ++secondary;
 321             tertiary = 0;
 322             break;
 323           case ',':
 324             ++tertiary;
 325             break;
 326           case '=':
 327             break;
 328           }
 329         // This must match CollationElementIterator.
 330         map.put(r.key, new Integer (primary << 16
 331                                     | secondary << 8 | tertiary));
 332
 333         // Make a map of all lookaheads we might need.
 334         for (int i = r.key.length() - 1; i >= 1; --i)
 335           prefixes.put(r.key.substring(0, i), Boolean.TRUE);
 336       }
 337   }
 338
 339   // This is a helper for clone.
 340   private RuleBasedCollator (RuleBasedCollator other)
 341   {
 342     frenchAccents = other.frenchAccents;
 343     rules = other.rules;
 344     decmp = other.decmp;
 345     strength = other.strength;
 346     map = other.map;
 347     prefixes = other.prefixes;
 348   }
 349
 350   // True if we are using French-style accent ordering.
 351   private boolean frenchAccents;
 352
 353   // It's easier to just save the rules than to try to recreate them.
 354   private String rules;
 355
 356   // This maps strings onto collation values.
 357   private Hashtable map;
 358   // An entry in this hash means that more lookahead is required for
 359   // the prefix string.
 360   private Hashtable prefixes;
 361 }