1 /*
   2  * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.text;
  27 
  28 import java.util.*;
  29 import java.text.AttributedCharacterIterator.Attribute;
  30 
  31 /**
  32  * An AttributedString holds text and related attribute information. It
  33  * may be used as the actual data storage in some cases where a text
  34  * reader wants to access attributed text through the AttributedCharacterIterator
  35  * interface.
  36  *
  37  * <p>
  38  * An attribute is a key/value pair, identified by the key.  No two
  39  * attributes on a given character can have the same key.
  40  *
  41  * <p>The values for an attribute are immutable, or must not be mutated
  42  * by clients or storage.  They are always passed by reference, and not
  43  * cloned.
  44  *
  45  * @see AttributedCharacterIterator
  46  * @see Annotation
  47  * @since 1.2
  48  */
  49 
  50 public class AttributedString {
  51     // field holding the text
  52     String text;
  53 
  54     // Fields holding run attribute information.
  55     // Run attributes are organized by run.
  56     // Arrays are always of equal lengths (the current capacity).
  57     // Since there are no vectors of int, we have to use arrays.
  58     private static final int INITIAL_CAPACITY = 10;
  59     int runCount;                   // actual number of runs, <= current capacity
  60     int[] runStarts;                // start index for each run
  61     Vector<Attribute>[] runAttributes;   // vector of attribute keys for each run
  62     Vector<Object>[] runAttributeValues; // parallel vector of attribute values for each run
  63 
  64     /**
  65      * Constructs an AttributedString instance with the given
  66      * AttributedCharacterIterators.
  67      *
  68      * @param iterators AttributedCharacterIterators to construct
  69      * AttributedString from.
  70      * @throws NullPointerException if iterators is null
  71      */
  72     AttributedString(AttributedCharacterIterator[] iterators) {
  73         if (iterators == null) {
  74             throw new NullPointerException("Iterators must not be null");
  75         }
  76         if (iterators.length == 0) {
  77             text = "";
  78         }
  79         else {
  80             // Build the String contents
  81             StringBuffer buffer = new StringBuffer();
  82             for (int counter = 0; counter < iterators.length; counter++) {
  83                 appendContents(buffer, iterators[counter]);
  84             }
  85 
  86             text = buffer.toString();
  87 
  88             if (text.length() > 0) {
  89                 // Determine the runs, creating a new run when the attributes
  90                 // differ.
  91                 int offset = 0;
  92                 Map<Attribute,Object> last = null;
  93 
  94                 for (int counter = 0; counter < iterators.length; counter++) {
  95                     AttributedCharacterIterator iterator = iterators[counter];
  96                     int start = iterator.getBeginIndex();
  97                     int end = iterator.getEndIndex();
  98                     int index = start;
  99 
 100                     while (index < end) {
 101                         iterator.setIndex(index);
 102 
 103                         Map<Attribute,Object> attrs = iterator.getAttributes();
 104 
 105                         if (mapsDiffer(last, attrs)) {
 106                             setAttributes(attrs, index - start + offset);
 107                         }
 108                         last = attrs;
 109                         index = iterator.getRunLimit();
 110                     }
 111                     offset += (end - start);
 112                 }
 113             }
 114         }
 115     }
 116 
 117     /**
 118      * Constructs an AttributedString instance with the given text.
 119      * @param text The text for this attributed string.
 120      * @exception NullPointerException if <code>text</code> is null.
 121      */
 122     public AttributedString(String text) {
 123         if (text == null) {
 124             throw new NullPointerException();
 125         }
 126         this.text = text;
 127     }
 128 
 129     /**
 130      * Constructs an AttributedString instance with the given text and attributes.
 131      * @param text The text for this attributed string.
 132      * @param attributes The attributes that apply to the entire string.
 133      * @exception NullPointerException if <code>text</code> or
 134      *            <code>attributes</code> is null.
 135      * @exception IllegalArgumentException if the text has length 0
 136      * and the attributes parameter is not an empty Map (attributes
 137      * cannot be applied to a 0-length range).
 138      */
 139     public AttributedString(String text,
 140                             Map<? extends Attribute, ?> attributes)
 141     {
 142         if (text == null || attributes == null) {
 143             throw new NullPointerException();
 144         }
 145         this.text = text;
 146 
 147         if (text.length() == 0) {
 148             if (attributes.isEmpty())
 149                 return;
 150             throw new IllegalArgumentException("Can't add attribute to 0-length text");
 151         }
 152 
 153         int attributeCount = attributes.size();
 154         if (attributeCount > 0) {
 155             createRunAttributeDataVectors();
 156             Vector<Attribute> newRunAttributes = new Vector<>(attributeCount);
 157             Vector<Object> newRunAttributeValues = new Vector<>(attributeCount);
 158             runAttributes[0] = newRunAttributes;
 159             runAttributeValues[0] = newRunAttributeValues;
 160 
 161             Iterator<? extends Map.Entry<? extends Attribute, ?>> iterator = attributes.entrySet().iterator();
 162             while (iterator.hasNext()) {
 163                 Map.Entry<? extends Attribute, ?> entry = iterator.next();
 164                 newRunAttributes.addElement(entry.getKey());
 165                 newRunAttributeValues.addElement(entry.getValue());
 166             }
 167         }
 168     }
 169 
 170     /**
 171      * Constructs an AttributedString instance with the given attributed
 172      * text represented by AttributedCharacterIterator.
 173      * @param text The text for this attributed string.
 174      * @exception NullPointerException if <code>text</code> is null.
 175      */
 176     public AttributedString(AttributedCharacterIterator text) {
 177         // If performance is critical, this constructor should be
 178         // implemented here rather than invoking the constructor for a
 179         // subrange. We can avoid some range checking in the loops.
 180         this(text, text.getBeginIndex(), text.getEndIndex(), null);
 181     }
 182 
 183     /**
 184      * Constructs an AttributedString instance with the subrange of
 185      * the given attributed text represented by
 186      * AttributedCharacterIterator. If the given range produces an
 187      * empty text, all attributes will be discarded.  Note that any
 188      * attributes wrapped by an Annotation object are discarded for a
 189      * subrange of the original attribute range.
 190      *
 191      * @param text The text for this attributed string.
 192      * @param beginIndex Index of the first character of the range.
 193      * @param endIndex Index of the character following the last character
 194      * of the range.
 195      * @exception NullPointerException if <code>text</code> is null.
 196      * @exception IllegalArgumentException if the subrange given by
 197      * beginIndex and endIndex is out of the text range.
 198      * @see java.text.Annotation
 199      */
 200     public AttributedString(AttributedCharacterIterator text,
 201                             int beginIndex,
 202                             int endIndex) {
 203         this(text, beginIndex, endIndex, null);
 204     }
 205 
 206     /**
 207      * Constructs an AttributedString instance with the subrange of
 208      * the given attributed text represented by
 209      * AttributedCharacterIterator.  Only attributes that match the
 210      * given attributes will be incorporated into the instance. If the
 211      * given range produces an empty text, all attributes will be
 212      * discarded. Note that any attributes wrapped by an Annotation
 213      * object are discarded for a subrange of the original attribute
 214      * range.
 215      *
 216      * @param text The text for this attributed string.
 217      * @param beginIndex Index of the first character of the range.
 218      * @param endIndex Index of the character following the last character
 219      * of the range.
 220      * @param attributes Specifies attributes to be extracted
 221      * from the text. If null is specified, all available attributes will
 222      * be used.
 223      * @exception NullPointerException if <code>text</code> is null.
 224      * @exception IllegalArgumentException if the subrange given by
 225      * beginIndex and endIndex is out of the text range.
 226      * @see java.text.Annotation
 227      */
 228     public AttributedString(AttributedCharacterIterator text,
 229                             int beginIndex,
 230                             int endIndex,
 231                             Attribute[] attributes) {
 232         if (text == null) {
 233             throw new NullPointerException();
 234         }
 235 
 236         // Validate the given subrange
 237         int textBeginIndex = text.getBeginIndex();
 238         int textEndIndex = text.getEndIndex();
 239         if (beginIndex < textBeginIndex || endIndex > textEndIndex || beginIndex > endIndex)
 240             throw new IllegalArgumentException("Invalid substring range");
 241 
 242         // Copy the given string
 243         StringBuilder textBuilder = new StringBuilder();
 244         text.setIndex(beginIndex);
 245         for (char c = text.current(); text.getIndex() < endIndex; c = text.next())
 246             textBuilder.append(c);
 247         this.text = textBuilder.toString();
 248 
 249         if (beginIndex == endIndex)
 250             return;
 251 
 252         // Select attribute keys to be taken care of
 253         HashSet<Attribute> keys = new HashSet<>();
 254         if (attributes == null) {
 255             keys.addAll(text.getAllAttributeKeys());
 256         } else {
 257             for (int i = 0; i < attributes.length; i++)
 258                 keys.add(attributes[i]);
 259             keys.retainAll(text.getAllAttributeKeys());
 260         }
 261         if (keys.isEmpty())
 262             return;
 263 
 264         // Get and set attribute runs for each attribute name. Need to
 265         // scan from the top of the text so that we can discard any
 266         // Annotation that is no longer applied to a subset text segment.
 267         Iterator<Attribute> itr = keys.iterator();
 268         while (itr.hasNext()) {
 269             Attribute attributeKey = itr.next();
 270             text.setIndex(textBeginIndex);
 271             while (text.getIndex() < endIndex) {
 272                 int start = text.getRunStart(attributeKey);
 273                 int limit = text.getRunLimit(attributeKey);
 274                 Object value = text.getAttribute(attributeKey);
 275 
 276                 if (value != null) {
 277                     if (value instanceof Annotation) {
 278                         if (start >= beginIndex && limit <= endIndex) {
 279                             addAttribute(attributeKey, value, start - beginIndex, limit - beginIndex);
 280                         } else {
 281                             if (limit > endIndex)
 282                                 break;
 283                         }
 284                     } else {
 285                         // if the run is beyond the given (subset) range, we
 286                         // don't need to process further.
 287                         if (start >= endIndex)
 288                             break;
 289                         if (limit > beginIndex) {
 290                             // attribute is applied to any subrange
 291                             if (start < beginIndex)
 292                                 start = beginIndex;
 293                             if (limit > endIndex)
 294                                 limit = endIndex;
 295                             if (start != limit) {
 296                                 addAttribute(attributeKey, value, start - beginIndex, limit - beginIndex);
 297                             }
 298                         }
 299                     }
 300                 }
 301                 text.setIndex(limit);
 302             }
 303         }
 304     }
 305 
 306     /**
 307      * Adds an attribute to the entire string.
 308      * @param attribute the attribute key
 309      * @param value the value of the attribute; may be null
 310      * @exception NullPointerException if <code>attribute</code> is null.
 311      * @exception IllegalArgumentException if the AttributedString has length 0
 312      * (attributes cannot be applied to a 0-length range).
 313      */
 314     public void addAttribute(Attribute attribute, Object value) {
 315 
 316         if (attribute == null) {
 317             throw new NullPointerException();
 318         }
 319 
 320         int len = length();
 321         if (len == 0) {
 322             throw new IllegalArgumentException("Can't add attribute to 0-length text");
 323         }
 324 
 325         addAttributeImpl(attribute, value, 0, len);
 326     }
 327 
 328     /**
 329      * Adds an attribute to a subrange of the string.
 330      * @param attribute the attribute key
 331      * @param value The value of the attribute. May be null.
 332      * @param beginIndex Index of the first character of the range.
 333      * @param endIndex Index of the character following the last character of the range.
 334      * @exception NullPointerException if <code>attribute</code> is null.
 335      * @exception IllegalArgumentException if beginIndex is less than 0, endIndex is
 336      * greater than the length of the string, or beginIndex and endIndex together don't
 337      * define a non-empty subrange of the string.
 338      */
 339     public void addAttribute(Attribute attribute, Object value,
 340             int beginIndex, int endIndex) {
 341 
 342         if (attribute == null) {
 343             throw new NullPointerException();
 344         }
 345 
 346         if (beginIndex < 0 || endIndex > length() || beginIndex >= endIndex) {
 347             throw new IllegalArgumentException("Invalid substring range");
 348         }
 349 
 350         addAttributeImpl(attribute, value, beginIndex, endIndex);
 351     }
 352 
 353     /**
 354      * Adds a set of attributes to a subrange of the string.
 355      * @param attributes The attributes to be added to the string.
 356      * @param beginIndex Index of the first character of the range.
 357      * @param endIndex Index of the character following the last
 358      * character of the range.
 359      * @exception NullPointerException if <code>attributes</code> is null.
 360      * @exception IllegalArgumentException if beginIndex is less than
 361      * 0, endIndex is greater than the length of the string, or
 362      * beginIndex and endIndex together don't define a non-empty
 363      * subrange of the string and the attributes parameter is not an
 364      * empty Map.
 365      */
 366     public void addAttributes(Map<? extends Attribute, ?> attributes,
 367                               int beginIndex, int endIndex)
 368     {
 369         if (attributes == null) {
 370             throw new NullPointerException();
 371         }
 372 
 373         if (beginIndex < 0 || endIndex > length() || beginIndex > endIndex) {
 374             throw new IllegalArgumentException("Invalid substring range");
 375         }
 376         if (beginIndex == endIndex) {
 377             if (attributes.isEmpty())
 378                 return;
 379             throw new IllegalArgumentException("Can't add attribute to 0-length text");
 380         }
 381 
 382         // make sure we have run attribute data vectors
 383         if (runCount == 0) {
 384             createRunAttributeDataVectors();
 385         }
 386 
 387         // break up runs if necessary
 388         int beginRunIndex = ensureRunBreak(beginIndex);
 389         int endRunIndex = ensureRunBreak(endIndex);
 390 
 391         Iterator<? extends Map.Entry<? extends Attribute, ?>> iterator =
 392             attributes.entrySet().iterator();
 393         while (iterator.hasNext()) {
 394             Map.Entry<? extends Attribute, ?> entry = iterator.next();
 395             addAttributeRunData(entry.getKey(), entry.getValue(), beginRunIndex, endRunIndex);
 396         }
 397     }
 398 
 399     private synchronized void addAttributeImpl(Attribute attribute, Object value,
 400             int beginIndex, int endIndex) {
 401 
 402         // make sure we have run attribute data vectors
 403         if (runCount == 0) {
 404             createRunAttributeDataVectors();
 405         }
 406 
 407         // break up runs if necessary
 408         int beginRunIndex = ensureRunBreak(beginIndex);
 409         int endRunIndex = ensureRunBreak(endIndex);
 410 
 411         addAttributeRunData(attribute, value, beginRunIndex, endRunIndex);
 412     }
 413 
 414     private final void createRunAttributeDataVectors() {
 415         // use temporary variables so things remain consistent in case of an exception
 416         int[] newRunStarts = new int[INITIAL_CAPACITY];
 417 
 418         @SuppressWarnings("unchecked")
 419         Vector<Attribute>[] newRunAttributes = (Vector<Attribute>[]) new Vector<?>[INITIAL_CAPACITY];
 420 
 421         @SuppressWarnings("unchecked")
 422         Vector<Object>[] newRunAttributeValues = (Vector<Object>[]) new Vector<?>[INITIAL_CAPACITY];
 423 
 424         runStarts = newRunStarts;
 425         runAttributes = newRunAttributes;
 426         runAttributeValues = newRunAttributeValues;
 427         runCount = 1; // assume initial run starting at index 0
 428     }
 429 
 430     // ensure there's a run break at offset, return the index of the run
 431     private final int ensureRunBreak(int offset) {
 432         return ensureRunBreak(offset, true);
 433     }
 434 
 435     /**
 436      * Ensures there is a run break at offset, returning the index of
 437      * the run. If this results in splitting a run, two things can happen:
 438      * <ul>
 439      * <li>If copyAttrs is true, the attributes from the existing run
 440      *     will be placed in both of the newly created runs.
 441      * <li>If copyAttrs is false, the attributes from the existing run
 442      * will NOT be copied to the run to the right (>= offset) of the break,
 443      * but will exist on the run to the left (< offset).
 444      * </ul>
 445      */
 446     private final int ensureRunBreak(int offset, boolean copyAttrs) {
 447         if (offset == length()) {
 448             return runCount;
 449         }
 450 
 451         // search for the run index where this offset should be
 452         int runIndex = 0;
 453         while (runIndex < runCount && runStarts[runIndex] < offset) {
 454             runIndex++;
 455         }
 456 
 457         // if the offset is at a run start already, we're done
 458         if (runIndex < runCount && runStarts[runIndex] == offset) {
 459             return runIndex;
 460         }
 461 
 462         // we'll have to break up a run
 463         // first, make sure we have enough space in our arrays
 464         int currentCapacity = runStarts.length;
 465         if (runCount == currentCapacity) {
 466             // We need to resize - we grow capacity by 25%.
 467             int newCapacity = currentCapacity + (currentCapacity >> 2);
 468 
 469             // use temporary variables so things remain consistent in case of an exception
 470             int[] newRunStarts =
 471                 Arrays.copyOf(runStarts, newCapacity);
 472             Vector<Attribute>[] newRunAttributes =
 473                 Arrays.copyOf(runAttributes, newCapacity);
 474             Vector<Object>[] newRunAttributeValues =
 475                 Arrays.copyOf(runAttributeValues, newCapacity);
 476 
 477             runStarts = newRunStarts;
 478             runAttributes = newRunAttributes;
 479             runAttributeValues = newRunAttributeValues;
 480         }
 481 
 482         // make copies of the attribute information of the old run that the new one used to be part of
 483         // use temporary variables so things remain consistent in case of an exception
 484         Vector<Attribute> newRunAttributes = null;
 485         Vector<Object> newRunAttributeValues = null;
 486 
 487         if (copyAttrs) {
 488             Vector<Attribute> oldRunAttributes = runAttributes[runIndex - 1];
 489             Vector<Object> oldRunAttributeValues = runAttributeValues[runIndex - 1];
 490             if (oldRunAttributes != null) {
 491                 newRunAttributes = new Vector<>(oldRunAttributes);
 492             }
 493             if (oldRunAttributeValues != null) {
 494                 newRunAttributeValues =  new Vector<>(oldRunAttributeValues);
 495             }
 496         }
 497 
 498         // now actually break up the run
 499         runCount++;
 500         for (int i = runCount - 1; i > runIndex; i--) {
 501             runStarts[i] = runStarts[i - 1];
 502             runAttributes[i] = runAttributes[i - 1];
 503             runAttributeValues[i] = runAttributeValues[i - 1];
 504         }
 505         runStarts[runIndex] = offset;
 506         runAttributes[runIndex] = newRunAttributes;
 507         runAttributeValues[runIndex] = newRunAttributeValues;
 508 
 509         return runIndex;
 510     }
 511 
 512     // add the attribute attribute/value to all runs where beginRunIndex <= runIndex < endRunIndex
 513     private void addAttributeRunData(Attribute attribute, Object value,
 514             int beginRunIndex, int endRunIndex) {
 515 
 516         for (int i = beginRunIndex; i < endRunIndex; i++) {
 517             int keyValueIndex = -1; // index of key and value in our vectors; assume we don't have an entry yet
 518             if (runAttributes[i] == null) {
 519                 Vector<Attribute> newRunAttributes = new Vector<>();
 520                 Vector<Object> newRunAttributeValues = new Vector<>();
 521                 runAttributes[i] = newRunAttributes;
 522                 runAttributeValues[i] = newRunAttributeValues;
 523             } else {
 524                 // check whether we have an entry already
 525                 keyValueIndex = runAttributes[i].indexOf(attribute);
 526             }
 527 
 528             if (keyValueIndex == -1) {
 529                 // create new entry
 530                 int oldSize = runAttributes[i].size();
 531                 runAttributes[i].addElement(attribute);
 532                 try {
 533                     runAttributeValues[i].addElement(value);
 534                 }
 535                 catch (Exception e) {
 536                     runAttributes[i].setSize(oldSize);
 537                     runAttributeValues[i].setSize(oldSize);
 538                 }
 539             } else {
 540                 // update existing entry
 541                 runAttributeValues[i].set(keyValueIndex, value);
 542             }
 543         }
 544     }
 545 
 546     /**
 547      * Creates an AttributedCharacterIterator instance that provides access to the entire contents of
 548      * this string.
 549      *
 550      * @return An iterator providing access to the text and its attributes.
 551      */
 552     public AttributedCharacterIterator getIterator() {
 553         return getIterator(null, 0, length());
 554     }
 555 
 556     /**
 557      * Creates an AttributedCharacterIterator instance that provides access to
 558      * selected contents of this string.
 559      * Information about attributes not listed in attributes that the
 560      * implementor may have need not be made accessible through the iterator.
 561      * If the list is null, all available attribute information should be made
 562      * accessible.
 563      *
 564      * @param attributes a list of attributes that the client is interested in
 565      * @return an iterator providing access to the entire text and its selected attributes
 566      */
 567     public AttributedCharacterIterator getIterator(Attribute[] attributes) {
 568         return getIterator(attributes, 0, length());
 569     }
 570 
 571     /**
 572      * Creates an AttributedCharacterIterator instance that provides access to
 573      * selected contents of this string.
 574      * Information about attributes not listed in attributes that the
 575      * implementor may have need not be made accessible through the iterator.
 576      * If the list is null, all available attribute information should be made
 577      * accessible.
 578      *
 579      * @param attributes a list of attributes that the client is interested in
 580      * @param beginIndex the index of the first character
 581      * @param endIndex the index of the character following the last character
 582      * @return an iterator providing access to the text and its attributes
 583      * @exception IllegalArgumentException if beginIndex is less than 0,
 584      * endIndex is greater than the length of the string, or beginIndex is
 585      * greater than endIndex.
 586      */
 587     public AttributedCharacterIterator getIterator(Attribute[] attributes, int beginIndex, int endIndex) {
 588         return new AttributedStringIterator(attributes, beginIndex, endIndex);
 589     }
 590 
 591     // all (with the exception of length) reading operations are private,
 592     // since AttributedString instances are accessed through iterators.
 593 
 594     // length is package private so that CharacterIteratorFieldDelegate can
 595     // access it without creating an AttributedCharacterIterator.
 596     int length() {
 597         return text.length();
 598     }
 599 
 600     private char charAt(int index) {
 601         return text.charAt(index);
 602     }
 603 
 604     private synchronized Object getAttribute(Attribute attribute, int runIndex) {
 605         Vector<Attribute> currentRunAttributes = runAttributes[runIndex];
 606         Vector<Object> currentRunAttributeValues = runAttributeValues[runIndex];
 607         if (currentRunAttributes == null) {
 608             return null;
 609         }
 610         int attributeIndex = currentRunAttributes.indexOf(attribute);
 611         if (attributeIndex != -1) {
 612             return currentRunAttributeValues.elementAt(attributeIndex);
 613         }
 614         else {
 615             return null;
 616         }
 617     }
 618 
 619     // gets an attribute value, but returns an annotation only if it's range does not extend outside the range beginIndex..endIndex
 620     private Object getAttributeCheckRange(Attribute attribute, int runIndex, int beginIndex, int endIndex) {
 621         Object value = getAttribute(attribute, runIndex);
 622         if (value instanceof Annotation) {
 623             // need to check whether the annotation's range extends outside the iterator's range
 624             if (beginIndex > 0) {
 625                 int currIndex = runIndex;
 626                 int runStart = runStarts[currIndex];
 627                 while (runStart >= beginIndex &&
 628                         valuesMatch(value, getAttribute(attribute, currIndex - 1))) {
 629                     currIndex--;
 630                     runStart = runStarts[currIndex];
 631                 }
 632                 if (runStart < beginIndex) {
 633                     // annotation's range starts before iterator's range
 634                     return null;
 635                 }
 636             }
 637             int textLength = length();
 638             if (endIndex < textLength) {
 639                 int currIndex = runIndex;
 640                 int runLimit = (currIndex < runCount - 1) ? runStarts[currIndex + 1] : textLength;
 641                 while (runLimit <= endIndex &&
 642                         valuesMatch(value, getAttribute(attribute, currIndex + 1))) {
 643                     currIndex++;
 644                     runLimit = (currIndex < runCount - 1) ? runStarts[currIndex + 1] : textLength;
 645                 }
 646                 if (runLimit > endIndex) {
 647                     // annotation's range ends after iterator's range
 648                     return null;
 649                 }
 650             }
 651             // annotation's range is subrange of iterator's range,
 652             // so we can return the value
 653         }
 654         return value;
 655     }
 656 
 657     // returns whether all specified attributes have equal values in the runs with the given indices
 658     private boolean attributeValuesMatch(Set<? extends Attribute> attributes, int runIndex1, int runIndex2) {
 659         Iterator<? extends Attribute> iterator = attributes.iterator();
 660         while (iterator.hasNext()) {
 661             Attribute key = iterator.next();
 662            if (!valuesMatch(getAttribute(key, runIndex1), getAttribute(key, runIndex2))) {
 663                 return false;
 664             }
 665         }
 666         return true;
 667     }
 668 
 669     // returns whether the two objects are either both null or equal
 670     private final static boolean valuesMatch(Object value1, Object value2) {
 671         if (value1 == null) {
 672             return value2 == null;
 673         } else {
 674             return value1.equals(value2);
 675         }
 676     }
 677 
 678     /**
 679      * Appends the contents of the CharacterIterator iterator into the
 680      * StringBuffer buf.
 681      */
 682     private final void appendContents(StringBuffer buf,
 683                                       CharacterIterator iterator) {
 684         int index = iterator.getBeginIndex();
 685         int end = iterator.getEndIndex();
 686 
 687         while (index < end) {
 688             iterator.setIndex(index++);
 689             buf.append(iterator.current());
 690         }
 691     }
 692 
 693     /**
 694      * Sets the attributes for the range from offset to the next run break
 695      * (typically the end of the text) to the ones specified in attrs.
 696      * This is only meant to be called from the constructor!
 697      */
 698     private void setAttributes(Map<Attribute, Object> attrs, int offset) {
 699         if (runCount == 0) {
 700             createRunAttributeDataVectors();
 701         }
 702 
 703         int index = ensureRunBreak(offset, false);
 704         int size;
 705 
 706         if (attrs != null && (size = attrs.size()) > 0) {
 707             Vector<Attribute> runAttrs = new Vector<>(size);
 708             Vector<Object> runValues = new Vector<>(size);
 709             Iterator<Map.Entry<Attribute, Object>> iterator = attrs.entrySet().iterator();
 710 
 711             while (iterator.hasNext()) {
 712                 Map.Entry<Attribute, Object> entry = iterator.next();
 713 
 714                 runAttrs.add(entry.getKey());
 715                 runValues.add(entry.getValue());
 716             }
 717             runAttributes[index] = runAttrs;
 718             runAttributeValues[index] = runValues;
 719         }
 720     }
 721 
 722     /**
 723      * Returns true if the attributes specified in last and attrs differ.
 724      */
 725     private static <K,V> boolean mapsDiffer(Map<K, V> last, Map<K, V> attrs) {
 726         if (last == null) {
 727             return (attrs != null && attrs.size() > 0);
 728         }
 729         return (!last.equals(attrs));
 730     }
 731 
 732 
 733     // the iterator class associated with this string class
 734 
 735     final private class AttributedStringIterator implements AttributedCharacterIterator {
 736 
 737         // note on synchronization:
 738         // we don't synchronize on the iterator, assuming that an iterator is only used in one thread.
 739         // we do synchronize access to the AttributedString however, since it's more likely to be shared between threads.
 740 
 741         // start and end index for our iteration
 742         private int beginIndex;
 743         private int endIndex;
 744 
 745         // attributes that our client is interested in
 746         private Attribute[] relevantAttributes;
 747 
 748         // the current index for our iteration
 749         // invariant: beginIndex <= currentIndex <= endIndex
 750         private int currentIndex;
 751 
 752         // information about the run that includes currentIndex
 753         private int currentRunIndex;
 754         private int currentRunStart;
 755         private int currentRunLimit;
 756 
 757         // constructor
 758         AttributedStringIterator(Attribute[] attributes, int beginIndex, int endIndex) {
 759 
 760             if (beginIndex < 0 || beginIndex > endIndex || endIndex > length()) {
 761                 throw new IllegalArgumentException("Invalid substring range");
 762             }
 763 
 764             this.beginIndex = beginIndex;
 765             this.endIndex = endIndex;
 766             this.currentIndex = beginIndex;
 767             updateRunInfo();
 768             if (attributes != null) {
 769                 relevantAttributes = attributes.clone();
 770             }
 771         }
 772 
 773         // Object methods. See documentation in that class.
 774 
 775         public boolean equals(Object obj) {
 776             if (this == obj) {
 777                 return true;
 778             }
 779             if (!(obj instanceof AttributedStringIterator)) {
 780                 return false;
 781             }
 782 
 783             AttributedStringIterator that = (AttributedStringIterator) obj;
 784 
 785             if (AttributedString.this != that.getString())
 786                 return false;
 787             if (currentIndex != that.currentIndex || beginIndex != that.beginIndex || endIndex != that.endIndex)
 788                 return false;
 789             return true;
 790         }
 791 
 792         public int hashCode() {
 793             return text.hashCode() ^ currentIndex ^ beginIndex ^ endIndex;
 794         }
 795 
 796         public Object clone() {
 797             try {
 798                 AttributedStringIterator other = (AttributedStringIterator) super.clone();
 799                 return other;
 800             }
 801             catch (CloneNotSupportedException e) {
 802                 throw new InternalError(e);
 803             }
 804         }
 805 
 806         // CharacterIterator methods. See documentation in that interface.
 807 
 808         public char first() {
 809             return internalSetIndex(beginIndex);
 810         }
 811 
 812         public char last() {
 813             if (endIndex == beginIndex) {
 814                 return internalSetIndex(endIndex);
 815             } else {
 816                 return internalSetIndex(endIndex - 1);
 817             }
 818         }
 819 
 820         public char current() {
 821             if (currentIndex == endIndex) {
 822                 return DONE;
 823             } else {
 824                 return charAt(currentIndex);
 825             }
 826         }
 827 
 828         public char next() {
 829             if (currentIndex < endIndex) {
 830                 return internalSetIndex(currentIndex + 1);
 831             }
 832             else {
 833                 return DONE;
 834             }
 835         }
 836 
 837         public char previous() {
 838             if (currentIndex > beginIndex) {
 839                 return internalSetIndex(currentIndex - 1);
 840             }
 841             else {
 842                 return DONE;
 843             }
 844         }
 845 
 846         public char setIndex(int position) {
 847             if (position < beginIndex || position > endIndex)
 848                 throw new IllegalArgumentException("Invalid index");
 849             return internalSetIndex(position);
 850         }
 851 
 852         public int getBeginIndex() {
 853             return beginIndex;
 854         }
 855 
 856         public int getEndIndex() {
 857             return endIndex;
 858         }
 859 
 860         public int getIndex() {
 861             return currentIndex;
 862         }
 863 
 864         // AttributedCharacterIterator methods. See documentation in that interface.
 865 
 866         public int getRunStart() {
 867             return currentRunStart;
 868         }
 869 
 870         public int getRunStart(Attribute attribute) {
 871             if (currentRunStart == beginIndex || currentRunIndex == -1) {
 872                 return currentRunStart;
 873             } else {
 874                 Object value = getAttribute(attribute);
 875                 int runStart = currentRunStart;
 876                 int runIndex = currentRunIndex;
 877                 while (runStart > beginIndex &&
 878                         valuesMatch(value, AttributedString.this.getAttribute(attribute, runIndex - 1))) {
 879                     runIndex--;
 880                     runStart = runStarts[runIndex];
 881                 }
 882                 if (runStart < beginIndex) {
 883                     runStart = beginIndex;
 884                 }
 885                 return runStart;
 886             }
 887         }
 888 
 889         public int getRunStart(Set<? extends Attribute> attributes) {
 890             if (currentRunStart == beginIndex || currentRunIndex == -1) {
 891                 return currentRunStart;
 892             } else {
 893                 int runStart = currentRunStart;
 894                 int runIndex = currentRunIndex;
 895                 while (runStart > beginIndex &&
 896                         AttributedString.this.attributeValuesMatch(attributes, currentRunIndex, runIndex - 1)) {
 897                     runIndex--;
 898                     runStart = runStarts[runIndex];
 899                 }
 900                 if (runStart < beginIndex) {
 901                     runStart = beginIndex;
 902                 }
 903                 return runStart;
 904             }
 905         }
 906 
 907         public int getRunLimit() {
 908             return currentRunLimit;
 909         }
 910 
 911         public int getRunLimit(Attribute attribute) {
 912             if (currentRunLimit == endIndex || currentRunIndex == -1) {
 913                 return currentRunLimit;
 914             } else {
 915                 Object value = getAttribute(attribute);
 916                 int runLimit = currentRunLimit;
 917                 int runIndex = currentRunIndex;
 918                 while (runLimit < endIndex &&
 919                         valuesMatch(value, AttributedString.this.getAttribute(attribute, runIndex + 1))) {
 920                     runIndex++;
 921                     runLimit = runIndex < runCount - 1 ? runStarts[runIndex + 1] : endIndex;
 922                 }
 923                 if (runLimit > endIndex) {
 924                     runLimit = endIndex;
 925                 }
 926                 return runLimit;
 927             }
 928         }
 929 
 930         public int getRunLimit(Set<? extends Attribute> attributes) {
 931             if (currentRunLimit == endIndex || currentRunIndex == -1) {
 932                 return currentRunLimit;
 933             } else {
 934                 int runLimit = currentRunLimit;
 935                 int runIndex = currentRunIndex;
 936                 while (runLimit < endIndex &&
 937                         AttributedString.this.attributeValuesMatch(attributes, currentRunIndex, runIndex + 1)) {
 938                     runIndex++;
 939                     runLimit = runIndex < runCount - 1 ? runStarts[runIndex + 1] : endIndex;
 940                 }
 941                 if (runLimit > endIndex) {
 942                     runLimit = endIndex;
 943                 }
 944                 return runLimit;
 945             }
 946         }
 947 
 948         public Map<Attribute,Object> getAttributes() {
 949             if (runAttributes == null || currentRunIndex == -1 || runAttributes[currentRunIndex] == null) {
 950                 // ??? would be nice to return null, but current spec doesn't allow it
 951                 // returning Hashtable saves AttributeMap from dealing with emptiness
 952                 return new Hashtable<>();
 953             }
 954             return new AttributeMap(currentRunIndex, beginIndex, endIndex);
 955         }
 956 
 957         public Set<Attribute> getAllAttributeKeys() {
 958             // ??? This should screen out attribute keys that aren't relevant to the client
 959             if (runAttributes == null) {
 960                 // ??? would be nice to return null, but current spec doesn't allow it
 961                 // returning HashSet saves us from dealing with emptiness
 962                 return new HashSet<>();
 963             }
 964             synchronized (AttributedString.this) {
 965                 // ??? should try to create this only once, then update if necessary,
 966                 // and give callers read-only view
 967                 Set<Attribute> keys = new HashSet<>();
 968                 int i = 0;
 969                 while (i < runCount) {
 970                     if (runStarts[i] < endIndex && (i == runCount - 1 || runStarts[i + 1] > beginIndex)) {
 971                         Vector<Attribute> currentRunAttributes = runAttributes[i];
 972                         if (currentRunAttributes != null) {
 973                             int j = currentRunAttributes.size();
 974                             while (j-- > 0) {
 975                                 keys.add(currentRunAttributes.get(j));
 976                             }
 977                         }
 978                     }
 979                     i++;
 980                 }
 981                 return keys;
 982             }
 983         }
 984 
 985         public Object getAttribute(Attribute attribute) {
 986             int runIndex = currentRunIndex;
 987             if (runIndex < 0) {
 988                 return null;
 989             }
 990             return AttributedString.this.getAttributeCheckRange(attribute, runIndex, beginIndex, endIndex);
 991         }
 992 
 993         // internally used methods
 994 
 995         private AttributedString getString() {
 996             return AttributedString.this;
 997         }
 998 
 999         // set the current index, update information about the current run if necessary,
1000         // return the character at the current index
1001         private char internalSetIndex(int position) {
1002             currentIndex = position;
1003             if (position < currentRunStart || position >= currentRunLimit) {
1004                 updateRunInfo();
1005             }
1006             if (currentIndex == endIndex) {
1007                 return DONE;
1008             } else {
1009                 return charAt(position);
1010             }
1011         }
1012 
1013         // update the information about the current run
1014         private void updateRunInfo() {
1015             if (currentIndex == endIndex) {
1016                 currentRunStart = currentRunLimit = endIndex;
1017                 currentRunIndex = -1;
1018             } else {
1019                 synchronized (AttributedString.this) {
1020                     int runIndex = -1;
1021                     while (runIndex < runCount - 1 && runStarts[runIndex + 1] <= currentIndex)
1022                         runIndex++;
1023                     currentRunIndex = runIndex;
1024                     if (runIndex >= 0) {
1025                         currentRunStart = runStarts[runIndex];
1026                         if (currentRunStart < beginIndex)
1027                             currentRunStart = beginIndex;
1028                     }
1029                     else {
1030                         currentRunStart = beginIndex;
1031                     }
1032                     if (runIndex < runCount - 1) {
1033                         currentRunLimit = runStarts[runIndex + 1];
1034                         if (currentRunLimit > endIndex)
1035                             currentRunLimit = endIndex;
1036                     }
1037                     else {
1038                         currentRunLimit = endIndex;
1039                     }
1040                 }
1041             }
1042         }
1043 
1044     }
1045 
1046     // the map class associated with this string class, giving access to the attributes of one run
1047 
1048     final private class AttributeMap extends AbstractMap<Attribute,Object> {
1049 
1050         int runIndex;
1051         int beginIndex;
1052         int endIndex;
1053 
1054         AttributeMap(int runIndex, int beginIndex, int endIndex) {
1055             this.runIndex = runIndex;
1056             this.beginIndex = beginIndex;
1057             this.endIndex = endIndex;
1058         }
1059 
1060         public Set<Map.Entry<Attribute, Object>> entrySet() {
1061             HashSet<Map.Entry<Attribute, Object>> set = new HashSet<>();
1062             synchronized (AttributedString.this) {
1063                 int size = runAttributes[runIndex].size();
1064                 for (int i = 0; i < size; i++) {
1065                     Attribute key = runAttributes[runIndex].get(i);
1066                     Object value = runAttributeValues[runIndex].get(i);
1067                     if (value instanceof Annotation) {
1068                         value = AttributedString.this.getAttributeCheckRange(key,
1069                                                              runIndex, beginIndex, endIndex);
1070                         if (value == null) {
1071                             continue;
1072                         }
1073                     }
1074 
1075                     Map.Entry<Attribute, Object> entry = new AttributeEntry(key, value);
1076                     set.add(entry);
1077                 }
1078             }
1079             return set;
1080         }
1081 
1082         public Object get(Object key) {
1083             return AttributedString.this.getAttributeCheckRange((Attribute) key, runIndex, beginIndex, endIndex);
1084         }
1085     }
1086 }
1087 
1088 class AttributeEntry implements Map.Entry<Attribute,Object> {
1089 
1090     private Attribute key;
1091     private Object value;
1092 
1093     AttributeEntry(Attribute key, Object value) {
1094         this.key = key;
1095         this.value = value;
1096     }
1097 
1098     public boolean equals(Object o) {
1099         if (!(o instanceof AttributeEntry)) {
1100             return false;
1101         }
1102         AttributeEntry other = (AttributeEntry) o;
1103         return other.key.equals(key) &&
1104             (value == null ? other.value == null : other.value.equals(value));
1105     }
1106 
1107     public Attribute getKey() {
1108         return key;
1109     }
1110 
1111     public Object getValue() {
1112         return value;
1113     }
1114 
1115     public Object setValue(Object newValue) {
1116         throw new UnsupportedOperationException();
1117     }
1118 
1119     public int hashCode() {
1120         return key.hashCode() ^ (value==null ? 0 : value.hashCode());
1121     }
1122 
1123     public String toString() {
1124         return key.toString()+"="+value.toString();
1125     }
1126 }