--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dwtx/text/edits/TextEdit.d	Sat Aug 23 19:10:48 2008 +0200
@@ -0,0 +1,980 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2008 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ * Port to the D programming language:
+ *     Frank Benoit <benoit@tionex.de>
+ *******************************************************************************/
+module dwtx.text.edits.TextEdit;
+
+import dwt.dwthelper.utils;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+
+import dwtx.core.runtime.Assert;
+import dwtx.jface.text.BadLocationException;
+import dwtx.jface.text.IDocument;
+import dwtx.jface.text.IRegion;
+import dwtx.jface.text.Region;
+
+
+/**
+ * A text edit describes an elementary text manipulation operation. Edits are
+ * executed by applying them to a document (e.g. an instance of <code>IDocument
+ * </code>).
+ * <p>
+ * Text edits form a tree. Clients can navigate the tree upwards, from child to
+ * parent, as well as downwards. Newly created edits are un-parented. New edits
+ * are added to the tree by calling one of the <code>add</code> methods on a parent
+ * edit.
+ * </p>
+ * <p>
+ * An edit tree is well formed in the following sense:
+ * <ul>
+ *   <li>a parent edit covers all its children</li>
+ *   <li>children don't overlap</li>
+ *   <li>an edit with length 0 can't have any children</li>
+ * </ul>
+ * Any manipulation of the tree that violates one of the above requirements results
+ * in a <code>MalformedTreeException</code>.
+ * </p>
+ * <p>
+ * Insert edits are represented by an edit of length 0. If more than one insert
+ * edit exists at the same offset then the edits are executed in the order in which
+ * they have been added to a parent. The following code example:
+ * <pre>
+ *    IDocument document= new Document("org");
+ *    MultiTextEdit edit= new MultiTextEdit();
+ *    edit.addChild(new InsertEdit(0, "www."));
+ *    edit.addChild(new InsertEdit(0, "eclipse."));
+ *    edit.apply(document);
+ * </pre>
+ * therefore results in string: "www.eclipse.org".
+ * </p>
+ * <p>
+ * Text edits can be executed in a mode where the edit's region is updated to
+ * reflect the edit's position in the changed document. Region updating is enabled
+ * by default or can be requested by passing <code>UPDATE_REGIONS</code> to the
+ * {@link #apply(IDocument, int) apply(IDocument, int)} method. In the above example
+ * the region of the <code>InsertEdit(0, "eclipse.")</code> edit after executing
+ * the root edit is <code>[3, 8]</code>. If the region of an edit got deleted during
+ * change execution the region is set to <code>[-1, -1]</code> and the method {@link
+ * #isDeleted() isDeleted} returns <code>true</code>.
+ * </p>
+ * This class isn't intended to be subclassed outside of the edit framework. Clients
+ * are only allowed to subclass <code>MultiTextEdit</code>.
+ *
+ * @since 3.0
+ * @noextend This class is not intended to be subclassed by clients.
+ */
+public abstract class TextEdit {
+
+    /**
+     * Flags indicating that neither <code>CREATE_UNDO</code> nor
+     * <code>UPDATE_REGIONS</code> is set.
+     */
+    public static final int NONE= 0;
+
+    /**
+     * Flags indicating that applying an edit tree to a document
+     * is supposed to create a corresponding undo edit. If not
+     * specified <code>null</code> is returned from method <code>
+     * apply</code>.
+     */
+    public static final int CREATE_UNDO= 1 << 0;
+
+    /**
+     * Flag indicating that the edit's region will be updated to
+     * reflect its position in the changed document. If not specified
+     * when applying an edit tree to a document the edit's region will
+     * be arbitrary. It is even not guaranteed that the tree is still
+     * well formed.
+     */
+    public static final int UPDATE_REGIONS= 1 << 1;
+
+    private static class InsertionComparator : Comparator {
+        public int compare(Object o1, Object o2) throws MalformedTreeException {
+            TextEdit edit1= (TextEdit)o1;
+            TextEdit edit2= (TextEdit)o2;
+
+            int offset1= edit1.getOffset();
+            int length1= edit1.getLength();
+
+            int offset2= edit2.getOffset();
+            int length2= edit2.getLength();
+
+            if (offset1 is offset2 && length1 is 0 && length2 is 0) {
+                return 0;
+            }
+            if (offset1 + length1 <= offset2) {
+                return -1;
+            }
+            if (offset2 + length2 <= offset1) {
+                return 1;
+            }
+            throw new MalformedTreeException(
+                    null, edit1,
+                    TextEditMessages.getString("TextEdit.overlapping")); //$NON-NLS-1$
+        }
+    }
+
+    private static final TextEdit[] EMPTY_ARRAY= new TextEdit[0];
+    private static final InsertionComparator INSERTION_COMPARATOR= new InsertionComparator();
+
+    private static final int DELETED_VALUE= -1;
+
+    private int fOffset;
+    private int fLength;
+
+    private TextEdit fParent;
+    private List fChildren;
+
+    int fDelta;
+
+    /**
+     * Create a new text edit. Parent is initialized to <code>
+     * null<code> and the edit doesn't have any children.
+     *
+     * @param offset the edit's offset
+     * @param length the edit's length
+     */
+    protected TextEdit(int offset, int length) {
+        Assert.isTrue(offset >= 0 && length >= 0);
+        fOffset= offset;
+        fLength= length;
+        fDelta= 0;
+    }
+
+    /**
+     * Copy constructor
+     *
+     * @param source the source to copy form
+     */
+    protected TextEdit(TextEdit source) {
+        fOffset= source.fOffset;
+        fLength= source.fLength;
+        fDelta= 0;
+    }
+
+    //---- Region management -----------------------------------------------
+
+    /**
+     * Returns the range that this edit is manipulating. The returned
+     * <code>IRegion</code> contains the edit's offset and length at
+     * the point in time when this call is made. Any subsequent changes
+     * to the edit's offset and length aren't reflected in the returned
+     * region object.
+     * <p>
+     * Creating a region for a deleted edit will result in an assertion
+     * failure.
+     *
+     * @return the manipulated region
+     */
+    public final IRegion getRegion() {
+        return new Region(getOffset(), getLength());
+    }
+
+    /**
+     * Returns the offset of the edit. An offset is a 0-based
+     * character index. Returns <code>-1</code> if the edit
+     * is marked as deleted.
+     *
+     * @return the offset of the edit
+     */
+    public int getOffset() {
+        return fOffset;
+    }
+
+    /**
+     * Returns the length of the edit. Returns <code>-1</code>
+     * if the edit is marked as deleted.
+     *
+     * @return the length of the edit
+     */
+    public int getLength() {
+        return fLength;
+    }
+
+    /**
+     * Returns the inclusive end position of this edit. The inclusive end
+     * position denotes the last character of the region manipulated by
+     * this edit. The returned value is the result of the following
+     * calculation:
+     * <pre>
+     *   getOffset() + getLength() - 1;
+     * <pre>
+     *
+     * @return the inclusive end position
+     */
+    public final int getInclusiveEnd() {
+        return getOffset() + getLength() - 1;
+    }
+
+    /**
+     * Returns the exclusive end position of this edit. The exclusive end
+     * position denotes the next character of the region manipulated by
+     * this edit. The returned value is the result of the following
+     * calculation:
+     * <pre>
+     *   getOffset() + getLength();
+     * </pre>
+     *
+     * @return the exclusive end position
+     */
+    public final int getExclusiveEnd() {
+        return getOffset() + getLength();
+    }
+
+    /**
+     * Returns whether this edit has been deleted or not.
+     *
+     * @return <code>true</code> if the edit has been
+     *  deleted; otherwise <code>false</code> is returned.
+     */
+    public final bool isDeleted() {
+        return fOffset is DELETED_VALUE && fLength is DELETED_VALUE;
+    }
+
+    /**
+     * Move all offsets in the tree by the given delta. This node must be a
+     * root node. The resulting offsets must be greater or equal to zero.
+     *
+     * @param delta the delta
+     * @since 3.1
+     */
+    public final void moveTree(int delta) {
+        Assert.isTrue(fParent is null);
+        Assert.isTrue(getOffset() + delta >= 0);
+        internalMoveTree(delta);
+    }
+
+    /**
+     * Returns <code>true</code> if the edit covers the given edit
+     * <code>other</code>. It is up to the concrete text edit to
+     * decide if a edit of length zero can cover another edit.
+     *
+     * @param other the other edit
+     * @return <code>true<code> if the edit covers the other edit;
+     *  otherwise <code>false</code> is returned.
+     */
+    public bool covers(TextEdit other) {
+        if (getLength() is 0 && !canZeroLengthCover())
+            return false;
+
+        if (!other.isDefined())
+            return true;
+
+        int thisOffset= getOffset();
+        int otherOffset= other.getOffset();
+        return thisOffset <= otherOffset && otherOffset + other.getLength() <= thisOffset + getLength();
+    }
+
+    /**
+     * Returns <code>true</code> if an edit with length zero can cover
+     * another edit. Returns <code>false</code> otherwise.
+     *
+     * @return whether an edit of length zero can cover another edit
+     */
+    protected bool canZeroLengthCover() {
+        return false;
+    }
+
+    /**
+     * Returns whether the region of this edit is defined or not.
+     *
+     * @return whether the region of this edit is defined or not
+     *
+     * @since 3.1
+     */
+    bool isDefined() {
+        return true;
+    }
+
+    //---- parent and children management -----------------------------
+
+    /**
+     * Returns the edit's parent. The method returns <code>null</code>
+     * if this edit hasn't been add to another edit.
+     *
+     * @return the edit's parent
+     */
+    public final TextEdit getParent() {
+        return fParent;
+    }
+
+    /**
+     * Returns the root edit of the edit tree.
+     *
+     * @return the root edit of the edit tree
+     * @since 3.1
+     */
+    public final TextEdit getRoot() {
+        TextEdit result= this;
+        while (result.fParent !is null) {
+            result= result.fParent;
+        }
+        return result;
+    }
+
+    /**
+     * Adds the given edit <code>child</code> to this edit.
+     *
+     * @param child the child edit to add
+     * @exception MalformedTreeException is thrown if the child
+     *  edit can't be added to this edit. This is the case if the child
+     *  overlaps with one of its siblings or if the child edit's region
+     *  isn't fully covered by this edit.
+     */
+    public final void addChild(TextEdit child) throws MalformedTreeException {
+        internalAdd(child);
+    }
+
+    /**
+     * Adds all edits in <code>edits</code> to this edit.
+     *
+     * @param edits the text edits to add
+     * @exception MalformedTreeException is thrown if one of
+     *  the given edits can't be added to this edit.
+     *
+     * @see #addChild(TextEdit)
+     */
+    public final void addChildren(TextEdit[] edits) throws MalformedTreeException {
+        for (int i= 0; i < edits.length; i++) {
+            internalAdd(edits[i]);
+        }
+    }
+
+    /**
+     * Removes the edit specified by the given index from the list
+     * of children. Returns the child edit that was removed from
+     * the list of children. The parent of the returned edit is
+     * set to <code>null</code>.
+     *
+     * @param index the index of the edit to remove
+     * @return the removed edit
+     * @exception IndexOutOfBoundsException if the index
+     *  is out of range
+     */
+    public final TextEdit removeChild(int index) {
+        if (fChildren is null)
+            throw new IndexOutOfBoundsException("Index: " + index + " Size: 0");  //$NON-NLS-1$//$NON-NLS-2$
+        TextEdit result= (TextEdit)fChildren.remove(index);
+        result.internalSetParent(null);
+        if (fChildren.isEmpty())
+            fChildren= null;
+        return result;
+    }
+
+    /**
+     * Removes the first occurrence of the given child from the list
+     * of children.
+     *
+     * @param child the child to be removed
+     * @return <code>true</code> if the edit contained the given
+     *  child; otherwise <code>false</code> is returned
+     */
+    public final bool removeChild(TextEdit child) {
+        Assert.isNotNull(child);
+        if (fChildren is null)
+            return false;
+        bool result= fChildren.remove(child);
+        if (result) {
+            child.internalSetParent(null);
+            if (fChildren.isEmpty())
+                fChildren= null;
+        }
+        return result;
+    }
+
+    /**
+     * Removes all child edits from and returns them. The parent
+     * of the removed edits is set to <code>null</code>.
+     *
+     * @return an array of the removed edits
+     */
+    public final TextEdit[] removeChildren() {
+        if (fChildren is null)
+            return EMPTY_ARRAY;
+        int size= fChildren.size();
+        TextEdit[] result= new TextEdit[size];
+        for (int i= 0; i < size; i++) {
+            result[i]= (TextEdit)fChildren.get(i);
+            result[i].internalSetParent(null);
+        }
+        fChildren= null;
+        return result;
+    }
+
+    /**
+     * Returns <code>true</code> if this edit has children. Otherwise
+     * <code>false</code> is returned.
+     *
+     * @return <code>true</code> if this edit has children; otherwise
+     *  <code>false</code> is returned
+     */
+    public final bool hasChildren() {
+        return fChildren !is null && ! fChildren.isEmpty();
+    }
+
+    /**
+     * Returns the edit's children. If the edit doesn't have any
+     * children an empty array is returned.
+     *
+     * @return the edit's children
+     */
+    public final TextEdit[] getChildren() {
+        if (fChildren is null)
+            return EMPTY_ARRAY;
+        return (TextEdit[])fChildren.toArray(new TextEdit[fChildren.size()]);
+    }
+
+    /**
+     * Returns the size of the managed children.
+     *
+     * @return the size of the children
+     */
+    public final int getChildrenSize() {
+        if (fChildren is null)
+            return 0;
+        return fChildren.size();
+    }
+
+    /**
+     * Returns the text range spawned by the given array of text edits.
+     * The method requires that the given array contains at least one
+     * edit. If all edits passed are deleted the method returns <code>
+     * null</code>.
+     *
+     * @param edits an array of edits
+     * @return the text range spawned by the given array of edits or
+     *  <code>null</code> if all edits are marked as deleted
+     */
+    public static IRegion getCoverage(TextEdit[] edits) {
+        Assert.isTrue(edits !is null && edits.length > 0);
+
+        int offset= Integer.MAX_VALUE;
+        int end= Integer.MIN_VALUE;
+        int deleted= 0;
+        for (int i= 0; i < edits.length; i++) {
+            TextEdit edit= edits[i];
+            if (edit.isDeleted()) {
+                deleted++;
+            } else {
+                offset= Math.min(offset, edit.getOffset());
+                end= Math.max(end, edit.getExclusiveEnd());
+            }
+        }
+        if (edits.length is deleted)
+            return null;
+
+        return new Region(offset, end - offset);
+    }
+
+    /*
+     * Hook called before this edit gets added to the passed
+     * parent.
+     */
+    void aboutToBeAdded(TextEdit parent) {
+    }
+
+    //---- Object methods ------------------------------------------------------
+
+    /**
+     * The <code>Edit</code> implementation of this <code>Object</code>
+     * method uses object identity (is).
+     *
+     * @param obj the other object
+     * @return <code>true</code> iff <code>this is obj</code>; otherwise
+     *  <code>false</code> is returned
+     *
+     * @see Object#equals(java.lang.Object)
+     */
+    public final bool equals(Object obj) {
+        return this is obj; // equivalent to Object.equals
+    }
+
+    /**
+     * The <code>Edit</code> implementation of this <code>Object</code>
+     * method calls uses <code>Object#hashCode()</code> to compute its
+     * hash code.
+     *
+     * @return the object's hash code value
+     *
+     * @see Object#hashCode()
+     */
+    public final int hashCode() {
+        return super.hashCode();
+    }
+
+    /*
+     * @see java.lang.Object#toString()
+     */
+    public String toString() {
+        StringBuffer buffer= new StringBuffer();
+        toStringWithChildren(buffer, 0);
+        return buffer.toString();
+    }
+
+    /**
+     * Adds the string representation of this text edit without
+     * children information to the given string buffer.
+     * 
+     * @param buffer    the string buffer
+     * @param indent    the indent level in number of spaces
+     * @since 3.3
+     */
+    void internalToString(StringBuffer buffer, int indent) {
+        for (int i= indent; i > 0; i--) {
+            buffer.append("  "); //$NON-NLS-1$
+        }
+        buffer.append("{"); //$NON-NLS-1$
+        String name= getClass().getName();
+        int index= name.lastIndexOf('.');
+        if (index !is -1) {
+            buffer.append(name.substring(index + 1));
+        } else {
+            buffer.append(name);
+        }
+        buffer.append("} "); //$NON-NLS-1$
+        if (isDeleted()) {
+            buffer.append("[deleted]"); //$NON-NLS-1$
+        } else {
+            buffer.append("["); //$NON-NLS-1$
+            buffer.append(getOffset());
+            buffer.append(","); //$NON-NLS-1$
+            buffer.append(getLength());
+            buffer.append("]"); //$NON-NLS-1$
+        }
+    }
+
+    /**
+     * Adds the string representation for this text edit 
+     * and its children to the given string buffer.
+     * 
+     * @param buffer    the string buffer
+     * @param indent    the indent level in number of spaces
+     * @since 3.3
+     */
+    private void toStringWithChildren(StringBuffer buffer, int indent) {
+        internalToString(buffer, indent);
+        if (fChildren !is null) {
+            for (Iterator iterator= fChildren.iterator(); iterator.hasNext();) {
+                TextEdit child= (TextEdit) iterator.next();
+                buffer.append('\n');
+                child.toStringWithChildren(buffer, indent + 1);
+            }
+        }
+    }
+    
+    //---- Copying -------------------------------------------------------------
+
+    /**
+     * Creates a deep copy of the edit tree rooted at this
+     * edit.
+     *
+     * @return a deep copy of the edit tree
+     * @see #doCopy()
+     */
+    public final TextEdit copy() {
+        TextEditCopier copier= new TextEditCopier(this);
+        return copier.perform();
+    }
+
+    /**
+     * Creates and returns a copy of this edit. The copy method should be
+     * implemented in a way so that the copy can executed without causing
+     * any harm to the original edit. Implementors of this method are
+     * responsible for creating deep or shallow copies of referenced
+     * object to fulfill this requirement.
+     * <p>
+     * Implementers of this method should use the copy constructor <code>
+     * Edit#Edit(Edit source) to initialize the edit part of the copy.
+     * Implementors aren't responsible to actually copy the children or
+     * to set the right parent.
+     * <p>
+     * This method <b>should not be called</b> from outside the framework.
+     * Please use <code>copy</code> to create a copy of a edit tree.
+     *
+     * @return a copy of this edit.
+     * @see #copy()
+     * @see #postProcessCopy(TextEditCopier)
+     * @see TextEditCopier
+     */
+    protected abstract TextEdit doCopy();
+
+    /**
+     * This method is called on every edit of the copied tree to do some
+     * post-processing like connected an edit to a different edit in the tree.
+     * <p>
+     * This default implementation does nothing
+     *
+     * @param copier the copier that manages a map between original and
+     *  copied edit.
+     * @see TextEditCopier
+     */
+    protected void postProcessCopy(TextEditCopier copier) {
+    }
+
+    //---- Visitor support -------------------------------------------------
+
+    /**
+     * Accepts the given visitor on a visit of the current edit.
+     *
+     * @param visitor the visitor object
+     * @exception IllegalArgumentException if the visitor is null
+     */
+    public final void accept(TextEditVisitor visitor) {
+        Assert.isNotNull(visitor);
+        // begin with the generic pre-visit
+        visitor.preVisit(this);
+        // dynamic dispatch to internal method for type-specific visit/endVisit
+        accept0(visitor);
+        // end with the generic post-visit
+        visitor.postVisit(this);
+    }
+
+    /**
+     * Accepts the given visitor on a type-specific visit of the current edit.
+     * This method must be implemented in all concrete text edits.
+     * <p>
+     * General template for implementation on each concrete TextEdit class:
+     * <pre>
+     * <code>
+     * bool visitChildren= visitor.visit(this);
+     * if (visitChildren) {
+     *    acceptChildren(visitor);
+     * }
+     * </code>
+     * </pre>
+     * Note that the caller (<code>accept</code>) takes care of invoking
+     * <code>visitor.preVisit(this)</code> and <code>visitor.postVisit(this)</code>.
+     * </p>
+     *
+     * @param visitor the visitor object
+     */
+    protected abstract void accept0(TextEditVisitor visitor);
+
+
+    /**
+     * Accepts the given visitor on the edits children.
+     * <p>
+     * This method must be used by the concrete implementations of
+     * <code>accept</code> to traverse list-values properties; it
+     * encapsulates the proper handling of on-the-fly changes to the list.
+     * </p>
+     *
+     * @param visitor the visitor object
+     */
+    protected final void acceptChildren(TextEditVisitor visitor) {
+        if (fChildren is null)
+            return;
+        Iterator iterator= fChildren.iterator();
+        while (iterator.hasNext()) {
+            TextEdit curr= (TextEdit) iterator.next();
+            curr.accept(visitor);
+        }
+    }
+
+    //---- Execution -------------------------------------------------------
+
+    /**
+     * Applies the edit tree rooted by this edit to the given document. To check
+     * if the edit tree can be applied to the document either catch <code>
+     * MalformedTreeException</code> or use <code>TextEditProcessor</code> to
+     * execute an edit tree.
+     *
+     * @param document the document to be manipulated
+     * @param style flags controlling the execution of the edit tree. Valid
+     *  flags are: <code>CREATE_UNDO</code> and </code>UPDATE_REGIONS</code>.
+     * @return a undo edit, if <code>CREATE_UNDO</code> is specified. Otherwise
+     *  <code>null</code> is returned.
+     *
+     * @exception MalformedTreeException is thrown if the tree isn't
+     *  in a valid state. This exception is thrown before any edit
+     *  is executed. So the document is still in its original state.
+     * @exception BadLocationException is thrown if one of the edits
+     *  in the tree can't be executed. The state of the document is
+     *  undefined if this exception is thrown.
+     *
+     * @see TextEditProcessor#performEdits()
+     */
+    public final UndoEdit apply(IDocument document, int style) throws MalformedTreeException, BadLocationException {
+        try {
+            TextEditProcessor processor= new TextEditProcessor(document, this, style);
+            return processor.performEdits();
+        } finally {
+            // disconnect from text edit processor
+            fParent= null;
+        }
+    }
+
+    /**
+     * Applies the edit tree rooted by this edit to the given document. This
+     * method is a convenience method for <code>apply(document, CREATE_UNDO | UPDATE_REGIONS)
+     * </code>
+     *
+     * @param document the document to which to apply this edit
+     * @return a undo edit, if <code>CREATE_UNDO</code> is specified. Otherwise
+     *  <code>null</code> is returned.
+     * @exception MalformedTreeException is thrown if the tree isn't
+     *  in a valid state. This exception is thrown before any edit
+     *  is executed. So the document is still in its original state.
+     * @exception BadLocationException is thrown if one of the edits
+     *  in the tree can't be executed. The state of the document is
+     *  undefined if this exception is thrown.
+     * @see #apply(IDocument, int)
+     */
+    public final UndoEdit apply(IDocument document) throws MalformedTreeException, BadLocationException {
+        return apply(document, CREATE_UNDO | UPDATE_REGIONS);
+    }
+
+    UndoEdit dispatchPerformEdits(TextEditProcessor processor) throws BadLocationException {
+        return processor.executeDo();
+    }
+
+    void dispatchCheckIntegrity(TextEditProcessor processor) throws MalformedTreeException {
+        processor.checkIntegrityDo();
+    }
+
+    //---- internal state accessors ----------------------------------------------------------
+
+    void internalSetParent(TextEdit parent) {
+        if (parent !is null)
+            Assert.isTrue(fParent is null);
+        fParent= parent;
+    }
+
+    void internalSetOffset(int offset) {
+        Assert.isTrue(offset >= 0);
+        fOffset= offset;
+    }
+
+    void internalSetLength(int length) {
+        Assert.isTrue(length >= 0);
+        fLength= length;
+    }
+
+    List internalGetChildren() {
+        return fChildren;
+    }
+
+    void internalSetChildren(List children) {
+        fChildren= children;
+    }
+
+    void internalAdd(TextEdit child) throws MalformedTreeException {
+        child.aboutToBeAdded(this);
+        if (child.isDeleted())
+            throw new MalformedTreeException(this, child, TextEditMessages.getString("TextEdit.deleted_edit")); //$NON-NLS-1$
+        if (!covers(child))
+            throw new MalformedTreeException(this, child, TextEditMessages.getString("TextEdit.range_outside")); //$NON-NLS-1$
+        if (fChildren is null) {
+            fChildren= new ArrayList(2);
+        }
+        int index= computeInsertionIndex(child);
+        fChildren.add(index, child);
+        child.internalSetParent(this);
+    }
+
+    private int computeInsertionIndex(TextEdit edit) throws MalformedTreeException {
+        int size= fChildren.size();
+        if (size is 0)
+            return 0;
+        int lastIndex= size - 1;
+        TextEdit last= (TextEdit)fChildren.get(lastIndex);
+        if (last.getExclusiveEnd() <= edit.getOffset())
+            return size;
+        try {
+
+            int index= Collections.binarySearch(fChildren, edit, INSERTION_COMPARATOR);
+
+            if (index < 0)
+                // edit is not in fChildren
+                return -index - 1;
+
+            // edit is already in fChildren
+            // make sure that multiple insertion points at the same offset are inserted last.
+            while (index < lastIndex && INSERTION_COMPARATOR.compare(fChildren.get(index), fChildren.get(index + 1)) is 0)
+                index++;
+
+            return index + 1;
+
+        } catch(MalformedTreeException e) {
+            e.setParent(this);
+            throw e;
+        }
+    }
+
+    //---- Offset & Length updating -------------------------------------------------
+
+    /**
+     * Adjusts the edits offset according to the given
+     * delta. This method doesn't update any children.
+     *
+     * @param delta the delta of the text replace operation
+     */
+    void adjustOffset(int delta) {
+        if (isDeleted())
+            return;
+        fOffset+= delta;
+        Assert.isTrue(fOffset >= 0);
+    }
+
+    /**
+     * Adjusts the edits length according to the given
+     * delta. This method doesn't update any children.
+     *
+     * @param delta the delta of the text replace operation
+     */
+    void adjustLength(int delta) {
+        if (isDeleted())
+            return;
+        fLength+= delta;
+        Assert.isTrue(fLength >= 0);
+    }
+
+    /**
+     * Marks the edit as deleted. This method doesn't update
+     * any children.
+     */
+    void markAsDeleted() {
+        fOffset= DELETED_VALUE;
+        fLength= DELETED_VALUE;
+    }
+
+    //---- Edit processing ----------------------------------------------
+
+    /**
+     * Traverses the edit tree to perform the consistency check.
+     *
+     * @param processor the text edit processor
+     * @param document the document to be manipulated
+     * @param sourceEdits the list of source edits to be performed before
+     *  the actual tree is applied to the document
+     *
+     * @return the number of indirect move or copy target edit children
+     */
+    int traverseConsistencyCheck(TextEditProcessor processor, IDocument document, List sourceEdits) {
+        int result= 0;
+        if (fChildren !is null) {
+            for (int i= fChildren.size() - 1; i >= 0; i--) {
+                TextEdit child= (TextEdit)fChildren.get(i);
+                result= Math.max(result, child.traverseConsistencyCheck(processor, document, sourceEdits));
+            }
+        }
+        if (processor.considerEdit(this)) {
+            performConsistencyCheck(processor, document);
+        }
+        return result;
+    }
+
+    void performConsistencyCheck(TextEditProcessor processor, IDocument document) {
+    }
+
+    void traverseSourceComputation(TextEditProcessor processor, IDocument document) {
+    }
+
+    void performSourceComputation(TextEditProcessor processor, IDocument document) {
+    }
+
+    int traverseDocumentUpdating(TextEditProcessor processor, IDocument document) throws BadLocationException {
+        int delta= 0;
+        if (fChildren !is null) {
+            for (int i= fChildren.size() - 1; i >= 0; i--) {
+                TextEdit child= (TextEdit)fChildren.get(i);
+                delta+= child.traverseDocumentUpdating(processor, document);
+                childDocumentUpdated();
+            }
+        }
+        if (processor.considerEdit(this)) {
+            if (delta !is 0)
+                adjustLength(delta);
+            int r= performDocumentUpdating(document);
+            if (r !is 0)
+                adjustLength(r);
+            delta+= r;
+        }
+        return delta;
+    }
+
+    /**
+     * Hook method called when the document updating of a child edit has been
+     * completed. When a client calls {@link #apply(IDocument)} or
+     * {@link #apply(IDocument, int)} this method is called
+     * {@link #getChildrenSize()} times.
+     * <p>
+     * May be overridden by subclasses of {@link MultiTextEdit}.
+     *
+     * @since 3.1
+     */
+    protected void childDocumentUpdated() {
+    }
+
+    abstract int performDocumentUpdating(IDocument document) throws BadLocationException;
+
+    int traverseRegionUpdating(TextEditProcessor processor, IDocument document, int accumulatedDelta, bool delete) {
+        performRegionUpdating(accumulatedDelta, delete);
+        if (fChildren !is null) {
+            bool childDelete= delete || deleteChildren();
+            for (Iterator iter= fChildren.iterator(); iter.hasNext();) {
+                TextEdit child= (TextEdit)iter.next();
+                accumulatedDelta= child.traverseRegionUpdating(processor, document, accumulatedDelta, childDelete);
+                childRegionUpdated();
+            }
+        }
+        return accumulatedDelta + fDelta;
+    }
+
+    /**
+     * Hook method called when the region updating of a child edit has been
+     * completed. When a client calls {@link #apply(IDocument)} this method is
+     * called {@link #getChildrenSize()} times. When calling
+     * {@link #apply(IDocument, int)} this method is called
+     * {@link #getChildrenSize()} times, when the style parameter contains the
+     * {@link #UPDATE_REGIONS} flag.
+     * <p>
+     * May be overridden by subclasses of {@link MultiTextEdit}.
+     *
+     * @since 3.1
+     */
+    protected void childRegionUpdated() {
+    }
+
+    void performRegionUpdating(int accumulatedDelta, bool delete) {
+        if (delete)
+            markAsDeleted();
+        else
+            adjustOffset(accumulatedDelta);
+    }
+
+    abstract bool deleteChildren();
+
+    void internalMoveTree(int delta) {
+        adjustOffset(delta);
+        if (fChildren !is null) {
+            for (Iterator iter= fChildren.iterator(); iter.hasNext();) {
+                ((TextEdit)iter.next()).internalMoveTree(delta);
+            }
+        }
+    }
+
+    void deleteTree() {
+        markAsDeleted();
+        if (fChildren !is null) {
+            for (Iterator iter= fChildren.iterator(); iter.hasNext();) {
+                TextEdit child= (TextEdit)iter.next();
+                child.deleteTree();
+            }
+        }
+    }
+}
+