/*
 * @(#)AttributedString.java	1.39 05/11/17
 *
 * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

package java.text;

import java.util.*;
import java.text.AttributedCharacterIterator.Attribute;

/**
 * An AttributedString holds text and related attribute information. It
 * may be used as the actual data storage in some cases where a text
 * reader wants to access attributed text through the AttributedCharacterIterator
 * interface.
 *
 * <p>
 * An attribute is a key/value pair, identified by the key.  No two
 * attributes on a given character can have the same key.
 *
 * <p>The values for an attribute are immutable, or must not be mutated
 * by clients or storage.  They are always passed by reference, and not
 * cloned.
 *
 * @see AttributedCharacterIterator
 * @see Annotation
 * @since 1.2
 */

public class AttributedString {

    // since there are no vectors of int, we have to use arrays.
    // We allocate them in chunks of 10 elements so we don't have to allocate all the time.
    private static final int ARRAY_SIZE_INCREMENT = 10;

    // field holding the text
    String text;
    
    // fields holding run attribute information
    // run attributes are organized by run
    int runArraySize;               // current size of the arrays
    int runCount;                   // actual number of runs, <= runArraySize
    int runStarts[];                // start index for each run
    Vector runAttributes[];         // vector of attribute keys for each run
    Vector runAttributeValues[];    // parallel vector of attribute values for each run

    /**
     * Constructs an AttributedString instance with the given
     * AttributedCharacterIterators.
     *
     * @param iterators AttributedCharacterIterators to construct
     * AttributedString from.
     * @throws NullPointerException if iterators is null
     */
    AttributedString(AttributedCharacterIterator[] iterators) {
	if (iterators == null) {
            throw new NullPointerException("Iterators must not be null");
	}
        if (iterators.length == 0) {
            text = "";
        }
        else {
            // Build the String contents
            StringBuffer buffer = new StringBuffer();
            for (int counter = 0; counter < iterators.length; counter++) {
                appendContents(buffer, iterators[counter]);
            }

            text = buffer.toString();

            if (text.length() > 0) {
                // Determine the runs, creating a new run when the attributes
                // differ.
                int offset = 0;
                Map last = null;

                for (int counter = 0; counter < iterators.length; counter++) {
                    AttributedCharacterIterator iterator = iterators[counter];
                    int start = iterator.getBeginIndex();
                    int end = iterator.getEndIndex();
                    int index = start;

                    while (index < end) {
                        iterator.setIndex(index);

                        Map attrs = iterator.getAttributes();

                        if (mapsDiffer(last, attrs)) {
                            setAttributes(attrs, index - start + offset);
                        }
                        last = attrs;
                        index = iterator.getRunLimit();
                    }
                    offset += (end - start);
                }
            }
        }
    }

    /**
     * Constructs an AttributedString instance with the given text.
     * @param text The text for this attributed string.
     * @exception NullPointerException if <code>text</code> is null.
     */
    public AttributedString(String text) {
        if (text == null) {
            throw new NullPointerException();
        }
        this.text = text;
    }
    
    /**
     * Constructs an AttributedString instance with the given text and attributes.
     * @param text The text for this attributed string.
     * @param attributes The attributes that apply to the entire string.
     * @exception NullPointerException if <code>text</code> or
     *            <code>attributes</code> is null.
     * @exception IllegalArgumentException if the text has length 0
     * and the attributes parameter is not an empty Map (attributes
     * cannot be applied to a 0-length range).
     */
    public AttributedString(String text,
			    Map<? extends Attribute, ?> attributes)
    {
        if (text == null || attributes == null) {
            throw new NullPointerException();
        }
        this.text = text;
        
        if (text.length() == 0) {
	    if (attributes.isEmpty())
		return;
            throw new IllegalArgumentException("Can't add attribute to 0-length text");
        }
        
        int attributeCount = attributes.size();
        if (attributeCount > 0) {
            createRunAttributeDataVectors();
            Vector newRunAttributes = new Vector(attributeCount);
            Vector newRunAttributeValues = new Vector(attributeCount);
            runAttributes[0] = newRunAttributes;
            runAttributeValues[0] = newRunAttributeValues;
            Iterator iterator = attributes.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry entry = (Map.Entry) iterator.next();
                newRunAttributes.addElement(entry.getKey());
                newRunAttributeValues.addElement(entry.getValue());
            }
        }
    }
    
    /**
     * Constructs an AttributedString instance with the given attributed
     * text represented by AttributedCharacterIterator.
     * @param text The text for this attributed string.
     * @exception NullPointerException if <code>text</code> is null.
     */
    public AttributedString(AttributedCharacterIterator text) {
	// If performance is critical, this constructor should be
	// implemented here rather than invoking the constructor for a
	// subrange. We can avoid some range checking in the loops.
	this(text, text.getBeginIndex(), text.getEndIndex(), null);
    }

    /**
     * Constructs an AttributedString instance with the subrange of
     * the given attributed text represented by
     * AttributedCharacterIterator. If the given range produces an
     * empty text, all attributes will be discarded.  Note that any
     * attributes wrapped by an Annotation object are discarded for a
     * subrange of the original attribute range.
     *
     * @param text The text for this attributed string.
     * @param beginIndex Index of the first character of the range.
     * @param endIndex Index of the character following the last character
     * of the range.
     * @exception NullPointerException if <code>text</code> is null.
     * @exception IllegalArgumentException if the subrange given by
     * beginIndex and endIndex is out of the text range.
     * @see java.text.Annotation
     */
    public AttributedString(AttributedCharacterIterator text,
			    int beginIndex,
			    int endIndex) {
	this(text, beginIndex, endIndex, null);
    }

    /**
     * Constructs an AttributedString instance with the subrange of
     * the given attributed text represented by
     * AttributedCharacterIterator.  Only attributes that match the
     * given attributes will be incorporated into the instance. If the
     * given range produces an empty text, all attributes will be
     * discarded. Note that any attributes wrapped by an Annotation
     * object are discarded for a subrange of the original attribute
     * range.
     *
     * @param text The text for this attributed string.
     * @param beginIndex Index of the first character of the range.
     * @param endIndex Index of the character following the last character
     * of the range.
     * @param attributes Specifies attributes to be extracted
     * from the text. If null is specified, all available attributes will
     * be used.
     * @exception NullPointerException if <code>text</code> or
     *            <code>attributes</code> is null.
     * @exception IllegalArgumentException if the subrange given by
     * beginIndex and endIndex is out of the text range.
     * @see java.text.Annotation
     */
    public AttributedString(AttributedCharacterIterator text,
			    int beginIndex,
			    int endIndex,
			    Attribute[] attributes) {
        if (text == null) {
            throw new NullPointerException();
        }

	// Validate the given subrange
	int textBeginIndex = text.getBeginIndex();
	int textEndIndex = text.getEndIndex();
	if (beginIndex < textBeginIndex || endIndex > textEndIndex || beginIndex > endIndex)
	    throw new IllegalArgumentException("Invalid substring range");

	// Copy the given string
	StringBuffer textBuffer = new StringBuffer();
	text.setIndex(beginIndex);
	for (char c = text.current(); text.getIndex() < endIndex; c = text.next())
	    textBuffer.append(c);
	this.text = textBuffer.toString();

	if (beginIndex == endIndex)
	    return;

	// Select attribute keys to be taken care of
	HashSet keys = new HashSet();
	if (attributes == null) {
	    keys.addAll(text.getAllAttributeKeys());
	} else {
	    for (int i = 0; i < attributes.length; i++)
		keys.add(attributes[i]);
	    keys.retainAll(text.getAllAttributeKeys());
	}
	if (keys.isEmpty())
	    return;

	// Get and set attribute runs for each attribute name. Need to
	// scan from the top of the text so that we can discard any
	// Annotation that is no longer applied to a subset text segment.
	Iterator itr = keys.iterator();
	while (itr.hasNext()) {
	    Attribute attributeKey = (Attribute)itr.next();
	    text.setIndex(textBeginIndex);
	    while (text.getIndex() < endIndex) {
		int start = text.getRunStart(attributeKey);
		int limit = text.getRunLimit(attributeKey);
		Object value = text.getAttribute(attributeKey);

		if (value != null) {
		    if (value instanceof Annotation) {
			if (start >= beginIndex && limit <= endIndex) {
			    addAttribute(attributeKey, value, start - beginIndex, limit - beginIndex);
			} else {
			    if (limit > endIndex)
				break;
			}
		    } else {
			// if the run is beyond the given (subset) range, we
			// don't need to process further.
			if (start >= endIndex)
			    break;
			if (limit > beginIndex) {
			    // attribute is applied to any subrange
			    if (start < beginIndex)
				start = beginIndex;
			    if (limit > endIndex)
				limit = endIndex;
			    if (start != limit) {
				addAttribute(attributeKey, value, start - beginIndex, limit - beginIndex);
			    }
			}
		    }
		}
		text.setIndex(limit);
	    }
	}
    }

    /**
     * Adds an attribute to the entire string.
     * @param attribute the attribute key
     * @param value the value of the attribute; may be null
     * @exception NullPointerException if <code>attribute</code> is null.
     * @exception IllegalArgumentException if the AttributedString has length 0
     * (attributes cannot be applied to a 0-length range).
     */
    public void addAttribute(Attribute attribute, Object value) {
        
        if (attribute == null) {
            throw new NullPointerException();
        }

        int len = length();
        if (len == 0) {
            throw new IllegalArgumentException("Can't add attribute to 0-length text");
        }
        
        addAttributeImpl(attribute, value, 0, len);
    }

    /**
     * Adds an attribute to a subrange of the string.
     * @param attribute the attribute key
     * @param value The value of the attribute. May be null.
     * @param beginIndex Index of the first character of the range.
     * @param endIndex Index of the character following the last character of the range.
     * @exception NullPointerException if <code>attribute</code> is null.
     * @exception IllegalArgumentException if beginIndex is less then 0, endIndex is
     * greater than the length of the string, or beginIndex and endIndex together don't
     * define a non-empty subrange of the string.
     */
    public void addAttribute(Attribute attribute, Object value,
            int beginIndex, int endIndex) {
        
        if (attribute == null) {
            throw new NullPointerException();
        }

        if (beginIndex < 0 || endIndex > length() || beginIndex >= endIndex) {
            throw new IllegalArgumentException("Invalid substring range");
        }
        
        addAttributeImpl(attribute, value, beginIndex, endIndex);
    }
    
    /**
     * Adds a set of attributes to a subrange of the string.
     * @param attributes The attributes to be added to the string.
     * @param beginIndex Index of the first character of the range.
     * @param endIndex Index of the character following the last
     * character of the range.
     * @exception NullPointerException if <code>attributes</code> is null.
     * @exception IllegalArgumentException if beginIndex is less then
     * 0, endIndex is greater than the length of the string, or
     * beginIndex and endIndex together don't define a non-empty
     * subrange of the string and the attributes parameter is not an
     * empty Map.
     */
    public void addAttributes(Map<? extends Attribute, ?> attributes,
			      int beginIndex, int endIndex)
    {
        if (attributes == null) {
            throw new NullPointerException();
        }

        if (beginIndex < 0 || endIndex > length() || beginIndex > endIndex) {
            throw new IllegalArgumentException("Invalid substring range");
        }
	if (beginIndex == endIndex) {
	    if (attributes.isEmpty())
		return;
            throw new IllegalArgumentException("Can't add attribute to 0-length text");
        }

        // make sure we have run attribute data vectors
        if (runCount == 0) {
            createRunAttributeDataVectors();
        }
        
        // break up runs if necessary
        int beginRunIndex = ensureRunBreak(beginIndex);
        int endRunIndex = ensureRunBreak(endIndex);
        
        Iterator iterator = attributes.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator.next();
            addAttributeRunData((Attribute) entry.getKey(), entry.getValue(), beginRunIndex, endRunIndex);
        }
    }

    private synchronized void addAttributeImpl(Attribute attribute, Object value,
            int beginIndex, int endIndex) {
        
        // make sure we have run attribute data vectors
        if (runCount == 0) {
            createRunAttributeDataVectors();
        }
        
        // break up runs if necessary
        int beginRunIndex = ensureRunBreak(beginIndex);
        int endRunIndex = ensureRunBreak(endIndex);
        
        addAttributeRunData(attribute, value, beginRunIndex, endRunIndex);
    }
    
    private final void createRunAttributeDataVectors() {
        // use temporary variables so things remain consistent in case of an exception
        int newRunStarts[] = new int[ARRAY_SIZE_INCREMENT];
        Vector newRunAttributes[] = new Vector[ARRAY_SIZE_INCREMENT];
        Vector newRunAttributeValues[] = new Vector[ARRAY_SIZE_INCREMENT];
        runStarts = newRunStarts;
        runAttributes = newRunAttributes;
        runAttributeValues = newRunAttributeValues;
        runArraySize = ARRAY_SIZE_INCREMENT;
        runCount = 1; // assume initial run starting at index 0
    }

    // ensure there's a run break at offset, return the index of the run
    private final int ensureRunBreak(int offset) {
        return ensureRunBreak(offset, true);
    }

    /**
     * Ensures there is a run break at offset, returning the index of
     * the run. If this results in splitting a run, two things can happen:
     * <ul>
     * <li>If copyAttrs is true, the attributes from the existing run
     *     will be placed in both of the newly created runs.
     * <li>If copyAttrs is false, the attributes from the existing run
     * will NOT be copied to the run to the right (>= offset) of the break,
     * but will exist on the run to the left (< offset).
     * </ul>
     */
    private final int ensureRunBreak(int offset, boolean copyAttrs) {
        if (offset == length()) {
            return runCount;
        }

        // search for the run index where this offset should be
        int runIndex = 0;
        while (runIndex < runCount && runStarts[runIndex] < offset) {
            runIndex++;
        }

        // if the offset is at a run start already, we're done
        if (runIndex < runCount && runStarts[runIndex] == offset) {
            return runIndex;
        }
        
        // we'll have to break up a run
        // first, make sure we have enough space in our arrays
        if (runCount == runArraySize) {
            int newArraySize = runArraySize + ARRAY_SIZE_INCREMENT;
            int newRunStarts[] = new int[newArraySize];
            Vector newRunAttributes[] = new Vector[newArraySize];
            Vector newRunAttributeValues[] = new Vector[newArraySize];
            for (int i = 0; i < runArraySize; i++) {
                newRunStarts[i] = runStarts[i];
                newRunAttributes[i] = runAttributes[i];
                newRunAttributeValues[i] = runAttributeValues[i];
            }
            runStarts = newRunStarts;
            runAttributes = newRunAttributes;
            runAttributeValues = newRunAttributeValues;
            runArraySize = newArraySize;
        }
        
        // make copies of the attribute information of the old run that the new one used to be part of
        // use temporary variables so things remain consistent in case of an exception
        Vector newRunAttributes = null;
        Vector newRunAttributeValues = null;

        if (copyAttrs) {
            Vector oldRunAttributes = runAttributes[runIndex - 1];
            Vector oldRunAttributeValues = runAttributeValues[runIndex - 1];
            if (oldRunAttributes != null) {
                newRunAttributes = (Vector) oldRunAttributes.clone();
            }
            if (oldRunAttributeValues != null) {
                newRunAttributeValues = (Vector) oldRunAttributeValues.clone();
            }
        }
        
        // now actually break up the run
        runCount++;
        for (int i = runCount - 1; i > runIndex; i--) {
            runStarts[i] = runStarts[i - 1];
            runAttributes[i] = runAttributes[i - 1];
            runAttributeValues[i] = runAttributeValues[i - 1];
        }
        runStarts[runIndex] = offset;
        runAttributes[runIndex] = newRunAttributes;
        runAttributeValues[runIndex] = newRunAttributeValues;

        return runIndex;
    }

    // add the attribute attribute/value to all runs where beginRunIndex <= runIndex < endRunIndex
    private void addAttributeRunData(Attribute attribute, Object value,
            int beginRunIndex, int endRunIndex) {

        for (int i = beginRunIndex; i < endRunIndex; i++) {
            int keyValueIndex = -1; // index of key and value in our vectors; assume we don't have an entry yet
            if (runAttributes[i] == null) {
                Vector newRunAttributes = new Vector();
                Vector newRunAttributeValues = new Vector();
                runAttributes[i] = newRunAttributes;
                runAttributeValues[i] = newRunAttributeValues;
            } else {
                // check whether we have an entry already
                keyValueIndex = runAttributes[i].indexOf(attribute);
            }

            if (keyValueIndex == -1) {
                // create new entry
                int oldSize = runAttributes[i].size();
                runAttributes[i].addElement(attribute);
                try {
                    runAttributeValues[i].addElement(value);
                }
                catch (Exception e) {
                    runAttributes[i].setSize(oldSize);
                    runAttributeValues[i].setSize(oldSize);
                }
            } else {
                // update existing entry
                runAttributeValues[i].set(keyValueIndex, value);
            }
        }
    }

    /**
     * Creates an AttributedCharacterIterator instance that provides access to the entire contents of
     * this string.
     *
     * @return An iterator providing access to the text and its attributes.
     */
    public AttributedCharacterIterator getIterator() {
        return getIterator(null, 0, length());
    }

    /**
     * Creates an AttributedCharacterIterator instance that provides access to
     * selected contents of this string.
     * Information about attributes not listed in attributes that the
     * implementor may have need not be made accessible through the iterator.
     * If the list is null, all available attribute information should be made
     * accessible.
     *
     * @param attributes a list of attributes that the client is interested in
     * @return an iterator providing access to the entire text and its selected attributes
     */
    public AttributedCharacterIterator getIterator(Attribute[] attributes) {
        return getIterator(attributes, 0, length());
    }

    /**
     * Creates an AttributedCharacterIterator instance that provides access to
     * selected contents of this string.
     * Information about attributes not listed in attributes that the
     * implementor may have need not be made accessible through the iterator.
     * If the list is null, all available attribute information should be made
     * accessible.
     *
     * @param attributes a list of attributes that the client is interested in
     * @param beginIndex the index of the first character
     * @param endIndex the index of the character following the last character
     * @return an iterator providing access to the text and its attributes
     * @exception IllegalArgumentException if beginIndex is less then 0,
     * endIndex is greater than the length of the string, or beginIndex is
     * greater than endIndex.
     */
    public AttributedCharacterIterator getIterator(Attribute[] attributes, int beginIndex, int endIndex) {
        return new AttributedStringIterator(attributes, beginIndex, endIndex);
    }

    // all (with the exception of length) reading operations are private,
    // since AttributedString instances are accessed through iterators.

    // length is package private so that CharacterIteratorFieldDelegate can
    // access it without creating an AttributedCharacterIterator.
    int length() {
        return text.length();
    }
    
    private char charAt(int index) {
        return text.charAt(index);
    }
    
    private synchronized Object getAttribute(Attribute attribute, int runIndex) {
        Vector currentRunAttributes = runAttributes[runIndex];
        Vector currentRunAttributeValues = runAttributeValues[runIndex];
        if (currentRunAttributes == null) {
            return null;
        }
        int attributeIndex = currentRunAttributes.indexOf(attribute);
        if (attributeIndex != -1) {
            return currentRunAttributeValues.elementAt(attributeIndex);
        }
        else {
            return null;
        }
    }

    // gets an attribute value, but returns an annotation only if it's range does not extend outside the range beginIndex..endIndex
    private Object getAttributeCheckRange(Attribute attribute, int runIndex, int beginIndex, int endIndex) {
        Object value = getAttribute(attribute, runIndex);
        if (value instanceof Annotation) {
            // need to check whether the annotation's range extends outside the iterator's range
            if (beginIndex > 0) {
                int currIndex = runIndex;
                int runStart = runStarts[currIndex];
                while (runStart >= beginIndex &&
                        valuesMatch(value, getAttribute(attribute, currIndex - 1))) {
                    currIndex--;
                    runStart = runStarts[currIndex];
                }
                if (runStart < beginIndex) {
                    // annotation's range starts before iterator's range
                    return null;
                }
            }
            int textLength = length();
            if (endIndex < textLength) {
                int currIndex = runIndex;
                int runLimit = (currIndex < runCount - 1) ? runStarts[currIndex + 1] : textLength;
                while (runLimit <= endIndex &&
                        valuesMatch(value, getAttribute(attribute, currIndex + 1))) {
                    currIndex++;
                    runLimit = (currIndex < runCount - 1) ? runStarts[currIndex + 1] : textLength;
                }
                if (runLimit > endIndex) {
                    // annotation's range ends after iterator's range
                    return null;
                }
            }
            // annotation's range is subrange of iterator's range,
            // so we can return the value
        }
        return value;
    }

    // returns whether all specified attributes have equal values in the runs with the given indices
    private boolean attributeValuesMatch(Set attributes, int runIndex1, int runIndex2) {
        Iterator iterator = attributes.iterator();
        while (iterator.hasNext()) {
            Attribute key = (Attribute) iterator.next();
           if (!valuesMatch(getAttribute(key, runIndex1), getAttribute(key, runIndex2))) {
                return false;
            }
        }
        return true;
    }

    // returns whether the two objects are either both null or equal
    private final static boolean valuesMatch(Object value1, Object value2) {
        if (value1 == null) {
            return value2 == null;
        } else {
            return value1.equals(value2);
        }
    }

    /**
     * Appends the contents of the CharacterIterator iterator into the
     * StringBuffer buf.
     */
    private final void appendContents(StringBuffer buf,
                                      CharacterIterator iterator) {
        int index = iterator.getBeginIndex();
        int end = iterator.getEndIndex();

        while (index < end) {
            iterator.setIndex(index++);
            buf.append(iterator.current());
        }
    }

    /**
     * Sets the attributes for the range from offset to the next run break 
     * (typically the end of the text) to the ones specified in attrs.
     * This is only meant to be called from the constructor!
     */
    private void setAttributes(Map attrs, int offset) {
        if (runCount == 0) {
            createRunAttributeDataVectors();
        }

        int index = ensureRunBreak(offset, false);
        int size;

        if (attrs != null && (size = attrs.size()) > 0) {
            Vector runAttrs = new Vector(size);
            Vector runValues = new Vector(size);
            Iterator iterator = attrs.entrySet().iterator();

            while (iterator.hasNext()) {
                Map.Entry entry = (Map.Entry)iterator.next();

                runAttrs.add(entry.getKey());
                runValues.add(entry.getValue());
            }
            runAttributes[index] = runAttrs;
            runAttributeValues[index] = runValues;	    
        }
    }

    /**
     * Returns true if the attributes specified in last and attrs differ.
     */
    private static boolean mapsDiffer(Map last, Map attrs) {
        if (last == null) {
            return (attrs != null && attrs.size() > 0);
        }
        return (!last.equals(attrs));
    }


    // the iterator class associated with this string class

    final private class AttributedStringIterator implements AttributedCharacterIterator {
        
        // note on synchronization:
        // we don't synchronize on the iterator, assuming that an iterator is only used in one thread.
        // we do synchronize access to the AttributedString however, since it's more likely to be shared between threads.

        // start and end index for our iteration
        private int beginIndex;
        private int endIndex;
        
        // attributes that our client is interested in
        private Attribute[] relevantAttributes;

        // the current index for our iteration
        // invariant: beginIndex <= currentIndex <= endIndex
        private int currentIndex;

        // information about the run that includes currentIndex
        private int currentRunIndex;
        private int currentRunStart;
        private int currentRunLimit;
        
        // constructor
        AttributedStringIterator(Attribute[] attributes, int beginIndex, int endIndex) {
        
            if (beginIndex < 0 || beginIndex > endIndex || endIndex > length()) {
                throw new IllegalArgumentException("Invalid substring range");
            }
            
            this.beginIndex = beginIndex;
            this.endIndex = endIndex;
            this.currentIndex = beginIndex;
            updateRunInfo();
            if (attributes != null) {
                relevantAttributes = (Attribute[]) attributes.clone();
            }
        }
        
        // Object methods. See documentation in that class.
        
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (!(obj instanceof AttributedStringIterator)) {
                return false;
            }

            AttributedStringIterator that = (AttributedStringIterator) obj;

            if (AttributedString.this != that.getString())
                return false;
            if (currentIndex != that.currentIndex || beginIndex != that.beginIndex || endIndex != that.endIndex)
                return false;
            return true;
        }

        public int hashCode() {
            return text.hashCode() ^ currentIndex ^ beginIndex ^ endIndex;
        }

        public Object clone() {
            try {
                AttributedStringIterator other = (AttributedStringIterator) super.clone();
                return other;
            }
            catch (CloneNotSupportedException e) {
                throw new InternalError();
            }
        }
        
        // CharacterIterator methods. See documentation in that interface.
        
        public char first() {
            return internalSetIndex(beginIndex);
        }
        
        public char last() {
            if (endIndex == beginIndex) {
                return internalSetIndex(endIndex);
            } else {
                return internalSetIndex(endIndex - 1);
            }
        }
        
        public char current() {
            if (currentIndex == endIndex) {
                return DONE;
            } else {
                return charAt(currentIndex);
            }
        }

        public char next() {
            if (currentIndex < endIndex) {
                return internalSetIndex(currentIndex + 1);
            }
            else {
                return DONE;
            }
        }

        public char previous() {
            if (currentIndex > beginIndex) {
                return internalSetIndex(currentIndex - 1);
            }
            else {
                return DONE;
            }
        }

        public char setIndex(int position) {
            if (position < beginIndex || position > endIndex)
                throw new IllegalArgumentException("Invalid index");
            return internalSetIndex(position);
        }

        public int getBeginIndex() {
            return beginIndex;
        }

        public int getEndIndex() {
            return endIndex;
        }

        public int getIndex() {
            return currentIndex;
        }

        // AttributedCharacterIterator methods. See documentation in that interface.

        public int getRunStart() {
            return currentRunStart;
        }
        
        public int getRunStart(Attribute attribute) {
            if (currentRunStart == beginIndex || currentRunIndex == -1) {
                return currentRunStart;
            } else {
                Object value = getAttribute(attribute);
                int runStart = currentRunStart;
                int runIndex = currentRunIndex;
                while (runStart > beginIndex &&
                        valuesMatch(value, AttributedString.this.getAttribute(attribute, runIndex - 1))) {
                    runIndex--;
                    runStart = runStarts[runIndex];
                }
                if (runStart < beginIndex) {
                    runStart = beginIndex;
                }
                return runStart;
            }
        }

        public int getRunStart(Set<? extends Attribute> attributes) {
            if (currentRunStart == beginIndex || currentRunIndex == -1) {
                return currentRunStart;
            } else {
                int runStart = currentRunStart;
                int runIndex = currentRunIndex;
                while (runStart > beginIndex &&
                        AttributedString.this.attributeValuesMatch(attributes, currentRunIndex, runIndex - 1)) {
                    runIndex--;
                    runStart = runStarts[runIndex];
                }
                if (runStart < beginIndex) {
                    runStart = beginIndex;
                }
                return runStart;
            }
        }

        public int getRunLimit() {
            return currentRunLimit;
        }
        
        public int getRunLimit(Attribute attribute) {
            if (currentRunLimit == endIndex || currentRunIndex == -1) {
                return currentRunLimit;
            } else {
                Object value = getAttribute(attribute);
                int runLimit = currentRunLimit;
                int runIndex = currentRunIndex;
                while (runLimit < endIndex &&
                        valuesMatch(value, AttributedString.this.getAttribute(attribute, runIndex + 1))) {
                    runIndex++;
                    runLimit = runIndex < runCount - 1 ? runStarts[runIndex + 1] : endIndex;
                }
                if (runLimit > endIndex) {
                    runLimit = endIndex;
                }
                return runLimit;
            }
        }
        
        public int getRunLimit(Set<? extends Attribute> attributes) {
            if (currentRunLimit == endIndex || currentRunIndex == -1) {
                return currentRunLimit;
            } else {
                int runLimit = currentRunLimit;
                int runIndex = currentRunIndex;
                while (runLimit < endIndex &&
                        AttributedString.this.attributeValuesMatch(attributes, currentRunIndex, runIndex + 1)) {
                    runIndex++;
                    runLimit = runIndex < runCount - 1 ? runStarts[runIndex + 1] : endIndex;
                }
                if (runLimit > endIndex) {
                    runLimit = endIndex;
                }
                return runLimit;
            }
        }
        
        public Map<Attribute,Object> getAttributes() {
            if (runAttributes == null || currentRunIndex == -1 || runAttributes[currentRunIndex] == null) {
                // ??? would be nice to return null, but current spec doesn't allow it
                // returning Hashtable saves AttributeMap from dealing with emptiness
                return new Hashtable();
            }
            return new AttributeMap(currentRunIndex, beginIndex, endIndex);
        }
        
        public Set<Attribute> getAllAttributeKeys() {
            // ??? This should screen out attribute keys that aren't relevant to the client
            if (runAttributes == null) {
                // ??? would be nice to return null, but current spec doesn't allow it
                // returning HashSet saves us from dealing with emptiness
                return new HashSet();
            }
            synchronized (AttributedString.this) {
                // ??? should try to create this only once, then update if necessary,
                // and give callers read-only view
                Set keys = new HashSet();
                int i = 0;
                while (i < runCount) {
                    if (runStarts[i] < endIndex && (i == runCount - 1 || runStarts[i + 1] > beginIndex)) {
                        Vector currentRunAttributes = runAttributes[i];
                        if (currentRunAttributes != null) {
                            int j = currentRunAttributes.size();
                            while (j-- > 0) {
                                keys.add(currentRunAttributes.get(j));
                            }
                        }
                    }
                    i++;
                }
                return keys;
            }
        }
        
        public Object getAttribute(Attribute attribute) {
            int runIndex = currentRunIndex;
            if (runIndex < 0) {
                return null;
            }
            return AttributedString.this.getAttributeCheckRange(attribute, runIndex, beginIndex, endIndex);
        }
        
        // internally used methods
        
        private AttributedString getString() {
            return AttributedString.this;
        }
        
        // set the current index, update information about the current run if necessary,
        // return the character at the current index
        private char internalSetIndex(int position) {
            currentIndex = position;
            if (position < currentRunStart || position >= currentRunLimit) {
                updateRunInfo();
            }
            if (currentIndex == endIndex) {
                return DONE;
            } else {
                return charAt(position);
            }
        }

        // update the information about the current run
        private void updateRunInfo() {
            if (currentIndex == endIndex) {
                currentRunStart = currentRunLimit = endIndex;
                currentRunIndex = -1;
            } else {
                synchronized (AttributedString.this) {
                    int runIndex = -1;
                    while (runIndex < runCount - 1 && runStarts[runIndex + 1] <= currentIndex)
                        runIndex++;
                    currentRunIndex = runIndex;
                    if (runIndex >= 0) {
                        currentRunStart = runStarts[runIndex];
                        if (currentRunStart < beginIndex)
                            currentRunStart = beginIndex;
                    }
                    else {
                        currentRunStart = beginIndex;
                    }
                    if (runIndex < runCount - 1) {
                        currentRunLimit = runStarts[runIndex + 1];
                        if (currentRunLimit > endIndex)
                            currentRunLimit = endIndex;
                    }
                    else {
                        currentRunLimit = endIndex;
                    }
                }
            }
        }

    }

    // the map class associated with this string class, giving access to the attributes of one run

    final private class AttributeMap extends AbstractMap<Attribute,Object> {
    
        int runIndex;
        int beginIndex;
        int endIndex;

        AttributeMap(int runIndex, int beginIndex, int endIndex) {
            this.runIndex = runIndex;
            this.beginIndex = beginIndex;
            this.endIndex = endIndex;
        }

        public Set entrySet() {
            HashSet set = new HashSet();
            synchronized (AttributedString.this) {
                int size = runAttributes[runIndex].size();
                for (int i = 0; i < size; i++) {
                    Attribute key = (Attribute) runAttributes[runIndex].get(i);
                    Object value = runAttributeValues[runIndex].get(i);
                    if (value instanceof Annotation) {
                        value = AttributedString.this.getAttributeCheckRange(key,
							     runIndex, beginIndex, endIndex);
                        if (value == null) {
                            continue;
                        }
                    }
                    Map.Entry entry = new AttributeEntry(key, value);
                    set.add(entry);
                }
            }
            return set;
        }
        
        public Object get(Object key) {
            return AttributedString.this.getAttributeCheckRange((Attribute) key, runIndex, beginIndex, endIndex);
        }
    }
}

class AttributeEntry implements Map.Entry {

    private Attribute key;
    private Object value;

    AttributeEntry(Attribute key, Object value) {
        this.key = key;
        this.value = value;
    }
    
    public boolean equals(Object o) {
        if (!(o instanceof AttributeEntry)) {
            return false;
        }
        AttributeEntry other = (AttributeEntry) o;
        return other.key.equals(key) &&
            (value == null ? other.value == null : other.value.equals(value));
    }
    
    public Object getKey() {
        return key;
    }
    
    public Object getValue() {
        return value;
    }
    
    public Object setValue(Object newValue) {
        throw new UnsupportedOperationException();
    }
    
    public int hashCode() {
        return key.hashCode() ^ (value==null ? 0 : value.hashCode());
    }

    public String toString() {
        return key.toString()+"="+value.toString();
    }
}