https://openjdk.java.net/ 
/*
 * Copyright (c) 2000, 2003, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

/*
 * (C) Copyright IBM Corp. 1999-2000 - All Rights Reserved
 *
 * The original version of this source code and documentation is
 * copyrighted and owned by IBM. These materials are provided
 * under terms of a License Agreement between IBM and Sun.
 * This technology is protected by multiple US and International
 * patents. This notice and attribution to IBM may not be removed.
 */

package sun.font;

import java.text.Bidi;

public final class BidiUtils {



    
Return the level of each character into the levels array starting at start.
This is a convenience method for clients who prefer to use an explicit levels
array instead of iterating over the runs.

Params:
  • levels – the array to receive the character levels
  • start – the starting offset into the the array
Throws:
/**
     * Return the level of each character into the levels array starting at start.
     * This is a convenience method for clients who prefer to use an explicit levels
     * array instead of iterating over the runs.
     *
     * @param levels the array to receive the character levels
     * @param start the starting offset into the the array
     * @throws IndexOutOfBoundsException if <code>start</code> is less than 0 or
     * <code>start + getLength()</code> is greater than <code>levels.length</code>.
     */
    public static void getLevels(Bidi bidi, byte[] levels, int start) {
        int limit = start + bidi.getLength();

        if (start < 0 || limit > levels.length) {
            throw new IndexOutOfBoundsException("levels.length = " + levels.length +
                " start: " + start + " limit: " + limit);
        }

        int runCount = bidi.getRunCount();
        int p = start;
        for (int i = 0; i < runCount; ++i) {
            int rlimit = start + bidi.getRunLimit(i);
            byte rlevel = (byte)bidi.getRunLevel(i);

            while (p < rlimit) {
                levels[p++] = rlevel;
            }
        }
    }

    
Return an array containing the resolved bidi level of each character, in logical order.

Returns:an array containing the level of each character, in logical order.
/**
     * Return an array containing the resolved bidi level of each character, in logical order.
     * @return an array containing the level of each character, in logical order.
     */
    public static byte[] getLevels(Bidi bidi) {
        byte[] levels = new byte[bidi.getLength()];
        getLevels(bidi, levels, 0);
        return levels;
    }

    static final char NUMLEVELS = 62;

    
Given level data, compute a a visual to logical mapping.
The leftmost (or topmost) character is at visual index zero.  The
logical index of the character is derived from the visual index
by the expression li = map[vi];.

Params:
  • levels – the levels array
Returns:the mapping array from visual to logical
/**
     * Given level data, compute a a visual to logical mapping.
     * The leftmost (or topmost) character is at visual index zero.  The
     * logical index of the character is derived from the visual index
     * by the expression <code>li = map[vi];</code>.
     * @param levels the levels array
     * @return the mapping array from visual to logical
     */
    public static int[] createVisualToLogicalMap(byte[] levels) {
        int len = levels.length;
        int[] mapping = new int[len];

        byte lowestOddLevel = (byte)(NUMLEVELS + 1);
        byte highestLevel = 0;

        // initialize mapping and levels

        for (int i = 0; i < len; i++) {
            mapping[i] = i;

            byte level = levels[i];
            if (level > highestLevel) {
                highestLevel = level;
            }

            if ((level & 0x01) != 0 && level < lowestOddLevel) {
                lowestOddLevel = level;
            }
        }

        while (highestLevel >= lowestOddLevel) {
            int i = 0;
            for (;;) {
                while (i < len && levels[i] < highestLevel) {
                    i++;
                }
                int begin = i++;

                if (begin == levels.length) {
                    break; // no more runs at this level
                }

                while (i < len && levels[i] >= highestLevel) {
                    i++;
                }
                int end = i - 1;

                while (begin < end) {
                    int temp = mapping[begin];
                    mapping[begin] = mapping[end];
                    mapping[end] = temp;
                    ++begin;
                    --end;
                }
            }

            --highestLevel;
        }

        return mapping;
    }

    
Return the inverse position map.  The source array must map one-to-one (each value
is distinct and the values run from zero to the length of the array minus one).
For example, if values[i] = j, then inverse[j] = i.

Params:
  • values – the source ordering array
Returns:the inverse array
/**
     * Return the inverse position map.  The source array must map one-to-one (each value
     * is distinct and the values run from zero to the length of the array minus one).
     * For example, if <code>values[i] = j</code>, then <code>inverse[j] = i</code>.
     * @param values the source ordering array
     * @return the inverse array
     */
    public static int[] createInverseMap(int[] values) {
        if (values == null) {
            return null;
        }

        int[] result = new int[values.length];
        for (int i = 0; i < values.length; i++) {
            result[values[i]] = i;
        }

        return result;
    }


    
Return an array containing contiguous values from 0 to length
having the same ordering as the source array. If this would be
a canonical ltr ordering, return null.  The data in values[] is NOT
required to be a permutation, but elements in values are required
to be distinct.

Params:
  • values – an array containing the discontiguous values
Returns:the contiguous values
/**
     * Return an array containing contiguous values from 0 to length
     * having the same ordering as the source array. If this would be
     * a canonical ltr ordering, return null.  The data in values[] is NOT
     * required to be a permutation, but elements in values are required
     * to be distinct.
     * @param values an array containing the discontiguous values
     * @return the contiguous values
     */
    public static int[] createContiguousOrder(int[] values) {
        if (values != null) {
            return computeContiguousOrder(values, 0, values.length);
        }

        return null;
    }

    
Compute a contiguous order for the range start, limit.

/**
     * Compute a contiguous order for the range start, limit.
     */
    private static int[] computeContiguousOrder(int[] values, int start,
                                                int limit) {

        int[] result = new int[limit-start];
        for (int i=0; i < result.length; i++) {
            result[i] = i + start;
        }

        // now we'll sort result[], with the following comparison:
        // result[i] lessthan result[j] iff values[result[i]] < values[result[j]]

        // selection sort for now;  use more elaborate sorts if desired
        for (int i=0; i < result.length-1; i++) {
            int minIndex = i;
            int currentValue = values[result[minIndex]];
            for (int j=i; j < result.length; j++) {
                if (values[result[j]] < currentValue) {
                    minIndex = j;
                    currentValue = values[result[minIndex]];
                }
            }
            int temp = result[i];
            result[i] = result[minIndex];
            result[minIndex] = temp;
        }

        // shift result by start:
        if (start != 0) {
            for (int i=0; i < result.length; i++) {
                result[i] -= start;
            }
        }

        // next, check for canonical order:
        int k;
        for (k=0; k < result.length; k++) {
            if (result[k] != k) {
                break;
            }
        }

        if (k == result.length) {
            return null;
        }

        // now return inverse of result:
        return createInverseMap(result);
    }

    
Return an array containing the data in the values array from start up to limit,
normalized to fall within the range from 0 up to limit - start.
If this would be a canonical ltr ordering, return null.
NOTE: This method assumes that values[] is a logical to visual map
generated from levels[].

Params:
  • values – the source mapping
  • levels – the levels corresponding to the values
  • start – the starting offset in the values and levels arrays
  • limit – the limiting offset in the values and levels arrays
Returns:the normlized map
/**
     * Return an array containing the data in the values array from start up to limit,
     * normalized to fall within the range from 0 up to limit - start.
     * If this would be a canonical ltr ordering, return null.
     * NOTE: This method assumes that values[] is a logical to visual map
     * generated from levels[].
     * @param values the source mapping
     * @param levels the levels corresponding to the values
     * @param start the starting offset in the values and levels arrays
     * @param limit the limiting offset in the values and levels arrays
     * @return the normlized map
     */
    public static int[] createNormalizedMap(int[] values, byte[] levels,
                                           int start, int limit) {

        if (values != null) {
            if (start != 0 || limit != values.length) {
                // levels optimization
                boolean copyRange, canonical;
                byte primaryLevel;

                if (levels == null) {
                    primaryLevel = (byte) 0x0;
                    copyRange = true;
                    canonical = true;
                }
                else {
                    if (levels[start] == levels[limit-1]) {
                        primaryLevel = levels[start];
                        canonical = (primaryLevel & (byte)0x1) == 0;

                        // scan for levels below primary
                        int i;
                        for (i=start; i < limit; i++) {
                            if (levels[i] < primaryLevel) {
                                break;
                            }
                            if (canonical) {
                                canonical = levels[i] == primaryLevel;
                            }
                        }

                        copyRange = (i == limit);
                    }
                    else {
                        copyRange = false;

                        // these don't matter;  but the compiler cares:
                        primaryLevel = (byte) 0x0;
                        canonical = false;
                    }
                }

                if (copyRange) {
                    if (canonical) {
                        return null;
                    }

                    int[] result = new int[limit-start];
                    int baseValue;

                    if ((primaryLevel & (byte)0x1) != 0) {
                        baseValue = values[limit-1];
                    } else {
                        baseValue = values[start];
                    }

                    if (baseValue == 0) {
                        System.arraycopy(values, start, result, 0, limit-start);
                    }
                    else {
                        for (int j=0; j < result.length; j++) {
                            result[j] = values[j+start] - baseValue;
                        }
                    }

                    return result;
                }
                else {
                    return computeContiguousOrder(values, start, limit);
                }
            }
            else {
                return values;
            }
        }

        return null;
    }

    
Reorder the objects in the array into visual order based on their levels.
This is a utility function to use when you have a collection of objects
representing runs of text in logical order, each run containing text
at a single level.  The elements in the objects array will be reordered
into visual order assuming each run of text has the level provided
by the corresponding element in the levels array.

Params:
  • levels – an array representing the bidi level of each object
  • objects – the array of objects to be reordered into visual order
/**
     * Reorder the objects in the array into visual order based on their levels.
     * This is a utility function to use when you have a collection of objects
     * representing runs of text in logical order, each run containing text
     * at a single level.  The elements in the objects array will be reordered
     * into visual order assuming each run of text has the level provided
     * by the corresponding element in the levels array.
     * @param levels an array representing the bidi level of each object
     * @param objects the array of objects to be reordered into visual order
     */
    public static void reorderVisually(byte[] levels, Object[] objects) {
        int len = levels.length;

        byte lowestOddLevel = (byte)(NUMLEVELS + 1);
        byte highestLevel = 0;

        // initialize mapping and levels

        for (int i = 0; i < len; i++) {
            byte level = levels[i];
            if (level > highestLevel) {
                highestLevel = level;
            }

            if ((level & 0x01) != 0 && level < lowestOddLevel) {
                lowestOddLevel = level;
            }
        }

        while (highestLevel >= lowestOddLevel) {
            int i = 0;
            for (;;) {
                while (i < len && levels[i] < highestLevel) {
                    i++;
                }
                int begin = i++;

                if (begin == levels.length) {
                    break; // no more runs at this level
                }

                while (i < len && levels[i] >= highestLevel) {
                    i++;
                }
                int end = i - 1;

                while (begin < end) {
                    Object temp = objects[begin];
                    objects[begin] = objects[end];
                    objects[end] = temp;
                    ++begin;
                    --end;
                }
            }

            --highestLevel;
        }
    }
}