Collator suitable
* for string collation in a wide variety of languages. An instance of
* this class is normally returned by the getInstance method
* of Collator with rules predefined for the requested
* locale. However, an instance of this class can be created manually
* with any desired rules.
*
* Rules take the form of a String with the following syntax
*
* As for the text argument itself, this is any sequence of Unicode * characters not in the following ranges: 0x0009-0x000D, 0x0020-0x002F, * 0x003A-0x0040, 0x005B-0x0060, and 0x007B-0x007E. If these characters are * desired, they must be enclosed in single quotes. If any whitespace is * encountered, it is ignored. (For example, "a b" is equal to "ab"). *
* The reset operation inserts the following rule at the point where the
* text argument to it exists in the previously declared rule string. This
* makes it easy to add new rules to an existing string by simply including
* them in a reset sequence at the end. Note that the text argument, or
* at least the first character of it, must be present somewhere in the
* previously declared rules in order to be inserted properly. If this
* is not satisfied, a ParseException will be thrown.
*
* This system of configuring RuleBasedCollator is needlessly
* complex and the people at Taligent who developed it (along with the folks
* at Sun who accepted it into the Java standard library) deserve a slow
* and agonizing death.
*
* Here are a couple of example of rule strings: *
* "< a < b < c" - This string says that a is greater than b which is * greater than c, with all differences being primary differences. *
* "< a,A < b,B < c,C" - This string says that 'A' is greater than 'a' with * a tertiary strength comparison. Both 'b' and 'B' are greater than 'a' and * 'A' during a primary strength comparison. But 'B' is greater than 'b' * under a tertiary strength comparison. *
* "< a < c & a < b " - This sequence is identical in function to the * "< a < b < c" rule string above. The '&' reset symbol indicates that * the rule "< b" is to be inserted after the text argument "a" in the * previous rule string segment. *
* "< a < b & y < z" - This is an error. The character 'y' does not appear * anywhere in the previous rule string segment so the rule following the * reset rule cannot be inserted. *
* For a description of the various comparison strength types, see the
* documentation for the Collator class.
*
* As an additional complication to this already overly complex rule scheme, * if any characters precede the first rule, these characters are considered * ignorable. They will be treated as if they did not exist during * comparisons. For example, "- < a < b ..." would make '-' an ignorable * character such that the strings "high-tech" and "hightech" would * be considered identical. *
* A ParseException will be thrown for any of the following
* conditions:
*
RuleBasedCollator
* with the specified collation rules. Note that an application normally
* obtains an instance of RuleBasedCollator by calling the
* getInstance method of Collator. That method
* automatically loads the proper set of rules for the desired locale.
*
* @param rules The collation rule string.
*
* @exception ParseException If the rule string contains syntax errors.
*/
public RuleBasedCollator (String rules) throws ParseException
{
if (rules.equals (""))
throw new ParseException ("empty rule set", 0);
this.rules = rules;
this.frenchAccents = false;
// We keep each rule in order in a vector. At the end we traverse
// the vector and compute collation values from it.
int insertion_index = 0;
Vector vec = new Vector ();
StringBuffer argument = new StringBuffer ();
int len = rules.length();
for (int index = 0; index < len; ++index)
{
char c = rules.charAt(index);
// Just skip whitespace.
if (Character.isWhitespace(c))
continue;
// Modifier.
if (c == '@')
{
frenchAccents = true;
continue;
}
// Check for relation or reset operator.
if (! (c == '<' || c == ';' || c == ',' || c == '=' || c == '&'))
throw new ParseException ("invalid character", index);
++index;
while (index < len)
{
if (! Character.isWhitespace(rules.charAt(index)))
break;
++index;
}
if (index == len)
throw new ParseException ("missing argument", index);
int save = index;
index = text_argument (rules, index, argument);
if (argument.length() == 0)
throw new ParseException ("invalid character", save);
String arg = argument.toString();
int item_index = -1;
for (int j = 0; j < vec.size(); ++j)
{
CollationElement e = (CollationElement) vec.elementAt (j);
if (arg.equals (e.key))
{
item_index = j;
break;
}
}
if (c != '&')
{
// If the argument already appears in the vector, then we
// must remove it in order to re-order.
if (item_index != -1)
{
vec.removeElementAt(item_index);
if (insertion_index >= item_index)
--insertion_index;
}
CollationElement r = new CollationElement (arg, c);
vec.insertElementAt(r, insertion_index);
++insertion_index;
}
else
{
// Reset.
if (item_index == -1)
throw
new ParseException ("argument to reset not previously seen",
save);
insertion_index = item_index + 1;
}
// Ugly: in this case the resulting INDEX comes from
// text_argument, which returns the index of the next
// character we should examine.
--index;
}
// Now construct a hash table that maps strings onto their
// collation values.
int primary = 0;
int secondary = 0;
int tertiary = 0;
this.map = new Hashtable ();
this.prefixes = new Hashtable ();
Enumeration e = vec.elements();
while (e.hasMoreElements())
{
CollationElement r = (CollationElement) e.nextElement();
switch (r.relation)
{
case '<':
++primary;
secondary = 0;
tertiary = 0;
break;
case ';':
++secondary;
tertiary = 0;
break;
case ',':
++tertiary;
break;
case '=':
break;
}
// This must match CollationElementIterator.
map.put(r.key, new Integer (primary << 16
| secondary << 8 | tertiary));
// Make a map of all lookaheads we might need.
for (int i = r.key.length() - 1; i >= 1; --i)
prefixes.put(r.key.substring(0, i), Boolean.TRUE);
}
}
/**
* This method creates a copy of this object.
*
* @return A copy of this object.
*/
public Object clone()
{
RuleBasedCollator c = (RuleBasedCollator) super.clone ();
c.map = (Hashtable) map.clone ();
c.prefixes = (Hashtable) map.clone ();
return c;
}
// A helper for CollationElementIterator.next().
int ceiNext (CollationElementIterator cei)
{
if (cei.lookahead_set)
{
cei.lookahead_set = false;
return cei.lookahead;
}
int save = cei.index;
int max = cei.text.length();
String s = null;
// It is possible to have a case where `abc' has a mapping, but
// neither `ab' nor `abd' do. In this case we must treat `abd' as
// nothing special.
boolean found = false;
int i;
for (i = save + 1; i <= max; ++i)
{
s = cei.text.substring(save, i);
if (prefixes.get(s) == null)
break;
found = true;
}
// Assume s != null.
Object obj = map.get(s);
// The special case.
while (found && obj == null && s.length() > 1)
{
--i;
s = cei.text.substring(save, i);
obj = map.get(s);
}
// Update state.
cei.index = i;
if (obj == null)
{
// This idea, and the values, come from JDK.
// assert (s.length() == 1)
cei.lookahead_set = true;
cei.lookahead = s.charAt(0) << 8;
return 0x7fff << 16;
}
return ((Integer) obj).intValue();
}
// A helper for compareTo() that returns the next character that has
// a nonzero ordering at the indicated strength. This is also used
// in CollationKey.
static final int next (CollationElementIterator iter, int strength)
{
while (true)
{
int os = iter.next();
if (os == CollationElementIterator.NULLORDER)
return os;
int c = 0;
switch (strength)
{
case PRIMARY:
c = os & ~0xffff;
break;
case SECONDARY:
c = os & ~0x00ff;
break;
case TERTIARY:
case IDENTICAL:
c = os;
break;
}
if (c != 0)
return c;
}
}
/**
* This method returns an integer which indicates whether the first
* specified String is less than, greater than, or equal to
* the second. The value depends not only on the collation rules in
* effect, but also the strength and decomposition settings of this object.
*
* @param s1 The first String to compare.
* @param s2 A second String to compare to the first.
*
* @return A negative integer if s1 < s2, a positive integer
* if s1 > s2, or 0 if s1 == s2.
*/
public int compare (String source, String target)
{
CollationElementIterator cs, ct;
cs = new CollationElementIterator (source, this);
ct = new CollationElementIterator (target, this);
while (true)
{
int os = next (cs, strength);
int ot = next (ct, strength);
if (os == CollationElementIterator.NULLORDER
&& ot == CollationElementIterator.NULLORDER)
break;
else if (os == CollationElementIterator.NULLORDER)
{
// Source string is shorter, so return "less than".
return -1;
}
else if (ot == CollationElementIterator.NULLORDER)
{
// Target string is shorter, so return "greater than".
return 1;
}
if (os != ot)
return os - ot;
}
return 0;
}
/**
* This method tests this object for equality against the specified
* object. This will be true if and only if the specified object is
* another reference to this object.
*
* @param obj The Object to compare against this object.
*
* @return true if the specified object is equal to this object, false otherwise.
*/
public boolean equals (Object obj)
{
if (! (obj instanceof RuleBasedCollator) || ! super.equals(obj))
return false;
RuleBasedCollator rbc = (RuleBasedCollator) obj;
// FIXME: this is probably wrong. Instead we should compare maps
// directly.
return (frenchAccents == rbc.frenchAccents
&& rules.equals(rbc.rules));
}
/**
* This method returns an instance for CollationElementIterator
* for the specified String under the collation rules for this
* object.
*
* @param str The String to return the CollationElementIterator instance for.
*
* @return A CollationElementIterator for the specified String.
*/
public CollationElementIterator getCollationElementIterator (String source)
{
StringBuffer expand = new StringBuffer (source.length());
int max = source.length();
for (int i = 0; i < max; ++i)
decomposeCharacter (source.charAt(i), expand);
return new CollationElementIterator (expand.toString(), this);
}
/**
* This method returns an instance of CollationElementIterator
* for the String represented by the specified
* CharacterIterator.
*
* @param ci The CharacterIterator with the desired String.
*
* @return A CollationElementIterator for the specified String.
*/
public CollationElementIterator getCollationElementIterator (CharacterIterator source)
{
StringBuffer expand = new StringBuffer ();
for (char c = source.first ();
c != CharacterIterator.DONE;
c = source.next ())
decomposeCharacter (c, expand);
return new CollationElementIterator (expand.toString(), this);
}
/**
* This method returns an instance of CollationKey for the
* specified String. The object returned will have a
* more efficient mechanism for its comparison function that could
* provide speed benefits if multiple comparisons are performed, such
* as during a sort.
*
* @param str The String to create a CollationKey for.
*
* @return A CollationKey for the specified String.
*/
public CollationKey getCollationKey (String source)
{
return new CollationKey (getCollationElementIterator (source), source,
strength);
}
/**
* This method returns a String containing the collation rules
* for this object.
*
* @return The collation rules for this object.
*/
public String getRules()
{
return rules;
}
/**
* This method returns a hash value for this object.
*
* @return A hash value for this object.
*/
public int hashCode()
{
return (frenchAccents ? 1231 : 1237
^ rules.hashCode()
^ map.hashCode()
^ prefixes.hashCode());
}
private final boolean is_special (char c)
{
// Rules from JCL book.
return ((c >= 0x0021 && c <= 0x002f)
|| (c >= 0x003a && c <= 0x0040)
|| (c >= 0x005b && c <= 0x0060)
|| (c >= 0x007b && c <= 0x007e));
}
private final int text_argument (String rules, int index,
StringBuffer result)
{
result.setLength(0);
int len = rules.length();
while (index < len)
{
char c = rules.charAt (index);
if (c == '\''
&& index + 2 < len
&& rules.charAt (index + 2) == '\'')
{
result.append (rules.charAt (index + 1));
index += 2;
}
else if (is_special (c))
return index;
else if (!Character.isWhitespace (c))
result.append (c);
++index;
}
return index;
}
}