001: /*
002: *
003: * %W% %E%
004: *
005: * Portions Copyright 2000-2006 Sun Microsystems, Inc. All Rights
006: * Reserved. Use is subject to license terms.
007: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
008: *
009: * This program is free software; you can redistribute it and/or
010: * modify it under the terms of the GNU General Public License version
011: * 2 only, as published by the Free Software Foundation.
012: *
013: * This program is distributed in the hope that it will be useful, but
014: * WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * General Public License version 2 for more details (a copy is
017: * included at /legal/license.txt).
018: *
019: * You should have received a copy of the GNU General Public License
020: * version 2 along with this work; if not, write to the Free Software
021: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
022: * 02110-1301 USA
023: *
024: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
025: * Clara, CA 95054 or visit www.sun.com if you need additional
026: * information or have any questions.
027: */
028:
029: /*
030: * (C) Copyright Taligent, Inc. 1996, 1997 - All Rights Reserved
031: * (C) Copyright IBM Corp. 1996-1998 - All Rights Reserved
032: *
033: * The original version of this source code and documentation is copyrighted
034: * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
035: * materials are provided under terms of a License Agreement between Taligent
036: * and Sun. This technology is protected by multiple US and International
037: * patents. This notice and attribution to Taligent may not be removed.
038: * Taligent is a registered trademark of Taligent, Inc.
039: *
040: */
041:
042: package java.text;
043:
044: import java.util.Vector;
045: import sun.text.CompactIntArray;
046: import sun.text.IntHashtable;
047: import sun.text.Normalizer;
048: import sun.text.ComposedCharIter;
049: import sun.text.NormalizerUtilities;
050:
051: /**
052: * This class contains all the code to parse a RuleBasedCollator pattern
053: * and build a RBCollationTables object from it. A particular instance
054: * of tis class exists only during the actual build process-- once an
055: * RBCollationTables object has been built, the RBTableBuilder object
056: * goes away. This object carries all of the state which is only needed
057: * during the build process, plus a "shadow" copy of all of the state
058: * that will go into the tables object itself. This object communicates
059: * with RBCollationTables through a separate class, RBCollationTables.BuildAPI,
060: * this is an inner class of RBCollationTables and provides a separate
061: * private API for communication with RBTableBuilder.
062: * This class isn't just an inner class of RBCollationTables itself because
063: * of its large size. For source-code readability, it seemed better for the
064: * builder to have its own source file.
065: */
066: final class RBTableBuilder {
067:
068: public RBTableBuilder(RBCollationTables.BuildAPI tables) {
069: this .tables = tables;
070: }
071:
072: /**
073: * Create a table-based collation object with the given rules.
074: * This is the main function that actually builds the tables and
075: * stores them back in the RBCollationTables object. It is called
076: * ONLY by the RBCollationTables constructor.
077: * @see java.util.RuleBasedCollator#RuleBasedCollator
078: * @exception ParseException If the rules format is incorrect.
079: */
080: public void build(String pattern, int decmp) throws ParseException {
081: boolean isSource = true;
082: int i = 0;
083: String expChars;
084: String groupChars;
085: if (pattern.length() == 0)
086: throw new ParseException("Build rules empty.", 0);
087:
088: // This array maps Unicode characters to their collation ordering
089: mapping = new CompactIntArray((int) RBCollationTables.UNMAPPED);
090:
091: // Normalize the build rules. Find occurances of all decomposed characters
092: // and normalize the rules before feeding into the builder. By "normalize",
093: // we mean that all precomposed Unicode characters must be converted into
094: // a base character and one or more combining characters (such as accents).
095: // When there are multiple combining characters attached to a base character,
096: // the combining characters must be in their canonical order
097: //
098: Normalizer.Mode mode = NormalizerUtilities
099: .toNormalizerMode(decmp);
100: pattern = Normalizer.normalize(pattern, mode, 0, true);
101:
102: // Build the merged collation entries
103: // Since rules can be specified in any order in the string
104: // (e.g. "c , C < d , D < e , E .... C < CH")
105: // this splits all of the rules in the string out into separate
106: // objects and then sorts them. In the above example, it merges the
107: // "C < CH" rule in just before the "C < D" rule.
108: //
109: mPattern = new MergeCollation(pattern);
110: int order = 0;
111:
112: // Now walk though each entry and add it to my own tables
113: for (i = 0; i < mPattern.getCount(); ++i) {
114: PatternEntry entry = mPattern.getItemAt(i);
115: if (entry != null) {
116: groupChars = entry.getChars();
117: if (groupChars.length() > 1) {
118: switch (groupChars.charAt(groupChars.length() - 1)) {
119: case '@':
120: frenchSec = true;
121: groupChars = groupChars.substring(0, groupChars
122: .length() - 1);
123: break;
124: case '!':
125: seAsianSwapping = true;
126: groupChars = groupChars.substring(0, groupChars
127: .length() - 1);
128: break;
129: }
130: }
131:
132: order = increment(entry.getStrength(), order);
133: expChars = entry.getExtension();
134:
135: if (expChars.length() != 0) {
136: addExpandOrder(groupChars, expChars, order);
137: } else if (groupChars.length() > 1) {
138: addContractOrder(groupChars, order);
139: } else {
140: char ch = groupChars.charAt(0);
141: addOrder(ch, order);
142: }
143: }
144: }
145:
146: addComposedChars();
147:
148: commit();
149: mapping.compact();
150:
151: tables.fillInTables(frenchSec, seAsianSwapping, mapping,
152: contractTable, expandTable, contractFlags, maxSecOrder,
153: maxTerOrder);
154: }
155:
156: /** Add expanding entries for pre-composed unicode characters so that this
157: * collator can be used reasonably well with decomposition turned off.
158: */
159: private void addComposedChars() throws ParseException {
160: StringBuffer buf = new StringBuffer(1);
161:
162: // Iterate through all of the pre-composed characters in Unicode
163: ComposedCharIter iter = new ComposedCharIter(false,
164: Normalizer.IGNORE_HANGUL);
165:
166: while (iter.hasNext()) {
167: char c = iter.next();
168:
169: if (getCharOrder(c) == RBCollationTables.UNMAPPED) {
170: //
171: // We don't already have an ordering for this pre-composed character.
172: //
173: // First, see if the decomposed string is already in our
174: // tables as a single contracting-string ordering.
175: // If so, just map the precomposed character to that order.
176: //
177: // TODO: What we should really be doing here is trying to find the
178: // longest initial substring of the decomposition that is present
179: // in the tables as a contracting character sequence, and find its
180: // ordering. Then do this recursively with the remaining chars
181: // so that we build a list of orderings, and add that list to
182: // the expansion table.
183: // That would be more correct but also significantly slower, so
184: // I'm not totally sure it's worth doing.
185: //
186: String s = iter.decomposition();
187: int contractOrder = getContractOrder(s);
188: if (contractOrder != RBCollationTables.UNMAPPED) {
189: addOrder(c, contractOrder);
190: } else {
191: //
192: // We don't have a contracting ordering for the entire string
193: // that results from the decomposition, but if we have orders
194: // for each individual character, we can add an expanding
195: // table entry for the pre-composed character
196: //
197: boolean allThere = true;
198: for (int i = 0; i < s.length(); i++) {
199: if (getCharOrder(s.charAt(i)) == RBCollationTables.UNMAPPED) {
200: allThere = false;
201: break;
202: }
203: }
204: if (allThere) {
205: buf.setLength(0);
206: buf.append(c);
207: addExpandOrder(buf.toString(), s,
208: RBCollationTables.UNMAPPED);
209: }
210: }
211: }
212: }
213: }
214:
215: /**
216: * Look up for unmapped values in the expanded character table.
217: *
218: * When the expanding character tables are built by addExpandOrder,
219: * it doesn't know what the final ordering of each character
220: * in the expansion will be. Instead, it just puts the raw character
221: * code into the table, adding CHARINDEX as a flag. Now that we've
222: * finished building the mapping table, we can go back and look up
223: * that character to see what its real collation order is and
224: * stick that into the expansion table. That lets us avoid doing
225: * a two-stage lookup later.
226: */
227: private final void commit() {
228: if (expandTable != null) {
229: for (int i = 0; i < expandTable.size(); i++) {
230: int[] valueList = (int[]) expandTable.elementAt(i);
231: for (int j = 0; j < valueList.length; j++) {
232: int order = valueList[j];
233: if (order < RBCollationTables.EXPANDCHARINDEX
234: && order > CHARINDEX) {
235: // found a expanding character that isn't filled in yet
236: char ch = (char) (order - CHARINDEX);
237:
238: // Get the real values for the non-filled entry
239: int realValue = getCharOrder(ch);
240:
241: if (realValue == RBCollationTables.UNMAPPED) {
242: // The real value is still unmapped, maybe it's ignorable
243: valueList[j] = IGNORABLEMASK & ch;
244: } else {
245: // just fill in the value
246: valueList[j] = realValue;
247: }
248: }
249: }
250: }
251: }
252: }
253:
254: /**
255: * Increment of the last order based on the comparison level.
256: */
257: private final int increment(int aStrength, int lastValue) {
258: switch (aStrength) {
259: case Collator.PRIMARY:
260: // increment priamry order and mask off secondary and tertiary difference
261: lastValue += PRIMARYORDERINCREMENT;
262: lastValue &= RBCollationTables.PRIMARYORDERMASK;
263: isOverIgnore = true;
264: break;
265: case Collator.SECONDARY:
266: // increment secondary order and mask off tertiary difference
267: lastValue += SECONDARYORDERINCREMENT;
268: lastValue &= RBCollationTables.SECONDARYDIFFERENCEONLY;
269: // record max # of ignorable chars with secondary difference
270: if (!isOverIgnore)
271: maxSecOrder++;
272: break;
273: case Collator.TERTIARY:
274: // increment tertiary order
275: lastValue += TERTIARYORDERINCREMENT;
276: // record max # of ignorable chars with tertiary difference
277: if (!isOverIgnore)
278: maxTerOrder++;
279: break;
280: }
281: return lastValue;
282: }
283:
284: /**
285: * Adds a character and its designated order into the collation table.
286: */
287: private final void addOrder(char ch, int anOrder) {
288: // See if the char already has an order in the mapping table
289: int order = mapping.elementAt(ch);
290:
291: if (order >= RBCollationTables.CONTRACTCHARINDEX) {
292: // There's already an entry for this character that points to a contracting
293: // character table. Instead of adding the character directly to the mapping
294: // table, we must add it to the contract table instead.
295:
296: key.setLength(0);
297: key.append(ch);
298: addContractOrder(key.toString(), anOrder);
299: } else {
300: // add the entry to the mapping table,
301: // the same later entry replaces the previous one
302: mapping.setElementAt(ch, anOrder);
303: }
304: }
305:
306: private final void addContractOrder(String groupChars, int anOrder) {
307: addContractOrder(groupChars, anOrder, true);
308: }
309:
310: /**
311: * Adds the contracting string into the collation table.
312: */
313: private final void addContractOrder(String groupChars, int anOrder,
314: boolean fwd) {
315: if (contractTable == null) {
316: contractTable = new Vector(INITIALTABLESIZE);
317: }
318:
319: // See if the initial character of the string already has a contract table.
320: int entry = mapping.elementAt(groupChars.charAt(0));
321: Vector entryTable = getContractValues(entry
322: - RBCollationTables.CONTRACTCHARINDEX);
323:
324: if (entryTable == null) {
325: // We need to create a new table of contract entries for this base char
326: int tableIndex = RBCollationTables.CONTRACTCHARINDEX
327: + contractTable.size();
328: entryTable = new Vector(INITIALTABLESIZE);
329: contractTable.addElement(entryTable);
330:
331: // Add the initial character's current ordering first. then
332: // update its mapping to point to this contract table
333: entryTable.addElement(new EntryPair(groupChars.substring(0,
334: 1), entry));
335: mapping.setElementAt(groupChars.charAt(0), tableIndex);
336: }
337:
338: // Now add (or replace) this string in the table
339: int index = RBCollationTables.getEntry(entryTable, groupChars,
340: fwd);
341: if (index != RBCollationTables.UNMAPPED) {
342: EntryPair pair = (EntryPair) entryTable.elementAt(index);
343: pair.value = anOrder;
344: } else {
345: EntryPair pair = (EntryPair) entryTable.lastElement();
346:
347: // NOTE: This little bit of logic is here to speed CollationElementIterator
348: // .nextContractChar(). This code ensures that the longest sequence in
349: // this list is always the _last_ one in the list. This keeps
350: // nextContractChar() from having to search the entire list for the longest
351: // sequence.
352: if (groupChars.length() > pair.entryName.length()) {
353: entryTable.addElement(new EntryPair(groupChars,
354: anOrder, fwd));
355: } else {
356: entryTable.insertElementAt(new EntryPair(groupChars,
357: anOrder, fwd), entryTable.size() - 1);
358: }
359: }
360:
361: // If this was a forward mapping for a contracting string, also add a
362: // reverse mapping for it, so that CollationElementIterator.previous
363: // can work right
364: if (fwd && groupChars.length() > 1) {
365: addContractFlags(groupChars);
366: addContractOrder(new StringBuffer(groupChars).reverse()
367: .toString(), anOrder, false);
368: }
369: }
370:
371: /**
372: * If the given string has been specified as a contracting string
373: * in this collation table, return its ordering.
374: * Otherwise return UNMAPPED.
375: */
376: private int getContractOrder(String groupChars) {
377: int result = RBCollationTables.UNMAPPED;
378: if (contractTable != null) {
379: Vector entryTable = getContractValues(groupChars.charAt(0));
380: if (entryTable != null) {
381: int index = RBCollationTables.getEntry(entryTable,
382: groupChars, true);
383: if (index != RBCollationTables.UNMAPPED) {
384: EntryPair pair = (EntryPair) entryTable
385: .elementAt(index);
386: result = pair.value;
387: }
388: }
389: }
390: return result;
391: }
392:
393: private final int getCharOrder(char ch) {
394: int order = mapping.elementAt(ch);
395:
396: if (order >= RBCollationTables.CONTRACTCHARINDEX) {
397: Vector groupList = getContractValues(order
398: - RBCollationTables.CONTRACTCHARINDEX);
399: EntryPair pair = (EntryPair) groupList.firstElement();
400: order = pair.value;
401: }
402: return order;
403: }
404:
405: /**
406: * Get the entry of hash table of the contracting string in the collation
407: * table.
408: * @param ch the starting character of the contracting string
409: */
410: Vector getContractValues(char ch) {
411: int index = mapping.elementAt(ch);
412: return getContractValues(index
413: - RBCollationTables.CONTRACTCHARINDEX);
414: }
415:
416: Vector getContractValues(int index) {
417: if (index >= 0) {
418: return (Vector) contractTable.elementAt(index);
419: } else // not found
420: {
421: return null;
422: }
423: }
424:
425: /**
426: * Adds the expanding string into the collation table.
427: */
428: private final void addExpandOrder(String contractChars,
429: String expandChars, int anOrder) throws ParseException {
430: // Create an expansion table entry
431: int tableIndex = addExpansion(anOrder, expandChars);
432:
433: // And add its index into the main mapping table
434: if (contractChars.length() > 1) {
435: addContractOrder(contractChars, tableIndex);
436: } else {
437: addOrder(contractChars.charAt(0), tableIndex);
438: }
439: }
440:
441: /**
442: * Create a new entry in the expansion table that contains the orderings
443: * for the given characers. If anOrder is valid, it is added to the
444: * beginning of the expanded list of orders.
445: */
446: private int addExpansion(int anOrder, String expandChars) {
447: if (expandTable == null) {
448: expandTable = new Vector(INITIALTABLESIZE);
449: }
450:
451: // If anOrder is valid, we want to add it at the beginning of the list
452: int offset = (anOrder == RBCollationTables.UNMAPPED) ? 0 : 1;
453:
454: int[] valueList = new int[expandChars.length() + offset];
455: if (offset == 1) {
456: valueList[0] = anOrder;
457: }
458:
459: for (int i = 0; i < expandChars.length(); i++) {
460: char ch = expandChars.charAt(i);
461: int mapValue = getCharOrder(ch);
462:
463: if (mapValue != RBCollationTables.UNMAPPED) {
464: valueList[i + offset] = mapValue;
465: } else {
466: // can't find it in the table, will be filled in by commit().
467: valueList[i + offset] = CHARINDEX + (int) ch;
468: }
469: }
470:
471: // Add the expanding char list into the expansion table.
472: int tableIndex = RBCollationTables.EXPANDCHARINDEX
473: + expandTable.size();
474: expandTable.addElement(valueList);
475:
476: return tableIndex;
477: }
478:
479: private void addContractFlags(String chars) {
480: char c;
481: int len = chars.length();
482: for (int i = 0; i < len; i++) {
483: c = chars.charAt(i);
484: contractFlags.put(c, 1);
485: }
486: }
487:
488: // ==============================================================
489: // constants
490: // ==============================================================
491: final static int CHARINDEX = 0x70000000; // need look up in .commit()
492:
493: private final static int IGNORABLEMASK = 0x0000ffff;
494: private final static int PRIMARYORDERINCREMENT = 0x00010000;
495: private final static int SECONDARYORDERINCREMENT = 0x00000100;
496: private final static int TERTIARYORDERINCREMENT = 0x00000001;
497: private final static int INITIALTABLESIZE = 20;
498: private final static int MAXKEYSIZE = 5;
499:
500: // ==============================================================
501: // instance variables
502: // ==============================================================
503:
504: // variables used by the build process
505: private RBCollationTables.BuildAPI tables = null;
506: private MergeCollation mPattern = null;
507: private boolean isOverIgnore = false;
508: private StringBuffer key = new StringBuffer(MAXKEYSIZE);
509: private IntHashtable contractFlags = new IntHashtable(100);
510:
511: // "shadow" copies of the instance variables in RBCollationTables
512: // (the values in these variables are copied back into RBCollationTables
513: // at the end of the build process)
514: private boolean frenchSec = false;
515: private boolean seAsianSwapping = false;
516:
517: private CompactIntArray mapping = null;
518: private Vector contractTable = null;
519: private Vector expandTable = null;
520:
521: private short maxSecOrder = 0;
522: private short maxTerOrder = 0;
523: }
|