/*

 * Copyright (c) 1997, 2006, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

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> 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,