1 /* 2 * Copyright (c) 2000, 2003, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 /* 27 * (C) Copyright IBM Corp. 1999-2000 - All Rights Reserved 28 * 29 * The original version of this source code and documentation is 30 * copyrighted and owned by IBM. These materials are provided 31 * under terms of a License Agreement between IBM and Sun. 32 * This technology is protected by multiple US and International 33 * patents. This notice and attribution to IBM may not be removed. 34 */ 35 36 package sun.font; 37 38 import java.text.Bidi; 39 40 public final class BidiUtils { 41 42 43 44 /** 45 * Return the level of each character into the levels array starting at start. 46 * This is a convenience method for clients who prefer to use an explicit levels 47 * array instead of iterating over the runs. 48 * 49 * @param levels the array to receive the character levels 50 * @param start the starting offset into the array 51 * @throws IndexOutOfBoundsException if {@code start} is less than 0 or 52 * {@code start + getLength()} is greater than {@code levels.length}. 53 */ getLevels(Bidi bidi, byte[] levels, int start)54 public static void getLevels(Bidi bidi, byte[] levels, int start) { 55 int limit = start + bidi.getLength(); 56 57 if (start < 0 || limit > levels.length) { 58 throw new IndexOutOfBoundsException("levels.length = " + levels.length + 59 " start: " + start + " limit: " + limit); 60 } 61 62 int runCount = bidi.getRunCount(); 63 int p = start; 64 for (int i = 0; i < runCount; ++i) { 65 int rlimit = start + bidi.getRunLimit(i); 66 byte rlevel = (byte)bidi.getRunLevel(i); 67 68 while (p < rlimit) { 69 levels[p++] = rlevel; 70 } 71 } 72 } 73 74 /** 75 * Return an array containing the resolved bidi level of each character, in logical order. 76 * @return an array containing the level of each character, in logical order. 77 */ getLevels(Bidi bidi)78 public static byte[] getLevels(Bidi bidi) { 79 byte[] levels = new byte[bidi.getLength()]; 80 getLevels(bidi, levels, 0); 81 return levels; 82 } 83 84 static final char NUMLEVELS = 62; 85 86 /** 87 * Given level data, compute a a visual to logical mapping. 88 * The leftmost (or topmost) character is at visual index zero. The 89 * logical index of the character is derived from the visual index 90 * by the expression {@code li = map[vi];}. 91 * @param levels the levels array 92 * @return the mapping array from visual to logical 93 */ createVisualToLogicalMap(byte[] levels)94 public static int[] createVisualToLogicalMap(byte[] levels) { 95 int len = levels.length; 96 int[] mapping = new int[len]; 97 98 byte lowestOddLevel = (byte)(NUMLEVELS + 1); 99 byte highestLevel = 0; 100 101 // initialize mapping and levels 102 103 for (int i = 0; i < len; i++) { 104 mapping[i] = i; 105 106 byte level = levels[i]; 107 if (level > highestLevel) { 108 highestLevel = level; 109 } 110 111 if ((level & 0x01) != 0 && level < lowestOddLevel) { 112 lowestOddLevel = level; 113 } 114 } 115 116 while (highestLevel >= lowestOddLevel) { 117 int i = 0; 118 for (;;) { 119 while (i < len && levels[i] < highestLevel) { 120 i++; 121 } 122 int begin = i++; 123 124 if (begin == levels.length) { 125 break; // no more runs at this level 126 } 127 128 while (i < len && levels[i] >= highestLevel) { 129 i++; 130 } 131 int end = i - 1; 132 133 while (begin < end) { 134 int temp = mapping[begin]; 135 mapping[begin] = mapping[end]; 136 mapping[end] = temp; 137 ++begin; 138 --end; 139 } 140 } 141 142 --highestLevel; 143 } 144 145 return mapping; 146 } 147 148 /** 149 * Return the inverse position map. The source array must map one-to-one (each value 150 * is distinct and the values run from zero to the length of the array minus one). 151 * For example, if {@code values[i] = j}, then {@code inverse[j] = i}. 152 * @param values the source ordering array 153 * @return the inverse array 154 */ createInverseMap(int[] values)155 public static int[] createInverseMap(int[] values) { 156 if (values == null) { 157 return null; 158 } 159 160 int[] result = new int[values.length]; 161 for (int i = 0; i < values.length; i++) { 162 result[values[i]] = i; 163 } 164 165 return result; 166 } 167 168 169 /** 170 * Return an array containing contiguous values from 0 to length 171 * having the same ordering as the source array. If this would be 172 * a canonical ltr ordering, return null. The data in values[] is NOT 173 * required to be a permutation, but elements in values are required 174 * to be distinct. 175 * @param values an array containing the discontiguous values 176 * @return the contiguous values 177 */ createContiguousOrder(int[] values)178 public static int[] createContiguousOrder(int[] values) { 179 if (values != null) { 180 return computeContiguousOrder(values, 0, values.length); 181 } 182 183 return null; 184 } 185 186 /** 187 * Compute a contiguous order for the range start, limit. 188 */ computeContiguousOrder(int[] values, int start, int limit)189 private static int[] computeContiguousOrder(int[] values, int start, 190 int limit) { 191 192 int[] result = new int[limit-start]; 193 for (int i=0; i < result.length; i++) { 194 result[i] = i + start; 195 } 196 197 // now we'll sort result[], with the following comparison: 198 // result[i] lessthan result[j] iff values[result[i]] < values[result[j]] 199 200 // selection sort for now; use more elaborate sorts if desired 201 for (int i=0; i < result.length-1; i++) { 202 int minIndex = i; 203 int currentValue = values[result[minIndex]]; 204 for (int j=i; j < result.length; j++) { 205 if (values[result[j]] < currentValue) { 206 minIndex = j; 207 currentValue = values[result[minIndex]]; 208 } 209 } 210 int temp = result[i]; 211 result[i] = result[minIndex]; 212 result[minIndex] = temp; 213 } 214 215 // shift result by start: 216 if (start != 0) { 217 for (int i=0; i < result.length; i++) { 218 result[i] -= start; 219 } 220 } 221 222 // next, check for canonical order: 223 int k; 224 for (k=0; k < result.length; k++) { 225 if (result[k] != k) { 226 break; 227 } 228 } 229 230 if (k == result.length) { 231 return null; 232 } 233 234 // now return inverse of result: 235 return createInverseMap(result); 236 } 237 238 /** 239 * Return an array containing the data in the values array from start up to limit, 240 * normalized to fall within the range from 0 up to limit - start. 241 * If this would be a canonical ltr ordering, return null. 242 * NOTE: This method assumes that values[] is a logical to visual map 243 * generated from levels[]. 244 * @param values the source mapping 245 * @param levels the levels corresponding to the values 246 * @param start the starting offset in the values and levels arrays 247 * @param limit the limiting offset in the values and levels arrays 248 * @return the normlized map 249 */ createNormalizedMap(int[] values, byte[] levels, int start, int limit)250 public static int[] createNormalizedMap(int[] values, byte[] levels, 251 int start, int limit) { 252 253 if (values != null) { 254 if (start != 0 || limit != values.length) { 255 // levels optimization 256 boolean copyRange, canonical; 257 byte primaryLevel; 258 259 if (levels == null) { 260 primaryLevel = (byte) 0x0; 261 copyRange = true; 262 canonical = true; 263 } 264 else { 265 if (levels[start] == levels[limit-1]) { 266 primaryLevel = levels[start]; 267 canonical = (primaryLevel & (byte)0x1) == 0; 268 269 // scan for levels below primary 270 int i; 271 for (i=start; i < limit; i++) { 272 if (levels[i] < primaryLevel) { 273 break; 274 } 275 if (canonical) { 276 canonical = levels[i] == primaryLevel; 277 } 278 } 279 280 copyRange = (i == limit); 281 } 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 */ reorderVisually(byte[] levels, Object[] objects)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