001: /*
002: *
003: * @(#)MergeCollation.java 1.22 06/10/03
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, 1997 - 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.ArrayList;
045:
046: /**
047: * Utility class for normalizing and merging patterns for collation.
048: * Patterns are strings of the form <entry>*, where <entry> has the
049: * form:
050: * <pattern> := <entry>*
051: * <entry> := <separator><chars>{"/"<extension>}
052: * <separator> := "=", ",", ";", "<", "&"
053: * <chars>, and <extension> are both arbitrary strings.
054: * unquoted whitespaces are ignored.
055: * 'xxx' can be used to quote characters
056: * One difference from Collator is that & is used to reset to a current
057: * point. Or, in other words, it introduces a new sequence which is to
058: * be added to the old.
059: * That is: "a < b < c < d" is the same as "a < b & b < c & c < d" OR
060: * "a < b < d & b < c"
061: * TODO: make '' be a single quote.
062: * @see PatternEntry
063: * @version 1.14 01/19/00
064: * @author Mark Davis, Helena Shih
065: */
066:
067: final class MergeCollation {
068:
069: /**
070: * Creates from a pattern
071: * @exception ParseException If the input pattern is incorrect.
072: */
073: public MergeCollation(String pattern) throws ParseException {
074: for (int i = 0; i < statusArray.length; i++)
075: statusArray[i] = 0;
076: setPattern(pattern);
077: }
078:
079: /**
080: * recovers current pattern
081: */
082: public String getPattern() {
083: return getPattern(true);
084: }
085:
086: /**
087: * recovers current pattern.
088: * @param withWhiteSpace puts spacing around the entries, and \n
089: * before & and <
090: */
091: public String getPattern(boolean withWhiteSpace) {
092: StringBuffer result = new StringBuffer();
093: PatternEntry tmp = null;
094: ArrayList extList = null;
095: int i;
096: for (i = 0; i < patterns.size(); ++i) {
097: PatternEntry entry = (PatternEntry) patterns.get(i);
098: if (entry.extension.length() != 0) {
099: if (extList == null)
100: extList = new ArrayList();
101: extList.add(entry);
102: } else {
103: if (extList != null) {
104: PatternEntry last = findLastWithNoExtension(i - 1);
105: for (int j = extList.size() - 1; j >= 0; j--) {
106: tmp = (PatternEntry) (extList.get(j));
107: tmp.addToBuffer(result, false, withWhiteSpace,
108: last);
109: }
110: extList = null;
111: }
112: entry.addToBuffer(result, false, withWhiteSpace, null);
113: }
114: }
115: if (extList != null) {
116: PatternEntry last = findLastWithNoExtension(i - 1);
117: for (int j = extList.size() - 1; j >= 0; j--) {
118: tmp = (PatternEntry) (extList.get(j));
119: tmp.addToBuffer(result, false, withWhiteSpace, last);
120: }
121: extList = null;
122: }
123: return result.toString();
124: }
125:
126: private final PatternEntry findLastWithNoExtension(int i) {
127: for (--i; i >= 0; --i) {
128: PatternEntry entry = (PatternEntry) patterns.get(i);
129: if (entry.extension.length() == 0) {
130: return entry;
131: }
132: }
133: return null;
134: }
135:
136: /**
137: * emits the pattern for collation builder.
138: * @return emits the string in the format understable to the collation
139: * builder.
140: */
141: public String emitPattern() {
142: return emitPattern(true);
143: }
144:
145: /**
146: * emits the pattern for collation builder.
147: * @param withWhiteSpace puts spacing around the entries, and \n
148: * before & and <
149: * @return emits the string in the format understable to the collation
150: * builder.
151: */
152: public String emitPattern(boolean withWhiteSpace) {
153: StringBuffer result = new StringBuffer();
154: for (int i = 0; i < patterns.size(); ++i) {
155: PatternEntry entry = (PatternEntry) patterns.get(i);
156: if (entry != null) {
157: entry.addToBuffer(result, true, withWhiteSpace, null);
158: }
159: }
160: return result.toString();
161: }
162:
163: /**
164: * sets the pattern.
165: */
166: public void setPattern(String pattern) throws ParseException {
167: patterns.clear();
168: addPattern(pattern);
169: }
170:
171: /**
172: * adds a pattern to the current one.
173: * @param pattern the new pattern to be added
174: */
175: public void addPattern(String pattern) throws ParseException {
176: if (pattern == null)
177: return;
178:
179: PatternEntry.Parser parser = new PatternEntry.Parser(pattern);
180:
181: PatternEntry entry = parser.next();
182: while (entry != null) {
183: fixEntry(entry);
184: entry = parser.next();
185: }
186: }
187:
188: /**
189: * gets count of separate entries
190: * @return the size of pattern entries
191: */
192: public int getCount() {
193: return patterns.size();
194: }
195:
196: /**
197: * gets count of separate entries
198: * @param index the offset of the desired pattern entry
199: * @return the requested pattern entry
200: */
201: public PatternEntry getItemAt(int index) {
202: return (PatternEntry) patterns.get(index);
203: }
204:
205: //============================================================
206: // privates
207: //============================================================
208: ArrayList patterns = new ArrayList(); // a list of PatternEntries
209:
210: private transient PatternEntry saveEntry = null;
211: private transient PatternEntry lastEntry = null;
212:
213: // This is really used as a local variable inside fixEntry, but we cache
214: // it here to avoid newing it up every time the method is called.
215: private transient StringBuffer excess = new StringBuffer();
216:
217: //
218: // When building a MergeCollation, we need to do lots of searches to see
219: // whether a given entry is already in the table. Since we're using an
220: // array, this would make the algorithm O(N*N). To speed things up, we
221: // use this bit array to remember whether the array contains any entries
222: // starting with each Unicode character. If not, we can avoid the search.
223: // Using BitSet would make this easier, but it's significantly slower.
224: //
225: private transient byte[] statusArray = new byte[8192];
226: private final byte BITARRAYMASK = (byte) 0x1;
227: private final int BYTEPOWER = 3;
228: private final int BYTEMASK = (1 << BYTEPOWER) - 1;
229:
230: /*
231: If the strength is RESET, then just change the lastEntry to
232: be the current. (If the current is not in patterns, signal an error).
233: If not, then remove the current entry, and add it after lastEntry
234: (which is usually at the end).
235: */
236: private final void fixEntry(PatternEntry newEntry)
237: throws ParseException {
238: // check to see whether the new entry has the same characters as the previous
239: // entry did (this can happen when a pattern declaring a difference between two
240: // strings that are canonically equivalent is normalized). If so, and the strength
241: // is anything other than IDENTICAL or RESET, throw an exception (you can't
242: // declare a string to be unequal to itself). --rtg 5/24/99
243: if (lastEntry != null && newEntry.chars.equals(lastEntry.chars)
244: && newEntry.extension.equals(lastEntry.extension)) {
245: if (newEntry.strength != Collator.IDENTICAL
246: && newEntry.strength != PatternEntry.RESET) {
247: throw new ParseException(
248: "The entries "
249: + lastEntry
250: + " and "
251: + newEntry
252: + " are adjacent in the rules, but have conflicting "
253: + "strengths: A character can't be unequal to itself.",
254: -1);
255: } else {
256: // otherwise, just skip this entry and behave as though you never saw it
257: return;
258: }
259: }
260:
261: boolean changeLastEntry = true;
262: if (newEntry.strength != PatternEntry.RESET) {
263: int oldIndex = -1;
264:
265: if ((newEntry.chars.length() == 1)) {
266:
267: char c = newEntry.chars.charAt(0);
268: int statusIndex = c >> BYTEPOWER;
269: byte bitClump = statusArray[statusIndex];
270: byte setBit = (byte) (BITARRAYMASK << (c & BYTEMASK));
271:
272: if (bitClump != 0 && (bitClump & setBit) != 0) {
273: oldIndex = patterns.lastIndexOf(newEntry);
274: } else {
275: // We're going to add an element that starts with this
276: // character, so go ahead and set its bit.
277: statusArray[statusIndex] = (byte) (bitClump | setBit);
278: }
279: } else {
280: oldIndex = patterns.lastIndexOf(newEntry);
281: }
282: if (oldIndex != -1) {
283: patterns.remove(oldIndex);
284: }
285:
286: excess.setLength(0);
287: int lastIndex = findLastEntry(lastEntry, excess);
288:
289: if (excess.length() != 0) {
290: newEntry.extension = excess + newEntry.extension;
291: if (lastIndex != patterns.size()) {
292: lastEntry = saveEntry;
293: changeLastEntry = false;
294: }
295: }
296: if (lastIndex == patterns.size()) {
297: patterns.add(newEntry);
298: saveEntry = newEntry;
299: } else {
300: patterns.add(lastIndex, newEntry);
301: }
302: }
303: if (changeLastEntry) {
304: lastEntry = newEntry;
305: }
306: }
307:
308: private final int findLastEntry(PatternEntry entry,
309: StringBuffer excessChars) throws ParseException {
310: if (entry == null)
311: return 0;
312:
313: if (entry.strength != PatternEntry.RESET) {
314: // Search backwards for string that contains this one;
315: // most likely entry is last one
316:
317: int oldIndex = -1;
318: if ((entry.chars.length() == 1)) {
319: int index = entry.chars.charAt(0) >> BYTEPOWER;
320: if ((statusArray[index] & (BITARRAYMASK << (entry.chars
321: .charAt(0) & BYTEMASK))) != 0) {
322: oldIndex = patterns.lastIndexOf(entry);
323: }
324: } else {
325: oldIndex = patterns.lastIndexOf(entry);
326: }
327: if ((oldIndex == -1))
328: throw new ParseException("couldn't find last entry: "
329: + entry, oldIndex);
330: return oldIndex + 1;
331: } else {
332: int i;
333: for (i = patterns.size() - 1; i >= 0; --i) {
334: PatternEntry e = (PatternEntry) patterns.get(i);
335: if (e.chars.regionMatches(0, entry.chars, 0, e.chars
336: .length())) {
337: excessChars.append(entry.chars.substring(e.chars
338: .length(), entry.chars.length()));
339: break;
340: }
341: }
342: if (i == -1)
343: throw new ParseException("couldn't find: " + entry, i);
344: return i + 1;
345: }
346: }
347: }
|