/*
 * @(#)AbstractDocument.java	1.101 01/11/29
 *
 * Copyright 2002 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package javax.swing.text;

import java.util.*;
import java.io.*;

import javax.swing.undo.*;
import javax.swing.event.ChangeListener;
import javax.swing.event.*;
import javax.swing.tree.TreeNode;

/**
 * An implementation of the document interface to serve as a 
 * basis for implementing various kinds of documents.  At this
 * level there is very little policy, so there is a corresponding
 * increase in difficulty of use.
 * <p>
 * This class implements a locking mechanism for the document.  It
 * allows multiple readers or one writer, and writers must wait until 
 * all observers of the document have been notified of a previous 
 * change before beginning another mutation to the document.  The
 * read lock is aquired and released using the <code>render</code>
 * method.  A write lock is aquired by the methods that mutate the
 * document, and are held for the duration of the method call.
 * Notification is done on the thread that produced the mutation, 
 * and the thread has full read access to the document for the
 * duration of the notification, but other readers are kept out
 * until the notification has finished.  The notification is a
 * beans event notification which does not allow any further 
 * mutations until all listeners have been notified.
 * <p>
 * Any models subclassed from this class and used in conjunction
 * with a text component that has a look and feel implementation
 * that is derived from BasicTextUI may be safely updated
 * asynchronously, because all access to the View hierarchy
 * is serialized by BasicTextUI if the document is of type
 * <code>AbstractDocument</code>.  The locking assumes that an
 * independant thread will access the View hierarchy only from
 * the DocumentListener methods, and that there will be only
 * one event thread active at a time.
 * <p>
 * If concurrency support is desired, there are the following 
 * additional implications.  The code path for any DocumentListener 
 * implementation and any UndoListener implementation must be threadsafe, 
 * and not access the component lock if trying to be safe from deadlocks.  
 * The <code>repaint</code> and <code>revalidate</code> methods 
 * on JComponent are safe.
 * <p>
 * <strong>Warning:</strong>
 * Serialized objects of this class will not be compatible with 
 * future Swing releases.  The current serialization support is appropriate
 * for short term storage or RMI between applications running the same
 * version of Swing.  A future release of Swing will provide support for
 * long term persistence.
 *
 * @author  Timothy Prinzing
 * @version 1.101 11/29/01
 */
public abstract class AbstractDocument implements Document, Serializable {

    /**
     * Constructs a new AbstractDocument, wrapped around some
     * specified content storage mechanism.
     *
     * @param data the content
     */
    protected AbstractDocument(Content data) {
	this(data, StyleContext.getDefaultStyleContext());
    }

    /**
     * Constructs a new AbstractDocument, wrapped around some
     * specified content storage mechanism.
     *
     * @param data the content
     * @param context the attribute context
     */
    protected AbstractDocument(Content data, AttributeContext context) {
	this.data = data;
	this.context = context;
        bidiRoot = new BidiRootElement();

	//if (Utilities.is1dot2) {
	//putProperty( I18NProperty, Boolean.TRUE );
	//} else {
	putProperty( I18NProperty, Boolean.FALSE );
	//}

        //REMIND(bcb) This creates an initial bidi element to account for
        //the \n that exists by default in the content.  Doing it this way
        //seems to expose a little too much knowledge of the content given
        //to us by the sub-class.  Consider having the sub-class' constructor
        //make an initial call to insertUpdate.
        try {
            writeLock();
            Element[] p = new Element[1];
            p[0] = new BidiElement( bidiRoot, 0, 1, 0 );
            bidiRoot.replace(0,0,p);
        } finally {
            writeUnlock();
        }
    }

    /**
     * Support for managing a set of properties. Callers
     * can use the documentProperties dictionary to annotate the
     * document with document-wide properties.
     * 
     * @return a non null Dictionary 
     * @see #setDocumentProperties
     */
    public Dictionary getDocumentProperties() {
	if (documentProperties == null) {
	    documentProperties = new Hashtable(2);
	}
	return documentProperties;
    }

    /**
     * Replace the document properties dictionary for this document.
     * 
     * @param x the new dictionary
     * @see #getDocumentProperties
     */
    public void setDocumentProperties(Dictionary x) {
	documentProperties = x;
    }

    /**
     * Notifies all listeners that have registered interest for
     * notification on this event type.  The event instance 
     * is lazily created using the parameters passed into 
     * the fire method.
     *
     * @param e the event
     * @see EventListenerList
     */
    protected void fireInsertUpdate(DocumentEvent e) {
	// Guaranteed to return a non-null array
	Object[] listeners = listenerList.getListenerList();
	// Process the listeners last to first, notifying
	// those that are interested in this event
	for (int i = listeners.length-2; i>=0; i-=2) {
	    if (listeners[i]==DocumentListener.class) {
		// Lazily create the event:
		// if (e == null)
		// e = new ListSelectionEvent(this, firstIndex, lastIndex);
		((DocumentListener)listeners[i+1]).insertUpdate(e);
	    }	       
	}
    }

    /**
     * Notifies all listeners that have registered interest for
     * notification on this event type.  The event instance 
     * is lazily created using the parameters passed into 
     * the fire method.
     *
     * @param e the event
     * @see EventListenerList
     */
    protected void fireChangedUpdate(DocumentEvent e) {
	// Guaranteed to return a non-null array
	Object[] listeners = listenerList.getListenerList();
	// Process the listeners last to first, notifying
	// those that are interested in this event
	for (int i = listeners.length-2; i>=0; i-=2) {
	    if (listeners[i]==DocumentListener.class) {
		// Lazily create the event:
		// if (e == null)
		// e = new ListSelectionEvent(this, firstIndex, lastIndex);
		((DocumentListener)listeners[i+1]).changedUpdate(e);
	    }	       
	}
    }

    /**
     * Notifies all listeners that have registered interest for
     * notification on this event type.  The event instance 
     * is lazily created using the parameters passed into 
     * the fire method.
     *
     * @param e the event
     * @see EventListenerList
     */
    protected void fireRemoveUpdate(DocumentEvent e) {
	// Guaranteed to return a non-null array
	Object[] listeners = listenerList.getListenerList();
	// Process the listeners last to first, notifying
	// those that are interested in this event
	for (int i = listeners.length-2; i>=0; i-=2) {
	    if (listeners[i]==DocumentListener.class) {
		// Lazily create the event:
		// if (e == null)
		// e = new ListSelectionEvent(this, firstIndex, lastIndex);
		((DocumentListener)listeners[i+1]).removeUpdate(e);
	    }	       
	}
    }

    /**
     * Notifies all listeners that have registered interest for
     * notification on this event type.  The event instance 
     * is lazily created using the parameters passed into 
     * the fire method.
     *
     * @param e the event
     * @see EventListenerList
     */
    protected void fireUndoableEditUpdate(UndoableEditEvent e) {
	// Guaranteed to return a non-null array
	Object[] listeners = listenerList.getListenerList();
	// Process the listeners last to first, notifying
	// those that are interested in this event
	for (int i = listeners.length-2; i>=0; i-=2) {
	    if (listeners[i]==UndoableEditListener.class) {
		// Lazily create the event:
		// if (e == null)
		// e = new ListSelectionEvent(this, firstIndex, lastIndex);
		((UndoableEditListener)listeners[i+1]).undoableEditHappened(e);
	    }	       
	}
    }

    /**
     * Get the asynchronous loading priority.  If less than zero,
     * the document should not be loaded asynchronously.
     */
    public int getAsynchronousLoadPriority() {
	Integer loadPriority = (Integer) 
	    getProperty(AbstractDocument.AsyncLoadPriority);
	if (loadPriority != null) {
	    return loadPriority.intValue();
	}
	return -1;
    }

    /**
     * Set the asynchronous loading priority. 
     */
    public void setAsynchronousLoadPriority(int p) {
	Integer loadPriority = (p >= 0) ? new Integer(p) : null;
	putProperty(AbstractDocument.AsyncLoadPriority, loadPriority);
    }

    // --- Document methods -----------------------------------------

    /**
     * This allows the model to be safely rendered in the presence
     * of currency, if the model supports being updated asynchronously.
     * The given runnable will be executed in a way that allows it
     * to safely read the model with no changes while the runnable
     * is being executed.  The runnable itself may <em>not</em>
     * make any mutations. 
     * <p>
     * This is implemented to aquire a read lock for the duration
     * of the runnables execution.  There may be multiple runnables
     * executing at the same time, and all writers will be blocked
     * while there are active rendering runnables.  If the runnable
     * throws an exception, its lock will be safely released.
     * There is no protection against a runnable that never exits,
     * which will effectively leave the document locked for it's
     * lifetime.
     * <p>
     * If the given runnable attempts to make any mutations in
     * this implementation, a deadlock will occur.  There is
     * no tracking of individual rendering threads to enable
     * detecting this situation, but a subclass could incur
     * the overhead of tracking them and throwing an error.
     * <p>
     * This method is thread safe, although most Swing methods
     * are not. Please see 
     * <A HREF="http://java.sun.com/products/jfc/swingdoc-archive/threads.html">Threads
     * and Swing</A> for more information.
     *
     * @param r the renderer to execute.
     */
    public void render(Runnable r) {
	try {
	    readLock();
	    r.run();
	} finally {
	    readUnlock();
	}
    }

    /**
     * Returns the length of the data.  This is the number of
     * characters of content that represents the users data.
     *
     * @return the length >= 0
     * @see Document#getLength
     */
    public int getLength() {
	return data.length() - 1;
    }

    /**
     * Adds a document listener for notification of any changes.
     *
     * @param listener the listener
     * @see Document#addDocumentListener
     */
    public void addDocumentListener(DocumentListener listener) {
	listenerList.add(DocumentListener.class, listener);
    }

    /**
     * Removes a document listener.
     *
     * @param listener the listener
     * @see Document#removeDocumentListener
     */
    public void removeDocumentListener(DocumentListener listener) {
	listenerList.remove(DocumentListener.class, listener);
    }

    /**
     * Adds an undo listener for notification of any changes.
     * Undo/Redo operations performed on the UndoableEdit will
     * cause the appropriate DocumentEvent to be fired to keep
     * the view(s) in sync with the model.
     *
     * @param listener the listener
     * @see Document#addUndoableEditListener
     */
    public void addUndoableEditListener(UndoableEditListener listener) {
	listenerList.add(UndoableEditListener.class, listener);
    }

    /**
     * Removes an undo listener.
     *
     * @param listener the listener
     * @see Document#removeDocumentListener
     */
    public void removeUndoableEditListener(UndoableEditListener listener) {
	listenerList.remove(UndoableEditListener.class, listener);
    }

    /**
     * A convenience method for looking up a property value. It is
     * equivalent to:
     * <pre>
     * getDocumentProperties().get(key);
     * </pre>
     * 
     * @param key the non-null property key
     * @return the value of this property or null
     * @see #getDocumentProperties
     */
    public final Object getProperty(Object key) {
        return getDocumentProperties().get(key);
    }


    /**
     * A convenience method for storing up a property value.  It is
     * equivalent to:
     * <pre>
     * getDocumentProperties().put(key, value);
     * </pre>
     * If value is null this method will remove the property
     * 
     * @param key the non-null key
     * @param value the value
     * @see #getDocumentProperties
     */
    public final void putProperty(Object key, Object value) {
	if (value != null) {
	    getDocumentProperties().put(key, value);
	} else
            getDocumentProperties().remove(key);
    }

    /**
     * Removes some content from the document.
     * Removing content causes a write lock to be held while the
     * actual changes are taking place.  Observers are notified
     * of the change on the thread that called this method.
     * <p>
     * This method is thread safe, although most Swing methods
     * are not. Please see 
     * <A HREF="http://java.sun.com/products/jfc/swingdoc-archive/threads.html">Threads
     * and Swing</A> for more information.
     * 
     * @param offs the starting offset >= 0
     * @param len the number of characters to remove >= 0
     * @exception BadLocationException  the given remove position is not a valid 
     *   position within the document
     * @see Document#remove
     */
    public void remove(int offs, int len) throws BadLocationException {
	if (len > 0) {
	    try {
		writeLock();
		DefaultDocumentEvent chng = 
		    new DefaultDocumentEvent(offs, len, DocumentEvent.EventType.REMOVE);

		boolean isComposedTextElement = false;
		if (Utilities.is1dot2) {
		    // Check whether the position of interest is the composed text
		    Element elem = getDefaultRootElement();
		    while (!elem.isLeaf()) {
			elem = elem.getElement(elem.getElementIndex(offs));
		    }
		    isComposedTextElement = Utilities.isComposedTextElement(elem);
		}

		removeUpdate(chng);
		UndoableEdit u = data.remove(offs, len);
		if (u != null) {
		    chng.addEdit(u);
		}
                postRemoveUpdate(chng);
		// Mark the edit as done.
		chng.end();
		fireRemoveUpdate(chng);
		// only fire undo if Content implementation supports it
		// undo for the composed text is not supported for now
		if ((u != null) && !isComposedTextElement) {
		    fireUndoableEditUpdate(new UndoableEditEvent(this, chng));
		}
	    } finally {
		writeUnlock();
	    }
	}
    }

    /**
     * Inserts some content into the document.
     * Inserting content causes a write lock to be held while the
     * actual changes are taking place, followed by notification
     * to the observers on the thread that grabbed the write lock.
     * <p>
     * This method is thread safe, although most Swing methods
     * are not. Please see 
     * <A HREF="http://java.sun.com/products/jfc/swingdoc-archive/threads.html">Threads
     * and Swing</A> for more information.
     *
     * @param offs the starting offset >= 0
     * @param str the string to insert; does nothing with null/empty strings
     * @param a the attributes for the inserted content
     * @exception BadLocationException  the given insert position is not a valid 
     *   position within the document
     * @see Document#insertString
     */
    public void insertString(int offs, String str, AttributeSet a) throws BadLocationException {
        if ((str == null) || (str.length() == 0)) {
	    return;
	}
	try {
	    writeLock();
	    UndoableEdit u = data.insertString(offs, str);
	    DefaultDocumentEvent e = 
		new DefaultDocumentEvent(offs, str.length(), DocumentEvent.EventType.INSERT);
	    if (u != null) {
		e.addEdit(u);
	    }
	    insertUpdate(e, a);
	    // Mark the edit as done.
	    e.end();
	    fireInsertUpdate(e);
	    // only fire undo if Content implementation supports it
	    // undo for the composed text is not supported for now
	    if (u != null && 
		(a == null || !a.isDefined(StyleConstants.ComposedTextAttribute))) {
		fireUndoableEditUpdate(new UndoableEditEvent(this, e));
	    }
	} finally {
	    writeUnlock();
	}
    }

    /**
     * Gets a sequence of text from the document.  
     *
     * @param offset the starting offset >= 0
     * @param length the number of characters to retrieve >= 0
     * @return the text
     * @exception BadLocationException  the range given includes a position 
     *   that is not a valid position within the document
     * @see Document#getText
     */
    public String getText(int offset, int length) throws BadLocationException {
	String str = data.getString(offset, length);
	return str;
    }

    /**
     * Gets some text from the document potentially without
     * making a copy.  The character array returned in the
     * given <code>Segment</code> should never be mutated.
     * This kind of access to the characters of the document
     * is provided to help make the rendering potentially more
     * efficient.  The caller should make no assumptions about
     * the lifetime of the returned character array, which
     * should be copied if needed beyond the use for rendering.
     *
     * @param offset the starting offset >= 0
     * @param length the number of characters to retrieve >= 0
     * @param txt the Segment object to retrieve the text into
     * @exception BadLocationException  the range given includes a position 
     *   that is not a valid position within the document
     */
    public void getText(int offset, int length, Segment txt) throws BadLocationException {
	data.getChars(offset, length, txt);
    }

    /**
     * Returns a position that will track change as the document
     * is altered.
     * <p>
     * This method is thread safe, although most Swing methods
     * are not. Please see 
     * <A HREF="http://java.sun.com/products/jfc/swingdoc-archive/threads.html">Threads
     * and Swing</A> for more information.
     *
     * @param offs the position in the model >= 0
     * @return the position
     * @exception BadLocationException  if the given position does not
     *   represent a valid location in the associated document
     * @see Document#createPosition
     */
    public synchronized Position createPosition(int offs) throws BadLocationException {
	return data.createPosition(offs);
    }

    /**
     * Returns a position that represents the start of the document.  The 
     * position returned can be counted on to track change and stay 
     * located at the beginning of the document.
     *
     * @return the position
     */
    public final Position getStartPosition() {
	Position p;
	try {
	    p = createPosition(0);
	} catch (BadLocationException bl) {
	    p = null;
	}
	return p;
    }
    
    /**
     * Returns a position that represents the end of the document.  The
     * position returned can be counted on to track change and stay 
     * located at the end of the document.
     *
     * @return the position
     */
    public final Position getEndPosition() {
	Position p;
	try {
	    p = createPosition(data.length());
	} catch (BadLocationException bl) {
	    p = null;
	}
	return p;
    }

    /**
     * Gets all root elements defined.  Typically, there
     * will only be one so the default implementation
     * is to return the default root element.
     *
     * @return the root element
     */
    public Element[] getRootElements() {
	Element[] elems = new Element[2];
	elems[0] = getDefaultRootElement();
        elems[1] = getBidiRootElement();
	return elems;
    }

    /**
     * Returns the root element that views should be based upon
     * unless some other mechanism for assigning views to element
     * structures is provided.
     *
     * @return the root element
     * @see Document#getDefaultRootElement
     */
    public abstract Element getDefaultRootElement();

    // ---- local methods -----------------------------------------

    /**
     * Returns the root element of the bidirectional structure for this
     * document.  Its children represent character runs with a given
     * Unicode bidi level.
     */
    public Element getBidiRootElement() {
        return bidiRoot;
    }

    /**
     * Returns true if the text in the range <code>p0</code> to
     * <code>p1</code> is left to right.
     */
    boolean isLeftToRight(int p0, int p1) {
	Element bidiRoot = getBidiRootElement();
	int index = bidiRoot.getElementIndex(p0);
	Element bidiElem = bidiRoot.getElement(index);
	if(bidiElem.getEndOffset() >= p1) {
	    AttributeSet bidiAttrs = bidiElem.getAttributes();
	    return ((StyleConstants.getBidiLevel(bidiAttrs) % 2) == 0);
	}
	return true;
    }

    /**
     * Get the paragraph element containing the given position.  Sub-classes
     * must define for themselves what exactly constitutes a paragraph.  They
     * should keep in mind however that a paragraph should at least be the
     * unit of text over which to run the Unicode bidirectional algorithm.
     *
     * @param pos the starting offset >= 0
     * @return the element */
    public abstract Element getParagraphElement(int pos);


    /**
     * Fetches the context for managing attributes.  This
     * method effectively establishes the strategy used 
     * for compressing AttributeSet information.
     *
     * @return the context
     */
    protected final AttributeContext getAttributeContext() {
	return context;
    }

    /**
     * Updates document structure as a result of text insertion.  This
     * will happen within a write lock.  If a subclass of
     * this class reimplements this method, it should delegate to the
     * superclass as well.
     *
     * @param chng a description of the change
     * @param attr the attributes for the change
     */
    protected void insertUpdate(DefaultDocumentEvent chng, AttributeSet attr) {
        if( getProperty(I18NProperty).equals( Boolean.TRUE ) )
            updateBidi( chng );
    }

    /**
     * Updates any document structure as a result of text removal.  This
     * method is called before the text is actually removed from the Content.
     * This will happen within a write lock. If a subclass
     * of this class reimplements this method, it should delegate to the
     * superclass as well.
     *
     * @param chng a description of the change
     */
    protected void removeUpdate(DefaultDocumentEvent chng) {
    }

    /**
     * Updates any document structure as a result of text removal.  This
     * method is called after the text has been removed from the Content.
     * This will happen within a write lock. If a subclass
     * of this class reimplements this method, it should delegate to the
     * superclass as well.
     *
     * @param chng a description of the change
     */
    protected void postRemoveUpdate(DefaultDocumentEvent chng) {
        if( getProperty(I18NProperty).equals( Boolean.TRUE ) )
            updateBidi( chng );
    }

    
    /**
     * Update the bidi element structure as a result of the given change
     * to the document.  The given change will be updated to reflect the
     * changes made to the bidi structure.
     *
     * This method assumes that every offset in the model is contained in
     * exactly one paragraph.  This method also assumes that it is called
     * after the change is made to the default element structure.
     */
    private void updateBidi( DefaultDocumentEvent chng ) {

        // Calculate the range of paragraphs affected by the change.
        int firstPStart;
        int lastPEnd;
        if( chng.type == DocumentEvent.EventType.INSERT ) {
            int chngStart = chng.getOffset();
            int chngEnd =  chngStart + chng.getLength();
            firstPStart = getParagraphElement(chngStart).getStartOffset();
            lastPEnd = getParagraphElement(chngEnd).getEndOffset();
        } else if( chng.type == DocumentEvent.EventType.REMOVE ) {
            Element paragraph = getParagraphElement( chng.getOffset() );
            firstPStart = paragraph.getStartOffset();
            lastPEnd = paragraph.getEndOffset();
        } else {
            throw new Error("Internal error: unknown event type.");
        }
        //System.out.println("updateBidi: firstPStart = " + firstPStart + " lastPEnd = " + lastPEnd );

        
        // Calculate the bidi levels for the affected range of paragraphs.  The
        // levels array will contain a bidi level for each character in the
        // affected text.
        byte levels[] = calculateBidiLevels( firstPStart, lastPEnd );

        
        Vector newElements = new Vector();
        
        // Calculate the first span of characters in the affected range with
        // the same bidi level.  If this level is the same as the level of the
        // previous bidi element (the existing bidi element containing
        // firstPStart-1), then merge in the previous element.  If not, but
        // the previous element overlaps the affected range, truncate the
        // previous element at firstPStart.
        int firstSpanStart = firstPStart;
        int removeFromIndex = 0;
        if( firstSpanStart > 0 ) {
            int prevElemIndex = bidiRoot.getElementIndex(firstPStart-1);
            removeFromIndex = prevElemIndex;
            Element prevElem = bidiRoot.getElement(prevElemIndex);
            int prevLevel=StyleConstants.getBidiLevel(prevElem.getAttributes());
            //System.out.println("createbidiElements: prevElem= " + prevElem  + " prevLevel= " + prevLevel + "level[0] = " + levels[0]);
            if( prevLevel==levels[0] ) {
                firstSpanStart = prevElem.getStartOffset();
            } else if( prevElem.getEndOffset() > firstPStart ) {
                newElements.addElement(new BidiElement(bidiRoot,
                                                       prevElem.getStartOffset(),
                                                       firstPStart, prevLevel));
            } else {
                removeFromIndex++;
            }
        }
        
        int firstSpanEnd = 0;
        while((firstSpanEnd<levels.length) && (levels[firstSpanEnd]==levels[0]))
            firstSpanEnd++;


        // Calculate the last span of characters in the affected range with
        // the same bidi level.  If this level is the same as the level of the
        // next bidi element (the existing bidi element containing lastPEnd),
        // then merge in the next element.  If not, but the next element
        // overlaps the affected range, adjust the next element to start at
        // lastPEnd.
        int lastSpanEnd = lastPEnd;
        Element newNextElem = null;
        int removeToIndex = bidiRoot.getElementCount() - 1;
        if( lastSpanEnd <= getLength() ) {
            int nextElemIndex = bidiRoot.getElementIndex( lastPEnd );
            removeToIndex = nextElemIndex;
            Element nextElem = bidiRoot.getElement( nextElemIndex );
            int nextLevel = StyleConstants.getBidiLevel(nextElem.getAttributes());
            if( nextLevel == levels[levels.length-1] ) {
                lastSpanEnd = nextElem.getEndOffset();
            } else if( nextElem.getStartOffset() < lastPEnd ) {
                newNextElem = new BidiElement(bidiRoot, lastPEnd, 
                                              nextElem.getEndOffset(),
                                              nextLevel);
            } else {
                removeToIndex--;
            }
        }
        
        int lastSpanStart = levels.length;
        while( (lastSpanStart>firstSpanEnd)
               && (levels[lastSpanStart-1]==levels[levels.length-1]) )
            lastSpanStart--;


        // If the first and last spans are contiguous and have the same level,
        // merge them and create a single new element for the entire span.
        // Otherwise, create elements for the first and last spans as well as
        // any spans in between.
        if((firstSpanEnd==lastSpanStart)&&(levels[0]==levels[levels.length-1])){
            newElements.addElement(new BidiElement(bidiRoot, firstSpanStart,
                                                   lastSpanEnd, levels[0]));
        } else {
            // Create an element for the first span.
            newElements.addElement(new BidiElement(bidiRoot, firstSpanStart,
                                                   firstSpanEnd+firstPStart,
                                                   levels[0]));
            // Create elements for the spans in between the first and last
            for( int i=firstSpanEnd; i<lastSpanStart; ) {
                //System.out.println("executed line 872");
                int j;
                for( j=i;  (j<levels.length) && (levels[j] == levels[i]); j++ );
                newElements.addElement(new BidiElement(bidiRoot, firstPStart+i,
                                                       firstPStart+j,
                                                       (int)levels[i]));
                i=j;
            }
            // Create an element for the last span.
            newElements.addElement(new BidiElement(bidiRoot,
                                                   lastSpanStart+firstPStart,
                                                   lastSpanEnd,
                                                   levels[levels.length-1]));
        }
        
        if( newNextElem != null )
            newElements.addElement( newNextElem );

        
        // Calculate the set of existing bidi elements which must be
        // removed.
        int removedElemCount = 0;
        if( bidiRoot.getElementCount() > 0 ) {
            removedElemCount = removeToIndex - removeFromIndex + 1;
        }
        Element[] removedElems = new Element[removedElemCount];
        for( int i=0; i<removedElemCount; i++ ) {
            removedElems[i] = bidiRoot.getElement(removeFromIndex+i);
        }            

        Element[] addedElems = new Element[ newElements.size() ];
        newElements.copyInto( addedElems );
        
        // Update the change record.
        ElementEdit ee = new ElementEdit( bidiRoot, removeFromIndex,
                                          removedElems, addedElems );
        chng.addEdit( ee );

        // Update the bidi element structure.
        bidiRoot.replace( removeFromIndex, removedElems.length, addedElems );
    }

    
    /**
     * Calculate the levels array for a range of paragraphs.  
     */
    private byte[] calculateBidiLevels( int firstPStart, int lastPEnd ) {
        
        byte levels[] = new byte[ lastPEnd - firstPStart ];
        int  levelsEnd = 0;

        // For each paragraph in the given range of paragraphs, get its
        // levels array and add it to the levels array for the entire span.
        for(int o=firstPStart; o<lastPEnd; ) {
            
            Element p = getParagraphElement( o );
            int pStart = p.getStartOffset();
            int pEnd = p.getEndOffset();
            //System.out.println("updateBidi: paragraph start = " + pStart + " paragraph end = " + pEnd);
            
            // Create a Bidi over this paragraph then get the level
            // array.
            String pText;
            try {
                pText = getText(pStart, pEnd-pStart);
            } catch (BadLocationException e ) {
                throw new Error("Internal error: " + e.toString());
            }
            // REMIND(bcb) we should really be using a Segment here.
            Bidi bidiAnalyzer = new Bidi( pText.toCharArray() );
            byte[] pLevels = bidiAnalyzer.getLevels();
            System.arraycopy( pLevels, 0, levels, levelsEnd, pLevels.length );
            levelsEnd += pLevels.length;

            o =  p.getEndOffset();
        }

        // REMIND(bcb) remove this code when debugging is done.
        if( levelsEnd != levels.length )
            throw new Error("levelsEnd assertion failed.");

        return levels;
    }

    /**
     * Gives a diagnostic dump.
     *
     * @param out the output stream
     */
    public void dump(PrintStream out) {
	Element root = getDefaultRootElement();
	if (root instanceof AbstractElement) {
	    ((AbstractElement)root).dump(out, 0);
	}
        bidiRoot.dump(out,0);
    }

    /**
     * Gets the content for the document.
     *
     * @return the content
     */
    protected final Content getContent() {
	return data;
    }

    /**
     * Creates a document leaf element.
     * Hook through which elements are created to represent the 
     * document structure.  Because this implementation keeps 
     * structure and content seperate, elements grow automatically
     * when content is extended so splits of existing elements 
     * follow.  The document itself gets to decide how to generate 
     * elements to give flexibility in the type of elements used.
     *
     * @param parent the parent element
     * @param a the attributes for the element
     * @param p0 the beginning of the range >= 0
     * @param p1 the end of the range >= p0
     * @return the new element
     */
    protected Element createLeafElement(Element parent, AttributeSet a, int p0, int p1) {
	return new LeafElement(parent, a, p0, p1);
    }

    /**
     * Creates a document branch element, that can contain other elements.
     *
     * @param parent the parent element
     * @param a the attributes
     * @return the element
     */
    protected Element createBranchElement(Element parent, AttributeSet a) {
	return new BranchElement(parent, a);
    }

    // --- Document locking ----------------------------------

    /**
     * Fetches the current writing thread if there is one.
     * This can be used to distinguish whether a method is
     * being called as part of an existing modification or
     * if a lock needs to be acquired and a new transaction
     * started.  
     *
     * @returns the thread actively modifying the document
     *  or null if there are no modifications in progress
     */
    protected synchronized final Thread getCurrentWriter() {
	return currWriter;
    }

    /**
     * Acquires a lock to begin mutating the document this lock
     * protects.  There can be no writing, notification of changes, or
     * reading going on in order to gain the lock.
     *
     * @exception IllegalStateException thrown on illegal lock
     *  attempt.  If the document is implemented properly, this can
     *  only happen if a document listener attempts to mutate the 
     *  document.  This situation violates the bean event model
     *  where order of delivery is not guaranteed and all listeners
     *  should be notified before further mutations are allowed.
     */
    protected synchronized final void writeLock() {
	try {
	    while ((numReaders > 0) || (currWriter != null)) {
		if (Thread.currentThread() == currWriter) {
		    // Assuming one doesn't do something wrong in a subclass
		    // this should only happen if a DocumentListener tries to
		    // mutate the document.
		    throw new IllegalStateException("Attempt to mutate in notification");
		}
		wait();
	    }
	    currWriter = Thread.currentThread();
	} catch (InterruptedException e) {
	    // safe to let this pass... write lock not
	    // held if the thread lands here.
	}
    }

    /**
     * Releases the write lock held because the write
     * operation is finished.  This allows either a new
     * writer or readers to aquire a lock.
     */
    protected synchronized final void writeUnlock() {
	currWriter = null;
	notify();
    }

    /**
     * Acquires a lock to begin reading some state from the 
     * document.  There can be multiple readers at the same time.
     * Writing blocks the readers until notification of the change
     * to the listeners has been completed.  This method should
     * be used very carefully to avoid unintended compromise
     * of the document.  It should always be balanced with a
     * <code>readUnlock</code>.
     *
     * @see #readUnlock
     */
    public synchronized final void readLock() {
	try {
	    while (currWriter != null) {
		if (currWriter == Thread.currentThread()) {
		    // writer has full read access.... may try to acquire
		    // lock in notification
		    return;
		}
		wait();
	    }
	    numReaders += 1;
	} catch (InterruptedException e) {
	    // safe to let this pass... read lock not
	    // held if the thread lands here.
	}
    }

    /**
     * Does a read unlock.  This signals that one
     * of the readers is done.  If there are no more readers
     * then writing can begin again.  This should be balanced
     * with a readLock, and should occur in a finally statement
     * so that the balance is guaranteed.  The following is an
     * example.
     * <pre><code>
       try {
         readLock();
	 // do something
       } finally {
         readUnlock();
       }
     * </code></pre>
     *
     * @see #readLock
     */
    public synchronized final void readUnlock() {
	if (currWriter == Thread.currentThread()) {
	    // writer has full read access.... may try to acquire
	    // lock in notification
	    return;
	}
	if (numReaders <= 0) {
	    throw new StateInvariantError(BAD_LOCK_STATE);
	}
	numReaders -= 1;
	notify();
    }

    // --- serialization ---------------------------------------------

    private void readObject(ObjectInputStream s)
      throws ClassNotFoundException, IOException 
    {
	s.defaultReadObject();
	listenerList = new EventListenerList();

        // Restore bidi structure
        //REMIND(bcb) This creates an initial bidi element to account for
        //the \n that exists by default in the content.  
        bidiRoot = new BidiRootElement();
        try {
            writeLock();
            Element[] p = new Element[1];
            p[0] = new BidiElement( bidiRoot, 0, 1, 0 );
            bidiRoot.replace(0,0,p);
        } finally {
            writeUnlock();
        }        
	// At this point bidi root is only partially correct. To fully
	// restore it we need access to getDefaultRootElement. But, this
	// is created by the subclass and at this point will be null. We
	// thus use registerValidation.
	s.registerValidation(new ObjectInputValidation() {
	    public void validateObject() {
		try {
		    writeLock();
		    DefaultDocumentEvent e = new DefaultDocumentEvent
			           (0, getLength(),
				    DocumentEvent.EventType.INSERT);
		    updateBidi( e );
		}
		finally {
		    writeUnlock();
		}
	    }
	}, 0);
    }

    // ----- member variables ------------------------------------------

    private transient int numReaders;
    private transient Thread currWriter;

    /**
     * Storage for document-wide properties.
     */
    private Dictionary documentProperties = null;

    /**
     * The event listener list for the document.
     */
    protected EventListenerList listenerList = new EventListenerList();

    /**
     * Where the text is actually stored, and a set of marks
     * that track change as the document is edited are managed.
     */
    private Content data;

    /**
     * Factory for the attributes.  This is the strategy for
     * attribute compression and control of the lifetime of
     * a set of attributes as a collection.  This may be shared
     * with other documents.
     */
    private AttributeContext context;

    /**
     * The root of the bidirectional structure for this document.  Its children
     * represent character runs with the same Unicode bidi level.
     */
    private transient BranchElement bidiRoot;
    
    private static final String BAD_LOCK_STATE = "document lock failure";

    /**
     * Error message to indicate a bad location.
     */
    protected static final String BAD_LOCATION = "document location failure";

    /**
     * Name of elements used to represent paragraphs
     */
    public static final String ParagraphElementName = "paragraph";

    /**
     * Name of elements used to represent content
     */
    public static final String ContentElementName = "content";

    /**
     * Name of elements used to hold sections (lines/paragraphs).
     */
    public static final String SectionElementName = "section";

    /**
     * Name of elements used to hold a unidirectional run
     */
    public static final String BidiElementName = "bidi level";

    /**
     * Name of the attribute used to specify element
     * names.
     */
    public static final String ElementNameAttribute = "$ename";

    /**
     * Document property that indicates whether internationalization
     * functions such as text reordering or reshaping should be
     * performed.  It is currently turned off while this code is
     * being stabilized.  It is also left as a package private for now
     * until its long term benefit is decided.
     */
    static final String I18NProperty = "i18n";

    /**
     * Document property that indicates asynchronous loading is
     * desired, with the thread priority given as the value.
     */
    static final String AsyncLoadPriority = "load priority";

    /**
     * Interface to describe a sequence of character content that
     * can be edited.  Implementations may or may not support a 
     * history mechanism which will be reflected by whether or not
     * mutations return an UndoableEdit implementation.  
     * @see AbstractDocument
     */
    public interface Content {

	/**
	 * Creates a position within the content that will
	 * track change as the content is mutated.
         *
         * @param offset the offset in the content >= 0
         * @return a Position
         * @exception BadLocationException for an invalid offset
	 */
	public Position createPosition(int offset) throws BadLocationException;

	/**
	 * Current length of the sequence of character content.
         *
         * @return the length >= 0
	 */
        public int length();

	/**
	 * Inserts a string of characters into the sequence.
	 * 
	 * @param where   Offset into the sequence to make the insertion >= 0.
	 * @param str     String to insert.
	 * @return  If the implementation supports a history mechansim, 
	 *    a reference to an Edit implementation will be returned, 
	 *    otherwise null.
	 * @exception BadLocationException  Thrown if the area covered by
	 *   the arguments is not contained in the character sequence.
	 */
        public UndoableEdit insertString(int where, String str) throws BadLocationException;

	/**
	 * Removes some portion of the sequence.  
	 *
	 * @param where   The offset into the sequence to make the
         *   insertion >= 0.
	 * @param nitems  The number of items in the sequence to remove >= 0.
	 * @return  If the implementation supports a history mechansim, 
	 *    a reference to an Edit implementation will be returned, 
	 *    otherwise null.
	 * @exception BadLocationException  Thrown if the area covered by
	 *   the arguments is not contained in the character sequence.
	 */
        public UndoableEdit remove(int where, int nitems) throws BadLocationException;

	/**
	 * Fetches a string of characters contained in the sequence.
	 * 
	 * @param where   Offset into the sequence to fetch >= 0.
	 * @param len     number of characters to copy >= 0.
         * @return the string
	 * @exception BadLocationException  Thrown if the area covered by
	 *   the arguments is not contained in the character sequence.
	 */
        public String getString(int where, int len) throws BadLocationException;

        /**
         * Gets a sequence of characters and copies them into a Segment.
         *
         * @param where the starting offset >= 0
         * @param len the number of characters >= 0
         * @param txt the target location to copy into
	 * @exception BadLocationException  Thrown if the area covered by
	 *   the arguments is not contained in the character sequence.
         */
        public void getChars(int where, int len, Segment txt) throws BadLocationException;
    }

    /**
     * An interface that can be used to allow MutableAttributeSet 
     * implementations to use pluggable attribute compression
     * techniques.  Each mutation of the attribute set can be
     * used to exchange a previous AttributeSet instance with
     * another, preserving the possibility of the AttributeSet
     * remaining immutable.  An implementation is provided by
     * the StyleContext class.
     *
     * The Element implementations provided by this class use
     * this interface to provide their MutableAttributeSet
     * implementations, so that different AttributeSet compression
     * techniques can be employed.  The method 
     * <code>getAttributeContext</code> should be implemented to
     * return the object responsible for implementing the desired
     * compression technique.
     * 
     * @see StyleContext
     */
    public interface AttributeContext {

	/**
	 * Adds an attribute to the given set, and returns
	 * the new representative set.
	 *
         * @param old the old attribute set
	 * @param name the non-null attribute name
	 * @param value the attribute value
         * @return the updated attribute set
	 * @see MutableAttributeSet#addAttribute
	 */
        public AttributeSet addAttribute(AttributeSet old, Object name, Object value);

	/**
	 * Adds a set of attributes to the element.
	 *
         * @param old the old attribute set
	 * @param attr the attributes to add
         * @return the updated attribute set
	 * @see MutableAttributeSet#addAttribute
	 */
        public AttributeSet addAttributes(AttributeSet old, AttributeSet attr);

	/**
	 * Removes an attribute from the set.
	 *
         * @param old the old attribute set
	 * @param name the non-null attribute name
         * @return the updated attribute set
	 * @see MutableAttributeSet#removeAttribute
	 */
        public AttributeSet removeAttribute(AttributeSet old, Object name);

	/**
	 * Removes a set of attributes for the element.
	 *
         * @param old the old attribute set
	 * @param names the attribute names
         * @return the updated attribute set
	 * @see MutableAttributeSet#removeAttributes
	 */
        public AttributeSet removeAttributes(AttributeSet old, Enumeration names);

	/**
	 * Removes a set of attributes for the element.
	 *
         * @param old the old attribute set
	 * @param attrs the attributes
         * @return the updated attribute set
	 * @see MutableAttributeSet#removeAttributes
	 */
        public AttributeSet removeAttributes(AttributeSet old, AttributeSet attrs);

	/**
	 * Fetches an empty AttributeSet.
         *
         * @return the attribute set
	 */
	public AttributeSet getEmptySet();

	/**
         * Reclaims an attribute set.
	 * This is a way for a MutableAttributeSet to mark that it no 
	 * longer need a particular immutable set.  This is only necessary
	 * in 1.1 where there are no weak references.  A 1.1 implementation
	 * would call this in its finalize method.
         *
         * @param a the attribute set to reclaim
	 */
	public void reclaim(AttributeSet a);
    }

    /**
     * Implements the abstract part of an element.  By default elements
     * support attributes by having a field that represents the immutable
     * part of the current attribute set for the element.  The element itself
     * implements MutableAttributeSet which can be used to modify the set
     * by fetching a new immutable set.  The immutable sets are provided
     * by the AttributeContext associated with the document.
     * <p>
     * <strong>Warning:</strong>
     * Serialized objects of this class will not be compatible with
     * future Swing releases.  The current serialization support is appropriate
     * for short term storage or RMI between applications running the same
     * version of Swing.  A future release of Swing will provide support for
     * long term persistence.
     */
    public abstract class AbstractElement implements Element, MutableAttributeSet, Serializable, TreeNode {

        /**
         * Creates a new AbstractElement.
         *
         * @param parent the parent element
         * @param a the attributes for the element
         */
        public AbstractElement(Element parent, AttributeSet a) {
	    this.parent = parent;
	    attributes = getAttributeContext().getEmptySet();
	    if (a != null) {
		addAttributes(a);
	    }
	}

	private final void indent(PrintWriter out, int n) {
	    for (int i = 0; i < n; i++) {
		out.print("  ");
	    }
	}

	/**
	 * Dumps a debugging representation of the element hierarchy.
         *
         * @param out the output stream
         * @param indentAmount the indentation level >= 0
	 */
	public void dump(PrintStream psOut, int indentAmount) {
            PrintWriter out;
            try {
                out = new PrintWriter(new OutputStreamWriter(psOut,"JavaEsc"),
                                      true);
            } catch (UnsupportedEncodingException e){
                out = new PrintWriter(psOut,true);
            }
	    indent(out, indentAmount);
	    if (getName() == null) {
		out.print("<??");
	    } else {
		out.print("<" + getName());
	    }
	    if (getAttributeCount() > 0) {
		out.println("");
		// dump the attributes
		Enumeration names = attributes.getAttributeNames();
		while (names.hasMoreElements()) {
		    Object name = names.nextElement();
		    indent(out, indentAmount + 1);
		    out.println(name + "=" + getAttribute(name));
		}
		indent(out, indentAmount);
	    }
	    out.println(">");

	    if (isLeaf()) {
		indent(out, indentAmount+1);
		out.print("[" + getStartOffset() + "," + getEndOffset() + "]");
		Content c = getContent();
		try {
		    String contentStr = c.getString(getStartOffset(), 
                                                    getEndOffset() - getStartOffset())/*.trim()*/;
		    if (contentStr.length() > 40) {
			contentStr = contentStr.substring(0, 40) + "...";
		    }
		    out.println("["+contentStr+"]");		
	        } catch (BadLocationException e) {
			;
		}

	    } else {
		int n = getElementCount();
		for (int i = 0; i < n; i++) {
		    AbstractElement e = (AbstractElement) getElement(i);
		    e.dump(psOut, indentAmount+1);
		}
	    }
	}
	 
	// --- Object methods ---------------------------

        /**
         * Finalizes an AbstractElement.
         */
	protected void finalize() throws Throwable {
	    AttributeContext context = getAttributeContext();
	    context.reclaim(attributes);
	}

	// --- AttributeSet ----------------------------
	// delegated to the immutable field "attributes"

	/**
         * Gets the number of attributes that are defined.
         *
         * @return the number of attributes >= 0
	 * @see AttributeSet#getAttributeCount
	 */
        public int getAttributeCount() {
	    return attributes.getAttributeCount();
	}

	/**
         * Checks whether a given attribute is defined.
         *
         * @param attrName the non-null attribute name
         * @return true if the attribute is defined
	 * @see AttributeSet#isDefined
	 */
        public boolean isDefined(Object attrName) {
	    return attributes.isDefined(attrName);
	}

	/**
         * Checks whether two attribute sets are equal.
         *
         * @param attr the attribute set to check against
         * @return true if the same
	 * @see AttributeSet#isEqual
	 */
        public boolean isEqual(AttributeSet attr) {
	    return attributes.isEqual(attr);
	}

	/**
         * Copies a set of attributes.
         *
         * @return the copy
	 * @see AttributeSet#copyAttributes
	 */
        public AttributeSet copyAttributes() {
	    return attributes.copyAttributes();
	}

	/**
         * Gets the value of an attribute.
         *
         * @param attrName the non-null attribute name
         * @return the attribute value
	 * @see AttributeSet#getAttribute
	 */
        public Object getAttribute(Object attrName) {
	    Object value = attributes.getAttribute(attrName);
	    if (value == null) {
		// The delegate nor it's resolvers had a match,
		// so we'll try to resolve through the parent
		// element.
		AttributeSet a = (parent != null) ? parent.getAttributes() : null;
		if (a != null) {
		    value = a.getAttribute(attrName);
		}
	    }
	    return value;
	}

	/**
         * Gets the names of all attributes.
         *
         * @return the attribute names as an enumeration
	 * @see AttributeSet#getAttributeNames
	 */
        public Enumeration getAttributeNames() {
	    return attributes.getAttributeNames();
	}

	/**
         * Checks whether a given attribute name/value is defined.
         *
         * @param name the non-null attribute name
         * @param value the attribute value
         * @return true if the name/value is defined
	 * @see AttributeSet#containsAttribute
	 */
        public boolean containsAttribute(Object name, Object value) {
	    return attributes.containsAttribute(name, value);
	}


	/**
         * Checks whether the element contains all the attributes.
         *
         * @param attrs the attributes to check
         * @return true if the element contains all the attributes
	 * @see AttributeSet#containsAttributes
	 */
        public boolean containsAttributes(AttributeSet attrs) {
	    return attributes.containsAttributes(attrs);
	}

	/**
         * Gets the resolving parent.
	 * If not overriden, the resolving parent defaults to 
	 * the parent element.
         *
         * @return the attributes from the parent, null if none
	 * @see AttributeSet#getResolveParent
	 */
        public AttributeSet getResolveParent() {
	    AttributeSet a = attributes.getResolveParent();
	    if ((a == null) && (parent != null)) {
		a = parent.getAttributes();
	    }
	    return a;
	}

	// --- MutableAttributeSet ----------------------------------
	// should fetch a new immutable record for the field
	// "attributes".

	/**
         * Adds an attribute to the element.
         *
         * @param name the non-null attribute name
         * @param value the attribute value
	 * @see MutableAttributeSet#addAttribute
	 */
        public void addAttribute(Object name, Object value) {
	    checkForIllegalCast();
	    AttributeContext context = getAttributeContext();
	    attributes = context.addAttribute(attributes, name, value);
	}

	/**
         * Adds a set of attributes to the element.
         *
         * @param attr the attributes to add
	 * @see MutableAttributeSet#addAttribute
	 */
        public void addAttributes(AttributeSet attr) {
	    checkForIllegalCast();
	    AttributeContext context = getAttributeContext();
	    attributes = context.addAttributes(attributes, attr);
	}

	/**
         * Removes an attribute from the set.
         *
         * @param name the non-null attribute name
	 * @see MutableAttributeSet#removeAttribute
	 */
        public void removeAttribute(Object name) {
	    checkForIllegalCast();
	    AttributeContext context = getAttributeContext();
	    attributes = context.removeAttribute(attributes, name);
	}

	/**
         * Removes a set of attributes for the element.
         *
         * @param names the attribute names
	 * @see MutableAttributeSet#removeAttributes
	 */
        public void removeAttributes(Enumeration names) {
	    checkForIllegalCast();
	    AttributeContext context = getAttributeContext();
	    attributes = context.removeAttributes(attributes, names);
	}

	/**
         * Removes a set of attributes for the element.
         *
         * @param attrs the attributes
	 * @see MutableAttributeSet#removeAttributes
	 */
        public void removeAttributes(AttributeSet attrs) {
	    checkForIllegalCast();
	    AttributeContext context = getAttributeContext();
	    if (attrs == this) {
		attributes = context.getEmptySet();
	    } else {
		attributes = context.removeAttributes(attributes, attrs);
	    }
	}

	/**
         * Sets the resolving parent.
         *
         * @param parent the parent, null if none
	 * @see MutableAttributeSet#setResolveParent
	 */
        public void setResolveParent(AttributeSet parent) {
	    checkForIllegalCast();
	    AttributeContext context = getAttributeContext();
	    if (parent != null) {
		attributes = 
		    context.addAttribute(attributes, StyleConstants.ResolveAttribute,
					 parent);
	    } else {
		attributes = 
		    context.removeAttribute(attributes, StyleConstants.ResolveAttribute);
	    }
	}

	private final void checkForIllegalCast() {
	    Thread t = getCurrentWriter();
	    if ((t == null) || (t != Thread.currentThread())) {
		throw new StateInvariantError("Illegal cast to MutableAttributeSet");
	    }
	}

        // --- Element methods -------------------------------------

        /**
         * Retrieves the underlying model.
         *
         * @return the model
         */
	public Document getDocument() {
	    return AbstractDocument.this;
	}

        /**
         * Gets the parent of the element.
         *
         * @return the parent
         */
	public Element getParentElement() {
	    return parent;
	}

        /**
         * Gets the attributes for the element.
         *
         * @return the attribute set
         */
	public AttributeSet getAttributes() {
	    return this;
	}

        /**
         * Gets the name of the element.
         *
         * @return the name, null if none
         */
        public String getName() {
	    if (attributes.isDefined(ElementNameAttribute)) {
		return (String) attributes.getAttribute(ElementNameAttribute);
	    }
	    return null;
	}

        /**
         * Gets the starting offset in the model for the element.
         *
         * @return the offset >= 0
         */
	public abstract int getStartOffset();

        /**
         * Gets the ending offset in the model for the element.
         *
         * @return the offset >= 0
         */
	public abstract int getEndOffset();
    
        /**
         * Gets a child element.
         *
         * @param index the child index, >= 0 && < getElementCount()
         * @return the child element
         */
	public abstract Element getElement(int index);

        /**
         * Gets the number of children for the element.
         *
         * @return the number of children >= 0
         */
	public abstract int getElementCount();

        /**
         * Gets the child element index closest to the given model offset.
         *
         * @param offset the offset >= 0
         * @return the element index >= 0
         */
	public abstract int getElementIndex(int offset);

        /**
         * Checks whether the element is a leaf.
         *
         * @return true if a leaf
         */
	public abstract boolean isLeaf();

        // --- TreeNode methods -------------------------------------

	/**
	 * Returns the child <code>TreeNode</code> at index 
	 * <code>childIndex</code>.
	 */
	public TreeNode getChildAt(int childIndex) {
	    return (TreeNode)getElement(childIndex);
	}

	/**
	 * Returns the number of children <code>TreeNode</code>s the receiver
	 * contains.
	 */
	public int getChildCount() {
	    return getElementCount();
	}

	/**
	 * Returns the parent <code>TreeNode</code> of the receiver.
	 */
	public TreeNode getParent() {
	    return (TreeNode)getParentElement();
	}

	/**
	 * Returns the index of <code>node</code> in the receivers children.
	 * If the receiver does not contain <code>node</code>, -1 will be
	 * returned.
	 */
	public int getIndex(TreeNode node) {
	    for(int counter = getChildCount() - 1; counter >= 0; counter--)
		if(getChildAt(counter) == node)
		    return counter;
	    return -1;
	}

	/**
	 * Returns true if the receiver allows children.
	 */
	public abstract boolean getAllowsChildren();


	/**
	 * Returns the children of the reciever as an Enumeration.
	 */
	public abstract Enumeration children();


	// --- serialization ---------------------------------------------

        private void writeObject(ObjectOutputStream s) throws IOException {
	    s.defaultWriteObject();
	    StyleContext.writeAttributeSet(s, attributes);
	}

        private void readObject(ObjectInputStream s)
            throws ClassNotFoundException, IOException 
        {
	    s.defaultReadObject();
	    MutableAttributeSet attr = new SimpleAttributeSet();
	    StyleContext.readAttributeSet(s, attr);
	    AttributeContext context = getAttributeContext();
	    attributes = context.addAttributes(SimpleAttributeSet.EMPTY, attr);
	}

	// ---- variables -----------------------------------------------------

	private Element parent;
	private transient AttributeSet attributes;

    }

    /**
     * Implements a composite element that contains other elements.
     * <p>
     * <strong>Warning:</strong>
     * Serialized objects of this class will not be compatible with
     * future Swing releases.  The current serialization support is appropriate
     * for short term storage or RMI between applications running the same
     * version of Swing.  A future release of Swing will provide support for
     * long term persistence.
     */
    public class BranchElement extends AbstractElement {

	/**
	 * Constructs a composite element that initially contains
	 * no children.
	 *
	 * @param parent  The parent element
         * @param a the attributes for the element
	 */
	public BranchElement(Element parent, AttributeSet a) {
	    super(parent, a);
	    children = new AbstractElement[1];
	    nchildren = 0;
	    lastIndex = -1;
	}

	/**
	 * Gets the child element that contains
	 * the given model position.
         *
         * @param pos the position >= 0
         * @return the element, null if none
	 */
	public Element positionToElement(int pos) {
	    int index = getElementIndex(pos);
	    Element child = children[index];
	    int p0 = child.getStartOffset();
	    int p1 = child.getEndOffset();
	    if ((pos >= p0) && (pos < p1)) {
		return child;
	    }
	    return null;
	}

        /**
         * Replaces content with a new set of elements.
         *
         * @param offset the starting offset >= 0
         * @param length the length to replace >= 0
         * @param elems the new elements
         */
        public void replace(int offset, int length, Element[] elems) {
	    int delta = elems.length - length;
	    int src = offset + length;
	    int nmove = nchildren - src;
	    int dest = src + delta;
	    if ((nchildren + delta) >= children.length) {
		// need to grow the array
		int newLength = Math.max(2*children.length, nchildren + delta);
		AbstractElement[] newChildren = new AbstractElement[newLength];
		System.arraycopy(children, 0, newChildren, 0, offset);
		System.arraycopy(elems, 0, newChildren, offset, elems.length);
		System.arraycopy(children, src, newChildren, dest, nmove);
		children = newChildren;
	    } else {
		// patch the existing array
		System.arraycopy(children, src, children, dest, nmove);
		System.arraycopy(elems, 0, children, offset, elems.length);
	    }
	    nchildren = nchildren + delta;
	}

        /**
         * Converts the element to a string.
         *
         * @return the string
         */
	public String toString() {
	    return "BranchElement(" + getName() + ") " + getStartOffset() + "," +
		getEndOffset() + "\n";
	}

	// --- Element methods -----------------------------------

        /**
         * Gets the element name.
         *
         * @return the element name
         */
	public String getName() {
	    String nm = super.getName();
	    if (nm == null) {
		nm = ParagraphElementName;
	    }
	    return nm;
	}

        /**
         * Gets the starting offset in the model for the element.
         *
         * @return the offset >= 0
         */
        public int getStartOffset() {
	    return children[0].getStartOffset();
	}

        /**
         * Gets the ending offset in the model for the element.
         *
         * @return the offset >= 0
         */
        public int getEndOffset() {
	    Element child = children[nchildren - 1];
	    return child.getEndOffset();
	}
    
        /**
         * Gets a child element.
         *
         * @param index the child index, >= 0 && < getElementCount()
         * @return the child element, null if none
         */
	public Element getElement(int index) {
	    if (index < nchildren) {
		return children[index];
	    }
	    return null;
	}

        /**
         * Gets the number of children for the element.
         *
         * @return the number of children >= 0
         */
	public int getElementCount()  {
	    return nchildren;
	}

        /**
         * Gets the child element index closest to the given model offset.
         *
         * @param offset the offset >= 0
         * @return the element index >= 0
         */
	public int getElementIndex(int offset) {
	    int index;
	    int lower = 0; 
	    int upper = nchildren - 1;
	    int mid = 0;
	    int p0 = getStartOffset();
	    int p1;

	    if (nchildren == 0) {
		return 0;
	    }
	    if (offset >= getEndOffset()) {
		return nchildren - 1;
	    }

	    // see if the last index can be used.
	    if ((lastIndex >= lower) && (lastIndex <= upper)) {
		Element lastHit = children[lastIndex];
		p0 = lastHit.getStartOffset();
		p1 = lastHit.getEndOffset();
		if ((offset >= p0) && (offset < p1)) {
		    return lastIndex;
		}

		// last index wasn't a hit, but it does give useful info about
		// where a hit (if any) would be.
		if (offset < p0) {
		    upper = lastIndex;
		} else  {
		    lower = lastIndex;
		}  
	    }

	    while (lower <= upper) {
		mid = lower + ((upper - lower) / 2);
		Element elem = children[mid];
		p0 = elem.getStartOffset();
		p1 = elem.getEndOffset();
		if ((offset >= p0) && (offset < p1)) {
		    // found the location
		    index = mid;
		    lastIndex = index;
		    return index;
		} else if (offset < p0) {        
		    upper = mid - 1;
		} else {
		    lower = mid + 1;
		}
	    }

	    // didn't find it, but we indicate the index of where it would belong
	    if (offset < p0) {
		index = mid;
	    } else {
		index = mid + 1;
	    }
	    lastIndex = index;
	    return index;   
	}

        /**
         * Checks whether the element is a leaf.
         *
         * @return true if a leaf
         */
	public boolean isLeaf() {
	    return false;
	}


	// ------ TreeNode ----------------------------------------------

	/**
	 * Returns true if the receiver allows children.
	 */
	public boolean getAllowsChildren() {
	    return true;
	}


	/**
	 * Returns the children of the reciever as an Enumeration.
	 */
	public Enumeration children() {
	    if(nchildren == 0)
		return null;

	    Vector tempVector = new Vector(nchildren);

	    for(int counter = 0; counter < nchildren; counter++)
		tempVector.addElement(children[counter]);
	    return tempVector.elements();
	}

	// ------ members ----------------------------------------------

	private AbstractElement[] children;
	private int nchildren;
	private int lastIndex;
    }
    
    /**
     * Implements an element that directly represents content of
     * some kind.
     * <p>
     * <strong>Warning:</strong>
     * Serialized objects of this class will not be compatible with
     * future Swing releases.  The current serialization support is appropriate
     * for short term storage or RMI between applications running the same
     * version of Swing.  A future release of Swing will provide support for
     * long term persistence.
     *
     * @see     Element
     */
    public class LeafElement extends AbstractElement {

	/**
	 * Constructs an element that represents content within the
	 * document (has no children).
	 *
	 * @param parent  The parent element
	 * @param a       The element attributes
	 * @param offs0   The start offset >= 0
	 * @param offs1   The end offset >= offs0
	 */
	public LeafElement(Element parent, AttributeSet a, int offs0, int offs1) {
	    super(parent, a);
	    try {
		p0 = createPosition(offs0);
		p1 = createPosition(offs1);
	    } catch (BadLocationException e) {
		p0 = null;
		p1 = null;
		throw new StateInvariantError("Can't create Position references");
	    }
	}

        /**
         * Converts the element to a string.
         *
         * @return the string
         */
	public String toString() {
	    return "LeafElement(" + getName() + ") " + p0 + "," + p1 + "\n";
	}

	// --- Element methods ---------------------------------------------

        /**
         * Gets the starting offset in the model for the element.
         *
         * @return the offset >= 0
         */
	public int getStartOffset() {
	    return p0.getOffset();
	}

        /**
         * Gets the ending offset in the model for the element.
         *
         * @return the offset >= 0
         */
	public int getEndOffset() {
	    return p1.getOffset();
	}

        /**
         * Gets the element name.
         *
         * @return the name
         */
	public String getName() {
	    String nm = super.getName();
	    if (nm == null) {
		nm = ContentElementName;
	    }
	    return nm;
	}

        /**
         * Gets the child element index closest to the given model offset.
         *
         * @param pos the offset >= 0
         * @return the element index >= 0
         */
	public int getElementIndex(int pos) {
	    return -1;
	}

        /**
         * Gets a child element.
         *
         * @param index the child index, >= 0 && < getElementCount()
         * @return the child element
         */
	public Element getElement(int index) {
	    return null;
	}

        /**
         * Returns the number of child elements.
         *
         * @return the number of children >= 0
         */
	public int getElementCount()  {
	    return 0;
	}

        /**
         * Checks whether the element is a leaf.
         *
         * @return true if a leaf
         */
	public boolean isLeaf() {
	    return true;
	}

	// ------ TreeNode ----------------------------------------------

	/**
	 * Returns true if the receiver allows children.
	 */
	public boolean getAllowsChildren() {
	    return false;
	}


	/**
	 * Returns the children of the reciever as an Enumeration.
	 */
	public Enumeration children() {
	    return null;
	}

	// --- serialization ---------------------------------------------

        private void writeObject(ObjectOutputStream s) throws IOException {
	    s.defaultWriteObject();
	    s.writeInt(p0.getOffset());
	    s.writeInt(p1.getOffset());
	}

        private void readObject(ObjectInputStream s)
            throws ClassNotFoundException, IOException 
        {
	    s.defaultReadObject();

	    // set the range with positions that track change
	    int off0 = s.readInt();
	    int off1 = s.readInt();
	    try {
		p0 = createPosition(off0);
		p1 = createPosition(off1);
	    } catch (BadLocationException e) {
		p0 = null;
		p1 = null;
		throw new IOException("Can't restore Position references");
	    }
	}

	// ---- members -----------------------------------------------------

	private transient Position p0;
	private transient Position p1;
    }

    /**
     * Represents the root element of the bidirectional element structure.
     * The root element is the only element in the bidi element structure
     * which contains children.  
     */
    class BidiRootElement extends BranchElement {

	BidiRootElement() {
            super( null, null );
	}

        /**
         * Gets the name of the element.
         * @return the name
         */
        public String getName() {
	    return "bidi root";
	}
    }

    /**
     * Represents an element of the bidirectional element structure.
     */
    class BidiElement extends LeafElement {

        /**
         * Creates a new BidiElement.
         */
	BidiElement(Element parent, int start, int end, int level) {
	    super(parent, new SimpleAttributeSet(), start, end);
            addAttribute(StyleConstants.BidiLevel, new Integer(level));
            //System.out.println("BidiElement: start = " + start
            //                   + " end = " + end + " level = " + level );
	}

        /**
         * Gets the name of the element.
         * @return the name
         */
        public String getName() {
	    return BidiElementName;
	}

        int getLevel() {
            Integer o = (Integer) getAttribute(StyleConstants.BidiLevel);
            if (o != null) {
                return o.intValue();
            }
            return 0;  // Level 0 is base level (non-embedded) left-to-right
        }

        boolean isLeftToRight() {
            return ((getLevel() % 2) == 0);
        }            
    }

    /**
     * Stores document changes as the document is being
     * modified.  Can subsequently be used for change notification
     * when done with the document modification transaction.
     * This is used by the AbstractDocument class and its extensions
     * for broadcasting change information to the document listeners.
     */
    public class DefaultDocumentEvent extends CompoundEdit implements DocumentEvent {

	/**
	 * Constructs a change record.
	 *
	 * @param offs the offset into the document of the change >= 0
	 * @param len  the length of the change >= 0
	 * @param type the type of event (DocumentEvent.EventType)
	 */
        public DefaultDocumentEvent(int offs, int len, DocumentEvent.EventType type) {
	    super();
	    offset = offs;
	    length = len;
	    this.type = type;
	}

	/**
	 * Returns a string description of the change event.
	 *
	 * @return a string
	 */
        public String toString() {
	    return edits.toString();
	}
	
	// --- CompoundEdit methods --------------------------

	/**
	 * Adds a document edit.  If the number of edits crosses
	 * a threshold, this switches on a hashtable lookup for
	 * ElementChange implementations since access of these
	 * needs to be relatively quick.
	 *
	 * @param anEdit a document edit record
	 * @return true if the edit was added
	 */ 
        public boolean addEdit(UndoableEdit anEdit) {
	    // if the number of changes gets too great, start using
	    // a hashtable for to locate the change for a given element.
	    if ((changeLookup == null) && (edits.size() > 10)) {
		changeLookup = new Hashtable();
		int n = edits.size();
		for (int i = 0; i < n; i++) {
		    Object o = edits.elementAt(i);
		    if (o instanceof DocumentEvent.ElementChange) {
			DocumentEvent.ElementChange ec = (DocumentEvent.ElementChange) o;
			changeLookup.put(ec.getElement(), ec);
		    }
		}
	    }

	    // if we have a hashtable... add the entry if it's 
	    // an ElementChange.
	    if ((changeLookup != null) && (anEdit instanceof DocumentEvent.ElementChange)) {
		DocumentEvent.ElementChange ec = (DocumentEvent.ElementChange) anEdit;
		changeLookup.put(ec.getElement(), ec);
	    }
	    return super.addEdit(anEdit);
	}

	/**
	 * Redoes a change.
	 *
	 * @exception CannotRedoException if the change cannot be redone
	 */
        public void redo() throws CannotRedoException {
	    writeLock();
	    try {
		// change the state
		super.redo();
		// fire a DocumentEvent to notify the view(s)
		if (type == DocumentEvent.EventType.INSERT) {
		    fireInsertUpdate(this);
		} else if (type == DocumentEvent.EventType.REMOVE) {
		    fireRemoveUpdate(this);
		} else {
		    fireChangedUpdate(this);
		}
	    } finally {
		writeUnlock();
	    }
	}

	/**
	 * Undoes a change.
	 *
	 * @exception CannotUndoException if the change cannot be undone
	 */
        public void undo() throws CannotUndoException {
	    writeLock();
	    try {
		// change the state
		super.undo();
		// fire a DocumentEvent to notify the view(s)
		if (type == DocumentEvent.EventType.REMOVE) {
		    fireInsertUpdate(this);
		} else if (type == DocumentEvent.EventType.INSERT) {
		    fireRemoveUpdate(this);
		} else {
		    fireChangedUpdate(this);
		}
	    } finally {
		writeUnlock();
	    }
	}

	/**
	 * DefaultDocument events are significant.  If you wish to aggregate
	 * DefaultDocumentEvents to present them as a single edit to the user
	 * place them into a CompoundEdit.
         *
         * @return whether the event is significant for edit undo purposes
	 */
	public boolean isSignificant() {
	    return true;
	}


	/**
	 * Provides a localized, human readable description of this edit
	 * suitable for use in, say, a change log.
         *
         * @return the description
	 */
	public String getPresentationName() {
	    DocumentEvent.EventType type = getType();
	    if(type == DocumentEvent.EventType.INSERT)
		return "addition";
	    if(type == DocumentEvent.EventType.REMOVE)
		return "deletion";
	    return "style change";
	}

	/**
	 * Provides a localized, human readable description of the undoable
	 * form of this edit, e.g. for use as an Undo menu item. Typically
	 * derived from getDescription();
         *
         * @return the description
	 */
	public String getUndoPresentationName() {
	    return "Undo " + getPresentationName();
	}

	/**
	 * Provides a localized, human readable description of the redoable
	 * form of this edit, e.g. for use as a Redo menu item. Typically
	 * derived from getPresentationName();
         *
         * @return the description
	 */
	public String getRedoPresentationName() {
	    return "Redo " + getPresentationName();
	}

	// --- DocumentEvent methods --------------------------

	/**
	 * Returns the type of event.
         *
         * @return the event type as a DocumentEvent.EventType
	 * @see DocumentEvent#getType
	 */
	public DocumentEvent.EventType getType() {
	    return type;
	}

	/**
	 * Returns the offset within the document of the start of the change.
	 *
	 * @return the offset >= 0
	 * @see DocumentEvent#getOffset
	 */
        public int getOffset() {
	    return offset;
	}

	/**
	 * Returns the length of the change.
	 *
	 * @return the length >= 0
	 * @see DocumentEvent#getLength
	 */
        public int getLength() {
	    return length;
	}
	
	/**
	 * Gets the document that sourced the change event.
	 *
	 * @return the document
	 * @see DocumentEvent#getDocument
	 */
        public Document getDocument() {
	    return AbstractDocument.this;
	}

	/**
	 * Gets the changes for an element.
	 *
	 * @param elem the element
	 * @return the changes
	 */
        public DocumentEvent.ElementChange getChange(Element elem) {
	    if (changeLookup != null) {
		return (DocumentEvent.ElementChange) changeLookup.get(elem);
	    }
	    int n = edits.size();
	    for (int i = 0; i < n; i++) {
		Object o = edits.elementAt(i);
		if (o instanceof DocumentEvent.ElementChange) {
		    DocumentEvent.ElementChange c = (DocumentEvent.ElementChange) o;
		    if (c.getElement() == elem) {
			return c;
		    }
		}
	    }
	    return null;
	}

	// --- member variables ------------------------------------

        private int offset;
        private int length;
        private Hashtable changeLookup;
	private DocumentEvent.EventType type;

    }

    /**
     * An implementation of ElementChange that can be added to the document
     * event.
     */
    public static class ElementEdit extends AbstractUndoableEdit implements DocumentEvent.ElementChange {

	/**
	 * Constructs an edit record.  This does not modify the element
	 * so it can safely be used to <em>catch up</em> a view to the
	 * current model state for views that just attached to a model.
	 *
	 * @param e the element
	 * @param index the index into the model >= 0
	 * @param removed a set of elements that were removed
	 * @param added a set of elements that were added
	 */
        public ElementEdit(Element e, int index, Element[] removed, Element[] added) {
	    super();
	    this.e = e;
	    this.index = index;
	    this.removed = removed;
	    this.added = added;
	}
	    
	/**
	 * Returns the underlying element.
	 *
	 * @return the element
	 */
        public Element getElement() {
	    return e;
	} 

	/**
	 * Returns the index into the list of elements.
	 *
	 * @return the index >= 0
	 */
        public int getIndex() {
	    return index;
	}

	/**
	 * Gets a list of children that were removed.
	 *
	 * @return the list
	 */
        public Element[] getChildrenRemoved() {
	    return removed;
	}

	/**
	 * Gets a list of children that were added.
	 *
	 * @return the list
	 */
        public Element[] getChildrenAdded() {
	    return added;
	}

	/**
	 * Redoes a change.
	 *
	 * @exception CannotRedoException if the change cannot be redone
	 */
        public void redo() throws CannotRedoException {
	    super.redo();

	    // Since this event will be reused, switch around added/removed.
	    Element[] tmp = removed;
	    removed = added;
	    added = tmp;

	    // PENDING(prinz) need MutableElement interface, canRedo() should check
	    ((AbstractDocument.BranchElement)e).replace(index, removed.length, added);
	}

	/**
	 * Undoes a change.
	 *
	 * @exception CannotUndoException if the change cannot be undone
	 */
        public void undo() throws CannotUndoException {
	    super.undo();
	    // PENDING(prinz) need MutableElement interface, canUndo() should check
	    ((AbstractDocument.BranchElement)e).replace(index, added.length, removed);

	    // Since this event will be reused, switch around added/removed.
	    Element[] tmp = removed;
	    removed = added;
	    added = tmp;
	}

        private Element e;
	private int index;
	private Element[] removed;
	private Element[] added;
    }

}