001    /* TextLayout.java --
002       Copyright (C) 2006  Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    
039    package java.awt.font;
040    
041    import gnu.java.lang.CPStringBuilder;
042    
043    import java.awt.Font;
044    import java.awt.Graphics2D;
045    import java.awt.Shape;
046    import java.awt.geom.AffineTransform;
047    import java.awt.geom.Line2D;
048    import java.awt.geom.Rectangle2D;
049    import java.awt.geom.GeneralPath;
050    import java.awt.geom.Point2D;
051    import java.text.CharacterIterator;
052    import java.text.AttributedCharacterIterator;
053    import java.text.Bidi;
054    import java.util.ArrayList;
055    import java.util.Map;
056    
057    /**
058     * @author Sven de Marothy
059     */
060    public final class TextLayout implements Cloneable
061    {
062      /**
063       * Holds the layout data that belongs to one run of characters.
064       */
065      private class Run
066      {
067        /**
068         * The actual glyph vector.
069         */
070        GlyphVector glyphVector;
071    
072        /**
073         * The font for this text run.
074         */
075        Font font;
076    
077        /**
078         * The start of the run.
079         */
080        int runStart;
081    
082        /**
083         * The end of the run.
084         */
085        int runEnd;
086    
087        /**
088         * The layout location of the beginning of the run.
089         */
090        float location;
091    
092        /**
093         * Initializes the Run instance.
094         *
095         * @param gv the glyph vector
096         * @param start the start index of the run
097         * @param end the end index of the run
098         */
099        Run(GlyphVector gv, Font f, int start, int end)
100        {
101          glyphVector = gv;
102          font = f;
103          runStart = start;
104          runEnd = end;
105        }
106    
107        /**
108         * Returns <code>true</code> when this run is left to right,
109         * <code>false</code> otherwise.
110         *
111         * @return <code>true</code> when this run is left to right,
112         *         <code>false</code> otherwise
113         */
114        boolean isLeftToRight()
115        {
116          return (glyphVector.getLayoutFlags() & GlyphVector.FLAG_RUN_RTL) == 0;
117        }
118      }
119    
120      /**
121       * The laid out character runs.
122       */
123      private Run[] runs;
124    
125      private FontRenderContext frc;
126      private char[] string;
127      private int offset;
128      private int length;
129      private Rectangle2D boundsCache;
130      private LineMetrics lm;
131    
132      /**
133       * The total advance of this text layout. This is cache for maximum
134       * performance.
135       */
136      private float totalAdvance = -1F;
137      
138      /**
139       * The cached natural bounds.
140       */
141      private Rectangle2D naturalBounds;
142    
143      /**
144       * Character indices.
145       * Fixt index is the glyphvector, second index is the (first) glyph.
146       */
147      private int[][] charIndices;
148    
149      /**
150       * Base directionality, determined from the first char.
151       */
152      private boolean leftToRight;
153    
154      /**
155       * Whether this layout contains whitespace or not.
156       */
157      private boolean hasWhitespace = false;
158    
159      /**
160       * The {@link Bidi} object that is used for reordering and by
161       * {@link #getCharacterLevel(int)}.
162       */
163      private Bidi bidi;
164    
165      /**
166       * Mpas the logical position of each individual character in the original
167       * string to its visual position.
168       */
169      private int[] logicalToVisual;
170    
171      /**
172       * Maps visual positions of a character to its logical position
173       * in the original string.
174       */
175      private int[] visualToLogical;
176    
177      /**
178       * The cached hashCode.
179       */
180      private int hash;
181    
182      /**
183       * The default caret policy.
184       */
185      public static final TextLayout.CaretPolicy DEFAULT_CARET_POLICY =
186        new CaretPolicy();
187    
188      /**
189       * Constructs a TextLayout.
190       */
191      public TextLayout (String str, Font font, FontRenderContext frc) 
192      {
193        this.frc = frc;
194        string = str.toCharArray();
195        offset = 0;
196        length = this.string.length;
197        lm = font.getLineMetrics(this.string, offset, length, frc);
198    
199        // Get base direction and whitespace info
200        getStringProperties();
201    
202        if (Bidi.requiresBidi(string, offset, offset + length))
203          {
204            bidi = new Bidi(str, leftToRight ? Bidi.DIRECTION_LEFT_TO_RIGHT
205                                             : Bidi.DIRECTION_RIGHT_TO_LEFT );
206            int rc = bidi.getRunCount();
207            byte[] table = new byte[ rc ];
208            for(int i = 0; i < table.length; i++)
209              table[i] = (byte)bidi.getRunLevel(i);
210    
211            runs = new Run[rc];
212            for(int i = 0; i < rc; i++)
213              {
214                int start = bidi.getRunStart(i);
215                int end = bidi.getRunLimit(i);
216                if(start != end) // no empty runs.
217                  {
218                    GlyphVector gv = font.layoutGlyphVector(frc,
219                                                            string, start, end,
220                               ((table[i] & 1) == 0) ? Font.LAYOUT_LEFT_TO_RIGHT
221                                                     : Font.LAYOUT_RIGHT_TO_LEFT );
222                    runs[i] = new Run(gv, font, start, end);
223                  }
224              }
225            Bidi.reorderVisually( table, 0, runs, 0, runs.length );
226            // Clean up null runs.
227            ArrayList cleaned = new ArrayList(rc);
228            for (int i = 0; i < rc; i++)
229              {
230                if (runs[i] != null)
231                  cleaned.add(runs[i]);
232              }
233            runs = new Run[cleaned.size()];
234            runs = (Run[]) cleaned.toArray(runs);
235          }
236        else
237          {
238            GlyphVector gv = font.layoutGlyphVector( frc, string, offset, length,
239                                         leftToRight ? Font.LAYOUT_LEFT_TO_RIGHT
240                                                     : Font.LAYOUT_RIGHT_TO_LEFT );
241            Run run = new Run(gv, font, 0, length);
242            runs = new Run[]{ run };
243          }
244        setCharIndices();
245        setupMappings();
246        layoutRuns();
247      }
248    
249      public TextLayout (String string,
250                         Map<? extends AttributedCharacterIterator.Attribute, ?> attributes,
251                         FontRenderContext frc)  
252      {
253        this( string, new Font( attributes ), frc );
254      }
255    
256      public TextLayout (AttributedCharacterIterator text, FontRenderContext frc)
257      {
258        // FIXME: Very rudimentary.
259        this(getText(text), getFont(text), frc);
260      }
261    
262      /**
263       * Package-private constructor to make a textlayout from an existing one.
264       * This is used by TextMeasurer for returning sub-layouts, and it 
265       * saves a lot of time in not having to relayout the text.
266       */
267      TextLayout(TextLayout t, int startIndex, int endIndex)
268      {
269        frc = t.frc;
270        boundsCache = null;
271        lm = t.lm;
272        leftToRight = t.leftToRight;
273    
274        if( endIndex > t.getCharacterCount() )
275          endIndex = t.getCharacterCount();
276        string = t.string;
277        offset = startIndex + offset;
278        length = endIndex - startIndex;
279    
280        int startingRun = t.charIndices[startIndex][0];
281        int nRuns = 1 + t.charIndices[endIndex - 1][0] - startingRun;
282    
283        runs = new Run[nRuns];
284        for( int i = 0; i < nRuns; i++ )
285          {
286            Run run = t.runs[i + startingRun];
287            GlyphVector gv = run.glyphVector;
288            Font font = run.font;
289            // Copy only the relevant parts of the first and last runs.
290            int beginGlyphIndex = (i > 0) ? 0 : t.charIndices[startIndex][1];
291            int numEntries = ( i < nRuns - 1) ? gv.getNumGlyphs() : 
292              1 + t.charIndices[endIndex - 1][1] - beginGlyphIndex;
293            
294            int[] codes = gv.getGlyphCodes(beginGlyphIndex, numEntries, null);
295            gv = font.createGlyphVector(frc, codes);
296            runs[i] = new Run(gv, font, run.runStart - startIndex,
297                              run.runEnd - startIndex);
298          }
299        runs[nRuns - 1].runEnd = endIndex - 1;
300    
301        setCharIndices();
302        setupMappings();
303        determineWhiteSpace();
304        layoutRuns();
305      }
306    
307      private void setCharIndices()
308      {
309        charIndices = new int[ getCharacterCount() ][2];
310        int i = 0;
311        int currentChar = 0;
312        for(int run = 0; run < runs.length; run++)
313          {
314            currentChar = -1;
315            Run current = runs[run];
316            GlyphVector gv = current.glyphVector;
317            for( int gi = 0; gi < gv.getNumGlyphs(); gi++)
318              {
319                if( gv.getGlyphCharIndex( gi ) != currentChar )
320                  {
321                    charIndices[ i ][0] = run;
322                    charIndices[ i ][1] = gi;
323                    currentChar = gv.getGlyphCharIndex( gi );
324                    i++;
325                  }
326              }
327          }
328      }
329    
330      /**
331       * Initializes the logicalToVisual and visualToLogial maps.
332       */
333      private void setupMappings()
334      {
335        int numChars = getCharacterCount();
336        logicalToVisual = new int[numChars];
337        visualToLogical = new int[numChars];
338        int lIndex = 0;
339        int vIndex = 0;
340        // We scan the runs in visual order and set the mappings accordingly.
341        for (int i = 0; i < runs.length; i++)
342          {
343            Run run = runs[i];
344            if (run.isLeftToRight())
345              {
346                for (lIndex = run.runStart; lIndex < run.runEnd; lIndex++)
347                  {
348                    logicalToVisual[lIndex] = vIndex;
349                    visualToLogical[vIndex] = lIndex;
350                    vIndex++;
351                  }
352              }
353            else
354              {
355                for (lIndex = run.runEnd - 1; lIndex >= run.runStart; lIndex--)
356                  {
357                    logicalToVisual[lIndex] = vIndex;
358                    visualToLogical[vIndex] = lIndex;
359                    vIndex++;
360                  }
361              }
362          }
363      }
364    
365      private static String getText(AttributedCharacterIterator iter)
366      {
367        CPStringBuilder sb = new CPStringBuilder();
368        int idx = iter.getIndex();
369        for(char c = iter.first(); c != CharacterIterator.DONE; c = iter.next()) 
370          sb.append(c);
371        iter.setIndex( idx );
372        return sb.toString();
373      }
374    
375      private static Font getFont(AttributedCharacterIterator iter)
376      {
377        Font f = (Font)iter.getAttribute(TextAttribute.FONT);
378        if( f == null )
379          {
380            int size;
381            Float i = (Float)iter.getAttribute(TextAttribute.SIZE);
382            if( i != null )
383              size = (int)i.floatValue();
384            else
385              size = 14;
386            f = new Font("Dialog", Font.PLAIN, size );
387          }
388        return f;
389      }
390    
391      /**
392       * Scan the character run for the first strongly directional character,
393       * which in turn defines the base directionality of the whole layout.
394       */
395      private void getStringProperties()
396      {
397        boolean gotDirection = false;
398        int i = offset;
399        int endOffs = offset + length;
400        leftToRight = true;
401        while( i < endOffs && !gotDirection )
402          switch( Character.getDirectionality(string[i++]) )
403            {
404            case Character.DIRECTIONALITY_LEFT_TO_RIGHT:
405            case Character.DIRECTIONALITY_LEFT_TO_RIGHT_EMBEDDING:
406            case Character.DIRECTIONALITY_LEFT_TO_RIGHT_OVERRIDE:
407              gotDirection = true;
408              break;
409              
410            case Character.DIRECTIONALITY_RIGHT_TO_LEFT:
411            case Character.DIRECTIONALITY_RIGHT_TO_LEFT_ARABIC:
412            case Character.DIRECTIONALITY_RIGHT_TO_LEFT_EMBEDDING:
413            case Character.DIRECTIONALITY_RIGHT_TO_LEFT_OVERRIDE:
414              leftToRight = false;
415              gotDirection = true;
416              break;
417            }
418        determineWhiteSpace();
419      }
420    
421      private void determineWhiteSpace()
422      {
423        // Determine if there's whitespace in the thing.
424        // Ignore trailing chars.
425        int i = offset + length - 1; 
426        hasWhitespace = false;
427        while( i >= offset && Character.isWhitespace( string[i] ) )
428          i--;
429        // Check the remaining chars
430        while( i >= offset )
431          if( Character.isWhitespace( string[i--] ) )
432            hasWhitespace = true;
433      }
434    
435      protected Object clone ()
436      {
437        return new TextLayout( this, 0, length);
438      }
439    
440      public void draw (Graphics2D g2, float x, float y) 
441      {    
442        for(int i = 0; i < runs.length; i++)
443          {
444            Run run = runs[i];
445            GlyphVector gv = run.glyphVector;
446            g2.drawGlyphVector(gv, x, y);
447            Rectangle2D r = gv.getLogicalBounds();
448            x += r.getWidth();
449          }
450      }
451    
452      public boolean equals (Object obj)
453      {
454        if( !( obj instanceof TextLayout) )
455          return false;
456    
457        return equals( (TextLayout) obj );
458      }
459    
460      public boolean equals (TextLayout tl)
461      {
462        if( runs.length != tl.runs.length )
463          return false;
464        // Compare all glyph vectors.
465        for( int i = 0; i < runs.length; i++ )
466          if( !runs[i].equals( tl.runs[i] ) )
467            return false;
468        return true;
469      }
470    
471      public float getAdvance ()
472      {
473        if (totalAdvance == -1F)
474          {
475            totalAdvance = 0f;
476            for(int i = 0; i < runs.length; i++)
477              {
478                Run run = runs[i];
479                GlyphVector gv = run.glyphVector;
480                totalAdvance += gv.getLogicalBounds().getWidth();
481              }
482          }
483        return totalAdvance;
484      }
485    
486      public float getAscent ()
487      {
488        return lm.getAscent();
489      }
490    
491      public byte getBaseline ()
492      {
493        return (byte)lm.getBaselineIndex();
494      }
495    
496      public float[] getBaselineOffsets ()
497      {
498        return lm.getBaselineOffsets();
499      }
500    
501      public Shape getBlackBoxBounds (int firstEndpoint, int secondEndpoint)
502      {
503        if( secondEndpoint - firstEndpoint <= 0 )
504          return new Rectangle2D.Float(); // Hmm? 
505    
506        if( firstEndpoint < 0 || secondEndpoint > getCharacterCount())
507          return new Rectangle2D.Float();
508    
509        GeneralPath gp = new GeneralPath();
510        
511        int ri = charIndices[ firstEndpoint ][0];
512        int gi = charIndices[ firstEndpoint ][1];
513    
514        double advance = 0;
515       
516        for( int i = 0; i < ri; i++ )
517          {
518            Run run = runs[i];
519            GlyphVector gv = run.glyphVector;
520            advance += gv.getLogicalBounds().getWidth();
521          }
522        
523        for( int i = ri; i <= charIndices[ secondEndpoint - 1 ][0]; i++ )
524          {
525            Run run = runs[i];
526            GlyphVector gv = run.glyphVector;
527            int dg;
528            if( i == charIndices[ secondEndpoint - 1 ][0] )
529              dg = charIndices[ secondEndpoint - 1][1];
530            else
531              dg = gv.getNumGlyphs() - 1;
532    
533            for( int j = 0; j <= dg; j++ )
534              {
535                Rectangle2D r2 = (gv.getGlyphVisualBounds( j )).
536                  getBounds2D();
537                Point2D p = gv.getGlyphPosition( j );
538                r2.setRect( advance + r2.getX(), r2.getY(), 
539                            r2.getWidth(), r2.getHeight() );
540                gp.append(r2, false);
541              }
542    
543            advance += gv.getLogicalBounds().getWidth();
544          }
545        return gp;
546      }
547    
548      public Rectangle2D getBounds()
549      {
550        if( boundsCache == null )
551          boundsCache = getOutline(new AffineTransform()).getBounds();
552        return boundsCache;
553      }
554    
555      public float[] getCaretInfo (TextHitInfo hit)
556      {
557        return getCaretInfo(hit, getNaturalBounds());
558      }
559    
560      public float[] getCaretInfo (TextHitInfo hit, Rectangle2D bounds)
561      {
562        float[] info = new float[2];
563        int index = hit.getCharIndex();
564        boolean leading = hit.isLeadingEdge();
565        // For the boundary cases we return the boundary runs.
566        Run run;
567        
568        if (index >= length)
569          {
570            info[0] = getAdvance();
571            info[1] = 0;
572          }
573        else
574          {
575            if (index < 0)
576              {
577                run = runs[0];
578                index = 0;
579                leading = true;
580              }
581            else
582              run = findRunAtIndex(index);
583    
584            int glyphIndex = index - run.runStart;
585            Shape glyphBounds = run.glyphVector.getGlyphLogicalBounds(glyphIndex);
586            Rectangle2D glyphRect = glyphBounds.getBounds2D();
587            if (isVertical())
588              {
589                if (leading)
590                  info[0] = (float) glyphRect.getMinY();
591                else
592                  info[0] = (float) glyphRect.getMaxY();
593              }
594            else
595              {
596                if (leading)
597                  info[0] = (float) glyphRect.getMinX();
598                else
599                  info[0] = (float) glyphRect.getMaxX();
600              }
601            info[0] += run.location;
602            info[1] = run.font.getItalicAngle();
603          }
604        return info;
605      }
606    
607      public Shape getCaretShape(TextHitInfo hit)
608      {
609        return getCaretShape(hit, getBounds());
610      }
611    
612      public Shape getCaretShape(TextHitInfo hit, Rectangle2D bounds)
613      {
614        // TODO: Handle vertical shapes somehow.
615        float[] info = getCaretInfo(hit);
616        float x1 = info[0];
617        float y1 = (float) bounds.getMinY();
618        float x2 = info[0];
619        float y2 = (float) bounds.getMaxY();
620        if (info[1] != 0)
621          {
622            // Shift x1 and x2 according to the slope.
623            x1 -= y1 * info[1];
624            x2 -= y2 * info[1];
625          }
626        GeneralPath path = new GeneralPath(GeneralPath.WIND_EVEN_ODD, 2);
627        path.moveTo(x1, y1);
628        path.lineTo(x2, y2);
629        return path;
630      }
631    
632      public Shape[] getCaretShapes(int offset)
633      {
634        return getCaretShapes(offset, getNaturalBounds());
635      }
636    
637      public Shape[] getCaretShapes(int offset, Rectangle2D bounds)
638      {
639        return getCaretShapes(offset, bounds, DEFAULT_CARET_POLICY);
640      }
641    
642      public Shape[] getCaretShapes(int offset, Rectangle2D bounds,
643                                    CaretPolicy policy)
644      {
645        // The RI returns a 2-size array even when there's only one
646        // shape in it.
647        Shape[] carets = new Shape[2];
648        TextHitInfo hit1 = TextHitInfo.afterOffset(offset);
649        int caretHit1 = hitToCaret(hit1);
650        TextHitInfo hit2 = hit1.getOtherHit();
651        int caretHit2 = hitToCaret(hit2);
652        if (caretHit1 == caretHit2)
653          {
654            carets[0] = getCaretShape(hit1);
655            carets[1] = null; // The RI returns null in this seldom case.
656          }
657        else
658          {
659            Shape caret1 = getCaretShape(hit1);
660            Shape caret2 = getCaretShape(hit2);
661            TextHitInfo strong = policy.getStrongCaret(hit1, hit2, this);
662            if (strong == hit1)
663              {
664                carets[0] = caret1;
665                carets[1] = caret2;
666              }
667            else
668              {
669                carets[0] = caret2;
670                carets[1] = caret1;
671              }
672          }
673        return carets;
674      }
675    
676      public int getCharacterCount ()
677      {
678        return length;
679      }
680    
681      public byte getCharacterLevel (int index)
682      {
683        byte level;
684        if( bidi == null )
685          level = 0;
686        else
687          level = (byte) bidi.getLevelAt(index);
688        return level;
689      }
690    
691      public float getDescent ()
692      {
693        return lm.getDescent();
694      }
695    
696      public TextLayout getJustifiedLayout (float justificationWidth)
697      {
698        TextLayout newLayout = (TextLayout)clone();
699    
700        if( hasWhitespace )
701          newLayout.handleJustify( justificationWidth );
702    
703        return newLayout;
704      }
705    
706      public float getLeading ()
707      {
708        return lm.getLeading();
709      }
710    
711      public Shape getLogicalHighlightShape (int firstEndpoint, int secondEndpoint)
712      {
713        return getLogicalHighlightShape( firstEndpoint, secondEndpoint, 
714                                         getBounds() );
715      }
716    
717      public Shape getLogicalHighlightShape (int firstEndpoint, int secondEndpoint,
718                                             Rectangle2D bounds)
719      {
720        if( secondEndpoint - firstEndpoint <= 0 )
721          return new Rectangle2D.Float(); // Hmm? 
722    
723        if( firstEndpoint < 0 || secondEndpoint > getCharacterCount())
724          return new Rectangle2D.Float();
725    
726        Rectangle2D r = null;
727        int ri = charIndices[ firstEndpoint ][0];
728        int gi = charIndices[ firstEndpoint ][1];
729    
730        double advance = 0;
731       
732        for( int i = 0; i < ri; i++ )
733          advance += runs[i].glyphVector.getLogicalBounds().getWidth();
734    
735        for( int i = ri; i <= charIndices[ secondEndpoint - 1 ][0]; i++ )
736          {
737            Run run = runs[i];
738            GlyphVector gv = run.glyphVector;
739            int dg; // last index in this run to use.
740            if( i == charIndices[ secondEndpoint - 1 ][0] )
741              dg = charIndices[ secondEndpoint - 1][1];
742            else
743              dg = gv.getNumGlyphs() - 1;
744    
745            for(; gi <= dg; gi++ )
746              {
747                Rectangle2D r2 = (gv.getGlyphLogicalBounds( gi )).
748                  getBounds2D();
749                if( r == null )
750                  r = r2;
751                else
752                  r = r.createUnion(r2);
753              }
754            gi = 0; // reset glyph index into run for next run.
755    
756            advance += gv.getLogicalBounds().getWidth();
757          }
758    
759        return r;
760      }
761    
762      public int[] getLogicalRangesForVisualSelection (TextHitInfo firstEndpoint,
763                                                       TextHitInfo secondEndpoint)
764      {
765        // Check parameters.
766        checkHitInfo(firstEndpoint);
767        checkHitInfo(secondEndpoint);
768    
769        // Convert to visual and order correctly.
770        int start = hitToCaret(firstEndpoint);
771        int end = hitToCaret(secondEndpoint);
772        if (start > end)
773          {
774            // Swap start and end so that end >= start.
775            int temp = start;
776            start = end;
777            end = temp;
778          }
779    
780        // Now walk through the visual indices and mark the included pieces.
781        boolean[] include = new boolean[length];
782        for (int i = start; i < end; i++)
783          {
784            include[visualToLogical[i]] = true;
785          }
786    
787        // Count included runs.
788        int numRuns = 0;
789        boolean in = false;
790        for (int i = 0; i < length; i++)
791          {
792            if (include[i] != in) // At each run in/out point we toggle the in var.
793              {
794                in = ! in;
795                if (in) // At each run start we count up.
796                  numRuns++;
797              }
798          }
799    
800        // Put together the ranges array.
801        int[] ranges = new int[numRuns * 2];
802        int index = 0;
803        in = false;
804        for (int i = 0; i < length; i++)
805          {
806            if (include[i] != in)
807              {
808                ranges[index] = i;
809                index++;
810                in = ! in;
811              }
812          }
813        // If the last run ends at the very end, include that last bit too.
814        if (in)
815          ranges[index] = length;
816    
817        return ranges;
818      }
819    
820      public TextHitInfo getNextLeftHit(int offset)
821      {
822        return getNextLeftHit(offset, DEFAULT_CARET_POLICY);
823      }
824    
825      public TextHitInfo getNextLeftHit(int offset, CaretPolicy policy)
826      {
827        if (policy == null)
828          throw new IllegalArgumentException("Null policy not allowed");
829        if (offset < 0 || offset > length)
830          throw new IllegalArgumentException("Offset out of bounds");
831    
832        TextHitInfo hit1 = TextHitInfo.afterOffset(offset);
833        TextHitInfo hit2 = hit1.getOtherHit();
834    
835        TextHitInfo strong = policy.getStrongCaret(hit1, hit2, this);
836        TextHitInfo next = getNextLeftHit(strong);
837        TextHitInfo ret = null;
838        if (next != null)
839          {
840            TextHitInfo next2 = getVisualOtherHit(next);
841            ret = policy.getStrongCaret(next2, next, this);
842          }
843        return ret;
844      }
845    
846      public TextHitInfo getNextLeftHit (TextHitInfo hit)
847      {
848        checkHitInfo(hit);
849        int index = hitToCaret(hit);
850        TextHitInfo next = null;
851        if (index != 0)
852          {
853            index--;
854            next = caretToHit(index);
855          }
856        return next;
857      }
858    
859      public TextHitInfo getNextRightHit(int offset)
860      {
861        return getNextRightHit(offset, DEFAULT_CARET_POLICY);
862      }
863    
864      public TextHitInfo getNextRightHit(int offset, CaretPolicy policy)
865      {
866        if (policy == null)
867          throw new IllegalArgumentException("Null policy not allowed");
868        if (offset < 0 || offset > length)
869          throw new IllegalArgumentException("Offset out of bounds");
870    
871        TextHitInfo hit1 = TextHitInfo.afterOffset(offset);
872        TextHitInfo hit2 = hit1.getOtherHit();
873    
874        TextHitInfo next = getNextRightHit(policy.getStrongCaret(hit1, hit2, this));
875        TextHitInfo ret = null;
876        if (next != null)
877          {
878            TextHitInfo next2 = getVisualOtherHit(next);
879            ret = policy.getStrongCaret(next2, next, this);
880          }
881        return ret;
882      }
883    
884      public TextHitInfo getNextRightHit(TextHitInfo hit)
885      {
886        checkHitInfo(hit);
887        int index = hitToCaret(hit);
888        TextHitInfo next = null;
889        if (index < length)
890          {
891            index++;
892            next = caretToHit(index);
893          }
894        return next;
895      }
896    
897      public Shape getOutline (AffineTransform tx)
898      {
899        float x = 0f;
900        GeneralPath gp = new GeneralPath();
901        for(int i = 0; i < runs.length; i++)
902          {
903            GlyphVector gv = runs[i].glyphVector;
904            gp.append( gv.getOutline( x, 0f ), false );
905            Rectangle2D r = gv.getLogicalBounds();
906            x += r.getWidth();
907          }
908        if( tx != null )
909          gp.transform( tx );
910        return gp;
911      }
912    
913      public float getVisibleAdvance ()
914      {
915        float totalAdvance = 0f;
916    
917        if( runs.length <= 0 )
918          return 0f;
919    
920        // No trailing whitespace
921        if( !Character.isWhitespace( string[offset + length - 1]) )
922          return getAdvance();
923    
924        // Get length of all runs up to the last
925        for(int i = 0; i < runs.length - 1; i++)
926          totalAdvance += runs[i].glyphVector.getLogicalBounds().getWidth();
927    
928        int lastRun = runs[runs.length - 1].runStart;
929        int j = length - 1;
930        while( j >= lastRun && Character.isWhitespace( string[j] ) ) j--;
931    
932        if( j < lastRun )
933          return totalAdvance; // entire last run is whitespace
934    
935        int lastNonWSChar = j - lastRun;
936        j = 0;
937        while( runs[ runs.length - 1 ].glyphVector.getGlyphCharIndex( j )
938               <= lastNonWSChar )
939          {
940            totalAdvance += runs[ runs.length - 1 ].glyphVector
941                                                   .getGlyphLogicalBounds( j )
942                                                   .getBounds2D().getWidth();
943            j ++;
944          }
945        
946        return totalAdvance;
947      }
948    
949      public Shape getVisualHighlightShape (TextHitInfo firstEndpoint,
950                                            TextHitInfo secondEndpoint)
951      {
952        return getVisualHighlightShape( firstEndpoint, secondEndpoint, 
953                                        getBounds() );
954      }
955    
956      public Shape getVisualHighlightShape (TextHitInfo firstEndpoint,
957                                            TextHitInfo secondEndpoint,
958                                            Rectangle2D bounds)
959      {
960        GeneralPath path = new GeneralPath(GeneralPath.WIND_EVEN_ODD);
961        Shape caret1 = getCaretShape(firstEndpoint, bounds);
962        path.append(caret1, false);
963        Shape caret2 = getCaretShape(secondEndpoint, bounds);
964        path.append(caret2, false);
965        // Append left (top) bounds to selection if necessary.
966        int c1 = hitToCaret(firstEndpoint);
967        int c2 = hitToCaret(secondEndpoint);
968        if (c1 == 0 || c2 == 0)
969          {
970            path.append(left(bounds), false);
971          }
972        // Append right (bottom) bounds if necessary.
973        if (c1 == length || c2 == length)
974          {
975            path.append(right(bounds), false);
976          }
977        return path.getBounds2D();
978      }
979    
980      /**
981       * Returns the shape that makes up the left (top) edge of this text layout.
982       *
983       * @param b the bounds
984       *
985       * @return the shape that makes up the left (top) edge of this text layout
986       */
987      private Shape left(Rectangle2D b)
988      {
989        GeneralPath left = new GeneralPath(GeneralPath.WIND_EVEN_ODD);
990        left.append(getCaretShape(TextHitInfo.beforeOffset(0)), false);
991        if (isVertical())
992          {
993            float y = (float) b.getMinY();
994            left.append(new Line2D.Float((float) b.getMinX(), y,
995                                         (float) b.getMaxX(), y), false);
996          }
997        else
998          {
999            float x = (float) b.getMinX();
1000            left.append(new Line2D.Float(x, (float) b.getMinY(),
1001                                         x, (float) b.getMaxY()), false);
1002          }
1003        return left.getBounds2D();
1004      }
1005    
1006      /**
1007       * Returns the shape that makes up the right (bottom) edge of this text
1008       * layout.
1009       *
1010       * @param b the bounds
1011       *
1012       * @return the shape that makes up the right (bottom) edge of this text
1013       *         layout
1014       */
1015      private Shape right(Rectangle2D b)
1016      {
1017        GeneralPath right = new GeneralPath(GeneralPath.WIND_EVEN_ODD);
1018        right.append(getCaretShape(TextHitInfo.afterOffset(length)), false);
1019        if (isVertical())
1020          {
1021            float y = (float) b.getMaxY();
1022            right.append(new Line2D.Float((float) b.getMinX(), y,
1023                                          (float) b.getMaxX(), y), false);
1024          }
1025        else
1026          {
1027            float x = (float) b.getMaxX();
1028            right.append(new Line2D.Float(x, (float) b.getMinY(),
1029                                          x, (float) b.getMaxY()), false);
1030          }
1031        return right.getBounds2D();
1032      }
1033    
1034      public TextHitInfo getVisualOtherHit (TextHitInfo hit)
1035      {
1036        checkHitInfo(hit);
1037        int hitIndex = hit.getCharIndex();
1038    
1039        int index;
1040        boolean leading;
1041        if (hitIndex == -1 || hitIndex == length)
1042          {
1043            // Boundary case.
1044            int visual;
1045            if (isLeftToRight() == (hitIndex == -1))
1046              visual = 0;
1047            else
1048              visual = length - 1;
1049            index = visualToLogical[visual];
1050            if (isLeftToRight() == (hitIndex == -1))
1051              leading = isCharacterLTR(index); // LTR.
1052            else
1053              leading = ! isCharacterLTR(index); // RTL.
1054          }
1055        else
1056          {
1057            // Normal case.
1058            int visual = logicalToVisual[hitIndex];
1059            boolean b;
1060            if (isCharacterLTR(hitIndex) == hit.isLeadingEdge())
1061              {
1062                visual--;
1063                b = false;
1064              }
1065            else
1066              {
1067                visual++;
1068                b = true;
1069              }
1070            if (visual >= 0 && visual < length)
1071              {
1072                index = visualToLogical[visual];
1073                leading = b == isLeftToRight();
1074              }
1075            else
1076              {
1077                index = b == isLeftToRight() ? length : -1;
1078                leading = index == length;
1079              }
1080          }
1081        return leading ? TextHitInfo.leading(index) : TextHitInfo.trailing(index);
1082      }
1083    
1084      /**
1085       * This is a protected method of a <code>final</code> class, meaning
1086       * it exists only to taunt you.
1087       */
1088      protected void handleJustify (float justificationWidth)
1089      {
1090        // We assume that the text has non-trailing whitespace.
1091        // First get the change in width to insert into the whitespaces.
1092        double deltaW = justificationWidth - getVisibleAdvance();
1093        int nglyphs = 0; // # of whitespace chars
1094    
1095        // determine last non-whitespace char.
1096        int lastNWS = offset + length - 1;
1097        while( Character.isWhitespace( string[lastNWS] ) ) lastNWS--;
1098    
1099        // locations of the glyphs.
1100        int[] wsglyphs = new int[length * 10];
1101        for(int run = 0; run < runs.length; run++ )
1102          {
1103          Run current = runs[run];
1104          for(int i = 0; i < current.glyphVector.getNumGlyphs(); i++ )
1105            {
1106              int cindex = current.runStart
1107                           + current.glyphVector.getGlyphCharIndex( i );
1108              if( Character.isWhitespace( string[cindex] ) )
1109                //        && cindex < lastNWS )
1110                {
1111                  wsglyphs[ nglyphs * 2 ] = run;
1112                  wsglyphs[ nglyphs * 2 + 1] = i;
1113                  nglyphs++;
1114                }
1115            }
1116          }
1117        deltaW = deltaW / nglyphs; // Change in width per whitespace glyph
1118        double w = 0;
1119        int cws = 0;
1120        // Shift all characters
1121        for(int run = 0; run < runs.length; run++ )
1122          {
1123            Run current = runs[run];
1124            for(int i = 0; i < current.glyphVector.getNumGlyphs(); i++ )
1125              {
1126                if( wsglyphs[ cws * 2 ] == run && wsglyphs[ cws * 2 + 1 ] == i )
1127                  {
1128                    cws++; // update 'current whitespace'
1129                    w += deltaW; // increment the shift
1130                  }
1131                Point2D p = current.glyphVector.getGlyphPosition( i );
1132                p.setLocation( p.getX() + w, p.getY() );
1133                current.glyphVector.setGlyphPosition( i, p );
1134              }
1135          }
1136      }
1137    
1138      public TextHitInfo hitTestChar (float x, float y)
1139      {
1140        return hitTestChar(x, y, getNaturalBounds());
1141      }
1142    
1143      /**
1144       * Finds the character hit at the specified point. This 'clips' this
1145       * text layout against the specified <code>bounds</code> rectangle. That
1146       * means that in the case where a point is outside these bounds, this method
1147       * returns the leading edge of the first character or the trailing edge of
1148       * the last character.
1149       *
1150       * @param x the X location to test
1151       * @param y the Y location to test
1152       * @param bounds the bounds to test against
1153       *
1154       * @return the character hit at the specified point
1155       */
1156      public TextHitInfo hitTestChar (float x, float y, Rectangle2D bounds)
1157      {
1158        // Check bounds.
1159        if (isVertical())
1160          {
1161            if (y < bounds.getMinY())
1162              return TextHitInfo.leading(0);
1163            else if (y > bounds.getMaxY())
1164              return TextHitInfo.trailing(getCharacterCount() - 1);
1165          }
1166        else
1167          {
1168            if (x < bounds.getMinX())
1169              return TextHitInfo.leading(0);
1170            else if (x > bounds.getMaxX())
1171              return TextHitInfo.trailing(getCharacterCount() - 1);
1172          }
1173    
1174        TextHitInfo hitInfo = null;
1175        if (isVertical())
1176          {
1177            // Search for the run at the location.
1178            // TODO: Perform binary search for maximum efficiency. However, we
1179            // need the run location laid out statically to do that.
1180            int numRuns = runs.length;
1181            Run hitRun = null;
1182            for (int i = 0; i < numRuns && hitRun == null; i++)
1183              {
1184                Run run = runs[i];
1185                Rectangle2D lBounds = run.glyphVector.getLogicalBounds();
1186                if (lBounds.getMinY() + run.location <= y
1187                    && lBounds.getMaxY() + run.location >= y)
1188                  hitRun = run;
1189              }
1190            // Now we have (hopefully) found a run that hits. Now find the
1191            // right character.
1192            if (hitRun != null)
1193              {
1194                GlyphVector gv = hitRun.glyphVector;
1195                for (int i = hitRun.runStart;
1196                     i < hitRun.runEnd && hitInfo == null; i++)
1197                  {
1198                    int gi = i - hitRun.runStart;
1199                    Rectangle2D lBounds = gv.getGlyphLogicalBounds(gi)
1200                                          .getBounds2D();
1201                    if (lBounds.getMinY() + hitRun.location <= y
1202                        && lBounds.getMaxY() + hitRun.location >= y)
1203                      {
1204                        // Found hit. Now check if we are leading or trailing.
1205                        boolean leading = true;
1206                        if (lBounds.getCenterY() + hitRun.location <= y)
1207                          leading = false;
1208                        hitInfo = leading ? TextHitInfo.leading(i)
1209                                          : TextHitInfo.trailing(i);
1210                      }
1211                  }
1212              }
1213          }
1214        else
1215          {
1216            // Search for the run at the location.
1217            // TODO: Perform binary search for maximum efficiency. However, we
1218            // need the run location laid out statically to do that.
1219            int numRuns = runs.length;
1220            Run hitRun = null;
1221            for (int i = 0; i < numRuns && hitRun == null; i++)
1222              {
1223                Run run = runs[i];
1224                Rectangle2D lBounds = run.glyphVector.getLogicalBounds();
1225                if (lBounds.getMinX() + run.location <= x
1226                    && lBounds.getMaxX() + run.location >= x)
1227                  hitRun = run;
1228              }
1229            // Now we have (hopefully) found a run that hits. Now find the
1230            // right character.
1231            if (hitRun != null)
1232              {
1233                GlyphVector gv = hitRun.glyphVector;
1234                for (int i = hitRun.runStart;
1235                     i < hitRun.runEnd && hitInfo == null; i++)
1236                  {
1237                    int gi = i - hitRun.runStart;
1238                    Rectangle2D lBounds = gv.getGlyphLogicalBounds(gi)
1239                                          .getBounds2D();
1240                    if (lBounds.getMinX() + hitRun.location <= x
1241                        && lBounds.getMaxX() + hitRun.location >= x)
1242                      {
1243                        // Found hit. Now check if we are leading or trailing.
1244                        boolean leading = true;
1245                        if (lBounds.getCenterX() + hitRun.location <= x)
1246                          leading = false;
1247                        hitInfo = leading ? TextHitInfo.leading(i)
1248                                          : TextHitInfo.trailing(i);
1249                      }
1250                  }
1251              }
1252          }
1253        return hitInfo;
1254      }
1255    
1256      public boolean isLeftToRight ()
1257      {
1258        return leftToRight;
1259      }
1260    
1261      public boolean isVertical ()
1262      {
1263        return false; // FIXME: How do you create a vertical layout?
1264      }
1265    
1266      public int hashCode ()
1267      {
1268        // This is implemented in sync to equals().
1269        if (hash == 0 && runs.length > 0)
1270          {
1271            hash = runs.length;
1272            for (int i = 0; i < runs.length; i++)
1273              hash ^= runs[i].glyphVector.hashCode();
1274          }
1275        return hash;
1276      }
1277    
1278      public String toString ()
1279      {
1280        return "TextLayout [string:"+ new String(string, offset, length)
1281        +" Rendercontext:"+
1282          frc+"]";
1283      }
1284    
1285      /**
1286       * Returns the natural bounds of that text layout. This is made up
1287       * of the ascent plus descent and the text advance.
1288       *
1289       * @return the natural bounds of that text layout
1290       */
1291      private Rectangle2D getNaturalBounds()
1292      {
1293        if (naturalBounds == null)
1294          naturalBounds = new Rectangle2D.Float(0.0F, -getAscent(), getAdvance(),
1295                                                getAscent() + getDescent());
1296        return naturalBounds;
1297      }
1298    
1299      private void checkHitInfo(TextHitInfo hit)
1300      {
1301        if (hit == null)
1302          throw new IllegalArgumentException("Null hit info not allowed");
1303        int index = hit.getInsertionIndex();
1304        if (index < 0 || index > length)
1305          throw new IllegalArgumentException("Hit index out of range");
1306      }
1307    
1308      private int hitToCaret(TextHitInfo hit)
1309      {
1310        int index = hit.getCharIndex();
1311        int ret;
1312        if (index < 0)
1313          ret = isLeftToRight() ? 0 : length;
1314        else if (index >= length)
1315          ret = isLeftToRight() ? length : 0;
1316        else
1317          {
1318            ret = logicalToVisual[index];
1319            if (hit.isLeadingEdge() != isCharacterLTR(index))
1320              ret++;
1321          }
1322        return ret;
1323      }
1324    
1325      private TextHitInfo caretToHit(int index)
1326      {
1327        TextHitInfo hit;
1328        if (index == 0 || index == length)
1329          {
1330            if ((index == length) == isLeftToRight())
1331              hit = TextHitInfo.leading(length);
1332            else
1333              hit = TextHitInfo.trailing(-1);
1334          }
1335        else
1336          {
1337            int logical = visualToLogical[index];
1338            boolean leading = isCharacterLTR(logical); // LTR.
1339            hit = leading ? TextHitInfo.leading(logical)
1340                          : TextHitInfo.trailing(logical);
1341          }
1342        return hit;
1343      }
1344    
1345      private boolean isCharacterLTR(int index)
1346      {
1347        byte level = getCharacterLevel(index);
1348        return (level & 1) == 0;
1349      }
1350    
1351      /**
1352       * Finds the run that holds the specified (logical) character index. This
1353       * returns <code>null</code> when the index is not inside the range.
1354       *
1355       * @param index the index of the character to find
1356       *
1357       * @return the run that holds the specified character
1358       */
1359      private Run findRunAtIndex(int index)
1360      {
1361        Run found = null;
1362        // TODO: Can we do better than linear searching here?
1363        for (int i = 0; i < runs.length && found == null; i++)
1364          {
1365            Run run = runs[i];
1366            if (run.runStart <= index && run.runEnd > index)
1367              found = run;
1368          }
1369        return found;
1370      }
1371    
1372      /**
1373       * Computes the layout locations for each run.
1374       */
1375      private void layoutRuns()
1376      {
1377        float loc = 0.0F;
1378        float lastWidth = 0.0F;
1379        for (int i = 0; i < runs.length; i++)
1380          {
1381            runs[i].location = loc;
1382            Rectangle2D bounds = runs[i].glyphVector.getLogicalBounds();
1383            loc += isVertical() ? bounds.getHeight() : bounds.getWidth();
1384          }
1385      }
1386    
1387      /**
1388       * Inner class describing a caret policy
1389       */
1390      public static class CaretPolicy
1391      {
1392        public CaretPolicy()
1393        {
1394        }
1395    
1396        public TextHitInfo getStrongCaret(TextHitInfo hit1,
1397                                          TextHitInfo hit2,
1398                                          TextLayout layout)
1399        {
1400          byte l1 = layout.getCharacterLevel(hit1.getCharIndex());
1401          byte l2 = layout.getCharacterLevel(hit2.getCharIndex());
1402          TextHitInfo strong;
1403          if (l1 == l2)
1404            {
1405              if (hit2.isLeadingEdge() && ! hit1.isLeadingEdge())
1406                strong = hit2;
1407              else
1408                strong = hit1;
1409            }
1410          else
1411            {
1412              if (l1 < l2)
1413                strong = hit1;
1414              else
1415                strong = hit2;
1416            }
1417          return strong;
1418        }
1419      }
1420    }
1421    
1422