001: /*
002: * Copyright 2000-2003 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: /*
027: * (C) Copyright IBM Corp. 1999-2000 - All Rights Reserved
028: *
029: * The original version of this source code and documentation is
030: * copyrighted and owned by IBM. These materials are provided
031: * under terms of a License Agreement between IBM and Sun.
032: * This technology is protected by multiple US and International
033: * patents. This notice and attribution to IBM may not be removed.
034: */
035:
036: package sun.font;
037:
038: import java.text.Bidi;
039:
040: public final class BidiUtils {
041:
042: /**
043: * Return the level of each character into the levels array starting at start.
044: * This is a convenience method for clients who prefer to use an explicit levels
045: * array instead of iterating over the runs.
046: *
047: * @param levels the array to receive the character levels
048: * @param start the starting offset into the the array
049: * @throws IndexOutOfBoundsException if <code>start</code> is less than 0 or
050: * <code>start + getLength()</code> is greater than <code>levels.length</code>.
051: */
052: public static void getLevels(Bidi bidi, byte[] levels, int start) {
053: int limit = start + bidi.getLength();
054:
055: if (start < 0 || limit > levels.length) {
056: throw new IndexOutOfBoundsException("levels.length = "
057: + levels.length + " start: " + start + " limit: "
058: + limit);
059: }
060:
061: int runCount = bidi.getRunCount();
062: int p = start;
063: for (int i = 0; i < runCount; ++i) {
064: int rlimit = start + bidi.getRunLimit(i);
065: byte rlevel = (byte) bidi.getRunLevel(i);
066:
067: while (p < rlimit) {
068: levels[p++] = rlevel;
069: }
070: }
071: }
072:
073: /**
074: * Return an array containing the resolved bidi level of each character, in logical order.
075: * @return an array containing the level of each character, in logical order.
076: */
077: public static byte[] getLevels(Bidi bidi) {
078: byte[] levels = new byte[bidi.getLength()];
079: getLevels(bidi, levels, 0);
080: return levels;
081: }
082:
083: static final char NUMLEVELS = 62;
084:
085: /**
086: * Given level data, compute a a visual to logical mapping.
087: * The leftmost (or topmost) character is at visual index zero. The
088: * logical index of the character is derived from the visual index
089: * by the expression <code>li = map[vi];</code>.
090: * @param levels the levels array
091: * @return the mapping array from visual to logical
092: */
093: public static int[] createVisualToLogicalMap(byte[] levels) {
094: int len = levels.length;
095: int[] mapping = new int[len];
096:
097: byte lowestOddLevel = (byte) (NUMLEVELS + 1);
098: byte highestLevel = 0;
099:
100: // initialize mapping and levels
101:
102: for (int i = 0; i < len; i++) {
103: mapping[i] = i;
104:
105: byte level = levels[i];
106: if (level > highestLevel) {
107: highestLevel = level;
108: }
109:
110: if ((level & 0x01) != 0 && level < lowestOddLevel) {
111: lowestOddLevel = level;
112: }
113: }
114:
115: while (highestLevel >= lowestOddLevel) {
116: int i = 0;
117: for (;;) {
118: while (i < len && levels[i] < highestLevel) {
119: i++;
120: }
121: int begin = i++;
122:
123: if (begin == levels.length) {
124: break; // no more runs at this level
125: }
126:
127: while (i < len && levels[i] >= highestLevel) {
128: i++;
129: }
130: int end = i - 1;
131:
132: while (begin < end) {
133: int temp = mapping[begin];
134: mapping[begin] = mapping[end];
135: mapping[end] = temp;
136: ++begin;
137: --end;
138: }
139: }
140:
141: --highestLevel;
142: }
143:
144: return mapping;
145: }
146:
147: /**
148: * Return the inverse position map. The source array must map one-to-one (each value
149: * is distinct and the values run from zero to the length of the array minus one).
150: * For example, if <code>values[i] = j</code>, then <code>inverse[j] = i</code>.
151: * @param values the source ordering array
152: * @return the inverse array
153: */
154: public static int[] createInverseMap(int[] values) {
155: if (values == null) {
156: return null;
157: }
158:
159: int[] result = new int[values.length];
160: for (int i = 0; i < values.length; i++) {
161: result[values[i]] = i;
162: }
163:
164: return result;
165: }
166:
167: /**
168: * Return an array containing contiguous values from 0 to length
169: * having the same ordering as the source array. If this would be
170: * a canonical ltr ordering, return null. The data in values[] is NOT
171: * required to be a permutation, but elements in values are required
172: * to be distinct.
173: * @param values an array containing the discontiguous values
174: * @return the contiguous values
175: */
176: public static int[] createContiguousOrder(int[] values) {
177: if (values != null) {
178: return computeContiguousOrder(values, 0, values.length);
179: }
180:
181: return null;
182: }
183:
184: /**
185: * Compute a contiguous order for the range start, limit.
186: */
187: private static int[] computeContiguousOrder(int[] values,
188: int start, int limit) {
189:
190: int[] result = new int[limit - start];
191: for (int i = 0; i < result.length; i++) {
192: result[i] = i + start;
193: }
194:
195: // now we'll sort result[], with the following comparison:
196: // result[i] lessthan result[j] iff values[result[i]] < values[result[j]]
197:
198: // selection sort for now; use more elaborate sorts if desired
199: for (int i = 0; i < result.length - 1; i++) {
200: int minIndex = i;
201: int currentValue = values[result[minIndex]];
202: for (int j = i; j < result.length; j++) {
203: if (values[result[j]] < currentValue) {
204: minIndex = j;
205: currentValue = values[result[minIndex]];
206: }
207: }
208: int temp = result[i];
209: result[i] = result[minIndex];
210: result[minIndex] = temp;
211: }
212:
213: // shift result by start:
214: if (start != 0) {
215: for (int i = 0; i < result.length; i++) {
216: result[i] -= start;
217: }
218: }
219:
220: // next, check for canonical order:
221: int k;
222: for (k = 0; k < result.length; k++) {
223: if (result[k] != k) {
224: break;
225: }
226: }
227:
228: if (k == result.length) {
229: return null;
230: }
231:
232: // now return inverse of result:
233: return createInverseMap(result);
234: }
235:
236: /**
237: * Return an array containing the data in the values array from start up to limit,
238: * normalized to fall within the range from 0 up to limit - start.
239: * If this would be a canonical ltr ordering, return null.
240: * NOTE: This method assumes that values[] is a logical to visual map
241: * generated from levels[].
242: * @param values the source mapping
243: * @param levels the levels corresponding to the values
244: * @param start the starting offset in the values and levels arrays
245: * @param limit the limiting offset in the values and levels arrays
246: * @return the normlized map
247: */
248: public static int[] createNormalizedMap(int[] values,
249: byte[] levels, int start, int limit) {
250:
251: if (values != null) {
252: if (start != 0 || limit != values.length) {
253: // levels optimization
254: boolean copyRange, canonical;
255: byte primaryLevel;
256:
257: if (levels == null) {
258: primaryLevel = (byte) 0x0;
259: copyRange = true;
260: canonical = true;
261: } else {
262: if (levels[start] == levels[limit - 1]) {
263: primaryLevel = levels[start];
264: canonical = (primaryLevel & (byte) 0x1) == 0;
265:
266: // scan for levels below primary
267: int i;
268: for (i = start; i < limit; i++) {
269: if (levels[i] < primaryLevel) {
270: break;
271: }
272: if (canonical) {
273: canonical = levels[i] == primaryLevel;
274: }
275: }
276:
277: copyRange = (i == limit);
278: } else {
279: copyRange = false;
280:
281: // these don't matter; but the compiler cares:
282: primaryLevel = (byte) 0x0;
283: canonical = false;
284: }
285: }
286:
287: if (copyRange) {
288: if (canonical) {
289: return null;
290: }
291:
292: int[] result = new int[limit - start];
293: int baseValue;
294:
295: if ((primaryLevel & (byte) 0x1) != 0) {
296: baseValue = values[limit - 1];
297: } else {
298: baseValue = values[start];
299: }
300:
301: if (baseValue == 0) {
302: System.arraycopy(values, start, result, 0,
303: limit - start);
304: } else {
305: for (int j = 0; j < result.length; j++) {
306: result[j] = values[j + start] - baseValue;
307: }
308: }
309:
310: return result;
311: } else {
312: return computeContiguousOrder(values, start, limit);
313: }
314: } else {
315: return values;
316: }
317: }
318:
319: return null;
320: }
321:
322: /**
323: * Reorder the objects in the array into visual order based on their levels.
324: * This is a utility function to use when you have a collection of objects
325: * representing runs of text in logical order, each run containing text
326: * at a single level. The elements in the objects array will be reordered
327: * into visual order assuming each run of text has the level provided
328: * by the corresponding element in the levels array.
329: * @param levels an array representing the bidi level of each object
330: * @param objects the array of objects to be reordered into visual order
331: */
332: public static void reorderVisually(byte[] levels, Object[] objects) {
333: int len = levels.length;
334:
335: byte lowestOddLevel = (byte) (NUMLEVELS + 1);
336: byte highestLevel = 0;
337:
338: // initialize mapping and levels
339:
340: for (int i = 0; i < len; i++) {
341: byte level = levels[i];
342: if (level > highestLevel) {
343: highestLevel = level;
344: }
345:
346: if ((level & 0x01) != 0 && level < lowestOddLevel) {
347: lowestOddLevel = level;
348: }
349: }
350:
351: while (highestLevel >= lowestOddLevel) {
352: int i = 0;
353: for (;;) {
354: while (i < len && levels[i] < highestLevel) {
355: i++;
356: }
357: int begin = i++;
358:
359: if (begin == levels.length) {
360: break; // no more runs at this level
361: }
362:
363: while (i < len && levels[i] >= highestLevel) {
364: i++;
365: }
366: int end = i - 1;
367:
368: while (begin < end) {
369: Object temp = objects[begin];
370: objects[begin] = objects[end];
371: objects[end] = temp;
372: ++begin;
373: --end;
374: }
375: }
376:
377: --highestLevel;
378: }
379: }
380: }
|