001/* AbstractDocument.java --
002   Copyright (C) 2002, 2004, 2005, 2006  Free Software Foundation, Inc.
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038
039package javax.swing.text;
040
041import gnu.java.lang.CPStringBuilder;
042
043import java.awt.font.TextAttribute;
044import java.io.PrintStream;
045import java.io.Serializable;
046import java.text.Bidi;
047import java.util.ArrayList;
048import java.util.Dictionary;
049import java.util.Enumeration;
050import java.util.EventListener;
051import java.util.HashMap;
052import java.util.Hashtable;
053import java.util.Vector;
054
055import javax.swing.event.DocumentEvent;
056import javax.swing.event.DocumentListener;
057import javax.swing.event.EventListenerList;
058import javax.swing.event.UndoableEditEvent;
059import javax.swing.event.UndoableEditListener;
060import javax.swing.text.DocumentFilter;
061import javax.swing.tree.TreeNode;
062import javax.swing.undo.AbstractUndoableEdit;
063import javax.swing.undo.CompoundEdit;
064import javax.swing.undo.UndoableEdit;
065
066/**
067 * An abstract base implementation for the {@link Document} interface.
068 * This class provides some common functionality for all <code>Element</code>s,
069 * most notably it implements a locking mechanism to make document modification
070 * thread-safe.
071 *
072 * @author original author unknown
073 * @author Roman Kennke (roman@kennke.org)
074 */
075public abstract class AbstractDocument implements Document, Serializable
076{
077  /** The serialization UID (compatible with JDK1.5). */
078  private static final long serialVersionUID = 6842927725919637215L;
079
080  /**
081   * Standard error message to indicate a bad location.
082   */
083  protected static final String BAD_LOCATION = "document location failure";
084
085  /**
086   * Standard name for unidirectional <code>Element</code>s.
087   */
088  public static final String BidiElementName = "bidi level";
089
090  /**
091   * Standard name for content <code>Element</code>s. These are usually
092   * {@link LeafElement}s.
093   */
094  public static final String ContentElementName = "content";
095
096  /**
097   * Standard name for paragraph <code>Element</code>s. These are usually
098   * {@link BranchElement}s.
099   */
100  public static final String ParagraphElementName = "paragraph";
101
102  /**
103   * Standard name for section <code>Element</code>s. These are usually
104   * {@link DefaultStyledDocument.SectionElement}s.
105   */
106  public static final String SectionElementName = "section";
107
108  /**
109   * Attribute key for storing the element name.
110   */
111  public static final String ElementNameAttribute = "$ename";
112
113  /**
114   * Standard name for the bidi root element.
115   */
116  private static final String BidiRootName = "bidi root";
117
118  /**
119   * Key for storing the asynchronous load priority.
120   */
121  private static final String AsyncLoadPriority = "load priority";
122
123  /**
124   * Key for storing the I18N state.
125   */
126  private static final String I18N = "i18n";
127
128  /**
129   * The actual content model of this <code>Document</code>.
130   */
131  Content content;
132
133  /**
134   * The AttributeContext for this <code>Document</code>.
135   */
136  AttributeContext context;
137
138  /**
139   * The currently installed <code>DocumentFilter</code>.
140   */
141  DocumentFilter documentFilter;
142
143  /**
144   * The documents properties.
145   */
146  Dictionary properties;
147
148  /**
149   * Manages event listeners for this <code>Document</code>.
150   */
151  protected EventListenerList listenerList = new EventListenerList();
152
153  /**
154   * Stores the current writer thread.  Used for locking.
155   */
156  private Thread currentWriter = null;
157
158  /**
159   * The number of readers.  Used for locking.
160   */
161  private int numReaders = 0;
162
163  /**
164   * The number of current writers. If this is > 1 then the same thread entered
165   * the write lock more than once.
166   */
167  private int numWriters = 0;
168
169  /** An instance of a DocumentFilter.FilterBypass which allows calling
170   * the insert, remove and replace method without checking for an installed
171   * document filter.
172   */
173  private DocumentFilter.FilterBypass bypass;
174
175  /**
176   * The bidi root element.
177   */
178  private BidiRootElement bidiRoot;
179
180  /**
181   * True when we are currently notifying any listeners. This is used
182   * to detect illegal situations in writeLock().
183   */
184  private transient boolean notifyListeners;
185
186  /**
187   * Creates a new <code>AbstractDocument</code> with the specified
188   * {@link Content} model.
189   *
190   * @param doc the <code>Content</code> model to be used in this
191   *        <code>Document<code>
192   *
193   * @see GapContent
194   * @see StringContent
195   */
196  protected AbstractDocument(Content doc)
197  {
198    this(doc, StyleContext.getDefaultStyleContext());
199  }
200
201  /**
202   * Creates a new <code>AbstractDocument</code> with the specified
203   * {@link Content} model and {@link AttributeContext}.
204   *
205   * @param doc the <code>Content</code> model to be used in this
206   *        <code>Document<code>
207   * @param ctx the <code>AttributeContext</code> to use
208   *
209   * @see GapContent
210   * @see StringContent
211   */
212  protected AbstractDocument(Content doc, AttributeContext ctx)
213  {
214    content = doc;
215    context = ctx;
216
217    // FIXME: Fully implement bidi.
218    bidiRoot = new BidiRootElement();
219
220    // FIXME: This is determined using a Mauve test. Make the document
221    // actually use this.
222    putProperty(I18N, Boolean.FALSE);
223
224    // Add one child to the bidi root.
225    writeLock();
226    try
227      {
228        Element[] children = new Element[1];
229        children[0] = new BidiElement(bidiRoot, 0, 1, 0);
230        bidiRoot.replace(0, 0, children);
231      }
232    finally
233      {
234        writeUnlock();
235      }
236  }
237
238  /** Returns the DocumentFilter.FilterBypass instance for this
239   * document and create it if it does not exist yet.
240   *
241   * @return This document's DocumentFilter.FilterBypass instance.
242   */
243  private DocumentFilter.FilterBypass getBypass()
244  {
245    if (bypass == null)
246      bypass = new Bypass();
247
248    return bypass;
249  }
250
251  /**
252   * Returns the paragraph {@link Element} that holds the specified position.
253   *
254   * @param pos the position for which to get the paragraph element
255   *
256   * @return the paragraph {@link Element} that holds the specified position
257   */
258  public abstract Element getParagraphElement(int pos);
259
260  /**
261   * Returns the default root {@link Element} of this <code>Document</code>.
262   * Usual <code>Document</code>s only have one root element and return this.
263   * However, there may be <code>Document</code> implementations that
264   * support multiple root elements, they have to return a default root element
265   * here.
266   *
267   * @return the default root {@link Element} of this <code>Document</code>
268   */
269  public abstract Element getDefaultRootElement();
270
271  /**
272   * Creates and returns a branch element with the specified
273   * <code>parent</code> and <code>attributes</code>. Note that the new
274   * <code>Element</code> is linked to the parent <code>Element</code>
275   * through {@link Element#getParentElement}, but it is not yet added
276   * to the parent <code>Element</code> as child.
277   *
278   * @param parent the parent <code>Element</code> for the new branch element
279   * @param attributes the text attributes to be installed in the new element
280   *
281   * @return the new branch <code>Element</code>
282   *
283   * @see BranchElement
284   */
285  protected Element createBranchElement(Element parent,
286                                        AttributeSet attributes)
287  {
288    return new BranchElement(parent, attributes);
289  }
290
291  /**
292   * Creates and returns a leaf element with the specified
293   * <code>parent</code> and <code>attributes</code>. Note that the new
294   * <code>Element</code> is linked to the parent <code>Element</code>
295   * through {@link Element#getParentElement}, but it is not yet added
296   * to the parent <code>Element</code> as child.
297   *
298   * @param parent the parent <code>Element</code> for the new branch element
299   * @param attributes the text attributes to be installed in the new element
300   *
301   * @return the new branch <code>Element</code>
302   *
303   * @see LeafElement
304   */
305  protected Element createLeafElement(Element parent, AttributeSet attributes,
306                                      int start, int end)
307  {
308    return new LeafElement(parent, attributes, start, end);
309  }
310
311  /**
312   * Creates a {@link Position} that keeps track of the location at the
313   * specified <code>offset</code>.
314   *
315   * @param offset the location in the document to keep track by the new
316   *        <code>Position</code>
317   *
318   * @return the newly created <code>Position</code>
319   *
320   * @throws BadLocationException if <code>offset</code> is not a valid
321   *         location in the documents content model
322   */
323  public synchronized Position createPosition(final int offset)
324    throws BadLocationException
325  {
326    return content.createPosition(offset);
327  }
328
329  /**
330   * Notifies all registered listeners when the document model changes.
331   *
332   * @param event the <code>DocumentEvent</code> to be fired
333   */
334  protected void fireChangedUpdate(DocumentEvent event)
335  {
336    notifyListeners = true;
337    try
338      {
339        DocumentListener[] listeners = getDocumentListeners();
340        for (int index = 0; index < listeners.length; ++index)
341          listeners[index].changedUpdate(event);
342      }
343    finally
344      {
345        notifyListeners = false;
346      }
347  }
348
349  /**
350   * Notifies all registered listeners when content is inserted in the document
351   * model.
352   *
353   * @param event the <code>DocumentEvent</code> to be fired
354   */
355  protected void fireInsertUpdate(DocumentEvent event)
356  {
357    notifyListeners = true;
358    try
359      {
360        DocumentListener[] listeners = getDocumentListeners();
361        for (int index = 0; index < listeners.length; ++index)
362          listeners[index].insertUpdate(event);
363      }
364    finally
365      {
366        notifyListeners = false;
367      }
368  }
369
370  /**
371   * Notifies all registered listeners when content is removed from the
372   * document model.
373   *
374   * @param event the <code>DocumentEvent</code> to be fired
375   */
376  protected void fireRemoveUpdate(DocumentEvent event)
377  {
378    notifyListeners = true;
379    try
380      {
381        DocumentListener[] listeners = getDocumentListeners();
382        for (int index = 0; index < listeners.length; ++index)
383          listeners[index].removeUpdate(event);
384      }
385    finally
386      {
387        notifyListeners = false;
388      }
389  }
390
391  /**
392   * Notifies all registered listeners when an <code>UndoableEdit</code> has
393   * been performed on this <code>Document</code>.
394   *
395   * @param event the <code>UndoableEditEvent</code> to be fired
396   */
397  protected void fireUndoableEditUpdate(UndoableEditEvent event)
398  {
399    UndoableEditListener[] listeners = getUndoableEditListeners();
400
401    for (int index = 0; index < listeners.length; ++index)
402      listeners[index].undoableEditHappened(event);
403  }
404
405  /**
406   * Returns the asynchronous loading priority. Returns <code>-1</code> if this
407   * document should not be loaded asynchronously.
408   *
409   * @return the asynchronous loading priority
410   */
411  public int getAsynchronousLoadPriority()
412  {
413    Object val = getProperty(AsyncLoadPriority);
414    int prio = -1;
415    if (val != null)
416      prio = ((Integer) val).intValue();
417    return prio;
418  }
419
420  /**
421   * Returns the {@link AttributeContext} used in this <code>Document</code>.
422   *
423   * @return the {@link AttributeContext} used in this <code>Document</code>
424   */
425  protected final AttributeContext getAttributeContext()
426  {
427    return context;
428  }
429
430  /**
431   * Returns the root element for bidirectional content.
432   *
433   * @return the root element for bidirectional content
434   */
435  public Element getBidiRootElement()
436  {
437    return bidiRoot;
438  }
439
440  /**
441   * Returns the {@link Content} model for this <code>Document</code>
442   *
443   * @return the {@link Content} model for this <code>Document</code>
444   *
445   * @see GapContent
446   * @see StringContent
447   */
448  protected final Content getContent()
449  {
450    return content;
451  }
452
453  /**
454   * Returns the thread that currently modifies this <code>Document</code>
455   * if there is one, otherwise <code>null</code>. This can be used to
456   * distinguish between a method call that is part of an ongoing modification
457   * or if it is a separate modification for which a new lock must be aquired.
458   *
459   * @return the thread that currently modifies this <code>Document</code>
460   *         if there is one, otherwise <code>null</code>
461   */
462  protected final synchronized Thread getCurrentWriter()
463  {
464    return currentWriter;
465  }
466
467  /**
468   * Returns the properties of this <code>Document</code>.
469   *
470   * @return the properties of this <code>Document</code>
471   */
472  public Dictionary<Object, Object> getDocumentProperties()
473  {
474    // FIXME: make me thread-safe
475    if (properties == null)
476      properties = new Hashtable();
477
478    return properties;
479  }
480
481  /**
482   * Returns a {@link Position} which will always mark the end of the
483   * <code>Document</code>.
484   *
485   * @return a {@link Position} which will always mark the end of the
486   *         <code>Document</code>
487   */
488  public final Position getEndPosition()
489  {
490    Position p;
491    try
492      {
493        p = createPosition(content.length());
494      }
495    catch (BadLocationException ex)
496      {
497        // Shouldn't really happen.
498        p = null;
499      }
500    return p;
501  }
502
503  /**
504   * Returns the length of this <code>Document</code>'s content.
505   *
506   * @return the length of this <code>Document</code>'s content
507   */
508  public int getLength()
509  {
510    // We return Content.getLength() -1 here because there is always an
511    // implicit \n at the end of the Content which does count in Content
512    // but not in Document.
513    return content.length() - 1;
514  }
515
516  /**
517   * Returns all registered listeners of a given listener type.
518   *
519   * @param listenerType the type of the listeners to be queried
520   *
521   * @return all registered listeners of the specified type
522   */
523  public <T extends EventListener> T[] getListeners(Class<T> listenerType)
524  {
525    return listenerList.getListeners(listenerType);
526  }
527
528  /**
529   * Returns a property from this <code>Document</code>'s property list.
530   *
531   * @param key the key of the property to be fetched
532   *
533   * @return the property for <code>key</code> or <code>null</code> if there
534   *         is no such property stored
535   */
536  public final Object getProperty(Object key)
537  {
538    // FIXME: make me thread-safe
539    Object value = null;
540    if (properties != null)
541      value = properties.get(key);
542
543    return value;
544  }
545
546  /**
547   * Returns all root elements of this <code>Document</code>. By default
548   * this just returns the single root element returned by
549   * {@link #getDefaultRootElement()}. <code>Document</code> implementations
550   * that support multiple roots must override this method and return all roots
551   * here.
552   *
553   * @return all root elements of this <code>Document</code>
554   */
555  public Element[] getRootElements()
556  {
557    Element[] elements = new Element[2];
558    elements[0] = getDefaultRootElement();
559    elements[1] = getBidiRootElement();
560    return elements;
561  }
562
563  /**
564   * Returns a {@link Position} which will always mark the beginning of the
565   * <code>Document</code>.
566   *
567   * @return a {@link Position} which will always mark the beginning of the
568   *         <code>Document</code>
569   */
570  public final Position getStartPosition()
571  {
572    Position p;
573    try
574      {
575        p = createPosition(0);
576      }
577    catch (BadLocationException ex)
578      {
579        // Shouldn't really happen.
580        p = null;
581      }
582    return p;
583  }
584
585  /**
586   * Returns a piece of this <code>Document</code>'s content.
587   *
588   * @param offset the start offset of the content
589   * @param length the length of the content
590   *
591   * @return the piece of content specified by <code>offset</code> and
592   *         <code>length</code>
593   *
594   * @throws BadLocationException if <code>offset</code> or <code>offset +
595   *         length</code> are invalid locations with this
596   *         <code>Document</code>
597   */
598  public String getText(int offset, int length) throws BadLocationException
599  {
600    return content.getString(offset, length);
601  }
602
603  /**
604   * Fetches a piece of this <code>Document</code>'s content and stores
605   * it in the given {@link Segment}.
606   *
607   * @param offset the start offset of the content
608   * @param length the length of the content
609   * @param segment the <code>Segment</code> to store the content in
610   *
611   * @throws BadLocationException if <code>offset</code> or <code>offset +
612   *         length</code> are invalid locations with this
613   *         <code>Document</code>
614   */
615  public void getText(int offset, int length, Segment segment)
616    throws BadLocationException
617  {
618    content.getChars(offset, length, segment);
619  }
620
621  /**
622   * Inserts a String into this <code>Document</code> at the specified
623   * position and assigning the specified attributes to it.
624   *
625   * <p>If a {@link DocumentFilter} is installed in this document, the
626   * corresponding method of the filter object is called.</p>
627   *
628   * <p>The method has no effect when <code>text</code> is <code>null</code>
629   * or has a length of zero.</p>
630   *
631   *
632   * @param offset the location at which the string should be inserted
633   * @param text the content to be inserted
634   * @param attributes the text attributes to be assigned to that string
635   *
636   * @throws BadLocationException if <code>offset</code> is not a valid
637   *         location in this <code>Document</code>
638   */
639  public void insertString(int offset, String text, AttributeSet attributes)
640    throws BadLocationException
641  {
642    // Bail out if we have a bogus insertion (Behavior observed in RI).
643    if (text == null || text.length() == 0)
644      return;
645
646    writeLock();
647    try
648      {
649        if (documentFilter == null)
650          insertStringImpl(offset, text, attributes);
651        else
652          documentFilter.insertString(getBypass(), offset, text, attributes);
653      }
654    finally
655      {
656        writeUnlock();
657      }
658  }
659
660  void insertStringImpl(int offset, String text, AttributeSet attributes)
661    throws BadLocationException
662  {
663    // Just return when no text to insert was given.
664    if (text == null || text.length() == 0)
665      return;
666    DefaultDocumentEvent event =
667      new DefaultDocumentEvent(offset, text.length(),
668                               DocumentEvent.EventType.INSERT);
669
670    UndoableEdit undo = content.insertString(offset, text);
671    if (undo != null)
672      event.addEdit(undo);
673
674    // Check if we need bidi layout.
675    if (getProperty(I18N).equals(Boolean.FALSE))
676      {
677        Object dir = getProperty(TextAttribute.RUN_DIRECTION);
678        if (TextAttribute.RUN_DIRECTION_RTL.equals(dir))
679          putProperty(I18N, Boolean.TRUE);
680        else
681          {
682            char[] chars = text.toCharArray();
683            if (Bidi.requiresBidi(chars, 0, chars.length))
684              putProperty(I18N, Boolean.TRUE);
685          }
686      }
687
688    insertUpdate(event, attributes);
689
690    fireInsertUpdate(event);
691
692    if (undo != null)
693      fireUndoableEditUpdate(new UndoableEditEvent(this, undo));
694  }
695
696  /**
697   * Called to indicate that text has been inserted into this
698   * <code>Document</code>. The default implementation does nothing.
699   * This method is executed within a write lock.
700   *
701   * @param chng the <code>DefaultDocumentEvent</code> describing the change
702   * @param attr the attributes of the changed content
703   */
704  protected void insertUpdate(DefaultDocumentEvent chng, AttributeSet attr)
705  {
706    if (Boolean.TRUE.equals(getProperty(I18N)))
707      updateBidi(chng);
708  }
709
710  /**
711   * Called after some content has been removed from this
712   * <code>Document</code>. The default implementation does nothing.
713   * This method is executed within a write lock.
714   *
715   * @param chng the <code>DefaultDocumentEvent</code> describing the change
716   */
717  protected void postRemoveUpdate(DefaultDocumentEvent chng)
718  {
719    if (Boolean.TRUE.equals(getProperty(I18N)))
720      updateBidi(chng);
721  }
722
723  /**
724   * Stores a property in this <code>Document</code>'s property list.
725   *
726   * @param key the key of the property to be stored
727   * @param value the value of the property to be stored
728   */
729  public final void putProperty(Object key, Object value)
730  {
731    // FIXME: make me thread-safe
732    if (properties == null)
733      properties = new Hashtable();
734
735    if (value == null)
736      properties.remove(key);
737    else
738      properties.put(key, value);
739
740    // Update bidi structure if the RUN_DIRECTION is set.
741    if (TextAttribute.RUN_DIRECTION.equals(key))
742      {
743        if (TextAttribute.RUN_DIRECTION_RTL.equals(value)
744            && Boolean.FALSE.equals(getProperty(I18N)))
745          putProperty(I18N, Boolean.TRUE);
746
747        if (Boolean.TRUE.equals(getProperty(I18N)))
748          {
749            writeLock();
750            try
751              {
752                DefaultDocumentEvent ev =
753                  new DefaultDocumentEvent(0, getLength(),
754                                           DocumentEvent.EventType.INSERT);
755                updateBidi(ev);
756              }
757            finally
758              {
759                writeUnlock();
760              }
761          }
762      }
763  }
764
765  /**
766   * Updates the bidi element structure.
767   *
768   * @param ev the document event for the change
769   */
770  private void updateBidi(DefaultDocumentEvent ev)
771  {
772    // Determine start and end offset of the paragraphs to be scanned.
773    int start = 0;
774    int end = 0;
775    DocumentEvent.EventType type = ev.getType();
776    if (type == DocumentEvent.EventType.INSERT
777        || type == DocumentEvent.EventType.CHANGE)
778      {
779        int offs = ev.getOffset();
780        int endOffs = offs + ev.getLength();
781        start = getParagraphElement(offs).getStartOffset();
782        end = getParagraphElement(endOffs).getEndOffset();
783      }
784    else if (type == DocumentEvent.EventType.REMOVE)
785      {
786        Element par = getParagraphElement(ev.getOffset());
787        start = par.getStartOffset();
788        end = par.getEndOffset();
789      }
790    else
791      assert false : "Unknown event type";
792
793    // Determine the bidi levels for the affected range.
794    Bidi[] bidis = getBidis(start, end);
795
796    int removeFrom = 0;
797    int removeTo = 0;
798
799    int offs = 0;
800    int lastRunStart = 0;
801    int lastRunEnd = 0;
802    int lastRunLevel = 0;
803    ArrayList newEls = new ArrayList();
804    for (int i = 0; i < bidis.length; i++)
805      {
806        Bidi bidi = bidis[i];
807        int numRuns = bidi.getRunCount();
808        for (int r = 0; r < numRuns; r++)
809          {
810            if (r == 0 && i == 0)
811              {
812                if (start > 0)
813                  {
814                    // Try to merge with the previous element if it has the
815                    // same bidi level as the first run.
816                    int prevElIndex = bidiRoot.getElementIndex(start - 1);
817                    removeFrom = prevElIndex;
818                    Element prevEl = bidiRoot.getElement(prevElIndex);
819                    AttributeSet atts = prevEl.getAttributes();
820                    int prevElLevel = StyleConstants.getBidiLevel(atts);
821                    if (prevElLevel == bidi.getRunLevel(r))
822                      {
823                        // Merge previous element with current run.
824                        lastRunStart = prevEl.getStartOffset() - start;
825                        lastRunEnd = bidi.getRunLimit(r);
826                        lastRunLevel  = bidi.getRunLevel(r);
827                      }
828                    else if (prevEl.getEndOffset() > start)
829                      {
830                        // Split previous element and replace by 2 new elements.
831                        lastRunStart = 0;
832                        lastRunEnd = bidi.getRunLimit(r);
833                        lastRunLevel = bidi.getRunLevel(r);
834                        newEls.add(new BidiElement(bidiRoot,
835                                                   prevEl.getStartOffset(),
836                                                   start, prevElLevel));
837                      }
838                    else
839                      {
840                        // Simply start new run at start location.
841                        lastRunStart = 0;
842                        lastRunEnd = bidi.getRunLimit(r);
843                        lastRunLevel = bidi.getRunLevel(r);
844                        removeFrom++;
845                      }
846                  }
847                else
848                  {
849                    // Simply start new run at start location.
850                    lastRunStart = 0;
851                    lastRunEnd = bidi.getRunLimit(r);
852                    lastRunLevel = bidi.getRunLevel(r);
853                    removeFrom = 0;
854                  }
855              }
856            if (i == bidis.length - 1 && r == numRuns - 1)
857              {
858                if (end <= getLength())
859                  {
860                    // Try to merge last element with next element.
861                    int nextIndex = bidiRoot.getElementIndex(end);
862                    Element nextEl = bidiRoot.getElement(nextIndex);
863                    AttributeSet atts = nextEl.getAttributes();
864                    int nextLevel = StyleConstants.getBidiLevel(atts);
865                    int level = bidi.getRunLevel(r);
866                    if (lastRunLevel == level && level == nextLevel)
867                      {
868                        // Merge runs together.
869                        if (lastRunStart + start == nextEl.getStartOffset())
870                          removeTo = nextIndex - 1;
871                        else
872                          {
873                            newEls.add(new BidiElement(bidiRoot, start + lastRunStart,
874                                                       nextEl.getEndOffset(), level));
875                            removeTo = nextIndex;
876                          }
877                      }
878                    else if (lastRunLevel == level)
879                      {
880                        // Merge current and last run.
881                        int endOffs = offs + bidi.getRunLimit(r);
882                        newEls.add(new BidiElement(bidiRoot, start + lastRunStart,
883                                                   start + endOffs, level));
884                        if (start + endOffs == nextEl.getStartOffset())
885                          removeTo = nextIndex - 1;
886                        else
887                          {
888                            newEls.add(new BidiElement(bidiRoot, start + endOffs,
889                                                       nextEl.getEndOffset(),
890                                                       nextLevel));
891                            removeTo = nextIndex;
892                          }
893                      }
894                    else if (level == nextLevel)
895                      {
896                        // Merge current and next run.
897                        newEls.add(new BidiElement(bidiRoot, start + lastRunStart,
898                                                   start + lastRunEnd,
899                                                   lastRunLevel));
900                        newEls.add(new BidiElement(bidiRoot, start + lastRunEnd,
901                                                   nextEl.getEndOffset(), level));
902                        removeTo = nextIndex;
903                      }
904                    else
905                      {
906                        // Split next element.
907                        int endOffs = offs + bidi.getRunLimit(r);
908                        newEls.add(new BidiElement(bidiRoot, start + lastRunStart,
909                                                   start + lastRunEnd,
910                                                   lastRunLevel));
911                        newEls.add(new BidiElement(bidiRoot, start + lastRunEnd,
912                                                   start + endOffs, level));
913                        newEls.add(new BidiElement(bidiRoot, start + endOffs,
914                                                   nextEl.getEndOffset(),
915                                                   nextLevel));
916                        removeTo = nextIndex;
917                      }
918                  }
919                else
920                  {
921                    removeTo = bidiRoot.getElementIndex(end);
922                    int level = bidi.getRunLevel(r);
923                    int runEnd = offs + bidi.getRunLimit(r);
924
925                    if (level == lastRunLevel)
926                      {
927                        // Merge with previous.
928                        lastRunEnd = offs + runEnd;
929                        newEls.add(new BidiElement(bidiRoot,
930                                                  start + lastRunStart,
931                                                  start + runEnd, level));
932                      }
933                    else
934                      {
935                        // Create element for last run and current run.
936                        newEls.add(new BidiElement(bidiRoot, start + lastRunStart,
937                                                   start + lastRunEnd,
938                                                   lastRunLevel));
939                        newEls.add(new BidiElement(bidiRoot,
940                                                   start + lastRunEnd,
941                                                   start + runEnd,
942                                                   level));
943                       }
944                  }
945              }
946            else
947              {
948                int level = bidi.getRunLevel(r);
949                int runEnd = bidi.getRunLimit(r);
950
951                if (level == lastRunLevel)
952                  {
953                    // Merge with previous.
954                    lastRunEnd = offs + runEnd;
955                  }
956                else
957                  {
958                    // Create element for last run and update values for
959                    // current run.
960                    newEls.add(new BidiElement(bidiRoot, start + lastRunStart,
961                                               start + lastRunEnd,
962                                               lastRunLevel));
963                    lastRunStart = lastRunEnd;
964                    lastRunEnd = offs + runEnd;
965                    lastRunLevel = level;
966                  }
967              }
968          }
969        offs += bidi.getLength();
970      }
971
972    // Determine the bidi elements which are to be removed.
973    int numRemoved = 0;
974    if (bidiRoot.getElementCount() > 0)
975      numRemoved = removeTo - removeFrom + 1;
976    Element[] removed = new Element[numRemoved];
977    for (int i = 0; i < numRemoved; i++)
978      removed[i] = bidiRoot.getElement(removeFrom + i);
979
980    Element[] added = new Element[newEls.size()];
981    added = (Element[]) newEls.toArray(added);
982
983    // Update the event.
984    ElementEdit edit = new ElementEdit(bidiRoot, removeFrom, removed, added);
985    ev.addEdit(edit);
986
987    // Update the structure.
988    bidiRoot.replace(removeFrom, numRemoved, added);
989  }
990
991  /**
992   * Determines the Bidi objects for the paragraphs in the specified range.
993   *
994   * @param start the start of the range
995   * @param end the end of the range
996   *
997   * @return the Bidi analysers for the paragraphs in the range
998   */
999  private Bidi[] getBidis(int start, int end)
1000  {
1001    // Determine the default run direction from the document property.
1002    Boolean defaultDir = null;
1003    Object o = getProperty(TextAttribute.RUN_DIRECTION);
1004    if (o instanceof Boolean)
1005      defaultDir = (Boolean) o;
1006
1007    // Scan paragraphs and add their level arrays to the overall levels array.
1008    ArrayList bidis = new ArrayList();
1009    Segment s = new Segment();
1010    for (int i = start; i < end;)
1011      {
1012        Element par = getParagraphElement(i);
1013        int pStart = par.getStartOffset();
1014        int pEnd = par.getEndOffset();
1015
1016        // Determine the default run direction of the paragraph.
1017        Boolean dir = defaultDir;
1018        o = par.getAttributes().getAttribute(TextAttribute.RUN_DIRECTION);
1019        if (o instanceof Boolean)
1020          dir = (Boolean) o;
1021
1022        // Bidi over the paragraph.
1023        try
1024          {
1025            getText(pStart, pEnd - pStart, s);
1026          }
1027        catch (BadLocationException ex)
1028          {
1029            assert false : "Must not happen";
1030          }
1031        int flag = Bidi.DIRECTION_DEFAULT_LEFT_TO_RIGHT;
1032        if (dir != null)
1033          {
1034            if (TextAttribute.RUN_DIRECTION_LTR.equals(dir))
1035              flag = Bidi.DIRECTION_LEFT_TO_RIGHT;
1036            else
1037              flag = Bidi.DIRECTION_RIGHT_TO_LEFT;
1038          }
1039        Bidi bidi = new Bidi(s.array, s.offset, null, 0, s.count, flag);
1040        bidis.add(bidi);
1041        i = pEnd;
1042      }
1043    Bidi[] ret = new Bidi[bidis.size()];
1044    ret = (Bidi[]) bidis.toArray(ret);
1045    return ret;
1046  }
1047
1048  /**
1049   * Blocks until a read lock can be obtained.  Must block if there is
1050   * currently a writer modifying the <code>Document</code>.
1051   */
1052  public final synchronized void readLock()
1053  {
1054    try
1055      {
1056        while (currentWriter != null)
1057          {
1058            if (currentWriter == Thread.currentThread())
1059              return;
1060            wait();
1061          }
1062        numReaders++;
1063      }
1064    catch (InterruptedException ex)
1065      {
1066        throw new Error("Interrupted during grab read lock");
1067      }
1068  }
1069
1070  /**
1071   * Releases the read lock. If this was the only reader on this
1072   * <code>Document</code>, writing may begin now.
1073   */
1074  public final synchronized void readUnlock()
1075  {
1076    // Note we could have a problem here if readUnlock was called without a
1077    // prior call to readLock but the specs simply warn users to ensure that
1078    // balance by using a finally block:
1079    // readLock()
1080    // try
1081    // {
1082    //   doSomethingHere
1083    // }
1084    // finally
1085    // {
1086    //   readUnlock();
1087    // }
1088
1089    // All that the JDK seems to check for is that you don't call unlock
1090    // more times than you've previously called lock, but it doesn't make
1091    // sure that the threads calling unlock were the same ones that called lock
1092
1093    // If the current thread holds the write lock, and attempted to also obtain
1094    // a readLock, then numReaders hasn't been incremented and we don't need
1095    // to unlock it here.
1096    if (currentWriter == Thread.currentThread())
1097      return;
1098
1099    // FIXME: the reference implementation throws a
1100    // javax.swing.text.StateInvariantError here
1101    if (numReaders <= 0)
1102      throw new IllegalStateException("document lock failure");
1103
1104    // If currentWriter is not null, the application code probably had a
1105    // writeLock and then tried to obtain a readLock, in which case
1106    // numReaders wasn't incremented
1107    numReaders--;
1108    notify();
1109  }
1110
1111  /**
1112   * Removes a piece of content from this <code>Document</code>.
1113   *
1114   * <p>If a {@link DocumentFilter} is installed in this document, the
1115   * corresponding method of the filter object is called. The
1116   * <code>DocumentFilter</code> is called even if <code>length</code>
1117   * is zero. This is different from {@link #replace}.</p>
1118   *
1119   * <p>Note: When <code>length</code> is zero or below the call is not
1120   * forwarded to the underlying {@link AbstractDocument.Content} instance
1121   * of this document and no exception is thrown.</p>
1122   *
1123   * @param offset the start offset of the fragment to be removed
1124   * @param length the length of the fragment to be removed
1125   *
1126   * @throws BadLocationException if <code>offset</code> or
1127   *         <code>offset + length</code> or invalid locations within this
1128   *         document
1129   */
1130  public void remove(int offset, int length) throws BadLocationException
1131  {
1132    writeLock();
1133    try
1134      {
1135        DocumentFilter f = getDocumentFilter();
1136        if (f == null)
1137          removeImpl(offset, length);
1138        else
1139          f.remove(getBypass(), offset, length);
1140      }
1141    finally
1142      {
1143        writeUnlock();
1144      }
1145  }
1146
1147  void removeImpl(int offset, int length) throws BadLocationException
1148  {
1149    // The RI silently ignores all requests that have a negative length.
1150    // Don't ask my why, but that's how it is.
1151    if (length > 0)
1152      {
1153        if (offset < 0 || offset > getLength())
1154          throw new BadLocationException("Invalid remove position", offset);
1155
1156        if (offset + length > getLength())
1157          throw new BadLocationException("Invalid remove length", offset);
1158
1159        DefaultDocumentEvent event =
1160          new DefaultDocumentEvent(offset, length,
1161                                   DocumentEvent.EventType.REMOVE);
1162
1163        // The order of the operations below is critical!
1164        removeUpdate(event);
1165        UndoableEdit temp = content.remove(offset, length);
1166
1167        postRemoveUpdate(event);
1168        fireRemoveUpdate(event);
1169      }
1170  }
1171
1172  /**
1173   * Replaces a piece of content in this <code>Document</code> with
1174   * another piece of content.
1175   *
1176   * <p>If a {@link DocumentFilter} is installed in this document, the
1177   * corresponding method of the filter object is called.</p>
1178   *
1179   * <p>The method has no effect if <code>length</code> is zero (and
1180   * only zero) and, at the same time, <code>text</code> is
1181   * <code>null</code> or has zero length.</p>
1182   *
1183   * @param offset the start offset of the fragment to be removed
1184   * @param length the length of the fragment to be removed
1185   * @param text the text to replace the content with
1186   * @param attributes the text attributes to assign to the new content
1187   *
1188   * @throws BadLocationException if <code>offset</code> or
1189   *         <code>offset + length</code> or invalid locations within this
1190   *         document
1191   *
1192   * @since 1.4
1193   */
1194  public void replace(int offset, int length, String text,
1195                      AttributeSet attributes)
1196    throws BadLocationException
1197  {
1198    // Bail out if we have a bogus replacement (Behavior observed in RI).
1199    if (length == 0
1200        && (text == null || text.length() == 0))
1201      return;
1202
1203    writeLock();
1204    try
1205      {
1206        if (documentFilter == null)
1207          {
1208            // It is important to call the methods which again do the checks
1209            // of the arguments and the DocumentFilter because subclasses may
1210            // have overridden these methods and provide crucial behavior
1211            // which would be skipped if we call the non-checking variants.
1212            // An example for this is PlainDocument where insertString can
1213            // provide a filtering of newlines.
1214            remove(offset, length);
1215            insertString(offset, text, attributes);
1216          }
1217        else
1218          documentFilter.replace(getBypass(), offset, length, text, attributes);
1219      }
1220    finally
1221      {
1222        writeUnlock();
1223      }
1224  }
1225
1226  void replaceImpl(int offset, int length, String text,
1227                      AttributeSet attributes)
1228    throws BadLocationException
1229  {
1230    removeImpl(offset, length);
1231    insertStringImpl(offset, text, attributes);
1232  }
1233
1234  /**
1235   * Adds a <code>DocumentListener</code> object to this document.
1236   *
1237   * @param listener the listener to add
1238   */
1239  public void addDocumentListener(DocumentListener listener)
1240  {
1241    listenerList.add(DocumentListener.class, listener);
1242  }
1243
1244  /**
1245   * Removes a <code>DocumentListener</code> object from this document.
1246   *
1247   * @param listener the listener to remove
1248   */
1249  public void removeDocumentListener(DocumentListener listener)
1250  {
1251    listenerList.remove(DocumentListener.class, listener);
1252  }
1253
1254  /**
1255   * Returns all registered <code>DocumentListener</code>s.
1256   *
1257   * @return all registered <code>DocumentListener</code>s
1258   */
1259  public DocumentListener[] getDocumentListeners()
1260  {
1261    return (DocumentListener[]) getListeners(DocumentListener.class);
1262  }
1263
1264  /**
1265   * Adds an {@link UndoableEditListener} to this <code>Document</code>.
1266   *
1267   * @param listener the listener to add
1268   */
1269  public void addUndoableEditListener(UndoableEditListener listener)
1270  {
1271    listenerList.add(UndoableEditListener.class, listener);
1272  }
1273
1274  /**
1275   * Removes an {@link UndoableEditListener} from this <code>Document</code>.
1276   *
1277   * @param listener the listener to remove
1278   */
1279  public void removeUndoableEditListener(UndoableEditListener listener)
1280  {
1281    listenerList.remove(UndoableEditListener.class, listener);
1282  }
1283
1284  /**
1285   * Returns all registered {@link UndoableEditListener}s.
1286   *
1287   * @return all registered {@link UndoableEditListener}s
1288   */
1289  public UndoableEditListener[] getUndoableEditListeners()
1290  {
1291    return (UndoableEditListener[]) getListeners(UndoableEditListener.class);
1292  }
1293
1294  /**
1295   * Called before some content gets removed from this <code>Document</code>.
1296   * The default implementation does nothing but may be overridden by
1297   * subclasses to modify the <code>Document</code> structure in response
1298   * to a remove request. The method is executed within a write lock.
1299   *
1300   * @param chng the <code>DefaultDocumentEvent</code> describing the change
1301   */
1302  protected void removeUpdate(DefaultDocumentEvent chng)
1303  {
1304    // Do nothing here. Subclasses may wish to override this.
1305  }
1306
1307  /**
1308   * Called to render this <code>Document</code> visually. It obtains a read
1309   * lock, ensuring that no changes will be made to the <code>document</code>
1310   * during the rendering process. It then calls the {@link Runnable#run()}
1311   * method on <code>runnable</code>. This method <em>must not</em> attempt
1312   * to modifiy the <code>Document</code>, since a deadlock will occur if it
1313   * tries to obtain a write lock. When the {@link Runnable#run()} method
1314   * completes (either naturally or by throwing an exception), the read lock
1315   * is released. Note that there is nothing in this method related to
1316   * the actual rendering. It could be used to execute arbitrary code within
1317   * a read lock.
1318   *
1319   * @param runnable the {@link Runnable} to execute
1320   */
1321  public void render(Runnable runnable)
1322  {
1323    readLock();
1324    try
1325    {
1326      runnable.run();
1327    }
1328    finally
1329    {
1330      readUnlock();
1331    }
1332  }
1333
1334  /**
1335   * Sets the asynchronous loading priority for this <code>Document</code>.
1336   * A value of <code>-1</code> indicates that this <code>Document</code>
1337   * should be loaded synchronously.
1338   *
1339   * @param p the asynchronous loading priority to set
1340   */
1341  public void setAsynchronousLoadPriority(int p)
1342  {
1343    Integer val = p >= 0 ? new Integer(p) : null;
1344    putProperty(AsyncLoadPriority, val);
1345  }
1346
1347  /**
1348   * Sets the properties of this <code>Document</code>.
1349   *
1350   * @param p the document properties to set
1351   */
1352  public void setDocumentProperties(Dictionary<Object, Object> p)
1353  {
1354    // FIXME: make me thread-safe
1355    properties = p;
1356  }
1357
1358  /**
1359   * Blocks until a write lock can be obtained.  Must wait if there are
1360   * readers currently reading or another thread is currently writing.
1361   */
1362  protected synchronized final void writeLock()
1363  {
1364    try
1365      {
1366        while (numReaders > 0 || currentWriter != null)
1367          {
1368            if (Thread.currentThread() == currentWriter)
1369              {
1370                if (notifyListeners)
1371                  throw new IllegalStateException("Mutation during notify");
1372                numWriters++;
1373                return;
1374              }
1375            wait();
1376          }
1377        currentWriter = Thread.currentThread();
1378        numWriters = 1;
1379      }
1380    catch (InterruptedException ex)
1381      {
1382        throw new Error("Interupted during grab write lock");
1383      }
1384  }
1385
1386  /**
1387   * Releases the write lock. This allows waiting readers or writers to
1388   * obtain the lock.
1389   */
1390  protected final synchronized void writeUnlock()
1391  {
1392    if (--numWriters <= 0)
1393      {
1394        numWriters = 0;
1395        currentWriter = null;
1396        notifyAll();
1397      }
1398  }
1399
1400  /**
1401   * Returns the currently installed {@link DocumentFilter} for this
1402   * <code>Document</code>.
1403   *
1404   * @return the currently installed {@link DocumentFilter} for this
1405   *         <code>Document</code>
1406   *
1407   * @since 1.4
1408   */
1409  public DocumentFilter getDocumentFilter()
1410  {
1411    return documentFilter;
1412  }
1413
1414  /**
1415   * Sets the {@link DocumentFilter} for this <code>Document</code>.
1416   *
1417   * @param filter the <code>DocumentFilter</code> to set
1418   *
1419   * @since 1.4
1420   */
1421  public void setDocumentFilter(DocumentFilter filter)
1422  {
1423    this.documentFilter = filter;
1424  }
1425
1426  /**
1427   * Dumps diagnostic information to the specified <code>PrintStream</code>.
1428   *
1429   * @param out the stream to write the diagnostic information to
1430   */
1431  public void dump(PrintStream out)
1432  {
1433    ((AbstractElement) getDefaultRootElement()).dump(out, 0);
1434    ((AbstractElement) getBidiRootElement()).dump(out, 0);
1435  }
1436
1437  /**
1438   * Defines a set of methods for managing text attributes for one or more
1439   * <code>Document</code>s.
1440   *
1441   * Replicating {@link AttributeSet}s throughout a <code>Document</code> can
1442   * be very expensive. Implementations of this interface are intended to
1443   * provide intelligent management of <code>AttributeSet</code>s, eliminating
1444   * costly duplication.
1445   *
1446   * @see StyleContext
1447   */
1448  public interface AttributeContext
1449  {
1450    /**
1451     * Returns an {@link AttributeSet} that contains the attributes
1452     * of <code>old</code> plus the new attribute specified by
1453     * <code>name</code> and <code>value</code>.
1454     *
1455     * @param old the attribute set to be merged with the new attribute
1456     * @param name the name of the attribute to be added
1457     * @param value the value of the attribute to be added
1458     *
1459     * @return the old attributes plus the new attribute
1460     */
1461    AttributeSet addAttribute(AttributeSet old, Object name, Object value);
1462
1463    /**
1464     * Returns an {@link AttributeSet} that contains the attributes
1465     * of <code>old</code> plus the new attributes in <code>attributes</code>.
1466     *
1467     * @param old the set of attributes where to add the new attributes
1468     * @param attributes the attributes to be added
1469     *
1470     * @return an {@link AttributeSet} that contains the attributes
1471     *         of <code>old</code> plus the new attributes in
1472     *         <code>attributes</code>
1473     */
1474    AttributeSet addAttributes(AttributeSet old, AttributeSet attributes);
1475
1476    /**
1477     * Returns an empty {@link AttributeSet}.
1478     *
1479     * @return  an empty {@link AttributeSet}
1480     */
1481    AttributeSet getEmptySet();
1482
1483    /**
1484     * Called to indicate that the attributes in <code>attributes</code> are
1485     * no longer used.
1486     *
1487     * @param attributes the attributes are no longer used
1488     */
1489    void reclaim(AttributeSet attributes);
1490
1491    /**
1492     * Returns a {@link AttributeSet} that has the attribute with the specified
1493     * <code>name</code> removed from <code>old</code>.
1494     *
1495     * @param old the attribute set from which an attribute is removed
1496     * @param name the name of the attribute to be removed
1497     *
1498     * @return the attributes of <code>old</code> minus the attribute
1499     *         specified by <code>name</code>
1500     */
1501    AttributeSet removeAttribute(AttributeSet old, Object name);
1502
1503    /**
1504     * Removes all attributes in <code>attributes</code> from <code>old</code>
1505     * and returns the resulting <code>AttributeSet</code>.
1506     *
1507     * @param old the set of attributes from which to remove attributes
1508     * @param attributes the attributes to be removed from <code>old</code>
1509     *
1510     * @return the attributes of <code>old</code> minus the attributes in
1511     *         <code>attributes</code>
1512     */
1513    AttributeSet removeAttributes(AttributeSet old, AttributeSet attributes);
1514
1515    /**
1516     * Removes all attributes specified by <code>names</code> from
1517     * <code>old</code> and returns the resulting <code>AttributeSet</code>.
1518     *
1519     * @param old the set of attributes from which to remove attributes
1520     * @param names the names of the attributes to be removed from
1521     *        <code>old</code>
1522     *
1523     * @return the attributes of <code>old</code> minus the attributes in
1524     *         <code>attributes</code>
1525     */
1526    AttributeSet removeAttributes(AttributeSet old, Enumeration<?> names);
1527  }
1528
1529  /**
1530   * A sequence of data that can be edited. This is were the actual content
1531   * in <code>AbstractDocument</code>'s is stored.
1532   */
1533  public interface Content
1534  {
1535    /**
1536     * Creates a {@link Position} that keeps track of the location at
1537     * <code>offset</code>.
1538     *
1539     * @return a {@link Position} that keeps track of the location at
1540     *         <code>offset</code>.
1541     *
1542     * @throw BadLocationException if <code>offset</code> is not a valid
1543     *        location in this <code>Content</code> model
1544     */
1545    Position createPosition(int offset) throws BadLocationException;
1546
1547    /**
1548     * Returns the length of the content.
1549     *
1550     * @return the length of the content
1551     */
1552    int length();
1553
1554    /**
1555     * Inserts a string into the content model.
1556     *
1557     * @param where the offset at which to insert the string
1558     * @param str the string to be inserted
1559     *
1560     * @return an <code>UndoableEdit</code> or <code>null</code> if undo is
1561     *         not supported by this <code>Content</code> model
1562     *
1563     * @throws BadLocationException if <code>where</code> is not a valid
1564     *         location in this <code>Content</code> model
1565     */
1566    UndoableEdit insertString(int where, String str)
1567      throws BadLocationException;
1568
1569    /**
1570     * Removes a piece of content from the content model.
1571     *
1572     * @param where the offset at which to remove content
1573     * @param nitems the number of characters to be removed
1574     *
1575     * @return an <code>UndoableEdit</code> or <code>null</code> if undo is
1576     *         not supported by this <code>Content</code> model
1577     *
1578     * @throws BadLocationException if <code>where</code> is not a valid
1579     *         location in this <code>Content</code> model
1580     */
1581    UndoableEdit remove(int where, int nitems) throws BadLocationException;
1582
1583    /**
1584     * Returns a piece of content.
1585     *
1586     * @param where the start offset of the requested fragment
1587     * @param len the length of the requested fragment
1588     *
1589     * @return the requested fragment
1590     * @throws BadLocationException if <code>offset</code> or
1591     *         <code>offset + len</code>is not a valid
1592     *         location in this <code>Content</code> model
1593     */
1594    String getString(int where, int len) throws BadLocationException;
1595
1596    /**
1597     * Fetches a piece of content and stores it in <code>txt</code>.
1598     *
1599     * @param where the start offset of the requested fragment
1600     * @param len the length of the requested fragment
1601     * @param txt the <code>Segment</code> where to fragment is stored into
1602     *
1603     * @throws BadLocationException if <code>offset</code> or
1604     *         <code>offset + len</code>is not a valid
1605     *         location in this <code>Content</code> model
1606     */
1607    void getChars(int where, int len, Segment txt) throws BadLocationException;
1608  }
1609
1610  /**
1611   * An abstract base implementation of the {@link Element} interface.
1612   */
1613  public abstract class AbstractElement
1614    implements Element, MutableAttributeSet, TreeNode, Serializable
1615  {
1616    /** The serialization UID (compatible with JDK1.5). */
1617    private static final long serialVersionUID = 1712240033321461704L;
1618
1619    /** The number of characters that this Element spans. */
1620    int count;
1621
1622    /** The starting offset of this Element. */
1623    int offset;
1624
1625    /** The attributes of this Element. */
1626    AttributeSet attributes;
1627
1628    /** The parent element. */
1629    Element element_parent;
1630
1631    /** The parent in the TreeNode interface. */
1632    TreeNode tree_parent;
1633
1634    /** The children of this element. */
1635    Vector tree_children;
1636
1637    /**
1638     * Creates a new instance of <code>AbstractElement</code> with a
1639     * specified parent <code>Element</code> and <code>AttributeSet</code>.
1640     *
1641     * @param p the parent of this <code>AbstractElement</code>
1642     * @param s the attributes to be assigned to this
1643     *        <code>AbstractElement</code>
1644     */
1645    public AbstractElement(Element p, AttributeSet s)
1646    {
1647      element_parent = p;
1648      AttributeContext ctx = getAttributeContext();
1649      attributes = ctx.getEmptySet();
1650      if (s != null)
1651        addAttributes(s);
1652    }
1653
1654    /**
1655     * Returns the child nodes of this <code>Element</code> as an
1656     * <code>Enumeration</code> of {@link TreeNode}s.
1657     *
1658     * @return the child nodes of this <code>Element</code> as an
1659     *         <code>Enumeration</code> of {@link TreeNode}s
1660     */
1661    public abstract Enumeration children();
1662
1663    /**
1664     * Returns <code>true</code> if this <code>AbstractElement</code>
1665     * allows children.
1666     *
1667     * @return <code>true</code> if this <code>AbstractElement</code>
1668     *         allows children
1669     */
1670    public abstract boolean getAllowsChildren();
1671
1672    /**
1673     * Returns the child of this <code>AbstractElement</code> at
1674     * <code>index</code>.
1675     *
1676     * @param index the position in the child list of the child element to
1677     *        be returned
1678     *
1679     * @return the child of this <code>AbstractElement</code> at
1680     *         <code>index</code>
1681     */
1682    public TreeNode getChildAt(int index)
1683    {
1684      return (TreeNode) tree_children.get(index);
1685    }
1686
1687    /**
1688     * Returns the number of children of this <code>AbstractElement</code>.
1689     *
1690     * @return the number of children of this <code>AbstractElement</code>
1691     */
1692    public int getChildCount()
1693    {
1694      return tree_children.size();
1695    }
1696
1697    /**
1698     * Returns the index of a given child <code>TreeNode</code> or
1699     * <code>-1</code> if <code>node</code> is not a child of this
1700     * <code>AbstractElement</code>.
1701     *
1702     * @param node the node for which the index is requested
1703     *
1704     * @return the index of a given child <code>TreeNode</code> or
1705     *         <code>-1</code> if <code>node</code> is not a child of this
1706     *         <code>AbstractElement</code>
1707     */
1708    public int getIndex(TreeNode node)
1709    {
1710      return tree_children.indexOf(node);
1711    }
1712
1713    /**
1714     * Returns the parent <code>TreeNode</code> of this
1715     * <code>AbstractElement</code> or <code>null</code> if this element
1716     * has no parent.
1717     *
1718     * @return the parent <code>TreeNode</code> of this
1719     *         <code>AbstractElement</code> or <code>null</code> if this
1720     *         element has no parent
1721     */
1722    public TreeNode getParent()
1723    {
1724      return tree_parent;
1725    }
1726
1727    /**
1728     * Returns <code>true</code> if this <code>AbstractElement</code> is a
1729     * leaf element, <code>false</code> otherwise.
1730     *
1731     * @return <code>true</code> if this <code>AbstractElement</code> is a
1732     *         leaf element, <code>false</code> otherwise
1733     */
1734    public abstract boolean isLeaf();
1735
1736    /**
1737     * Adds an attribute to this element.
1738     *
1739     * @param name the name of the attribute to be added
1740     * @param value the value of the attribute to be added
1741     */
1742    public void addAttribute(Object name, Object value)
1743    {
1744      attributes = getAttributeContext().addAttribute(attributes, name, value);
1745    }
1746
1747    /**
1748     * Adds a set of attributes to this element.
1749     *
1750     * @param attrs the attributes to be added to this element
1751     */
1752    public void addAttributes(AttributeSet attrs)
1753    {
1754      attributes = getAttributeContext().addAttributes(attributes, attrs);
1755    }
1756
1757    /**
1758     * Removes an attribute from this element.
1759     *
1760     * @param name the name of the attribute to be removed
1761     */
1762    public void removeAttribute(Object name)
1763    {
1764      attributes = getAttributeContext().removeAttribute(attributes, name);
1765    }
1766
1767    /**
1768     * Removes a set of attributes from this element.
1769     *
1770     * @param attrs the attributes to be removed
1771     */
1772    public void removeAttributes(AttributeSet attrs)
1773    {
1774      attributes = getAttributeContext().removeAttributes(attributes, attrs);
1775    }
1776
1777    /**
1778     * Removes a set of attribute from this element.
1779     *
1780     * @param names the names of the attributes to be removed
1781     */
1782    public void removeAttributes(Enumeration<?> names)
1783    {
1784      attributes = getAttributeContext().removeAttributes(attributes, names);
1785    }
1786
1787    /**
1788     * Sets the parent attribute set against which the element can resolve
1789     * attributes that are not defined in itself.
1790     *
1791     * @param parent the resolve parent to set
1792     */
1793    public void setResolveParent(AttributeSet parent)
1794    {
1795      attributes = getAttributeContext().addAttribute(attributes,
1796                                                      ResolveAttribute,
1797                                                      parent);
1798    }
1799
1800    /**
1801     * Returns <code>true</code> if this element contains the specified
1802     * attribute.
1803     *
1804     * @param name the name of the attribute to check
1805     * @param value the value of the attribute to check
1806     *
1807     * @return <code>true</code> if this element contains the specified
1808     *         attribute
1809     */
1810    public boolean containsAttribute(Object name, Object value)
1811    {
1812      return attributes.containsAttribute(name, value);
1813    }
1814
1815    /**
1816     * Returns <code>true</code> if this element contains all of the
1817     * specified attributes.
1818     *
1819     * @param attrs the attributes to check
1820     *
1821     * @return <code>true</code> if this element contains all of the
1822     *         specified attributes
1823     */
1824    public boolean containsAttributes(AttributeSet attrs)
1825    {
1826      return attributes.containsAttributes(attrs);
1827    }
1828
1829    /**
1830     * Returns a copy of the attributes of this element.
1831     *
1832     * @return a copy of the attributes of this element
1833     */
1834    public AttributeSet copyAttributes()
1835    {
1836      return attributes.copyAttributes();
1837    }
1838
1839    /**
1840     * Returns the attribute value with the specified key. If this attribute
1841     * is not defined in this element and this element has a resolving
1842     * parent, the search goes upward to the resolve parent chain.
1843     *
1844     * @param key the key of the requested attribute
1845     *
1846     * @return the attribute value for <code>key</code> of <code>null</code>
1847     *         if <code>key</code> is not found locally and cannot be resolved
1848     *         in this element's resolve parents
1849     */
1850    public Object getAttribute(Object key)
1851    {
1852      Object result = attributes.getAttribute(key);
1853      if (result == null)
1854        {
1855          AttributeSet resParent = getResolveParent();
1856          if (resParent != null)
1857            result = resParent.getAttribute(key);
1858        }
1859      return result;
1860    }
1861
1862    /**
1863     * Returns the number of defined attributes in this element.
1864     *
1865     * @return the number of defined attributes in this element
1866     */
1867    public int getAttributeCount()
1868    {
1869      return attributes.getAttributeCount();
1870    }
1871
1872    /**
1873     * Returns the names of the attributes of this element.
1874     *
1875     * @return the names of the attributes of this element
1876     */
1877    public Enumeration<?> getAttributeNames()
1878    {
1879      return attributes.getAttributeNames();
1880    }
1881
1882    /**
1883     * Returns the resolve parent of this element.
1884     * This is taken from the AttributeSet, but if this is null,
1885     * this method instead returns the Element's parent's
1886     * AttributeSet
1887     *
1888     * @return the resolve parent of this element
1889     *
1890     * @see #setResolveParent(AttributeSet)
1891     */
1892    public AttributeSet getResolveParent()
1893    {
1894      return attributes.getResolveParent();
1895    }
1896
1897    /**
1898     * Returns <code>true</code> if an attribute with the specified name
1899     * is defined in this element, <code>false</code> otherwise.
1900     *
1901     * @param attrName the name of the requested attributes
1902     *
1903     * @return <code>true</code> if an attribute with the specified name
1904     *         is defined in this element, <code>false</code> otherwise
1905     */
1906    public boolean isDefined(Object attrName)
1907    {
1908      return attributes.isDefined(attrName);
1909    }
1910
1911    /**
1912     * Returns <code>true</code> if the specified <code>AttributeSet</code>
1913     * is equal to this element's <code>AttributeSet</code>, <code>false</code>
1914     * otherwise.
1915     *
1916     * @param attrs the attributes to compare this element to
1917     *
1918     * @return <code>true</code> if the specified <code>AttributeSet</code>
1919     *         is equal to this element's <code>AttributeSet</code>,
1920     *         <code>false</code> otherwise
1921     */
1922    public boolean isEqual(AttributeSet attrs)
1923    {
1924      return attributes.isEqual(attrs);
1925    }
1926
1927    /**
1928     * Returns the attributes of this element.
1929     *
1930     * @return the attributes of this element
1931     */
1932    public AttributeSet getAttributes()
1933    {
1934      return this;
1935    }
1936
1937    /**
1938     * Returns the {@link Document} to which this element belongs.
1939     *
1940     * @return the {@link Document} to which this element belongs
1941     */
1942    public Document getDocument()
1943    {
1944      return AbstractDocument.this;
1945    }
1946
1947    /**
1948     * Returns the child element at the specified <code>index</code>.
1949     *
1950     * @param index the index of the requested child element
1951     *
1952     * @return the requested element
1953     */
1954    public abstract Element getElement(int index);
1955
1956    /**
1957     * Returns the name of this element.
1958     *
1959     * @return the name of this element
1960     */
1961    public String getName()
1962    {
1963      return (String) attributes.getAttribute(ElementNameAttribute);
1964    }
1965
1966    /**
1967     * Returns the parent element of this element.
1968     *
1969     * @return the parent element of this element
1970     */
1971    public Element getParentElement()
1972    {
1973      return element_parent;
1974    }
1975
1976    /**
1977     * Returns the offset inside the document model that is after the last
1978     * character of this element.
1979     *
1980     * @return the offset inside the document model that is after the last
1981     *         character of this element
1982     */
1983    public abstract int getEndOffset();
1984
1985    /**
1986     * Returns the number of child elements of this element.
1987     *
1988     * @return the number of child elements of this element
1989     */
1990    public abstract int getElementCount();
1991
1992    /**
1993     * Returns the index of the child element that spans the specified
1994     * offset in the document model.
1995     *
1996     * @param offset the offset for which the responsible element is searched
1997     *
1998     * @return the index of the child element that spans the specified
1999     *         offset in the document model
2000     */
2001    public abstract int getElementIndex(int offset);
2002
2003    /**
2004     * Returns the start offset if this element inside the document model.
2005     *
2006     * @return the start offset if this element inside the document model
2007     */
2008    public abstract int getStartOffset();
2009
2010    /**
2011     * Prints diagnostic output to the specified stream.
2012     *
2013     * @param stream the stream to write to
2014     * @param indent the indentation level
2015     */
2016    public void dump(PrintStream stream, int indent)
2017    {
2018      CPStringBuilder b = new CPStringBuilder();
2019      for (int i = 0; i < indent; ++i)
2020        b.append(' ');
2021      b.append('<');
2022      b.append(getName());
2023      // Dump attributes if there are any.
2024      if (getAttributeCount() > 0)
2025        {
2026          b.append('\n');
2027          Enumeration attNames = getAttributeNames();
2028          while (attNames.hasMoreElements())
2029            {
2030              for (int i = 0; i < indent + 2; ++i)
2031                b.append(' ');
2032              Object attName = attNames.nextElement();
2033              b.append(attName);
2034              b.append('=');
2035              Object attribute = getAttribute(attName);
2036              b.append(attribute);
2037              b.append('\n');
2038            }
2039        }
2040      if (getAttributeCount() > 0)
2041        {
2042          for (int i = 0; i < indent; ++i)
2043            b.append(' ');
2044        }
2045      b.append(">\n");
2046
2047      // Dump element content for leaf elements.
2048      if (isLeaf())
2049        {
2050          for (int i = 0; i < indent + 2; ++i)
2051            b.append(' ');
2052          int start = getStartOffset();
2053          int end = getEndOffset();
2054          b.append('[');
2055          b.append(start);
2056          b.append(',');
2057          b.append(end);
2058          b.append("][");
2059          try
2060            {
2061              b.append(getDocument().getText(start, end - start));
2062            }
2063          catch (BadLocationException ex)
2064            {
2065              AssertionError err = new AssertionError("BadLocationException "
2066                                                      + "must not be thrown "
2067                                                      + "here.");
2068              err.initCause(ex);
2069              throw err;
2070            }
2071          b.append("]\n");
2072        }
2073      stream.print(b.toString());
2074
2075      // Dump child elements if any.
2076      int count = getElementCount();
2077      for (int i = 0; i < count; ++i)
2078        {
2079          Element el = getElement(i);
2080          if (el instanceof AbstractElement)
2081            ((AbstractElement) el).dump(stream, indent + 2);
2082        }
2083    }
2084  }
2085
2086  /**
2087   * An implementation of {@link Element} to represent composite
2088   * <code>Element</code>s that contain other <code>Element</code>s.
2089   */
2090  public class BranchElement extends AbstractElement
2091  {
2092    /** The serialization UID (compatible with JDK1.5). */
2093    private static final long serialVersionUID = -6037216547466333183L;
2094
2095    /**
2096     * The child elements of this BranchElement.
2097     */
2098    private Element[] children;
2099
2100    /**
2101     * The number of children in the branch element.
2102     */
2103    private int numChildren;
2104
2105    /**
2106     * The last found index in getElementIndex(). Used for faster searching.
2107     */
2108    private int lastIndex;
2109
2110    /**
2111     * Creates a new <code>BranchElement</code> with the specified
2112     * parent and attributes.
2113     *
2114     * @param parent the parent element of this <code>BranchElement</code>
2115     * @param attributes the attributes to set on this
2116     *        <code>BranchElement</code>
2117     */
2118    public BranchElement(Element parent, AttributeSet attributes)
2119    {
2120      super(parent, attributes);
2121      children = new Element[1];
2122      numChildren = 0;
2123      lastIndex = -1;
2124    }
2125
2126    /**
2127     * Returns the children of this <code>BranchElement</code>.
2128     *
2129     * @return the children of this <code>BranchElement</code>
2130     */
2131    public Enumeration children()
2132    {
2133      if (numChildren == 0)
2134        return null;
2135
2136      Vector tmp = new Vector();
2137
2138      for (int index = 0; index < numChildren; ++index)
2139        tmp.add(children[index]);
2140
2141      return tmp.elements();
2142    }
2143
2144    /**
2145     * Returns <code>true</code> since <code>BranchElements</code> allow
2146     * child elements.
2147     *
2148     * @return <code>true</code> since <code>BranchElements</code> allow
2149     *         child elements
2150     */
2151    public boolean getAllowsChildren()
2152    {
2153      return true;
2154    }
2155
2156    /**
2157     * Returns the child element at the specified <code>index</code>.
2158     *
2159     * @param index the index of the requested child element
2160     *
2161     * @return the requested element
2162     */
2163    public Element getElement(int index)
2164    {
2165      if (index < 0 || index >= numChildren)
2166        return null;
2167
2168      return children[index];
2169    }
2170
2171    /**
2172     * Returns the number of child elements of this element.
2173     *
2174     * @return the number of child elements of this element
2175     */
2176    public int getElementCount()
2177    {
2178      return numChildren;
2179    }
2180
2181    /**
2182     * Returns the index of the child element that spans the specified
2183     * offset in the document model.
2184     *
2185     * @param offset the offset for which the responsible element is searched
2186     *
2187     * @return the index of the child element that spans the specified
2188     *         offset in the document model
2189     */
2190    public int getElementIndex(int offset)
2191    {
2192      // Implemented using an improved linear search.
2193      // This makes use of the fact that searches are not random but often
2194      // close to the previous search. So we try to start the binary
2195      // search at the last found index.
2196
2197      int i0 = 0; // The lower bounds.
2198      int i1 = numChildren - 1; // The upper bounds.
2199      int index = -1; // The found index.
2200
2201      int p0 = getStartOffset();
2202      int p1; // Start and end offset local variables.
2203
2204      if (numChildren == 0)
2205        index = 0;
2206      else if (offset >= getEndOffset())
2207        index = numChildren - 1;
2208      else
2209        {
2210          // Try lastIndex.
2211          if (lastIndex >= i0 && lastIndex <= i1)
2212            {
2213              Element last = getElement(lastIndex);
2214              p0 = last.getStartOffset();
2215              p1 = last.getEndOffset();
2216              if (offset >= p0 && offset < p1)
2217                index = lastIndex;
2218              else
2219                {
2220                  // Narrow the search bounds using the lastIndex, even
2221                  // if it hasn't been a hit.
2222                  if (offset < p0)
2223                    i1 = lastIndex;
2224                  else
2225                    i0 = lastIndex;
2226                }
2227            }
2228          // The actual search.
2229          int i = 0;
2230          while (i0 <= i1 && index == -1)
2231            {
2232              i = i0 + (i1 - i0) / 2;
2233              Element el = getElement(i);
2234              p0 = el.getStartOffset();
2235              p1 = el.getEndOffset();
2236              if (offset >= p0 && offset < p1)
2237                {
2238                  // Found it!
2239                  index = i;
2240                }
2241              else if (offset < p0)
2242                i1 = i - 1;
2243              else
2244                i0 = i + 1;
2245            }
2246
2247          if (index == -1)
2248            {
2249              // Didn't find it. Return the boundary index.
2250              if (offset < p0)
2251                index = i;
2252              else
2253                index = i + 1;
2254            }
2255
2256          lastIndex = index;
2257        }
2258      return index;
2259    }
2260
2261    /**
2262     * Returns the offset inside the document model that is after the last
2263     * character of this element.
2264     * This is the end offset of the last child element. If this element
2265     * has no children, this method throws a <code>NullPointerException</code>.
2266     *
2267     * @return the offset inside the document model that is after the last
2268     *         character of this element
2269     *
2270     * @throws NullPointerException if this branch element has no children
2271     */
2272    public int getEndOffset()
2273    {
2274      // This might accss one cached element or trigger an NPE for
2275      // numChildren == 0. This is checked by a Mauve test.
2276      Element child = numChildren > 0 ? children[numChildren - 1]
2277                                      : children[0];
2278      return child.getEndOffset();
2279    }
2280
2281    /**
2282     * Returns the name of this element. This is {@link #ParagraphElementName}
2283     * in this case.
2284     *
2285     * @return the name of this element
2286     */
2287    public String getName()
2288    {
2289      return ParagraphElementName;
2290    }
2291
2292    /**
2293     * Returns the start offset of this element inside the document model.
2294     * This is the start offset of the first child element. If this element
2295     * has no children, this method throws a <code>NullPointerException</code>.
2296     *
2297     * @return the start offset of this element inside the document model
2298     *
2299     * @throws NullPointerException if this branch element has no children and
2300     *         no startOffset value has been cached
2301     */
2302    public int getStartOffset()
2303    {
2304      // Do not explicitly throw an NPE here. If the first element is null
2305      // then the NPE gets thrown anyway. If it isn't, then it either
2306      // holds a real value (for numChildren > 0) or a cached value
2307      // (for numChildren == 0) as we don't fully remove elements in replace()
2308      // when removing single elements.
2309      // This is checked by a Mauve test.
2310      return children[0].getStartOffset();
2311    }
2312
2313    /**
2314     * Returns <code>false</code> since <code>BranchElement</code> are no
2315     * leafes.
2316     *
2317     * @return <code>false</code> since <code>BranchElement</code> are no
2318     *         leafes
2319     */
2320    public boolean isLeaf()
2321    {
2322      return false;
2323    }
2324
2325    /**
2326     * Returns the <code>Element</code> at the specified <code>Document</code>
2327     * offset.
2328     *
2329     * @return the <code>Element</code> at the specified <code>Document</code>
2330     *         offset
2331     *
2332     * @see #getElementIndex(int)
2333     */
2334    public Element positionToElement(int position)
2335    {
2336      // XXX: There is surely a better algorithm
2337      // as beginning from first element each time.
2338      for (int index = 0; index < numChildren; ++index)
2339        {
2340          Element elem = children[index];
2341
2342          if ((elem.getStartOffset() <= position)
2343              && (position < elem.getEndOffset()))
2344            return elem;
2345        }
2346
2347      return null;
2348    }
2349
2350    /**
2351     * Replaces a set of child elements with a new set of child elemens.
2352     *
2353     * @param offset the start index of the elements to be removed
2354     * @param length the number of elements to be removed
2355     * @param elements the new elements to be inserted
2356     */
2357    public void replace(int offset, int length, Element[] elements)
2358    {
2359      int delta = elements.length - length;
2360      int copyFrom = offset + length; // From where to copy.
2361      int copyTo = copyFrom + delta;    // Where to copy to.
2362      int numMove = numChildren - copyFrom; // How many elements are moved.
2363      if (numChildren + delta > children.length)
2364        {
2365          // Gotta grow the array.
2366          int newSize = Math.max(2 * children.length, numChildren + delta);
2367          Element[] target = new Element[newSize];
2368          System.arraycopy(children, 0, target, 0, offset);
2369          System.arraycopy(elements, 0, target, offset, elements.length);
2370          System.arraycopy(children, copyFrom, target, copyTo, numMove);
2371          children = target;
2372        }
2373      else
2374        {
2375          System.arraycopy(children, copyFrom, children, copyTo, numMove);
2376          System.arraycopy(elements, 0, children, offset, elements.length);
2377        }
2378      numChildren += delta;
2379    }
2380
2381    /**
2382     * Returns a string representation of this element.
2383     *
2384     * @return a string representation of this element
2385     */
2386    public String toString()
2387    {
2388      return ("BranchElement(" + getName() + ") "
2389              + getStartOffset() + "," + getEndOffset() + "\n");
2390    }
2391  }
2392
2393  /**
2394   * Stores the changes when a <code>Document</code> is beeing modified.
2395   */
2396  public class DefaultDocumentEvent extends CompoundEdit
2397    implements DocumentEvent
2398  {
2399    /** The serialization UID (compatible with JDK1.5). */
2400    private static final long serialVersionUID = 5230037221564563284L;
2401
2402    /**
2403     * The threshold that indicates when we switch to using a Hashtable.
2404     */
2405    private static final int THRESHOLD = 10;
2406
2407    /** The starting offset of the change. */
2408    private int offset;
2409
2410    /** The length of the change. */
2411    private int length;
2412
2413    /** The type of change. */
2414    private DocumentEvent.EventType type;
2415
2416    /**
2417     * Maps <code>Element</code> to their change records. This is only
2418     * used when the changes array gets too big. We can use an
2419     * (unsync'ed) HashMap here, since changes to this are (should) always
2420     * be performed inside a write lock.
2421     */
2422    private HashMap changes;
2423
2424    /**
2425     * Indicates if this event has been modified or not. This is used to
2426     * determine if this event is thrown.
2427     */
2428    private boolean modified;
2429
2430    /**
2431     * Creates a new <code>DefaultDocumentEvent</code>.
2432     *
2433     * @param offset the starting offset of the change
2434     * @param length the length of the change
2435     * @param type the type of change
2436     */
2437    public DefaultDocumentEvent(int offset, int length,
2438                                DocumentEvent.EventType type)
2439    {
2440      this.offset = offset;
2441      this.length = length;
2442      this.type = type;
2443      modified = false;
2444    }
2445
2446    /**
2447     * Adds an UndoableEdit to this <code>DocumentEvent</code>. If this
2448     * edit is an instance of {@link ElementEdit}, then this record can
2449     * later be fetched by calling {@link #getChange}.
2450     *
2451     * @param edit the undoable edit to add
2452     */
2453    public boolean addEdit(UndoableEdit edit)
2454    {
2455      // Start using Hashtable when we pass a certain threshold. This
2456      // gives a good memory/performance compromise.
2457      if (changes == null && edits.size() > THRESHOLD)
2458        {
2459          changes = new HashMap();
2460          int count = edits.size();
2461          for (int i = 0; i < count; i++)
2462            {
2463              Object o = edits.elementAt(i);
2464              if (o instanceof ElementChange)
2465                {
2466                  ElementChange ec = (ElementChange) o;
2467                  changes.put(ec.getElement(), ec);
2468                }
2469            }
2470        }
2471
2472      if (changes != null && edit instanceof ElementChange)
2473        {
2474          ElementChange elEdit = (ElementChange) edit;
2475          changes.put(elEdit.getElement(), elEdit);
2476        }
2477      return super.addEdit(edit);
2478    }
2479
2480    /**
2481     * Returns the document that has been modified.
2482     *
2483     * @return the document that has been modified
2484     */
2485    public Document getDocument()
2486    {
2487      return AbstractDocument.this;
2488    }
2489
2490    /**
2491     * Returns the length of the modification.
2492     *
2493     * @return the length of the modification
2494     */
2495    public int getLength()
2496    {
2497      return length;
2498    }
2499
2500    /**
2501     * Returns the start offset of the modification.
2502     *
2503     * @return the start offset of the modification
2504     */
2505    public int getOffset()
2506    {
2507      return offset;
2508    }
2509
2510    /**
2511     * Returns the type of the modification.
2512     *
2513     * @return the type of the modification
2514     */
2515    public DocumentEvent.EventType getType()
2516    {
2517      return type;
2518    }
2519
2520    /**
2521     * Returns the changes for an element.
2522     *
2523     * @param elem the element for which the changes are requested
2524     *
2525     * @return the changes for <code>elem</code> or <code>null</code> if
2526     *         <code>elem</code> has not been changed
2527     */
2528    public ElementChange getChange(Element elem)
2529    {
2530      ElementChange change = null;
2531      if (changes != null)
2532        {
2533          change = (ElementChange) changes.get(elem);
2534        }
2535      else
2536        {
2537          int count = edits.size();
2538          for (int i = 0; i < count && change == null; i++)
2539            {
2540              Object o = edits.get(i);
2541              if (o instanceof ElementChange)
2542                {
2543                  ElementChange ec = (ElementChange) o;
2544                  if (elem.equals(ec.getElement()))
2545                    change = ec;
2546                }
2547            }
2548        }
2549      return change;
2550    }
2551
2552    /**
2553     * Returns a String description of the change event.  This returns the
2554     * toString method of the Vector of edits.
2555     */
2556    public String toString()
2557    {
2558      return edits.toString();
2559    }
2560  }
2561
2562  /**
2563   * An implementation of {@link DocumentEvent.ElementChange} to be added
2564   * to {@link DefaultDocumentEvent}s.
2565   */
2566  public static class ElementEdit extends AbstractUndoableEdit
2567    implements DocumentEvent.ElementChange
2568  {
2569    /** The serial version UID of ElementEdit. */
2570    private static final long serialVersionUID = -1216620962142928304L;
2571
2572    /**
2573     * The changed element.
2574     */
2575    private Element elem;
2576
2577    /**
2578     * The index of the change.
2579     */
2580    private int index;
2581
2582    /**
2583     * The removed elements.
2584     */
2585    private Element[] removed;
2586
2587    /**
2588     * The added elements.
2589     */
2590    private Element[] added;
2591
2592    /**
2593     * Creates a new <code>ElementEdit</code>.
2594     *
2595     * @param elem the changed element
2596     * @param index the index of the change
2597     * @param removed the removed elements
2598     * @param added the added elements
2599     */
2600    public ElementEdit(Element elem, int index,
2601                       Element[] removed, Element[] added)
2602    {
2603      this.elem = elem;
2604      this.index = index;
2605      this.removed = removed;
2606      this.added = added;
2607    }
2608
2609    /**
2610     * Returns the added elements.
2611     *
2612     * @return the added elements
2613     */
2614    public Element[] getChildrenAdded()
2615    {
2616      return added;
2617    }
2618
2619    /**
2620     * Returns the removed elements.
2621     *
2622     * @return the removed elements
2623     */
2624    public Element[] getChildrenRemoved()
2625    {
2626      return removed;
2627    }
2628
2629    /**
2630     * Returns the changed element.
2631     *
2632     * @return the changed element
2633     */
2634    public Element getElement()
2635    {
2636      return elem;
2637    }
2638
2639    /**
2640     * Returns the index of the change.
2641     *
2642     * @return the index of the change
2643     */
2644    public int getIndex()
2645    {
2646      return index;
2647    }
2648  }
2649
2650  /**
2651   * An implementation of {@link Element} that represents a leaf in the
2652   * document structure. This is used to actually store content.
2653   */
2654  public class LeafElement extends AbstractElement
2655  {
2656    /** The serialization UID (compatible with JDK1.5). */
2657    private static final long serialVersionUID = -8906306331347768017L;
2658
2659    /**
2660     * Manages the start offset of this element.
2661     */
2662    private Position startPos;
2663
2664    /**
2665     * Manages the end offset of this element.
2666     */
2667    private Position endPos;
2668
2669    /**
2670     * Creates a new <code>LeafElement</code>.
2671     *
2672     * @param parent the parent of this <code>LeafElement</code>
2673     * @param attributes the attributes to be set
2674     * @param start the start index of this element inside the document model
2675     * @param end the end index of this element inside the document model
2676     */
2677    public LeafElement(Element parent, AttributeSet attributes, int start,
2678                       int end)
2679    {
2680      super(parent, attributes);
2681      try
2682        {
2683          startPos = createPosition(start);
2684          endPos = createPosition(end);
2685        }
2686      catch (BadLocationException ex)
2687        {
2688          AssertionError as;
2689          as = new AssertionError("BadLocationException thrown "
2690                                  + "here. start=" + start
2691                                  + ", end=" + end
2692                                  + ", length=" + getLength());
2693          as.initCause(ex);
2694          throw as;
2695        }
2696    }
2697
2698    /**
2699     * Returns <code>null</code> since <code>LeafElement</code>s cannot have
2700     * children.
2701     *
2702     * @return <code>null</code> since <code>LeafElement</code>s cannot have
2703     *         children
2704     */
2705    public Enumeration children()
2706    {
2707      return null;
2708    }
2709
2710    /**
2711     * Returns <code>false</code> since <code>LeafElement</code>s cannot have
2712     * children.
2713     *
2714     * @return <code>false</code> since <code>LeafElement</code>s cannot have
2715     *         children
2716     */
2717    public boolean getAllowsChildren()
2718    {
2719      return false;
2720    }
2721
2722    /**
2723     * Returns <code>null</code> since <code>LeafElement</code>s cannot have
2724     * children.
2725     *
2726     * @return <code>null</code> since <code>LeafElement</code>s cannot have
2727     *         children
2728     */
2729    public Element getElement(int index)
2730    {
2731      return null;
2732    }
2733
2734    /**
2735     * Returns <code>0</code> since <code>LeafElement</code>s cannot have
2736     * children.
2737     *
2738     * @return <code>0</code> since <code>LeafElement</code>s cannot have
2739     *         children
2740     */
2741    public int getElementCount()
2742    {
2743      return 0;
2744    }
2745
2746    /**
2747     * Returns <code>-1</code> since <code>LeafElement</code>s cannot have
2748     * children.
2749     *
2750     * @return <code>-1</code> since <code>LeafElement</code>s cannot have
2751     *         children
2752     */
2753    public int getElementIndex(int offset)
2754    {
2755      return -1;
2756    }
2757
2758    /**
2759     * Returns the end offset of this <code>Element</code> inside the
2760     * document.
2761     *
2762     * @return the end offset of this <code>Element</code> inside the
2763     *         document
2764     */
2765    public int getEndOffset()
2766    {
2767      return endPos.getOffset();
2768    }
2769
2770    /**
2771     * Returns the name of this <code>Element</code>. This is
2772     * {@link #ContentElementName} in this case.
2773     *
2774     * @return the name of this <code>Element</code>
2775     */
2776    public String getName()
2777    {
2778      String name = super.getName();
2779      if (name == null)
2780        name = ContentElementName;
2781      return name;
2782    }
2783
2784    /**
2785     * Returns the start offset of this <code>Element</code> inside the
2786     * document.
2787     *
2788     * @return the start offset of this <code>Element</code> inside the
2789     *         document
2790     */
2791    public int getStartOffset()
2792    {
2793      return startPos.getOffset();
2794    }
2795
2796    /**
2797     * Returns <code>true</code>.
2798     *
2799     * @return <code>true</code>
2800     */
2801    public boolean isLeaf()
2802    {
2803      return true;
2804    }
2805
2806    /**
2807     * Returns a string representation of this <code>Element</code>.
2808     *
2809     * @return a string representation of this <code>Element</code>
2810     */
2811    public String toString()
2812    {
2813      return ("LeafElement(" + getName() + ") "
2814              + getStartOffset() + "," + getEndOffset() + "\n");
2815    }
2816  }
2817
2818  /**
2819   * The root element for bidirectional text.
2820   */
2821  private class BidiRootElement
2822    extends BranchElement
2823  {
2824    /**
2825     * Creates a new bidi root element.
2826     */
2827    BidiRootElement()
2828    {
2829      super(null, null);
2830    }
2831
2832    /**
2833     * Returns the name of the element.
2834     *
2835     * @return the name of the element
2836     */
2837    public String getName()
2838    {
2839      return BidiRootName;
2840    }
2841  }
2842
2843  /**
2844   * A leaf element for the bidi structure.
2845   */
2846  private class BidiElement
2847    extends LeafElement
2848  {
2849    /**
2850     * Creates a new BidiElement.
2851     *
2852     * @param parent the parent element
2853     * @param start the start offset
2854     * @param end the end offset
2855     * @param level the bidi level
2856     */
2857    BidiElement(Element parent, int start, int end, int level)
2858    {
2859      super(parent, new SimpleAttributeSet(), start, end);
2860      addAttribute(StyleConstants.BidiLevel, new Integer(level));
2861    }
2862
2863    /**
2864     * Returns the name of the element.
2865     *
2866     * @return the name of the element
2867     */
2868    public String getName()
2869    {
2870      return BidiElementName;
2871    }
2872  }
2873
2874  /** A class whose methods delegate to the insert, remove and replace methods
2875   * of this document which do not check for an installed DocumentFilter.
2876   */
2877  class Bypass extends DocumentFilter.FilterBypass
2878  {
2879
2880    public Document getDocument()
2881    {
2882      return AbstractDocument.this;
2883    }
2884
2885    public void insertString(int offset, String string, AttributeSet attr)
2886    throws BadLocationException
2887    {
2888      AbstractDocument.this.insertStringImpl(offset, string, attr);
2889    }
2890
2891    public void remove(int offset, int length)
2892    throws BadLocationException
2893    {
2894      AbstractDocument.this.removeImpl(offset, length);
2895    }
2896
2897    public void replace(int offset, int length, String string,
2898                        AttributeSet attrs)
2899    throws BadLocationException
2900    {
2901      AbstractDocument.this.replaceImpl(offset, length, string, attrs);
2902    }
2903
2904  }
2905
2906}