home *** CD-ROM | disk | FTP | other *** search
/ Java 1.2 How-To / JavaHowTo.iso / 3rdParty / jbuilder / unsupported / JDK1.2beta3 / SOURCE / SRC.ZIP / java / awt / font / IncrementalBidi.java < prev    next >
Encoding:
Java Source  |  1998-03-20  |  79.6 KB  |  2,334 lines
  1. /*
  2.  * @(#)IncrementalBidi.java    1.10 98/03/18
  3.  *
  4.  * Copyright 1997, 1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  *
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. /*
  16.  * (C) Copyright Taligent, Inc. 1996 - 1997, All Rights Reserved
  17.  * (C) Copyright IBM Corp. 1996 - 1998, All Rights Reserved
  18.  *
  19.  * The original version of this source code and documentation is
  20.  * copyrighted and owned by Taligent, Inc., a wholly-owned subsidiary
  21.  * of IBM. These materials are provided under terms of a License
  22.  * Agreement between Taligent and Sun. This technology is protected
  23.  * by multiple US and International patents.
  24.  *
  25.  * This notice and attribution to Taligent may not be removed.
  26.  * Taligent is a registered trademark of Taligent, Inc.
  27.  *
  28.  */
  29.  
  30. package java.awt.font;
  31.  
  32. import java.text.CharacterIterator;
  33. import java.text.AttributedCharacterIterator;
  34. import java.text.AttributeSet;
  35.  
  36. // Debugging
  37. import java.io.PrintStream;
  38.  
  39. /**
  40.  * This version has been modified to support a modified bidi algorithm that
  41.  * increases the locality of operations on the text.
  42.  *
  43.  * <p>1. It treats roman numeric text three different ways:
  44.  *
  45.  * <p>STRONG_ROMAN - EN remains EN, and is treated as L when resolving neutrals
  46.  * <br>STRONG_ARABIC - EN becomes AN, and is treated as R when resolving
  47.  * neutrals
  48.  * <br>WEAK_ARABIC - EN remains EN, and is treated as R when resolving neutrals
  49.  *
  50.  * <p>The client sees a style that applies to characters that can have one of
  51.  * these three possible values.  Bidi interprets these styles to override the
  52.  * default direction array.
  53.  * Clients calling bidi using the low level api that takes a direction and
  54.  * level array should initialize the values of the arrays similarly.
  55.  *
  56.  * <p>This affects bidi rules are P0 and N3, as follows:
  57.  *
  58.  * <p>Rule P0 is disabled.  EN values that should become AN must be styled using
  59.  * STRONG_ARABIC.
  60.  * <p>Rule N3 (a) and (b) are disabled.  EN values that should be treated as R
  61.  * must be styled using WEAK_ARABIC.  Those values that should be treated as L
  62.  * may be styled STRONG_ROMAN
  63.  * or left unstyled.
  64.  *
  65.  * <p>2. It does not default run direction.
  66.  *
  67.  * <p> The client sees a style that applies to paragraphs that can have either
  68.  * of two values, RUN_DIRECTION_LTR or RUN_DIRECTION_RTL.  The client applies
  69.  * the appropriate style
  70.  * to the paragraph text.
  71.  *
  72.  * <p>This disables bidi rules B1 and B2.
  73.  *
  74.  * <p>The default rules <b>are applied</b> when constructing a bidi object from
  75.  * unstyled text (String or CharacterIterator) or from styled text
  76.  * (AttributedCharacterIterator) when embedding styles are absent.  These rules
  77.  * are applied <b>only at construction time</b>, and so this behavior is only
  78.  * useful for static text.  Calling insert or delete on the bidi object will
  79.  * not reapply these rules.
  80.  */
  81.  
  82. final class IncrementalBidi {
  83.  
  84.     /* All public so clients can construct any direction array. */
  85.  
  86.     public static final byte L  = 0;    /* left to right (strong) */
  87.     public static final byte R  = 1;    /* right to left (strong) */
  88.     public static final byte EN = 2;    /* european number (weak) */
  89.     public static final byte ES = 3;    /* european number separator (weak) */
  90.     public static final byte ET = 4;    /* european number terminator (weak) */
  91.     public static final byte AN = 5;    /* arabic number (weak) */
  92.     public static final byte CS = 6;    /* common number separator (weak) */
  93.     public static final byte B  = 7;    /* block separator */
  94.     public static final byte S  = 8;    /* segment separator */
  95.     public static final byte WS = 9;    /* whitespace */
  96.     public static final byte ON = 10;   /* other neutral */
  97.  
  98.     public static final byte WA = 11;   /* weak arabic variant of EN */
  99.  
  100.     /* These are used by the utility that strips explicit formatting codes. When editing,
  101.      * these just can't be around.  Otherwise client editors need to be smart and delete the
  102.      * matching codes.  I'd rather convert going in and out of the editor, and forget
  103.      * about keeping in synch with the original source while editing. */
  104.  
  105.     private static final char LRE = 0x202A; /* left to right embedding */
  106.     private static final char RLE = 0x202B; /* right to left embedding */
  107.     private static final char PDF = 0x202C; /* pop directional formatting */
  108.     private static final char LRO = 0x202D; /* left to right override */
  109.     private static final char RLO = 0x202E; /* right to left override */
  110.  
  111.     private static final char MIN_EXPLICIT_CODE = LRE; // bounds of range of explicit formatting codes
  112.     private static final char MAX_EXPLICIT_CODE = RLO;
  113.  
  114.     /* These codes are not stripped. */
  115.  
  116.     private static final char LRM = 0x200E; /* left to right mark */
  117.     private static final char RLM = 0x200F; /* right to left mark */
  118.  
  119.     /* The embedding/override level stack limit */
  120.  
  121.     private static final char NUMLEVELS = 16;
  122.  
  123.     /* The range of Arabic unicode values, used for default style application. */
  124.  
  125.     private static final char ARABIC_BLOCK_START = 0x0600;
  126.     private static final char ARABIC_BLOCK_LIMIT = 0x0700;
  127.  
  128.     // !!! debug flags, remove when ship
  129.     static boolean TEST = false;
  130.     static boolean DEBUGGING = false;
  131.     static PrintStream debugStream = null;
  132.  
  133.     /* State. */
  134.  
  135.     private int length;                 // the length of the paragraph
  136.     private boolean canonical;          // true if all levels are zero
  137.     private boolean ltr;                // the base nesting level (line direction)
  138.     private GapArrayOfByte srcdirs;     // the source directional formatting codes
  139.     private GapArrayOfByte srclevels;   // the source nesting levels
  140.     private GapArrayOfByte dirs;        // the resulting directional formatting codes
  141.     private GapArrayOfByte levels;      // the resulting levels
  142.  
  143.     /**
  144.      * Return the default direction class for this character.
  145.      */
  146.     public static byte getDirectionClass(char c) {
  147.         if (TEST) {
  148.             byte dir;
  149.  
  150.             if (((c >= 'a') && (c <= 'z')) || c == LRO || c == LRE || c == LRM)
  151.                 dir = L;
  152.             else if (((c >= 'A') && (c <= 'Z')) || c == RLO || c == RLE || c == RLM)
  153.                 dir = R;
  154.             else if ((c >= '0') && (c <= '9')) // !!! no arabic numerals for now
  155.                 dir = EN;
  156.             else if ((c == '.') || (c == '/'))
  157.                 dir = ES;
  158.             else if ((c == '$') || (c == '+'))
  159.                 dir = ET;
  160.             else if ((c >= '5') && (c <= '9'))
  161.                 dir = AN;
  162.             else if ((c == ',') || (c == ':'))
  163.                 dir = CS;
  164.             else if (c == '\r')
  165.                 dir = B;
  166.             else if (c == '\t')
  167.                 dir = S;
  168.             else if (c == ' ')
  169.                 dir = WS;
  170.             else
  171.                 dir = ON;
  172.  
  173.             return dir;
  174.         } else {
  175.             // real code
  176.             return fgDirectionClassArray.elementAt(c);
  177.         }
  178.     }
  179.  
  180.     //
  181.     // Helper functions
  182.     //
  183.  
  184.     /**
  185.      * Return true if the string contains any right-to-left characters that
  186.      * might require bidi processing.
  187.      */
  188.     private static boolean containsBidi(String str) {
  189.         // return containsBidi(str.toCharArray(), 0, str.length());
  190.         int start = 0;
  191.         int limit = str.length();
  192.         if (TEST) {
  193.             while (start < limit) {
  194.                 char c = str.charAt(start);
  195.                 if (c <= 'Z' && c >= 'A') {
  196.                     byte dir = getDirectionClass(c);
  197.                     if (dir == R || dir == AN)
  198.                         return true;
  199.                 }
  200.                 ++start;
  201.             }
  202.         } else {
  203.             while (start < limit) {
  204.                 char c = str.charAt(start);
  205.                 if (c > 0x00ff) {
  206.                     byte dir = getDirectionClass(c);
  207.                     if (dir == R || dir == AN)
  208.                         return true;
  209.                 }
  210.                 ++start;
  211.             }
  212.         }
  213.  
  214.         return false;
  215.     }
  216.  
  217.     /**
  218.      * Return true if the iterator contains any right-to-left characters in its
  219.      * range that might require bidi processing.
  220.      */
  221.     private static boolean containsBidi(CharacterIterator iter)
  222.     {
  223.         char[] text = toCharArray(iter);
  224.         return containsBidi(text, 0, text.length);
  225.     }
  226.  
  227.     /**
  228.      * Return true if the text range contains any right-to-left characters that
  229.      * might require bidi processing.
  230.      */
  231.     private static boolean containsBidi(char[] text, int start, int limit)
  232.     {
  233.         if (TEST) {
  234.             while (start < limit) {
  235.                 char c = text[start];
  236.                 if (c <= 'Z' && c >= 'A') {
  237.                     byte dir = getDirectionClass(c);
  238.                     if (dir == R || dir == AN)
  239.                         return true;
  240.                 }
  241.                 ++start;
  242.             }
  243.         } else {
  244.             while (start < limit) {
  245.                 char c = text[start];
  246.                 if (c > 0x00ff) {
  247.                     byte dir = getDirectionClass(c);
  248.                     if (dir == R || dir == AN)
  249.                         return true;
  250.                 }
  251.                 ++start;
  252.             }
  253.         }
  254.         return false;
  255.     }
  256.  
  257.     /**
  258.      * Return true if the styled string contains any right-to-left characters
  259.      * that might require bidi processing, or any bidirectional styles that
  260.      * might require bidi processing.
  261.      */
  262.     private static boolean containsBidi(StyledString sstr) {
  263.       // !!! package access to internal array removed by jk
  264.       // See StyledString.getChars()
  265.         return containsBidi(sstr.getChars(), 0, sstr.getChars().length) ||
  266.            attrContainsBidi(new StyledStringIterator(sstr));
  267.     }
  268.  
  269.     /**
  270.      * Return true if the iterator contains any right-to-left characters in its
  271.      * range that might require bidi processing, or any bidirectional styles
  272.      * that might require bidi processing.
  273.      */
  274.     private static boolean containsBidi(AttributedCharacterIterator iter) {
  275.         return containsBidi((CharacterIterator)iter) || attrContainsBidi(iter);
  276.     }
  277.  
  278.     /**
  279.      * Return true if the attribute set indicates bidi processing is required.
  280.      */
  281.     private static boolean attrContainsBidi(AttributeSet attrs) {
  282.         if (attrs != null) {
  283.             if (TextAttributeSet.RUN_DIRECTION_RTL.equals(
  284.         attrs.get(TextAttributeSet.RUN_DIRECTION))) {
  285.                 return true;
  286.         }
  287.             if (attrs.get(TextAttributeSet.BIDI_EMBEDDING) != null) {
  288.                 return true;
  289.         }
  290.             if (attrs.get(TextAttributeSet.BIDI_NUMERIC) != null) {
  291.                 return true;
  292.         }
  293.         }
  294.  
  295.         return false;
  296.     }
  297.  
  298.     private static boolean attrContainsBidi(AttributedCharacterIterator iter) {
  299.         iter.first();
  300.         AttributeSet attrs = iter.getAttributes();
  301.         if (TextAttributeSet.RUN_DIRECTION_RTL.equals(
  302.         attrs.get(TextAttributeSet.RUN_DIRECTION))) {
  303.             return true;
  304.     }
  305.  
  306.         for (;;) {
  307.             if (attrs.get(TextAttributeSet.BIDI_EMBEDDING) != null ||
  308.                 attrs.get(TextAttributeSet.BIDI_NUMERIC) != null) {
  309.                     return true;
  310.                 }
  311.  
  312.             if (iter.setIndex(iter.getRunLimit()) == CharacterIterator.DONE) {
  313.                 break;
  314.             }
  315.  
  316.             attrs = iter.getAttributes();
  317.         }
  318.  
  319.         return false;
  320.     }
  321.  
  322.     private static char[] toCharArray(CharacterIterator iter) {
  323.         int start = iter.getBeginIndex();
  324.         int limit = iter.getEndIndex();
  325.         char[] text = new char[limit - start];
  326.  
  327.         int n = 0;
  328.         for (char c = iter.first(); c != iter.DONE; c = iter.next()) {
  329.             text[n++] = c;
  330.         }
  331.  
  332.         return text;
  333.     }
  334.  
  335.     /**
  336.      * Check to see if the paragraph represented by the string requires bidi
  337.      * processing, and if so, return a bidi object.  Otherwise return null.
  338.      */
  339.     public static IncrementalBidi createBidi(String str) {
  340.         if (containsBidi(str)) {
  341.             return new IncrementalBidi(str.toCharArray(),
  342.                 0, str.length(), null);
  343.         }
  344.  
  345.         return null;
  346.     }
  347.  
  348.     /**
  349.      * Check to see if the paragraph represented by the iterator's range
  350.      * requires bidi processing, and if so, return a bidi object.  Otherwise
  351.      * return null.
  352.      */
  353.     public static IncrementalBidi createBidi(CharacterIterator iter) {
  354.         char[] text = toCharArray(iter);
  355.         return createBidi(text, 0, text.length, null);
  356.     }
  357.  
  358.     /**
  359.      * Check to see if the paragraph represented by the iterator's range
  360.      * requires bidi processing, and if so, return a bidi object.  Otherwise
  361.      * return null.
  362.      */
  363.     public static IncrementalBidi createBidi(char[] text, int start,
  364.         int limit, AttributeSet attrs) {
  365.  
  366.         if (containsBidi(text, start, limit) || attrContainsBidi(attrs)) {
  367.             return new IncrementalBidi(text, start, limit, attrs);
  368.         }
  369.         return null;
  370.     }
  371.  
  372.     /**
  373.      * Check to see if the paragraph represented by the iterator's range
  374.      * requires bidi processing, and if so, return a bidi object.  Otherwise
  375.      *  return null.
  376.      */
  377.     public static IncrementalBidi createBidi(AttributedCharacterIterator iter) {
  378.         if (containsBidi(iter)) {
  379.             return new IncrementalBidi(iter);
  380.         }
  381.  
  382.         return null;
  383.     }
  384.  
  385.     /**
  386.      * Apply default rules for line direction and numeric type.  Return
  387.      * true if the default line direction is ltr, false otherwise.  Generate
  388.      * values in the direction array, applying default numeric rules.
  389.      */
  390.      private boolean applyDefaultRules(CharacterIterator iter,
  391.          byte[] dirArray, byte[] lvlArray) {
  392.  
  393.         char[] text = toCharArray(iter);
  394.         return applyDefaultRules(text, 0, text.length, dirArray, lvlArray,
  395.                                  null);
  396.      }
  397.  
  398.      private boolean applyDefaultRules(char[] text, int start, int limit,
  399.         byte[] dirArray, byte[] lvlArray, AttributeSet attrs) {
  400.  
  401.         boolean ltr = true;
  402.         Boolean rd = (Boolean)(attrs != null ?
  403.             attrs.get(TextAttributeSet.RUN_DIRECTION) : null);
  404.         if (rd != null) {
  405.             ltr = TextAttributeSet.RUN_DIRECTION_LTR.equals(rd);
  406.         } else {
  407.             for (int i = start; i < limit; i++) {
  408.                 byte dir = getDirectionClass(text[i]);
  409.                 if (dir == L || dir == R) {
  410.                     ltr = dir == L;
  411.                     break;
  412.                 }
  413.             }
  414.         }
  415.  
  416.         int emb = -1;
  417.         Integer be = (Integer)(attrs != null ?
  418.             attrs.get(TextAttributeSet.BIDI_EMBEDDING) : null);
  419.         if (be != null) {
  420.             emb = be.intValue();
  421.             if (emb > 0xf) {
  422.                 byte lvl = (byte)(emb & 0xf);
  423.                 byte dir = (byte)(emb & 0x1);
  424.                 for (int i = 0; i < dirArray.length; i++) {
  425.                     dirArray[i] = dir;
  426.                     lvlArray[i] = lvl;
  427.                 }
  428.  
  429.                 // !!! early return
  430.                 return dir == 0;
  431.             } else {
  432.                 byte lvl = (byte)emb;
  433.                 for (int i = 0; i < lvlArray.length; i++) {
  434.                     lvlArray[i] = lvl;
  435.                 }
  436.             }
  437.         }
  438.  
  439.         Integer bn = (Integer)(attrs != null ?
  440.             attrs.get(TextAttributeSet.BIDI_NUMERIC) : null);
  441.         if (bn != null) {
  442.             byte enConvert = (byte)bn.intValue();
  443.             int n = 0;
  444.             for (int i = start; i < limit; i++) {
  445.                 byte dir = getDirectionClass(text[i]);
  446.                 if (enConvert != EN && dir == EN) {
  447.                     dir = enConvert;
  448.                 }
  449.                 dirArray[n++] = dir;
  450.             }
  451.         } else {
  452.             // apply default numeric rules
  453.             // P0. EN following first strong == arabic (R) -> AN
  454.             // N3. EN following first strong == R (not arabic) -> WA
  455.             byte enConvert = WA;
  456.             boolean convert = ltr == false;
  457.             int n = 0;
  458.             for (int i = start; i < limit; i++) {
  459.                 char c = text[i];
  460.                 byte dir = getDirectionClass(c);
  461.                 if (dir == R) {
  462.                     convert = true;
  463.                     if (c >= ARABIC_BLOCK_START && c < ARABIC_BLOCK_LIMIT)
  464.                         enConvert = AN;
  465.                     else
  466.                         enConvert = WA;
  467.                 } else if (dir == L) {
  468.                     convert = false;
  469.                 } else if (dir == EN) {
  470.                     if (convert)
  471.                         dir = enConvert;
  472.                 }
  473.  
  474.                 dirArray[n++] = dir;
  475.             }
  476.         }
  477.  
  478.  
  479.         if (ltr == false && emb < 1)
  480.             for (int i = 0; i < lvlArray.length; i++)
  481.                 lvlArray[i] = 1;
  482.  
  483.         return ltr;
  484.      }
  485.  
  486.     /**
  487.      * Construct an incremental bidi with no text, but with the indicated line
  488.      * direction. This line direction is fixed for all subsequent insertions
  489.      * and deletions from the bidi.
  490.      */
  491.     public IncrementalBidi(boolean ltr) {
  492.         reset(new byte[] {}, new byte[] {}, ltr, 0);
  493.     }
  494.  
  495.     /**
  496.      * Construct from a paragraph represented by the string, applying default
  497.      * rules.
  498.      *
  499.      * The default rules for line direction and numeric type are applied.
  500.      * To avoid this, clients should call the styled text interface, setting
  501.      * the run direction style to indicate default processing is complete.
  502.      *
  503.      * @param str the paragraph for which to generate bidi information.
  504.      */
  505.     public IncrementalBidi(String str) {
  506.         this(str.toCharArray(), 0, str.length(), null);
  507.     }
  508.  
  509.     /**
  510.      * Construct from a text array.
  511.      */
  512.     public IncrementalBidi(char[] text, int start, int limit, AttributeSet attrs) {
  513.         int len = limit - start;
  514.  
  515.         byte[] dirArray = new byte[len];
  516.         byte[] lvlArray = new byte[len];
  517.  
  518.         boolean ltr = applyDefaultRules(text, start, limit, dirArray, lvlArray, attrs);
  519.  
  520.         reset(dirArray, lvlArray, ltr, len);
  521.     }
  522.  
  523.     /**
  524.      * Construct from styled text.
  525.      *
  526.      * @param text the styled text to use.  The entire current range will be
  527.      * considered to be one
  528.      * paragraph.
  529.      */
  530.     public IncrementalBidi(AttributedCharacterIterator text) {
  531.         int begin = text.getBeginIndex();
  532.         int end = text.getEndIndex();
  533.         int len = end - begin;
  534.  
  535.         boolean ltr = true;
  536.         byte[] dirArray = new byte[len];
  537.         byte[] lvlArray = new byte[len];
  538.  
  539.         boolean appliedDefaults = false;
  540.  
  541.         char c = text.first();
  542.  
  543.         AttributeSet ff = text.getAttributes();
  544.         Boolean runDirection = (Boolean)ff.get(TextAttributeSet.RUN_DIRECTION);
  545.         if (runDirection != null) {
  546.             ltr = TextAttributeSet.RUN_DIRECTION_LTR.equals(runDirection);
  547.         } else {
  548.             ltr = applyDefaultRules(text, dirArray, lvlArray);
  549.             c = text.first(); // reset iterator
  550.             appliedDefaults = true;
  551.         }
  552.  
  553.         boolean embeddingOverride = false; // no override
  554.         byte    embeddingOverrideDir = L;
  555.         boolean numericOverride = false; // EN unchanged
  556.         byte    numericOverrideDir = AN;
  557.         byte    baseLevel = ltr ? L : R;
  558.         byte    level = baseLevel;
  559.         int     index = 0;
  560.  
  561.         while (index < len) {
  562.             ff = text.getAttributes();
  563.             int indexLimit = text.getRunLimit() - begin;
  564.  
  565.             Integer embedding = (Integer)ff.get(TextAttributeSet.BIDI_EMBEDDING);
  566.             if (embedding != null) {
  567.                 level = (byte)embedding.intValue();
  568.                 if (level > 0xf) {
  569.                     embeddingOverride = true;
  570.                     // (level & 0x1) == 0 ? L : R;
  571.                     embeddingOverrideDir = (byte)(level & 0x1);
  572.                     level = (byte)(level & 0xf);
  573.                 } else {
  574.                     embeddingOverride = false;
  575.                 }
  576.             } else {
  577.                 embeddingOverride = false;
  578.                 level = baseLevel;
  579.             }
  580.  
  581.             Integer numeric = (Integer)ff.get(TextAttributeSet.BIDI_NUMERIC);
  582.             if (numeric != null) {
  583.                 numericOverrideDir =(byte)numeric.intValue();
  584.                 if (numericOverrideDir != EN) {
  585.                     numericOverride = true;
  586.                 } else {
  587.                     numericOverride = false;
  588.                 }
  589.             } else {
  590.                 numericOverride = false;
  591.             }
  592.  
  593.             while (index < indexLimit) {
  594.                 if (embeddingOverride) {
  595.                     dirArray[index] = embeddingOverrideDir;
  596.                 } else if (numericOverride) {
  597.                     if (appliedDefaults) {
  598.                         if (dirArray[index] == EN) {
  599.                             dirArray[index] = numericOverrideDir;
  600.                         }
  601.                     } else {
  602.                         byte direction = getDirectionClass(c);
  603.                         if (direction == EN) {
  604.                             direction = numericOverrideDir;
  605.                         }
  606.                         dirArray[index] = direction;
  607.                     }
  608.                 } else {
  609.                     if (!appliedDefaults) {
  610.                         dirArray[index] = getDirectionClass(c);
  611.                     }
  612.                 }
  613.  
  614.                 lvlArray[index] = level;
  615.  
  616.                 index++;
  617.                 c = text.next();
  618.             }
  619.         }
  620.  
  621.         reset(dirArray, lvlArray, ltr, len);
  622.     }
  623.  
  624.     /**
  625.      * Construct from a dirs and levels array.
  626.      *
  627.      * This is the low-level constructor, the raw data is passed directly into
  628.      * the  bidi object.  The bidi object does not modify or keep a reference
  629.      * to these arrays.
  630.      *
  631.      * @param dirArray the array of character bidi direction codes.
  632.      * @param levelArray the array of embedding levels.  It contains
  633.      * values from 0 to 15 indicating the embedding level for the corresponding
  634.      * character. Overrides have already been incorporated into the dirs array.
  635.      * If ltr is false, all levels must be greater than zero.
  636.      * @param ltr true if the text is left to right (top to bottom), false
  637.      * otherwise.
  638.      * @param length the length of the paragraph.  It must be less than or
  639.      * equal to the length of each array.
  640.      */
  641.     public IncrementalBidi(byte[] dirArray, byte[] levelArray, boolean ltr,
  642.                            int length) {
  643.         reset(dirArray, levelArray, ltr, length);
  644.     }
  645.  
  646.     /**
  647.      * Reset the bidi information.
  648.      *
  649.      * Constructors call this to complete initialization of the bidi object.
  650.      *
  651.      */
  652.     private void reset(byte[] dirArray, byte[] lvlArray, boolean ltr,
  653.                        int length)
  654.     {
  655.         if (dirArray == null || lvlArray == null ||
  656.             dirArray.length < length || lvlArray.length < length) {
  657.             throw new Error("invalid arguments");
  658.         }
  659.  
  660.         this.length = length;
  661.         this.canonical = ltr;
  662.         this.ltr = ltr;
  663.         // !!! could use just one 4x array...
  664.         this.srcdirs = new GapArrayOfByte(dirArray, 0, length);
  665.         this.srclevels = new GapArrayOfByte(lvlArray, 0, length);
  666.         this.dirs = (GapArrayOfByte)srcdirs.clone();
  667.         this.levels = (GapArrayOfByte)srclevels.clone();
  668.  
  669.         /*
  670.          * this early check for canonical text differs from the public check
  671.          * since it is on the source data.  This idea is to avoid running
  672.          * reapply at all.
  673.          */
  674.  
  675.         for (int i = 0; canonical && i < length; i++)
  676.             canonical = dirArray[i] != R && lvlArray[i] == 0;
  677.  
  678.         if (!canonical)
  679.             reapply(0, length);
  680.     }
  681.  
  682.     /**
  683.      * Return true if the bidi is canonical-- the level of each character is
  684.      * even. Canonical text is all left-to-right.
  685.      */
  686.     public boolean isCanonical() {
  687.         return canonical;
  688.     }
  689.  
  690.     /** Return true if the bidi is canonical over the range. */
  691.     public boolean isCanonical(int start, int limit) {
  692.         for (int i = start; i < limit; i++) {
  693.             if (levels.at(i) > 0) {
  694.                 return false;
  695.             }
  696.         }
  697.         return true;
  698.     }
  699.  
  700.     /** Reapply the bidi algorithm to the range start-limit */
  701.  
  702.     private void reapply(int start, int limit) {
  703.         if (start == limit) {
  704.             return;
  705.         }
  706.  
  707.         if (DEBUGGING) debug("reapply from " + start + " to " + limit, null);
  708.  
  709.         resolveWeakTypes(start, limit);
  710.  
  711.         if (DEBUGGING) debug("after resolveWeakTypes", null);
  712.  
  713.         resolveNeutralTypes(start, limit);
  714.  
  715.         if (DEBUGGING) debug("after resolveNeutralTypes", null);
  716.  
  717.         resolveImplicitLevels(start, limit);
  718.  
  719.         if (DEBUGGING) debug("after resolveImplicitLevels", null);
  720.  
  721.         canonical = canonical ? isCanonical(start, limit) :
  722.             isCanonical(0, length);
  723.     }
  724.  
  725.     /*
  726.      * Reset the final arrays to the original arrays in preparation for
  727.      * calling reapply.
  728.      * Will this introduce an apparent embedding boundary at the limits?
  729.      * It shouldn't since the algorithm never computes from the resolved
  730.      * levels, only the source levels.  In the algorithm we're careful-- after
  731.      * writing the tests, anyway-- to distinguish the recomputation limits from
  732.      * an embedding boundary.
  733.      *
  734.      * Since reapply is also called when we construct, and the constructor takes
  735.      * care of setting up dirs and levels, keep this code here so we don't
  736.      * iterate over all the values again.
  737.      */
  738.  
  739.     private void reinit(int start, int limit) {
  740.         for (int i = start; i < limit; i++) {
  741.             dirs.atPut(i, srcdirs.at(i));
  742.             levels.atPut(i, srclevels.at(i));
  743.         }
  744.     }
  745.  
  746.     // This is used by insert to adjust the range to examine.
  747.  
  748.     private static final boolean canBecomeNeutral[] = {
  749.         false, // "L"
  750.         false, // "R"
  751.         false, // "EN"
  752.         true,  // "ES"
  753.         true,  // "ET"
  754.         false, // "AN"
  755.         true,  // "CS"
  756.         true,  // "B"
  757.         true,  // "S"
  758.         true,  // "WS"
  759.         true,  // "ON"
  760.         false  // "WA"
  761.     };
  762.  
  763.     /**
  764.      * Insert a character into the bidi information.  The new character is
  765.      * inserted
  766.      * at pos and has the indicated direction code and level.  Determine the
  767.      * damage area about pos and reapply bidi to it.
  768.      */
  769.     public void insert(int pos, byte dir, byte level) {
  770.         srcdirs.insert(pos, dir);
  771.         srclevels.insert(pos, level);
  772.         dirs.insert(pos, dir);
  773.         levels.insert(pos, level);
  774.  
  775.         length += 1;
  776.  
  777.         /*
  778.          * Set range to include anything that is or can become a neutral.
  779.          * This includes ES, CS, and ET which can become neutral due to weak
  780.          * type processing.  This takes care of resolveWeakTypes and
  781.          * resolveNeutralTypes.  ResolveImplicitLevels also needs a range
  782.          * adjustment to include the EN after a change, since the level of
  783.          * this EN depends on the previous direction.
  784.          */
  785.  
  786.         int start = pos;
  787.         int limit = pos + 1;
  788.  
  789.         while (start > 0 && canBecomeNeutral[srcdirs.at(start-1)]) {
  790.             --start;
  791.         }
  792.         while (limit < length && canBecomeNeutral[srcdirs.at(limit)]) {
  793.             ++limit;
  794.         }
  795.  
  796.         if (limit < length && srcdirs.at(limit) == EN) {
  797.             limit++;
  798.         }
  799.  
  800.         /*
  801.          * Reset dir and levels array within range to original values, we'll
  802.          * recompute. We must do this because the later parts of the algorithm
  803.          * use dirs, which the first part assumes is already initialized.
  804.          * Similarly, the resolveImplicitLevels function assumes levels has
  805.          * already been initialized and only writes changes to it.
  806.          */
  807.         reinit(start, limit);
  808.  
  809.         reapply(start, limit);
  810.     }
  811.  
  812.     /**
  813.      * Delete a character at pos.  Determine the damage area about pos and reapply bidi
  814.      * to it.
  815.      */
  816.     public void delete(int pos)
  817.     {
  818.         // see insert for notes on range adjustments
  819.  
  820.         srcdirs.delete(pos, 1);
  821.         srclevels.delete(pos, 1);
  822.         dirs.delete(pos, 1);
  823.         levels.delete(pos, 1);
  824.  
  825.         length -= 1;
  826.  
  827.         int start = pos;
  828.         int limit = pos;
  829.  
  830.         while (start > 0 && canBecomeNeutral[srcdirs.at(start-1)]) --start;
  831.         while (limit < length && canBecomeNeutral[srcdirs.at(limit)]) ++limit;
  832.  
  833.         if (limit < length && srcdirs.at(limit) == EN)
  834.             limit++;
  835.  
  836.         reinit(start, limit);
  837.  
  838.         reapply(start, limit);
  839.     }
  840.  
  841.     // This resolves serially in order from left to right, with the results of previous changes
  842.     // taken into account for later characters.  So, for example, a series of ET's after an EN
  843.     // will all change to EN, since once the first ET changes to EN, it is then treated as EN
  844.     // for transforming the following ET, and so on.  It will also process ETs before EN by
  845.     // scanning forward across runs of ET and checking the following character.
  846.     //
  847.     // Since this processes within the range only, the range must include any ET values
  848.     // that could be transformed by this function.  Otherwise, for example, a start
  849.     // at an EN that follows an ET will not transform the ET, although a start at the ET
  850.     // would.  When applying incrementally, start and limit should be past any runs of ET
  851.     // about the modification position.
  852.     //
  853.     // !!! This does not take embedded levels into account.  Should it?
  854.  
  855.     private void resolveWeakTypes(int start, int limit)
  856.     {
  857.         int i = start;
  858.  
  859.         byte prev = (i == 0) ? -1 : srcdirs.at(i - 1);
  860.  
  861.         byte cur = srcdirs.at(i);
  862.  
  863.         while (i < limit) {
  864.             int ii = i + 1;
  865.             byte next = (ii == length) ? -1 : srcdirs.at(ii);
  866.             byte ncur = cur;
  867.  
  868.             switch (cur) {
  869.                 case L:
  870.                 case R:
  871.                     break;
  872.  
  873.                 case ES:
  874.                     if ((prev == EN || prev == WA) && (next == EN || next == WA))
  875.                         ncur = EN;
  876.                     else
  877.                         ncur = ON;
  878.                     break;
  879.  
  880.                 case CS:
  881.                     if ((prev == EN || prev == WA) && (next == EN || next == WA))
  882.                         ncur = EN;
  883.                     else if (prev == AN && next == AN)
  884.                         ncur = AN;
  885.                     else
  886.                         ncur = ON;
  887.                     break;
  888.  
  889.                 case ET:
  890.                     if (prev == EN || prev == WA || next == EN || next == WA) {
  891.                         ncur = EN;
  892.                     } else if (next == ET) { // forward scan to handle ET ET EN
  893.                         for (int j = ii + 1; j < limit; ++j) {
  894.                             byte dir = srcdirs.at(j);
  895.                             if (dir == ET)
  896.                                 continue;
  897.  
  898.                             if (dir == EN || dir == WA) {
  899.                                 while (ii < j)
  900.                                     dirs.atPut(ii++, EN);
  901.                                 ncur = EN;
  902.                                 next = dir;
  903.                             }
  904.                             break;
  905.                         }
  906.                     } else {
  907.                         ncur = ON;
  908.                     }
  909.                     break;
  910.  
  911.                 default:
  912.                     break;
  913.             }
  914.  
  915.             if (ncur != cur)
  916.                 dirs.atPut(i, ncur);
  917.             i = ii;
  918.             prev = ncur;
  919.             cur = next;
  920.         }
  921.     }
  922.  
  923.     // According to Mark, this operation should never span a level boundary.  The start and end
  924.     // of the level should be treated like sot and eot, with the base direction the direction of the
  925.     // level.
  926.     //
  927.     // When applying incrementally, start and limit should be past any runs of neutrals about
  928.     // the modification position.
  929.  
  930.     private static final boolean isNeutral[] = {
  931.         false, // "L"
  932.         false, // "R"
  933.         false, // "EN"
  934.         false, // "ES"
  935.         false, // "ET"
  936.         false, // "AN"
  937.         false, // "CS"
  938.         true,  // "B"
  939.         true,  // "S"
  940.         true,  // "WS"
  941.         true,  // "ON"
  942.         false  // "WA"
  943.     };
  944.  
  945.     private void resolveNeutralTypes(int start, int limit)
  946.     {
  947.         int i = start;
  948.         while (i < limit) {
  949.             byte tempBaseLevel = srclevels.at(i);
  950.             byte tempBaseDir = ((tempBaseLevel & 0x1) == 0) ? L : R;
  951.  
  952.             int eot = i + 1;
  953.             while (eot < limit && srclevels.at(eot) == tempBaseLevel)
  954.                 eot++;
  955.  
  956.             byte last = tempBaseDir;
  957.             // if we're starting a level boundary, the above value for last is correct.
  958.             // otherwise last depends on the direction type of the previous character.
  959.             // for for the very first pass, set 'last' correctly
  960.             if (i == start && i > 0 && srclevels.at(i-1) == tempBaseLevel) {
  961.                 switch (dirs.at(i-1)) {
  962.                     case L:
  963.                     case EN:
  964.                         last = L;
  965.                         break;
  966.  
  967.                     case R:
  968.                     case WA:
  969.                     case AN:
  970.                         last = R;
  971.                         break;
  972.                 }
  973.             }
  974.  
  975.             while (i < eot) {
  976.                 byte dir = dirs.at(i);
  977.                 if (isNeutral[dir]) { // any neutral
  978.                     int j = i + 1;
  979.                     while (j < eot && isNeutral[dir = dirs.at(j)])
  980.                         j++;
  981.  
  982.                     byte next = tempBaseDir;
  983.                     if (j < eot || (eot == limit && limit < length && srclevels.at(eot) == tempBaseLevel)) {
  984.                         if (j == eot)
  985.                             dir = dirs.at(eot);
  986.                         switch(dir) {
  987.                             case L:
  988.                             case EN:
  989.                                 next = L;
  990.                                 break;
  991.  
  992.                             case R:
  993.                             case WA:
  994.                             case AN:
  995.                                 next = R;
  996.                                 break;
  997.                         }
  998.                     }
  999.  
  1000.                     if (last != next)
  1001.                         last = tempBaseDir;
  1002.  
  1003.                     while (i < j) {
  1004.                         dirs.atPut(i, last);
  1005.                         i++;
  1006.                     }
  1007.  
  1008.                     if (i == eot)
  1009.                         break;
  1010.                 }
  1011.  
  1012.                 switch (dir) {
  1013.                     case L:
  1014.                     case EN:
  1015.                         last = L;
  1016.                         break;
  1017.  
  1018.                     case R:
  1019.                     case WA:
  1020.                     case AN:
  1021.                         last = R;
  1022.                         break;
  1023.                 }
  1024.  
  1025.                 i++;
  1026.             }
  1027.         }
  1028.     }
  1029.  
  1030.     // Mark says to not use "global direction" but instead use the resolved level.
  1031.     // EN processing is influenced by level boundaries.
  1032.     // this also processes segment and paragraph separator directions
  1033.     //
  1034.     // Implicit level processing looks at the previous position in some cases
  1035.     // involving EN.  This means that a change to that position can affect the
  1036.     // level of a following EN.  The reapply range must be expanded to
  1037.     // account for this case.
  1038.     //
  1039.     // This interprets 'end of line' in L1 to mean end of segment.  Runs of whitespace at
  1040.     // the end of the paragraph, and before a block or segment separator, are set to the
  1041.     // base level.
  1042.  
  1043.     private void resolveImplicitLevels(int start, int limit) {
  1044.         byte baselevel = (byte)(ltr ? 0 : 1);
  1045.         for (int i = start; i < limit; i++) {
  1046.             byte level = srclevels.at(i);
  1047.             byte nlevel = level;
  1048.             switch (dirs.at(i)) {
  1049.             case L: nlevel = (byte)((level + 1) & 0xe); break;
  1050.             case R: nlevel = (byte)(level | 0x1); break;
  1051.             case AN: nlevel = (byte)((level + 2) & 0xe); break;
  1052.             case WA:
  1053.             case EN:
  1054.                 if ((level & 0x1) != 0) {
  1055.                     nlevel += 1;
  1056.                 } else if (i == 0 || srclevels.at(i-1) != level) {
  1057.                     // !!!
  1058.                     nlevel += 2;
  1059.                 } else {
  1060.                     byte dir = dirs.at(i-1);
  1061.                     if (dir == EN || dir == WA) {
  1062.                         nlevel = levels.at(i-1);
  1063.                     } else if (dir != L) {
  1064.                         nlevel += 2;
  1065.                     }
  1066.                 }
  1067.                 break;
  1068.             case B:
  1069.             case S: nlevel = baselevel;
  1070.                 // scan over preceeding spaces and set them to baselevel too
  1071.                 for (int j = i - 1; j >= start && dirs.at(j) == WS; --j) {
  1072.                     levels.atPut(j, baselevel);
  1073.                 }
  1074.                 break;
  1075.             }
  1076.  
  1077.             if (nlevel < NUMLEVELS && nlevel != level) {
  1078.                 levels.atPut(i, nlevel);
  1079.             }
  1080.         }
  1081.  
  1082.         if (limit == length || dirs.at(limit) == B || dirs.at(limit) == S) {
  1083.             for (int j = limit - 1; j >= start && dirs.at(j) == WS; --j) {
  1084.                 levels.atPut(j, baselevel);
  1085.             }
  1086.         }
  1087.     }
  1088.  
  1089.     /**
  1090.      * Return a mapping of the entire bidirectional information from logical to
  1091.      * visual position.
  1092.      */
  1093.     public int[] createLogicalToVisualMap() {
  1094.         return createLogicalToVisualMap(0, length);
  1095.     }
  1096.  
  1097.     /**
  1098.      * Return a mapping of the subrange of bidirectional information from
  1099.      * logical to visual position.  For example, result[x] = y means that,
  1100.      * when only the glyphs from logical positions start to limit are
  1101.      * displayed on a line, the glyph at logical position start + x is at
  1102.      * visual position y (measuring from the left or top).
  1103.      */
  1104.     public int[] createLogicalToVisualMap(int start, int limit) {
  1105.         /*
  1106.          * !!! I'm having trouble thinking through how to generate this
  1107.          * directly, so for now let's wimp out and invert the vtl map.
  1108.          *  Too bad because this is the map TextLayout wants.
  1109.          */
  1110.  
  1111.         int[] mapping = createVisualToLogicalMap(start, limit);
  1112.         if (mapping == null) {
  1113.             return null;
  1114.         }
  1115.  
  1116.         for (int i = 0; i < mapping.length; i++) {
  1117.             mapping[i] -= start;
  1118.         }
  1119.         return GlyphSet.getInverseOrder(mapping);
  1120.     }
  1121.  
  1122.     /**
  1123.      * Return a mapping of the entire bidirectional information from visual to
  1124.      * logical position.
  1125.      */
  1126.     public int[] createVisualToLogicalMap() {
  1127.         return createVisualToLogicalMap(0, length);
  1128.     }
  1129.  
  1130.     /**
  1131.      * Return a mapping of the subrange of bidirectional information from visual
  1132.      * to logical position.  For example, result[x] = y means that, when only
  1133.      * the glyphs from logical positions start to limit are displayed on a
  1134.      * line, the glyph at visual position x (measuring from left or top) is
  1135.      * logical glyph y.
  1136.      *
  1137.      * Whitespace at the end of the range is mapped to the base level,
  1138.      * implementing the line reordering rules of the bidi algorithm.
  1139.      *
  1140.      * @param start the start of the logical range for which to generate the
  1141.      * mapping.
  1142.      * @param limit the limit of the logical range for which to generate the
  1143.      * mapping.
  1144.      */
  1145.     public int[] createVisualToLogicalMap(int start, int limit) {
  1146.         if (levels == null) {
  1147.             return null;
  1148.         }
  1149.  
  1150.         boolean canonical = true;
  1151.         for (int i = start; canonical && i < limit; i++) {
  1152.             canonical = levels.at(i) == 0;
  1153.         }
  1154.         if (canonical) {
  1155.             if (DEBUGGING) debugStream.println("*** vtl map canonical from " + start + " to " + limit);
  1156.             return null;
  1157.         }
  1158.  
  1159.         int maplen = limit - start;
  1160.         int[] mapping = new int[maplen];
  1161.  
  1162.         // find out how much trailing whitespace there is
  1163.         // first skip over runs of B and S, then over runs of WS
  1164.         int ws = 0;
  1165.         int wsi = limit - 1;
  1166.         byte d;
  1167.         for (; (wsi >= start) && ((d = dirs.at(wsi)) == B || d == S);
  1168.              --wsi)
  1169.         {
  1170.             ws++;
  1171.         }
  1172.         for (; (wsi >= start) && (dirs.at(wsi) == WS); --wsi) {
  1173.             ws++;
  1174.         }
  1175.  
  1176.         // don't process these values, we'll special case them later
  1177.         limit -= ws;
  1178.  
  1179.         int mapstart = ltr ? 0 : ws;
  1180.  
  1181.         byte lowestOddLevel = (byte)(NUMLEVELS + 1);
  1182.         byte highestLevel = 0;
  1183.  
  1184.         // initialize mapping and levels
  1185.  
  1186.         for (int i = start; i < limit; i++) {
  1187.             mapping[i - start + mapstart] = i;
  1188.  
  1189.             byte level = levels.at(i);
  1190.             if (level > highestLevel) {
  1191.                 highestLevel = level;
  1192.             }
  1193.             if (((level & 0x01) != 0) && (level < lowestOddLevel)) {
  1194.                 lowestOddLevel = level;
  1195.             }
  1196.         }
  1197.  
  1198.         while (highestLevel >= lowestOddLevel) {
  1199.             int i = start;
  1200.             for (;;) {
  1201.                 while ((i < limit) && (levels.at(i) < highestLevel)) {
  1202.                     i++;
  1203.                 }
  1204.                 int begin = i++;
  1205.  
  1206.                 if (begin == limit) {
  1207.                     break; // no more runs at this level
  1208.                 }
  1209.  
  1210.                 while ((i < limit) && (levels.at(i) >= highestLevel)) {
  1211.                     i++;
  1212.                 }
  1213.                 int end = i - 1;
  1214.  
  1215.                 begin -= start - mapstart;
  1216.                 end -= start - mapstart;
  1217.                 while (begin < end) {
  1218.                     int temp = mapping[begin];
  1219.                     mapping[begin] = mapping[end];
  1220.                     mapping[end] = temp;
  1221.                     ++begin;
  1222.                     --end;
  1223.                 }
  1224.             }
  1225.  
  1226.             // debug("after remap "+highestLevel+" "+ mappedString());
  1227.  
  1228.             --highestLevel;
  1229.         }
  1230.  
  1231.         // now let's handle the whitespace
  1232.         if (ltr) {
  1233.             for (int i = limit; ws > 0; --ws, ++i) {
  1234.                 mapping[i - start] = i;
  1235.             }
  1236.         } else {
  1237.             while (ws > 0) {
  1238.                 mapping[--ws] = limit++;
  1239.             }
  1240.         }
  1241.  
  1242.         return mapping;
  1243.     }
  1244.  
  1245.     /**
  1246.      * Return true if the base line direction for the paragraph is left to
  1247.      * right.
  1248.      */
  1249.     public boolean isDirectionLTR()  {
  1250.         return ltr;
  1251.     }
  1252.  
  1253.     /*
  1254.      * Return the level array.  If the bidi is canonical, return null.
  1255.      */
  1256.     public byte[] getLevels() {
  1257.         if (canonical) {
  1258.             return null;
  1259.         }
  1260.  
  1261.         return levels.getArray();
  1262.     }
  1263.  
  1264. /*
  1265.     public byte[] createLevels(int start, int limit)
  1266.     {
  1267.         boolean canonical = true;
  1268.         for (int i = start; canonical && i < limit; i++)
  1269.             canonical = levels.at(i) == 0;
  1270.  
  1271.         if (canonical) {
  1272.             if (DEBUGGING) debugStream.println("*** levels canonical from " + start + " to " + limit);
  1273.             return null;
  1274.         }
  1275.  
  1276.         int levlen = limit - start;
  1277.         byte[] newlevels = new byte[levlen];
  1278.         levels.writeout(start, newlevels, 0, levlen);
  1279.  
  1280.         // set trailing whitespace to base level.  Don't worry about
  1281.         // extra work if this is a lower odd level than the ideal odd
  1282.         // level for this line, this situation won't happen often.
  1283.  
  1284.         byte baseLevel = (byte)(ltr ? 0 : 1);
  1285.         for (int i = limit - 1; (i >= start) && (dirs.at(i) == WS); --i)
  1286.             newlevels[i - start] = baseLevel;
  1287.  
  1288.         return newlevels;
  1289.     }
  1290. */
  1291.     /**
  1292.      * Return true if there are any embedding or override codes in the text.
  1293.      */
  1294.     static boolean containsExplicitFormatting(CharacterIterator iter)
  1295.     {
  1296.         for (char c = iter.first(); c != CharacterIterator.DONE; c = iter.next()) {
  1297.             if ((c >= MIN_EXPLICIT_CODE) && (c <= MAX_EXPLICIT_CODE))
  1298.                 return true;
  1299.         }
  1300.  
  1301.         return false;
  1302.     }
  1303.  
  1304.     /**
  1305.      * Return true if an analysis of the text reveals a left to right run
  1306.      * direction.
  1307.      */
  1308.     static boolean defaultRunIsLeftToRight(AttributedCharacterIterator iter) {
  1309.         boolean ltr = true;
  1310.         for (char c = iter.first();
  1311.              c != CharacterIterator.DONE;
  1312.              c = iter.next()) {
  1313.             byte dir = getDirectionClass(c);
  1314.             if (dir == L || dir == R) {
  1315.                 ltr = dir == L;
  1316.                 break;
  1317.             }
  1318.         }
  1319.         return ltr;
  1320.     }
  1321.  
  1322.     //
  1323.     // debugging code. package access for tests.
  1324.     //
  1325.  
  1326.     static final char[] digits = "0123456789abcde".toCharArray();
  1327.  
  1328.     static String lvlString(byte[] lvlArray) {
  1329.         if (lvlArray == null) {
  1330.             return null;
  1331.         }
  1332.  
  1333.         StringBuffer buf = new StringBuffer(lvlArray.length);
  1334.         for (int i = 0; i < lvlArray.length; i++) {
  1335.             buf.append(digits[lvlArray[i]]);
  1336.     }
  1337.  
  1338.         return buf.toString();
  1339.     }
  1340.  
  1341.     static final char[] dircodes = "lr#,.A:bswna".toCharArray();
  1342.  
  1343.     static String dirString(byte[] dirArray) {
  1344.         if (dirArray == null) {
  1345.             return null;
  1346.         }
  1347.  
  1348.         StringBuffer buf = new StringBuffer(dirArray.length);
  1349.         for (int i = 0; i < dirArray.length; i++) {
  1350.             buf.append(dircodes[dirArray[i]]);
  1351.         }
  1352.  
  1353.         return buf.toString();
  1354.     }
  1355.  
  1356.     // output a message and the current state of the algorithm
  1357.     // text, if present, is the string the bidi is ostensibly working on
  1358.  
  1359.     void debug(String message, String text)  {
  1360.         debugStream.println(message);
  1361.         debugStream.println("length: " + length + ", ltr: " + ltr);
  1362.  
  1363.         if (text != null) {
  1364.             debugStream.println("string:  " + text);
  1365.     }
  1366.  
  1367.         byte[] temp = new byte[length];
  1368.         srcdirs.writeout(0, temp, 0, length);
  1369.         debugStream.println("srcdirs: " + dirString(temp));
  1370.  
  1371.         srclevels.writeout(0, temp, 0, length);
  1372.         debugStream.println("srclvls: " + lvlString(temp));
  1373.  
  1374.         dirs.writeout(0, temp, 0, length);
  1375.         debugStream.println("dirs:    " + dirString(temp));
  1376.  
  1377.         levels.writeout(0, temp, 0, length);
  1378.         debugStream.println("levels:  " + lvlString(temp));
  1379.  
  1380.         if (text != null) {
  1381.             String result = null;
  1382.  
  1383.             int[] vtl = createVisualToLogicalMap();
  1384.  
  1385.             if (vtl == null) {
  1386.                 result = text;
  1387.             } else {
  1388.                 StringBuffer buffer = new StringBuffer(vtl.length);
  1389.  
  1390.                 for (int i = 0; i < vtl.length; i++) {
  1391.                     char c = text.charAt(vtl[i]);
  1392.                     if ((levels.at(vtl[i]) & 0x1) != 0) {
  1393.                         buffer.append(c /* mappedChar(c) */);
  1394.                     } else {
  1395.                         buffer.append(c);
  1396.             }
  1397.                 }
  1398.  
  1399.                 result = buffer.toString();
  1400.             }
  1401.  
  1402.             debugStream.println("result:  " + result);
  1403.         }
  1404.  
  1405.         debugStream.println();
  1406.     }
  1407.  
  1408. private static final byte fgCharDirValues[] = {
  1409.     ON, ON, ON, ON, ON, ON, ON, ON, ON, S, ON,
  1410.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1411.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1412.     ON, WS, ON, ON, ET, ET, ET, L, ON, ON,
  1413.     ON, ON, ET, CS, ET, ES, ES, EN, EN, EN,
  1414.     EN, EN, EN, EN, EN, EN, EN, CS, ON, ON,
  1415.     ON, ON, ON, L, L, L, L, L, L, L,
  1416.     L, L, L, L, L, L, L, L, L, L,
  1417.     L, L, L, L, L, L, L, L, L, L,
  1418.     ON, ON, ON, ON, ON, ON, L, L, L, L,
  1419.     L, L, L, L, L, L, L, L, L, L,
  1420.     L, L, L, L, L, L, L, L, L, L,
  1421.     L, L, ON, ON, ON, ON, ON, ON, ON, ON,
  1422.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1423.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1424.     ON, ON, ON, ON, WS, ON, ET, ET, ET, ET,
  1425.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1426.     ET, ET, EN, EN, ON, ON, ON, ON, ON, EN,
  1427.     ON, ON, ON, ON, ON, ON, L, L, L, L,
  1428.     L, L, L, L, L, L, L, L, L, L,
  1429.     L, L, L, L, L, L, L, L, L, ON,
  1430.     L, L, L, L, L, L, L, L, L, L,
  1431.     L, L, L, L, L, L, L, L, L, L,
  1432.     L, L, L, L, L, L, L, L, L, L,
  1433.     L, ON, L, L, L, L, L, L, L, L,
  1434.     L, L, L, L, L, L, L, L, L, L,
  1435.     L, L, L, L, L, L, L, L, L, L,
  1436.     L, L, L, L, L, L, L, L, L, L,
  1437.     L, L, L, L, L, L, L, L, L, L,
  1438.     L, L, L, L, L, L, L, L, L, L,
  1439.     L, L, L, L, L, L, L, L, L, L,
  1440.     L, L, L, L, L, L, L, L, L, L,
  1441.     L, L, L, L, L, L, L, L, L, L,
  1442.     L, L, L, L, L, L, L, L, L, L,
  1443.     L, L, L, L, L, L, L, L, L, L,
  1444.     L, L, L, L, L, L, L, L, L, L,
  1445.     L, L, L, L, L, L, L, L, L, L,
  1446.     ON, ON, ON, ON, L, L, L, L, L, L,
  1447.     L, L, L, L, L, L, L, L, L, L,
  1448.     L, L, L, L, L, L, L, L, ON, ON,
  1449.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1450.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1451.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1452.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1453.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1454.     ON, ON, ON, ON, L, L, L, L, L, L,
  1455.     L, L, L, L, L, L, L, L, L, L,
  1456.     L, L, L, L, L, L, L, L, L, L,
  1457.     L, L, L, L, L, L, L, L, L, L,
  1458.     L, L, L, L, L, L, L, L, L, L,
  1459.     L, L, ON, ON, ON, ON, ON, ON, ON, L,
  1460.     L, L, L, L, L, L, L, L, L, L,
  1461.     L, L, L, L, L, L, L, L, L, L,
  1462.     L, L, L, L, L, L, L, L, L, L,
  1463.     L, L, L, L, L, L, L, L, L, L,
  1464.     L, L, L, L, L, L, ON, L, L, L,
  1465.     L, L, L, L, L, L, L, ON, ON, ON,
  1466.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1467.     ON, ON, ON, ON, ON, ON, ON, ON, ON, L,
  1468.     L, L, L, L, L, L, L, L, L, L,
  1469.     L, L, L, L, L, L, L, L, L, L,
  1470.     L, L, L, L, L, L, L, L, L, L,
  1471.     L, L, L, L, L, L, L, L, L, L,
  1472.     L, L, L, L, L, L, L, L, L, L,
  1473.     L, L, L, L, L, L, L, L, L, L,
  1474.     L, L, L, L, L, L, L, L, L, ON,
  1475.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1476.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1477.     ON, ON, ON, ON, ON, L, L, ON, ON, ON,
  1478.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1479.     ON, ON, ON, ON, ON, L, L, ON, ON, ON,
  1480.     ON, L, ON, ON, ON, L, ON, ON, ON, ON,
  1481.     L, L, L, L, L, L, L, ON, L, ON,
  1482.     L, L, L, L, L, L, L, L, L, L,
  1483.     L, L, L, L, L, L, L, L, L, L,
  1484.     ON, L, L, L, L, L, L, L, L, L,
  1485.     L, L, L, L, L, L, L, L, L, L,
  1486.     L, L, L, L, L, L, L, L, L, L,
  1487.     L, L, L, L, L, L, L, L, L, L,
  1488.     L, L, L, L, L, ON, L, L, L, L,
  1489.     L, L, L, ON, ON, ON, L, ON, L, ON,
  1490.     L, ON, L, ON, L, L, L, L, L, L,
  1491.     L, L, L, L, L, L, L, L, L, L,
  1492.     L, L, ON, ON, ON, ON, ON, ON, ON, ON,
  1493.     ON, ON, ON, ON, L, L, L, L, L, L,
  1494.     L, L, L, L, L, L, ON, L, L, L,
  1495.     L, L, L, L, L, L, L, L, L, L,
  1496.     L, L, L, L, L, L, L, L, L, L,
  1497.     L, L, L, L, L, L, L, L, L, L,
  1498.     L, L, L, L, L, L, L, L, L, L,
  1499.     L, L, L, L, L, L, L, L, L, L,
  1500.     L, L, L, L, L, L, L, L, L, L,
  1501.     L, L, L, ON, L, L, L, L, L, L,
  1502.     L, L, L, L, L, L, ON, L, L, L,
  1503.     L, L, L, L, L, L, L, L, L, L,
  1504.     L, L, L, L, L, L, L, L, L, L,
  1505.     L, L, L, L, L, L, L, L, L, L,
  1506.     L, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1507.     L, L, L, L, L, L, L, L, L, L,
  1508.     L, L, L, L, L, L, L, L, L, L,
  1509.     L, L, L, L, L, L, L, L, L, L,
  1510.     L, L, L, L, L, L, L, L, L, L,
  1511.     L, L, L, L, L, L, L, L, L, L,
  1512.     L, L, L, ON, ON, L, L, ON, ON, L,
  1513.     L, ON, ON, ON, L, L, L, L, L, L,
  1514.     L, L, L, L, L, L, L, L, L, L,
  1515.     L, L, L, L, L, L, L, L, L, L,
  1516.     L, L, ON, ON, L, L, L, L, L, L,
  1517.     L, L, ON, ON, L, L, ON, ON, ON, ON,
  1518.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1519.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1520.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1521.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1522.     ON, ON, ON, ON, ON, L, L, L, L, L,
  1523.     L, L, L, L, L, L, L, L, L, L,
  1524.     L, L, L, L, L, L, L, L, L, L,
  1525.     L, L, L, L, L, L, L, L, L, L,
  1526.     L, L, L, ON, ON, L, L, L, L, L,
  1527.     L, L, ON, L, L, L, L, L, L, L,
  1528.     L, L, L, L, L, L, L, L, L, L,
  1529.     L, L, L, L, L, L, L, L, L, L,
  1530.     L, L, L, L, ON, L, ON, ON, ON, ON,
  1531.     ON, ON, ON, R, R, R, R, R, R, R,
  1532.     R, R, R, R, R, R, R, R, R, R,
  1533.     ON, R, R, R, R, R, R, R, R, R,
  1534.     R, R, R, R, R, R, R, R, R, R,
  1535.     R, R, R, R, ON, R, R, R, R, R,
  1536.     R, R, R, R, R, ON, ON, ON, ON, ON,
  1537.     ON, ON, ON, ON, ON, ON, R, R, R, R,
  1538.     R, R, R, R, R, R, R, R, R, R,
  1539.     R, R, R, R, R, R, R, R, R, R,
  1540.     R, R, R, ON, ON, ON, ON, ON, R, R,
  1541.     R, R, R, ON, ON, ON, ON, ON, ON, ON,
  1542.     ON, ON, ON, ON, ON, R, ON, ON, ON, ON,
  1543.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1544.     R, ON, ON, ON, R, ON, R, R, R, R,
  1545.     R, R, R, R, R, R, R, R, R, R,
  1546.     R, R, R, R, R, R, R, R, R, R,
  1547.     R, R, ON, ON, ON, ON, ON, R, R, R,
  1548.     R, R, R, R, R, R, R, R, R, R,
  1549.     R, R, R, R, R, R, ON, ON, ON, ON,
  1550.     ON, ON, ON, ON, ON, ON, ON, ON, ON, AN,
  1551.     AN, AN, AN, AN, AN, AN, AN, AN, AN, ET,
  1552.     AN, AN, R, ON, ON, R, R, R, R, R,
  1553.     R, R, R, R, R, R, R, R, R, R,
  1554.     R, R, R, R, R, R, R, R, R, R,
  1555.     R, R, R, R, R, R, R, R, R, R,
  1556.     R, R, R, R, R, R, R, R, R, R,
  1557.     R, R, R, R, R, R, R, R, R, R,
  1558.     R, ON, ON, R, R, R, R, R, ON, R,
  1559.     R, R, R, R, R, R, R, R, R, R,
  1560.     R, R, R, R, ON, R, R, R, R, R,
  1561.     R, R, R, R, R, R, R, R, R, R,
  1562.     R, R, R, R, R, R, R, R, R, R,
  1563.     R, R, R, R, R, ON, ON, EN, EN, EN,
  1564.     EN, EN, EN, EN, EN, EN, EN, ON, ON, ON,
  1565.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1566.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1567.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1568.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1569.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1570.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1571.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1572.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1573.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1574.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1575.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1576.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1577.     ON, ON, ON, ON, ON, L, L, L, ON, L,
  1578.     L, L, L, L, L, L, L, L, L, L,
  1579.     L, L, L, L, L, L, L, L, L, L,
  1580.     L, L, L, L, L, L, L, L, L, L,
  1581.     L, L, L, L, L, L, L, L, L, L,
  1582.     L, L, L, L, L, L, L, L, L, L,
  1583.     L, L, ON, ON, L, L, L, L, L, L,
  1584.     L, L, L, L, L, L, L, L, L, L,
  1585.     L, L, ON, ON, L, L, L, L, L, ON,
  1586.     ON, ON, L, L, L, L, L, L, L, L,
  1587.     L, L, L, L, L, L, L, L, L, L,
  1588.     L, L, L, L, L, L, L, ON, ON, ON,
  1589.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1590.     ON, ON, L, L, L, ON, L, L, L, L,
  1591.     L, L, L, L, ON, ON, L, L, ON, ON,
  1592.     L, L, L, L, L, L, L, L, L, L,
  1593.     L, L, L, L, L, L, L, L, L, L,
  1594.     L, L, ON, L, L, L, L, L, L, L,
  1595.     ON, L, ON, ON, ON, L, L, L, L, ON,
  1596.     ON, L, ON, L, L, L, L, L, L, L,
  1597.     ON, ON, L, L, ON, ON, L, L, L, ON,
  1598.     ON, ON, ON, ON, ON, ON, ON, ON, L, ON,
  1599.     ON, ON, ON, L, L, ON, L, L, L, L,
  1600.     L, ON, ON, L, L, L, L, L, L, L,
  1601.     L, L, L, L, L, L, L, L, L, L,
  1602.     L, L, L, L, ON, ON, ON, ON, ON, L,
  1603.     ON, ON, L, L, L, L, L, L, ON, ON,
  1604.     ON, ON, L, L, ON, ON, L, L, L, L,
  1605.     L, L, L, L, L, L, L, L, L, L,
  1606.     L, L, L, L, L, L, L, L, ON, L,
  1607.     L, L, L, L, L, L, ON, L, L, ON,
  1608.     L, L, ON, L, L, ON, ON, L, ON, L,
  1609.     L, L, L, L, ON, ON, ON, ON, L, L,
  1610.     ON, ON, L, L, L, ON, ON, ON, ON, ON,
  1611.     ON, ON, ON, ON, ON, ON, L, L, L, L,
  1612.     ON, L, ON, ON, ON, ON, ON, ON, ON, L,
  1613.     L, L, L, L, L, L, L, L, L, L,
  1614.     L, L, L, L, ON, ON, ON, ON, ON, ON,
  1615.     ON, ON, ON, ON, ON, L, L, L, ON, L,
  1616.     L, L, L, L, L, L, ON, L, ON, L,
  1617.     L, L, ON, L, L, L, L, L, L, L,
  1618.     L, L, L, L, L, L, L, L, L, L,
  1619.     L, L, L, L, L, ON, L, L, L, L,
  1620.     L, L, L, ON, L, L, ON, L, L, L,
  1621.     L, L, ON, ON, L, L, L, L, L, L,
  1622.     L, L, L, L, ON, L, L, L, ON, L,
  1623.     L, L, ON, ON, L, ON, ON, ON, ON, ON,
  1624.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1625.     L, ON, ON, ON, ON, ON, L, L, L, L,
  1626.     L, L, L, L, L, L, ON, ON, ON, ON,
  1627.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1628.     ON, ON, L, L, L, ON, L, L, L, L,
  1629.     L, L, L, L, ON, ON, L, L, ON, ON,
  1630.     L, L, L, L, L, L, L, L, L, L,
  1631.     L, L, L, L, L, L, L, L, L, L,
  1632.     L, L, ON, L, L, L, L, L, L, L,
  1633.     ON, L, L, ON, ON, L, L, L, L, ON,
  1634.     ON, L, L, L, L, L, L, L, L, ON,
  1635.     ON, ON, L, L, ON, ON, L, L, L, ON,
  1636.     ON, ON, ON, ON, ON, ON, ON, L, L, ON,
  1637.     ON, ON, ON, L, L, ON, L, L, L, ON,
  1638.     ON, ON, ON, L, L, L, L, L, L, L,
  1639.     L, L, L, L, ON, ON, ON, ON, ON, ON,
  1640.     ON, ON, ON, ON, ON, ON, ON, ON, ON, L,
  1641.     L, ON, L, L, L, L, L, L, ON, ON,
  1642.     ON, L, L, L, ON, L, L, L, L, ON,
  1643.     ON, ON, L, L, ON, L, ON, L, L, ON,
  1644.     ON, ON, L, L, ON, ON, ON, L, L, L,
  1645.     ON, ON, ON, L, L, L, L, L, L, L,
  1646.     L, ON, L, L, L, ON, ON, ON, ON, L,
  1647.     L, L, L, L, ON, ON, ON, L, L, L,
  1648.     ON, L, L, L, L, ON, ON, ON, ON, ON,
  1649.     ON, ON, ON, ON, L, ON, ON, ON, ON, ON,
  1650.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1651.     L, L, L, L, L, L, L, L, L, L,
  1652.     L, L, ON, ON, ON, ON, ON, ON, ON, ON,
  1653.     ON, ON, ON, ON, ON, L, L, L, ON, L,
  1654.     L, L, L, L, L, L, L, ON, L, L,
  1655.     L, ON, L, L, L, L, L, L, L, L,
  1656.     L, L, L, L, L, L, L, L, L, L,
  1657.     L, L, L, L, L, ON, L, L, L, L,
  1658.     L, L, L, L, L, L, ON, L, L, L,
  1659.     L, L, ON, ON, ON, ON, L, L, L, L,
  1660.     L, L, L, ON, L, L, L, ON, L, L,
  1661.     L, L, ON, ON, ON, ON, ON, ON, ON, L,
  1662.     L, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1663.     L, L, ON, ON, ON, ON, L, L, L, L,
  1664.     L, L, L, L, L, L, ON, ON, ON, ON,
  1665.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1666.     ON, ON, L, L, ON, L, L, L, L, L,
  1667.     L, L, L, ON, L, L, L, ON, L, L,
  1668.     L, L, L, L, L, L, L, L, L, L,
  1669.     L, L, L, L, L, L, L, L, L, L,
  1670.     L, ON, L, L, L, L, L, L, L, L,
  1671.     L, L, ON, L, L, L, L, L, ON, ON,
  1672.     ON, ON, L, L, L, L, L, L, L, ON,
  1673.     L, L, L, ON, L, L, L, L, ON, ON,
  1674.     ON, ON, ON, ON, ON, L, L, ON, ON, ON,
  1675.     ON, ON, ON, ON, L, ON, L, L, ON, ON,
  1676.     ON, ON, L, L, L, L, L, L, L, L,
  1677.     L, L, ON, ON, ON, ON, ON, ON, ON, ON,
  1678.     ON, ON, ON, ON, ON, ON, ON, ON, L, L,
  1679.     ON, L, L, L, L, L, L, L, L, ON,
  1680.     L, L, L, ON, L, L, L, L, L, L,
  1681.     L, L, L, L, L, L, L, L, L, L,
  1682.     L, L, L, L, L, L, L, ON, L, L,
  1683.     L, L, L, L, L, L, L, L, L, L,
  1684.     L, L, L, L, ON, ON, ON, ON, L, L,
  1685.     L, L, L, L, ON, ON, L, L, L, ON,
  1686.     L, L, L, L, ON, ON, ON, ON, ON, ON,
  1687.     ON, ON, ON, L, ON, ON, ON, ON, ON, ON,
  1688.     ON, ON, L, L, ON, ON, ON, ON, L, L,
  1689.     L, L, L, L, L, L, L, L, ON, ON,
  1690.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1691.     ON, ON, ON, ON, L, L, L, L, L, L,
  1692.     L, L, L, L, L, L, L, L, L, L,
  1693.     L, L, L, L, L, L, L, L, L, L,
  1694.     L, L, L, L, L, L, L, L, L, L,
  1695.     L, L, L, L, L, L, L, L, L, L,
  1696.     L, L, L, L, L, L, L, L, L, L,
  1697.     L, L, ON, ON, ON, ON, L, L, L, L,
  1698.     L, L, L, L, L, L, L, L, L, L,
  1699.     L, L, L, L, L, L, L, L, L, L,
  1700.     L, L, L, L, L, ON, ON, ON, ON, ON,
  1701.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1702.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1703.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1704.     ON, L, L, ON, L, ON, ON, L, L, ON,
  1705.     L, ON, ON, L, ON, ON, ON, ON, ON, ON,
  1706.     L, L, L, L, ON, L, L, L, L, L,
  1707.     L, L, ON, L, L, L, ON, L, ON, L,
  1708.     ON, ON, L, L, ON, L, L, L, L, L,
  1709.     L, L, L, L, L, L, L, L, ON, L,
  1710.     L, L, ON, ON, L, L, L, L, L, ON,
  1711.     L, ON, L, L, L, L, L, L, ON, ON,
  1712.     L, L, L, L, L, L, L, L, L, L,
  1713.     ON, ON, L, L, ON, ON, ON, ON, ON, ON,
  1714.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1715.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1716.     ON, ON, ON, ON, ON, ON, ON, ON, L, L,
  1717.     L, L, L, L, L, L, L, L, L, L,
  1718.     L, L, L, L, L, L, L, L, L, L,
  1719.     L, L, L, L, L, L, L, L, L, L,
  1720.     L, L, L, L, L, L, L, L, L, L,
  1721.     L, L, L, L, L, L, L, L, L, L,
  1722.     L, L, L, L, L, L, L, L, L, L,
  1723.     L, L, L, L, L, L, L, L, L, L,
  1724.     ON, L, L, L, L, L, L, L, L, L,
  1725.     L, L, L, L, L, L, L, L, L, L,
  1726.     L, L, L, L, L, L, L, L, L, L,
  1727.     L, L, L, L, ON, ON, ON, ON, ON, ON,
  1728.     ON, L, L, L, L, L, L, L, L, L,
  1729.     L, L, L, L, L, L, ON, ON, ON, ON,
  1730.     L, L, L, L, L, L, ON, L, ON, L,
  1731.     L, L, L, L, L, L, L, L, L, L,
  1732.     L, L, L, L, L, L, L, L, L, L,
  1733.     ON, ON, ON, L, L, L, L, L, L, L,
  1734.     ON, L, ON, ON, ON, ON, ON, ON, ON, ON,
  1735.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1736.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1737.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1738.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1739.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1740.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1741.     ON, ON, L, L, L, L, L, L, L, L,
  1742.     L, L, L, L, L, L, L, L, L, L,
  1743.     L, L, L, L, L, L, L, L, L, L,
  1744.     L, L, L, L, L, L, L, L, L, L,
  1745.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1746.     L, L, L, L, L, L, L, L, L, L,
  1747.     L, L, L, L, L, L, L, L, L, L,
  1748.     L, L, L, L, L, L, L, L, L, L,
  1749.     L, L, L, L, L, L, L, L, L, ON,
  1750.     ON, ON, ON, L, ON, ON, ON, ON, L, L,
  1751.     L, L, L, L, L, L, L, L, L, L,
  1752.     L, L, L, L, L, L, L, L, L, L,
  1753.     L, L, L, L, L, L, L, L, L, L,
  1754.     L, L, L, L, L, L, L, L, L, L,
  1755.     L, L, L, L, L, L, L, L, L, L,
  1756.     L, L, L, L, L, L, L, L, L, L,
  1757.     L, L, L, L, L, L, L, L, L, L,
  1758.     L, L, L, L, L, L, L, L, L, L,
  1759.     L, L, L, L, L, L, L, L, ON, ON,
  1760.     ON, ON, ON, L, L, L, L, L, L, L,
  1761.     L, L, L, L, L, L, L, L, L, L,
  1762.     L, L, L, L, L, L, L, L, L, L,
  1763.     L, L, L, L, L, L, L, L, L, L,
  1764.     L, L, L, L, L, L, L, L, L, L,
  1765.     L, L, L, L, L, L, L, L, L, L,
  1766.     L, L, L, L, L, L, L, L, L, L,
  1767.     L, L, L, L, L, L, L, L, L, L,
  1768.     L, L, L, L, L, ON, ON, ON, ON, ON,
  1769.     ON, L, L, L, L, L, L, L, L, L,
  1770.     L, L, L, L, L, L, L, L, L, L,
  1771.     L, L, L, L, L, L, L, L, L, ON,
  1772.     ON, ON, ON, L, L, L, L, L, L, L,
  1773.     L, L, L, L, L, L, L, L, L, L,
  1774.     L, L, L, L, L, L, L, L, L, L,
  1775.     L, L, L, L, L, L, L, L, L, L,
  1776.     L, L, L, L, L, L, L, L, L, L,
  1777.     L, L, L, L, L, L, L, L, L, L,
  1778.     L, L, L, L, L, L, L, L, L, L,
  1779.     L, L, L, L, L, L, L, L, L, L,
  1780.     L, L, L, L, L, L, L, L, L, L,
  1781.     L, L, L, ON, ON, ON, ON, ON, ON, L,
  1782.     L, L, L, L, L, L, L, L, L, L,
  1783.     L, L, L, L, L, L, L, L, L, L,
  1784.     L, ON, ON, L, L, L, L, L, L, ON,
  1785.     ON, L, L, L, L, L, L, L, L, L,
  1786.     L, L, L, L, L, L, L, L, L, L,
  1787.     L, L, L, L, L, L, L, L, L, L,
  1788.     L, L, L, L, L, L, L, L, L, ON,
  1789.     ON, L, L, L, L, L, L, ON, ON, L,
  1790.     L, L, L, L, L, L, L, ON, L, ON,
  1791.     L, ON, L, ON, L, L, L, L, L, L,
  1792.     L, L, L, L, L, L, L, L, L, L,
  1793.     L, L, L, L, L, L, L, L, L, L,
  1794.     L, L, L, L, L, ON, ON, L, L, L,
  1795.     L, L, L, L, L, L, L, L, L, L,
  1796.     L, L, L, L, L, L, L, L, L, L,
  1797.     L, L, L, L, L, L, L, L, L, L,
  1798.     L, L, L, L, L, L, L, L, L, L,
  1799.     L, L, L, L, L, L, L, L, L, L,
  1800.     ON, L, L, L, L, L, L, L, L, L,
  1801.     L, L, L, L, L, L, ON, L, L, L,
  1802.     L, L, L, L, L, L, L, L, L, L,
  1803.     L, ON, ON, L, L, L, L, L, L, ON,
  1804.     L, L, L, L, L, L, L, L, L, L,
  1805.     L, L, L, L, L, L, L, L, L, ON,
  1806.     ON, L, L, L, ON, L, L, L, L, L,
  1807.     L, L, L, L, ON, WS, WS, WS, WS, WS,
  1808.     WS, WS, ES, WS, WS, WS, WS, ON, ON, L,
  1809.     R, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1810.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1811.     ON, ON, ON, ON, ON, B, B, ON, ON, ON,
  1812.     ON, ON, ON, ET, ET, ET, ET, ET, ON, ON,
  1813.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1814.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1815.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1816.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1817.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1818.     ON, ON, ON, ON, ON, ON, ON, EN, ON, ON,
  1819.     ON, EN, EN, EN, EN, EN, EN, ET, ET, ON,
  1820.     ON, ON, ON, EN, EN, EN, EN, EN, EN, EN,
  1821.     EN, EN, EN, ET, ET, ON, ON, ON, ON, ON,
  1822.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1823.     ON, ON, ON, ON, ON, ET, ET, ET, ET, ET,
  1824.     ET, ET, ET, ET, ET, ET, ET, ON, ON, ON,
  1825.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1826.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1827.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1828.     ON, ON, ON, L, L, L, L, L, L, L,
  1829.     L, L, L, L, L, L, L, L, L, L,
  1830.     L, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1831.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1832.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1833.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1834.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1835.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1836.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1837.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1838.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1839.     ON, ON, ON, ON, ON, ON, ON, L, L, L,
  1840.     L, L, L, L, L, L, L, L, L, L,
  1841.     L, L, L, L, L, L, L, L, L, L,
  1842.     L, L, L, L, L, L, L, L, L, ON,
  1843.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1844.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1845.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1846.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1847.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1848.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1849.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1850.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1851.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1852.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1853.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1854.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1855.     ON, ON, ON, ON, ET, ET, ON, ON, ON, ON,
  1856.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1857.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1858.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1859.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1860.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1861.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1862.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1863.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1864.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1865.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1866.     ON, ON, ON, ON, L, L, L, L, L, L,
  1867.     L, L, L, L, L, L, L, L, L, L,
  1868.     L, L, L, L, L, L, L, L, L, L,
  1869.     L, L, L, L, L, L, L, L, L, L,
  1870.     L, L, L, L, L, L, L, L, L, L,
  1871.     L, L, L, L, L, L, L, L, L, L,
  1872.     L, L, L, L, L, L, L, L, L, L,
  1873.     L, L, L, ON, ON, ON, ON, ON, WS, ON,
  1874.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1875.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1876.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1877.     ON, L, L, L, L, L, L, L, L, L,
  1878.     L, L, L, L, L, L, ON, ON, ON, ON,
  1879.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1880.     ON, ON, ON, L, L, L, L, L, L, L,
  1881.     L, L, L, L, L, L, L, L, L, L,
  1882.     L, L, L, L, L, L, L, L, L, L,
  1883.     L, L, L, L, L, L, L, L, L, L,
  1884.     L, L, L, L, L, L, L, L, L, L,
  1885.     L, L, L, L, L, L, L, L, L, L,
  1886.     L, L, L, L, L, L, ON, ON, ON, ON,
  1887.     L, L, L, L, L, L, ON, ON, L, L,
  1888.     L, L, L, L, L, L, L, L, L, L,
  1889.     L, L, L, L, L, L, L, L, L, L,
  1890.     L, L, L, L, L, L, L, L, L, L,
  1891.     L, L, L, L, L, L, L, L, L, L,
  1892.     L, L, L, L, L, L, L, L, L, L,
  1893.     L, L, L, L, L, L, L, L, L, L,
  1894.     L, L, L, L, L, L, L, L, L, L,
  1895.     L, L, L, L, L, L, L, L, L, L,
  1896.     L, L, L, L, L, L, L, L, L, L,
  1897.     L, L, ON, ON, ON, ON, ON, L, L, L,
  1898.     L, L, L, L, L, L, L, L, L, L,
  1899.     L, L, L, L, L, L, L, L, L, L,
  1900.     L, L, L, L, L, L, L, L, L, L,
  1901.     L, L, L, L, L, L, L, ON, ON, ON,
  1902.     ON, L, L, L, L, L, L, L, L, L,
  1903.     L, L, L, L, L, L, L, L, L, L,
  1904.     L, L, L, L, L, L, L, L, L, L,
  1905.     L, L, L, L, L, L, L, L, L, L,
  1906.     L, L, L, L, L, L, L, L, L, L,
  1907.     L, L, L, L, L, L, L, L, L, L,
  1908.     L, L, L, L, L, L, L, L, L, L,
  1909.     L, L, L, L, L, L, L, L, L, L,
  1910.     ON, L, L, L, L, L, L, L, L, L,
  1911.     L, L, L, L, L, L, L, ON, ON, ON,
  1912.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1913.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1914.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1915.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1916.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1917.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1918.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1919.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1920.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1921.     ON, ON, ON, L, L, L, L, L, L, L,
  1922.     L, L, L, L, L, L, L, L, L, L,
  1923.     L, L, L, L, L, L, L, L, L, L,
  1924.     L, L, ON, ON, ON, L, L, L, L, L,
  1925.     L, L, L, L, L, L, L, L, L, L,
  1926.     L, L, L, L, L, L, L, L, L, L,
  1927.     L, L, L, L, L, L, L, L, L, L,
  1928.     L, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1929.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1930.     ON, ON, ON, ON, ON, ON, ON, ON, ON, L,
  1931.     L, L, L, L, L, L, L, L, L, L,
  1932.     L, L, L, L, L, L, L, L, L, L,
  1933.     L, L, L, L, L, L, L, ON, ON, ON,
  1934.     L, L, L, L, L, L, L, L, L, L,
  1935.     L, L, L, L, L, L, L, L, L, L,
  1936.     L, L, L, L, L, L, L, L, L, L,
  1937.     L, L, L, L, L, L, L, L, L, L,
  1938.     L, L, L, L, L, L, L, L, L, ON,
  1939.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1940.     ON, ON, ON, ON, L, L, L, L, L, L,
  1941.     L, L, L, L, L, L, ON, ON, ON, ON,
  1942.     L, L, L, L, L, L, L, L, L, L,
  1943.     L, L, L, L, L, L, L, L, L, L,
  1944.     L, L, L, L, L, L, L, L, L, L,
  1945.     L, L, L, L, L, L, L, L, L, L,
  1946.     L, L, L, L, L, L, L, ON, L, L,
  1947.     L, L, L, L, L, L, L, L, L, L,
  1948.     L, L, L, L, L, L, L, L, L, L,
  1949.     L, L, L, L, L, L, L, L, L, L,
  1950.     L, L, L, L, L, L, L, L, L, L,
  1951.     L, L, L, L, L, L, L, L, L, L,
  1952.     L, L, L, L, L, L, L, L, L, L,
  1953.     L, L, L, L, L, L, L, L, L, L,
  1954.     L, L, L, L, L, L, L, L, L, L,
  1955.     L, L, L, L, L, L, L, L, L, L,
  1956.     L, L, ON, ON, L, L, L, L, L, L,
  1957.     L, L, L, L, L, L, L, L, L, L,
  1958.     L, L, L, L, L, L, L, L, L, L,
  1959.     L, L, L, L, L, ON, L, L, L, L,
  1960.     L, L, L, L, L, L, L, L, L, L,
  1961.     L, L, L, L, L, L, L, L, L, L,
  1962.     L, L, L, L, L, L, L, L, L, L,
  1963.     L, L, L, L, ON, ON, ON, ON, ON, ON,
  1964.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1965.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1966.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1967.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1968.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1969.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1970.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1971.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1972.     ON, ON, ON, ON, ON, ON, L, L, L, L,
  1973.     L, L, L, L, L, L, L, L, L, L,
  1974.     L, L, L, L, L, L, L, L, L, L,
  1975.     L, L, L, L, L, L, L, L, L, L,
  1976.     L, L, L, L, L, L, L, L, L, L,
  1977.     L, L, ON, ON, ON, ON, ON, ON, ON, ON,
  1978.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1979.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1980.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1981.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1982.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1983.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1984.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1985.     ON, ON, ON, ON, L, L, L, L, L, L,
  1986.     L, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  1987.     ON, ON, ON, L, L, L, L, L, ON, ON,
  1988.     ON, ON, ON, ON, R, R, R, R, R, R,
  1989.     R, R, R, R, R, R, R, R, R, R,
  1990.     R, R, R, R, R, R, R, R, R, ON,
  1991.     R, R, R, R, R, ON, R, ON, R, R,
  1992.     ON, R, R, ON, R, R, R, R, R, R,
  1993.     R, R, R, R, R, R, R, R, R, R,
  1994.     R, R, R, R, R, R, R, R, R, R,
  1995.     R, R, R, R, R, R, R, R, R, R,
  1996.     R, R, R, R, R, R, R, R, R, R,
  1997.     R, R, R, R, R, R, R, R, R, R,
  1998.     R, R, ON, ON, ON, ON, ON, ON, ON, ON,
  1999.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2000.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2001.     ON, ON, ON, ON, ON, R, R, R, R, R,
  2002.     R, R, R, R, R, R, R, R, R, R,
  2003.     R, R, R, R, R, R, R, R, R, R,
  2004.     R, R, R, R, R, R, R, R, R, R,
  2005.     R, R, R, R, R, R, R, R, R, R,
  2006.     R, R, R, R, R, R, R, R, R, R,
  2007.     R, R, R, R, R, R, R, R, R, R,
  2008.     R, R, R, R, R, R, R, R, R, R,
  2009.     R, R, R, R, R, R, R, R, R, R,
  2010.     R, R, R, R, R, R, R, R, R, R,
  2011.     R, R, R, R, R, R, R, R, R, R,
  2012.     R, R, R, R, R, R, R, R, R, R,
  2013.     R, R, R, R, R, R, R, R, R, R,
  2014.     R, R, R, ON, ON, ON, ON, ON, ON, ON,
  2015.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2016.     ON, R, R, R, R, R, R, R, R, R,
  2017.     R, R, R, R, R, R, R, R, R, R,
  2018.     R, R, R, R, R, R, R, R, R, R,
  2019.     R, R, R, R, R, R, R, R, R, R,
  2020.     R, R, R, R, R, R, R, R, R, ON,
  2021.     ON, R, R, R, R, R, R, R, R, R,
  2022.     R, R, R, R, R, R, R, R, R, R,
  2023.     R, R, R, R, R, R, R, R, R, R,
  2024.     R, R, R, R, R, R, R, R, R, R,
  2025.     R, R, R, R, R, R, R, R, R, R,
  2026.     R, R, R, R, R, ON, ON, ON, ON, ON,
  2027.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2028.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2029.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2030.     ON, ON, ON, ON, ON, R, R, R, R, R,
  2031.     R, R, R, R, R, R, R, ON, ON, ON,
  2032.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2033.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2034.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2035.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2036.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2037.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2038.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2039.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2040.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2041.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2042.     ON, ON, ON, ON, ON, ON, ON, ON, ON, R,
  2043.     R, R, ON, R, ON, R, R, R, R, R,
  2044.     R, R, R, R, R, ON, ON, ON, ON, ON,
  2045.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2046.     ON, EN, EN, EN, EN, EN, EN, EN, EN, EN,
  2047.     EN, ON, ON, ON, ON, ON, ON, ON, L, L,
  2048.     L, L, L, L, L, L, L, L, L, L,
  2049.     L, L, L, L, L, L, L, L, L, L,
  2050.     L, L, L, L, ON, ON, ON, ON, ON, ON,
  2051.     L, L, L, L, L, L, L, L, L, L,
  2052.     L, L, L, L, L, L, L, L, L, L,
  2053.     L, L, L, L, L, L, ON, ON, ON, ON,
  2054.     ON, ON, ON, ON, ON, ON, L, L, L, L,
  2055.     L, L, L, L, L, L, L, L, L, L,
  2056.     L, L, L, L, L, L, L, L, L, L,
  2057.     L, L, L, L, L, L, L, L, L, L,
  2058.     L, L, L, L, L, L, L, L, L, L,
  2059.     L, L, L, L, L, L, L, L, L, L,
  2060.     L, L, L, L, L, L, L, L, L, ON,
  2061.     ON, ON, L, L, L, L, L, L, ON, ON,
  2062.     L, L, L, L, L, L, ON, ON, L, L,
  2063.     L, L, L, L, ON, ON, L, L, L, ON,
  2064.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2065.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2066.     ON, ON, ON, ON, ON, ON, ON, ON, ON, ON,
  2067.     ON, ON, ON, 10
  2068.     };
  2069.  
  2070. private static final short fgCharDirIndices[] = {
  2071.     0, 123, 243, 253, 375, 462, 590, 717, 844, 965, 1087,
  2072.     1207, 1324, 1436, 1558, 1558, 1558, 1558, 1685, 1812, 1938,
  2073.     2065, 2192, 2318, 2445, 2571, 2697, 1558, 2824, 2951, 3079,
  2074.     3195, 1558, 3291, 3419, 3474, 1558, 1558, 1558, 1558, 1558,
  2075.     1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558,
  2076.     1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 243,
  2077.     3602, 3730, 3858, 3986, 4114, 4212, 4337, 4447, 1558, 4521,
  2078.     1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558,
  2079.     1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558,
  2080.     1558, 1558, 1558, 1558, 1558, 4649, 4756, 4883, 4996, 5124,
  2081.     5251, 252, 5379, 1558, 1558, 1558, 1558, 1558, 1558, 1558,
  2082.     1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558,
  2083.     1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558,
  2084.     1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558,
  2085.     1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558,
  2086.     1558, 1558, 1558, 1558, 1558, 243, 243, 243, 243, 243,
  2087.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2088.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2089.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2090.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2091.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2092.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2093.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2094.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2095.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2096.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2097.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2098.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2099.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2100.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2101.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2102.     243, 243, 243, 243, 243, 243, 243, 243, 5507, 1558,
  2103.     1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558,
  2104.     1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558, 1558,
  2105.     1558, 1558, 1558, 243, 243, 243, 243, 243, 243, 243,
  2106.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2107.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2108.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2109.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2110.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2111.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2112.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2113.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2114.     5509, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2115.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2116.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2117.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2118.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2119.     243, 243, 243, 243, 243, 243, 243, 243, 243, 243,
  2120.     243, 243, 243, 243, 243, 243, 243, 243, 243, 5637,
  2121.     1558, 5765, 5843, 5926, 5926, 5992, 6104, 6228, 5929, 6356,
  2122.     6457
  2123. };
  2124.  
  2125.     private static final CompactByteArray fgDirectionClassArray
  2126.             = new CompactByteArray(fgCharDirIndices, fgCharDirValues);
  2127. }
  2128.  
  2129. /**
  2130.  * Gap storage optimized for repeated insertion.
  2131.  */
  2132. final class GapArrayOfByte implements Cloneable {
  2133.     private byte[] array;
  2134.     private int count;
  2135.     private int gap;
  2136.  
  2137.     /** Construct a new gap array with room for count elements. */
  2138.     public GapArrayOfByte(int count) {
  2139.         array = new byte[count];
  2140.         count = count;
  2141.     }
  2142.  
  2143.     /** Construct a new gap array with the provided src data. */
  2144.     public GapArrayOfByte(byte[] src) {
  2145.         array = (byte[])src.clone();
  2146.         count = src.length;
  2147.         gap = src.length;
  2148.     }
  2149.  
  2150.     /**
  2151.      * Construct a new gap array with a subrange of the provided src data.
  2152.      */
  2153.     public GapArrayOfByte(byte[] src, int spos, int slen) {
  2154.         array = new byte[slen];
  2155.         readin(src, spos, slen, src.length, src.length);
  2156.     }
  2157.  
  2158.     /**
  2159.      * Construct a new gap array with a subrange of the provided gap array.
  2160.      */
  2161.     public GapArrayOfByte(GapArrayOfByte src, int spos, int slen) {
  2162.         array = new byte[slen];
  2163.         readin(src.array, spos, slen, src.gap, src.count);
  2164.     }
  2165.  
  2166.     /**
  2167.      * Remove gap from array and return it.  Callers should release the array
  2168.      * before subsequent calls to this object.
  2169.      */
  2170.     public byte[] getArray() {
  2171.         if (gap < count) { // can't be > count!
  2172.             int len = count - gap;
  2173.             System.arraycopy(array, array.length - len, array, gap, len);
  2174.             gap = count;
  2175.         }
  2176.  
  2177.         return array;
  2178.     }
  2179.  
  2180.     /** Deep clone the array. */
  2181.     public Object clone() {
  2182.         GapArrayOfByte result = null;
  2183.         try {
  2184.             result = (GapArrayOfByte)super.clone();
  2185.         }
  2186.         catch (CloneNotSupportedException e) {
  2187.         }
  2188.  
  2189.         result.array = (byte[])array.clone();
  2190.         return result;
  2191.     }
  2192.  
  2193.     /** Insert a single source element at pos. */
  2194.     public void insert(int pos, byte src) {
  2195.         realloc(pos, 0, 1);
  2196.         array[gap] = src;
  2197.         gap++;
  2198.         count++;
  2199.     }
  2200.  
  2201.     /** Insert slen elements at pos starting from spos in src. */
  2202.     public void insert(int pos, byte[] src, int spos, int slen) {
  2203.         realloc(pos, 0, slen);
  2204.         readin(src, spos, slen, src.length, src.length);
  2205.     }
  2206.  
  2207.     /** Insert slen elements at pos starting from spos in src. */
  2208.     public void insert(int pos, GapArrayOfByte src, int spos, int slen) {
  2209.         realloc(pos, 0, slen);
  2210.         readin(src.array, spos, slen, src.gap, src.count);
  2211.     }
  2212.  
  2213.     /** Delete len elements at pos. */
  2214.     public void delete(int pos, int len)  {
  2215.         if (pos <= gap && pos + len >= gap) {
  2216.             gap = pos;
  2217.             count -= len;
  2218.         } else {
  2219.             realloc(pos, len, 0);
  2220.         }
  2221.     }
  2222.  
  2223.     /** Replace dlen elements at dpos with slen elements from src at spos. */
  2224.     public void replace(int dpos, int dlen, byte[] src, int spos, int slen) {
  2225.         realloc(dpos, dlen, slen);
  2226.         readin(src, spos, slen, src.length, src.length);
  2227.     }
  2228.  
  2229.     /** Replace dlen elements at dpos with slen elements from src at spos. */
  2230.     public void replace(int dpos, int dlen, GapArrayOfByte src, int spos,
  2231.                         int slen) {
  2232.         realloc(dpos, dlen, slen);
  2233.         readin(src.array, spos, slen, src.gap, src.count);
  2234.     }
  2235.  
  2236.     /** Return the element at pos. */
  2237.     public byte at(int pos) {
  2238.         if (pos >= gap) {
  2239.             int delta = array.length - count;
  2240.             pos += delta;
  2241.         }
  2242.         return array[pos];
  2243.     }
  2244.  
  2245.     /** Set the element at pos to val. */
  2246.     public void atPut(int pos, byte val) {
  2247.         if (pos >= gap) {
  2248.             int delta = array.length - count;
  2249.             pos += delta;
  2250.         }
  2251.         array[pos] = val;
  2252.     }
  2253.  
  2254.     /** Copy count elements starting at pos to dest starting at dpos. */
  2255.     public void writeout(int spos, byte[] dst, int dpos, int len) {
  2256.         if (spos < gap) {
  2257.             int blen = Math.min(len, gap - spos);
  2258.             System.arraycopy(array, spos, dst, dpos, blen);
  2259.             len -= blen;
  2260.             spos += blen;
  2261.             dpos += blen;
  2262.         }
  2263.  
  2264.         if (len > 0) {
  2265.             System.arraycopy(array, spos + array.length - count, dst, dpos,
  2266.                              len);
  2267.         }
  2268.     }
  2269.  
  2270.     /**
  2271.      * Copy slen elements from gap storage src starting at spos.  Elements
  2272.      * are inserted at gap, src has a gap at sgap and a count of scnt.
  2273.      */
  2274.     private void readin(byte[] src, int spos, int slen, int sgap, int scnt) {
  2275.         count += slen;
  2276.  
  2277.         if (spos < sgap) { // copy data before gap
  2278.             int blen = Math.min(slen, sgap - spos);
  2279.             System.arraycopy(src, spos, array, gap, blen);
  2280.             gap += blen;
  2281.             slen -= blen;
  2282.         }
  2283.  
  2284.         if (slen > 0) { // copy remaining data after gap
  2285.             System.arraycopy(src, sgap + src.length - scnt, array, gap, slen);
  2286.             gap += slen;
  2287.         }
  2288.     }
  2289.  
  2290.     /**
  2291.      * Reallocate the storage to move the gap to dpos, delete dlen existing
  2292.      * elements, and reserve space for slen new elements.
  2293.      */
  2294.     private void realloc(int dpos, int dlen, int slen) {
  2295.         if (dpos > gap || dpos + dlen < gap ||
  2296.             count + slen - dlen > array.length) {
  2297.             int ncount = count + slen - dlen;
  2298.  
  2299.             byte[] newarray = array;
  2300.             if (ncount > array.length) {
  2301.                 // assume increments are small
  2302.                 newarray = new byte[ncount + 64];
  2303.  
  2304.                 int hc = Math.min(dpos, gap); // count of elements at head
  2305.                 System.arraycopy(array, 0, newarray, 0, hc);
  2306.  
  2307.                 // count of elements at tail
  2308.                 int tc = count - Math.max(dpos + dlen, gap);
  2309.                 System.arraycopy(array, array.length - tc, newarray,
  2310.                                  newarray.length - tc, tc);
  2311.             }
  2312.  
  2313.             if (dpos > gap) {
  2314.                 int space = array.length - count;
  2315.                 System.arraycopy(array, gap + space, newarray, gap, dpos - gap);
  2316.             } else {
  2317.                 int dend = dpos + dlen;
  2318.                 if (dend < gap) {
  2319.                     int nspace = newarray.length - count;
  2320.                     System.arraycopy(array, dend, newarray, dend + nspace,
  2321.                                      gap - dend);
  2322.                 }
  2323.             }
  2324.  
  2325.             array = newarray;
  2326.         }
  2327.  
  2328.         gap = dpos;
  2329.         count -= dlen;
  2330.     }
  2331. }
  2332.  
  2333.  
  2334.