// IMPLEMENTATION NOTES: The implementation of the collation algorithm is

// divided across three classes: RuleBasedCollator, RBCollationTables, and

// CollationElementIterator. RuleBasedCollator contains the collator's

// transient state and includes the code that uses the other classes to

// implement comparison and sort-key building. RuleBasedCollator also

// contains the logic to handle French secondary accent sorting.

// A RuleBasedCollator has two CollationElementIterators. State doesn't

// need to be preserved in these objects between calls to compare() or

// getCollationKey(), but the objects persist anyway to avoid wasting extra

// creation time. compare() and getCollationKey() are synchronized to ensure

// thread safety with this scheme. The CollationElementIterator is responsible

// for generating collation elements from strings and returning one element at

// a time (sometimes there's a one-to-many or many-to-one mapping between

// characters and collation elements-- this class handles that).

// CollationElementIterator depends on RBCollationTables, which contains the

// collator's static state. RBCollationTables contains the actual data

// tables specifying the collation order of characters for a particular locale

// or use. It also contains the base logic that CollationElementIterator

// uses to map from characters to collation elements. A single RBCollationTables

// object is shared among all RuleBasedCollators for the same locale, and

// thus by all the CollationElementIterators they create.

/**

public RuleBasedCollator(String rules) throws ParseException {

this(rules, Collator.CANONICAL_DECOMPOSITION);

}

/**

RuleBasedCollator(String rules, int decomp) throws ParseException {

setStrength(Collator.TERTIARY);

setDecomposition(decomp);

tables = new RBCollationTables(rules, decomp);

}

/**

private RuleBasedCollator(RuleBasedCollator that) {

setStrength(that.getStrength());

setDecomposition(that.getDecomposition());

tables = that.tables;

}

/**

public String getRules()

{

return tables.getRules();

}

/**

public CollationElementIterator getCollationElementIterator(String source) {

return new CollationElementIterator( source, this );

}

/**

public CollationElementIterator getCollationElementIterator(

CharacterIterator source) {

return new CollationElementIterator( source, this );

}

/**

public synchronized int compare(String source, String target)

{

if (source == null || target == null) {

throw new NullPointerException();

}

// The basic algorithm here is that we use CollationElementIterators

// to step through both the source and target strings. We compare each

// collation element in the source string against the corresponding one

// in the target, checking for differences.

//

// If a difference is found, we set <result> to LESS or GREATER to

// indicate whether the source string is less or greater than the target.

//

// However, it's not that simple. If we find a tertiary difference

// (e.g. 'A' vs. 'a') near the beginning of a string, it can be

// overridden by a primary difference (e.g. "A" vs. "B") later in

// the string. For example, "AA" < "aB", even though 'A' > 'a'.

//

// To keep track of this, we use strengthResult to keep track of the

// strength of the most significant difference that has been found

// so far. When we find a difference whose strength is greater than

// strengthResult, it overrides the last difference (if any) that

// was found.

int result = Collator.EQUAL;

if (sourceCursor == null) {

sourceCursor = getCollationElementIterator(source);

} else {

sourceCursor.setText(source);

}

if (targetCursor == null) {

targetCursor = getCollationElementIterator(target);

} else {

targetCursor.setText(target);

}

int sOrder = 0, tOrder = 0;

boolean initialCheckSecTer = getStrength() >= Collator.SECONDARY;

boolean checkSecTer = initialCheckSecTer;

boolean checkTertiary = getStrength() >= Collator.TERTIARY;

boolean gets = true, gett = true;

while(true) {

// Get the next collation element in each of the strings, unless

// we've been requested to skip it.

if (gets) sOrder = sourceCursor.next(); else gets = true;

if (gett) tOrder = targetCursor.next(); else gett = true;

// If we've hit the end of one of the strings, jump out of the loop

if ((sOrder == CollationElementIterator.NULLORDER)||

(tOrder == CollationElementIterator.NULLORDER))

break;

int pSOrder = CollationElementIterator.primaryOrder(sOrder);

int pTOrder = CollationElementIterator.primaryOrder(tOrder);

// If there's no difference at this position, we can skip it

if (sOrder == tOrder) {

if (tables.isFrenchSec() && pSOrder != 0) {

if (!checkSecTer) {

// in french, a secondary difference more to the right is stronger,

// so accents have to be checked with each base element

checkSecTer = initialCheckSecTer;

// but tertiary differences are less important than the first

// secondary difference, so checking tertiary remains disabled

checkTertiary = false;

}

}

continue;

}

// Compare primary differences first.

if ( pSOrder != pTOrder )

{

if (sOrder == 0) {

// The entire source element is ignorable.

// Skip to the next source element, but don't fetch another target element.

gett = false;

continue;

}

if (tOrder == 0) {

gets = false;

continue;

}

// The source and target elements aren't ignorable, but it's still possible

// for the primary component of one of the elements to be ignorable....

if (pSOrder == 0) // primary order in source is ignorable

{

// The source's primary is ignorable, but the target's isn't. We treat ignorables

// as a secondary difference, so remember that we found one.

if (checkSecTer) {

result = Collator.GREATER; // (strength is SECONDARY)

checkSecTer = false;

}

// Skip to the next source element, but don't fetch another target element.

gett = false;

}

else if (pTOrder == 0)

{

// record differences - see the comment above.

if (checkSecTer) {

result = Collator.LESS; // (strength is SECONDARY)

checkSecTer = false;

}

// Skip to the next source element, but don't fetch another target element.

gets = false;

} else {

// Neither of the orders is ignorable, and we already know that the primary

// orders are different because of the (pSOrder != pTOrder) test above.

// Record the difference and stop the comparison.

if (pSOrder < pTOrder) {

return Collator.LESS; // (strength is PRIMARY)

} else {

return Collator.GREATER; // (strength is PRIMARY)

}

}

} else { // else of if ( pSOrder != pTOrder )

// primary order is the same, but complete order is different. So there

// are no base elements at this point, only ignorables (Since the strings are

// normalized)

if (checkSecTer) {

// a secondary or tertiary difference may still matter

short secSOrder = CollationElementIterator.secondaryOrder(sOrder);

short secTOrder = CollationElementIterator.secondaryOrder(tOrder);

if (secSOrder != secTOrder) {

// there is a secondary difference

result = (secSOrder < secTOrder) ? Collator.LESS : Collator.GREATER;

// (strength is SECONDARY)

checkSecTer = false;

// (even in french, only the first secondary difference within

// a base character matters)

} else {

if (checkTertiary) {

// a tertiary difference may still matter

short terSOrder = CollationElementIterator.tertiaryOrder(sOrder);

short terTOrder = CollationElementIterator.tertiaryOrder(tOrder);

if (terSOrder != terTOrder) {

// there is a tertiary difference

result = (terSOrder < terTOrder) ? Collator.LESS : Collator.GREATER;

// (strength is TERTIARY)

checkTertiary = false;

}

}

}

} // if (checkSecTer)

} // if ( pSOrder != pTOrder )

} // while()

if (sOrder != CollationElementIterator.NULLORDER) {

// (tOrder must be CollationElementIterator::NULLORDER,

// since this point is only reached when sOrder or tOrder is NULLORDER.)

// The source string has more elements, but the target string hasn't.

do {

if (CollationElementIterator.primaryOrder(sOrder) != 0) {

// We found an additional non-ignorable base character in the source string.

// This is a primary difference, so the source is greater

return Collator.GREATER; // (strength is PRIMARY)

}

else if (CollationElementIterator.secondaryOrder(sOrder) != 0) {

// Additional secondary elements mean the source string is greater

if (checkSecTer) {

result = Collator.GREATER; // (strength is SECONDARY)

checkSecTer = false;

}

}

} while ((sOrder = sourceCursor.next()) != CollationElementIterator.NULLORDER);

}

else if (tOrder != CollationElementIterator.NULLORDER) {

// The target string has more elements, but the source string hasn't.

do {

if (CollationElementIterator.primaryOrder(tOrder) != 0)

// We found an additional non-ignorable base character in the target string.

// This is a primary difference, so the source is less

return Collator.LESS; // (strength is PRIMARY)

else if (CollationElementIterator.secondaryOrder(tOrder) != 0) {

// Additional secondary elements in the target mean the source string is less

if (checkSecTer) {

result = Collator.LESS; // (strength is SECONDARY)

checkSecTer = false;

}

}

} while ((tOrder = targetCursor.next()) != CollationElementIterator.NULLORDER);

}

// For IDENTICAL comparisons, we use a bitwise character comparison

// as a tiebreaker if all else is equal

if (result == 0 && getStrength() == IDENTICAL) {

int mode = getDecomposition();

Normalizer.Form form;

if (mode == CANONICAL_DECOMPOSITION) {

form = Normalizer.Form.NFD;

} else if (mode == FULL_DECOMPOSITION) {

form = Normalizer.Form.NFKD;

} else {

return source.compareTo(target);

}

String sourceDecomposition = Normalizer.normalize(source, form);

String targetDecomposition = Normalizer.normalize(target, form);

return sourceDecomposition.compareTo(targetDecomposition);

}

return result;

}

/**

public synchronized CollationKey getCollationKey(String source)

{

//

// The basic algorithm here is to find all of the collation elements for each

// character in the source string, convert them to a char representation,

// and put them into the collation key. But it's trickier than that.

// Each collation element in a string has three components: primary (A vs B),

// secondary (A vs A-acute), and tertiary (A' vs a); and a primary difference

// at the end of a string takes precedence over a secondary or tertiary

// difference earlier in the string.

//

// To account for this, we put all of the primary orders at the beginning of the

// string, followed by the secondary and tertiary orders, separated by nulls.

//

// Here's a hypothetical example, with the collation element represented as

// a three-digit number, one digit for primary, one for secondary, etc.

//

// String: A a B \u00e9 <--(e-acute)

// Collation Elements: 101 100 201 510

//

// Collation Key: 1125<null>0001<null>1010

//

// To make things even trickier, secondary differences (accent marks) are compared

// starting at the *end* of the string in languages with French secondary ordering.

// But when comparing the accent marks on a single base character, they are compared

// from the beginning. To handle this, we reverse all of the accents that belong

// to each base character, then we reverse the entire string of secondary orderings

// at the end. Taking the same example above, a French collator might return

// this instead:

//

// Collation Key: 1125<null>1000<null>1010

//

if (source == null)

return null;

if (primResult == null) {

primResult = new StringBuffer();

secResult = new StringBuffer();

terResult = new StringBuffer();

} else {

primResult.setLength(0);

secResult.setLength(0);

terResult.setLength(0);

}

int order = 0;

boolean compareSec = (getStrength() >= Collator.SECONDARY);

boolean compareTer = (getStrength() >= Collator.TERTIARY);

int secOrder = CollationElementIterator.NULLORDER;

int terOrder = CollationElementIterator.NULLORDER;

int preSecIgnore = 0;

if (sourceCursor == null) {

sourceCursor = getCollationElementIterator(source);

} else {

sourceCursor.setText(source);

}

// walk through each character

while ((order = sourceCursor.next()) !=

CollationElementIterator.NULLORDER)

{

secOrder = CollationElementIterator.secondaryOrder(order);

terOrder = CollationElementIterator.tertiaryOrder(order);

if (!CollationElementIterator.isIgnorable(order))

{

primResult.append((char) (CollationElementIterator.primaryOrder(order)

+ COLLATIONKEYOFFSET));

if (compareSec) {

//

// accumulate all of the ignorable/secondary characters attached

// to a given base character

//

if (tables.isFrenchSec() && preSecIgnore < secResult.length()) {

//

// We're doing reversed secondary ordering and we've hit a base

// (non-ignorable) character. Reverse any secondary orderings

// that applied to the last base character. (see block comment above.)

//

RBCollationTables.reverse(secResult, preSecIgnore, secResult.length());

}

// Remember where we are in the secondary orderings - this is how far

// back to go if we need to reverse them later.

secResult.append((char)(secOrder+ COLLATIONKEYOFFSET));

preSecIgnore = secResult.length();

}

if (compareTer) {

terResult.append((char)(terOrder+ COLLATIONKEYOFFSET));

}

}

else

{

if (compareSec && secOrder != 0)

secResult.append((char)

(secOrder + tables.getMaxSecOrder() + COLLATIONKEYOFFSET));

if (compareTer && terOrder != 0)

terResult.append((char)

(terOrder + tables.getMaxTerOrder() + COLLATIONKEYOFFSET));

}

}

if (tables.isFrenchSec())

{

if (preSecIgnore < secResult.length()) {

// If we've accumulated any secondary characters after the last base character,

// reverse them.

RBCollationTables.reverse(secResult, preSecIgnore, secResult.length());

}

// And now reverse the entire secResult to get French secondary ordering.

RBCollationTables.reverse(secResult, 0, secResult.length());

}

primResult.append((char)0);

secResult.append((char)0);

secResult.append(terResult.toString());

primResult.append(secResult.toString());

if (getStrength() == IDENTICAL) {

primResult.append((char)0);

int mode = getDecomposition();

if (mode == CANONICAL_DECOMPOSITION) {

primResult.append(Normalizer.normalize(source, Normalizer.Form.NFD));

} else if (mode == FULL_DECOMPOSITION) {

primResult.append(Normalizer.normalize(source, Normalizer.Form.NFKD));

} else {

primResult.append(source);

}

}

return new RuleBasedCollationKey(source, primResult.toString());

}

/**

public Object clone() {

// if we know we're not actually a subclass of RuleBasedCollator

// (this class really should have been made final), bypass

// Object.clone() and use our "copy constructor". This is faster.

if (getClass() == RuleBasedCollator.class) {

return new RuleBasedCollator(this);

}

else {

RuleBasedCollator result = (RuleBasedCollator) super.clone();

result.primResult = null;

result.secResult = null;

result.terResult = null;

result.sourceCursor = null;

result.targetCursor = null;

return result;

}

}

/**

public boolean equals(Object obj) {

if (obj == null) return false;

if (!super.equals(obj)) return false; // super does class check

RuleBasedCollator other = (RuleBasedCollator) obj;

// all other non-transient information is also contained in rules.

return (getRules().equals(other.getRules()));

}

/**

public int hashCode() {

return getRules().hashCode();

}

/**

RBCollationTables getTables() {

return tables;

}

// ==============================================================

// private

// ==============================================================

final static int CHARINDEX = 0x70000000; // need look up in .commit()

final static int EXPANDCHARINDEX = 0x7E000000; // Expand index follows

final static int CONTRACTCHARINDEX = 0x7F000000; // contract indexes follow

final static int UNMAPPED = 0xFFFFFFFF;

private final static int COLLATIONKEYOFFSET = 1;

private RBCollationTables tables = null;

// Internal objects that are cached across calls so that they don't have to

// be created/destroyed on every call to compare() and getCollationKey()

private StringBuffer primResult = null;

private StringBuffer secResult = null;

private StringBuffer terResult = null;

private CollationElementIterator sourceCursor = null;

private CollationElementIterator targetCursor = null;