/*

 * Copyright (c) 2009, 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. and others, 1996-2009 - 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    *

 * to removed.                                                                 *

 *******************************************************************************

 */

/* FOOD FOR THOUGHT: currently the reordering modes are a mixture of

 * algorithm for direct BiDi, algorithm for inverse Bidi and the bizarre

 * concept of RUNS_ONLY which is a double operation.

 * It could be advantageous to divide this into 3 concepts:

 * a) Operation: direct / inverse / RUNS_ONLY

 * b) Direct algorithm: default / NUMBERS_SPECIAL / GROUP_NUMBERS_WITH_L

 * c) Inverse algorithm: default / INVERSE_LIKE_DIRECT / NUMBERS_SPECIAL

 * This would allow combinations not possible today like RUNS_ONLY with

 * NUMBERS_SPECIAL.

 * Also allow to set INSERT_MARKS for the direct step of RUNS_ONLY and

 * REMOVE_CONTROLS for the inverse step.

 * Not all combinations would be supported, and probably not all do make sense.

 * This would need to document which ones are supported and what are the

 * fallbacks for unsupported combinations.

 */

package sun.text.bidi;

import java.io.IOException;

import java.lang.reflect.Array;

import java.lang.reflect.Field;

import java.lang.reflect.Method;

import java.lang.reflect.InvocationTargetException;

import java.text.AttributedCharacterIterator;

import java.text.Bidi;

import java.util.Arrays;

import java.util.MissingResourceException;

import sun.text.normalizer.UBiDiProps;

import sun.text.normalizer.UCharacter;

import sun.text.normalizer.UTF16;

/**

 *

 * <h2>Bidi algorithm for ICU</h2>

 *

 * This is an implementation of the Unicode Bidirectional algorithm. The

 * algorithm is defined in the <a

 * href="http://www.unicode.org/unicode/reports/tr9/">Unicode Standard Annex #9</a>,

 * version 13, also described in The Unicode Standard, Version 4.0 .

 * <p>

 *

 * Note: Libraries that perform a bidirectional algorithm and reorder strings

 * accordingly are sometimes called "Storage Layout Engines". ICU's Bidi and

 * shaping (ArabicShaping) classes can be used at the core of such "Storage

 * Layout Engines".

 *

 * <h3>General remarks about the API:</h3>

 *

 * The "limit" of a sequence of characters is the position just after

 * their last character, i.e., one more than that position.

 * <p>

 *

 * Some of the API methods provide access to "runs". Such a

 * "run" is defined as a sequence of characters that are at the same

 * embedding level after performing the Bidi algorithm.

 * <p>

 *

 * <h3>Basic concept: paragraph</h3>

 * A piece of text can be divided into several paragraphs by characters

 * with the Bidi class <code>Block Separator</code>. For handling of

 * paragraphs, see:

 * <ul>

 * <li>{@link #countParagraphs}

 * <li>{@link #getParaLevel}

 * <li>{@link #getParagraph}

 * <li>{@link #getParagraphByIndex}

 * </ul>

 *

 * <h3>Basic concept: text direction</h3>

 * The direction of a piece of text may be:

 * <ul>

 * <li>{@link #LTR}

 * <li>{@link #RTL}

 * <li>{@link #MIXED}

 * </ul>

 *

 * <h3>Basic concept: levels</h3>

 *

 * Levels in this API represent embedding levels according to the Unicode

 * Bidirectional Algorithm.

 * Their low-order bit (even/odd value) indicates the visual direction.<p>

 *

 * Levels can be abstract values when used for the

 * <code>paraLevel</code> and <code>embeddingLevels</code>

 * arguments of <code>setPara()</code>; there:

 * <ul>

 * <li>the high-order bit of an <code>embeddingLevels[]</code>

 * value indicates whether the using application is

 * specifying the level of a character to <i>override</i> whatever the

 * Bidi implementation would resolve it to.</li>

 * <li><code>paraLevel</code> can be set to the

 * pseudo-level values <code>LEVEL_DEFAULT_LTR</code>

 * and <code>LEVEL_DEFAULT_RTL</code>.</li>

 * </ul>

 *

 * <p>The related constants are not real, valid level values.

 * <code>DEFAULT_XXX</code> can be used to specify

 * a default for the paragraph level for

 * when the <code>setPara()</code> method

 * shall determine it but there is no

 * strongly typed character in the input.<p>

 *

 * Note that the value for <code>LEVEL_DEFAULT_LTR</code> is even

 * and the one for <code>LEVEL_DEFAULT_RTL</code> is odd,

 * just like with normal LTR and RTL level values -

 * these special values are designed that way. Also, the implementation

 * assumes that MAX_EXPLICIT_LEVEL is odd.

 *

 * <ul><b>See Also:</b>

 * <li>{@link #LEVEL_DEFAULT_LTR}

 * <li>{@link #LEVEL_DEFAULT_RTL}

 * <li>{@link #LEVEL_OVERRIDE}

 * <li>{@link #MAX_EXPLICIT_LEVEL}

 * <li>{@link #setPara}

 * </ul>

 *

 * <h3>Basic concept: Reordering Mode</h3>

 * Reordering mode values indicate which variant of the Bidi algorithm to

 * use.

 *

 * <ul><b>See Also:</b>

 * <li>{@link #setReorderingMode}

 * <li>{@link #REORDER_DEFAULT}

 * <li>{@link #REORDER_NUMBERS_SPECIAL}

 * <li>{@link #REORDER_GROUP_NUMBERS_WITH_R}

 * <li>{@link #REORDER_RUNS_ONLY}

 * <li>{@link #REORDER_INVERSE_NUMBERS_AS_L}

 * <li>{@link #REORDER_INVERSE_LIKE_DIRECT}

 * <li>{@link #REORDER_INVERSE_FOR_NUMBERS_SPECIAL}

 * </ul>

 *

 * <h3>Basic concept: Reordering Options</h3>

 * Reordering options can be applied during Bidi text transformations.

 * <ul><b>See Also:</b>

 * <li>{@link #setReorderingOptions}

 * <li>{@link #OPTION_DEFAULT}

 * <li>{@link #OPTION_INSERT_MARKS}

 * <li>{@link #OPTION_REMOVE_CONTROLS}

 * <li>{@link #OPTION_STREAMING}

 * </ul>

 *

 *

 * @author Simon Montagu, Matitiahu Allouche (ported from C code written by Markus W. Scherer)

 * @stable ICU 3.8

 *

 *

 * <h4> Sample code for the ICU Bidi API </h4>

 *

 * <h5>Rendering a paragraph with the ICU Bidi API</h5>

 *

 * This is (hypothetical) sample code that illustrates how the ICU Bidi API

 * could be used to render a paragraph of text. Rendering code depends highly on

 * the graphics system, therefore this sample code must make a lot of

 * assumptions, which may or may not match any existing graphics system's

 * properties.

 *

 * <p>

 * The basic assumptions are:

 * </p>

 * <ul>

 * <li>Rendering is done from left to right on a horizontal line.</li>

 * <li>A run of single-style, unidirectional text can be rendered at once.

 * </li>

 * <li>Such a run of text is passed to the graphics system with characters

 * (code units) in logical order.</li>

 * <li>The line-breaking algorithm is very complicated and Locale-dependent -

 * and therefore its implementation omitted from this sample code.</li>

 * </ul>

 *

 * <pre>

 *

 *  package com.ibm.icu.dev.test.bidi;

 *

 *  import com.ibm.icu.text.Bidi;

 *  import com.ibm.icu.text.BidiRun;

 *

 *  public class Sample {

 *

 *      static final int styleNormal = 0;

 *      static final int styleSelected = 1;

 *      static final int styleBold = 2;

 *      static final int styleItalics = 4;

 *      static final int styleSuper=8;

 *      static final int styleSub = 16;

 *

 *      static class StyleRun {

 *          int limit;

 *          int style;

 *

 *          public StyleRun(int limit, int style) {

 *              this.limit = limit;

 *              this.style = style;

 *          }

 *      }

 *

 *      static class Bounds {

 *          int start;

 *          int limit;

 *

 *          public Bounds(int start, int limit) {

 *              this.start = start;

 *              this.limit = limit;

 *          }

 *      }

 *

 *      static int getTextWidth(String text, int start, int limit,

 *                              StyleRun[] styleRuns, int styleRunCount) {

 *          // simplistic way to compute the width

 *          return limit - start;

 *      }

 *

 *      // set limit and StyleRun limit for a line

 *      // from text[start] and from styleRuns[styleRunStart]

 *      // using Bidi.getLogicalRun(...)

 *      // returns line width

 *      static int getLineBreak(String text, Bounds line, Bidi para,

 *                              StyleRun styleRuns[], Bounds styleRun) {

 *          // dummy return

 *          return 0;

 *      }

 *

 *      // render runs on a line sequentially, always from left to right

 *

 *      // prepare rendering a new line

 *      static void startLine(byte textDirection, int lineWidth) {

 *          System.out.println();

 *      }

 *

 *      // render a run of text and advance to the right by the run width

 *      // the text[start..limit-1] is always in logical order

 *      static void renderRun(String text, int start, int limit,

 *                            byte textDirection, int style) {

 *      }

 *

 *      // We could compute a cross-product

 *      // from the style runs with the directional runs

 *      // and then reorder it.

 *      // Instead, here we iterate over each run type

 *      // and render the intersections -

 *      // with shortcuts in simple (and common) cases.

 *      // renderParagraph() is the main function.

 *

 *      // render a directional run with

 *      // (possibly) multiple style runs intersecting with it

 *      static void renderDirectionalRun(String text, int start, int limit,

 *                                       byte direction, StyleRun styleRuns[],

 *                                       int styleRunCount) {

 *          int i;

 *

 *          // iterate over style runs

 *          if (direction == Bidi.LTR) {

 *              int styleLimit;

 *              for (i = 0; i < styleRunCount; ++i) {

 *                  styleLimit = styleRuns[i].limit;

 *                  if (start < styleLimit) {

 *                      if (styleLimit > limit) {

 *                          styleLimit = limit;

 *                      }

 *                      renderRun(text, start, styleLimit,

 *                                direction, styleRuns[i].style);

 *                      if (styleLimit == limit) {

 *                          break;

 *                      }

 *                      start = styleLimit;

 *                  }

 *              }

 *          } else {

 *              int styleStart;

 *

 *              for (i = styleRunCount-1; i >= 0; --i) {

 *                  if (i > 0) {

 *                      styleStart = styleRuns[i-1].limit;

 *                  } else {

 *                      styleStart = 0;

 *                  }

 *                  if (limit >= styleStart) {

 *                      if (styleStart < start) {

 *                          styleStart = start;

 *                      }

 *                      renderRun(text, styleStart, limit, direction,

 *                                styleRuns[i].style);

 *                      if (styleStart == start) {

 *                          break;

 *                      }

 *                      limit = styleStart;

 *                  }

 *              }

 *          }

 *      }

 *

 *      // the line object represents text[start..limit-1]

 *      static void renderLine(Bidi line, String text, int start, int limit,

 *                             StyleRun styleRuns[], int styleRunCount) {

 *          byte direction = line.getDirection();

 *          if (direction != Bidi.MIXED) {

 *              // unidirectional

 *              if (styleRunCount <= 1) {

 *                  renderRun(text, start, limit, direction, styleRuns[0].style);

 *              } else {

 *                  renderDirectionalRun(text, start, limit, direction,

 *                                       styleRuns, styleRunCount);

 *              }

 *          } else {

 *              // mixed-directional

 *              int count, i;

 *              BidiRun run;

 *

 *              try {

 *                  count = line.countRuns();

 *              } catch (IllegalStateException e) {

 *                  e.printStackTrace();

 *                  return;

 *              }

 *              if (styleRunCount <= 1) {

 *                  int style = styleRuns[0].style;

 *

 *                  // iterate over directional runs

 *                  for (i = 0; i < count; ++i) {

 *                      run = line.getVisualRun(i);

 *                      renderRun(text, run.getStart(), run.getLimit(),

 *                                run.getDirection(), style);

 *                  }

 *              } else {

 *                  // iterate over both directional and style runs

 *                  for (i = 0; i < count; ++i) {

 *                      run = line.getVisualRun(i);

 *                      renderDirectionalRun(text, run.getStart(),

 *                                           run.getLimit(), run.getDirection(),

 *                                           styleRuns, styleRunCount);

 *                  }

 *              }

 *          }

 *      }

 *

 *      static void renderParagraph(String text, byte textDirection,

 *                                  StyleRun styleRuns[], int styleRunCount,

 *                                  int lineWidth) {

 *          int length = text.length();

 *          Bidi para = new Bidi();

 *          try {

 *              para.setPara(text,

 *                           textDirection != 0 ? Bidi.LEVEL_DEFAULT_RTL

 *                                              : Bidi.LEVEL_DEFAULT_LTR,

 *                           null);

 *          } catch (Exception e) {

 *              e.printStackTrace();

 *              return;

 *          }

 *          byte paraLevel = (byte)(1 & para.getParaLevel());

 *          StyleRun styleRun = new StyleRun(length, styleNormal);

 *

 *          if (styleRuns == null || styleRunCount <= 0) {

 *              styleRuns = new StyleRun[1];

 *              styleRunCount = 1;

 *              styleRuns[0] = styleRun;

 *          }

 *          // assume styleRuns[styleRunCount-1].limit>=length

 *

 *          int width = getTextWidth(text, 0, length, styleRuns, styleRunCount);

 *          if (width <= lineWidth) {

 *              // everything fits onto one line

 *

 *              // prepare rendering a new line from either left or right

 *              startLine(paraLevel, width);

 *

 *              renderLine(para, text, 0, length, styleRuns, styleRunCount);

 *          } else {

 *              // we need to render several lines

 *              Bidi line = new Bidi(length, 0);

 *              int start = 0, limit;

 *              int styleRunStart = 0, styleRunLimit;

 *

 *              for (;;) {

 *                  limit = length;

 *                  styleRunLimit = styleRunCount;

 *                  width = getLineBreak(text, new Bounds(start, limit),

 *                                       para, styleRuns,

 *                                       new Bounds(styleRunStart, styleRunLimit));

 *                  try {

 *                      line = para.setLine(start, limit);

 *                  } catch (Exception e) {

 *                      e.printStackTrace();

 *                      return;

 *                  }

 *                  // prepare rendering a new line

 *                  // from either left or right

 *                  startLine(paraLevel, width);

 *

 *                  if (styleRunStart > 0) {

 *                      int newRunCount = styleRuns.length - styleRunStart;

 *                      StyleRun[] newRuns = new StyleRun[newRunCount];

 *                      System.arraycopy(styleRuns, styleRunStart, newRuns, 0,

 *                                       newRunCount);

 *                      renderLine(line, text, start, limit, newRuns,

 *                                 styleRunLimit - styleRunStart);

 *                  } else {

 *                      renderLine(line, text, start, limit, styleRuns,

 *                                 styleRunLimit - styleRunStart);

 *                  }

 *                  if (limit == length) {

 *                      break;

 *                  }

 *                  start = limit;

 *                  styleRunStart = styleRunLimit - 1;

 *                  if (start >= styleRuns[styleRunStart].limit) {

 *                      ++styleRunStart;

 *                  }

 *              }

 *          }

 *      }

 *

 *      public static void main(String[] args)

 *      {

 *          renderParagraph("Some Latin text...", Bidi.LTR, null, 0, 80);

 *          renderParagraph("Some Hebrew text...", Bidi.RTL, null, 0, 60);

 *      }

 *  }

 *

 * </pre>

 */

public class BidiBase {

    class Point {

        int pos;    /* position in text */

        int flag;   /* flag for LRM/RLM, before/after */

    }

    class InsertPoints {

        int size;

        int confirmed;

        Point[] points = new Point[0];

    }

    /** Paragraph level setting<p>

     *

     * Constant indicating that the base direction depends on the first strong

     * directional character in the text according to the Unicode Bidirectional

     * Algorithm. If no strong directional character is present,

     * then set the paragraph level to 0 (left-to-right).<p>

     *

     * If this value is used in conjunction with reordering modes

     * <code>REORDER_INVERSE_LIKE_DIRECT</code> or

     * <code>REORDER_INVERSE_FOR_NUMBERS_SPECIAL</code>, the text to reorder

     * is assumed to be visual LTR, and the text after reordering is required

     * to be the corresponding logical string with appropriate contextual

     * direction. The direction of the result string will be RTL if either

     * the righmost or leftmost strong character of the source text is RTL

     * or Arabic Letter, the direction will be LTR otherwise.<p>

     *

     * If reordering option <code>OPTION_INSERT_MARKS</code> is set, an RLM may

     * be added at the beginning of the result string to ensure round trip

     * (that the result string, when reordered back to visual, will produce

     * the original source text).

     * @see #REORDER_INVERSE_LIKE_DIRECT

     * @see #REORDER_INVERSE_FOR_NUMBERS_SPECIAL

     * @stable ICU 3.8

     */

    public static final byte INTERNAL_LEVEL_DEFAULT_LTR = (byte)0x7e;

    /** Paragraph level setting<p>

     *

     * Constant indicating that the base direction depends on the first strong

     * directional character in the text according to the Unicode Bidirectional

     * Algorithm. If no strong directional character is present,

     * then set the paragraph level to 1 (right-to-left).<p>

     *

     * If this value is used in conjunction with reordering modes

     * <code>REORDER_INVERSE_LIKE_DIRECT</code> or

     * <code>REORDER_INVERSE_FOR_NUMBERS_SPECIAL</code>, the text to reorder

     * is assumed to be visual LTR, and the text after reordering is required

     * to be the corresponding logical string with appropriate contextual

     * direction. The direction of the result string will be RTL if either

     * the righmost or leftmost strong character of the source text is RTL

     * or Arabic Letter, or if the text contains no strong character;

     * the direction will be LTR otherwise.<p>

     *

     * If reordering option <code>OPTION_INSERT_MARKS</code> is set, an RLM may

     * be added at the beginning of the result string to ensure round trip

     * (that the result string, when reordered back to visual, will produce

     * the original source text).

     * @see #REORDER_INVERSE_LIKE_DIRECT

     * @see #REORDER_INVERSE_FOR_NUMBERS_SPECIAL

     * @stable ICU 3.8

     */

    public static final byte INTERNAL_LEVEL_DEFAULT_RTL = (byte)0x7f;

    /**

     * Maximum explicit embedding level.

     * (The maximum resolved level can be up to <code>MAX_EXPLICIT_LEVEL+1</code>).

     * @stable ICU 3.8