BidiUtils.java revision 11099:678faa7d1a6a
175584Sru/* 275584Sru * Copyright (c) 2000, 2003, Oracle and/or its affiliates. All rights reserved. 375584Sru * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 475584Sru * 575584Sru * This code is free software; you can redistribute it and/or modify it 6114402Sru * under the terms of the GNU General Public License version 2 only, as 7114402Sru * published by the Free Software Foundation. Oracle designates this 8114402Sru * particular file as subject to the "Classpath" exception as provided 9114402Sru * by Oracle in the LICENSE file that accompanied this code. 10114402Sru * 11114402Sru * This code is distributed in the hope that it will be useful, but WITHOUT 12114402Sru * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13114402Sru * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14114402Sru * version 2 for more details (a copy is included in the LICENSE file that 15114402Sru * accompanied this code). 16114402Sru * 17114402Sru * You should have received a copy of the GNU General Public License version 1875584Sru * 2 along with this work; if not, write to the Free Software Foundation, 19114402Sru * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2075584Sru * 21114402Sru * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2275584Sru * or visit www.oracle.com if you need additional information or have any 23114402Sru * questions. 24114402Sru */ 25114402Sru 2675584Sru/* 27114402Sru * (C) Copyright IBM Corp. 1999-2000 - All Rights Reserved 28114402Sru * 29114402Sru * The original version of this source code and documentation is 30114402Sru * copyrighted and owned by IBM. These materials are provided 31114402Sru * under terms of a License Agreement between IBM and Sun. 32114402Sru * This technology is protected by multiple US and International 3375584Sru * patents. This notice and attribution to IBM may not be removed. 34114402Sru */ 35114402Sru 3675584Srupackage sun.font; 37114402Sru 38114402Sruimport java.text.Bidi; 39114402Sru 40114402Srupublic final class BidiUtils { 41114402Sru 42114402Sru 43114402Sru 44114402Sru /** 45114402Sru * Return the level of each character into the levels array starting at start. 46114402Sru * This is a convenience method for clients who prefer to use an explicit levels 47114402Sru * array instead of iterating over the runs. 48114402Sru * 49114402Sru * @param levels the array to receive the character levels 50114402Sru * @param start the starting offset into the array 51114402Sru * @throws IndexOutOfBoundsException if <code>start</code> is less than 0 or 52114402Sru * <code>start + getLength()</code> is greater than <code>levels.length</code>. 53114402Sru */ 5475584Sru public static void getLevels(Bidi bidi, byte[] levels, int start) { 55114402Sru int limit = start + bidi.getLength(); 56114402Sru 57114402Sru if (start < 0 || limit > levels.length) { 58114402Sru throw new IndexOutOfBoundsException("levels.length = " + levels.length + 59114402Sru " start: " + start + " limit: " + limit); 60114402Sru } 61114402Sru 62114402Sru int runCount = bidi.getRunCount(); 63114402Sru int p = start; 64114402Sru for (int i = 0; i < runCount; ++i) { 65114402Sru int rlimit = start + bidi.getRunLimit(i); 66114402Sru byte rlevel = (byte)bidi.getRunLevel(i); 67114402Sru 68114402Sru while (p < rlimit) { 69114402Sru levels[p++] = rlevel; 70114402Sru } 71114402Sru } 72114402Sru } 73114402Sru 74114402Sru /** 75114402Sru * Return an array containing the resolved bidi level of each character, in logical order. 76114402Sru * @return an array containing the level of each character, in logical order. 77114402Sru */ 78114402Sru public static byte[] getLevels(Bidi bidi) { 79114402Sru byte[] levels = new byte[bidi.getLength()]; 80114402Sru getLevels(bidi, levels, 0); 81114402Sru return levels; 8275584Sru } 83114402Sru 8475584Sru static final char NUMLEVELS = 62; 85114402Sru 8675584Sru /** 87114402Sru * Given level data, compute a a visual to logical mapping. 8875584Sru * The leftmost (or topmost) character is at visual index zero. The 89114402Sru * logical index of the character is derived from the visual index 90114402Sru * by the expression <code>li = map[vi];</code>. 9175584Sru * @param levels the levels array 92114402Sru * @return the mapping array from visual to logical 93114402Sru */ 94114402Sru public static int[] createVisualToLogicalMap(byte[] levels) { 95114402Sru int len = levels.length; 96114402Sru int[] mapping = new int[len]; 97114402Sru 98114402Sru byte lowestOddLevel = (byte)(NUMLEVELS + 1); 99114402Sru byte highestLevel = 0; 100114402Sru 101114402Sru // initialize mapping and levels 102114402Sru 103114402Sru for (int i = 0; i < len; i++) { 104114402Sru mapping[i] = i; 105114402Sru 106114402Sru byte level = levels[i]; 107114402Sru if (level > highestLevel) { 108114402Sru highestLevel = level; 109114402Sru } 110114402Sru 111114402Sru if ((level & 0x01) != 0 && level < lowestOddLevel) { 112114402Sru lowestOddLevel = level; 113114402Sru } 114114402Sru } 115114402Sru 116114402Sru while (highestLevel >= lowestOddLevel) { 117114402Sru int i = 0; 118114402Sru for (;;) { 11975584Sru while (i < len && levels[i] < highestLevel) { 120114402Sru i++; 12175584Sru } 122114402Sru int begin = i++; 12375584Sru 124114402Sru if (begin == levels.length) { 12575584Sru break; // no more runs at this level 126114402Sru } 127114402Sru 128114402Sru while (i < len && levels[i] >= highestLevel) { 129114402Sru i++; 130114402Sru } 131114402Sru int end = i - 1; 132114402Sru 133114402Sru while (begin < end) { 134114402Sru int temp = mapping[begin]; 135114402Sru mapping[begin] = mapping[end]; 136114402Sru mapping[end] = temp; 137114402Sru ++begin; 138114402Sru --end; 139114402Sru } 140114402Sru } 141114402Sru 142114402Sru --highestLevel; 143114402Sru } 144114402Sru 145114402Sru return mapping; 146114402Sru } 147114402Sru 148114402Sru /** 149114402Sru * Return the inverse position map. The source array must map one-to-one (each value 150114402Sru * is distinct and the values run from zero to the length of the array minus one). 151114402Sru * For example, if <code>values[i] = j</code>, then <code>inverse[j] = i</code>. 152114402Sru * @param values the source ordering array 153114402Sru * @return the inverse array 154114402Sru */ 155114402Sru public static int[] createInverseMap(int[] values) { 156114402Sru if (values == null) { 157114402Sru return null; 158114402Sru } 159114402Sru 160114402Sru int[] result = new int[values.length]; 161114402Sru for (int i = 0; i < values.length; i++) { 162114402Sru result[values[i]] = i; 163114402Sru } 164114402Sru 165114402Sru return result; 166114402Sru } 167114402Sru 168114402Sru 169114402Sru /** 170114402Sru * Return an array containing contiguous values from 0 to length 171114402Sru * having the same ordering as the source array. If this would be 172114402Sru * a canonical ltr ordering, return null. The data in values[] is NOT 173114402Sru * required to be a permutation, but elements in values are required 174114402Sru * to be distinct. 175114402Sru * @param values an array containing the discontiguous values 176114402Sru * @return the contiguous values 177114402Sru */ 178114402Sru public static int[] createContiguousOrder(int[] values) { 179114402Sru if (values != null) { 180114402Sru return computeContiguousOrder(values, 0, values.length); 181114402Sru } 182114402Sru 183114402Sru return null; 184114402Sru } 185114402Sru 186114402Sru /** 187114402Sru * Compute a contiguous order for the range start, limit. 188114402Sru */ 189114402Sru private static int[] computeContiguousOrder(int[] values, int start, 190114402Sru int limit) { 191114402Sru 192114402Sru int[] result = new int[limit-start]; 193114402Sru for (int i=0; i < result.length; i++) { 194114402Sru result[i] = i + start; 195114402Sru } 196114402Sru 197114402Sru // now we'll sort result[], with the following comparison: 198114402Sru // result[i] lessthan result[j] iff values[result[i]] < values[result[j]] 199114402Sru 200114402Sru // selection sort for now; use more elaborate sorts if desired 201114402Sru for (int i=0; i < result.length-1; i++) { 202114402Sru int minIndex = i; 203114402Sru int currentValue = values[result[minIndex]]; 204114402Sru for (int j=i; j < result.length; j++) { 205114402Sru if (values[result[j]] < currentValue) { 206114402Sru minIndex = j; 207114402Sru currentValue = values[result[minIndex]]; 208114402Sru } 209114402Sru } 210114402Sru int temp = result[i]; 211114402Sru result[i] = result[minIndex]; 212114402Sru result[minIndex] = temp; 213114402Sru } 214114402Sru 215114402Sru // shift result by start: 216114402Sru if (start != 0) { 217114402Sru for (int i=0; i < result.length; i++) { 218114402Sru result[i] -= start; 219114402Sru } 220114402Sru } 221114402Sru 222114402Sru // next, check for canonical order: 223114402Sru int k; 224114402Sru for (k=0; k < result.length; k++) { 225114402Sru if (result[k] != k) { 226114402Sru break; 227114402Sru } 228114402Sru } 229114402Sru 230114402Sru if (k == result.length) { 231114402Sru return null; 232114402Sru } 233114402Sru 234114402Sru // now return inverse of result: 235114402Sru return createInverseMap(result); 236114402Sru } 237114402Sru 238114402Sru /** 239114402Sru * Return an array containing the data in the values array from start up to limit, 240114402Sru * normalized to fall within the range from 0 up to limit - start. 241114402Sru * If this would be a canonical ltr ordering, return null. 242114402Sru * NOTE: This method assumes that values[] is a logical to visual map 243114402Sru * generated from levels[]. 244114402Sru * @param values the source mapping 245114402Sru * @param levels the levels corresponding to the values 246114402Sru * @param start the starting offset in the values and levels arrays 247114402Sru * @param limit the limiting offset in the values and levels arrays 248114402Sru * @return the normlized map 249114402Sru */ 250114402Sru public static int[] createNormalizedMap(int[] values, byte[] levels, 251114402Sru int start, int limit) { 252114402Sru 253114402Sru if (values != null) { 254114402Sru if (start != 0 || limit != values.length) { 255114402Sru // levels optimization 256114402Sru boolean copyRange, canonical; 257114402Sru byte primaryLevel; 258114402Sru 259114402Sru if (levels == null) { 260114402Sru primaryLevel = (byte) 0x0; 261114402Sru copyRange = true; 262114402Sru canonical = true; 263114402Sru } 264114402Sru else { 265114402Sru if (levels[start] == levels[limit-1]) { 266114402Sru primaryLevel = levels[start]; 267114402Sru canonical = (primaryLevel & (byte)0x1) == 0; 268114402Sru 269114402Sru // scan for levels below primary 270114402Sru int i; 271114402Sru for (i=start; i < limit; i++) { 272114402Sru if (levels[i] < primaryLevel) { 273114402Sru break; 274114402Sru } 275114402Sru if (canonical) { 276114402Sru canonical = levels[i] == primaryLevel; 277114402Sru } 278114402Sru } 279114402Sru 280114402Sru copyRange = (i == limit); 281114402Sru } 282 else { 283 copyRange = false; 284 285 // these don't matter; but the compiler cares: 286 primaryLevel = (byte) 0x0; 287 canonical = false; 288 } 289 } 290 291 if (copyRange) { 292 if (canonical) { 293 return null; 294 } 295 296 int[] result = new int[limit-start]; 297 int baseValue; 298 299 if ((primaryLevel & (byte)0x1) != 0) { 300 baseValue = values[limit-1]; 301 } else { 302 baseValue = values[start]; 303 } 304 305 if (baseValue == 0) { 306 System.arraycopy(values, start, result, 0, limit-start); 307 } 308 else { 309 for (int j=0; j < result.length; j++) { 310 result[j] = values[j+start] - baseValue; 311 } 312 } 313 314 return result; 315 } 316 else { 317 return computeContiguousOrder(values, start, limit); 318 } 319 } 320 else { 321 return values; 322 } 323 } 324 325 return null; 326 } 327 328 /** 329 * Reorder the objects in the array into visual order based on their levels. 330 * This is a utility function to use when you have a collection of objects 331 * representing runs of text in logical order, each run containing text 332 * at a single level. The elements in the objects array will be reordered 333 * into visual order assuming each run of text has the level provided 334 * by the corresponding element in the levels array. 335 * @param levels an array representing the bidi level of each object 336 * @param objects the array of objects to be reordered into visual order 337 */ 338 public static void reorderVisually(byte[] levels, Object[] objects) { 339 int len = levels.length; 340 341 byte lowestOddLevel = (byte)(NUMLEVELS + 1); 342 byte highestLevel = 0; 343 344 // initialize mapping and levels 345 346 for (int i = 0; i < len; i++) { 347 byte level = levels[i]; 348 if (level > highestLevel) { 349 highestLevel = level; 350 } 351 352 if ((level & 0x01) != 0 && level < lowestOddLevel) { 353 lowestOddLevel = level; 354 } 355 } 356 357 while (highestLevel >= lowestOddLevel) { 358 int i = 0; 359 for (;;) { 360 while (i < len && levels[i] < highestLevel) { 361 i++; 362 } 363 int begin = i++; 364 365 if (begin == levels.length) { 366 break; // no more runs at this level 367 } 368 369 while (i < len && levels[i] >= highestLevel) { 370 i++; 371 } 372 int end = i - 1; 373 374 while (begin < end) { 375 Object temp = objects[begin]; 376 objects[begin] = objects[end]; 377 objects[end] = temp; 378 ++begin; 379 --end; 380 } 381 } 382 383 --highestLevel; 384 } 385 } 386} 387