Bidi


1   /*
2    * @(#)Bidi.java    1.16 03/12/19
3    *
4    * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6    */
7   
8   /*
9    * (C) Copyright IBM Corp. 1999-2003 - All Rights Reserved
10   *
11   * The original version of this source code and documentation is
12   * copyrighted and owned by IBM. These materials are provided
13   * under terms of a License Agreement between IBM and Sun.
14   * This technology is protected by multiple US and International
15   * patents. This notice and attribution to IBM may not be removed.
16   */
17  
18  package java.text;
19  
20  import java.awt.Toolkit  ;
21  import java.awt.font.TextAttribute  ;
22  import java.awt.font.NumericShaper  ;
23  import sun.text.CodePointIterator;
24  
25  /**
26   * This class implements the Unicode Bidirectional Algorithm.
27   * <p>
28   * A Bidi object provides information on the bidirectional reordering of the text
29   * used to create it.  This is required, for example, to properly display Arabic 
30   * or Hebrew text.  These languages are inherently mixed directional, as they order
31   * numbers from left-to-right while ordering most other text from right-to-left.
32   * <p>
33   * Once created, a Bidi object can be queried to see if the text it represents is
34   * all left-to-right or all right-to-left.  Such objects are very lightweight and
35   * this text is relatively easy to process.
36   * <p>
37   * If there are multiple runs of text, information about the runs can be accessed
38   * by indexing to get the start, limit, and level of a run.  The level represents
39   * both the direction and the 'nesting level' of a directional run.  Odd levels
40   * are right-to-left, while even levels are left-to-right.  So for example level
41   * 0 represents left-to-right text, while level 1 represents right-to-left text, and
42   * level 2 represents left-to-right text embedded in a right-to-left run.
43   *
44   * @since 1.4
45   */
46  public final class Bidi {
47      byte dir;
48      byte baselevel;
49      int length;
50      int[] runs;
51      int[] cws;
52  
53      static {
54      java.security.AccessController.doPrivileged(
55          new sun.security.action.LoadLibraryAction("awt"));
56      java.security.AccessController.doPrivileged(
57          new sun.security.action.LoadLibraryAction("fontmanager"));
58      }
59  
60      /** Constant indicating base direction is left-to-right. */
61      public static final int DIRECTION_LEFT_TO_RIGHT = 0;
62  
63      /** Constant indicating base direction is right-to-left. */
64      public static final int DIRECTION_RIGHT_TO_LEFT = 1;
65  
66      /** 
67       * Constant indicating that the base direction depends on the first strong
68       * directional character in the text according to the Unicode
69       * Bidirectional Algorithm.  If no strong directional character is present,
70       * the base direction is left-to-right.
71       */
72      public static final int DIRECTION_DEFAULT_LEFT_TO_RIGHT = -2;
73  
74      /** 
75       * Constant indicating that the base direction depends on the first strong
76       * directional character in the text according to the Unicode
77       * Bidirectional Algorithm.  If no strong directional character is present,
78       * the base direction is right-to-left.
79       */
80      public static final int DIRECTION_DEFAULT_RIGHT_TO_LEFT = -1;
81  
82      private static final int DIR_MIXED = 2;
83  
84      /**
85       * Create Bidi from the given paragraph of text and base direction.
86       * @param paragraph a paragraph of text
87       * @param flags a collection of flags that control the algorithm.  The
88       * algorithm understands the flags DIRECTION_LEFT_TO_RIGHT, DIRECTION_RIGHT_TO_LEFT,
89       * DIRECTION_DEFAULT_LEFT_TO_RIGHT, and DIRECTION_DEFAULT_RIGHT_TO_LEFT.
90       * Other values are reserved.
91       */
92      public Bidi(String   paragraph, int flags) {
93          if (paragraph == null) {
94              throw new IllegalArgumentException  ("paragraph is null");
95          }
96  
97          nativeBidiChars(this, paragraph.toCharArray(), 0, null, 0, paragraph.length(), flags);
98      }
99  
100     /**
101      * Create Bidi from the given paragraph of text.
102      * <p>
103      * The RUN_DIRECTION attribute in the text, if present, determines the base
104      * direction (left-to-right or right-to-left).  If not present, the base
105      * direction is computes using the Unicode Bidirectional Algorithm, defaulting to left-to-right
106      * if there are no strong directional characters in the text.  This attribute, if
107      * present, must be applied to all the text in the paragraph.
108      * <p>
109      * The BIDI_EMBEDDING attribute in the text, if present, represents embedding level
110      * information.  Negative values from -1 to -62 indicate overrides at the absolute value
111      * of the level.  Positive values from 1 to 62 indicate embeddings.  Where values are
112      * zero or not defined, the base embedding level as determined by the base direction
113      * is assumed.
114      * <p>
115      * The NUMERIC_SHAPING attribute in the text, if present, converts European digits to
116      * other decimal digits before running the bidi algorithm.  This attribute, if present,
117      * must be applied to all the text in the paragraph.
118      *
119      * @param paragraph a paragraph of text with optional character and paragraph attribute information
120      *
121      * @see TextAttribute#BIDI_EMBEDDING
122      * @see TextAttribute#NUMERIC_SHAPING
123      * @see TextAttribute#RUN_DIRECTION
124      */
125     public Bidi(AttributedCharacterIterator   paragraph) {
126         if (paragraph == null) {
127             throw new IllegalArgumentException  ("paragraph is null");
128         }
129 
130         int flags = DIRECTION_DEFAULT_LEFT_TO_RIGHT;
131         byte[] embeddings = null;
132 
133         int start = paragraph.getBeginIndex();
134         int limit = paragraph.getEndIndex();
135         int length = limit - start;
136         int n = 0;
137         char[] text = new char[length];
138         for (char c = paragraph.first(); c != paragraph.DONE; c = paragraph.next()) {
139             text[n++] = c;
140         }
141 
142         paragraph.first();
143         try {
144             Boolean   runDirection = (Boolean  )paragraph.getAttribute(TextAttribute.RUN_DIRECTION);
145             if (runDirection != null) {
146                 if (TextAttribute.RUN_DIRECTION_LTR.equals(runDirection)) {
147                     flags = DIRECTION_LEFT_TO_RIGHT; // clears default setting
148                 } else {
149                     flags = DIRECTION_RIGHT_TO_LEFT;
150                 }
151             }
152         }
153         catch (ClassCastException   e) {
154         }
155 
156     try {
157         NumericShaper   shaper = (NumericShaper  )paragraph.getAttribute(TextAttribute.NUMERIC_SHAPING);
158         if (shaper != null) {
159         shaper.shape(text, 0, text.length);
160         }
161     }
162     catch (ClassCastException   e) {
163     }
164 
165         int pos = start;
166         do {
167             paragraph.setIndex(pos);
168             Object   embeddingLevel = paragraph.getAttribute(TextAttribute.BIDI_EMBEDDING);
169             int newpos = paragraph.getRunLimit(TextAttribute.BIDI_EMBEDDING);
170 
171             if (embeddingLevel != null) {
172                 try {
173                     int intLevel = ((Integer  )embeddingLevel).intValue();
174                     if (intLevel >= -61 && intLevel < 61) {
175                         byte level = (byte)(intLevel < 0 ? (-intLevel | 0x80) : intLevel);
176                         if (embeddings == null) {
177                             embeddings = new byte[length];
178                         }
179                         for (int i = pos - start; i < newpos - start; ++i) {
180                             embeddings[i] = level;
181                         }
182                     }
183                 }
184         catch (ClassCastException   e) {
185         }
186             }
187             pos = newpos;
188         } while (pos < limit);
189 
190         nativeBidiChars(this, text, 0, embeddings, 0, text.length, flags);
191     }
192         
193     /**
194      * Create Bidi from the given text, embedding, and direction information.
195      * The embeddings array may be null.  If present, the values represent embedding level
196      * information.  Negative values from -1 to -61 indicate overrides at the absolute value
197      * of the level.  Positive values from 1 to 61 indicate embeddings.  Where values are
198      * zero, the base embedding level as determined by the base direction is assumed.
199      * @param text an array containing the paragraph of text to process.
200      * @param textStart the index into the text array of the start of the paragraph.
201      * @param embeddings an array containing embedding values for each character in the paragraph.
202      * This can be null, in which case it is assumed that there is no external embedding information.
203      * @param embStart the index into the embedding array of the start of the paragraph.
204      * @param paragraphLength the length of the paragraph in the text and embeddings arrays.
205      * @param flags a collection of flags that control the algorithm.  The
206      * algorithm understands the flags DIRECTION_LEFT_TO_RIGHT, DIRECTION_RIGHT_TO_LEFT,
207      * DIRECTION_DEFAULT_LEFT_TO_RIGHT, and DIRECTION_DEFAULT_RIGHT_TO_LEFT.
208      * Other values are reserved.
209      */
210     public Bidi(char[] text, int textStart, byte[] embeddings, int embStart, int paragraphLength, int flags) {
211         if (text == null) {
212             throw new IllegalArgumentException  ("text is null");
213         }
214         if (paragraphLength < 0) {
215             throw new IllegalArgumentException  ("bad length: " + paragraphLength);
216         }
217         if (textStart < 0 || paragraphLength > text.length - textStart) {
218             throw new IllegalArgumentException  ("bad range: " + textStart + 
219                                                " length: " + paragraphLength + 
220                                                " for text of length: " + text.length);
221         }
222         if (embeddings != null && (embStart < 0 || paragraphLength > embeddings.length - embStart)) {
223             throw new IllegalArgumentException  ("bad range: " + embStart + 
224                                                " length: " + paragraphLength + 
225                                                " for embeddings of length: " + text.length);
226         }
227 
228     if (embeddings != null) {
229         // native uses high bit to indicate override, not negative value, sigh
230 
231         for (int i = embStart, embLimit = embStart + paragraphLength; i < embLimit; ++i) {
232         if (embeddings[i] < 0) {
233             byte[] temp = new byte[paragraphLength];
234             System.arraycopy(embeddings, embStart, temp, 0, paragraphLength);
235 
236             for (i -= embStart; i < paragraphLength; ++i) {
237             if (temp[i] < 0) {
238                 temp[i] = (byte)(-temp[i] | 0x80);
239             }
240             }
241 
242             embeddings = temp;
243             embStart = 0;
244             break;
245         }
246         }
247     }
248 
249         nativeBidiChars(this, text, textStart, embeddings, embStart, paragraphLength, flags);
250     }
251 
252     /**
253      * Private constructor used by line bidi.
254      */
255     private Bidi(int dir, int baseLevel, int length, int[] data, int[] cws) {
256         reset(dir, baseLevel, length, data, cws);
257     }
258 
259     /**
260      * Private mutator used by native code.
261      */
262     private void reset(int dir, int baselevel, int length, int[] data, int[] cws) {
263         this.dir = (byte)dir;
264         this.baselevel = (byte)baselevel;
265         this.length = length;
266         this.runs = data;
267         this.cws = cws;
268     }
269 
270     /**
271      * Create a Bidi object representing the bidi information on a line of text within
272      * the paragraph represented by the current Bidi.  This call is not required if the
273      * entire paragraph fits on one line.
274      * @param lineStart the offset from the start of the paragraph to the start of the line.
275      * @param lineLimit the offset from the start of the paragraph to the limit of the line.
276      */
277     public Bidi   createLineBidi(int lineStart, int lineLimit) {
278     if (lineStart == 0 && lineLimit == length) {
279         return this;
280     }
281 
282     int lineLength = lineLimit - lineStart;
283         if (lineStart < 0 ||
284             lineLimit < lineStart ||
285             lineLimit > length) {
286             throw new IllegalArgumentException  ("range " + lineStart + 
287                                                " to " + lineLimit + 
288                                                " is invalid for paragraph of length " + length);
289         }
290 
291         if (runs == null) {
292             return new Bidi  (dir, baselevel, lineLength, null, null);
293         } else {
294             int cwspos = -1;
295             int[] ncws = null;
296             if (cws != null) {
297                 int cwss = 0;
298                 int cwsl = cws.length;
299                 while (cwss < cwsl) {
300                     if (cws[cwss] >= lineStart) {
301                         cwsl = cwss;
302                         while (cwsl < cws.length && cws[cwsl] < lineLimit) {
303                             cwsl++;
304                         }
305                         int ll = lineLimit-1;
306                         while (cwsl > cwss && cws[cwsl-1] == ll) {
307                             cwspos = ll; // record start of counter-directional whitespace
308                             --cwsl;
309                             --ll;
310                         }
311                         
312             if (cwspos == lineStart) { // entire line is cws, so ignore
313                 return new Bidi  (dir, baselevel, lineLength, null, null);
314             }
315 
316                         int ncwslen = cwsl - cwss;
317                         if (ncwslen > 0) {
318                             ncws = new int[ncwslen];
319                             for (int i = 0; i < ncwslen; ++i) {
320                                 ncws[i] = cws[cwss+i] - lineStart;
321                             }
322                         }
323                         break;
324                     }
325                     ++cwss;
326                 }
327             }
328 
329             int[] nruns = null;
330             int nlevel = baselevel;
331             int limit = cwspos == -1 ? lineLimit : cwspos;
332             int rs = 0;
333             int rl = runs.length;
334             int ndir = dir;
335             for (; rs < runs.length; rs += 2) {
336                 if (runs[rs] > lineStart) {
337                     rl = rs;
338                     while (rl < runs.length && runs[rl] < limit) {
339                         rl += 2;
340                     }
341                     if ((rl > rs) || (runs[rs+1] != baselevel)) {
342                         rl += 2;
343 
344                         if (cwspos != -1 && rl > rs && runs[rl-1] != baselevel) { // add level for cws
345                             nruns = new int[rl - rs + 2];
346                             nruns[rl - rs] = lineLength;
347                             nruns[rl - rs + 1] = baselevel;
348                         } else {
349                             limit = lineLimit;
350                             nruns = new int[rl - rs];
351                         }
352 
353                         int n = 0;
354                         for (int i = rs; i < rl; i += 2) {
355                             nruns[n++] = runs[i] - lineStart;
356                             nruns[n++] = runs[i+1];
357                         }
358                         nruns[n-2] = limit - lineStart;
359                     } else {
360                         ndir = (runs[rs+1] & 0x1) == 0 ? DIRECTION_LEFT_TO_RIGHT : DIRECTION_RIGHT_TO_LEFT;
361                     }
362                     break;
363                 }
364             }
365 
366             return new Bidi  (ndir, baselevel, lineLength, nruns, ncws);
367         }
368     }
369 
370     /**
371      * Return true if the line is not left-to-right or right-to-left.  This means it either has mixed runs of left-to-right 
372      * and right-to-left text, or the base direction differs from the direction of the only run of text.
373      * @return true if the line is not left-to-right or right-to-left.
374      */
375     public boolean isMixed() {
376         return dir == DIR_MIXED;
377     }
378 
379     /**
380      * Return true if the line is all left-to-right text and the base direction is left-to-right.
381      * @return true if the line is all left-to-right text and the base direction is left-to-right
382      */
383     public boolean isLeftToRight() {
384         return dir == DIRECTION_LEFT_TO_RIGHT;
385     }
386 
387     /**
388      * Return true if the line is all right-to-left text, and the base direction is right-to-left.
389      * @return true if the line is all right-to-left text, and the base direction is right-to-left
390      */
391     public boolean isRightToLeft() {
392         return dir == DIRECTION_RIGHT_TO_LEFT;
393     }
394 
395     /**
396      * Return the length of text in the line.
397      * @return the length of text in the line
398      */
399     public int getLength() {
400         return length;
401     }
402 
403     /**
404      * Return true if the base direction is left-to-right.
405      * @return true if the base direction is left-to-right
406      */
407     public boolean baseIsLeftToRight() {
408         return (baselevel & 0x1) == 0;
409     }
410 
411     /** 
412      * Return the base level (0 if left-to-right, 1 if right-to-left).
413      * @return the base level
414      */
415     public int getBaseLevel() {
416       return baselevel;
417     }
418 
419     /**
420      * Return the resolved level of the character at offset.  If offset is <0 or >=
421      * the length of the line, return the base direction level.
422      * @param offset the index of the character for which to return the level
423      * @return the resolved level of the character at offset 
424      */
425     public int getLevelAt(int offset) {
426         if (runs == null || offset < 0 || offset >= length) {
427             return baselevel;
428         } else {
429             int i = 0;
430             do {
431                 if (offset < runs[i]) {
432                     return runs[i+1];
433                 }
434                 i += 2;
435             } while (true);
436         }
437     }
438 
439     /**
440      * Return the number of level runs.
441      * @return the number of level runs
442      */
443     public int getRunCount() {
444         return runs == null ? 1 : runs.length / 2;
445     }
446 
447     /**
448      * Return the level of the nth logical run in this line.
449      * @param run the index of the run, between 0 and <code>getRunCount()</code>
450      * @return the level of the run
451      */
452     public int getRunLevel(int run) {
453         return runs == null ? baselevel : runs[run * 2 + 1];
454     }
455 
456     /**
457      * Return the index of the character at the start of the nth logical run in this line, as 
458      * an offset from the start of the line.
459      * @param run the index of the run, between 0 and <code>getRunCount()</code>
460      * @return the start of the run
461      */
462     public int getRunStart(int run) {
463         return (runs == null || run == 0) ? 0 : runs[run * 2 - 2];
464     }
465 
466     /**
467      * Return the index of the character past the end of the nth logical run in this line, as 
468      * an offset from the start of the line.  For example, this will return the length
469      * of the line for the last run on the line.
470      * @param run the index of the run, between 0 and <code>getRunCount()</code>
471      * @return limit the limit of the run
472      */
473     public int getRunLimit(int run) {
474         return runs == null ? length : runs[run * 2];
475     }
476 
477     /**
478      * Return true if the specified text requires bidi analysis.  If this returns false,
479      * the text will display left-to-right.  Clients can then avoid constructing a Bidi object.
480      * Text in the Arabic Presentation Forms area of Unicode is presumed to already be shaped
481      * and ordered for display, and so will not cause this function to return true.
482      *
483      * @param text the text containing the characters to test
484      * @param start the start of the range of characters to test
485      * @param limit the limit of the range of characters to test
486      * @return true if the range of characters requires bidi analysis
487      */
488     public static boolean requiresBidi(char[] text, int start, int limit) {
489     CodePointIterator cpi = CodePointIterator.create(text, start, limit);
490     for (int cp = cpi.next(); cp != CodePointIterator.DONE; cp = cpi.next()) {
491         if (cp > 0x0590) {
492         int dc = nativeGetDirectionCode(cp);
493         if ((RMASK & (1 << dc)) != 0) {
494             return true;
495         }
496         }
497     }
498     return false;
499     }
500 
501     /**
502      * Reorder the objects in the array into visual order based on their levels.
503      * This is a utility function to use when you have a collection of objects
504      * representing runs of text in logical order, each run containing text
505      * at a single level.  The elements at <code>index</code> from
506      * <code>objectStart</code> up to <code>objectStart + count</code> 
507      * in the objects array will be reordered into visual order assuming
508      * each run of text has the level indicated by the corresponding element 
509      * in the levels array (at <code>index - objectStart + levelStart</code>).
510      *
511      * @param levels an array representing the bidi level of each object
512      * @param levelStart the start position in the levels array
513      * @param objects the array of objects to be reordered into visual order
514      * @param objectStart the start position in the objects array
515      * @param count the number of objects to reorder
516      */
517     public static void reorderVisually(byte[] levels, int levelStart, Object  [] objects, int objectStart, int count) {
518 
519     if (count < 0) {
520         throw new IllegalArgumentException  ("count " + count + " must be >= 0");
521     }
522     if (levelStart < 0 || levelStart + count > levels.length) {
523         throw new IllegalArgumentException  ("levelStart " + levelStart + " and count " + count +
524                            " out of range [0, " + levels.length + "]");
525     }
526     if (objectStart < 0 || objectStart + count > objects.length) {
527         throw new IllegalArgumentException  ("objectStart " + objectStart + " and count " + count +
528                            " out of range [0, " + objects.length + "]");
529     }
530     
531         byte lowestOddLevel = (byte)(NUMLEVELS + 1);
532         byte highestLevel = 0;
533 
534         // initialize mapping and levels
535 
536     int levelLimit = levelStart + count;
537         for (int i = levelStart; i < levelLimit; i++) {
538             byte level = levels[i];
539             if (level > highestLevel) {
540                 highestLevel = level;
541             }
542 
543             if ((level & 0x01) != 0 && level < lowestOddLevel) {
544                 lowestOddLevel = level;
545             }
546         }
547 
548     int delta = objectStart - levelStart;
549 
550         while (highestLevel >= lowestOddLevel) {
551             int i = levelStart;
552 
553             for (;;) {
554                 while (i < levelLimit && levels[i] < highestLevel) {
555                     i++;
556                 }
557                 int begin = i++;
558 
559                 if (begin == levelLimit) {
560                     break; // no more runs at this level
561                 }
562 
563                 while (i < levelLimit && levels[i] >= highestLevel) {
564                     i++;
565                 }
566                 int end = i - 1;
567 
568         begin += delta;
569         end += delta;
570                 while (begin < end) {
571                     Object   temp = objects[begin];
572                     objects[begin] = objects[end];
573                     objects[end] = temp;
574                     ++begin;
575                     --end;
576                 }
577             }
578 
579             --highestLevel;
580         }
581     }
582 
583     private static final char NUMLEVELS = 62;
584 
585     private static final int RMASK = 
586     (1 << 1 /* U_RIGHT_TO_LEFT */) |
587     (1 << 5 /* U_ARABIC_NUMBER */) |
588     (1 << 13 /* U_RIGHT_TO_LEFT_ARABIC */) |
589     (1 << 14 /* U_RIGHT_TO_LEFT_EMBEDDING */) |
590     (1 << 15 /* U_RIGHT_TO_LEFT_OVERRIDE */);
591 
592     /** Access native bidi implementation. */
593     private static native int nativeGetDirectionCode(int cp);
594 
595     /** Access native bidi implementation. */
596     private static synchronized native void nativeBidiChars(Bidi   bidi, char[] text, int textStart,
597                                                             byte[] embeddings, int embeddingStart,
598                                                             int length, int flags);
599 
600     /**
601      * Display the bidi internal state, used in debugging.
602      */
603     public String   toString() {
604     StringBuffer   buf = new StringBuffer  (super.toString());
605     buf.append("[dir: " + dir);
606     buf.append(" baselevel: " + baselevel);
607     buf.append(" length: " + length);
608     if (runs == null) {
609         buf.append(" runs: null");
610     } else {
611         buf.append(" runs: [");
612         for (int i = 0; i < runs.length; i += 2) {
613         if (i != 0) {
614             buf.append(' ');
615         }
616         buf.append(runs[i]); // limit
617         buf.append('/');
618         buf.append(runs[i+1]); // level
619         }
620         buf.append(']');
621     }
622     if (cws == null) {
623         buf.append(" cws: null");
624     } else {
625         buf.append(" cws: [");
626         for (int i = 0; i < cws.length; ++i) {
627         if (i != 0) {
628             buf.append(' ');
629         }
630         buf.append(Integer.toHexString(cws[i]));
631         }
632         buf.append(']');
633     }
634     buf.append(']');
635 
636     return buf.toString();
637     }
638 }
639 
640
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags