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. *
* "< a & A @ < e & E < f& F" - This sequence is equivalent to the following * "< a & A < E & e < f & F". *
* 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:
*
ce_table. It is used to compute the
* ordering value of unspecified character.
*/
private int last_primary_value;
/**
* This is the value of the last secondary sequence of the
* primary 0, entered into
* ce_table. It is used to compute the
* ordering value of an unspecified accented character.
*/
private int last_tertiary_value;
/**
* This variable is true if accents need to be sorted
* in the other direction.
*/
private boolean inverseAccentComparison;
/**
* This collation element is special to unknown sequence.
* The JDK uses it to mark and sort the characters which has
* no collation rules.
*/
static final CollationElement SPECIAL_UNKNOWN_SEQ =
new CollationElement("", (short) 32767, (short) 0, (short) 0,
(short) 0, null, false);
/**
* This method initializes a new instance of 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;
buildCollationVector(parseString(rules));
buildPrefixAccess();
}
/**
* This method returns the number of common characters at the beginning
* of the string of the two parameters.
*
* @param prefix A string considered as a prefix to test against
* the other string.
* @param s A string to test the prefix against.
* @return The number of common characters.
*/
static int findPrefixLength(String prefix, String s)
{
int index;
int len = prefix.length();
for (index = 0; index < len && index < s.length(); ++index)
{
if (prefix.charAt(index) != s.charAt(index))
return index;
}
return index;
}
/**
* Here we are merging two sets of sorting instructions: 'patch' into 'main'. This methods
* checks whether it is possible to find an anchor point for the rules to be merged and
* then insert them at that precise point.
*
* @param offset Offset in the string containing rules of the beginning of the rules
* being merged in.
* @param starter Text of the rules being merged.
* @param main Repository of all already parsed rules.
* @param patch Rules to be merged into the repository.
* @throws ParseException if it is impossible to find an anchor point for the new rules.
*/
private void mergeRules(int offset, String starter, ArrayList main, ArrayList patch)
throws ParseException
{
int insertion_point = -1;
int max_length = 0;
/* We must check that no rules conflict with another already present. If it
* is the case delete the old rule.
*/
/* For the moment good old O(N^2) algorithm.
*/
for (int i = 0; i < patch.size(); i++)
{
int j = 0;
while (j < main.size())
{
CollationSorter rule1 = (CollationSorter) patch.get(i);
CollationSorter rule2 = (CollationSorter) main.get(j);
if (rule1.textElement.equals(rule2.textElement))
main.remove(j);
else
j++;
}
}
// Find the insertion point... O(N)
for (int i = 0; i < main.size(); i++)
{
CollationSorter sorter = (CollationSorter) main.get(i);
int length = findPrefixLength(starter, sorter.textElement);
if (length > max_length)
{
max_length = length;
insertion_point = i+1;
}
}
if (insertion_point < 0)
throw new ParseException("no insertion point found for " + starter, offset);
if (max_length < starter.length())
{
/*
* We need to expand the first entry. It must be sorted
* like if it was the reference key itself (like the spec
* said. So the first entry is special: the element is
* replaced by the specified text element for the sorting.
* This text replace the old one for comparisons. However
* to preserve the behaviour we replace the first key (corresponding
* to the found prefix) by a new code rightly ordered in the
* sequence. The rest of the subsequence must be appended
* to the end of the sequence.
*/
CollationSorter sorter = (CollationSorter) patch.get(0);
CollationSorter expansionPrefix =
(CollationSorter) main.get(insertion_point-1);
sorter.expansionOrdering = starter.substring(max_length); // Skip the first good prefix element
main.add(insertion_point, sorter);
/*
* This is a new set of rules. Append to the list.
*/
patch.remove(0);
insertion_point++;
}
// Now insert all elements of patch at the insertion point.
for (int i = 0; i < patch.size(); i++)
main.add(i+insertion_point, patch.get(i));
}
/**
* This method parses a string and build a set of sorting instructions. The parsing
* may only be partial on the case the rules are to be merged sometime later.
*
* @param stop_on_reset If this parameter is true then the parser stops when it
* encounters a reset instruction. In the other case, it tries to parse the subrules
* and merged it in the same repository.
* @param v Output vector for the set of instructions.
* @param base_offset Offset in the string to begin parsing.
* @param rules Rules to be parsed.
* @return -1 if the parser reached the end of the string, an integer representing the
* offset in the string at which it stopped parsing.
* @throws ParseException if something turned wrong during the parsing. To get details
* decode the message.
*/
private int subParseString(boolean stop_on_reset, ArrayList v,
int base_offset, String rules)
throws ParseException
{
boolean ignoreChars = (base_offset == 0);
int operator = -1;
StringBuffer sb = new StringBuffer();
boolean doubleQuote = false;
boolean eatingChars = false;
boolean nextIsModifier = false;
boolean isModifier = false;
int i;
main_parse_loop:
for (i = 0; i < rules.length(); i++)
{
char c = rules.charAt(i);
int type = -1;
if (!eatingChars &&
((c >= 0x09 && c <= 0x0D) || (c == 0x20)))
continue;
isModifier = nextIsModifier;
nextIsModifier = false;
if (eatingChars && c != '\'')
{
doubleQuote = false;
sb.append(c);
continue;
}
if (doubleQuote && eatingChars)
{
sb.append(c);
doubleQuote = false;
continue;
}
switch (c)
{
case '!':
throw new ParseException
("Modifier '!' is not yet supported by Classpath", i + base_offset);
case '<':
type = CollationSorter.GREATERP;
break;
case ';':
type = CollationSorter.GREATERS;
break;
case ',':
type = CollationSorter.GREATERT;
break;
case '=':
type = CollationSorter.EQUAL;
break;
case '\'':
eatingChars = !eatingChars;
doubleQuote = true;
break;
case '@':
if (ignoreChars)
throw new ParseException
("comparison list has not yet been started. You may only use"
+ "(<,;=&)", i + base_offset);
// Inverse the order of secondaries from now on.
nextIsModifier = true;
type = CollationSorter.INVERSE_SECONDARY;
break;
case '&':
type = CollationSorter.RESET;
if (stop_on_reset)
break main_parse_loop;
break;
default:
if (operator < 0)
throw new ParseException
("operator missing at " + (i + base_offset), i + base_offset);
if (! eatingChars
&& ((c >= 0x21 && c <= 0x2F)
|| (c >= 0x3A && c <= 0x40)
|| (c >= 0x5B && c <= 0x60)
|| (c >= 0x7B && c <= 0x7E)))
throw new ParseException
("unquoted punctuation character '" + c + "'", i + base_offset);
//type = ignoreChars ? CollationSorter.IGNORE : -1;
sb.append(c);
break;
}
if (type < 0)
continue;
if (operator < 0)
{
operator = type;
continue;
}
if (sb.length() == 0 && !isModifier)
throw new ParseException
("text element empty at " + (i+base_offset), i+base_offset);
if (operator == CollationSorter.RESET)
{
/* Reposition in the sorting list at the position
* indicated by the text element.
*/
String subrules = rules.substring(i);
ArrayList sorted_rules = new ArrayList();
int idx;
// Parse the subrules but do not iterate through all
// sublist. This is the priviledge of the first call.
idx = subParseString(true, sorted_rules, base_offset+i, subrules);
// Merge new parsed rules into the list.
mergeRules(base_offset+i, sb.toString(), v, sorted_rules);
sb.setLength(0);
// Reset state to none.
operator = -1;
type = -1;
// We have found a new subrule at 'idx' but it has not been parsed.
if (idx >= 0)
{
i += idx-1;
continue main_parse_loop;
}
else
// No more rules.
break main_parse_loop;
}
CollationSorter sorter = new CollationSorter();
if (operator == CollationSorter.GREATERP)
ignoreChars = false;
sorter.comparisonType = operator;
sorter.textElement = sb.toString();
sorter.hashText = sorter.textElement.hashCode();
sorter.offset = base_offset+rules.length();
sorter.ignore = ignoreChars;
sb.setLength(0);
v.add(sorter);
operator = type;
}
if (operator >= 0)
{
CollationSorter sorter = new CollationSorter();
int pos = rules.length() + base_offset;
if ((sb.length() != 0 && nextIsModifier)
|| (sb.length() == 0 && !nextIsModifier && !eatingChars))
throw new ParseException("text element empty at " + pos, pos);
if (operator == CollationSorter.GREATERP)
ignoreChars = false;
sorter.comparisonType = operator;
sorter.textElement = sb.toString();
sorter.hashText = sorter.textElement.hashCode();
sorter.offset = base_offset+pos;
sorter.ignore = ignoreChars;
v.add(sorter);
}
if (i == rules.length())
return -1;
else
return i;
}
/**
* This method creates a copy of this object.
*
* @return A copy of this object.
*/
public Object clone()
{
return super.clone();
}
/**
* This method completely parses a string 'rules' containing sorting rules.
*
* @param rules String containing the rules to be parsed.
* @return A set of sorting instructions stored in a Vector.
* @throws ParseException if something turned wrong during the parsing. To get details
* decode the message.
*/
private ArrayList parseString(String rules)
throws ParseException
{
ArrayList v = new ArrayList();
// result of the first subParseString is not absolute (may be -1 or a
// positive integer). But we do not care.
subParseString(false, v, 0, rules);
return v;
}
/**
* This method uses the sorting instructions built by {@link #parseString}
* to build collation elements which can be directly used to sort strings.
*
* @param parsedElements Parsed instructions stored in a ArrayList.
* @throws ParseException if the order of the instructions are not valid.
*/
private void buildCollationVector(ArrayList parsedElements)
throws ParseException
{
int primary_seq = 0;
int last_tertiary_seq = 0;
short secondary_seq = 0;
short tertiary_seq = 0;
short equality_seq = 0;
boolean inverseComparisons = false;
final boolean DECREASING = false;
final boolean INCREASING = true;
boolean secondaryType = INCREASING;
ArrayList v = new ArrayList();
// elts is completely sorted.
element_loop:
for (int i = 0; i < parsedElements.size(); i++)
{
CollationSorter elt = (CollationSorter) parsedElements.get(i);
boolean ignoreChar = false;
switch (elt.comparisonType)
{
case CollationSorter.GREATERP:
primary_seq++;
if (inverseComparisons)
{
secondary_seq = Short.MAX_VALUE;
secondaryType = DECREASING;
}
else
{
secondary_seq = 0;
secondaryType = INCREASING;
}
tertiary_seq = 0;
equality_seq = 0;
inverseComparisons = false;
break;
case CollationSorter.GREATERS:
if (secondaryType == DECREASING)
secondary_seq--;
else
secondary_seq++;
tertiary_seq = 0;
equality_seq = 0;
break;
case CollationSorter.INVERSE_SECONDARY:
inverseComparisons = true;
continue element_loop;
case CollationSorter.GREATERT:
tertiary_seq++;
if (primary_seq == 0)
last_tertiary_seq = tertiary_seq;
equality_seq = 0;
break;
case CollationSorter.EQUAL:
equality_seq++;
break;
case CollationSorter.RESET:
throw new ParseException
("Invalid reached state 'RESET'. Internal error", elt.offset);
default:
throw new ParseException
("Invalid unknown state '" + elt.comparisonType + "'", elt.offset);
}
v.add(new CollationElement(elt.textElement, primary_seq,
secondary_seq, tertiary_seq,
equality_seq, elt.expansionOrdering, elt.ignore));
}
this.inverseAccentComparison = inverseComparisons;
ce_table = v.toArray();
last_primary_value = primary_seq+1;
last_tertiary_value = last_tertiary_seq+1;
}
/**
* Build a tree where all keys are the texts of collation elements and data is
* the collation element itself. The tree is used when extracting all prefix
* for a given text.
*/
private void buildPrefixAccess()
{
prefix_tree = new HashMap();
for (int i = 0; i < ce_table.length; i++)
{
CollationElement e = (CollationElement) ce_table[i];
prefix_tree.put(e.key, e);
}
}
/**
* 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 source The first String to compare.
* @param target A second String to compare to the first.
*
* @return A negative integer if source < target, a positive integer
* if source > target, or 0 if source == target.
*/
public int compare(String source, String target)
{
CollationElementIterator cs, ct;
CollationElement ord1block = null;
CollationElement ord2block = null;
boolean advance_block_1 = true;
boolean advance_block_2 = true;
cs = getCollationElementIterator(source);
ct = getCollationElementIterator(target);
for(;;)
{
int ord1;
int ord2;
/*
* We have to check whether the characters are ignorable.
* If it is the case then forget them.
*/
if (advance_block_1)
{
ord1block = cs.nextBlock();
if (ord1block != null && ord1block.ignore)
continue;
}
if (advance_block_2)
{
ord2block = ct.nextBlock();
if (ord2block != null && ord2block.ignore)
{
advance_block_1 = false;
continue;
}
}
else
advance_block_2 = true;
if (!advance_block_1)
advance_block_1 = true;
if (ord1block != null)
ord1 = ord1block.getValue();
else
{
if (ord2block == null)
return 0;
return -1;
}
if (ord2block == null)
return 1;
ord2 = ord2block.getValue();
// We know chars are totally equal, so skip
if (ord1 == ord2)
{
if (getStrength() == IDENTICAL)
if (!ord1block.key.equals(ord2block.key))
return ord1block.key.compareTo(ord2block.key);
continue;
}
// Check for primary strength differences
int prim1 = CollationElementIterator.primaryOrder(ord1);
int prim2 = CollationElementIterator.primaryOrder(ord2);
if (prim1 == 0 && getStrength() < TERTIARY)
{
advance_block_2 = false;
continue;
}
else if (prim2 == 0 && getStrength() < TERTIARY)
{
advance_block_1 = false;
continue;
}
if (prim1 < prim2)
return -1;
else if (prim1 > prim2)
return 1;
else if (getStrength() == PRIMARY)
continue;
// Check for secondary strength differences
int sec1 = CollationElementIterator.secondaryOrder(ord1);
int sec2 = CollationElementIterator.secondaryOrder(ord2);
if (sec1 < sec2)
return -1;
else if (sec1 > sec2)
return 1;
else if (getStrength() == SECONDARY)
continue;
// Check for tertiary differences
int tert1 = CollationElementIterator.tertiaryOrder(ord1);
int tert2 = CollationElementIterator.tertiaryOrder(ord2);
if (tert1 < tert2)
return -1;
else if (tert1 > tert2)
return 1;
else if (getStrength() == TERTIARY)
continue;
// Apparently JDK does this (at least for my test case).
return ord1block.key.compareTo(ord2block.key);
}
}
/**
* 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 == this)
return true;
else
return false;
}
/**
* This method builds a default collation element without invoking
* the database created from the rules passed to the constructor.
*
* @param c Character which needs a collation element.
* @return A valid brand new CollationElement instance.
*/
CollationElement getDefaultElement(char c)
{
int v;
// Preliminary support for generic accent sorting inversion (I don't know if all
// characters in the range should be sorted backward). This is the place
// to fix this if needed.
if (inverseAccentComparison && (c >= 0x02B9 && c <= 0x0361))
v = 0x0361 - ((int) c - 0x02B9);
else
v = (short) c;
return new CollationElement("" + c, last_primary_value + v,
(short) 0, (short) 0, (short) 0, null, false);
}
/**
* This method builds a default collation element for an accented character
* without invoking the database created from the rules passed to the constructor.
*
* @param c Character which needs a collation element.
* @return A valid brand new CollationElement instance.
*/
CollationElement getDefaultAccentedElement(char c)
{
int v;
// Preliminary support for generic accent sorting inversion (I don't know if all
// characters in the range should be sorted backward). This is the place
// to fix this if needed.
if (inverseAccentComparison && (c >= 0x02B9 && c <= 0x0361))
v = 0x0361 - ((int) c - 0x02B9);
else
v = (short) c;
return new CollationElement("" + c, (short) 0,
(short) 0, (short) (last_tertiary_value + v), (short) 0, null, false);
}
/**
* This method returns an instance for CollationElementIterator
* for the specified String under the collation rules for this
* object.
*
* @param source The String to return the
* CollationElementIterator instance for.
*
* @return A CollationElementIterator for the specified
* String.
*/
public CollationElementIterator getCollationElementIterator(String source)
{
return new CollationElementIterator(this, source);
}
/**
* This method returns an instance of CollationElementIterator
* for the String represented by the specified
* CharacterIterator.
*
* @param source The CharacterIterator with the desired String.
*
* @return A CollationElementIterator for the specified String.
*/
public CollationElementIterator getCollationElementIterator(CharacterIterator source)
{
StringBuffer expand = new StringBuffer("");
// Right now we assume that we will read from the beginning of the string.
for (char c = source.first();
c != CharacterIterator.DONE;
c = source.next())
decomposeCharacter(c, expand);
return getCollationElementIterator(expand.toString());
}
/**
* 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 source The String to create a CollationKey for.
*
* @return A CollationKey for the specified String.
*/
public CollationKey getCollationKey(String source)
{
CollationElementIterator cei = getCollationElementIterator(source);
ArrayList vect = new ArrayList();
int ord = cei.next();
cei.reset(); //set to start of string
while (ord != CollationElementIterator.NULLORDER)
{
// If the primary order is null, it means this is an ignorable
// character.
if (CollationElementIterator.primaryOrder(ord) == 0)
{
ord = cei.next();
continue;
}
switch (getStrength())
{
case PRIMARY:
ord = CollationElementIterator.primaryOrder(ord);
break;
case SECONDARY:
ord = CollationElementIterator.primaryOrder(ord) << 8;
ord |= CollationElementIterator.secondaryOrder(ord);
default:
break;
}
vect.add(new Integer(ord));
ord = cei.next(); //increment to next key
}
Object[] objarr = vect.toArray();
byte[] key = new byte[objarr.length * 4];
for (int i = 0; i < objarr.length; i++)
{
int j = ((Integer) objarr[i]).intValue();
key [i * 4] = (byte) ((j & 0xFF000000) >> 24);
key [i * 4 + 1] = (byte) ((j & 0x00FF0000) >> 16);
key [i * 4 + 2] = (byte) ((j & 0x0000FF00) >> 8);
key [i * 4 + 3] = (byte) (j & 0x000000FF);
}
return new CollationKey(this, source, key);
}
/**
* 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 System.identityHashCode(this);
}
}