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</code> is less than 0 or
  52      * <code>start + getLength()</code> is greater than <code>levels.length</code>.
  53      */
  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      */
  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];</code>.
  91      * @param levels the levels array
  92      * @return the mapping array from visual to logical
  93      */
  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</code>, then <code>inverse[j] = i</code>.
 152      * @param values the source ordering array
 153      * @return the inverse array
 154      */
 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      */
 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      */
 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      */
 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      */
 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 }