/*
 * @(#)TextLayout.java	1.88 03/01/23
 *
 * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

/*
 * (C) Copyright Taligent, Inc. 1996 - 1997, All Rights Reserved
 * (C) Copyright IBM Corp. 1996 - 1998, All Rights Reserved
 *
 * The original version of this source code and documentation is
 * copyrighted and owned by Taligent, Inc., a wholly-owned subsidiary
 * of IBM. These materials are provided under terms of a License
 * Agreement between Taligent and Sun. This technology is protected
 * by multiple US and International patents.
 *
 * This notice and attribution to Taligent may not be removed.
 * Taligent is a registered trademark of Taligent, Inc.
 *
 */

package java.awt.font;

import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics2D;
import java.awt.Shape;
import java.awt.font.NumericShaper;
import java.awt.geom.AffineTransform;
import java.awt.geom.GeneralPath;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.text.AttributedString;
import java.text.AttributedCharacterIterator;
import java.util.Map;
import java.util.HashMap;
import java.util.Hashtable;
import sun.awt.font.AdvanceCache;
import sun.awt.font.Decoration;
import sun.awt.font.FontResolver;
import sun.awt.font.NativeFontWrapper;
import sun.java2d.SunGraphicsEnvironment;

/**
 * 
 * <code>TextLayout</code> is an immutable graphical representation of styled 
 * character data.
 * <p>
 * It provides the following capabilities:
 * <ul>
 * <li>implicit bidirectional analysis and reordering,
 * <li>cursor positioning and movement, including split cursors for
 * mixed directional text,
 * <li>highlighting, including both logical and visual highlighting
 * for mixed directional text,
 * <li>multiple baselines (roman, hanging, and centered),
 * <li>hit testing,
 * <li>justification,
 * <li>default font substitution,
 * <li>metric information such as ascent, descent, and advance, and
 * <li>rendering
 * </ul>
 * <p>
 * A <code>TextLayout</code> object can be rendered using 
 * its <code>draw</code> method.
 * <p>
 * <code>TextLayout</code> can be constructed either directly or through 
 * the use of a {@link LineBreakMeasurer}.  When constructed directly, the 
 * source text represents a single paragraph.  <code>LineBreakMeasurer</code>
 * allows styled text to be broken into lines that fit within a particular 
 * width.  See the <code>LineBreakMeasurer</code> documentation for more
 * information.
 * <p>
 * <code>TextLayout</code> construction logically proceeds as follows:
 * <ul>
 * <li>paragraph attributes are extracted and examined,
 * <li>text is analyzed for bidirectional reordering, and reordering
 * information is computed if needed,
 * <li>text is segmented into style runs
 * <li>fonts are chosen for style runs, first by using a font if the
 * attribute {@link TextAttribute#FONT} is present, otherwise by computing
 * a default font using the attributes that have been defined
 * <li>if text is on multiple baselines, the runs or subruns are further
 * broken into subruns sharing a common baseline,
 * <li>glyphvectors are generated for each run using the chosen font,
 * <li>final bidirectional reordering is performed on the glyphvectors
 * </ul>
 * <p>
 * All graphical information returned from a <code>TextLayout</code> 
 * object's methods is relative to the origin of the 
 * <code>TextLayout</code>, which is the intersection of the
 * <code>TextLayout</code> object's baseline with its left edge.  Also, 
 * coordinates passed into a <code>TextLayout</code> object's methods 
 * are assumed to be relative to the <code>TextLayout</code> object's
 * origin.  Clients usually need to translate between a 
 * <code>TextLayout</code> object's coordinate system and the coordinate
 * system in another object (such as a 
 * {@link java.awt.Graphics Graphics} object).
 * <p>
 * <code>TextLayout</code> objects are constructed from styled text, 
 * but they do not retain a reference to their source text.  Thus, 
 * changes in the text previously used to generate a <code>TextLayout</code>
 * do not affect the <code>TextLayout</code>.
 * <p>
 * Three methods on a <code>TextLayout</code> object 
 * (<code>getNextRightHit</code>, <code>getNextLeftHit</code>, and 
 * <code>hitTestChar</code>) return instances of {@link TextHitInfo}.  
 * The offsets contained in these <code>TextHitInfo</code> objects
 * are relative to the start of the <code>TextLayout</code>, <b>not</b> 
 * to the text used to create the <code>TextLayout</code>.  Similarly, 
 * <code>TextLayout</code> methods that accept <code>TextHitInfo</code>
 * instances as parameters expect the <code>TextHitInfo</code> object's 
 * offsets to be relative to the <code>TextLayout</code>, not to any 
 * underlying text storage model.
 * <p>
 * <strong>Examples</strong>:<p>
 * Constructing and drawing a <code>TextLayout</code> and its bounding 
 * rectangle:
 * <blockquote><pre>
 *   Graphics2D g = ...;
 *   Point2D loc = ...;
 *   Font font = Font.getFont("Helvetica-bold-italic");
 *   FontRenderContext frc = g.getFontRenderContext();
 *   TextLayout layout = new TextLayout("This is a string", font, frc);
 *   layout.draw(g, (float)loc.getX(), (float)loc.getY());
 *
 *   Rectangle2D bounds = layout.getBounds();
 *   bounds.setRect(bounds.getX()+loc.getX(),
 *                  bounds.getY()+loc.getY(),
 *                  bounds.getWidth(),
 *                  bounds.getHeight());
 *   g.draw(bounds);
 * </pre>
 * </blockquote>
 * <p>
 * Hit-testing a <code>TextLayout</code> (determining which character is at
 * a particular graphical location):
 * <blockquote><pre>
 *   Point2D click = ...;
 *   TextHitInfo hit = layout.hitTestChar(
 *                         (float) (click.getX() - loc.getX()),
 *                         (float) (click.getY() - loc.getY()));
 * </pre>
 * </blockquote>
 * <p>
 * Responding to a right-arrow key press:
 * <blockquote><pre>
 *   int insertionIndex = ...;
 *   TextHitInfo next = layout.getNextRightHit(insertionIndex);
 *   if (next != null) {
 *       // translate graphics to origin of layout on screen
 *       g.translate(loc.getX(), loc.getY());
 *       Shape[] carets = layout.getCaretShapes(next.getInsertionIndex());
 *       g.draw(carets[0]);
 *       if (carets[1] != null) {
 *           g.draw(carets[1]);
 *       }
 *   }
 * </pre></blockquote>
 * <p>
 * Drawing a selection range corresponding to a substring in the source text.
 * The selected area may not be visually contiguous:
 * <blockquote><pre>
 *   // selStart, selLimit should be relative to the layout,
 *   // not to the source text
 *
 *   int selStart = ..., selLimit = ...;
 *   Color selectionColor = ...;
 *   Shape selection = layout.getLogicalHighlightShape(selStart, selLimit);
 *   // selection may consist of disjoint areas
 *   // graphics is assumed to be tranlated to origin of layout
 *   g.setColor(selectionColor);
 *   g.fill(selection);
 * </pre></blockquote>
 * <p>
 * Drawing a visually contiguous selection range.  The selection range may
 * correspond to more than one substring in the source text.  The ranges of
 * the corresponding source text substrings can be obtained with
 * <code>getLogicalRangesForVisualSelection()</code>:
 * <blockquote><pre>
 *   TextHitInfo selStart = ..., selLimit = ...;
 *   Shape selection = layout.getVisualHighlightShape(selStart, selLimit);
 *   g.setColor(selectionColor);
 *   g.fill(selection);
 *   int[] ranges = getLogicalRangesForVisualSelection(selStart, selLimit);
 *   // ranges[0], ranges[1] is the first selection range,
 *   // ranges[2], ranges[3] is the second selection range, etc.
 * </pre></blockquote>
 * <p>
 * @see LineBreakMeasurer
 * @see TextAttribute
 * @see TextHitInfo
 */
public final class TextLayout implements Cloneable {

    private int characterCount;
    private boolean isVerticalLine = false;
    private byte baseline;
    private float[] baselineOffsets;  // why have these ?
    private TextLine textLine;

    // cached values computed from GlyphSets and set info:
    // all are recomputed from scratch in buildCache()
    private TextLine.TextLineMetrics lineMetrics = null;
    private float visibleAdvance;
    private int hashCodeCache;

    /**
     * temporary optimization
     */
    static class OptInfo implements Decoration.Label {
        private static final float MAGIC_ADVANCE = -12345.67f;

        // cache of required information for TextLine construction
        private FontRenderContext frc;
        private char[] chars;
        private Font font;
        private LineMetrics metrics;
        private Map attrs;

        // deferred initialization 
        private float advance;
	private Rectangle2D vb;
        private Decoration decoration;
        private String str;

        private OptInfo(FontRenderContext frc, char[] chars, Font font, LineMetrics metrics, Map attrs) {
            this.frc = frc;
            this.chars = chars;
            this.font = font;
            this.metrics = metrics;
            this.attrs = attrs;

	    if (attrs != null) {
		this.attrs = new HashMap(attrs); // sigh, need to clone since might change...
	    }

            this.advance = MAGIC_ADVANCE;
        }

        TextLine createTextLine() {
            return TextLine.fastCreateTextLine(frc, chars, font, metrics, attrs);
        }

        float getAdvance() {
            if (advance == MAGIC_ADVANCE) {
                AdvanceCache adv = AdvanceCache.get(font, frc);
                advance = adv.getAdvance(chars, 0, chars.length); // we pretested the chars array so no exception here
            }
            return advance;
        }

        // Decoration.Label reqd.
        public LineMetrics getLineMetrics() {
            return metrics;
        }

        // Decoration.Label reqd.
        public Rectangle2D getLogicalBounds() {
            return new Rectangle2D.Float(0, -metrics.getAscent(), getAdvance(), metrics.getHeight());
        }

        // Decoration.Label reqd.
        public void handleDraw(Graphics2D g2d, float x, float y) {
            if (str == null) {
                str = new String(chars, 0, chars.length);
            }
            g2d.drawString(str, x , y);
        }

        // Decoration.Label reqd.
        public Rectangle2D handleGetCharVisualBounds(int index) {
            // not used
            throw new InternalError();
        }

        // Decoration.Label reqd.
        public Rectangle2D handleGetVisualBounds() {
	    AdvanceCache adv = AdvanceCache.get(font, frc);
	    return adv.getVisualBounds(chars, 0, chars.length);
        }

        // Decoration.Label reqd.
        public Shape handleGetOutline(float x, float y) {
            // not used
            throw new InternalError();
        }

        // if we could successfully draw, then return true
        boolean draw(Graphics2D g2d, float x, float y) {
            // If the frc differs from the graphics frc, we punt to TextLayout because the
            // metrics might be different...
            if (g2d.getFontRenderContext().equals(frc)) {
                Font oldFont = g2d.getFont();
                g2d.setFont(font);
                    
                getDecoration().drawTextAndDecorations(this, g2d, x, y);

                g2d.setFont(oldFont);

                return true;
            }
            return false;
        }

	Rectangle2D getVisualBounds() {
	    if (vb == null) {
		vb = getDecoration().getVisualBounds(this);
	    }
	    return (Rectangle2D)vb.clone();
	}

	Decoration getDecoration() {
	    if (decoration == null) {
		if (attrs == null) {
		    decoration = Decoration.getDecoration(null);
		} else {
		    decoration = Decoration.getDecoration(StyledParagraph.addInputMethodAttrs(attrs));
		}
	    }
	    return decoration;
	}

        static OptInfo create(FontRenderContext frc, char[] chars, Font font, LineMetrics metrics, Map attrs) {
            // Preflight text to make sure advance cache supports it, otherwise it would throw an exception.
            // We also need to preflight to make sure we don't require layout.  If we limit optimizations to
            // latin-1 we handle both cases.  We could add an additional check for Japanese since currently
            // it doesn't require layout and the advance cache would be simple, but right now we don't.

            if (!font.isTransformed() && AdvanceCache.supportsText(chars)) {
		if (attrs == null || attrs.get(TextAttribute.CHAR_REPLACEMENT) == null) {
		    return new OptInfo(frc, chars, font, metrics, attrs);
		}
            }
            return null;
        }
    }
    private OptInfo optInfo;

    /*
     * TextLayouts are supposedly immutable.  If you mutate a TextLayout under
     * the covers (like the justification code does) you'll need to set this
     * back to false.  Could be replaced with textLine != null <--> cacheIsValid.
     */
    private boolean cacheIsValid = false;


    // This value is obtained from an attribute, and constrained to the
    // interval [0,1].  If 0, the layout cannot be justified.
    private float justifyRatio;

    // If a layout is produced by justification, then that layout
    // cannot be justified.  To enforce this constraint the
    // justifyRatio of the justified layout is set to this value.
    private static final float ALREADY_JUSTIFIED = -53.9f;

    // dx and dy specify the distance between the TextLayout's origin
    // and the origin of the leftmost GlyphSet (TextLayoutComponent,
    // actually).  They were used for hanging punctuation support,
    // which is no longer implemented.  Currently they are both always 0,
    // and TextLayout is not guaranteed to work with non-zero dx, dy
    // values right now.  They were left in as an aide and reminder to
    // anyone who implements hanging punctuation or other similar stuff.
    // They are static now so they don't take up space in TextLayout
    // instances.
    private static float dx;
    private static float dy;

    /*
     * Natural bounds is used internally.  It is built on demand in
     * getNaturalBounds.
     */
    private Rectangle2D naturalBounds = null;

    /*
     * boundsRect encloses all of the bits this TextLayout can draw.  It
     * is build on demand in getBounds.
     */
    private Rectangle2D boundsRect = null;

    /*
     * flag to supress/allow carets inside of ligatures when hit testing or
     * arrow-keying
     */
    private boolean caretsInLigaturesAreAllowed = false;

    /**
     * Defines a policy for determining the strong caret location.
     * This class contains one method, <code>getStrongCaret</code>, which
     * is used to specify the policy that determines the strong caret in 
     * dual-caret text.  The strong caret is used to move the caret to the
     * left or right. Instances of this class can be passed to
     * <code>getCaretShapes</code>, <code>getNextLeftHit</code> and 
     * <code>getNextRightHit</code> to customize strong caret
     * selection.
     * <p>
     * To specify alternate caret policies, subclass <code>CaretPolicy</code>
     * and override <code>getStrongCaret</code>.  <code>getStrongCaret</code>
     * should inspect the two <code>TextHitInfo</code> arguments and choose
     * one of them as the strong caret.
     * <p>
     * Most clients do not need to use this class.
     */
    public static class CaretPolicy {

        /**
         * Constructs a <code>CaretPolicy</code>.
         */
         public CaretPolicy() {
         }

        /**
         * Chooses one of the specified <code>TextHitInfo</code> instances as 
         * a strong caret in the specified <code>TextLayout</code>.
         * @param hit1 a valid hit in <code>layout</code>
         * @param hit2 a valid hit in <code>layout</code>
         * @param layout the <code>TextLayout</code> in which 
         *        <code>hit1</code> and <code>hit2</code> are used
         * @return <code>hit1</code> or <code>hit2</code>
         *        (or an equivalent <code>TextHitInfo</code>), indicating the
         *        strong caret.
         */
        public TextHitInfo getStrongCaret(TextHitInfo hit1,
                                          TextHitInfo hit2,
                                          TextLayout layout) {

            // default implmentation just calls private method on layout
            return layout.getStrongHit(hit1, hit2);
        }
    }

    /**
     * This <code>CaretPolicy</code> is used when a policy is not specified 
     * by the client.  With this policy, a hit on a character whose direction
     * is the same as the line direction is stronger than a hit on a
     * counterdirectional character.  If the characters' directions are
     * the same, a hit on the leading edge of a character is stronger
     * than a hit on the trailing edge of a character.
     */
    public static final CaretPolicy DEFAULT_CARET_POLICY = new CaretPolicy();

    /**
     * Constructs a <code>TextLayout</code> from a <code>String</code>
     * and a {@link Font}.  All the text is styled using the specified
     * <code>Font</code>.
     * <p>
     * The <code>String</code> must specify a single paragraph of text, 
     * because an entire paragraph is required for the bidirectional
     * algorithm.
     * @param string the text to display
     * @param font a <code>Font</code> used to style the text
     * @param frc contains information about a graphics device which is needed 
     *       to measure the text correctly.
     *       Text measurements can vary slightly depending on the
     *       device resolution, and attributes such as antialiasing.  This
     *       parameter does not specify a translation between the
     *       <code>TextLayout</code> and user space.
     */
    public TextLayout(String string, Font font, FontRenderContext frc) {

        if (font == null) {
            throw new IllegalArgumentException("Null font passed to TextLayout constructor.");
        }

        if (string == null) {
            throw new IllegalArgumentException("Null string passed to TextLayout constructor.");
        }

        if (string.length() == 0) {
            throw new IllegalArgumentException("Zero length string passed to TextLayout constructor.");
        }

        char[] text = string.toCharArray();
        if (sameBaselineUpTo(font, text, 0, text.length) == text.length) {
            fastInit(text, font, null, frc);
        } else {
            AttributedString as = new AttributedString(string);
            as.addAttribute(TextAttribute.FONT, font);
            standardInit(as.getIterator(), text, frc);
        }
    }

    /**
     * Constructs a <code>TextLayout</code> from a <code>String</code>
     * and an attribute set.
     * <p>
     * All the text is styled using the provided attributes.
     * <p>
     * <code>string</code> must specify a single paragraph of text because an
     * entire paragraph is required for the bidirectional algorithm.
     * @param string the text to display
     * @param attributes the attributes used to style the text
     * @param frc contains information about a graphics device which is needed 
     *       to measure the text correctly.
     *       Text measurements can vary slightly depending on the
     *       device resolution, and attributes such as antialiasing.  This
     *       parameter does not specify a translation between the
     *       <code>TextLayout</code> and user space.
     */
    public TextLayout(String string, Map attributes, FontRenderContext frc) {

        if (string == null) {
            throw new IllegalArgumentException("Null string passed to TextLayout constructor.");
        }

        if (attributes == null) {
            throw new IllegalArgumentException("Null map passed to TextLayout constructor.");
        }

        if (string.length() == 0) {
            throw new IllegalArgumentException("Zero length string passed to TextLayout constructor.");
        }

        char[] text = string.toCharArray();
        Font font = singleFont(text, 0, text.length, attributes);
        if (font != null) {
            fastInit(text, font, attributes, frc);
        } else {
            AttributedString as = new AttributedString(string, attributes);
            standardInit(as.getIterator(), text, frc);
        }
    }

    /*
     * Determines a font for the attributes, and if a single font can render
     * all the text on one baseline, return it, otherwise null.  If the 
     * attributes specify a font, assume it can display all the text without 
     * checking.
     * If the AttributeSet contains an embedded graphic, return null.
     */
    private static Font singleFont(char[] text,
                                   int start,
                                   int limit,
                                   Map attributes) {

        if (attributes.get(TextAttribute.CHAR_REPLACEMENT) != null) {
            return null;
        }

        Font font = (Font)attributes.get(TextAttribute.FONT);
        if (font == null) {
            if (attributes.get(TextAttribute.FAMILY) != null) {            
                font = Font.getFont(attributes);
                if (font.canDisplayUpTo(text, start, limit) != -1) {
                    return null;
                }
            }
            else {
                FontResolver resolver = FontResolver.getInstance();
                int fontIndex = resolver.getFontIndex(text[start]);
                for (int i=start+1; i<limit; i++) {
                    if (resolver.getFontIndex(text[i]) != fontIndex) {
                        return null;
                    }
                }
                font = resolver.getFont(fontIndex, attributes);
            }
        }

        if (sameBaselineUpTo(font, text, start, limit) != limit) {
            return null;
        }

        return font;
    }

    /**
     * Constructs a <code>TextLayout</code> from an iterator over styled text.
     * <p>
     * The iterator must specify a single paragraph of text because an
     * entire paragraph is required for the bidirectional
     * algorithm.
     * @param text the styled text to display
     * @param frc contains information about a graphics device which is needed 
     *       to measure the text correctly.
     *       Text measurements can vary slightly depending on the
     *       device resolution, and attributes such as antialiasing.  This
     *       parameter does not specify a translation between the
     *       <code>TextLayout</code> and user space.
     */
    public TextLayout(AttributedCharacterIterator text, FontRenderContext frc) {

        if (text == null) {
            throw new IllegalArgumentException("Null iterator passed to TextLayout constructor.");
        }

        int start = text.getBeginIndex();
        int limit = text.getEndIndex();
        if (start == limit) {
            throw new IllegalArgumentException("Zero length iterator passed to TextLayout constructor.");
        }

        int len = limit - start;
        text.first();
        char[] chars = new char[len];
        int n = 0;
        for (char c = text.first(); c != text.DONE; c = text.next()) {
            chars[n++] = c;
        }

        text.first();
        if (text.getRunLimit() == limit) {

            Map attributes = text.getAttributes();
            Font font = singleFont(chars, 0, len, attributes);
            if (font != null) {
                fastInit(chars, font, attributes, frc);
                return;
            }
        }

        standardInit(text, chars, frc);
    }

    /**
     * Creates a <code>TextLayout</code> from a {@link TextLine} and 
     * some paragraph data.  This method is used by {@link TextMeasurer}.
     * @param textLine the line measurement attributes to apply to the
     *       the resulting <code>TextLayout</code>
     * @param baseline the baseline of the text
     * @param baselineOffsets the baseline offsets for this 
     * <code>TextLayout</code>.  This should already be normalized to 
     * <code>baseline</code>
     * @param justifyRatio <code>0</code> if the <code>TextLayout</code>
     *     cannot be justified; <code>1</code> otherwise.
     */
    TextLayout(TextLine textLine,
               byte baseline,
               float[] baselineOffsets,
               float justifyRatio) {

        this.characterCount = textLine.characterCount();
        this.baseline = baseline;
        this.baselineOffsets = baselineOffsets;
        this.textLine = textLine;
        this.justifyRatio = justifyRatio;
    }

    /**
     * Initialize the paragraph-specific data.
     */
    private void paragraphInit(byte aBaseline, LineMetrics lm, Map paragraphAttrs, char[] text) {
        
        baseline = aBaseline;

        // normalize to current baseline
        baselineOffsets = TextLine.getNormalizedOffsets(lm.getBaselineOffsets(), baseline);
        
        justifyRatio = TextLine.getJustifyRatio(paragraphAttrs);

	if (paragraphAttrs != null) {
	    Object o = paragraphAttrs.get(TextAttribute.NUMERIC_SHAPING);
	    if (o != null) {
		try {
		  NumericShaper shaper = (NumericShaper)o;
		  shaper.shape(text, 0, text.length);
		}
		catch (ClassCastException e) {
		}
	    }
	}
    }

    /*
     * the fast init generates a single glyph set.  This requires:
     * all one style
     * all renderable by one font (ie no embedded graphics)
     * all on one baseline
     */
    private void fastInit(char[] chars, Font font, Map attrs, FontRenderContext frc) {
        // Object vf = attrs.get(TextAttribute.ORIENTATION);
        // isVerticalLine = TextAttribute.ORIENTATION_VERTICAL.equals(vf);
        isVerticalLine = false;

        LineMetrics lm = font.getLineMetrics(chars, 0, chars.length, frc);
        byte glyphBaseline = (byte) lm.getBaselineIndex();

        if (attrs == null) {
            baseline = glyphBaseline;
            baselineOffsets = lm.getBaselineOffsets();
            justifyRatio = 1.0f;
        } else {
            paragraphInit(glyphBaseline, lm, attrs, chars);
        }

        characterCount = chars.length;

        optInfo = OptInfo.create(frc, chars, font, lm, attrs);
        if (optInfo == null) {
            textLine = TextLine.fastCreateTextLine(frc, chars, font, lm, attrs);
        }
    }

    private void initTextLine() {
        textLine = optInfo.createTextLine();
        optInfo = null;
    }

    /*
     * the standard init generates multiple glyph sets based on style,
     * renderable, and baseline runs.
     * @param chars the text in the iterator, extracted into a char array
     */
    private void standardInit(AttributedCharacterIterator text, char[] chars, FontRenderContext frc) {

        characterCount = chars.length;

        // set paragraph attributes
        {
            // If there's an embedded graphic at the start of the
            // paragraph, look for the first non-graphic character
            // and use it and its font to initialize the paragraph.
            // If not, use the first graphic to initialize.

            Map paragraphAttrs = text.getAttributes();

            boolean haveFont = TextLine.advanceToFirstFont(text);

            if (haveFont) {
                Font defaultFont = TextLine.getFontAtCurrentPos(text);
                int charsStart = text.getIndex() - text.getBeginIndex();
                LineMetrics lm = defaultFont.getLineMetrics(chars, charsStart, charsStart+1, frc);
                paragraphInit((byte)lm.getBaselineIndex(), lm, paragraphAttrs, chars);
            }
            else {
                // hmmm what to do here?  Just try to supply reasonable
                // values I guess.

                GraphicAttribute graphic = (GraphicAttribute)
                                paragraphAttrs.get(TextAttribute.CHAR_REPLACEMENT);
                byte defaultBaseline = getBaselineFromGraphic(graphic);
                Font dummyFont = new Font(new Hashtable(5, (float)0.9));
                LineMetrics lm = dummyFont.getLineMetrics(" ", 0, 1, frc);

                paragraphInit(defaultBaseline, lm, paragraphAttrs, chars);
            }
        }

        textLine = TextLine.standardCreateTextLine(frc, text, chars, baselineOffsets);
    }

    /*
     * A utility to rebuild the ascent/descent/leading/advance cache.
     * You'll need to call this if you clone and mutate (like justification,
     * editing methods do)
     */
    private void ensureCache() {
        if (!cacheIsValid) {
            buildCache();
        }
    }

    private void buildCache() {
        if (textLine == null) {
            initTextLine();
        }

        lineMetrics = textLine.getMetrics();

        // compute visibleAdvance
        if (textLine.isDirectionLTR()) {

            int lastNonSpace = characterCount-1;
            while (lastNonSpace != -1) {
                int logIndex = textLine.visualToLogical(lastNonSpace);
                if (!textLine.isCharSpace(logIndex)) {
                    break;
                }
                else {
                    --lastNonSpace;
                }
            }
            if (lastNonSpace == characterCount-1) {
                visibleAdvance = lineMetrics.advance;
            }
            else if (lastNonSpace == -1) {
                visibleAdvance = 0;
            }
            else {
                int logIndex = textLine.visualToLogical(lastNonSpace);
                visibleAdvance = textLine.getCharLinePosition(logIndex)
                                        + textLine.getCharAdvance(logIndex);
            }
        }
        else {

            int leftmostNonSpace = 0;
            while (leftmostNonSpace != characterCount) {
                int logIndex = textLine.visualToLogical(leftmostNonSpace);
                if (!textLine.isCharSpace(logIndex)) {
                    break;
                }
                else {
                    ++leftmostNonSpace;
                }
            }
            if (leftmostNonSpace == characterCount) {
                visibleAdvance = 0;
            }
            else if (leftmostNonSpace == 0) {
                visibleAdvance = lineMetrics.advance;
            }
            else {
                int logIndex = textLine.visualToLogical(leftmostNonSpace);
                float pos = textLine.getCharLinePosition(logIndex);
                visibleAdvance = lineMetrics.advance - pos;
            }
        }


        // naturalBounds, boundsRect will be generated on demand
        naturalBounds = null;
        boundsRect = null;

        // hashCode will be regenerated on demand
        hashCodeCache = 0;

        cacheIsValid = true;
    }

    private Rectangle2D getNaturalBounds() {
        ensureCache();

        if (naturalBounds == null) {
            int leftmostCharIndex = textLine.visualToLogical(0);
            float angle = textLine.getCharAngle(leftmostCharIndex);
            float leftOrTop = isVerticalLine? -dy : -dx;
            if (angle < 0) {
                leftOrTop += angle*textLine.getCharAscent(leftmostCharIndex);
            }
            else if (angle > 0) {
                leftOrTop -= angle*textLine.getCharDescent(leftmostCharIndex);
            }

            int rightmostCharIndex = textLine.visualToLogical(characterCount-1);
            angle = textLine.getCharAngle(rightmostCharIndex);

            float rightOrBottom = lineMetrics.advance;
            if (angle < 0) {
                rightOrBottom -=
                            angle*textLine.getCharDescent(rightmostCharIndex);
            }
            else if (angle > 0) {
                rightOrBottom +=
                            angle*textLine.getCharAscent(rightmostCharIndex);
            }

            float lineDim = rightOrBottom - leftOrTop;

            if (isVerticalLine) {
                naturalBounds = new Rectangle2D.Float(
                            -lineMetrics.descent, leftOrTop,
                            lineMetrics.ascent + lineMetrics.descent, lineDim);
            }
            else {
                naturalBounds = new Rectangle2D.Float(
                            leftOrTop, -lineMetrics.ascent,
                            lineDim, lineMetrics.ascent + lineMetrics.descent);
            }
        }

        return naturalBounds;
    }

    /**
     * Creates a copy of this <code>TextLayout</code>.
     */
    protected Object clone() {
        /*
         * !!! I think this is safe.  Once created, nothing mutates the
         * glyphvectors or arrays.  But we need to make sure.
         * {jbr} actually, that's not quite true.  The justification code
         * mutates after cloning.  It doesn't actually change the glyphvectors
         * (that's impossible) but it replaces them with justified sets.  This
         * is a problem for GlyphIterator creation, since new GlyphIterators
         * are created by cloning a prototype.  If the prototype has outdated
         * glyphvectors, so will the new ones.  A partial solution is to set the
         * prototypical GlyphIterator to null when the glyphvectors change.  If
         * you forget this one time, you're hosed.
         */
        try {
            return super.clone();
        }
        catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

    /*
     * Utility to throw an expection if an invalid TextHitInfo is passed
     * as a parameter.  Avoids code duplication.
     */
    private void checkTextHit(TextHitInfo hit) {
        if (hit == null) {
            throw new IllegalArgumentException("TextHitInfo is null.");
        }

        if (hit.getInsertionIndex() < 0 ||
            hit.getInsertionIndex() > characterCount) {
            throw new IllegalArgumentException("TextHitInfo is out of range");
        }
    }

    /**
     * Creates a copy of this <code>TextLayout</code> justified to the 
     * specified width.
     * <p>
     * If this <code>TextLayout</code> has already been justified, an
     * exception is thrown.  If this <code>TextLayout</code> object's 
     * justification ratio is zero, a <code>TextLayout</code> identical 
     * to this <code>TextLayout</code> is returned.
     * @param justificationWidth the width to use when justifying the line.
     * For best results, it should not be too different from the current
     * advance of the line.
     * @return a <code>TextLayout</code> justified to the specified width.
     * @exception Error if this layout has already been justified, an Error is
     * thrown.
     */
    public TextLayout getJustifiedLayout(float justificationWidth) {

        if (justificationWidth <= 0) {
            throw new IllegalArgumentException("justificationWidth <= 0 passed to TextLayout.getJustifiedLayout()");
        }

        if (justifyRatio == ALREADY_JUSTIFIED) {
            throw new Error("Can't justify again.");
        }

	ensureCache(); // make sure textLine is not null

        // default justification range to exclude trailing logical whitespace
        int limit = characterCount;
        while (limit > 0 && textLine.isCharWhitespace(limit-1)) {
            --limit;
        }

        TextLine newLine = textLine.getJustifiedLine(justificationWidth, justifyRatio, 0, limit);
        if (newLine != null) {
            return new TextLayout(newLine, baseline, baselineOffsets, ALREADY_JUSTIFIED);
        }

        return this;
    }

    /**
     * Justify this layout.  Overridden by subclassers to control justification
     * (if there were subclassers, that is...)
     *
     * The layout will only justify if the paragraph attributes (from the
     * source text, possibly defaulted by the layout attributes) indicate a
     * non-zero justification ratio.  The text will be justified to the
     * indicated width.  The current implementation also adjusts hanging
     * punctuation and trailing whitespace to overhang the justification width.
     * Once justified, the layout may not be rejustified.
     * <p>
     * Some code may rely on immutablity of layouts.  Subclassers should not
     * call this directly, but instead should call getJustifiedLayout, which
     * will call this method on a clone of this layout, preserving
     * the original.
     *
     * @param justificationWidth the width to use when justifying the line.
     * For best results, it should not be too different from the current
     * advance of the line.
     * @see #getJustifiedLayout(float)
     */
    protected void handleJustify(float justificationWidth) {
      // never called
    }


    /**
     * Returns the baseline for this <code>TextLayout</code>.
     * The baseline is one of the values defined in <code>Font</code>,
     * which are roman, centered and hanging.  Ascent and descent are
     * relative to this baseline.  The <code>baselineOffsets</code>
     * are also relative to this baseline.
     * @return the baseline of this <code>TextLayout</code>.
     * @see #getBaselineOffsets()
     * @see Font
     */
    public byte getBaseline() {
        return baseline;
    }

    /**
     * Returns the offsets array for the baselines used for this 
     * <code>TextLayout</code>.
     * <p>
     * The array is indexed by one of the values defined in 
     * <code>Font</code>, which are roman, centered and hanging.  The 
     * values are relative to this <code>TextLayout</code> object's 
     * baseline, so that <code>getBaselineOffsets[getBaseline()] == 0</code>.
     * Offsets are added to the position of the <code>TextLayout</code> 
     * object's baseline to get the position for the new baseline.
     * @return the offsets array containing the baselines used for this
     *    <code>TextLayout</code>.
     * @see #getBaseline()
     * @see Font
     */
    public float[] getBaselineOffsets() {
        float[] offsets = new float[baselineOffsets.length];
        System.arraycopy(baselineOffsets, 0, offsets, 0, offsets.length);
        return offsets;
    }

    /**
     * Returns the advance of this <code>TextLayout</code>.
     * The advance is the distance from the origin to the advance of the
     * rightmost (bottommost) character measuring in the line direction.
     * @return the advance of this <code>TextLayout</code>.
     */
    public float getAdvance() {
        if (optInfo != null) {
            try {
                return optInfo.getAdvance();
            }
            catch (Error e) {
                // cache was flushed under optInfo
            }
        }
        ensureCache();
        return lineMetrics.advance;
    }

    /**
     * Returns the advance of this <code>TextLayout</code>, minus trailing 
     * whitespace.
     * @return the advance of this <code>TextLayout</code> without the
     *      trailing whitespace.
     * @see #getAdvance()
     */
    public float getVisibleAdvance() {
        ensureCache();
        return visibleAdvance;
    }

    /**
     * Returns the ascent of this <code>TextLayout</code>.
     * The ascent is the distance from the top (right) of the 
     * <code>TextLayout</code> to the baseline.  It is always either 
     * positive or zero.  The ascent is sufficient to
     * accomodate superscripted text and is the maximum of the sum of the
     * ascent, offset, and baseline of each glyph.
     * @return the ascent of this <code>TextLayout</code>.
     */
    public float getAscent() {
        if (optInfo != null) {
            return optInfo.getLineMetrics().getAscent();
        }
        ensureCache();
        return lineMetrics.ascent;
    }

    /**
     * Returns the descent of this <code>TextLayout</code>.
     * The descent is the distance from the baseline to the bottom (left) of
     * the <code>TextLayout</code>.  It is always either positive or zero.  
     * The descent is sufficient to accomodate subscripted text and is the 
     * maximum of the sum of the descent, offset, and baseline of each glyph.
     * @return the descent of this <code>TextLayout</code>.
     */
    public float getDescent() {
        if (optInfo != null) {
            return optInfo.getLineMetrics().getDescent();
        }
        ensureCache();
        return lineMetrics.descent;
    }

    /**
     * Returns the leading of the <code>TextLayout</code>.
     * The leading is the suggested interline spacing for this 
     * <code>TextLayout</code>.
     * <p>
     * The leading is computed from the leading, descent, and baseline
     * of all glyphvectors in the <code>TextLayout</code>.  The algorithm 
     * is roughly as follows:
     * <blockquote><pre>
     * maxD = 0;
     * maxDL = 0;
     * for (GlyphVector g in all glyphvectors) {
     *    maxD = max(maxD, g.getDescent() + offsets[g.getBaseline()]);
     *    maxDL = max(maxDL, g.getDescent() + g.getLeading() +
     *                       offsets[g.getBaseline()]);
     * }
     * return maxDL - maxD;
     * </pre></blockquote>
     * @return the leading of this <code>TextLayout</code>.
     */
    public float getLeading() {
        if (optInfo != null) {
            return optInfo.getLineMetrics().getLeading();
        }
        ensureCache();
        return lineMetrics.leading;
    }

    /**
     * Returns the bounds of this <code>TextLayout</code>.
     * The bounds contains all of the pixels the <code>TextLayout</code>
     * can draw.  It might not coincide exactly with the ascent, descent, 
     * origin or advance of the <code>TextLayout</code>.
     * @return a {@link Rectangle2D} that is the bounds of this
     *        <code>TextLayout</code>.
     */
    public Rectangle2D getBounds() {
	if (optInfo != null) {
	    return optInfo.getVisualBounds();
	}

        ensureCache();

        if (boundsRect == null) {
            Rectangle2D lineBounds = textLine.getBounds();
            if (dx != 0 || dy != 0) {
                lineBounds.setRect(lineBounds.getX() - dx,
                                   lineBounds.getY() - dy,
                                   lineBounds.getWidth(),
                                   lineBounds.getHeight());
            }
            boundsRect = lineBounds;
        }

        Rectangle2D bounds = new Rectangle2D.Float();
        bounds.setRect(boundsRect);

        return bounds;
    }

    /**
     * Returns <code>true</code> if this <code>TextLayout</code> has 
     * a left-to-right base direction or <code>false</code> if it has
     * a right-to-left base direction.  The <code>TextLayout</code>
     * has a base direction of either left-to-right (LTR) or
     * right-to-left (RTL).  The base direction is independent of the 
     * actual direction of text on the line, which may be either LTR, 
     * RTL, or mixed. Left-to-right layouts by default should position 
     * flush left.  If the layout is on a tabbed line, the
     * tabs run left to right, so that logically successive layouts position
     * left to right.  The opposite is true for RTL layouts. By default they
     * should position flush left, and tabs run right-to-left.
     * @return <code>true</code> if the base direction of this 
     *         <code>TextLayout</code> is left-to-right; <code>false</code>
     *         otherwise.
     */
    public boolean isLeftToRight() {
        return (optInfo != null) || textLine.isDirectionLTR();
    }

    /**
     * Returns <code>true</code> if this <code>TextLayout</code> is vertical.
     * @return <code>true</code> if this <code>TextLayout</code> is vertical;
     *      <code>false</code> otherwise.
     */
    public boolean isVertical() {
        return isVerticalLine;
    }

    /**
     * Returns the number of characters represented by this 
     * <code>TextLayout</code>.
     * @return the number of characters in this <code>TextLayout</code>.
     */
    public int getCharacterCount() {
        return characterCount;
    }

    /*
     * carets and hit testing
     *
     * Positions on a text line are represented by instances of TextHitInfo.
     * Any TextHitInfo with characterOffset between 0 and characterCount-1,
     * inclusive, represents a valid position on the line.  Additionally,
     * [-1, trailing] and [characterCount, leading] are valid positions, and
     * represent positions at the logical start and end of the line,
     * respectively.
     *
     * The characterOffsets in TextHitInfo's used and returned by TextLayout
     * are relative to the beginning of the text layout, not necessarily to
     * the beginning of the text storage the client is using.
     *
     *
     * Every valid TextHitInfo has either one or two carets associated with it.
     * A caret is a visual location in the TextLayout indicating where text at
     * the TextHitInfo will be displayed on screen.  If a TextHitInfo
     * represents a location on a directional boundary, then there are two
     * possible visible positions for newly inserted text.  Consider the
     * following example, in which capital letters indicate right-to-left text,
     * and the overall line direction is left-to-right:
     *
     * Text Storage: [ a, b, C, D, E, f ]
     * Display:        a b E D C f
     *
     * The text hit info (1, t) represents the trailing side of 'b'.  If 'q',
     * a left-to-right character is inserted into the text storage at this
     * location, it will be displayed between the 'b' and the 'E':
     *
     * Text Storage: [ a, b, q, C, D, E, f ]
     * Display:        a b q E D C f
     *
     * However, if a 'W', which is right-to-left, is inserted into the storage
     * after 'b', the storage and display will be:
     *
     * Text Storage: [ a, b, W, C, D, E, f ]
     * Display:        a b E D C W f
     *
     * So, for the original text storage, two carets should be displayed for
     * location (1, t): one visually between 'b' and 'E' and one visually
     * between 'C' and 'f'.
     *
     *
     * When two carets are displayed for a TextHitInfo, one caret is the
     * 'strong' caret and the other is the 'weak' caret.  The strong caret
     * indicates where an inserted character will be displayed when that
     * character's direction is the same as the direction of the TextLayout.
     * The weak caret shows where an character inserted character will be
     * displayed when the character's direction is opposite that of the
     * TextLayout.
     *
     *
     * Clients should not be overly concerned with the details of correct
     * caret display. TextLayout.getCaretShapes(TextHitInfo) will return an
     * array of two paths representing where carets should be displayed.
     * The first path in the array is the strong caret; the second element,
     * if non-null, is the weak caret.  If the second element is null,
     * then there is no weak caret for the given TextHitInfo.
     *
     *
     * Since text can be visually reordered, logically consecutive
     * TextHitInfo's may not be visually consecutive.  One implication of this
     * is that a client cannot tell from inspecting a TextHitInfo whether the
     * hit represents the first (or last) caret in the layout.  Clients
     * can call getVisualOtherHit();  if the visual companion is
     * (-1, TRAILING) or (characterCount, LEADING), then the hit is at the
     * first (last) caret position in the layout.
     */

    private float[] getCaretInfo(int caret, 
                                 Rectangle2D bounds,
                                 float[] info) {

        float top1X, top2X;
        float bottom1X, bottom2X;

        if (caret == 0 || caret == characterCount) {

            float pos;
            int logIndex;
            if (caret == characterCount) {
                logIndex = textLine.visualToLogical(characterCount-1);
                pos = textLine.getCharLinePosition(logIndex)
                                        + textLine.getCharAdvance(logIndex);
            }
            else {
                logIndex = textLine.visualToLogical(caret);
                pos = textLine.getCharLinePosition(logIndex);
            }
            float angle = textLine.getCharAngle(logIndex);
            top1X = top2X = pos + angle*textLine.getCharAscent(logIndex);
            bottom1X = bottom2X = pos - angle*textLine.getCharDescent(logIndex);
        }
        else {

            {
                int logIndex = textLine.visualToLogical(caret-1);
                float angle1 = textLine.getCharAngle(logIndex);
                float pos1 = textLine.getCharLinePosition(logIndex)
                                    + textLine.getCharAdvance(logIndex);
                if (angle1 != 0) {
                    top1X = pos1 + angle1*textLine.getCharAscent(logIndex);
                    bottom1X = pos1 - angle1*textLine.getCharDescent(logIndex);
                }
                else {
                    top1X = bottom1X = pos1;
                }
            }
            {
                int logIndex = textLine.visualToLogical(caret);
                float angle2 = textLine.getCharAngle(logIndex);
                float pos2 = textLine.getCharLinePosition(logIndex);
                if (angle2 != 0) {
                    top2X = pos2 + angle2*textLine.getCharAscent(logIndex);
                    bottom2X = pos2 - angle2*textLine.getCharDescent(logIndex);
                }
                else {
                    top2X = bottom2X = pos2;
                }
            }
        }

        float topX = (top1X + top2X) / 2;
        float bottomX = (bottom1X + bottom2X) / 2;

        if (info == null) {
            info = new float[2];
        }

        if (isVerticalLine) {
            info[1] = (float) ((topX - bottomX) / bounds.getWidth());
            info[0] = (float) (topX + (info[1]*bounds.getX()));
        }
        else {
            info[1] = (float) ((topX - bottomX) / bounds.getHeight());
            info[0] = (float) (bottomX + (info[1]*bounds.getMaxY()));
        }

        return info;
    }

    /**
     * Returns information about the caret corresponding to <code>hit</code>.
     * The first element of the array is the intersection of the caret with
     * the baseline. The second element of the array is the inverse slope 
     * (run/rise) of the caret.
     * <p>
     * This method is meant for informational use.  To display carets, it
     * is better to use <code>getCaretShapes</code>.
     * @param hit a hit on a character in this <code>TextLayout</code>
     * @param bounds the bounds to which the caret info is constructed
     * @return a two-element array containing the position and slope of
     * the caret.
     * @see #getCaretShapes(int, Rectangle2D, TextLayout.CaretPolicy)
     * @see Font#getItalicAngle
     */
    public float[] getCaretInfo(TextHitInfo hit, Rectangle2D bounds) {
        ensureCache();
        checkTextHit(hit);

        return getCaretInfo(hitToCaret(hit), bounds, null);
    }

    /**
     * Returns information about the caret corresponding to <code>hit</code>.
     * This method is a convenience overload of <code>getCaretInfo</code> and
     * uses the natural bounds of this <code>TextLayout</code>.
     * @param hit a hit on a character in this <code>TextLayout</code>
     * @return the information about a caret corresponding to a hit.
     */
    public float[] getCaretInfo(TextHitInfo hit) {

        return getCaretInfo(hit, getNaturalBounds());
    }

    /**
     * Returns a caret index corresponding to <code>hit</code>.
     * Carets are numbered from left to right (top to bottom) starting from
     * zero. This always places carets next to the character hit, on the
     * indicated side of the character.
     * @param hit a hit on a character in this <code>TextLayout</code>
     * @return a caret index corresponding to the specified hit.
     */
    private int hitToCaret(TextHitInfo hit) {

        int hitIndex = hit.getCharIndex();

        if (hitIndex < 0) {
            return textLine.isDirectionLTR() ? 0 : characterCount;
        } else if (hitIndex >= characterCount) {
            return textLine.isDirectionLTR() ? characterCount : 0;
        }

        int visIndex = textLine.logicalToVisual(hitIndex);

        if (hit.isLeadingEdge() != textLine.isCharLTR(hitIndex)) {
            ++visIndex;
        }

        return visIndex;
    }

    /**
     * Given a caret index, return a hit whose caret is at the index.
     * The hit is NOT guaranteed to be strong!!!
     *
     * @param caret a caret index.
     * @return a hit on this layout whose strong caret is at the requested
     * index.
     */
    private TextHitInfo caretToHit(int caret) {

        if (caret == 0 || caret == characterCount) {

            if ((caret == characterCount) == textLine.isDirectionLTR()) {
                return TextHitInfo.leading(characterCount);
            }
            else {
                return TextHitInfo.trailing(-1);
            }
        }
        else {

            int charIndex = textLine.visualToLogical(caret);
            boolean leading = textLine.isCharLTR(charIndex);

            return leading? TextHitInfo.leading(charIndex)
                            : TextHitInfo.trailing(charIndex);
        }
    }

    private boolean caretIsValid(int caret) {

        if (caret == characterCount || caret == 0) {
            return true;
        }

        int offset = textLine.visualToLogical(caret);

        if (!textLine.isCharLTR(offset)) {
            offset = textLine.visualToLogical(caret-1);
            if (textLine.isCharLTR(offset)) {
                return true;
            }
        }

        // At this point, the leading edge of the character
        // at offset is at the given caret.

        return textLine.caretAtOffsetIsValid(offset);
    }

    /**
     * Returns the hit for the next caret to the right (bottom); if there 
     * is no such hit, returns <code>null</code>.
     * If the hit character index is out of bounds, an 
     * {@link IllegalArgumentException} is thrown.
     * @param hit a hit on a character in this layout
     * @return a hit whose caret appears at the next position to the
     * right (bottom) of the caret of the provided hit or <code>null</code>.
     */
    public TextHitInfo getNextRightHit(TextHitInfo hit) {
        ensureCache();
        checkTextHit(hit);

        int caret = hitToCaret(hit);

        if (caret == characterCount) {
            return null;
        }

        do {
            ++caret;
        } while (!caretIsValid(caret));

        return caretToHit(caret);
    }

    /**
     * Returns the hit for the next caret to the right (bottom); if no
     * such hit, returns <code>null</code>.  The hit is to the right of 
     * the strong caret at the specified offset, as determined by the
     * specified policy.
     * The returned hit is the stronger of the two possible
     * hits, as determined by the specified policy.
     * @param offset an insertion offset in this <code>TextLayout</code>.
     * Cannot be less than 0 or greater than this <code>TextLayout</code> 
     * object's character count.
     * @param policy the policy used to select the strong caret
     * @return a hit whose caret appears at the next position to the
     * right (bottom) of the caret of the provided hit, or <code>null</code>.
     */
    public TextHitInfo getNextRightHit(int offset, CaretPolicy policy) {

        if (offset < 0 || offset > characterCount) {
            throw new IllegalArgumentException("Offset out of bounds in TextLayout.getNextRightHit()");
        }

        if (policy == null) {
            throw new IllegalArgumentException("Null CaretPolicy passed to TextLayout.getNextRightHit()");
        }

        TextHitInfo hit1 = TextHitInfo.afterOffset(offset);
        TextHitInfo hit2 = hit1.getOtherHit();

        TextHitInfo nextHit = getNextRightHit(policy.getStrongCaret(hit1, hit2, this));

        if (nextHit != null) {
            TextHitInfo otherHit = getVisualOtherHit(nextHit);
            return policy.getStrongCaret(otherHit, nextHit, this);
        }
        else {
            return null;
        }
    }

    /**
     * Returns the hit for the next caret to the right (bottom); if no
     * such hit, returns <code>null</code>.  The hit is to the right of
     * the strong caret at the specified offset, as determined by the 
     * default policy.
     * The returned hit is the stronger of the two possible
     * hits, as determined by the default policy.
     * @param offset an insertion offset in this <code>TextLayout</code>.
     * Cannot be less than 0 or greater than the <code>TextLayout</code>
     * object's character count.
     * @return a hit whose caret appears at the next position to the
     * right (bottom) of the caret of the provided hit, or <code>null</code>.
     */
    public TextHitInfo getNextRightHit(int offset) {

        return getNextRightHit(offset, DEFAULT_CARET_POLICY);
    }

    /**
     * Returns the hit for the next caret to the left (top); if no such
     * hit, returns <code>null</code>.
     * If the hit character index is out of bounds, an 
     * <code>IllegalArgumentException</code> is thrown.
     * @param hit a hit on a character in this <code>TextLayout</code>.
     * @return a hit whose caret appears at the next position to the
     * left (top) of the caret of the provided hit, or <code>null</code>.
     */
    public TextHitInfo getNextLeftHit(TextHitInfo hit) {
        ensureCache();
        checkTextHit(hit);

        int caret = hitToCaret(hit);

        if (caret == 0) {
            return null;
        }

        do {
            --caret;
        } while(!caretIsValid(caret));

        return caretToHit(caret);
    }

    /**
     * Returns the hit for the next caret to the left (top); if no
     * such hit, returns <code>null</code>.  The hit is to the left of
     * the strong caret at the specified offset, as determined by the
     * specified policy.
     * The returned hit is the stronger of the two possible
     * hits, as determined by the specified policy.
     * @param offset an insertion offset in this <code>TextLayout</code>.
     * Cannot be less than 0 or greater than this <code>TextLayout</code>
     * object's character count.
     * @param policy the policy used to select the strong caret
     * @return a hit whose caret appears at the next position to the
     * left (top) of the caret of the provided hit, or <code>null</code>.
     */
    public TextHitInfo getNextLeftHit(int offset, CaretPolicy policy) {

        if (policy == null) {
            throw new IllegalArgumentException("Null CaretPolicy passed to TextLayout.getNextLeftHit()");
        }

        if (offset < 0 || offset > characterCount) {
            throw new IllegalArgumentException("Offset out of bounds in TextLayout.getNextLeftHit()");
        }

        TextHitInfo hit1 = TextHitInfo.afterOffset(offset);
        TextHitInfo hit2 = hit1.getOtherHit();

        TextHitInfo nextHit = getNextLeftHit(policy.getStrongCaret(hit1, hit2, this));

        if (nextHit != null) {
            TextHitInfo otherHit = getVisualOtherHit(nextHit);
            return policy.getStrongCaret(otherHit, nextHit, this);
        }
        else {
            return null;
        }
    }

    /**
     * Returns the hit for the next caret to the left (top); if no
     * such hit, returns <code>null</code>.  The hit is to the left of
     * the strong caret at the specified offset, as determined by the
     * default policy.
     * The returned hit is the stronger of the two possible
     * hits, as determined by the default policy.
     * @param offset an insertion offset in this <code>TextLayout</code>.  
     * Cannot be less than 0 or greater than this <code>TextLayout</code>
     * object's character count.
     * @return a hit whose caret appears at the next position to the
     * left (top) of the caret of the provided hit, or <code>null</code>.
     */
    public TextHitInfo getNextLeftHit(int offset) {

        return getNextLeftHit(offset, DEFAULT_CARET_POLICY);
    }

    /**
     * Returns the hit on the opposite side of the specified hit's caret.
     * @param hit the specified hit
     * @return a hit that is on the opposite side of the specified hit's
     *    caret.
     */
    public TextHitInfo getVisualOtherHit(TextHitInfo hit) {

        ensureCache();
        checkTextHit(hit);

        int hitCharIndex = hit.getCharIndex();

        int charIndex;
        boolean leading;

        if (hitCharIndex == -1 || hitCharIndex == characterCount) {

            int visIndex;
            if (textLine.isDirectionLTR() == (hitCharIndex == -1)) {
                visIndex = 0;
            }
            else {
                visIndex = characterCount-1;
            }

            charIndex = textLine.visualToLogical(visIndex);

            if (textLine.isDirectionLTR() == (hitCharIndex == -1)) {
                // at left end
                leading = textLine.isCharLTR(charIndex);
            }
            else {
                // at right end
                leading = !textLine.isCharLTR(charIndex);
            }
        }
        else {

            int visIndex = textLine.logicalToVisual(hitCharIndex);

            boolean movedToRight;
            if (textLine.isCharLTR(hitCharIndex) == hit.isLeadingEdge()) {
                --visIndex;
                movedToRight = false;
            }
            else {
                ++visIndex;
                movedToRight = true;
            }

            if (visIndex > -1 && visIndex < characterCount) {
                charIndex = textLine.visualToLogical(visIndex);
                leading = movedToRight == textLine.isCharLTR(charIndex);
            }
            else {
                charIndex =
                    (movedToRight == textLine.isDirectionLTR())? characterCount : -1;
                leading = charIndex == characterCount;
            }
        }

        return leading? TextHitInfo.leading(charIndex) :
                                TextHitInfo.trailing(charIndex);
    }

    /**
     * Return an array of four floats corresponding the endpoints of the caret
     * x0, y0, x1, y1.
     *
     * This creates a line along the slope of the caret intersecting the
     * baseline at the caret
     * position, and extending from ascent above the baseline to descent below
     * it.
     */
    private double[] getCaretPath(int caret, Rectangle2D bounds,
                                  boolean clipToBounds) {

        float[] info = getCaretInfo(caret, bounds, null);

        double pos = info[0];
        double slope = info[1];

        double x0, y0, x1, y1;
        double x2 = -3141.59, y2 = -2.7; // values are there to make compiler happy

        double left = bounds.getX();
        double right = left + bounds.getWidth();
        double top = bounds.getY();
        double bottom = top + bounds.getHeight();

        boolean threePoints = false;

        if (isVerticalLine) {

            if (slope >= 0) {
                x0 = left;
                x1 = right;
            }
            else {
                x1 = left;
                x0 = right;
            }

            y0 = pos + x0 * slope;
            y1 = pos + x1 * slope;

            // y0 <= y1, always

            if (clipToBounds) {
                if (y0 < top) {
                    if (slope <= 0 || y1 <= top) {
                        y0 = y1 = top;
                    }
                    else {
                        threePoints = true;
                        y0 = top;
                        y2 = top;
                        x2 = x1 + (top-y1)/slope;
                        if (y1 > bottom) {
                            y1 = bottom;
                        }
                    }
                }
                else if (y1 > bottom) {
                    if (slope >= 0 || y0 >= bottom) {
                        y0 = y1 = bottom;
                    }
                    else {
                        threePoints = true;
                        y1 = bottom;
                        y2 = bottom;
                        x2 = x0 + (bottom-x1)/slope;
                    }
                }
            }

        }
        else {

            if (slope >= 0) {
                y0 = bottom;
                y1 = top;
            }
            else {
                y1 = bottom;
                y0 = top;
            }

            x0 = pos - y0 * slope;
            x1 = pos - y1 * slope;
            
            // x0 <= x1, always

            if (clipToBounds) {
                if (x0 < left) {
                    if (slope <= 0 || x1 <= left) {
                        x0 = x1 = left;
                    }
                    else {
                        threePoints = true;
                        x0 = left;
                        x2 = left;
                        y2 = y1 - (left-x1)/slope;
                        if (x1 > right) {
                            x1 = right;
                        }
                    }
                }
                else if (x1 > right) {
                    if (slope >= 0 || x0 >= right) {
                        x0 = x1 = right;
                    }
                    else {
                        threePoints = true;
                        x1 = right;
                        x2 = right;
                        y2 = y0 - (right-x0)/slope;
                    }
                }
            }
        }

        return threePoints?
                    new double[] { x0, y0, x2, y2, x1, y1 } :
                    new double[] { x0, y0, x1, y1 };
    }


    private static GeneralPath pathToShape(double[] path, boolean close) {
        GeneralPath result = new GeneralPath(GeneralPath.WIND_EVEN_ODD, path.length);
        result.moveTo((float)path[0], (float)path[1]);
        for (int i = 2; i < path.length; i += 2) {
            result.lineTo((float)path[i], (float)path[i+1]);
        }
        if (close) {
            result.closePath();
        }

        return result;
    }

    /**
     * Returns a {@link Shape} representing the caret at the specified 
     * hit inside the specified bounds.
     * @param hit the hit at which to generate the caret
     * @param bounds the bounds of the <code>TextLayout</code> to use 
     * in generating the caret.
     * @return a <code>Shape</code> representing the caret.
     */
    public Shape getCaretShape(TextHitInfo hit, Rectangle2D bounds) {
	ensureCache();
        checkTextHit(hit);

        if (bounds == null) {
            throw new IllegalArgumentException("Null Rectangle2D passed to TextLayout.getCaret()");
        }

        int hitCaret = hitToCaret(hit);
        GeneralPath hitShape =
                    pathToShape(getCaretPath(hitCaret, bounds, false), false);

        //return new Highlight(hitShape, true);
        return hitShape;
    }

    /**
     * Returns a <code>Shape</code> representing the caret at the specified
     * hit inside the natural bounds of this <code>TextLayout</code>.
     * @param hit the hit at which to generate the caret
     * @return a <code>Shape</code> representing the caret.
     */
    public Shape getCaretShape(TextHitInfo hit) {

        return getCaretShape(hit, getNaturalBounds());
    }

    /**
     * Return the "stronger" of the TextHitInfos.  The TextHitInfos
     * should be logical or visual counterparts.  They are not
     * checked for validity.
     */
    private final TextHitInfo getStrongHit(TextHitInfo hit1, TextHitInfo hit2) {

        // right now we're using the following rule for strong hits:
        // A hit on a character with a lower level
        // is stronger than one on a character with a higher level.
        // If this rule ties, the hit on the leading edge of a character wins.
        // If THIS rule ties, hit1 wins.  Both rules shouldn't tie, unless the
        // infos aren't counterparts of some sort.

        byte hit1Level = getCharacterLevel(hit1.getCharIndex());
        byte hit2Level = getCharacterLevel(hit2.getCharIndex());

        if (hit1Level == hit2Level) {
            if (hit2.isLeadingEdge() && !hit1.isLeadingEdge()) {
                return hit2;
            }
            else {
                return hit1;
            }
        }
        else {
            return (hit1Level < hit2Level)? hit1 : hit2;
        }
    }

    /**
     * Returns the level of the character at <code>index</code>.  
     * Indices -1 and <code>characterCount</code> are assigned the base
     * level of this <code>TextLayout</code>.
     * @param index the index of the character from which to get the level
     * @return the level of the character at the specified index.
     */
    public byte getCharacterLevel(int index) {

        // hmm, allow indices at endpoints?  For now, yes.
        if (index < -1 || index > characterCount) {
            throw new IllegalArgumentException("Index is out of range in getCharacterLevel.");
        }

        if (optInfo != null) {
            return 0;
        }

	ensureCache();
        if (index == -1 || index == characterCount) {
             return (byte) (textLine.isDirectionLTR()? 0 : 1);
        }

        return textLine.getCharLevel(index);
    }

    /**
     * Returns two paths corresponding to the strong and weak caret.
     * @param offset an offset in this <code>TextLayout</code>
     * @param bounds the bounds to which to extend the carets
     * @param policy the specified <code>CaretPolicy</code>
     * @return an array of two paths.  Element zero is the strong 
     * caret.  If there are two carets, element one is the weak caret,  
     * otherwise it is <code>null</code>. 
     */
    public Shape[] getCaretShapes(int offset, Rectangle2D bounds, CaretPolicy policy) {

        ensureCache();

        if (offset < 0 || offset > characterCount) {
            throw new IllegalArgumentException("Offset out of bounds in TextLayout.getCaretShapes()");
        }

        if (bounds == null) {
            throw new IllegalArgumentException("Null Rectangle2D passed to TextLayout.getCaretShapes()");
        }

        if (policy == null) {
            throw new IllegalArgumentException("Null CaretPolicy passed to TextLayout.getCaretShapes()");
        }

        Shape[] result = new Shape[2];

        TextHitInfo hit = TextHitInfo.afterOffset(offset);

        int hitCaret = hitToCaret(hit);
        Shape hitShape =
                    pathToShape(getCaretPath(hitCaret, bounds, false), false);

        TextHitInfo otherHit = hit.getOtherHit();
        int otherCaret = hitToCaret(otherHit);

        if (hitCaret == otherCaret) {
            result[0] = hitShape;
        }
        else { // more than one caret
            Shape otherShape =
                pathToShape(getCaretPath(otherCaret, bounds, false), false);

            TextHitInfo strongHit = policy.getStrongCaret(hit, otherHit, this);
            boolean hitIsStrong = strongHit.equals(hit);

            if (hitIsStrong) {// then other is weak
                result[0] = hitShape;
                result[1] = otherShape;
            }
            else {
                result[0] = otherShape;
                result[1] = hitShape;
            }
        }

        return result;
    }

    /**
     * Returns two paths corresponding to the strong and weak caret.  
     * This method is a convenience overload of <code>getCaretShapes</code>
     * that uses the default caret policy.
     * @param offset an offset in this <code>TextLayout</code>
     * @param bounds the bounds to which to extend the carets
     * @return two paths corresponding to the strong and weak caret as
     *    defined by the <code>DEFAULT_CARET_POLICY</code>
     */
     public Shape[] getCaretShapes(int offset, Rectangle2D bounds) {
        // {sfb} parameter checking is done in overloaded version
        return getCaretShapes(offset, bounds, DEFAULT_CARET_POLICY);
    }

    /**
     * Returns two paths corresponding to the strong and weak caret.  
     * This method is a convenience overload of <code>getCaretShapes</code>
     * that uses the default caret policy and this <code>TextLayout</code>
     * object's natural bounds.  
     * @param offset an offset in this <code>TextLayout</code>
     * @return two paths corresponding to the strong and weak caret as
     *    defined by the <code>DEFAULT_CARET_POLICY</code>
     */
    public Shape[] getCaretShapes(int offset) {
        // {sfb} parameter checking is done in overloaded version
        return getCaretShapes(offset, getNaturalBounds(), DEFAULT_CARET_POLICY);
    }

    // A utility to return a path enclosing the given path
    // Path0 must be left or top of path1
    // {jbr} no assumptions about size of path0, path1 anymore.
    private GeneralPath boundingShape(double[] path0, double[] path1) {

        // Really, we want the path to be a convex hull around all of the
        // points in path0 and path1.  But we can get by with less than
        // that.  We do need to prevent the two segments which
        // join path0 to path1 from crossing each other.  So, if we
        // traverse path0 from top to bottom, we'll traverse path1 from
        // bottom to top (and vice versa).

        GeneralPath result = pathToShape(path0, false);

        boolean sameDirection;
                
        if (isVerticalLine) {
            sameDirection = (path0[1] > path0[path0.length-1]) ==
                            (path1[1] > path1[path1.length-1]);
        }
        else {
            sameDirection = (path0[0] > path0[path0.length-2]) ==
                            (path1[0] > path1[path1.length-2]);
        }

        int start;
        int limit;
        int increment;

        if (sameDirection) {
            start = path1.length-2;
            limit = -2;
            increment = -2;
        }
        else {
            start = 0;
            limit = path1.length;
            increment = 2;
        }

        for (int i = start; i != limit; i += increment) {
            result.lineTo((float)path1[i], (float)path1[i+1]);
        }

        result.closePath();

        return result;
    }

    // A utility to convert a pair of carets into a bounding path
    // {jbr} Shape is never outside of bounds.
    private GeneralPath caretBoundingShape(int caret0,
                                           int caret1,
                                           Rectangle2D bounds) {

        if (caret0 > caret1) {
            int temp = caret0;
            caret0 = caret1;
            caret1 = temp;
        }

        return boundingShape(getCaretPath(caret0, bounds, true),
                             getCaretPath(caret1, bounds, true));
    }

    /*
     * A utility to return the path bounding the area to the left (top) of the
     * layout.
     * Shape is never outside of bounds.
     */
    private GeneralPath leftShape(Rectangle2D bounds) {

        double[] path0;
        if (isVerticalLine) {
            path0 = new double[] { bounds.getX(), bounds.getY(),
                                       bounds.getX() + bounds.getWidth(),
                                       bounds.getY() };
        } else {
            path0 = new double[] { bounds.getX(),
                                       bounds.getY() + bounds.getHeight(),
                                       bounds.getX(), bounds.getY() };
        }

        double[] path1 = getCaretPath(0, bounds, true);

        return boundingShape(path0, path1);
    }

    /*
     * A utility to return the path bounding the area to the right (bottom) of
     * the layout.
     */
    private GeneralPath rightShape(Rectangle2D bounds) {
        double[] path1;
        if (isVerticalLine) {
            path1 = new double[] {
                bounds.getX(),
                bounds.getY() + bounds.getHeight(),
                bounds.getX() + bounds.getWidth(),
                bounds.getY() + bounds.getHeight()
            };
        } else {
            path1 = new double[] {
                bounds.getX() + bounds.getWidth(),
                bounds.getY() + bounds.getHeight(),
                bounds.getX() + bounds.getWidth(),
                bounds.getY()
            };
        }

        double[] path0 = getCaretPath(characterCount, bounds, true);

        return boundingShape(path0, path1);
    }

    /**
     * Returns the logical ranges of text corresponding to a visual selection.
     * @param firstEndpoint an endpoint of the visual range
     * @param secondEndpoint the other endpoint of the visual range.
     * This endpoint can be less than <code>firstEndpoint</code>.
     * @return an array of integers representing start/limit pairs for the
     * selected ranges.
     * @see #getVisualHighlightShape(TextHitInfo, TextHitInfo, Rectangle2D)
     */
    public int[] getLogicalRangesForVisualSelection(TextHitInfo firstEndpoint,
                                                    TextHitInfo secondEndpoint) {
        ensureCache();

        checkTextHit(firstEndpoint);
        checkTextHit(secondEndpoint);

        // !!! probably want to optimize for all LTR text

        boolean[] included = new boolean[characterCount];

        int startIndex = hitToCaret(firstEndpoint);
        int limitIndex = hitToCaret(secondEndpoint);

        if (startIndex > limitIndex) {
            int t = startIndex;
            startIndex = limitIndex;
            limitIndex = t;
        }

        /*
         * now we have the visual indexes of the glyphs at the start and limit
         * of the selection range walk through runs marking characters that
         * were included in the visual range there is probably a more efficient
         * way to do this, but this ought to work, so hey
         */

        if (startIndex < limitIndex) {
            int visIndex = startIndex;
            while (visIndex < limitIndex) {
                included[textLine.visualToLogical(visIndex)] = true;
                ++visIndex;
            }
        }

        /*
         * count how many runs we have, ought to be one or two, but perhaps
         * things are especially weird
         */
        int count = 0;
        boolean inrun = false;
        for (int i = 0; i < characterCount; i++) {
            if (included[i] != inrun) {
                inrun = !inrun;
                if (inrun) {
                    count++;
                }
            }
        }

        int[] ranges = new int[count * 2];
        count = 0;
        inrun = false;
        for (int i = 0; i < characterCount; i++) {
            if (included[i] != inrun) {
                ranges[count++] = i;
                inrun = !inrun;
            }
        }
        if (inrun) {
            ranges[count++] = characterCount;
        }

        return ranges;
    }

    /**
     * Returns a path enclosing the visual selection in the specified range,
     * extended to <code>bounds</code>.
     * <p>
     * If the selection includes the leftmost (topmost) position, the selection
     * is extended to the left (top) of <code>bounds</code>.  If the 
     * selection includes the rightmost (bottommost) position, the selection
     * is extended to the right (bottom) of the bounds.  The height 
     * (width on vertical lines) of the selection is always extended to 
     * <code>bounds</code>.
     * <p>
     * Although the selection is always contiguous, the logically selected
     * text can be discontiguous on lines with mixed-direction text.  The
     * logical ranges of text selected can be retrieved using
     * <code>getLogicalRangesForVisualSelection</code>.  For example, 
     * consider the text 'ABCdef' where capital letters indicate 
     * right-to-left text, rendered on a right-to-left line, with a visual
     * selection from 0L (the leading edge of 'A') to 3T (the trailing edge
     * of 'd').  The text appears as follows, with bold underlined areas
     * representing the selection:
     * <br><pre>
     *    d<u><b>efCBA  </b></u>
     * </pre>
     * The logical selection ranges are 0-3, 4-6 (ABC, ef) because the
     * visually contiguous text is logically discontiguous.  Also note that
     * since the rightmost position on the layout (to the right of 'A') is
     * selected, the selection is extended to the right of the bounds.
     * @param firstEndpoint one end of the visual selection
     * @param secondEndpoint the other end of the visual selection
     * @param bounds the bounding rectangle to which to extend the selection
     * @return a <code>Shape</code> enclosing the selection.
     * @see #getLogicalRangesForVisualSelection(TextHitInfo, TextHitInfo)
     * @see #getLogicalHighlightShape(int, int, Rectangle2D)
     */
    public Shape getVisualHighlightShape(TextHitInfo firstEndpoint,
                                        TextHitInfo secondEndpoint,
                                        Rectangle2D bounds)
    {
        ensureCache();

        checkTextHit(firstEndpoint);
        checkTextHit(secondEndpoint);

        if(bounds == null) {
                throw new IllegalArgumentException("Null Rectangle2D passed to TextLayout.getVisualHighlightShape()");
        }

        GeneralPath result = new GeneralPath(GeneralPath.WIND_EVEN_ODD);

        int firstCaret = hitToCaret(firstEndpoint);
        int secondCaret = hitToCaret(secondEndpoint);

        result.append(caretBoundingShape(firstCaret, secondCaret, bounds),
                      false);

        if (firstCaret == 0 || secondCaret == 0) {
            result.append(leftShape(bounds), false);
        }

        if (firstCaret == characterCount || secondCaret == characterCount) {
            result.append(rightShape(bounds), false);
        }

        //return new Highlight(result, false);
        return  result;
    }

    /**
     * Returns a <code>Shape</code> enclosing the visual selection in the
     * specified range, extended to the bounds.  This method is a
     * convenience overload of <code>getVisualHighlightShape</code> that
     * uses the natural bounds of this <code>TextLayout</code>.
     * @param firstEndpoint one end of the visual selection
     * @param secondEndpoint the other end of the visual selection
     * @return a <code>Shape</code> enclosing the selection.     
     */
    public Shape getVisualHighlightShape(TextHitInfo firstEndpoint,
                                             TextHitInfo secondEndpoint) {
        return getVisualHighlightShape(firstEndpoint, secondEndpoint, getNaturalBounds());
    }

    /**
     * Returns a <code>Shape</code> enclosing the logical selection in the
     * specified range, extended to the specified <code>bounds</code>.
     * <p>
     * If the selection range includes the first logical character, the
     * selection is extended to the portion of <code>bounds</code> before 
     * the start of this <code>TextLayout</code>.  If the range includes
     * the last logical character, the selection is extended to the portion
     * of <code>bounds</code> after the end of this <code>TextLayout</code>.  
     * The height (width on vertical lines) of the selection is always
     * extended to <code>bounds</code>.
     * <p>
     * The selection can be discontiguous on lines with mixed-direction text.
     * Only those characters in the logical range between start and limit
     * appear selected.  For example, consider the text 'ABCdef' where capital
     * letters indicate right-to-left text, rendered on a right-to-left line,
     * with a logical selection from 0 to 4 ('ABCd').  The text appears as
     * follows, with bold standing in for the selection, and underlining for
     * the extension:
     * <br><pre>
     *    <u><b>d</b></u>ef<u><b>CBA  </b></u>
     * </pre>
     * The selection is discontiguous because the selected characters are
     * visually discontiguous. Also note that since the range includes the
     * first logical character (A), the selection is extended to the portion
     * of the <code>bounds</code> before the start of the layout, which in
     * this case (a right-to-left line) is the right portion of the 
     * <code>bounds</code>.
     * @param firstEndpoint an endpoint in the range of characters to select
     * @param secondEndpoint the other endpoint of the range of characters
     * to select. Can be less than <code>firstEndpoint</code>.  The range
     * includes the character at min(firstEndpoint, secondEndpoint), but
     * excludes max(firstEndpoint, secondEndpoint).
     * @param bounds the bounding rectangle to which to extend the selection
     * @return an area enclosing the selection.
     * @see #getVisualHighlightShape(TextHitInfo, TextHitInfo, Rectangle2D)
     */
    public Shape getLogicalHighlightShape(int firstEndpoint,
                                         int secondEndpoint,
                                         Rectangle2D bounds) {
        if (bounds == null) {
            throw new IllegalArgumentException("Null Rectangle2D passed to TextLayout.getLogicalHighlightShape()");
        }

        ensureCache();

        if (firstEndpoint > secondEndpoint) {
            int t = firstEndpoint;
            firstEndpoint = secondEndpoint;
            secondEndpoint = t;
        }

        if(firstEndpoint < 0 || secondEndpoint > characterCount) {
            throw new IllegalArgumentException("Range is invalid in TextLayout.getLogicalHighlightShape()");
        }

        int[] carets = new int[10]; // would this ever not handle all cases?
        int count = 0;

        if (firstEndpoint < secondEndpoint) {
            int logIndex = firstEndpoint;
            do {
                carets[count++] = hitToCaret(TextHitInfo.leading(logIndex));
                boolean ltr = textLine.isCharLTR(logIndex);

                do {
                    logIndex++;
                } while (logIndex < secondEndpoint && textLine.isCharLTR(logIndex) == ltr);

                int hitCh = logIndex;
                carets[count++] = hitToCaret(TextHitInfo.trailing(hitCh - 1));

                if (count == carets.length) {
                    int[] temp = new int[carets.length + 10];
                    System.arraycopy(carets, 0, temp, 0, count);
                    carets = temp;
                }
            } while (logIndex < secondEndpoint);
        }
        else {
            count = 2;
            carets[0] = carets[1] = hitToCaret(TextHitInfo.leading(firstEndpoint));
        }

        // now create paths for pairs of carets

        GeneralPath result = new GeneralPath(GeneralPath.WIND_EVEN_ODD);

        for (int i = 0; i < count; i += 2) {
            result.append(caretBoundingShape(carets[i], carets[i+1], bounds),
                          false);
        }

        if ((textLine.isDirectionLTR() && firstEndpoint == 0) || (!textLine.isDirectionLTR() &&
                                               secondEndpoint == characterCount)) {
            result.append(leftShape(bounds), false);
        }

        if ((textLine.isDirectionLTR() && secondEndpoint == characterCount) ||
            (!textLine.isDirectionLTR() && firstEndpoint == 0)) {
            result.append(rightShape(bounds), false);
        }

        return result;
    }

    /**
     * Returns a <code>Shape</code> enclosing the logical selection in the
     * specified range, extended to the natural bounds of this
     * <code>TextLayout</code>.  This method is a convenience overload of 
     * <code>getLogicalHighlightShape</code> that uses the natural bounds of 
     * this <code>TextLayout</code>.
     * @param firstEndpoint an endpoint in the range of characters to select
     * @param secondEndpoint the other endpoint of the range of characters
     * to select. Can be less than <code>firstEndpoint</code>.  The range
     * includes the character at min(firstEndpoint, secondEndpoint), but
     * excludes max(firstEndpoint, secondEndpoint).
     * @return a <code>Shape</code> enclosing the selection.     
     */
    public Shape getLogicalHighlightShape(int firstEndpoint, int secondEndpoint) {

        return getLogicalHighlightShape(firstEndpoint, secondEndpoint, getNaturalBounds());
    }

    /**
     * Returns the black box bounds of the characters in the specified range.
     * The black box bounds is an area consisting of the union of the bounding
     * boxes of all the glyphs corresponding to the characters between start
     * and limit.  This path may be disjoint.
     * @param firstEndpoint one end of the character range
     * @param secondEndpoint the other end of the character range.  Can be
     * less than <code>firstEndpoint</code>.
     * @return a <code>path</code> enclosing the black box bounds.
     */
    public Shape getBlackBoxBounds(int firstEndpoint, int secondEndpoint) {
        ensureCache();

        if (firstEndpoint > secondEndpoint) {
            int t = firstEndpoint;
            firstEndpoint = secondEndpoint;
            secondEndpoint = t;
        }

        if (firstEndpoint < 0 || secondEndpoint > characterCount) {
            throw new IllegalArgumentException("Invalid range passed to TextLayout.getBlackBoxBounds()");
        }

        /*
         * return an area that consists of the bounding boxes of all the
         * characters from firstEndpoint to limit
         */

        GeneralPath result = new GeneralPath(GeneralPath.WIND_NON_ZERO);

        if (firstEndpoint < characterCount) {
            for (int logIndex = firstEndpoint;
                        logIndex < secondEndpoint;
                        logIndex++) {

                if (!textLine.isCharWhitespace(logIndex)) {
                    Rectangle2D r = textLine.getCharBounds(logIndex);
                    result.append(r, false);
                }
            }
        }

        if (dx != 0 || dy != 0) {
            AffineTransform translate = new AffineTransform();
            translate.setToTranslation(dx, dy);
            result = (GeneralPath) result.createTransformedShape(translate);
        }

        //return new Highlight(result, false);
        return result;
    }

    /**
     * Returns the distance from the point (x, y) to the caret along 
     * the line direction defined in <code>caretInfo</code>.  Distance is 
     * negative if the point is to the left of the caret on a horizontal 
     * line, or above the caret on a vertical line.
     * Utility for use by hitTestChar.
     */
    private float caretToPointDistance(float[] caretInfo, float x, float y) {
        // distanceOffBaseline is negative if you're 'above' baseline

        float lineDistance = isVerticalLine? y : x;
        float distanceOffBaseline = isVerticalLine? -x : y;

        return lineDistance - caretInfo[0] +
            (distanceOffBaseline*caretInfo[1]);
    }


    /**
     * Returns a <code>TextHitInfo</code> corresponding to the 
     * specified point.
     * Coordinates outside the bounds of the <code>TextLayout</code>
     * map to hits on the leading edge of the first logical character, 
     * or the trailing edge of the last logical character, as appropriate, 
     * regardless of the position of that character in the line.  Only the
     * direction along the baseline is used to make this evaluation.
     * @param x the x offset from the origin of this 
     *          <code>TextLayout</code>
     * @param y the y offset from the origin of this
     *          <code>TextLayout</code>
     * @param bounds the bounds of the <code>TextLayout</code>
     * @return a hit describing the character and edge (leading or trailing)
     * under the specified point.
     */

    public TextHitInfo hitTestChar(float x, float y, Rectangle2D bounds) {

        ensureCache();

        int hitLB, hitUB;

        float[] caretInfo = new float[2];

        hitLB = 0;
        caretInfo = getCaretInfo(hitLB, bounds, caretInfo);

        if (caretToPointDistance(caretInfo, x, y) < 0) {
            return textLine.isDirectionLTR()? TextHitInfo.trailing(-1) :
                            TextHitInfo.leading(characterCount);
        }

        hitUB = characterCount;
        caretInfo = getCaretInfo(hitUB, bounds, caretInfo);

        if (caretToPointDistance(caretInfo, x, y) >= 0) {
            return textLine.isDirectionLTR()? TextHitInfo.leading(characterCount) :
                                                TextHitInfo.trailing(-1);
        }

        while (true) {

            // if there are no valid caret positions between
            // hitLB and hitUB then exit this loop;  otherwise
            // set test to a valid caret position in the
            // interval (hitLB, hitUB)

            if (hitLB + 1 == hitUB)
                break;

            int test = (hitLB + hitUB) / 2;

            while(!caretIsValid(test)) {
                test++;
            }

            if (test == hitUB) {
                // If we're here then there were no valid caret
                // positions between the halfway point and the
                // end of the test region.  Reset test and back
                // up to a valid caret position.

                test = (hitLB + hitUB) / 2;
                do {
                    --test;
                } while(!caretIsValid(test));

                if (test == hitLB)
                    break;
            }

            caretInfo = getCaretInfo(test, bounds, caretInfo);

            float caretDist = caretToPointDistance(caretInfo, x, y);

            if (caretDist == 0) {
                // return a hit on the left side of the glyph at test
                // test is a valid position, since it is less than characterCount
                int charIndex = textLine.visualToLogical(test);
                boolean leading = textLine.isCharLTR(charIndex);
                return leading? TextHitInfo.leading(charIndex) :
                                        TextHitInfo.trailing(charIndex);
            }
            else if (caretDist < 0) {
                hitUB = test;
            }
            else {
                hitLB = test;
            }
        }

        // now hit char is either to the right of hitLB
        // or left of hitUB

        // make caretInfo be center of glyph:
        int logIndex = textLine.visualToLogical(hitLB);
        float hitAdvance = textLine.getCharLinePosition(logIndex) +
                                            (isVerticalLine? -dy : -dx);

        // this positions hitAdvance at the "center" of the character(s)
        // between hitLB and hitUB
        {
            int tempLogIndex = textLine.visualToLogical(hitUB - 1);
            if (hitUB - hitLB > 1) {
                float tempPos = textLine.getCharLinePosition(tempLogIndex);
                hitAdvance += (tempPos - hitAdvance) / 2;
            }
            hitAdvance += textLine.getCharAdvance(tempLogIndex) / 2;
        }

        caretInfo[0] = hitAdvance;
        caretInfo[1] = textLine.getCharAngle(logIndex);
        if (caretInfo[1] != 0) {
            caretInfo[0] += caretInfo[1] * (isVerticalLine?
                                textLine.getCharXPosition(logIndex) :
                                textLine.getCharYPosition(logIndex));
        }

        float centerDist = caretToPointDistance(caretInfo, x, y);

        TextHitInfo rval;

        if (centerDist < 0) {
            rval = textLine.isCharLTR(logIndex)?
                                TextHitInfo.leading(logIndex) :
                                TextHitInfo.trailing(logIndex);
        }
        else {
            logIndex = textLine.visualToLogical(hitUB - 1);
            boolean leading = !textLine.isCharLTR(logIndex);
            rval = leading? TextHitInfo.leading(logIndex) :
                                TextHitInfo.trailing(logIndex);
        }

        return rval;
    }

    /**
     * Returns a <code>TextHitInfo</code> corresponding to the 
     * specified point.  This method is a convenience overload of 
     * <code>hitTestChar</code> that uses the natural bounds of this 
     * <code>TextLayout</code>.
     * @param x the x offset from the origin of this <code>TextLayout</code>
     * @param y the y offset from the origin of this
     *          <code>TextLayout</code>
     * @return a hit describing the character and edge (leading or trailing)
     * under the specified point.
     */
    public TextHitInfo hitTestChar(float x, float y) {

        return hitTestChar(x, y, getNaturalBounds());
    }

    /**
     * Returns the hash code of this <code>TextLayout</code>.
     * @return the hash code of this <code>TextLayout</code>.
     */
    public int hashCode() {
        if (hashCodeCache == 0) {
	    ensureCache();
            hashCodeCache = textLine.hashCode();
        }
        return hashCodeCache;
    }

    /**
     * Returns <code>true</code> if the specified <code>Object</code> is a 
     * <code>TextLayout</code> object and if the specified <code>Object</code>
     * equals this <code>TextLayout</code>.
     * @param obj an <code>Object</code> to test for equality
     * @return <code>true</code> if the specified <code>Object</code>
     *      equals this <code>TextLayout</code> <code>false</code>
     *      otherwise.
     */
    public boolean equals(Object obj) {
        return (obj instanceof TextLayout) && equals((TextLayout)obj);
    }

    /**
     * Returns <code>true</code> if the two layouts are equal.
     * Two layouts are equal if they contain equal glyphvectors in the same order.
     * @param rhs the <code>TextLayout</code> to compare to this 
     *       <code>TextLayout</code>
     * @return <code>true</code> if the specified <code>TextLayout</code>
     *      equals this <code>TextLayout</code>.
     *
     */
    public boolean equals(TextLayout rhs) {

        if (rhs == null) {
            return false;
        }
        if (rhs == this) {
            return true;
        }

	ensureCache();
        return textLine.equals(rhs.textLine);
    }

    /**
     * Returns debugging information for this <code>TextLayout</code>.
     * @return the <code>textLine</code> of this <code>TextLayout</code>
     *        as a <code>String</code>.
     */
    public String toString() {
	ensureCache();
        return textLine.toString();
     }

    /**
     * Renders this <code>TextLayout</code> at the specified location in 
     * the specified {@link java.awt.Graphics2D Graphics2D} context.
     * The origin of the layout is placed at x, y.  Rendering may touch
     * any point within <code>getBounds()</code> of this position.  This 
     * leaves the <code>g2</code> unchanged.
     * @param g2 the <code>Graphics2D</code> context into which to render
     *         the layout
     * @param x, y the coordinates of the origin of this
     *          <code>TextLayout</code>
     * @see #getBounds()
     */
    public void draw(Graphics2D g2, float x, float y) {

        if (g2 == null) {
            throw new IllegalArgumentException("Null Graphics2D passed to TextLayout.draw()");
        }
        if (optInfo != null) {
            if (optInfo.draw(g2, x, y)) { // might fail to draw because of frc change
                return;
            }
            // replace with TextLine and fall through
            initTextLine();
        }
        textLine.draw(g2, x - dx, y - dy);
    }

    /**
     * Package-only method for testing ONLY.  Please don't abuse.
     */
    TextLine getTextLineForTesting() {

        return textLine;
    }

    /**
     *
     * Return the index of the first character with a different baseline from the
     * character at start, or limit if all characters between start and limit have
     * the same baseline.
     */
    private static int sameBaselineUpTo(Font font, char[] text,
                                        int start, int limit) {
        // current implementation doesn't support multiple baselines
        return limit;
        /*
        byte bl = font.getBaselineFor(text[start++]);
        while (start < limit && font.getBaselineFor(text[start]) == bl) {
            ++start;
        }
        return start;
        */
    }

    static byte getBaselineFromGraphic(GraphicAttribute graphic) {

        byte alignment = (byte) graphic.getAlignment();

        if (alignment == GraphicAttribute.BOTTOM_ALIGNMENT ||
                alignment == GraphicAttribute.TOP_ALIGNMENT) {

            return (byte)GraphicAttribute.ROMAN_BASELINE;
        }
        else {
            return alignment;
        }
    }

  /**
   * Returns a <code>Shape</code> representing the outline of this
   * <code>TextLayout</code>.
   * @param tx an optional {@link AffineTransform} to apply to the
   *     outline of this <code>TextLayout</code>.
   * @return a <code>Shape</code> that is the outline of this
   *     <code>TextLayout</code>.
   */
    public Shape getOutline(AffineTransform tx) {
	ensureCache();
        return textLine.getOutline(tx);
    }
}