/*

 * 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.

     *

     * @param levels the array to receive the character levels

     * @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.

     * @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 <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 <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.

     * @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.

     */

    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[].

     * @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.

     * @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;

        }

    }

}