/*

 * Copyright (c) 1997, 2019, 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 {

    // field holding the text

    String text;

    // Fields holding run attribute information.

    // Run attributes are organized by run.

    // Arrays are always of equal lengths (the current capacity).

    // Since there are no vectors of int, we have to use arrays.

    private static final int INITIAL_CAPACITY = 10;

    int runCount;                   // actual number of runs, <= current capacity

    int[] runStarts;                // start index for each run

    Vector<Attribute>[] runAttributes;   // vector of attribute keys for each run

    Vector<Object>[] 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.isEmpty()) {

                // Determine the runs, creating a new run when the attributes

                // differ.

                int offset = 0;

                Map<Attribute,Object> 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<Attribute,Object> 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.

     * @throws    NullPointerException if {@code text} 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.

     * @throws    NullPointerException if {@code text} or

     *            {@code attributes} is null.

     * @throws    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.isEmpty()) {

            if (attributes.isEmpty())

                return;

            throw new IllegalArgumentException("Can't add attribute to 0-length text");

        }

        int attributeCount = attributes.size();

        if (attributeCount > 0) {

            createRunAttributeDataVectors();

            Vector<Attribute> newRunAttributes = new Vector<>(attributeCount);

            Vector<Object> newRunAttributeValues = new Vector<>(attributeCount);

            runAttributes[0] = newRunAttributes;

            runAttributeValues[0] = newRunAttributeValues;

            Iterator<? extends Map.Entry<? extends Attribute, ?>> iterator = attributes.entrySet().iterator();

            while (iterator.hasNext()) {

                Map.Entry<? extends Attribute, ?> 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.

     * @throws    NullPointerException if {@code text} 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.

     * @throws    NullPointerException if {@code text} is null.

     * @throws    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.

     * @throws    NullPointerException if {@code text} is null.

     * @throws    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

        StringBuilder textBuilder = new StringBuilder();

        text.setIndex(beginIndex);

        for (char c = text.current(); text.getIndex() < endIndex; c = text.next())

            textBuilder.append(c);

        this.text = textBuilder.toString();

        if (beginIndex == endIndex)

            return;

        // Select attribute keys to be taken care of

        HashSet<Attribute> 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<Attribute> itr = keys.iterator();

        while (itr.hasNext()) {

            Attribute attributeKey = 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

     * @throws    NullPointerException if {@code attribute} is null.

     * @throws    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.

     * @throws    NullPointerException if {@code attribute} is null.

     * @throws    IllegalArgumentException if beginIndex is less than 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.

     * @throws    NullPointerException if {@code attributes} is null.

     * @throws    IllegalArgumentException if beginIndex is less than

     * 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<? extends Map.Entry<? extends Attribute, ?>> iterator =

            attributes.entrySet().iterator();

        while (iterator.hasNext()) {

            Map.Entry<? extends Attribute, ?> entry = iterator.next();

            addAttributeRunData(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[INITIAL_CAPACITY];

        @SuppressWarnings("unchecked")

        Vector<Attribute>[] newRunAttributes = (Vector<Attribute>[]) new Vector<?>[INITIAL_CAPACITY];

        @SuppressWarnings("unchecked")

        Vector<Object>[] newRunAttributeValues = (Vector<Object>[]) new Vector<?>[INITIAL_CAPACITY];

        runStarts = newRunStarts;

        runAttributes = newRunAttributes;

        runAttributeValues = newRunAttributeValues;

        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

        int currentCapacity = runStarts.length;

        if (runCount == currentCapacity) {

            // We need to resize - we grow capacity by 25%.

            int newCapacity = currentCapacity + (currentCapacity >> 2);

            // use temporary variables so things remain consistent in case of an exception

            int[] newRunStarts =

                Arrays.copyOf(runStarts, newCapacity);

            Vector<Attribute>[] newRunAttributes =

                Arrays.copyOf(runAttributes, newCapacity);

            Vector<Object>[] newRunAttributeValues =

                Arrays.copyOf(runAttributeValues, newCapacity);

            runStarts = newRunStarts;

            runAttributes = newRunAttributes;

            runAttributeValues = newRunAttributeValues;

        }

        // 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<Attribute> newRunAttributes = null;

        Vector<Object> newRunAttributeValues = null;

        if (copyAttrs) {

            Vector<Attribute> oldRunAttributes = runAttributes[runIndex - 1];

            Vector<Object> oldRunAttributeValues = runAttributeValues[runIndex - 1];

            if (oldRunAttributes != null) {

                newRunAttributes = new Vector<>(oldRunAttributes);

            }

            if (oldRunAttributeValues != null) {

                newRunAttributeValues =  new Vector<>(oldRunAttributeValues);

            }

        }

        // 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) {