[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH] RuleBasedCollator
|
From: |
Guilhem Lavaux |
|
Subject: |
[PATCH] RuleBasedCollator |
|
Date: |
Sat, 13 Dec 2003 19:57:22 +0100 |
|
User-agent: |
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.4) Gecko/20030630 |
Hi,
As Savannah is down, here is the patch concerning java.text.RuleBasedCollator.
I should say instead a major rewrite of the rule parser. I send you the first file both in
diff format and the complete file because some parts are only small changes and some others
are purely rewritten. The change concerns java/text/RuleBasedCollator.java and
java/text/CollationElementIterator.java.
The diff were taken against the last available Classpath before savannah
shutdown.
Some methods are still undocumented but I'll add the doc later when the last
incompatibilities
will have been removed.
Here is a short summary of the new parser:
* rules are first translated into internal sorted representation. All
characters are interpreted
but the collation sorting numbers are not generated.
* The internal generated representations is used to build sorting numbers, at that time there
shouldn't be any RESET tag in the representation.
* '!' is still not supported, because I need some more documentation on
accented character
inversion.
* setText has been upgraded to match pattern into the input text. The previous
text analyzer
didn't make an extensive search of all prefix and caused some strings to be
sorted wrongly.
With the new algorithm, it should be able to sort strings using the best
sorting element in the
rules.
* Character expansion is now supported: in some cases one character should be
translater into
multiple characters, e.g. รค into ae it should be done partially in setText
(which adds
some extra character in the input text on demand) and by the parser (which
should recall
when some characters should be added).
I'm not proposing ChangeLog entry for the moment.
Please review.
Cheers,
Guilhem.
/* RuleBasedCollator.java -- Concrete Collator Class
Copyright (C) 1998, 1999, 2000, 2001, 2003 Free Software Foundation, Inc.
This file is part of GNU Classpath.
GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING. If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.
Linking this library statically or dynamically with other modules is
making a combined work based on this library. Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.
As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module. An independent module is a module which is not derived from
or based on this library. If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so. If you do not wish to do so, delete this
exception statement from your version. */
package java.text;
import java.util.Vector;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.Comparator;
/* Written using "Java Class Libraries", 2nd edition, plus online
* API docs for JDK 1.2 from http://www.javasoft.com.
* Status: Believed complete and correct
*/
/**
* This class is a concrete subclass of <code>Collator</code> suitable
* for string collation in a wide variety of languages. An instance of
* this class is normally returned by the <code>getInstance</code> method
* of <code>Collator</code> with rules predefined for the requested
* locale. However, an instance of this class can be created manually
* with any desired rules.
* <p>
* Rules take the form of a <code>String</code> with the following syntax
* <ul>
* <li> Modifier: '@'
* <li> Relation: '<' | ';' | ',' | '=' : <text>
* <li> Reset: '&' : <text>
* </ul>
* The modifier character indicates that accents sort backward as is the
* case with French. The modifier applies to all rules <b>after</b>
* the modifier but before the next primary sequence. If placed at the end
* of the sequence if applies to all unknown accented character.
* The relational operators specify how the text
* argument relates to the previous term. The relation characters have
* the following meanings:
* <ul>
* <li>'<' - The text argument is greater than the prior term at the primary
* difference level.
* <li>';' - The text argument is greater than the prior term at the secondary
* difference level.
* <li>',' - The text argument is greater than the prior term at the tertiary
* difference level.
* <li>'=' - The text argument is equal to the prior term
* </ul>
* <p>
* 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").
* <p>
* 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 <code>ParseException</code> will be thrown.
* <p>
* This system of configuring <code>RuleBasedCollator</code> 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.
* <p>
* Here are a couple of example of rule strings:
* <p>
* "< a < b < c" - This string says that a is greater than b which is
* greater than c, with all differences being primary differences.
* <p>
* "< 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.
* <p>
* "< 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.
* <p>
* "< 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.
* <p>
* "< a & A @ < e & E < f& F" - This sequence is equivalent
to the following
* "< a & A < E & e < f & F".
* <p>
* For a description of the various comparison strength types, see the
* documentation for the <code>Collator</code> class.
* <p>
* 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.
* <p>
* A <code>ParseException</code> will be thrown for any of the following
* conditions:
* <ul>
* <li>Unquoted punctuation characters in a text argument.
* <li>A relational or reset operator not followed by a text argument
* <li>A reset operator where the text argument is not present in
* the previous rule string section.
* </ul>
*
* @author Aaron M. Renn <address@hidden>
* @author Tom Tromey <address@hidden>
* @author Guilhem Lavaux <address@hidden>
* @date August 17, 2003
*/
public class RuleBasedCollator extends Collator
{
class CollationElement
{
String char_seq;
int primary;
short secondary;
short tertiary;
short equality;
boolean ignore;
String expansion;
CollationElement(String char_seq, int primary, short secondary, short
tertiary,
short equality, String expansion)
{
this.char_seq = char_seq;
this.primary = primary;
this.secondary = secondary;
this.tertiary = tertiary;
this.equality = equality;
this.ignore = false;
this.expansion = expansion;
}
CollationElement(String char_seq)
{
this.char_seq = char_seq;
this.ignore = true;
}
final int getValue()
{
return (primary << 16) + (secondary << 8) + tertiary;
}
} // inner class CollationElement
class CollationBlock
{
int value;
String textBlock;
}
class CollationSorter
{
static final int GREATERP = 0;
static final int GREATERS = 1;
static final int GREATERT = 2;
static final int EQUAL = 3;
static final int RESET = 4;
static final int IGNORE = 5;
static final int INVERSE_SECONDARY = 6;
int comparisonType;
String textElement;
int hashText;
int offset;
String expansionOrdering;
}
static int findPrefixLength(String prefix, String s)
{
int i;
for (i=0;i<prefix.length() && i < s.length();i++)
{
if (prefix.charAt(i) != s.charAt(i))
return i;
}
return i;
}
void mergeRules(int offset, String starter, Vector main, Vector patch)
throws ParseException
{
Enumeration elements = main.elements();
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.elementAt (i);
CollationSorter rule2 = (CollationSorter)main.elementAt (j);
if (rule1.textElement.equals (rule2.textElement))
main.removeElementAt (j);
else
j++;
}
}
// Find the insertion point... O(N)
for (int i=0;i<main.size();i++)
{
CollationSorter sorter = (CollationSorter)main.elementAt(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.elementAt (0);
CollationSorter expansionPrefix = (CollationSorter)main.elementAt
(insertion_point-1);
sorter.expansionOrdering = starter.substring (max_length); // Skip the
first good prefix element
main.insertElementAt (sorter, insertion_point);
/*
* This is a new set of rules. Append to the list.
*/
patch.removeElementAt (0);
insertion_point = main.size();
}
// Now insert all elements of patch at the insertion point.
for (int i=0;i<patch.size();i++)
main.insertElementAt (patch.elementAt (i), i+insertion_point);
}
int subParseString(boolean stop_on_reset, Vector 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 '<':
ignoreChars = false;
type = CollationSorter.GREATERP;
break;
case ';':
if (!ignoreChars)
type = CollationSorter.GREATERS;
else
type = CollationSorter.IGNORE;
break;
case ',':
if (!ignoreChars)
type = CollationSorter.GREATERT;
else
type = CollationSorter.IGNORE;
break;
case '=':
if (!ignoreChars)
type = CollationSorter.EQUAL;
else
type = CollationSorter.IGNORE;
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);
Vector sorted_rules = new Vector();
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();
sorter.comparisonType = operator;
sorter.textElement = sb.toString();
sorter.hashText = sorter.textElement.hashCode();
sorter.offset = base_offset+rules.length();
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);
sorter.comparisonType = operator;
sorter.textElement = sb.toString();
sorter.hashText = sorter.textElement.hashCode();
sorter.offset = base_offset+pos;
v.add (sorter);
}
if (i == rules.length())
return -1;
else
return i;
}
private Vector parseString(String rules) throws ParseException
{
Vector v = new Vector();
// result of the first subParseString is not certain (may be -1 or a
positive integer). But we
// do not care.
subParseString (false, v, 0, rules);
return v;
}
/**
* This the the original rule string.
*/
private String rules;
/**
* This is the table of collation element values
*/
private Object[] ce_table;
/**
* Quick-prefix finder.
*/
HashMap prefix_tree;
/**
* This is the value of the last sequence entered into
* <code>ce_table</code>. It is used to compute the
* ordering value of unspecified character.
*/
private int last_primary_value;
/**
* This variable is true if accents need to be sorted
* in the other direction.
*/
private boolean inverseAccentComparison;
private void buildCollationVector(Vector parsedElements) throws ParseException
{
int primary_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;
Vector v = new Vector();
// elts is completely sorted.
element_loop:
for (int i=0;i<parsedElements.size();i++)
{
CollationSorter elt = (CollationSorter)parsedElements.elementAt (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++;
equality_seq = 0;
break;
case CollationSorter.IGNORE:
ignoreChar = true;
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);
}
CollationElement e;
if (!ignoreChar)
{
e = new CollationElement (elt.textElement, primary_seq,
secondary_seq, tertiary_seq,
equality_seq, elt.expansionOrdering);
}
else
e = new CollationElement (elt.textElement);
v.add(e);
}
this.inverseAccentComparison = inverseComparisons;
ce_table = v.toArray();
last_primary_value = primary_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.char_seq, e);
}
}
/**
* This method initializes a new instance of <code>RuleBasedCollator</code>
* with the specified collation rules. Note that an application normally
* obtains an instance of <code>RuleBasedCollator</code> by calling the
* <code>getInstance</code> method of <code>Collator</code>. 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
{
this.rules = rules;
if (rules.equals (""))
throw new ParseException ("Empty rule set", 0);
buildCollationVector (parseString (rules));
buildPrefixAccess();
}
/**
* This method returns a <code>String</code> containing the collation rules
* for this object.
*
* @return The collation rules for this object.
*/
public String getRules()
{
return(rules);
}
/**
* This method builds a default collation element without invoking
* the database created from the rules passed to the constructor.
*/
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);
}
/**
* This method returns an instance for <code>CollationElementIterator</code>
* for the specified <code>String</code> under the collation rules for this
* object.
*
* @param str The <code>String</code> to return the
<code>CollationElementIterator</code> instance for.
*
* @return A <code>CollationElementIterator</code> for the specified
<code>String</code>.
*/
public CollationElementIterator getCollationElementIterator(String str)
{
return new CollationElementIterator (this, str);
}
/**
* This method returns an instance of <code>CollationElementIterator</code>
* for the <code>String</code> represented by the specified
* <code>CharacterIterator</code>.
*
* @param ci The <code>CharacterIterator</code> with the desired
<code>String</code>.
*
* @return A <code>CollationElementIterator</code> for the specified
<code>String</code>.
*/
public CollationElementIterator getCollationElementIterator(CharacterIterator
ci)
{
StringBuffer sb = new StringBuffer("");
// Right now we assume that we will read from the beginning of the string.
char c = ci.first();
while (c != CharacterIterator.DONE)
{
sb.append(c);
c = ci.next();
}
return getCollationElementIterator (sb.toString());
}
/**
* This method returns an integer which indicates whether the first
* specified <code>String</code> 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 <code>String</code> to compare.
* @param s2 A second <code>String</code> 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 s1, String s2)
{
CollationElementIterator cei1 = getCollationElementIterator (s1);
CollationElementIterator cei2 = getCollationElementIterator (s2);
for(;;)
{
CollationElement ord1block = cei1.nextBlock();
CollationElement ord2block = cei2.nextBlock();
int ord1;
int ord2;
// Hehehe. What we would do not to use if.
try
{
ord1 = ord1block.getValue();
}
catch (NullPointerException _)
{
if (ord2block == null)
return 0;
return -1;
}
try
{
ord2 = ord2block.getValue();
}
catch (NullPointerException _)
{
return 1;
}
// We know chars are totally equal, so skip
if (ord1 == ord2)
{
if (getStrength() == IDENTICAL)
if (!ord1block.char_seq.equals (ord2block.char_seq))
return ord1block.char_seq.compareTo (ord2block.char_seq);
continue;
}
// Check for primary strength differences
int prim1 = cei1.primaryOrder (ord1);
int prim2 = cei2.primaryOrder (ord2);
if (prim1 < prim2)
return(-1);
else if (prim1 > prim2)
return(1);
else if (getStrength() == PRIMARY)
continue;
// Check for secondary strength differences
int sec1 = cei1.secondaryOrder (ord1);
int sec2 = cei2.secondaryOrder (ord2);
if (sec1 < sec2)
return(-1);
else if (sec1 > sec2)
return(1);
else if (getStrength() == SECONDARY)
continue;
// Check for tertiary differences
int tert1 = cei1.tertiaryOrder (ord1);
int tert2 = cei2.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.char_seq.compareTo (ord2block.char_seq);
}
}
/**
* This method returns an instance of <code>CollationKey</code> for the
* specified <code>String</code>. 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 <code>String</code> to create a <code>CollationKey</code>
for.
*
* @return A <code>CollationKey</code> for the specified <code>String</code>.
*/
public CollationKey getCollationKey(String str)
{
CollationElementIterator cei = getCollationElementIterator (str);
Vector vect = new Vector(25);
int ord = cei.next();
cei.reset(); //set to start of string
while (ord != CollationElementIterator.NULLORDER)
{
switch (getStrength())
{
case PRIMARY:
ord = cei.primaryOrder (ord);
break;
case SECONDARY:
ord = cei.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, str, 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 <code>Object</code> to compare against this object.
*
* @return <code>true</code> if the specified object is equal to this object,
<code>false</code> otherwise.
*/
public boolean equals(Object obj)
{
if (obj == this)
return true;
else
return false;
}
/**
* This method returns a hash value for this object.
*
* @return A hash value for this object.
*/
public int hashCode()
{
return System.identityHashCode(this);
}
/**
* This method creates a copy of this object.
*
* @return A copy of this object.
*/
public Object clone()
{
return super.clone();
}
}
/* CollationElementIterator.java -- Walks through collation elements
Copyright (C) 1998, 1999, 2001, 2002, 2003 Free Software Foundation
This file is part of GNU Classpath.
GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING. If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.
Linking this library statically or dynamically with other modules is
making a combined work based on this library. Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.
As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module. An independent module is a module which is not derived from
or based on this library. If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so. If you do not wish to do so, delete this
exception statement from your version. */
package java.text;
import java.util.Vector;
import java.util.NoSuchElementException;
import java.util.Map;
import java.util.SortedMap;
/* Written using "Java Class Libraries", 2nd edition, plus online
* API docs for JDK 1.2 from http://www.javasoft.com.
* Status: Believed complete and correct to JDK 1.1.
*/
/**
* This class walks through the character collation elements of a
* <code>String</code> as defined by the collation rules in an instance of
* <code>RuleBasedCollator</code>. There is no public constructor for
* this class. An instance is created by calling the
* <code>getCollationElementIterator</code> method on
* <code>RuleBasedCollator</code>.
*
* @author Aaron M. Renn <address@hidden>
* @author Tom Tromey <address@hidden>
*/
public final class CollationElementIterator
{
/**
* This is a constant value that is returned to indicate that the end of
* the string was encountered.
*/
public static final int NULLORDER = -1;
/**
* This is the RuleBasedCollator this object was created from.
*/
private RuleBasedCollator collator;
/**
* This is the String that is being iterated over.
*/
private String text;
/**
* This is the index into the collation decomposition where we are currently
scanning.
*/
private int index;
/**
* This is the index into the String where we are currently scanning.
*/
private int textIndex;
/**
* Array containing the collation decomposition of the
* text given to the constructor.
*/
private Object[] text_decomposition;
/**
* This method initializes a new instance of
<code>CollationElementIterator</code>
* to iterate over the specified <code>String</code> using the rules in the
* specified <code>RuleBasedCollator</code>.
*
* @param collator The <code>RuleBasedCollation</code> used for calculating
collation values
* @param text The <code>String</code> to iterate over.
*/
CollationElementIterator (RuleBasedCollator collator, String text)
{
this.collator = collator;
setText (text);
}
RuleBasedCollator.CollationElement nextBlock()
{
if (index >= text_decomposition.length)
return null;
RuleBasedCollator.CollationElement e =
(RuleBasedCollator.CollationElement) text_decomposition[index++];
textIndex += e.char_seq.length();
return e;
}
RuleBasedCollator.CollationElement previousBlock()
{
if (index == 0)
return null;
index--;
RuleBasedCollator.CollationElement e =
(RuleBasedCollator.CollationElement) text_decomposition[index];
textIndex -= e.char_seq.length();
return e;
}
/**
* This method returns the collation ordering value of the next character
sequence
* in the string (it may be an extended character following collation rules).
* This method will return <code>NULLORDER</code> if the
* end of the string was reached.
*
* @return The collation ordering value.
*/
public int next ()
{
RuleBasedCollator.CollationElement e = nextBlock ();
if (e == null)
return NULLORDER;
return e.getValue();
}
/**
* This method returns the collation ordering value of the previous character
* in the string. This method will return <code>NULLORDER</code> if the
* beginning of the string was reached.
*
* @return The collation ordering value.
*/
public int previous ()
{
RuleBasedCollator.CollationElement e = previousBlock ();
if (e == null)
return NULLORDER;
return e.getValue();
}
/**
* This method returns the primary order value for the given collation
* value.
*
* @param value The collation value returned from <code>next()</code> or
<code>previous()</code>.
*
* @return The primary order value of the specified collation value. This is
the high 16 bits.
*/
public static final int primaryOrder (int order)
{
// From the JDK 1.2 spec.
return order >>> 16;
}
/**
* This method resets the internal position pointer to read from the
* beginning of the <code>String again.
*/
public void reset ()
{
index = 0;
textIndex = 0;
}
/**
* This method returns the secondary order value for the given collation
* value.
*
* @param value The collation value returned from <code>next()</code> or
<code>previous()</code>.
*
* @return The secondary order value of the specified collation value. This
is the bits 8-15.
*/
public static final short secondaryOrder (int order)
{
// From the JDK 1.2 spec.
return (short) ((order >>> 8) & 255);
}
/**
* This method returns the tertiary order value for the given collation
* value.
*
* @param value The collation value returned from <code>next()</code> or
<code>previous()</code>.
*
* @return The tertiary order value of the specified collation value. This
is the low eight bits.
*/
public static final short tertiaryOrder (int order)
{
// From the JDK 1.2 spec.
return (short) (order & 255);
}
/**
* This method sets the <code>String</code> that it is iterating over
* to the specified <code>String</code>.
*
* @param The new <code>String</code> to iterate over.
*/
public void setText (String text)
{
int idx = 0;
this.text = text;
index = 0;
String work_text = text.intern();
Vector v = new Vector();
// Build element collection ordered as they come in "text".
while (idx < work_text.length())
{
String key, key_old;
try
{
Object object = null;
int p = 1;
// IMPROVE: use a TreeMap with a prefix-ordering rule.
key_old = key = null;
do
{
if (object != null)
key_old = key;
key = work_text.substring (idx, idx+p);
object = collator.prefix_tree.get (key);
p++;
}
while (idx+p <= work_text.length());
if (object == null)
key = key_old;
RuleBasedCollator.CollationElement prefix =
(RuleBasedCollator.CollationElement)collator.prefix_tree.get
(key);
if (prefix.expansion != null)
{
work_text = prefix.expansion + work_text.substring
(idx+prefix.char_seq.length());
idx = 0;
v.add (prefix);
}
else
{
if (!prefix.ignore)
v.add (prefix);
idx += prefix.char_seq.length ();
}
}
catch (NullPointerException _)
{
RuleBasedCollator.CollationElement e =
collator.getDefaultElement(work_text.charAt (idx));
v.add (e);
idx++;
}
}
text_decomposition = v.toArray();
}
/**
* This method sets the <code>String</code> that it is iterating over
* to the <code>String</code> represented by the specified
* <code>CharacterIterator</code>.
*
* @param ci The <code>CharacterIterator</code> containing the new
<code>String</code> to iterate over.
*/
public void setText (CharacterIterator ci)
{
StringBuffer sb = new StringBuffer ("");
// For now assume we read from the beginning of the string.
char c = ci.first ();
while (c != CharacterIterator.DONE)
{
sb.append (c);
c = ci.next ();
}
setText (sb.toString ());
}
/**
* This method returns the current offset into the <code>String</code>
* that is being iterated over.
*
* @return The iteration index position.
*/
public int getOffset ()
{
return textIndex;
}
/**
* This method sets the iteration index position into the current
* <code>String</code> to the specified value. This value must not
* be negative and must not be greater than the last index position
* in the <code>String</code>.
*
* @param offset The new iteration index position.
*
* @exception IllegalArgumentException If the new offset is not valid.
*/
public void setOffset (int offset)
{
if (offset < 0)
throw new IllegalArgumentException ("Negative offset: " + offset);
if ((text.length () > 0) && (offset > 0))
throw new IllegalArgumentException ("Offset too large: " + offset);
else if (offset > (text.length () - 1))
throw new IllegalArgumentException ("Offset too large: " + offset);
textIndex = 0;
for (int i=0;i<text_decomposition.length;i++)
{
RuleBasedCollator.CollationElement e =
(RuleBasedCollator.CollationElement) text_decomposition[i];
int idx = textIndex + e.char_seq.length();
if (idx > offset)
break;
textIndex = idx;
}
}
/**
* This method returns the maximum length of any expansion sequence that
* ends with the specified collation order value. (Whatever that means).
*
* @param value The collation order value
*
* @param The maximum length of an expansion sequence.
*/
public int getMaxExpansion (int value)
{
return 1;
}
}
--- classpath-public/java/text/RuleBasedCollator.java 2003-11-19
20:44:22.000000000 +0100
+++ classpath/java/text/RuleBasedCollator.java 2003-12-13 19:39:31.000000000
+0100
@@ -39,6 +39,9 @@
package java.text;
import java.util.Vector;
+import java.util.Enumeration;
+import java.util.HashMap;
+import java.util.Comparator;
/* Written using "Java Class Libraries", 2nd edition, plus online
* API docs for JDK 1.2 from http://www.javasoft.com.
@@ -60,7 +63,10 @@
* <li> Reset: '&' : <text>
* </ul>
* The modifier character indicates that accents sort backward as is the
- * case with French. The relational operators specify how the text
+ * case with French. The modifier applies to all rules <b>after</b>
+ * the modifier but before the next primary sequence. If placed at the end
+ * of the sequence if applies to all unknown accented character.
+ * The relational operators specify how the text
* argument relates to the previous term. The relation characters have
* the following meanings:
* <ul>
@@ -111,6 +117,9 @@
* anywhere in the previous rule string segment so the rule following the
* reset rule cannot be inserted.
* <p>
+ * "< a & A @ < e & E < f& F" - This sequence is equivalent
to the following
+ * "< a & A < E & e < f & F".
+ * <p>
* For a description of the various comparison strength types, see the
* documentation for the <code>Collator</code> class.
* <p>
@@ -132,270 +141,518 @@
*
* @author Aaron M. Renn <address@hidden>
* @author Tom Tromey <address@hidden>
- * @date March 25, 1999
+ * @author Guilhem Lavaux <address@hidden>
+ * @date August 17, 2003
*/
public class RuleBasedCollator extends Collator
{
- final class CollationElement
+ class CollationElement
{
String char_seq;
int primary;
short secondary;
short tertiary;
+ short equality;
+ boolean ignore;
+ String expansion;
- CollationElement (String char_seq, int primary, short secondary, short
tertiary)
+ CollationElement(String char_seq, int primary, short secondary, short
tertiary,
+ short equality, String expansion)
{
this.char_seq = char_seq;
this.primary = primary;
this.secondary = secondary;
this.tertiary = tertiary;
+ this.equality = equality;
+ this.ignore = false;
+ this.expansion = expansion;
+ }
+
+ CollationElement(String char_seq)
+ {
+ this.char_seq = char_seq;
+ this.ignore = true;
+ }
+
+ final int getValue()
+ {
+ return (primary << 16) + (secondary << 8) + tertiary;
}
} // inner class CollationElement
- /**
- * This the the original rule string.
- */
- private String rules;
+ class CollationBlock
+ {
+ int value;
+ String textBlock;
+ }
- /**
- * This is the table of collation element values
- */
- private Object[] ce_table;
-
- /**
- * This method initializes a new instance of <code>RuleBasedCollator</code>
- * with the specified collation rules. Note that an application normally
- * obtains an instance of <code>RuleBasedCollator</code> by calling the
- * <code>getInstance</code> method of <code>Collator</code>. 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
+ class CollationSorter
{
- if (rules.equals (""))
- throw new ParseException ("empty rule set", 0);
+ static final int GREATERP = 0;
+ static final int GREATERS = 1;
+ static final int GREATERT = 2;
+ static final int EQUAL = 3;
+ static final int RESET = 4;
+ static final int IGNORE = 5;
+ static final int INVERSE_SECONDARY = 6;
- this.rules = rules;
- Vector vec = new Vector();
- boolean ignore_chars = true;
- int primary_seq = 0;
- short secondary_seq = 0;
- short tertiary_seq = 0;
- StringBuffer argument = new StringBuffer();
- int len = rules.length();
+ int comparisonType;
+ String textElement;
+ int hashText;
+ int offset;
+
+ String expansionOrdering;
+ }
+
+ static int findPrefixLength(String prefix, String s)
+ {
+ int i;
+
+ for (i=0;i<prefix.length() && i < s.length();i++)
+ {
+ if (prefix.charAt(i) != s.charAt(i))
+ return i;
+ }
+ return i;
+ }
+
+ void mergeRules(int offset, String starter, Vector main, Vector patch)
+ throws ParseException
+ {
+ Enumeration elements = main.elements();
+ int insertion_point = -1;
+ int max_length = 0;
- for (int index = 0; index < len; ++index)
+ /* 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++)
{
- char c = rules.charAt (index);
+ int j = 0;
+
+ while (j < main.size())
+ {
+ CollationSorter rule1 = (CollationSorter)patch.elementAt (i);
+ CollationSorter rule2 = (CollationSorter)main.elementAt (j);
+
+ if (rule1.textElement.equals (rule2.textElement))
+ main.removeElementAt (j);
+ else
+ j++;
+ }
+ }
- // Just skip whitespace.
- if (Character.isWhitespace (c))
- continue;
+ // Find the insertion point... O(N)
+ for (int i=0;i<main.size();i++)
+ {
+ CollationSorter sorter = (CollationSorter)main.elementAt(i);
+ int length = findPrefixLength (starter, sorter.textElement);
+
+ if (length > max_length)
+ {
+ max_length = length;
+ insertion_point = i+1;
+ }
+ }
- // Primary difference
- if (c == '<')
- {
- ignore_chars = false;
- CollationElement e = new CollationElement (argument.toString(),
primary_seq,
- secondary_seq,
- tertiary_seq);
- secondary_seq = 0;
- tertiary_seq = 0;
- ++primary_seq;
-
- vec.add (e);
- argument.setLength (0);
- continue;
- }
+ if (insertion_point < 0)
+ throw new ParseException("no insertion point found for " + starter,
offset);
- // Secondary difference
- if (c == ';')
- {
- if (primary_seq == 0)
- throw new ParseException (rules, index);
+ 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.elementAt (0);
+ CollationSorter expansionPrefix = (CollationSorter)main.elementAt
(insertion_point-1);
+
+ sorter.expansionOrdering = starter.substring (max_length); // Skip the
first good prefix element
+
+ main.insertElementAt (sorter, insertion_point);
+
+ /*
+ * This is a new set of rules. Append to the list.
+ */
+ patch.removeElementAt (0);
+ insertion_point = main.size();
+ }
- CollationElement e = new CollationElement (argument.toString(),
primary_seq,
- secondary_seq,
- tertiary_seq);
- ++secondary_seq;
- tertiary_seq = 0;
-
- vec.add (e);
- argument.setLength (0);
- continue;
- }
+ // Now insert all elements of patch at the insertion point.
+ for (int i=0;i<patch.size();i++)
+ main.insertElementAt (patch.elementAt (i), i+insertion_point);
- // Tertiary difference
- if (c == ',')
- {
- if (primary_seq == 0)
- throw new ParseException (rules, index);
+ }
- CollationElement e = new CollationElement (argument.toString(),
primary_seq,
- secondary_seq,
- tertiary_seq);
- ++tertiary_seq;
-
- vec.add (e);
- argument.setLength (0);
- continue;
- }
+ int subParseString(boolean stop_on_reset, Vector 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;
- // Is equal to
- if (c == '=')
- {
- if (primary_seq == 0)
- throw new ParseException (rules, index);
+ isModifier = nextIsModifier;
+ nextIsModifier = false;
- CollationElement e = new CollationElement (argument.toString(),
primary_seq,
- secondary_seq,
- tertiary_seq);
- vec.add (e);
- argument.setLength (0);
- continue;
- }
+ if (eatingChars && c != '\'')
+ {
+ doubleQuote = false;
+ sb.append (c);
+ continue;
+ }
+ if (doubleQuote && eatingChars)
+ {
+ sb.append (c);
+ doubleQuote = false;
+ continue;
+ }
- // Sort accents backwards
- if (c == '@')
- {
- throw new ParseException("French style accents not implemented
yet", 0);
- }
+ switch (c) {
+ case '!':
+ throw new ParseException ("Modifier '!' is not yet supported by
Classpath", i+base_offset);
+ case '<':
+ ignoreChars = false;
+ type = CollationSorter.GREATERP;
+ break;
+ case ';':
+ if (!ignoreChars)
+ type = CollationSorter.GREATERS;
+ else
+ type = CollationSorter.IGNORE;
+ break;
+ case ',':
+ if (!ignoreChars)
+ type = CollationSorter.GREATERT;
+ else
+ type = CollationSorter.IGNORE;
+ break;
+ case '=':
+ if (!ignoreChars)
+ type = CollationSorter.EQUAL;
+ else
+ type = CollationSorter.IGNORE;
+ 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;
+ }
- // Reset command
- if (c == '&')
- {
- throw new ParseException("Reset not implemented yet", 0);
- }
+ if (type < 0)
+ continue;
- // See if we are still reading characters to skip
- if (ignore_chars == true)
- {
- CollationElement e = new CollationElement (c + "", 0, (short)0,
- (short)0);
- vec.add(e);
- 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);
+ Vector sorted_rules = new Vector();
+ 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;
+ }
- argument.append (c);
+ CollationSorter sorter = new CollationSorter();
+
+ sorter.comparisonType = operator;
+ sorter.textElement = sb.toString();
+ sorter.hashText = sorter.textElement.hashCode();
+ sorter.offset = base_offset+rules.length();
+ sb.setLength(0);
+
+ v.add(sorter);
+ operator = type;
}
- if (argument.length() > 0)
+ if (operator >= 0)
{
- CollationElement e = new CollationElement (argument.toString(),
primary_seq,
- secondary_seq, tertiary_seq);
- vec.add (e);
+ 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);
+
+ sorter.comparisonType = operator;
+ sorter.textElement = sb.toString();
+ sorter.hashText = sorter.textElement.hashCode();
+ sorter.offset = base_offset+pos;
+ v.add (sorter);
}
- ce_table = vec.toArray();
+ 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()
+ private Vector parseString(String rules) throws ParseException
{
- RuleBasedCollator c = (RuleBasedCollator) super.clone ();
- return c;
+ Vector v = new Vector();
+
+ // result of the first subParseString is not certain (may be -1 or a
positive integer). But we
+ // do not care.
+ subParseString (false, v, 0, rules);
+
+ return v;
}
/**
- * This method returns an integer which indicates whether the first
- * specified <code>String</code> 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 <code>String</code> to compare.
- * @param target A second <code>String</code> to compare to the first.
- *
- * @return A negative integer if source < target, a positive integer
- * if source > target, or 0 if source == target.
+ * This the the original rule string.
*/
- public int compare (String source, String target)
- {
- CollationElementIterator cs = getCollationElementIterator (source);
- CollationElementIterator ct = getCollationElementIterator (target);
+ private String rules;
+
+ /**
+ * This is the table of collation element values
+ */
+ private Object[] ce_table;
- while (true)
+ /**
+ * Quick-prefix finder.
+ */
+ HashMap prefix_tree;
+
+ /**
+ * This is the value of the last sequence entered into
+ * <code>ce_table</code>. It is used to compute the
+ * ordering value of unspecified character.
+ */
+ private int last_primary_value;
+
+ /**
+ * This variable is true if accents need to be sorted
+ * in the other direction.
+ */
+ private boolean inverseAccentComparison;
+
+ private void buildCollationVector(Vector parsedElements) throws
ParseException
+ {
+ int primary_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;
+ Vector v = new Vector();
+
+ // elts is completely sorted.
+element_loop:
+ for (int i=0;i<parsedElements.size();i++)
{
- int os = cs.next();
- int ot = ct.next();
+ CollationSorter elt = (CollationSorter)parsedElements.elementAt (i);
+ boolean ignoreChar = false;
- // Check for end of string
- if (os == CollationElementIterator.NULLORDER
- && ot == CollationElementIterator.NULLORDER)
+ switch (elt.comparisonType)
{
- // Source and target string are equal.
- return 0;
+ 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++;
+ equality_seq = 0;
+ break;
+ case CollationSorter.IGNORE:
+ ignoreChar = true;
+ 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);
}
- else if (os == CollationElementIterator.NULLORDER)
- {
- // Source string is shorter, so return "less than".
- return -1;
- }
- else if (ot == CollationElementIterator.NULLORDER)
+
+ CollationElement e;
+
+ if (!ignoreChar)
{
- // Target string is shorter, so return "greater than".
- return 1;
+ e = new CollationElement (elt.textElement, primary_seq,
+ secondary_seq, tertiary_seq,
+ equality_seq, elt.expansionOrdering);
}
+ else
+ e = new CollationElement (elt.textElement);
- // We know chars are totally equal, so skip
- if (os == ot)
- continue;
+ v.add(e);
+ }
- // Check for primary strength differences
- int prim1 = cs.primaryOrder (os);
- int prim2 = ct.primaryOrder (ot);
+ this.inverseAccentComparison = inverseComparisons;
- if (prim1 < prim2)
- return -1;
- else if (prim1 > prim2)
- return 1;
- else if (getStrength() == PRIMARY)
- continue;
+ ce_table = v.toArray();
- // Check for secondary strength differences
- int sec1 = cs.secondaryOrder (os);
- int sec2 = ct.secondaryOrder (ot);
+ last_primary_value = primary_seq+1;
+ }
- if (sec1 < sec2)
- return -1;
- else if (sec1 > sec2)
- return 1;
- else if (getStrength() == SECONDARY)
- continue;
+ /**
+ * 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();
- // Check for tertiary differences
- int tert1 = cs.tertiaryOrder (os);
- int tert2 = ct.tertiaryOrder (ot);
+ for (int i=0;i<ce_table.length;i++)
+ {
+ CollationElement e = (CollationElement)ce_table[i];
- if (tert1 < tert2)
- return -1;
- else if (tert1 > tert2)
- return 1;
+ prefix_tree.put (e.char_seq, e);
}
}
/**
- * 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.
+ * This method initializes a new instance of <code>RuleBasedCollator</code>
+ * with the specified collation rules. Note that an application normally
+ * obtains an instance of <code>RuleBasedCollator</code> by calling the
+ * <code>getInstance</code> method of <code>Collator</code>. That method
+ * automatically loads the proper set of rules for the desired locale.
*
- * @param obj The <code>Object</code> to compare against this object.
+ * @param rules The collation rule string.
*
- * @return <code>true</code> if the specified object is equal to this
object, <code>false</code> otherwise.
+ * @exception ParseException If the rule string contains syntax errors.
*/
- public boolean equals (Object obj)
+ public RuleBasedCollator(String rules) throws ParseException
{
- if (obj == this)
- return true;
+ this.rules = rules;
+
+ if (rules.equals (""))
+ throw new ParseException ("Empty rule set", 0);
- return false;
+ buildCollationVector (parseString (rules));
+ buildPrefixAccess();
+ }
+
+ /**
+ * This method returns a <code>String</code> containing the collation rules
+ * for this object.
+ *
+ * @return The collation rules for this object.
+ */
+ public String getRules()
+ {
+ return(rules);
+ }
+
+ /**
+ * This method builds a default collation element without invoking
+ * the database created from the rules passed to the constructor.
+ */
+ 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);
}
/**
@@ -403,52 +660,146 @@
* for the specified <code>String</code> under the collation rules for this
* object.
*
- * @param source The <code>String</code> to return the
<code>CollationElementIterator</code> instance for.
+ * @param str The <code>String</code> to return the
<code>CollationElementIterator</code> instance for.
*
* @return A <code>CollationElementIterator</code> for the specified
<code>String</code>.
*/
- public CollationElementIterator getCollationElementIterator (String source)
+ public CollationElementIterator getCollationElementIterator(String str)
{
- return new CollationElementIterator (source, this);
- }
+ return new CollationElementIterator (this, str);
+ }
/**
* This method returns an instance of <code>CollationElementIterator</code>
* for the <code>String</code> represented by the specified
* <code>CharacterIterator</code>.
*
- * @param source The <code>CharacterIterator</code> with the desired
<code>String</code>.
+ * @param ci The <code>CharacterIterator</code> with the desired
<code>String</code>.
*
* @return A <code>CollationElementIterator</code> for the specified
<code>String</code>.
*/
- public CollationElementIterator getCollationElementIterator
(CharacterIterator source)
+ public CollationElementIterator
getCollationElementIterator(CharacterIterator ci)
{
- StringBuffer sb = new StringBuffer();
+ StringBuffer sb = 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())
+ char c = ci.first();
+ while (c != CharacterIterator.DONE)
{
- sb.append (c);
+ sb.append(c);
+ c = ci.next();
}
return getCollationElementIterator (sb.toString());
}
/**
+ * This method returns an integer which indicates whether the first
+ * specified <code>String</code> 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 <code>String</code> to compare.
+ * @param s2 A second <code>String</code> 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 s1, String s2)
+ {
+ CollationElementIterator cei1 = getCollationElementIterator (s1);
+ CollationElementIterator cei2 = getCollationElementIterator (s2);
+
+ for(;;)
+ {
+ CollationElement ord1block = cei1.nextBlock();
+ CollationElement ord2block = cei2.nextBlock();
+ int ord1;
+ int ord2;
+
+ // Hehehe. What we would do not to use if.
+ try
+ {
+ ord1 = ord1block.getValue();
+ }
+ catch (NullPointerException _)
+ {
+ if (ord2block == null)
+ return 0;
+ return -1;
+ }
+
+ try
+ {
+ ord2 = ord2block.getValue();
+ }
+ catch (NullPointerException _)
+ {
+ return 1;
+ }
+
+ // We know chars are totally equal, so skip
+ if (ord1 == ord2)
+ {
+ if (getStrength() == IDENTICAL)
+ if (!ord1block.char_seq.equals (ord2block.char_seq))
+ return ord1block.char_seq.compareTo (ord2block.char_seq);
+ continue;
+ }
+
+ // Check for primary strength differences
+ int prim1 = cei1.primaryOrder (ord1);
+ int prim2 = cei2.primaryOrder (ord2);
+
+ if (prim1 < prim2)
+ return(-1);
+ else if (prim1 > prim2)
+ return(1);
+ else if (getStrength() == PRIMARY)
+ continue;
+
+ // Check for secondary strength differences
+ int sec1 = cei1.secondaryOrder (ord1);
+ int sec2 = cei2.secondaryOrder (ord2);
+
+ if (sec1 < sec2)
+ return(-1);
+ else if (sec1 > sec2)
+ return(1);
+ else if (getStrength() == SECONDARY)
+ continue;
+
+ // Check for tertiary differences
+ int tert1 = cei1.tertiaryOrder (ord1);
+ int tert2 = cei2.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.char_seq.compareTo (ord2block.char_seq);
+ }
+ }
+
+ /**
* This method returns an instance of <code>CollationKey</code> for the
* specified <code>String</code>. 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 <code>String</code> to create a
<code>CollationKey</code> for.
+ * @param str The <code>String</code> to create a <code>CollationKey</code>
for.
*
* @return A <code>CollationKey</code> for the specified <code>String</code>.
*/
- public CollationKey getCollationKey (String source)
+ public CollationKey getCollationKey(String str)
{
- CollationElementIterator cei = getCollationElementIterator (source);
- Vector vec = new Vector (25);
+ CollationElementIterator cei = getCollationElementIterator (str);
+ Vector vect = new Vector(25);
int ord = cei.next();
cei.reset(); //set to start of string
@@ -468,34 +819,40 @@
break;
}
- vec.add (new Integer (ord));
+ vect.add (new Integer (ord));
ord = cei.next(); //increment to next key
}
- Object[] objarr = vec.toArray();
- byte[] key = new byte [objarr.length * 4];
+ 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);
+ 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);
+ return new CollationKey (this, str, key);
}
/**
- * This method returns a <code>String</code> containing the collation rules
- * for this object.
+ * 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.
*
- * @return The collation rules for this object.
+ * @param obj The <code>Object</code> to compare against this object.
+ *
+ * @return <code>true</code> if the specified object is equal to this
object, <code>false</code> otherwise.
*/
- public String getRules()
+ public boolean equals(Object obj)
{
- return rules;
+ if (obj == this)
+ return true;
+ else
+ return false;
}
/**
@@ -505,31 +862,16 @@
*/
public int hashCode()
{
- return System.identityHashCode (this);
+ return System.identityHashCode(this);
}
/**
- * This method calculates the collation element value for the specified
- * character(s).
+ * This method creates a copy of this object.
+ *
+ * @return A copy of this object.
*/
- int getCollationElementValue (String source)
+ public Object clone()
{
- CollationElement e = null;
-
- // The table is sorted. Change to a binary search later.
- for (int i = 0; i < ce_table.length; i++)
- if (((CollationElement) ce_table [i]).char_seq.equals (source))
- {
- e = (CollationElement) ce_table [i];
- break;
- }
-
- if (e == null)
- e = new CollationElement (source, 0xFFFF, (short)0xFF, (short)0xFF);
-
- int retval = (e.primary << 16) + (e.secondary << 8) + e.tertiary;
-
- return retval;
+ return super.clone();
}
-
-} // class RuleBaseCollator
+}
--- classpath-public/java/text/CollationElementIterator.java 2003-11-19
20:44:22.000000000 +0100
+++ classpath/java/text/CollationElementIterator.java 2003-12-07
19:47:47.000000000 +0100
@@ -38,6 +38,11 @@
package java.text;
+import java.util.Vector;
+import java.util.NoSuchElementException;
+import java.util.Map;
+import java.util.SortedMap;
+
/* Written using "Java Class Libraries", 2nd edition, plus online
* API docs for JDK 1.2 from http://www.javasoft.com.
* Status: Believed complete and correct to JDK 1.1.
@@ -73,11 +78,22 @@
private String text;
/**
- * This is the index into the String where we are currently scanning.
+ * This is the index into the collation decomposition where we are currently
scanning.
*/
private int index;
/**
+ * This is the index into the String where we are currently scanning.
+ */
+ private int textIndex;
+
+ /**
+ * Array containing the collation decomposition of the
+ * text given to the constructor.
+ */
+ private Object[] text_decomposition;
+
+ /**
* This method initializes a new instance of
<code>CollationElementIterator</code>
* to iterate over the specified <code>String</code> using the rules in the
* specified <code>RuleBasedCollator</code>.
@@ -85,27 +101,73 @@
* @param collator The <code>RuleBasedCollation</code> used for calculating
collation values
* @param text The <code>String</code> to iterate over.
*/
- CollationElementIterator (String text, RuleBasedCollator collator)
+ CollationElementIterator (RuleBasedCollator collator, String text)
{
- setText (text);
this.collator = collator;
+
+ setText (text);
+ }
+
+ RuleBasedCollator.CollationElement nextBlock()
+ {
+ if (index >= text_decomposition.length)
+ return null;
+
+ RuleBasedCollator.CollationElement e =
+ (RuleBasedCollator.CollationElement) text_decomposition[index++];
+
+ textIndex += e.char_seq.length();
+
+ return e;
+ }
+
+ RuleBasedCollator.CollationElement previousBlock()
+ {
+ if (index == 0)
+ return null;
+
+ index--;
+ RuleBasedCollator.CollationElement e =
+ (RuleBasedCollator.CollationElement) text_decomposition[index];
+
+ textIndex -= e.char_seq.length();
+
+ return e;
}
/**
- * This method returns the collation ordering value of the next character
- * in the string. This method will return <code>NULLORDER</code> if the
+ * This method returns the collation ordering value of the next character
sequence
+ * in the string (it may be an extended character following collation rules).
+ * This method will return <code>NULLORDER</code> if the
* end of the string was reached.
*
* @return The collation ordering value.
*/
- public int next()
+ public int next ()
{
- if (index == text.length())
+ RuleBasedCollator.CollationElement e = nextBlock ();
+
+ if (e == null)
return NULLORDER;
+
+ return e.getValue();
+ }
+
+ /**
+ * This method returns the collation ordering value of the previous character
+ * in the string. This method will return <code>NULLORDER</code> if the
+ * beginning of the string was reached.
+ *
+ * @return The collation ordering value.
+ */
+ public int previous ()
+ {
+ RuleBasedCollator.CollationElement e = previousBlock ();
- String s = text.charAt (index) + "";
- index++;
- return collator.getCollationElementValue (s);
+ if (e == null)
+ return NULLORDER;
+
+ return e.getValue();
}
/**
@@ -126,9 +188,10 @@
* This method resets the internal position pointer to read from the
* beginning of the <code>String again.
*/
- public void reset()
+ public void reset ()
{
index = 0;
+ textIndex = 0;
}
/**
@@ -163,14 +226,69 @@
* This method sets the <code>String</code> that it is iterating over
* to the specified <code>String</code>.
*
- * @param text The new <code>String</code> to iterate over.
- *
- * @since 1.2
+ * @param The new <code>String</code> to iterate over.
*/
public void setText (String text)
{
+ int idx = 0;
+
this.text = text;
index = 0;
+
+ String work_text = text.intern();
+
+ Vector v = new Vector();
+ // Build element collection ordered as they come in "text".
+ while (idx < work_text.length())
+ {
+ String key, key_old;
+
+ try
+ {
+ Object object = null;
+ int p = 1;
+
+ // IMPROVE: use a TreeMap with a prefix-ordering rule.
+ key_old = key = null;
+ do
+ {
+ if (object != null)
+ key_old = key;
+ key = work_text.substring (idx, idx+p);
+ object = collator.prefix_tree.get (key);
+ p++;
+ }
+ while (idx+p <= work_text.length());
+
+ if (object == null)
+ key = key_old;
+
+ RuleBasedCollator.CollationElement prefix =
+ (RuleBasedCollator.CollationElement)collator.prefix_tree.get
(key);
+
+ if (prefix.expansion != null)
+ {
+ work_text = prefix.expansion + work_text.substring
(idx+prefix.char_seq.length());
+ idx = 0;
+ v.add (prefix);
+ }
+ else
+ {
+ if (!prefix.ignore)
+ v.add (prefix);
+ idx += prefix.char_seq.length ();
+ }
+ }
+ catch (NullPointerException _)
+ {
+ RuleBasedCollator.CollationElement e =
collator.getDefaultElement(work_text.charAt (idx));
+
+ v.add (e);
+ idx++;
+ }
+ }
+
+ text_decomposition = v.toArray();
}
/**
@@ -182,17 +300,17 @@
*/
public void setText (CharacterIterator ci)
{
- // For now assume we read from the beginning of the string.
- char c = ci.first();
StringBuffer sb = new StringBuffer ("");
+ // For now assume we read from the beginning of the string.
+ char c = ci.first ();
while (c != CharacterIterator.DONE)
{
sb.append (c);
- c = ci.next();
+ c = ci.next ();
}
- setText (sb.toString());
+ setText (sb.toString ());
}
/**
@@ -200,12 +318,10 @@
* that is being iterated over.
*
* @return The iteration index position.
- *
- * @since 1.2
*/
- public int getOffset()
+ public int getOffset ()
{
- return index;
+ return textIndex;
}
/**
@@ -228,8 +344,18 @@
else if (offset > (text.length () - 1))
throw new IllegalArgumentException ("Offset too large: " + offset);
- index = offset;
- }
+ textIndex = 0;
+ for (int i=0;i<text_decomposition.length;i++)
+ {
+ RuleBasedCollator.CollationElement e =
+ (RuleBasedCollator.CollationElement) text_decomposition[i];
+ int idx = textIndex + e.char_seq.length();
+
+ if (idx > offset)
+ break;
+ textIndex = idx;
+ }
+ }
/**
* This method returns the maximum length of any expansion sequence that
@@ -241,26 +367,6 @@
*/
public int getMaxExpansion (int value)
{
- //************ Implement me!!!!!!!!!
- return 5;
+ return 1;
}
-
- /**
- * This method returns the collation ordering value of the previous character
- * in the string. This method will return <code>NULLORDER</code> if the
- * beginning of the string was reached.
- *
- * @return The collation ordering value.
- */
- public int previous()
- {
- --index;
- if (index < 0)
- return NULLORDER;
-
- String s = text.charAt (index) + "";
- return collator.getCollationElementValue (s);
- }
-
-} // class CollationElementIterator
-
+}
pgpD0vpE5i929.pgp
Description: PGP signature
- [PATCH] RuleBasedCollator,
Guilhem Lavaux <=