projects/dwt2: org.eclipse.text/src/org/eclipse/jface/text/TreeLineTracker.d annotate

annotate org.eclipse.text/src/org/eclipse/jface/text/TreeLineTracker.d @ 15:c4b1a29263fc

Successful build of org.eclipse.text

author	Frank Benoit <benoit@tionex.de>
date	Sun, 15 Mar 2009 19:51:07 +0100
parents	5feec68b4556
children	6f068362a363

rev	line source
12 bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1 /*******************************************************************************
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	2 * Copyright (c) 2005, 2006 IBM Corporation and others.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	3 * All rights reserved. This program and the accompanying materials
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	4 * are made available under the terms of the Eclipse Public License v1.0
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	5 * which accompanies this distribution, and is available at
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	6 * http://www.eclipse.org/legal/epl-v10.html
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	7 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	8 * Contributors:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	9 * IBM Corporation - initial API and implementation
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	10 * Port to the D programming language:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	11 * Frank Benoit <benoit@tionex.de>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	12 *******************************************************************************/
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	13 module org.eclipse.jface.text.TreeLineTracker;
14 5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	14 import org.eclipse.jface.text.IRepairableDocument;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	15 import org.eclipse.jface.text.AbstractDocument;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	16 import org.eclipse.jface.text.IDocumentPartitionerExtension3;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	17 import org.eclipse.jface.text.ConfigurableLineTracker;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	18 import org.eclipse.jface.text.IRegion;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	19 import org.eclipse.jface.text.TypedRegion;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	20 import org.eclipse.jface.text.IDocumentExtension2;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	21 import org.eclipse.jface.text.TypedPosition;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	22 import org.eclipse.jface.text.RewriteSessionEditProcessor;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	23 import org.eclipse.jface.text.SlaveDocumentEvent;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	24 import org.eclipse.jface.text.IDocumentExtension3;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	25 import org.eclipse.jface.text.IDocumentListener;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	26 import org.eclipse.jface.text.ISynchronizable;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	27 import org.eclipse.jface.text.DocumentEvent;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	28 import org.eclipse.jface.text.Position;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	29 import org.eclipse.jface.text.IRepairableDocumentExtension;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	30 import org.eclipse.jface.text.DocumentRewriteSessionType;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	31 import org.eclipse.jface.text.Region;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	32 import org.eclipse.jface.text.IDocumentExtension4;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	33 import org.eclipse.jface.text.BadLocationException;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	34 import org.eclipse.jface.text.TextMessages;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	35 import org.eclipse.jface.text.IDocumentPartitioningListenerExtension2;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	36 import org.eclipse.jface.text.IDocumentInformationMappingExtension;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	37 import org.eclipse.jface.text.IDocumentPartitioningListenerExtension;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	38 import org.eclipse.jface.text.ITextStore;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	39 import org.eclipse.jface.text.IDocumentPartitionerExtension;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	40 import org.eclipse.jface.text.DocumentRewriteSession;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	41 import org.eclipse.jface.text.IPositionUpdater;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	42 import org.eclipse.jface.text.ISlaveDocumentManagerExtension;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	43 import org.eclipse.jface.text.ILineTracker;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	44 import org.eclipse.jface.text.ListLineTracker;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	45 import org.eclipse.jface.text.IDocumentRewriteSessionListener;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	46 import org.eclipse.jface.text.IDocumentInformationMapping;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	47 import org.eclipse.jface.text.AbstractLineTracker;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	48 import org.eclipse.jface.text.DefaultLineTracker;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	49 import org.eclipse.jface.text.BadPositionCategoryException;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	50 import org.eclipse.jface.text.BadPartitioningException;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	51 import org.eclipse.jface.text.SequentialRewriteTextStore;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	52 import org.eclipse.jface.text.IDocumentInformationMappingExtension2;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	53 import org.eclipse.jface.text.DocumentPartitioningChangedEvent;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	54 import org.eclipse.jface.text.FindReplaceDocumentAdapter;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	55 import org.eclipse.jface.text.TextUtilities;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	56 import org.eclipse.jface.text.ISlaveDocumentManager;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	57 import org.eclipse.jface.text.IDocument;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	58 import org.eclipse.jface.text.ILineTrackerExtension;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	59 import org.eclipse.jface.text.IDocumentPartitioner;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	60 import org.eclipse.jface.text.GapTextStore;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	61 import org.eclipse.jface.text.Document;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	62 import org.eclipse.jface.text.IDocumentExtension;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	63 import org.eclipse.jface.text.IDocumentPartitioningListener;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	64 import org.eclipse.jface.text.CopyOnWriteTextStore;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	65 import org.eclipse.jface.text.DefaultPositionUpdater;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	66 import org.eclipse.jface.text.Line;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	67 import org.eclipse.jface.text.DocumentRewriteSessionEvent;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	68 import org.eclipse.jface.text.IDocumentPartitionerExtension2;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	69 import org.eclipse.jface.text.ITypedRegion;
12 bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	70
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	71
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	72 import java.lang.all;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	73 import java.util.ListIterator;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	74 import java.util.Arrays;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	75 import java.util.List;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	76 import java.util.LinkedList;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	77 import java.util.Set;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	78 import tango.text.convert.Format;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	79 import tango.core.Exception;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	80
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	81 import org.eclipse.core.runtime.Assert;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	82 import org.eclipse.jface.text.AbstractLineTracker;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	83
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	84 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	85 * Abstract implementation of <code>ILineTracker</code>. It lets the definition of line
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	86 * delimiters to subclasses. Assuming that '\n' is the only line delimiter, this abstract
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	87 * implementation defines the following line scheme:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	88 * <ul>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	89 * <li> "" -> [0,0]
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	90 * <li> "a" -> [0,1]
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	91 * <li> "\n" -> [0,1], [1,0]
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	92 * <li> "a\n" -> [0,2], [2,0]
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	93 * <li> "a\nb" -> [0,2], [2,1]
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	94 * <li> "a\nbc\n" -> [0,2], [2,3], [5,0]
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	95 * </ul>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	96 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	97 * This class must be subclassed.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	98 * </p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	99 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	100 * <strong>Performance:</strong> The query operations perform in <i>O(log n)</i> where <var>n</var>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	101 * is the number of lines in the document. The modification operations roughly perform in <i>O(l *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	102 * log n)</i> where <var>n</var> is the number of lines in the document and <var>l</var> is the
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	103 * sum of the number of removed, added or modified lines.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	104 * </p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	105 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	106 * @since 3.2
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	107 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	108 abstract class TreeLineTracker : ILineTracker {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	109 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	110 * Differential Balanced Binary Tree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	111 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	112 * Assumption: lines cannot overlap => there exists a total ordering of the lines by their offset,
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	113 * which is the same as the ordering by line number
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	114 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	115 * Base idea: store lines in a binary search tree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	116 * - the key is the line number / line offset
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	117 * -> lookup_line is O(log n)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	118 * -> lookup_offset is O(log n)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	119 * - a change in a line somewhere will change any succeeding line numbers / line offsets
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	120 * -> replace is O(n)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	121 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	122 * Differential tree: instead of storing the key (line number, line offset) directly, every node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	123 * stores the difference between its key and its parent's key
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	124 * - the sort key is still the line number / line offset, but it remains "virtual"
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	125 * - inserting a node (a line) really increases the virtual key of all succeeding nodes (lines), but this
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	126 * fact will not be realized in the key information encoded in the nodes.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	127 * -> any change only affects the nodes in the node's parent chain, although more bookkeeping
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	128 * has to be done when changing a node or balancing the tree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	129 * -> replace is O(log n)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	130 * -> line offsets and line numbers have to be computed when walking the tree from the root /
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	131 * from a node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	132 * -> still O(log n)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	133 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	134 * The balancing algorithm chosen does not depend on the differential tree property. An AVL tree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	135 * implementation has been chosen for simplicity.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	136 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	137
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	138 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	139 * Turns assertions on/off. Don't make this a a debug option for performance reasons - this way
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	140 * the compiler can optimize the asserts away.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	141 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	142 private static const bool ASSERT= false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	143
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	144 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	145 * The empty delimiter of the last line. The last line and only the last line must have this
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	146 * zero-length delimiter.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	147 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	148 private static const String NO_DELIM= ""; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	149
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	150 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	151 * A node represents one line. Its character and line offsets are 0-based and relative to the
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	152 * subtree covered by the node. All nodes under the left subtree represent lines before, all
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	153 * nodes under the right subtree lines after the current node.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	154 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	155 private static final class Node {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	156 this(int length, String delimiter) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	157 this.length= length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	158 this.delimiter= delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	159 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	160 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	161 * The line index in this node's line tree, or equivalently, the number of lines in the left
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	162 * subtree.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	163 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	164 int line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	165 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	166 * The line offset in this node's line tree, or equivalently, the number of characters in
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	167 * the left subtree.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	168 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	169 int offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	170 /** The number of characters in this line. */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	171 int length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	172 /** The line delimiter of this line, needed to answer the delimiter query. */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	173 String delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	174 /** The parent node, <code>null</code> if this is the root node. */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	175 Node parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	176 /** The left subtree, possibly <code>null</code>. */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	177 Node left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	178 /** The right subtree, possibly <code>null</code>. */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	179 Node right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	180 /** The balance factor. */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	181 byte balance;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	182
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	183 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	184 * @see java.lang.Object#toString()
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	185 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	186 public final override String toString() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	187 String bal;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	188 switch (balance) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	189 case 0:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	190 bal= "="; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	191 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	192 case 1:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	193 bal= "+"; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	194 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	195 case 2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	196 bal= "++"; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	197 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	198 case -1:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	199 bal= "-"; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	200 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	201 case -2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	202 bal= "--"; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	203 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	204 default:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	205 bal= Byte.toString(balance);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	206 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	207 return Format("[{}+{}+{}\|{}\|{}]", offset, pureLength(), delimiter.length, line, bal ); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$ //$NON-NLS-6$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	208 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	209
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	210 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	211 * Returns the pure (without the line delimiter) length of this line.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	212 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	213 * @return the pure line length
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	214 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	215 int pureLength() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	216 return length - delimiter.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	217 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	218 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	219
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	220 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	221 * The root node of the tree, never <code>null</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	222 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	223 private Node fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	224
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	225 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	226 * Creates a new line tracker.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	227 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	228 protected this() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	229 fRoot= new Node(0, NO_DELIM);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	230 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	231
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	232 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	233 * Package visible constructor for creating a tree tracker from a list tracker.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	234 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	235 * @param tracker
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	236 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	237 this(ListLineTracker tracker) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	238 fRoot= new Node(0, NO_DELIM);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	239 final List lines= tracker.getLines();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	240 final int n= lines.size();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	241 if (n is 0)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	242 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	243
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	244 Line line= cast(Line) lines.get(0);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	245 String delim= line.delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	246 if (delim is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	247 delim= NO_DELIM;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	248 int length= line.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	249 fRoot= new Node(length, delim);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	250 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	251
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	252 for (int i= 1; i < n; i++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	253 line= cast(Line) lines.get(i);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	254 delim= line.delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	255 if (delim is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	256 delim= NO_DELIM;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	257 length= line.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	258 node= insertAfter(node, length, delim);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	259 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	260
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	261 if (node.delimiter !is NO_DELIM)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	262 insertAfter(node, 0, NO_DELIM);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	263
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	264 if (ASSERT) checkTree();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	265 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	266
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	267 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	268 * Returns the node (line) including a certain offset. If the offset is between two
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	269 * lines, the line starting at <code>offset</code> is returned.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	270 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	271 * This means that for offsets smaller than the length, the following holds:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	272 * </p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	273 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	274 * <code>line.offset <= offset < line.offset + offset.length</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	275 * </p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	276 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	277 * If <code>offset</code> is the document length, then this is true:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	278 * </p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	279 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	280 * <code>offset= line.offset + line.length</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	281 * </p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	282 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	283 * @param offset a document offset
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	284 * @return the line starting at or containing <code>offset</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	285 * @throws BadLocationException if the offset is invalid
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	286 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	287 private Node nodeByOffset(int offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	288 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	289 * Works for any binary search tree.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	290 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	291 int remaining= offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	292 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	293 int line= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	294
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	295 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	296 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	297 fail(offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	298
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	299 if (remaining < node.offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	300 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	301 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	302 remaining -= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	303 line+= node.line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	304 if (remaining < node.length
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	305 \|\| remaining is node.length && node.right is null) { // last line
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	306 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	307 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	308 remaining -= node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	309 line ++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	310 node= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	311 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	312 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	313
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	314 return node;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	315 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	316 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	317 * Returns the line number for the given offset. If the offset is between two lines, the line
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	318 * starting at <code>offset</code> is returned. The last line is returned if
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	319 * <code>offset</code> is equal to the document length.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	320 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	321 * @param offset a document offset
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	322 * @return the line number starting at or containing <code>offset</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	323 * @throws BadLocationException if the offset is invalid
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	324 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	325 private int lineByOffset(int offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	326 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	327 * Works for any binary search tree.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	328 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	329 int remaining= offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	330 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	331 int line= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	332
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	333 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	334 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	335 fail(offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	336
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	337 if (remaining < node.offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	338 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	339 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	340 remaining -= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	341 line+= node.line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	342 if (remaining < node.length \|\| remaining is node.length && node.right is null) // last line
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	343 return line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	344
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	345 remaining -= node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	346 line ++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	347 node= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	348 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	349 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	350 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	351
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	352 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	353 * Returns the node (line) with the given line number. Note that the last line is always
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	354 * incomplete, i.e. has the {@link #NO_DELIM} delimiter.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	355 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	356 * @param line a line number
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	357 * @return the line with the given line number
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	358 * @throws BadLocationException if the line is invalid
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	359 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	360 private Node nodeByLine(int line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	361 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	362 * Works for any binary search tree.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	363 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	364 int remaining= line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	365 int offset= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	366 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	367
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	368 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	369 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	370 fail(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	371
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	372 if (remaining is node.line)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	373 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	374 if (remaining < node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	375 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	376 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	377 remaining -= node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	378 offset += node.offset + node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	379 node= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	380 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	381 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	382
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	383 return node;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	384 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	385
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	386 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	387 * Returns the offset for the given line number. Note that the
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	388 * last line is always incomplete, i.e. has the {@link #NO_DELIM} delimiter.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	389 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	390 * @param line a line number
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	391 * @return the line offset with the given line number
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	392 * @throws BadLocationException if the line is invalid
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	393 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	394 private int offsetByLine(int line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	395 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	396 * Works for any binary search tree.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	397 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	398 int remaining= line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	399 int offset= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	400 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	401
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	402 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	403 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	404 fail(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	405
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	406 if (remaining is node.line)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	407 return offset + node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	408
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	409 if (remaining < node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	410 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	411 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	412 remaining -= node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	413 offset += node.offset + node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	414 node= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	415 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	416 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	417 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	418
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	419 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	420 * Left rotation - the given node is rotated down, its right child is rotated up, taking the
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	421 * previous structural position of <code>node</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	422 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	423 * @param node the node to rotate around
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	424 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	425 private void rotateLeft(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	426 if (ASSERT) Assert.isNotNull(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	427 Node child= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	428 if (ASSERT) Assert.isNotNull(child);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	429 bool leftChild= node.parent is null \|\| node is node.parent.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	430
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	431 // restructure
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	432 setChild(node.parent, child, leftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	433
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	434 setChild(node, child.left, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	435 setChild(child, node, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	436
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	437 // update relative info
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	438 // child becomes the new parent, its line and offset counts increase as the former parent
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	439 // moves under child's left subtree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	440 child.line += node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	441 child.offset += node.offset + node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	442 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	443
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	444 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	445 * Right rotation - the given node is rotated down, its left child is rotated up, taking the
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	446 * previous structural position of <code>node</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	447 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	448 * @param node the node to rotate around
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	449 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	450 private void rotateRight(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	451 if (ASSERT) Assert.isNotNull(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	452 Node child= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	453 if (ASSERT) Assert.isNotNull(child);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	454 bool leftChild= node.parent is null \|\| node is node.parent.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	455
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	456 setChild(node.parent, child, leftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	457
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	458 setChild(node, child.right, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	459 setChild(child, node, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	460
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	461 // update relative info
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	462 // node loses its left subtree, except for what it keeps in its new subtree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	463 // this is exactly the amount in child
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	464 node.line -= child.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	465 node.offset -= child.offset + child.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	466 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	467
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	468 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	469 * Helper method for moving a child, ensuring that parent pointers are set correctly.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	470 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	471 * @param parent the new parent of <code>child</code>, <code>null</code> to replace the
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	472 * root node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	473 * @param child the new child of <code>parent</code>, may be <code>null</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	474 * @param isLeftChild <code>true</code> if <code>child</code> shall become
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	475 * <code>parent</code>'s left child, <code>false</code> if it shall become
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	476 * <code>parent</code>'s right child
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	477 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	478 private void setChild(Node parent, Node child, bool isLeftChild) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	479 if (parent is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	480 if (child is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	481 fRoot= new Node(0, NO_DELIM);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	482 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	483 fRoot= child;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	484 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	485 if (isLeftChild)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	486 parent.left= child;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	487 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	488 parent.right= child;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	489 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	490 if (child !is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	491 child.parent= parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	492 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	493
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	494 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	495 * A left rotation around <code>parent</code>, whose structural position is replaced by
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	496 * <code>node</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	497 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	498 * @param node the node moving up and left
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	499 * @param parent the node moving left and down
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	500 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	501 private void singleLeftRotation(Node node, Node parent) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	502 rotateLeft(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	503 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	504 parent.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	505 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	506
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	507 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	508 * A right rotation around <code>parent</code>, whose structural position is replaced by
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	509 * <code>node</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	510 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	511 * @param node the node moving up and right
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	512 * @param parent the node moving right and down
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	513 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	514 private void singleRightRotation(Node node, Node parent) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	515 rotateRight(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	516 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	517 parent.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	518 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	519
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	520 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	521 * A double left rotation, first rotating right around <code>node</code>, then left around
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	522 * <code>parent</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	523 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	524 * @param node the node that will be rotated right
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	525 * @param parent the node moving left and down
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	526 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	527 private void rightLeftRotation(Node node, Node parent) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	528 Node child= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	529 rotateRight(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	530 rotateLeft(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	531 if (child.balance is 1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	532 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	533 parent.balance= -1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	534 child.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	535 } else if (child.balance is 0) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	536 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	537 parent.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	538 } else if (child.balance is -1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	539 node.balance= 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	540 parent.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	541 child.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	542 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	543 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	544
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	545 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	546 * A double right rotation, first rotating left around <code>node</code>, then right around
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	547 * <code>parent</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	548 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	549 * @param node the node that will be rotated left
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	550 * @param parent the node moving right and down
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	551 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	552 private void leftRightRotation(Node node, Node parent) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	553 Node child= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	554 rotateLeft(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	555 rotateRight(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	556 if (child.balance is -1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	557 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	558 parent.balance= 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	559 child.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	560 } else if (child.balance is 0) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	561 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	562 parent.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	563 } else if (child.balance is 1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	564 node.balance= -1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	565 parent.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	566 child.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	567 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	568 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	569
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	570 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	571 * Inserts a line with the given length and delimiter after <code>node</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	572 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	573 * @param node the predecessor of the inserted node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	574 * @param length the line length of the inserted node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	575 * @param delimiter the delimiter of the inserted node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	576 * @return the inserted node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	577 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	578 private Node insertAfter(Node node, int length, String delimiter) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	579 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	580 * An insertion really shifts the key of all succeeding nodes. Hence we insert the added node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	581 * between node and the successor of node. The added node becomes either the right child
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	582 * of the predecessor node, or the left child of the successor node.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	583 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	584 Node added= new Node(length, delimiter);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	585
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	586 if (node.right is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	587 setChild(node, added, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	588 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	589 setChild(successorDown(node.right), added, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	590
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	591 // parent chain update
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	592 updateParentChain(added, length, 1);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	593 updateParentBalanceAfterInsertion(added);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	594
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	595 return added;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	596 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	597
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	598 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	599 * Updates the balance information in the parent chain of node until it reaches the root or
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	600 * finds a node whose balance violates the AVL constraint, which is the re-balanced.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	601 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	602 * @param node the child of the first node that needs balance updating
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	603 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	604 private void updateParentBalanceAfterInsertion(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	605 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	606 while (parent !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	607 if (node is parent.left)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	608 parent.balance--;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	609 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	610 parent.balance++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	611
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	612 switch (parent.balance) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	613 case 1:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	614 case -1:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	615 node= parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	616 parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	617 continue;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	618 case -2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	619 rebalanceAfterInsertionLeft(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	620 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	621 case 2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	622 rebalanceAfterInsertionRight(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	623 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	624 case 0:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	625 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	626 default:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	627 if (ASSERT)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	628 Assert.isTrue(false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	629 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	630 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	631 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	632 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	633
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	634 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	635 * Re-balances a node whose parent has a double positive balance.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	636 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	637 * @param node the node to re-balance
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	638 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	639 private void rebalanceAfterInsertionRight(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	640 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	641 if (node.balance is 1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	642 singleLeftRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	643 } else if (node.balance is -1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	644 rightLeftRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	645 } else if (ASSERT) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	646 Assert.isTrue(false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	647 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	648 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	649
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	650 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	651 * Re-balances a node whose parent has a double negative balance.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	652 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	653 * @param node the node to re-balance
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	654 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	655 private void rebalanceAfterInsertionLeft(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	656 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	657 if (node.balance is -1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	658 singleRightRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	659 } else if (node.balance is 1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	660 leftRightRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	661 } else if (ASSERT) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	662 Assert.isTrue(false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	663 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	664 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	665
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	666 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	667 * @see org.eclipse.jface.text.ILineTracker#replace(int, int, java.lang.String)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	668 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	669 public final void replace(int offset, int length, String text) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	670 if (ASSERT) checkTree();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	671
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	672 // Inlined nodeByOffset as we need both node and offset
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	673 int remaining= offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	674 Node first= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	675 int firstNodeOffset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	676
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	677 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	678 if (first is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	679 fail(offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	680
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	681 if (remaining < first.offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	682 first= first.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	683 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	684 remaining -= first.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	685 if (remaining < first.length
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	686 \|\| remaining is first.length && first.right is null) { // last line
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	687 firstNodeOffset= offset - remaining;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	688 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	689 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	690 remaining -= first.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	691 first= first.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	692 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	693 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	694 // Inline nodeByOffset end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	695 if (ASSERT) Assert.isTrue(first !is null);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	696
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	697 Node last;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	698 if (offset + length < firstNodeOffset + first.length)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	699 last= first;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	700 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	701 last= nodeByOffset(offset + length);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	702 if (ASSERT) Assert.isTrue(last !is null);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	703
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	704 int firstLineDelta= firstNodeOffset + first.length - offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	705 if (first is last)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	706 replaceInternal(first, text, length, firstLineDelta);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	707 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	708 replaceFromTo(first, last, text, length, firstLineDelta);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	709
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	710 if (ASSERT) checkTree();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	711 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	712
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	713 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	714 * Replace happening inside a single line.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	715 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	716 * @param node the affected node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	717 * @param text the added text
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	718 * @param length the replace length, < <code>firstLineDelta</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	719 * @param firstLineDelta the number of characters from the replacement offset to the end of
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	720 * <code>node</code> > <code>length</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	721 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	722 private void replaceInternal(Node node, String text, int length, int firstLineDelta) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	723 // 1) modification on a single line
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	724
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	725 AbstractLineTracker_DelimiterInfo info= text is null ? null : nextDelimiterInfo(text, 0);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	726
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	727 if (info is null \|\| info.delimiter is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	728 // a) trivial case: insert into a single node, no line mangling
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	729 int added= text is null ? 0 : text.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	730 updateLength(node, added - length);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	731 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	732 // b) more lines to add between two chunks of the first node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	733 // remember what we split off the first line
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	734 int remainder= firstLineDelta - length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	735 String remDelim= node.delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	736
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	737 // join the first line with the first added
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	738 int consumed= info.delimiterIndex + info.delimiterLength;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	739 int delta= consumed - firstLineDelta;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	740 updateLength(node, delta);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	741 node.delimiter= info.delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	742
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	743 // Inline addlines start
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	744 info= nextDelimiterInfo(text, consumed);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	745 while (info !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	746 int lineLen= info.delimiterIndex - consumed + info.delimiterLength;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	747 node= insertAfter(node, lineLen, info.delimiter);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	748 consumed += lineLen;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	749 info= nextDelimiterInfo(text, consumed);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	750 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	751 // Inline addlines end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	752
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	753 // add remaining chunk merged with last (incomplete) additional line
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	754 insertAfter(node, remainder + text.length - consumed, remDelim);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	755 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	756 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	757
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	758 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	759 * Replace spanning from one node to another.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	760 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	761 * @param node the first affected node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	762 * @param last the last affected node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	763 * @param text the added text
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	764 * @param length the replace length, >= <code>firstLineDelta</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	765 * @param firstLineDelta the number of characters removed from the replacement offset to the end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	766 * of <code>node</code>, <= <code>length</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	767 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	768 private void replaceFromTo(Node node, Node last, String text, int length, int firstLineDelta) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	769 // 2) modification covers several lines
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	770
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	771 // delete intermediate nodes
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	772 // TODO could be further optimized: replace intermediate lines with intermediate added lines
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	773 // to reduce re-balancing
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	774 Node successor_= successor(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	775 while (successor_ !is last) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	776 length -= successor_.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	777 Node toDelete= successor_;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	778 successor_= successor(successor_);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	779 updateLength(toDelete, -toDelete.length);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	780 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	781
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	782 AbstractLineTracker_DelimiterInfo info= text is null ? null : nextDelimiterInfo(text, 0);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	783
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	784 if (info is null \|\| info.delimiter is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	785 int added= text is null ? 0 : text.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	786
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	787 // join the two lines if there are no lines added
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	788 join(node, last, added - length);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	789
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	790 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	791
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	792 // join the first line with the first added
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	793 int consumed= info.delimiterIndex + info.delimiterLength;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	794 updateLength(node, consumed - firstLineDelta);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	795 node.delimiter= info.delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	796 length -= firstLineDelta;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	797
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	798 // Inline addLines start
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	799 info= nextDelimiterInfo(text, consumed);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	800 while (info !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	801 int lineLen= info.delimiterIndex - consumed + info.delimiterLength;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	802 node= insertAfter(node, lineLen, info.delimiter);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	803 consumed += lineLen;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	804 info= nextDelimiterInfo(text, consumed);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	805 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	806 // Inline addLines end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	807
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	808 updateLength(last, text.length - consumed - length);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	809 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	810 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	811
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	812 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	813 * Joins two consecutive node lines, additionally adjusting the resulting length of the combined
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	814 * line by <code>delta</code>. The first node gets deleted.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	815 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	816 * @param one the first node to join
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	817 * @param two the second node to join
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	818 * @param delta the delta to apply to the remaining single node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	819 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	820 private void join(Node one, Node two, int delta) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	821 int oneLength= one.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	822 updateLength(one, -oneLength);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	823 updateLength(two, oneLength + delta);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	824 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	825
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	826 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	827 * Adjusts the length of a node by <code>delta</code>, also adjusting the parent chain of
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	828 * <code>node</code>. If the node's length becomes zero and is not the last (incomplete)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	829 * node, it is deleted after the update.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	830 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	831 * @param node the node to adjust
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	832 * @param delta the character delta to add to the node's length
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	833 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	834 private void updateLength(Node node, int delta) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	835 if (ASSERT) Assert.isTrue(node.length + delta >= 0);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	836
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	837 // update the node itself
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	838 node.length += delta;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	839
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	840 // check deletion
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	841 int lineDelta;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	842 bool delete__= node.length is 0 && node.delimiter !is NO_DELIM;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	843 if (delete__)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	844 lineDelta= -1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	845 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	846 lineDelta= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	847
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	848 // update parent chain
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	849 if (delta !is 0 \|\| lineDelta !is 0)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	850 updateParentChain(node, delta, lineDelta);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	851
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	852 if (delete__)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	853 delete_(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	854 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	855
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	856 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	857 * Updates the differential indices following the parent chain. All nodes from
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	858 * <code>from.parent</code> to the root are updated.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	859 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	860 * @param node the child of the first node to update
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	861 * @param deltaLength the character delta
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	862 * @param deltaLines the line delta
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	863 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	864 private void updateParentChain(Node node, int deltaLength, int deltaLines) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	865 updateParentChain(node, null, deltaLength, deltaLines);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	866 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	867
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	868 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	869 * Updates the differential indices following the parent chain. All nodes from
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	870 * <code>from.parent</code> to <code>to</code> (exclusive) are updated.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	871 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	872 * @param from the child of the first node to update
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	873 * @param to the first node not to update
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	874 * @param deltaLength the character delta
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	875 * @param deltaLines the line delta
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	876 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	877 private void updateParentChain(Node from, Node to, int deltaLength, int deltaLines) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	878 Node parent= from.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	879 while (parent !is to) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	880 // only update node if update comes from left subtree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	881 if (from is parent.left) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	882 parent.offset += deltaLength;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	883 parent.line += deltaLines;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	884 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	885 from= parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	886 parent= from.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	887 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	888 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	889
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	890 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	891 * Deletes a node from the tree, re-balancing it if necessary. The differential indices in the
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	892 * node's parent chain have to be updated in advance to calling this method. Generally, don't
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	893 * call <code>delete</code> directly, but call
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	894 * {@link #updateLength(Node, int) update_length(node, -node.length)} to properly remove a
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	895 * node.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	896 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	897 * @param node the node to delete.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	898 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	899 private void delete_(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	900 if (ASSERT) Assert.isTrue(node !is null);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	901 if (ASSERT) Assert.isTrue(node.length is 0);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	902
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	903 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	904 Node toUpdate; // the parent of the node that lost a child
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	905 bool lostLeftChild;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	906 bool isLeftChild= parent is null \|\| node is parent.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	907
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	908 if (node.left is null \|\| node.right is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	909 // 1) node has one child at max - replace parent's pointer with the only child
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	910 // also handles the trivial case of no children
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	911 Node replacement= node.left is null ? node.right : node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	912 setChild(parent, replacement, isLeftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	913 toUpdate= parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	914 lostLeftChild= isLeftChild;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	915 // no updates to do - subtrees stay as they are
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	916 } else if (node.right.left is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	917 // 2a) node's right child has no left child - replace node with right child, giving node's
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	918 // left subtree to the right child
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	919 Node replacement= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	920 setChild(parent, replacement, isLeftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	921 setChild(replacement, node.left, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	922 replacement.line= node.line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	923 replacement.offset= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	924 replacement.balance= node.balance;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	925 toUpdate= replacement;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	926 lostLeftChild= false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	927 // } else if (node.left.right is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	928 // // 2b) symmetric case
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	929 // Node replacement= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	930 // set_child(parent, replacement, isLeftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	931 // set_child(replacement, node.right, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	932 // replacement.balance= node.balance;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	933 // toUpdate= replacement;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	934 // lostLeftChild= true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	935 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	936 // 3) hard case - replace node with its successor
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	937 Node successor_= successor(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	938
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	939 // successor exists (otherwise node would not have right child, case 1)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	940 if (ASSERT) Assert.isNotNull(successor_);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	941 // successor has no left child (a left child would be the real successor of node)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	942 if (ASSERT) Assert.isTrue(successor_.left is null);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	943 if (ASSERT) Assert.isTrue(successor_.line is 0);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	944 // successor is the left child of its parent (otherwise parent would be smaller and
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	945 // hence the real successor)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	946 if (ASSERT) Assert.isTrue(successor_ is successor_.parent.left);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	947 // successor is not a child of node (would have been covered by 2a)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	948 if (ASSERT) Assert.isTrue(successor_.parent !is node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	949
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	950 toUpdate= successor_.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	951 lostLeftChild= true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	952
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	953 // update relative indices
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	954 updateParentChain(successor_, node, -successor_.length, -1);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	955
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	956 // delete successor from its current place - like 1)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	957 setChild(toUpdate, successor_.right, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	958
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	959 // move node's subtrees to its successor
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	960 setChild(successor_, node.right, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	961 setChild(successor_, node.left, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	962
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	963 // replace node by successor in its parent
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	964 setChild(parent, successor_, isLeftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	965
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	966 // update the successor
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	967 successor_.line= node.line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	968 successor_.offset= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	969 successor_.balance= node.balance;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	970 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	971
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	972 updateParentBalanceAfterDeletion(toUpdate, lostLeftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	973 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	974
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	975 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	976 * Updates the balance information in the parent chain of node.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	977 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	978 * @param node the first node that needs balance updating
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	979 * @param wasLeftChild <code>true</code> if the deletion happened on <code>node</code>'s
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	980 * left subtree, <code>false</code> if it occurred on <code>node</code>'s right
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	981 * subtree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	982 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	983 private void updateParentBalanceAfterDeletion(Node node, bool wasLeftChild) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	984 while (node !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	985 if (wasLeftChild)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	986 node.balance++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	987 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	988 node.balance--;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	989
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	990 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	991 if (parent !is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	992 wasLeftChild= node is parent.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	993
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	994 switch (node.balance) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	995 case 1:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	996 case -1:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	997 return; // done, no tree change
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	998 case -2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	999 if (rebalanceAfterDeletionRight(node.left))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1000 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1001 break; // propagate up
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1002 case 2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1003 if (rebalanceAfterDeletionLeft(node.right))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1004 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1005 break; // propagate up
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1006 case 0:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1007 break; // propagate up
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1008 default:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1009 if (ASSERT)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1010 Assert.isTrue(false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1011 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1012
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1013 node= parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1014 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1015 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1016
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1017 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1018 * Re-balances a node whose parent has a double positive balance.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1019 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1020 * @param node the node to re-balance
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1021 * @return <code>true</code> if the re-balancement leaves the height at
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1022 * <code>node.parent</code> constant, <code>false</code> if the height changed
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1023 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1024 private bool rebalanceAfterDeletionLeft(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1025 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1026 if (node.balance is 1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1027 singleLeftRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1028 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1029 } else if (node.balance is -1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1030 rightLeftRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1031 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1032 } else if (node.balance is 0) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1033 rotateLeft(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1034 node.balance= -1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1035 parent.balance= 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1036 return true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1037 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1038 if (ASSERT) Assert.isTrue(false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1039 return true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1040 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1041 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1042
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1043 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1044 * Re-balances a node whose parent has a double negative balance.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1045 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1046 * @param node the node to re-balance
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1047 * @return <code>true</code> if the re-balancement leaves the height at
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1048 * <code>node.parent</code> constant, <code>false</code> if the height changed
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1049 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1050 private bool rebalanceAfterDeletionRight(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1051 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1052 if (node.balance is -1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1053 singleRightRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1054 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1055 } else if (node.balance is 1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1056 leftRightRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1057 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1058 } else if (node.balance is 0) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1059 rotateRight(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1060 node.balance= 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1061 parent.balance= -1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1062 return true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1063 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1064 if (ASSERT) Assert.isTrue(false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1065 return true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1066 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1067 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1068
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1069 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1070 * Returns the successor of a node, <code>null</code> if node is the last node.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1071 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1072 * @param node a node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1073 * @return the successor of <code>node</code>, <code>null</code> if there is none
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1074 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1075 private Node successor(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1076 if (node.right !is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1077 return successorDown(node.right);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1078
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1079 return successorUp(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1080 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1081
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1082 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1083 * Searches the successor of <code>node</code> in its parent chain.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1084 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1085 * @param node a node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1086 * @return the first node in <code>node</code>'s parent chain that is reached from its left
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1087 * subtree, <code>null</code> if there is none
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1088 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1089 private Node successorUp(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1090 Node child= node;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1091 Node parent= child.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1092 while (parent !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1093 if (child is parent.left)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1094 return parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1095 child= parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1096 parent= child.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1097 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1098 if (ASSERT) Assert.isTrue(node.delimiter is NO_DELIM);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1099 return null;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1100 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1101
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1102 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1103 * Searches the left-most node in a given subtree.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1104 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1105 * @param node a node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1106 * @return the left-most node in the given subtree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1107 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1108 private Node successorDown(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1109 Node child= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1110 while (child !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1111 node= child;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1112 child= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1113 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1114 return node;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1115 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1116
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1117 /* miscellaneous */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1118
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1119 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1120 * Throws an exception.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1121 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1122 * @param offset the illegal character or line offset that caused the exception
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1123 * @throws BadLocationException always
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1124 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1125 private void fail(int offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1126 throw new BadLocationException();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1127 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1128
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1129 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1130 * Returns the information about the first delimiter found in the given
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1131 * text starting at the given offset.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1132 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1133 * @param text the text to be searched
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1134 * @param offset the offset in the given text
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1135 * @return the information of the first found delimiter or <code>null</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1136 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1137 protected abstract AbstractLineTracker_DelimiterInfo nextDelimiterInfo(String text, int offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1138
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1139 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1140 * @see org.eclipse.jface.text.ILineTracker#getLineDelimiter(int)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1141 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1142 public final String getLineDelimiter(int line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1143 Node node= nodeByLine(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1144 return node.delimiter is NO_DELIM ? null : node.delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1145 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1146
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1147 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1148 * @see org.eclipse.jface.text.ILineTracker#computeNumberOfLines(java.lang.String)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1149 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1150 public final int computeNumberOfLines(String text) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1151 int count= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1152 int start= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1153 AbstractLineTracker_DelimiterInfo delimiterInfo= nextDelimiterInfo(text, start);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1154 while (delimiterInfo !is null && delimiterInfo.delimiterIndex > -1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1155 ++count;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1156 start= delimiterInfo.delimiterIndex + delimiterInfo.delimiterLength;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1157 delimiterInfo= nextDelimiterInfo(text, start);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1158 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1159 return count;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1160 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1161
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1162 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1163 * @see org.eclipse.jface.text.ILineTracker#getNumberOfLines()
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1164 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1165 public final int getNumberOfLines() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1166 // TODO track separately?
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1167 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1168 int lines= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1169 while (node !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1170 lines += node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1171 node= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1172 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1173 return lines;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1174 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1175
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1176 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1177 * @see org.eclipse.jface.text.ILineTracker#getNumberOfLines(int, int)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1178 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1179 public final int getNumberOfLines(int offset, int length) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1180 if (length is 0)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1181 return 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1182
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1183 int startLine= lineByOffset(offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1184 int endLine= lineByOffset(offset + length);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1185
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1186 return endLine - startLine + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1187 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1188
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1189 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1190 * @see org.eclipse.jface.text.ILineTracker#getLineOffset(int)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1191 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1192 public final int getLineOffset(int line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1193 return offsetByLine(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1194 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1195
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1196 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1197 * @see org.eclipse.jface.text.ILineTracker#getLineLength(int)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1198 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1199 public final int getLineLength(int line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1200 Node node= nodeByLine(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1201 return node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1202 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1203
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1204 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1205 * @see org.eclipse.jface.text.ILineTracker#getLineNumberOfOffset(int)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1206 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1207 public final int getLineNumberOfOffset(int offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1208 return lineByOffset(offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1209 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1210
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1211 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1212 * @see org.eclipse.jface.text.ILineTracker#getLineInformationOfOffset(int)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1213 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1214 public final IRegion getLineInformationOfOffset(int offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1215 // Inline nodeByOffset start as we need both node and offset
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1216 int remaining= offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1217 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1218 int lineOffset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1219
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1220 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1221 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1222 fail(offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1223
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1224 if (remaining < node.offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1225 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1226 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1227 remaining -= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1228 if (remaining < node.length
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1229 \|\| remaining is node.length && node.right is null) { // last line
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1230 lineOffset= offset - remaining;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1231 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1232 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1233 remaining -= node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1234 node= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1235 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1236 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1237 // Inline nodeByOffset end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1238 return new Region(lineOffset, node.pureLength());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1239 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1240
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1241 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1242 * @see org.eclipse.jface.text.ILineTracker#getLineInformation(int)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1243 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1244 public final IRegion getLineInformation(int line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1245 try {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1246 // Inline nodeByLine start
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1247 int remaining= line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1248 int offset= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1249 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1250
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1251 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1252 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1253 fail(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1254
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1255 if (remaining is node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1256 offset += node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1257 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1258 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1259 if (remaining < node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1260 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1261 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1262 remaining -= node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1263 offset += node.offset + node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1264 node= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1265 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1266 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1267 // Inline nodeByLine end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1268 return new Region(offset, node.pureLength());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1269 } catch (BadLocationException x) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1270 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1271 * FIXME: this really strange behavior is mandated by the previous line tracker
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1272 * implementation and included here for compatibility. See
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1273 * LineTrackerTest3#testFunnyLastLineCompatibility().
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1274 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1275 if (line > 0 && line is getNumberOfLines()) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1276 line= line - 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1277 // Inline nodeByLine start
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1278 int remaining= line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1279 int offset= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1280 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1281
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1282 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1283 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1284 fail(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1285
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1286 if (remaining is node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1287 offset+= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1288 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1289 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1290 if (remaining < node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1291 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1292 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1293 remaining -= node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1294 offset += node.offset + node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1295 node= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1296 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1297 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1298 Node last= node;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1299 // Inline nodeByLine end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1300 if (last.length > 0)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1301 return new Region(offset + last.length, 0);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1302 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1303 throw x;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1304 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1305 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1306
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1307 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1308 * @see org.eclipse.jface.text.ILineTracker#set(java.lang.String)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1309 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1310 public final void set(String text) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1311 fRoot= new Node(0, NO_DELIM);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1312 try {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1313 replace(0, 0, text);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1314 } catch (BadLocationException x) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1315 throw new AssertException(__FILE__,__LINE__);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1316 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1317 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1318
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1319 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1320 * @see java.lang.Object#toString()
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1321 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1322 public override String toString() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1323 int depth= computeDepth(fRoot);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1324 int WIDTH= 30;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1325 int leaves= cast(int) Math.pow( cast(real)2, cast(uint) depth - 1);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1326 int width= WIDTH * leaves;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1327 String empty= "."; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1328
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1329 List roots= new LinkedList();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1330 roots.add(fRoot);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1331 StringBuffer buf= new StringBuffer((width + 1) * depth);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1332 int nodes= 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1333 int indents= leaves;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1334 char[] space= new char[leaves * WIDTH / 2];
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1335 Arrays.fill(space, ' ');
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1336 for(int d= 0; d < depth; d++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1337 // compute indent
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1338 indents /= 2;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1339 int spaces= Math.max(0, indents * WIDTH - WIDTH / 2);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1340 // print nodes
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1341 for (ListIterator it= roots.listIterator(); it.hasNext();) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1342 // pad before
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1343 buf.append(space[ 0 .. spaces]);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1344
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1345 Node node= cast(Node) it.next();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1346 String box;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1347 // replace the node with its children
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1348 if (node is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1349 it.add(cast(Object)null);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1350 box= empty;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1351 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1352 it.set(node.left);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1353 it.add(node.right);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1354 box= node.toString();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1355 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1356
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1357 // draw the node, pad to WIDTH
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1358 int pad_left= (WIDTH - box.length() + 1) / 2;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1359 int pad_right= WIDTH - box.length() - pad_left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1360 buf.append(space[ 0 .. pad_left]);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1361 buf.append(box);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1362 buf.append(space[ 0 .. pad_right]);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1363
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1364 // pad after
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1365 buf.append(space[ 0 .. spaces]);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1366 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1367
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1368 buf.append('\n');
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1369 nodes *= 2;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1370 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1371
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1372 return buf.toString();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1373 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1374
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1375 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1376 * Recursively computes the depth of the tree. Only used by {@link #toString()}.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1377 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1378 * @param root the subtree to compute the depth of, may be <code>null</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1379 * @return the depth of the given tree, 0 if it is <code>null</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1380 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1381 private byte computeDepth(Node root) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1382 if (root is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1383 return 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1384
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1385 return cast(byte) (Math.max(computeDepth(root.left), computeDepth(root.right)) + 1);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1386 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1387
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1388 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1389 * Debug-only method that checks the tree structure and the differential offsets.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1390 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1391 private void checkTree() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1392 checkTreeStructure(fRoot);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1393
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1394 try {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1395 checkTreeOffsets(nodeByOffset(0), [0, 0], null);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1396 } catch (BadLocationException x) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1397 throw new AssertException(__FILE__,__LINE__);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1398 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1399 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1400
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1401 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1402 * Debug-only method that validates the tree structure below <code>node</code>. I.e. it
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1403 * checks whether all parent/child pointers are consistent and whether the AVL balance
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1404 * information is correct.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1405 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1406 * @param node the node to validate
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1407 * @return the depth of the tree under <code>node</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1408 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1409 private byte checkTreeStructure(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1410 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1411 return 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1412
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1413 byte leftDepth= checkTreeStructure(node.left);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1414 byte rightDepth= checkTreeStructure(node.right);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1415 Assert.isTrue(node.balance is rightDepth - leftDepth);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1416 Assert.isTrue(node.left is null \|\| node.left.parent is node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1417 Assert.isTrue(node.right is null \|\| node.right.parent is node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1418
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1419 return cast(byte) (Math.max(rightDepth, leftDepth) + 1);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1420 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1421
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1422 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1423 * Debug-only method that checks the differential offsets of the tree, starting at
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1424 * <code>node</code> and continuing until <code>last</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1425 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1426 * @param node the first <code>Node</code> to check, may be <code>null</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1427 * @param offLen an array of length 2, with <code>offLen[0]</code> the expected offset of
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1428 * <code>node</code> and <code>offLen[1]</code> the expected line of
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1429 * <code>node</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1430 * @param last the last <code>Node</code> to check, may be <code>null</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1431 * @return an <code>int[]</code> of length 2, with the first element being the character
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1432 * length of <code>node</code>'s subtree, and the second element the number of lines
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1433 * in <code>node</code>'s subtree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1434 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1435 private int[] checkTreeOffsets(Node node, int[] offLen, Node last) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1436 if (node is last)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1437 return offLen;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1438
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1439 Assert.isTrue(node.offset is offLen[0]);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1440 Assert.isTrue(node.line is offLen[1]);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1441
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1442 if (node.right !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1443 int[] result= checkTreeOffsets(successorDown(node.right), new int[2], node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1444 offLen[0] += result[0];
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1445 offLen[1] += result[1];
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1446 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1447
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1448 offLen[0] += node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1449 offLen[1]++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1450 return checkTreeOffsets(node.parent, offLen, last);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1451 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1452 }

Mercurial > projects > dwt2

annotate org.eclipse.text/src/org/eclipse/jface/text/TreeLineTracker.d @ 15:c4b1a29263fc