Merged gcj-eclipse branch to trunk.

From-SVN: r120621

3 files changed, 871 insertions, 157 deletions

diff --git a/libjava/classpath/java/awt/font/FontRenderContext.java b/libjava/classpath/java/awt/font/FontRenderContext.java
index c50e5e5..c25bae3 100644
--- a/libjava/classpath/java/awt/font/FontRenderContext.java
+++ b/libjava/classpath/java/awt/font/FontRenderContext.java
@@ -117,8 +117,12 @@ public class FontRenderContext
    */
   public int hashCode ()
   {
-    // FIXME: check what SUN does here.
-    return affineTransform == null ? 0 : affineTransform.hashCode ();
+    int code = ( isAntiAliased ? 1 : 0 ) + ( usesFractionalMetrics ? 2 : 0 );
+
+    if( affineTransform != null && !affineTransform.isIdentity() )
+      code ^= affineTransform.hashCode();
+
+    return code;
   }
 
   public boolean isAntiAliased ()
diff --git a/libjava/classpath/java/awt/font/TextHitInfo.java b/libjava/classpath/java/awt/font/TextHitInfo.java
index 2b23e19..f6fee1a 100644
--- a/libjava/classpath/java/awt/font/TextHitInfo.java
+++ b/libjava/classpath/java/awt/font/TextHitInfo.java
@@ -81,6 +81,9 @@ public final class TextHitInfo
 
   public boolean equals(TextHitInfo hitInfo)
   {
+    if (hitInfo == null)
+      return false;
+    
     return (charIndex == hitInfo.getCharIndex ())
             && (leadingEdge == hitInfo.isLeadingEdge ());
   }
@@ -97,7 +100,7 @@ public final class TextHitInfo
 
   public static TextHitInfo beforeOffset(int offset)
   {
-    return new TextHitInfo (offset, false);
+    return new TextHitInfo ((offset - 1), false);
   }
 
   public static TextHitInfo afterOffset(int offset)
diff --git a/libjava/classpath/java/awt/font/TextLayout.java b/libjava/classpath/java/awt/font/TextLayout.java
index b1473f2..dc0e537 100644
--- a/libjava/classpath/java/awt/font/TextLayout.java
+++ b/libjava/classpath/java/awt/font/TextLayout.java
@@ -38,18 +38,18 @@ exception statement from your version. */
 
 package java.awt.font;
 
-import gnu.classpath.NotImplementedException;
-
 import java.awt.Font;
 import java.awt.Graphics2D;
 import java.awt.Shape;
 import java.awt.geom.AffineTransform;
+import java.awt.geom.Line2D;
 import java.awt.geom.Rectangle2D;
 import java.awt.geom.GeneralPath;
 import java.awt.geom.Point2D;
 import java.text.CharacterIterator;
 import java.text.AttributedCharacterIterator;
 import java.text.Bidi;
+import java.util.ArrayList;
 import java.util.Map;
 
 /**
@@ -57,19 +57,86 @@ import java.util.Map;
  */
 public final class TextLayout implements Cloneable
 {
-  private GlyphVector[] runs;
-  private Font font;
+  /**
+   * Holds the layout data that belongs to one run of characters.
+   */
+  private class Run
+  {
+    /**
+     * The actual glyph vector.
+     */
+    GlyphVector glyphVector;
+
+    /**
+     * The font for this text run.
+     */
+    Font font;
+
+    /**
+     * The start of the run.
+     */
+    int runStart;
+
+    /**
+     * The end of the run.
+     */
+    int runEnd;
+
+    /**
+     * The layout location of the beginning of the run.
+     */
+    float location;
+
+    /**
+     * Initializes the Run instance.
+     *
+     * @param gv the glyph vector
+     * @param start the start index of the run
+     * @param end the end index of the run
+     */
+    Run(GlyphVector gv, Font f, int start, int end)
+    {
+      glyphVector = gv;
+      font = f;
+      runStart = start;
+      runEnd = end;
+    }
+
+    /**
+     * Returns <code>true</code> when this run is left to right,
+     * <code>false</code> otherwise.
+     *
+     * @return <code>true</code> when this run is left to right,
+     *         <code>false</code> otherwise
+     */
+    boolean isLeftToRight()
+    {
+      return (glyphVector.getLayoutFlags() & GlyphVector.FLAG_RUN_RTL) == 0;
+    }
+  }
+
+  /**
+   * The laid out character runs.
+   */
+  private Run[] runs;
+
   private FontRenderContext frc;
-  private String string;
+  private char[] string;
+  private int offset;
+  private int length;
   private Rectangle2D boundsCache;
   private LineMetrics lm;
 
   /**
-   * Start and end character indices of the runs.
-   * First index is the run number, second is 0 or 1 for the starting 
-   * and ending character index of the run, respectively.
+   * The total advance of this text layout. This is cache for maximum
+   * performance.
+   */
+  private float totalAdvance = -1F;
+  
+  /**
+   * The cached natural bounds.
    */
-  private int[][] runIndices;
+  private Rectangle2D naturalBounds;
 
   /**
    * Character indices.
@@ -88,66 +155,98 @@ public final class TextLayout implements Cloneable
   private boolean hasWhitespace = false;
 
   /**
+   * The {@link Bidi} object that is used for reordering and by
+   * {@link #getCharacterLevel(int)}.
+   */
+  private Bidi bidi;
+
+  /**
+   * Mpas the logical position of each individual character in the original
+   * string to its visual position.
+   */
+  private int[] logicalToVisual;
+
+  /**
+   * Maps visual positions of a character to its logical position
+   * in the original string.
+   */
+  private int[] visualToLogical;
+
+  /**
+   * The cached hashCode.
+   */
+  private int hash;
+
+  /**
    * The default caret policy.
    */
-  public static final TextLayout.CaretPolicy DEFAULT_CARET_POLICY = new CaretPolicy();
+  public static final TextLayout.CaretPolicy DEFAULT_CARET_POLICY =
+    new CaretPolicy();
 
   /**
    * Constructs a TextLayout.
    */
-  public TextLayout (String string, Font font, FontRenderContext frc) 
+  public TextLayout (String str, Font font, FontRenderContext frc) 
   {
-    this.font = font;
     this.frc = frc;
-    this.string = string;
-    lm = font.getLineMetrics(string, frc);
+    string = str.toCharArray();
+    offset = 0;
+    length = this.string.length;
+    lm = font.getLineMetrics(this.string, offset, length, frc);
 
     // Get base direction and whitespace info
     getStringProperties();
 
-    if( Bidi.requiresBidi( string.toCharArray(), 0, string.length() ) )
+    if (Bidi.requiresBidi(string, offset, offset + length))
       {
-	Bidi bidi = new Bidi( string, leftToRight ? 
-			      Bidi.DIRECTION_LEFT_TO_RIGHT : 
-			      Bidi.DIRECTION_RIGHT_TO_LEFT );
+	bidi = new Bidi(str, leftToRight ? Bidi.DIRECTION_LEFT_TO_RIGHT
+                                         : Bidi.DIRECTION_RIGHT_TO_LEFT );
 	int rc = bidi.getRunCount();
 	byte[] table = new byte[ rc ];
 	for(int i = 0; i < table.length; i++)
 	  table[i] = (byte)bidi.getRunLevel(i);
 
-	runs = new GlyphVector[ rc ];
-	runIndices = new int[rc][2];
-	for(int i = 0; i < runs.length; i++)
+        runs = new Run[rc];
+	for(int i = 0; i < rc; i++)
 	  {
-	    runIndices[i][0] = bidi.getRunStart( i );
-	    runIndices[i][1] = bidi.getRunLimit( i );
-	    if( runIndices[i][0] != runIndices[i][1] ) // no empty runs.
+	    int start = bidi.getRunStart(i);
+	    int end = bidi.getRunLimit(i);
+	    if(start != end) // no empty runs.
 	      {
-		runs[i] = font.layoutGlyphVector
-		  ( frc, string.toCharArray(),
-		    runIndices[i][0], runIndices[i][1],
-		    ((table[i] & 1) == 0) ? Font.LAYOUT_LEFT_TO_RIGHT :
-		    Font.LAYOUT_RIGHT_TO_LEFT );
-	      }
+	        GlyphVector gv = font.layoutGlyphVector(frc,
+                                                        string, start, end,
+                           ((table[i] & 1) == 0) ? Font.LAYOUT_LEFT_TO_RIGHT
+                                                 : Font.LAYOUT_RIGHT_TO_LEFT );
+                runs[i] = new Run(gv, font, start, end);
+              }
 	  }
 	Bidi.reorderVisually( table, 0, runs, 0, runs.length );
+        // Clean up null runs.
+        ArrayList cleaned = new ArrayList(rc);
+        for (int i = 0; i < rc; i++)
+          {
+            if (runs[i] != null)
+              cleaned.add(runs[i]);
+          }
+        runs = new Run[cleaned.size()];
+        runs = (Run[]) cleaned.toArray(runs);
       }
     else
       {
-	runs = new GlyphVector[ 1 ];
-	runIndices = new int[1][2];
-	runIndices[0][0] = 0;
-	runIndices[0][1] = string.length();
-	runs[ 0 ] = font.layoutGlyphVector( frc, string.toCharArray(), 
-					    0, string.length(),
-					    leftToRight ?
-					    Font.LAYOUT_LEFT_TO_RIGHT :
-					    Font.LAYOUT_RIGHT_TO_LEFT );
+        GlyphVector gv = font.layoutGlyphVector( frc, string, offset, length,
+                                     leftToRight ? Font.LAYOUT_LEFT_TO_RIGHT
+                                                 : Font.LAYOUT_RIGHT_TO_LEFT );
+        Run run = new Run(gv, font, 0, length);
+	runs = new Run[]{ run };
       }
     setCharIndices();
+    setupMappings();
+    layoutRuns();
   }
 
-  public TextLayout (String string, Map attributes, FontRenderContext frc)  
+  public TextLayout (String string,
+		     Map<? extends AttributedCharacterIterator.Attribute, ?> attributes,
+		     FontRenderContext frc)  
   {
     this( string, new Font( attributes ), frc );
   }
@@ -165,7 +264,6 @@ public final class TextLayout implements Cloneable
    */
   TextLayout(TextLayout t, int startIndex, int endIndex)
   {
-    font = t.font;
     frc = t.frc;
     boundsCache = null;
     lm = t.lm;
@@ -173,30 +271,35 @@ public final class TextLayout implements Cloneable
 
     if( endIndex > t.getCharacterCount() )
       endIndex = t.getCharacterCount();
-    string = t.string.substring( startIndex, endIndex );
+    string = t.string;
+    offset = startIndex + offset;
+    length = endIndex - startIndex;
 
     int startingRun = t.charIndices[startIndex][0];
     int nRuns = 1 + t.charIndices[endIndex - 1][0] - startingRun;
-    runIndices = new int[ nRuns ][2];
 
-    runs = new GlyphVector[ nRuns ];
+    runs = new Run[nRuns];
     for( int i = 0; i < nRuns; i++ )
       {
-	GlyphVector run = t.runs[ i + startingRun ];
+        Run run = t.runs[i + startingRun];
+	GlyphVector gv = run.glyphVector;
+        Font font = run.font;
 	// Copy only the relevant parts of the first and last runs.
 	int beginGlyphIndex = (i > 0) ? 0 : t.charIndices[startIndex][1];
-	int numEntries = ( i < nRuns - 1) ? run.getNumGlyphs() : 
+	int numEntries = ( i < nRuns - 1) ? gv.getNumGlyphs() : 
 	  1 + t.charIndices[endIndex - 1][1] - beginGlyphIndex;
 	
-	int[] codes = run.getGlyphCodes(beginGlyphIndex, numEntries, null);
-	runs[ i ] = font.createGlyphVector( frc, codes );
-	runIndices[ i ][0] = t.runIndices[i + startingRun][0] - startIndex;
-	runIndices[ i ][1] = t.runIndices[i + startingRun][1] - startIndex;
+	int[] codes = gv.getGlyphCodes(beginGlyphIndex, numEntries, null);
+        gv = font.createGlyphVector(frc, codes);
+        runs[i] = new Run(gv, font, run.runStart - startIndex,
+                          run.runEnd - startIndex);
       }
-    runIndices[ nRuns - 1 ][1] = endIndex - 1;
+    runs[nRuns - 1].runEnd = endIndex - 1;
 
     setCharIndices();
+    setupMappings();
     determineWhiteSpace();
+    layoutRuns();
   }
 
   private void setCharIndices()
@@ -207,16 +310,53 @@ public final class TextLayout implements Cloneable
     for(int run = 0; run < runs.length; run++)
       {
 	currentChar = -1;
-	for( int gi = 0; gi < runs[ run ].getNumGlyphs(); gi++)
-	  {
-	    if( runs[ run ].getGlyphCharIndex( gi ) != currentChar )
-	      {
-		charIndices[ i ][0] = run;
-		charIndices[ i ][1] = gi;
-		currentChar = runs[ run ].getGlyphCharIndex( gi );
-		i++;
-	      }
-	  }
+        Run current = runs[run];
+        GlyphVector gv = current.glyphVector;
+        for( int gi = 0; gi < gv.getNumGlyphs(); gi++)
+          {
+            if( gv.getGlyphCharIndex( gi ) != currentChar )
+              {
+                charIndices[ i ][0] = run;
+                charIndices[ i ][1] = gi;
+                currentChar = gv.getGlyphCharIndex( gi );
+                i++;
+              }
+          }
+      }
+  }
+
+  /**
+   * Initializes the logicalToVisual and visualToLogial maps.
+   */
+  private void setupMappings()
+  {
+    int numChars = getCharacterCount();
+    logicalToVisual = new int[numChars];
+    visualToLogical = new int[numChars];
+    int lIndex = 0;
+    int vIndex = 0;
+    // We scan the runs in visual order and set the mappings accordingly.
+    for (int i = 0; i < runs.length; i++)
+      {
+        Run run = runs[i];
+        if (run.isLeftToRight())
+          {
+            for (lIndex = run.runStart; lIndex < run.runEnd; lIndex++)
+              {
+                logicalToVisual[lIndex] = vIndex;
+                visualToLogical[vIndex] = lIndex;
+                vIndex++;
+              }
+          }
+        else
+          {
+            for (lIndex = run.runEnd - 1; lIndex >= run.runStart; lIndex--)
+              {
+                logicalToVisual[lIndex] = vIndex;
+                visualToLogical[vIndex] = lIndex;
+                vIndex++;
+              }
+          }
       }
   }
 
@@ -253,11 +393,11 @@ public final class TextLayout implements Cloneable
   private void getStringProperties()
   {
     boolean gotDirection = false;
-    int i = 0;
-
+    int i = offset;
+    int endOffs = offset + length;
     leftToRight = true;
-    while( i < string.length() && !gotDirection )
-      switch( Character.getDirectionality( string.charAt( i++ ) ) )
+    while( i < endOffs && !gotDirection )
+      switch( Character.getDirectionality(string[i++]) )
 	{
 	case Character.DIRECTIONALITY_LEFT_TO_RIGHT:
 	case Character.DIRECTIONALITY_LEFT_TO_RIGHT_EMBEDDING:
@@ -280,28 +420,30 @@ public final class TextLayout implements Cloneable
   {
     // Determine if there's whitespace in the thing.
     // Ignore trailing chars.
-    int i = string.length() - 1; 
+    int i = offset + length - 1; 
     hasWhitespace = false;
-    while( i >= 0 && Character.isWhitespace( string.charAt(i) ) )
+    while( i >= offset && Character.isWhitespace( string[i] ) )
       i--;
     // Check the remaining chars
-    while( i >= 0 )
-      if( Character.isWhitespace( string.charAt(i--) ) )
+    while( i >= offset )
+      if( Character.isWhitespace( string[i--] ) )
 	hasWhitespace = true;
   }
 
   protected Object clone ()
   {
-    return new TextLayout( string, font, frc );
+    return new TextLayout( this, 0, length);
   }
 
   public void draw (Graphics2D g2, float x, float y) 
   {    
     for(int i = 0; i < runs.length; i++)
       {
-	g2.drawGlyphVector(runs[i], x, y);
-	Rectangle2D r = runs[i].getLogicalBounds();
-	x += r.getWidth();
+        Run run = runs[i];
+        GlyphVector gv = run.glyphVector;
+        g2.drawGlyphVector(gv, x, y);
+        Rectangle2D r = gv.getLogicalBounds();
+        x += r.getWidth();
       }
   }
 
@@ -326,9 +468,16 @@ public final class TextLayout implements Cloneable
 
   public float getAdvance ()
   {
-    float totalAdvance = 0f;
-    for(int i = 0; i < runs.length; i++)
-      totalAdvance += runs[i].getLogicalBounds().getWidth();
+    if (totalAdvance == -1F)
+      {
+        totalAdvance = 0f;
+        for(int i = 0; i < runs.length; i++)
+          {
+            Run run = runs[i];
+            GlyphVector gv = run.glyphVector;
+            totalAdvance += gv.getLogicalBounds().getWidth();
+          }
+      }
     return totalAdvance;
   }
 
@@ -363,27 +512,33 @@ public final class TextLayout implements Cloneable
     double advance = 0;
    
     for( int i = 0; i < ri; i++ )
-      advance += runs[i].getLogicalBounds().getWidth();
+      {
+        Run run = runs[i];
+        GlyphVector gv = run.glyphVector;
+        advance += gv.getLogicalBounds().getWidth();
+      }
     
     for( int i = ri; i <= charIndices[ secondEndpoint - 1 ][0]; i++ )
       {
+        Run run = runs[i];
+        GlyphVector gv = run.glyphVector;
 	int dg;
 	if( i == charIndices[ secondEndpoint - 1 ][0] )
 	  dg = charIndices[ secondEndpoint - 1][1];
 	else
-	  dg = runs[i].getNumGlyphs() - 1;
+	  dg = gv.getNumGlyphs() - 1;
 
 	for( int j = 0; j <= dg; j++ )
 	  {
-	    Rectangle2D r2 = (runs[i].getGlyphVisualBounds( j )).
+	    Rectangle2D r2 = (gv.getGlyphVisualBounds( j )).
 	      getBounds2D();
-	    Point2D p = runs[i].getGlyphPosition( j );
+	    Point2D p = gv.getGlyphPosition( j );
 	    r2.setRect( advance + r2.getX(), r2.getY(), 
 			r2.getWidth(), r2.getHeight() );
 	    gp.append(r2, false);
 	  }
 
-	advance += runs[i].getLogicalBounds().getWidth();
+	advance += gv.getLogicalBounds().getWidth();
       }
     return gp;
   }
@@ -397,46 +552,138 @@ public final class TextLayout implements Cloneable
 
   public float[] getCaretInfo (TextHitInfo hit)
   {
-    return getCaretInfo(hit, getBounds());
+    return getCaretInfo(hit, getNaturalBounds());
   }
 
   public float[] getCaretInfo (TextHitInfo hit, Rectangle2D bounds)
-    throws NotImplementedException
   {
-    throw new Error ("not implemented");
+    float[] info = new float[2];
+    int index = hit.getCharIndex();
+    boolean leading = hit.isLeadingEdge();
+    // For the boundary cases we return the boundary runs.
+    Run run;
+    
+    if (index >= length)
+      {
+        info[0] = getAdvance();
+        info[1] = 0;
+      }
+    else
+      {
+        if (index < 0)
+          {
+            run = runs[0];
+            index = 0;
+            leading = true;
+          }
+        else
+          run = findRunAtIndex(index);
+
+        int glyphIndex = index - run.runStart;
+        Shape glyphBounds = run.glyphVector.getGlyphLogicalBounds(glyphIndex);
+        Rectangle2D glyphRect = glyphBounds.getBounds2D();
+        if (isVertical())
+          {
+            if (leading)
+              info[0] = (float) glyphRect.getMinY();
+            else
+              info[0] = (float) glyphRect.getMaxY();
+          }
+        else
+          {
+            if (leading)
+              info[0] = (float) glyphRect.getMinX();
+            else
+              info[0] = (float) glyphRect.getMaxX();
+          }
+        info[0] += run.location;
+        info[1] = run.font.getItalicAngle();
+      }
+    return info;
   }
 
-  public Shape getCaretShape (TextHitInfo hit)
+  public Shape getCaretShape(TextHitInfo hit)
   {
-    return getCaretShape( hit, getBounds() );
+    return getCaretShape(hit, getBounds());
   }
 
-  public Shape getCaretShape (TextHitInfo hit, Rectangle2D bounds)
-    throws NotImplementedException
+  public Shape getCaretShape(TextHitInfo hit, Rectangle2D bounds)
   {
-    throw new Error ("not implemented");
+    // TODO: Handle vertical shapes somehow.
+    float[] info = getCaretInfo(hit);
+    float x1 = info[0];
+    float y1 = (float) bounds.getMinY();
+    float x2 = info[0];
+    float y2 = (float) bounds.getMaxY();
+    if (info[1] != 0)
+      {
+        // Shift x1 and x2 according to the slope.
+        x1 -= y1 * info[1];
+        x2 -= y2 * info[1];
+      }
+    GeneralPath path = new GeneralPath(GeneralPath.WIND_EVEN_ODD, 2);
+    path.moveTo(x1, y1);
+    path.lineTo(x2, y2);
+    return path;
   }
 
-  public Shape[] getCaretShapes (int offset)
+  public Shape[] getCaretShapes(int offset)
   {
-    return getCaretShapes( offset, getBounds() );
+    return getCaretShapes(offset, getNaturalBounds());
   }
 
-  public Shape[] getCaretShapes (int offset, Rectangle2D bounds)
-    throws NotImplementedException
+  public Shape[] getCaretShapes(int offset, Rectangle2D bounds)
   {
-    throw new Error ("not implemented");
+    return getCaretShapes(offset, bounds, DEFAULT_CARET_POLICY);
+  }
+
+  public Shape[] getCaretShapes(int offset, Rectangle2D bounds,
+                                CaretPolicy policy)
+  {
+    // The RI returns a 2-size array even when there's only one
+    // shape in it.
+    Shape[] carets = new Shape[2];
+    TextHitInfo hit1 = TextHitInfo.afterOffset(offset);
+    int caretHit1 = hitToCaret(hit1);
+    TextHitInfo hit2 = hit1.getOtherHit();
+    int caretHit2 = hitToCaret(hit2);
+    if (caretHit1 == caretHit2)
+      {
+        carets[0] = getCaretShape(hit1);
+        carets[1] = null; // The RI returns null in this seldom case.
+      }
+    else
+      {
+        Shape caret1 = getCaretShape(hit1);
+        Shape caret2 = getCaretShape(hit2);
+        TextHitInfo strong = policy.getStrongCaret(hit1, hit2, this);
+        if (strong == hit1)
+          {
+            carets[0] = caret1;
+            carets[1] = caret2;
+          }
+        else
+          {
+            carets[0] = caret2;
+            carets[1] = caret1;
+          }
+      }
+    return carets;
   }
 
   public int getCharacterCount ()
   {
-    return string.length();
+    return length;
   }
 
   public byte getCharacterLevel (int index)
-    throws NotImplementedException
   {
-    throw new Error ("not implemented");
+    byte level;
+    if( bidi == null )
+      level = 0;
+    else
+      level = (byte) bidi.getLevelAt(index);
+    return level;
   }
 
   public float getDescent ()
@@ -481,19 +728,21 @@ public final class TextLayout implements Cloneable
     double advance = 0;
    
     for( int i = 0; i < ri; i++ )
-      advance += runs[i].getLogicalBounds().getWidth();
+      advance += runs[i].glyphVector.getLogicalBounds().getWidth();
 
     for( int i = ri; i <= charIndices[ secondEndpoint - 1 ][0]; i++ )
       {
+        Run run = runs[i];
+        GlyphVector gv = run.glyphVector;
 	int dg; // last index in this run to use.
 	if( i == charIndices[ secondEndpoint - 1 ][0] )
 	  dg = charIndices[ secondEndpoint - 1][1];
 	else
-	  dg = runs[i].getNumGlyphs() - 1;
+	  dg = gv.getNumGlyphs() - 1;
 
 	for(; gi <= dg; gi++ )
 	  {
-	    Rectangle2D r2 = (runs[i].getGlyphLogicalBounds( gi )).
+	    Rectangle2D r2 = (gv.getGlyphLogicalBounds( gi )).
 	      getBounds2D();
 	    if( r == null )
 	      r = r2;
@@ -502,7 +751,7 @@ public final class TextLayout implements Cloneable
 	  }
 	gi = 0; // reset glyph index into run for next run.
 
-	advance += runs[i].getLogicalBounds().getWidth();
+	advance += gv.getLogicalBounds().getWidth();
       }
 
     return r;
@@ -510,33 +759,137 @@ public final class TextLayout implements Cloneable
 
   public int[] getLogicalRangesForVisualSelection (TextHitInfo firstEndpoint,
                                                    TextHitInfo secondEndpoint)
-    throws NotImplementedException
   {
-    throw new Error ("not implemented");
+    // Check parameters.
+    checkHitInfo(firstEndpoint);
+    checkHitInfo(secondEndpoint);
+
+    // Convert to visual and order correctly.
+    int start = hitToCaret(firstEndpoint);
+    int end = hitToCaret(secondEndpoint);
+    if (start > end)
+      {
+        // Swap start and end so that end >= start.
+        int temp = start;
+        start = end;
+        end = temp;
+      }
+
+    // Now walk through the visual indices and mark the included pieces.
+    boolean[] include = new boolean[length];
+    for (int i = start; i < end; i++)
+      {
+        include[visualToLogical[i]] = true;
+      }
+
+    // Count included runs.
+    int numRuns = 0;
+    boolean in = false;
+    for (int i = 0; i < length; i++)
+      {
+        if (include[i] != in) // At each run in/out point we toggle the in var.
+          {
+            in = ! in;
+            if (in) // At each run start we count up.
+              numRuns++;
+          }
+      }
+
+    // Put together the ranges array.
+    int[] ranges = new int[numRuns * 2];
+    int index = 0;
+    in = false;
+    for (int i = 0; i < length; i++)
+      {
+        if (include[i] != in)
+          {
+            ranges[index] = i;
+            index++;
+            in = ! in;
+          }
+      }
+    // If the last run ends at the very end, include that last bit too.
+    if (in)
+      ranges[index] = length;
+
+    return ranges;
+  }
+
+  public TextHitInfo getNextLeftHit(int offset)
+  {
+    return getNextLeftHit(offset, DEFAULT_CARET_POLICY);
   }
 
-  public TextHitInfo getNextLeftHit (int offset)
-    throws NotImplementedException
+  public TextHitInfo getNextLeftHit(int offset, CaretPolicy policy)
   {
-    throw new Error ("not implemented");
+    if (policy == null)
+      throw new IllegalArgumentException("Null policy not allowed");
+    if (offset < 0 || offset > length)
+      throw new IllegalArgumentException("Offset out of bounds");
+
+    TextHitInfo hit1 = TextHitInfo.afterOffset(offset);
+    TextHitInfo hit2 = hit1.getOtherHit();
+
+    TextHitInfo strong = policy.getStrongCaret(hit1, hit2, this);
+    TextHitInfo next = getNextLeftHit(strong);
+    TextHitInfo ret = null;
+    if (next != null)
+      {
+        TextHitInfo next2 = getVisualOtherHit(next);
+        ret = policy.getStrongCaret(next2, next, this);
+      }
+    return ret;
   }
 
   public TextHitInfo getNextLeftHit (TextHitInfo hit)
-    throws NotImplementedException
   {
-    throw new Error ("not implemented");
+    checkHitInfo(hit);
+    int index = hitToCaret(hit);
+    TextHitInfo next = null;
+    if (index != 0)
+      {
+        index--;
+        next = caretToHit(index);
+      }
+    return next;
   }
 
-  public TextHitInfo getNextRightHit (int offset)
-    throws NotImplementedException
+  public TextHitInfo getNextRightHit(int offset)
   {
-    throw new Error ("not implemented");
+    return getNextRightHit(offset, DEFAULT_CARET_POLICY);
   }
 
-  public TextHitInfo getNextRightHit (TextHitInfo hit)
-    throws NotImplementedException
+  public TextHitInfo getNextRightHit(int offset, CaretPolicy policy)
   {
-    throw new Error ("not implemented");
+    if (policy == null)
+      throw new IllegalArgumentException("Null policy not allowed");
+    if (offset < 0 || offset > length)
+      throw new IllegalArgumentException("Offset out of bounds");
+
+    TextHitInfo hit1 = TextHitInfo.afterOffset(offset);
+    TextHitInfo hit2 = hit1.getOtherHit();
+
+    TextHitInfo next = getNextRightHit(policy.getStrongCaret(hit1, hit2, this));
+    TextHitInfo ret = null;
+    if (next != null)
+      {
+        TextHitInfo next2 = getVisualOtherHit(next);
+        ret = policy.getStrongCaret(next2, next, this);
+      }
+    return ret;
+  }
+
+  public TextHitInfo getNextRightHit(TextHitInfo hit)
+  {
+    checkHitInfo(hit);
+    int index = hitToCaret(hit);
+    TextHitInfo next = null;
+    if (index < length)
+      {
+        index++;
+        next = caretToHit(index);
+      }
+    return next;
   }
 
   public Shape getOutline (AffineTransform tx)
@@ -545,8 +898,9 @@ public final class TextLayout implements Cloneable
     GeneralPath gp = new GeneralPath();
     for(int i = 0; i < runs.length; i++)
       {
-	gp.append( runs[i].getOutline( x, 0f ), false );
-	Rectangle2D r = runs[i].getLogicalBounds();
+        GlyphVector gv = runs[i].glyphVector;
+	gp.append( gv.getOutline( x, 0f ), false );
+	Rectangle2D r = gv.getLogicalBounds();
 	x += r.getWidth();
       }
     if( tx != null )
@@ -562,27 +916,28 @@ public final class TextLayout implements Cloneable
       return 0f;
 
     // No trailing whitespace
-    if( !Character.isWhitespace( string.charAt( string.length() -1 ) ) )
+    if( !Character.isWhitespace( string[offset + length - 1]) )
       return getAdvance();
 
     // Get length of all runs up to the last
     for(int i = 0; i < runs.length - 1; i++)
-      totalAdvance += runs[i].getLogicalBounds().getWidth();
+      totalAdvance += runs[i].glyphVector.getLogicalBounds().getWidth();
 
-    int lastRun = runIndices[ runs.length - 1 ][0];
-    int j = string.length() - 1;
-    while( j >= lastRun && Character.isWhitespace( string.charAt( j ) ) ) j--;
+    int lastRun = runs[runs.length - 1].runStart;
+    int j = length - 1;
+    while( j >= lastRun && Character.isWhitespace( string[j] ) ) j--;
 
     if( j < lastRun )
       return totalAdvance; // entire last run is whitespace
 
     int lastNonWSChar = j - lastRun;
     j = 0;
-    while( runs[ runs.length - 1 ].getGlyphCharIndex( j )
+    while( runs[ runs.length - 1 ].glyphVector.getGlyphCharIndex( j )
 	   <= lastNonWSChar )
       {
-	totalAdvance += runs[ runs.length - 1 ].getGlyphLogicalBounds( j ).
-	  getBounds2D().getWidth();
+	totalAdvance += runs[ runs.length - 1 ].glyphVector
+                                               .getGlyphLogicalBounds( j )
+                                               .getBounds2D().getWidth();
 	j ++;
       }
     
@@ -599,15 +954,129 @@ public final class TextLayout implements Cloneable
   public Shape getVisualHighlightShape (TextHitInfo firstEndpoint,
                                         TextHitInfo secondEndpoint,
                                         Rectangle2D bounds)
-    throws NotImplementedException
   {
-    throw new Error ("not implemented");
+    GeneralPath path = new GeneralPath(GeneralPath.WIND_EVEN_ODD);
+    Shape caret1 = getCaretShape(firstEndpoint, bounds);
+    path.append(caret1, false);
+    Shape caret2 = getCaretShape(secondEndpoint, bounds);
+    path.append(caret2, false);
+    // Append left (top) bounds to selection if necessary.
+    int c1 = hitToCaret(firstEndpoint);
+    int c2 = hitToCaret(secondEndpoint);
+    if (c1 == 0 || c2 == 0)
+      {
+        path.append(left(bounds), false);
+      }
+    // Append right (bottom) bounds if necessary.
+    if (c1 == length || c2 == length)
+      {
+        path.append(right(bounds), false);
+      }
+    return path.getBounds2D();
+  }
+
+  /**
+   * Returns the shape that makes up the left (top) edge of this text layout.
+   *
+   * @param b the bounds
+   *
+   * @return the shape that makes up the left (top) edge of this text layout
+   */
+  private Shape left(Rectangle2D b)
+  {
+    GeneralPath left = new GeneralPath(GeneralPath.WIND_EVEN_ODD);
+    left.append(getCaretShape(TextHitInfo.beforeOffset(0)), false);
+    if (isVertical())
+      {
+        float y = (float) b.getMinY();
+        left.append(new Line2D.Float((float) b.getMinX(), y,
+                                     (float) b.getMaxX(), y), false);
+      }
+    else
+      {
+        float x = (float) b.getMinX();
+        left.append(new Line2D.Float(x, (float) b.getMinY(),
+                                     x, (float) b.getMaxY()), false);
+      }
+    return left.getBounds2D();
+  }
+
+  /**
+   * Returns the shape that makes up the right (bottom) edge of this text
+   * layout.
+   *
+   * @param b the bounds
+   *
+   * @return the shape that makes up the right (bottom) edge of this text
+   *         layout
+   */
+  private Shape right(Rectangle2D b)
+  {
+    GeneralPath right = new GeneralPath(GeneralPath.WIND_EVEN_ODD);
+    right.append(getCaretShape(TextHitInfo.afterOffset(length)), false);
+    if (isVertical())
+      {
+        float y = (float) b.getMaxY();
+        right.append(new Line2D.Float((float) b.getMinX(), y,
+                                      (float) b.getMaxX(), y), false);
+      }
+    else
+      {
+        float x = (float) b.getMaxX();
+        right.append(new Line2D.Float(x, (float) b.getMinY(),
+                                      x, (float) b.getMaxY()), false);
+      }
+    return right.getBounds2D();
   }
 
   public TextHitInfo getVisualOtherHit (TextHitInfo hit)
-    throws NotImplementedException
   {
-    throw new Error ("not implemented");
+    checkHitInfo(hit);
+    int hitIndex = hit.getCharIndex();
+
+    int index;
+    boolean leading;
+    if (hitIndex == -1 || hitIndex == length)
+      {
+        // Boundary case.
+        int visual;
+        if (isLeftToRight() == (hitIndex == -1))
+          visual = 0;
+        else
+          visual = length - 1;
+        index = visualToLogical[visual];
+        if (isLeftToRight() == (hitIndex == -1))
+          leading = isCharacterLTR(index); // LTR.
+        else
+          leading = ! isCharacterLTR(index); // RTL.
+      }
+    else
+      {
+        // Normal case.
+        int visual = logicalToVisual[hitIndex];
+        boolean b;
+        if (isCharacterLTR(hitIndex) == hit.isLeadingEdge())
+          {
+            visual--;
+            b = false;
+          }
+        else
+          {
+            visual++;
+            b = true;
+          }
+        if (visual >= 0 && visual < length)
+          {
+            index = visualToLogical[visual];
+            leading = b == isLeftToRight();
+          }
+        else
+          {
+            index = b == isLeftToRight() ? length : -1;
+            leading = index == length;
+          }
+      }
+    return leading ? TextHitInfo.leading(index) : TextHitInfo.trailing(index);
   }
 
   /**
@@ -622,16 +1091,19 @@ public final class TextLayout implements Cloneable
     int nglyphs = 0; // # of whitespace chars
 
     // determine last non-whitespace char.
-    int lastNWS = string.length() - 1;
-    while( Character.isWhitespace( string.charAt( lastNWS ) ) ) lastNWS--;
+    int lastNWS = offset + length - 1;
+    while( Character.isWhitespace( string[lastNWS] ) ) lastNWS--;
 
     // locations of the glyphs.
-    int[] wsglyphs = new int[string.length() * 10];
+    int[] wsglyphs = new int[length * 10];
     for(int run = 0; run < runs.length; run++ )
-      for(int i = 0; i < runs[run].getNumGlyphs(); i++ )
+      {
+      Run current = runs[run];
+      for(int i = 0; i < current.glyphVector.getNumGlyphs(); i++ )
 	{
-	  int cindex = runIndices[run][0] + runs[run].getGlyphCharIndex( i );
-	  if( Character.isWhitespace( string.charAt( cindex ) ) )
+	  int cindex = current.runStart
+                       + current.glyphVector.getGlyphCharIndex( i );
+	  if( Character.isWhitespace( string[cindex] ) )
 	    //	      && cindex < lastNWS )
 	    {
 	      wsglyphs[ nglyphs * 2 ] = run;
@@ -639,34 +1111,144 @@ public final class TextLayout implements Cloneable
 	      nglyphs++;
 	    }
 	}
-
+      }
     deltaW = deltaW / nglyphs; // Change in width per whitespace glyph
     double w = 0;
     int cws = 0;
     // Shift all characters
     for(int run = 0; run < runs.length; run++ )
-      for(int i = 0; i < runs[ run ].getNumGlyphs(); i++ )
-	{
-	  if( wsglyphs[ cws * 2 ] == run && wsglyphs[ cws * 2 + 1 ] == i )
-	    {
-	      cws++; // update 'current whitespace'
-	      w += deltaW; // increment the shift
-	    }
-	  Point2D p = runs[ run ].getGlyphPosition( i );
-	  p.setLocation( p.getX() + w, p.getY() );
-	  runs[ run ].setGlyphPosition( i, p );
-	}
+      {
+        Run current = runs[run];
+        for(int i = 0; i < current.glyphVector.getNumGlyphs(); i++ )
+          {
+            if( wsglyphs[ cws * 2 ] == run && wsglyphs[ cws * 2 + 1 ] == i )
+              {
+                cws++; // update 'current whitespace'
+                w += deltaW; // increment the shift
+              }
+            Point2D p = current.glyphVector.getGlyphPosition( i );
+            p.setLocation( p.getX() + w, p.getY() );
+            current.glyphVector.setGlyphPosition( i, p );
+          }
+      }
   }
 
   public TextHitInfo hitTestChar (float x, float y)
   {
-    return hitTestChar(x, y, getBounds());
+    return hitTestChar(x, y, getNaturalBounds());
   }
 
+  /**
+   * Finds the character hit at the specified point. This 'clips' this
+   * text layout against the specified <code>bounds</code> rectangle. That
+   * means that in the case where a point is outside these bounds, this method
+   * returns the leading edge of the first character or the trailing edge of
+   * the last character.
+   *
+   * @param x the X location to test
+   * @param y the Y location to test
+   * @param bounds the bounds to test against
+   *
+   * @return the character hit at the specified point
+   */
   public TextHitInfo hitTestChar (float x, float y, Rectangle2D bounds)
-    throws NotImplementedException
   {
-    throw new Error ("not implemented");
+    // Check bounds.
+    if (isVertical())
+      {
+        if (y < bounds.getMinY())
+          return TextHitInfo.leading(0);
+        else if (y > bounds.getMaxY())
+          return TextHitInfo.trailing(getCharacterCount() - 1);
+      }
+    else
+      {
+        if (x < bounds.getMinX())
+          return TextHitInfo.leading(0);
+        else if (x > bounds.getMaxX())
+          return TextHitInfo.trailing(getCharacterCount() - 1);
+      }
+
+    TextHitInfo hitInfo = null;
+    if (isVertical())
+      {
+        // Search for the run at the location.
+        // TODO: Perform binary search for maximum efficiency. However, we
+        // need the run location laid out statically to do that.
+        int numRuns = runs.length;
+        Run hitRun = null;
+        for (int i = 0; i < numRuns && hitRun == null; i++)
+          {
+            Run run = runs[i];
+            Rectangle2D lBounds = run.glyphVector.getLogicalBounds();
+            if (lBounds.getMinY() + run.location <= y
+                && lBounds.getMaxY() + run.location >= y)
+              hitRun = run;
+          }
+        // Now we have (hopefully) found a run that hits. Now find the
+        // right character.
+        if (hitRun != null)
+          {
+            GlyphVector gv = hitRun.glyphVector;
+            for (int i = hitRun.runStart;
+                 i < hitRun.runEnd && hitInfo == null; i++)
+              {
+                int gi = i - hitRun.runStart;
+                Rectangle2D lBounds = gv.getGlyphLogicalBounds(gi)
+                                      .getBounds2D();
+                if (lBounds.getMinY() + hitRun.location <= y
+                    && lBounds.getMaxY() + hitRun.location >= y)
+                  {
+                    // Found hit. Now check if we are leading or trailing.
+                    boolean leading = true;
+                    if (lBounds.getCenterY() + hitRun.location <= y)
+                      leading = false;
+                    hitInfo = leading ? TextHitInfo.leading(i)
+                                      : TextHitInfo.trailing(i);
+                  }
+              }
+          }
+      }
+    else
+      {
+        // Search for the run at the location.
+        // TODO: Perform binary search for maximum efficiency. However, we
+        // need the run location laid out statically to do that.
+        int numRuns = runs.length;
+        Run hitRun = null;
+        for (int i = 0; i < numRuns && hitRun == null; i++)
+          {
+            Run run = runs[i];
+            Rectangle2D lBounds = run.glyphVector.getLogicalBounds();
+            if (lBounds.getMinX() + run.location <= x
+                && lBounds.getMaxX() + run.location >= x)
+              hitRun = run;
+          }
+        // Now we have (hopefully) found a run that hits. Now find the
+        // right character.
+        if (hitRun != null)
+          {
+            GlyphVector gv = hitRun.glyphVector;
+            for (int i = hitRun.runStart;
+                 i < hitRun.runEnd && hitInfo == null; i++)
+              {
+                int gi = i - hitRun.runStart;
+                Rectangle2D lBounds = gv.getGlyphLogicalBounds(gi)
+                                      .getBounds2D();
+                if (lBounds.getMinX() + hitRun.location <= x
+                    && lBounds.getMaxX() + hitRun.location >= x)
+                  {
+                    // Found hit. Now check if we are leading or trailing.
+                    boolean leading = true;
+                    if (lBounds.getCenterX() + hitRun.location <= x)
+                      leading = false;
+                    hitInfo = leading ? TextHitInfo.leading(i)
+                                      : TextHitInfo.trailing(i);
+                  }
+              }
+          }
+      }
+    return hitInfo;
   }
 
   public boolean isLeftToRight ()
@@ -680,18 +1262,127 @@ public final class TextLayout implements Cloneable
   }
 
   public int hashCode ()
-    throws NotImplementedException
   {
-    throw new Error ("not implemented");
+    // This is implemented in sync to equals().
+    if (hash == 0 && runs.length > 0)
+      {
+        hash = runs.length;
+        for (int i = 0; i < runs.length; i++)
+          hash ^= runs[i].glyphVector.hashCode();
+      }
+    return hash;
   }
 
   public String toString ()
   {
-    return "TextLayout [string:"+string+", Font:"+font+" Rendercontext:"+
+    return "TextLayout [string:"+ new String(string, offset, length)
+    +" Rendercontext:"+
       frc+"]";
   }
 
   /**
+   * Returns the natural bounds of that text layout. This is made up
+   * of the ascent plus descent and the text advance.
+   *
+   * @return the natural bounds of that text layout
+   */
+  private Rectangle2D getNaturalBounds()
+  {
+    if (naturalBounds == null)
+      naturalBounds = new Rectangle2D.Float(0.0F, -getAscent(), getAdvance(),
+                                            getAscent() + getDescent());
+    return naturalBounds;
+  }
+
+  private void checkHitInfo(TextHitInfo hit)
+  {
+    if (hit == null)
+      throw new IllegalArgumentException("Null hit info not allowed");
+    int index = hit.getInsertionIndex();
+    if (index < 0 || index > length)
+      throw new IllegalArgumentException("Hit index out of range");
+  }
+
+  private int hitToCaret(TextHitInfo hit)
+  {
+    int index = hit.getCharIndex();
+    int ret;
+    if (index < 0)
+      ret = isLeftToRight() ? 0 : length;
+    else if (index >= length)
+      ret = isLeftToRight() ? length : 0;
+    else
+      {
+        ret = logicalToVisual[index];
+        if (hit.isLeadingEdge() != isCharacterLTR(index))
+          ret++;
+      }
+    return ret;
+  }
+
+  private TextHitInfo caretToHit(int index)
+  {
+    TextHitInfo hit;
+    if (index == 0 || index == length)
+      {
+        if ((index == length) == isLeftToRight())
+          hit = TextHitInfo.leading(length);
+        else
+          hit = TextHitInfo.trailing(-1);
+      }
+    else
+      {
+        int logical = visualToLogical[index];
+        boolean leading = isCharacterLTR(logical); // LTR.
+        hit = leading ? TextHitInfo.leading(logical)
+                      : TextHitInfo.trailing(logical);
+      }
+    return hit;
+  }
+
+  private boolean isCharacterLTR(int index)
+  {
+    byte level = getCharacterLevel(index);
+    return (level & 1) == 0;
+  }
+
+  /**
+   * Finds the run that holds the specified (logical) character index. This
+   * returns <code>null</code> when the index is not inside the range.
+   *
+   * @param index the index of the character to find
+   *
+   * @return the run that holds the specified character
+   */
+  private Run findRunAtIndex(int index)
+  {
+    Run found = null;
+    // TODO: Can we do better than linear searching here?
+    for (int i = 0; i < runs.length && found == null; i++)
+      {
+        Run run = runs[i];
+        if (run.runStart <= index && run.runEnd > index)
+          found = run;
+      }
+    return found;
+  }
+
+  /**
+   * Computes the layout locations for each run.
+   */
+  private void layoutRuns()
+  {
+    float loc = 0.0F;
+    float lastWidth = 0.0F;
+    for (int i = 0; i < runs.length; i++)
+      {
+        runs[i].location = loc;
+        Rectangle2D bounds = runs[i].glyphVector.getLogicalBounds();
+        loc += isVertical() ? bounds.getHeight() : bounds.getWidth();
+      }
+  }
+
+  /**
    * Inner class describing a caret policy
    */
   public static class CaretPolicy
@@ -703,9 +1394,25 @@ public final class TextLayout implements Cloneable
     public TextHitInfo getStrongCaret(TextHitInfo hit1,
 				      TextHitInfo hit2,
 				      TextLayout layout)
-      throws NotImplementedException
     {
-      throw new Error ("not implemented");
+      byte l1 = layout.getCharacterLevel(hit1.getCharIndex());
+      byte l2 = layout.getCharacterLevel(hit2.getCharIndex());
+      TextHitInfo strong;
+      if (l1 == l2)
+        {
+          if (hit2.isLeadingEdge() && ! hit1.isLeadingEdge())
+            strong = hit2;
+          else
+            strong = hit1;
+        }
+      else
+        {
+          if (l1 < l2)
+            strong = hit1;
+          else
+            strong = hit2;
+        }
+      return strong;
     }
   }
 }