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

annotate org.eclipse.text/src/org/eclipse/jface/text/TreeLineTracker.d @ 14:5feec68b4556

First run of automatic package imports

author	Frank Benoit <benoit@tionex.de>
date	Sat, 14 Mar 2009 18:41:58 +0100
parents	bc29606a740c
children	c4b1a29263fc

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.Assert;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	48 import org.eclipse.jface.text.AbstractLineTracker;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	49 import org.eclipse.jface.text.DefaultLineTracker;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	50 import org.eclipse.jface.text.BadPositionCategoryException;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	51 import org.eclipse.jface.text.BadPartitioningException;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	52 import org.eclipse.jface.text.SequentialRewriteTextStore;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	53 import org.eclipse.jface.text.IDocumentInformationMappingExtension2;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	54 import org.eclipse.jface.text.DocumentPartitioningChangedEvent;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	55 import org.eclipse.jface.text.FindReplaceDocumentAdapter;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	56 import org.eclipse.jface.text.TextUtilities;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	57 import org.eclipse.jface.text.ISlaveDocumentManager;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	58 import org.eclipse.jface.text.IDocument;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	59 import org.eclipse.jface.text.ILineTrackerExtension;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	60 import org.eclipse.jface.text.IDocumentPartitioner;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	61 import org.eclipse.jface.text.GapTextStore;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	62 import org.eclipse.jface.text.Document;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	63 import org.eclipse.jface.text.IDocumentExtension;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	64 import org.eclipse.jface.text.IDocumentPartitioningListener;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	65 import org.eclipse.jface.text.CopyOnWriteTextStore;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	66 import org.eclipse.jface.text.DefaultPositionUpdater;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	67 import org.eclipse.jface.text.Line;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	68 import org.eclipse.jface.text.DocumentRewriteSessionEvent;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	69 import org.eclipse.jface.text.IDocumentPartitionerExtension2;
5feec68b4556 First run of automatic package imports Frank Benoit <benoit@tionex.de> parents: 12 diff changeset	70 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	71
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	72
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	73 import java.lang.all;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	74 import java.util.ListIterator;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	75 import java.util.Arrays;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	76 import java.util.List;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	77 import java.util.LinkedList;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	78 import java.util.Set;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	79 import tango.text.convert.Format;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	80 import tango.core.Exception;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	81
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	82 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	83 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	84
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	85 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	86 * 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	87 * 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	88 * 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	89 * <ul>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	90 * <li> "" -> [0,0]
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	91 * <li> "a" -> [0,1]
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	92 * <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	93 * <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	94 * <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	95 * <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	96 * </ul>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	97 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	98 * This class must be subclassed.
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 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	101 * <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	102 * 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	103 * 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	104 * 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	105 * </p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	106 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	107 * @since 3.2
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	108 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	109 abstract class TreeLineTracker : ILineTracker {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	110 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	111 * Differential Balanced Binary Tree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	112 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	113 * 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	114 * 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	115 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	116 * 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	117 * - 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	118 * -> 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	119 * -> 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	120 * - 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	121 * -> replace is O(n)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	122 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	123 * 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	124 * 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	125 * - 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	126 * - 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	127 * 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	128 * -> 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	129 * 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	130 * -> replace is O(log n)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	131 * -> 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	132 * from a node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	133 * -> still O(log n)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	134 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	135 * 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	136 * 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	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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	140 * 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	141 * 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	142 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	143 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	144
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	145 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	146 * 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	147 * zero-length delimiter.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	148 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	149 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	150
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	151 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	152 * 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	153 * 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	154 * 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	155 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	156 private static final class Node {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	157 this(int length, String delimiter) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	158 this.length= length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	159 this.delimiter= delimiter;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	162 * 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	163 * subtree.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	164 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	165 int line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	166 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	167 * 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	168 * the left subtree.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	169 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	170 int offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	171 /** 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	172 int length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	173 /** 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	174 String delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	175 /** 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	176 Node parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	177 /** 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	178 Node left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	179 /** 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	180 Node right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	181 /** The balance factor. */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	182 byte balance;
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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	185 * @see java.lang.Object#toString()
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	186 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	187 public final override String toString() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	188 String bal;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	189 switch (balance) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	190 case 0:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	191 bal= "="; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	192 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	193 case 1:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	194 bal= "+"; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	195 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	196 case 2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	197 bal= "++"; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	198 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	199 case -1:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	200 bal= "-"; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	201 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	202 case -2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	203 bal= "--"; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	204 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	205 default:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	206 bal= Byte.toString(balance);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	207 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	208 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	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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	212 * 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	213 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	214 * @return the pure line length
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	215 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	216 int pureLength() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	217 return length - delimiter.length;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	222 * 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	223 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	224 private Node fRoot;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	227 * Creates a new line tracker.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	228 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	229 protected this() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	230 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	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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	234 * 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	235 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	236 * @param tracker
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	237 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	238 this(ListLineTracker tracker) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	239 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	240 final List lines= tracker.getLines();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	241 final int n= lines.size();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	242 if (n is 0)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	243 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	244
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	245 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	246 String delim= line.delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	247 if (delim is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	248 delim= NO_DELIM;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	249 int length= line.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	250 fRoot= new Node(length, delim);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	251 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	252
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	253 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	254 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	255 delim= line.delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	256 if (delim is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	257 delim= NO_DELIM;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	258 length= line.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	259 node= insertAfter(node, length, delim);
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
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	262 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	263 insertAfter(node, 0, NO_DELIM);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	264
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	265 if (ASSERT) checkTree();
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	269 * 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	270 * 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	271 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	272 * 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	273 * </p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	274 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	275 * <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	276 * </p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	277 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	278 * 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	279 * </p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	280 * <p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	281 * <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	282 * </p>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	283 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	284 * @param offset a document offset
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	285 * @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	286 * @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	287 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	288 private Node nodeByOffset(int offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	289 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	290 * 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	291 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	292 int remaining= offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	293 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	294 int line= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	295
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	296 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	297 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	298 fail(offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	299
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	300 if (remaining < node.offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	301 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	302 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	303 remaining -= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	304 line+= node.line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	305 if (remaining < node.length
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	306 \|\| 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	307 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	308 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	309 remaining -= node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	310 line ++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	311 node= node.right;
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
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	315 return node;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	318 * 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	319 * 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	320 * <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	321 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	322 * @param offset a document offset
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	323 * @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	324 * @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	325 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	326 private int lineByOffset(int offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	327 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	328 * 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	329 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	330 int remaining= offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	331 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	332 int line= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	333
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	334 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	335 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	336 fail(offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	337
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	338 if (remaining < node.offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	339 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	340 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	341 remaining -= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	342 line+= node.line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	343 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	344 return line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	345
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	346 remaining -= node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	347 line ++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	348 node= node.right;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	354 * 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	355 * 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	356 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	357 * @param line a line number
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	358 * @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	359 * @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	360 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	361 private Node nodeByLine(int line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	362 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	363 * 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	364 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	365 int remaining= line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	366 int offset= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	367 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	368
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	369 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	370 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	371 fail(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	372
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	373 if (remaining is node.line)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	374 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	375 if (remaining < node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	376 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	377 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	378 remaining -= node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	379 offset += node.offset + node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	380 node= node.right;
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
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	384 return node;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	388 * 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	389 * 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	390 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	391 * @param line a line number
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	392 * @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	393 * @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	394 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	395 private int offsetByLine(int line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	396 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	397 * 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	398 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	399 int remaining= line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	400 int offset= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	401 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	402
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	403 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	404 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	405 fail(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	406
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	407 if (remaining is node.line)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	408 return offset + node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	409
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	410 if (remaining < node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	411 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	412 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	413 remaining -= node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	414 offset += node.offset + node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	415 node= node.right;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	421 * 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	422 * 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	423 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	424 * @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	425 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	426 private void rotateLeft(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	427 if (ASSERT) Assert.isNotNull(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	428 Node child= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	429 if (ASSERT) Assert.isNotNull(child);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	430 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	431
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	432 // restructure
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	433 setChild(node.parent, child, leftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	434
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	435 setChild(node, child.left, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	436 setChild(child, node, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	437
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	438 // update relative info
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	439 // 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	440 // 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	441 child.line += node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	442 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	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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	446 * 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	447 * 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	448 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	449 * @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	450 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	451 private void rotateRight(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	452 if (ASSERT) Assert.isNotNull(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	453 Node child= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	454 if (ASSERT) Assert.isNotNull(child);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	455 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	456
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	457 setChild(node.parent, child, leftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	458
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	459 setChild(node, child.right, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	460 setChild(child, node, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	461
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	462 // update relative info
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	463 // 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	464 // 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	465 node.line -= child.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	466 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	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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	470 * 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	471 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	472 * @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	473 * root node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	474 * @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	475 * @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	476 * <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	477 * <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	478 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	479 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	480 if (parent is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	481 if (child is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	482 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	483 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	484 fRoot= child;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	485 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	486 if (isLeftChild)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	487 parent.left= child;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	488 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	489 parent.right= child;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	490 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	491 if (child !is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	492 child.parent= parent;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	496 * 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	497 * <code>node</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	498 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	499 * @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	500 * @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	501 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	502 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	503 rotateLeft(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	504 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	505 parent.balance= 0;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	509 * 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	510 * <code>node</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	511 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	512 * @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	513 * @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	514 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	515 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	516 rotateRight(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	517 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	518 parent.balance= 0;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	522 * 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	523 * <code>parent</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	524 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	525 * @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	526 * @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	527 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	528 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	529 Node child= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	530 rotateRight(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	531 rotateLeft(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	532 if (child.balance is 1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	533 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	534 parent.balance= -1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	535 child.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	536 } 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	537 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	538 parent.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	539 } 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	540 node.balance= 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	541 parent.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	542 child.balance= 0;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	547 * 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	548 * <code>parent</code>.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	549 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	550 * @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	551 * @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	552 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	553 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	554 Node child= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	555 rotateLeft(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	556 rotateRight(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	557 if (child.balance is -1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	558 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	559 parent.balance= 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	560 child.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	561 } 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	562 node.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	563 parent.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	564 } 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	565 node.balance= -1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	566 parent.balance= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	567 child.balance= 0;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	572 * 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	573 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	574 * @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	575 * @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	576 * @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	577 * @return the inserted node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	578 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	579 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	580 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	581 * 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	582 * 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	583 * 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	584 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	585 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	586
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	587 if (node.right is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	588 setChild(node, added, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	589 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	590 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	591
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	592 // parent chain update
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	593 updateParentChain(added, length, 1);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	594 updateParentBalanceAfterInsertion(added);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	595
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	596 return added;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	600 * 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	601 * 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	602 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	603 * @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	604 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	605 private void updateParentBalanceAfterInsertion(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	606 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	607 while (parent !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	608 if (node is parent.left)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	609 parent.balance--;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	610 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	611 parent.balance++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	612
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	613 switch (parent.balance) {
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 case -1:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	616 node= parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	617 parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	618 continue;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	619 case -2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	620 rebalanceAfterInsertionLeft(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	621 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	622 case 2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	623 rebalanceAfterInsertionRight(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	624 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	625 case 0:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	626 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	627 default:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	628 if (ASSERT)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	629 Assert.isTrue(false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	630 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	631 return;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	636 * 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	637 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	638 * @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	639 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	640 private void rebalanceAfterInsertionRight(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	641 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	642 if (node.balance is 1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	643 singleLeftRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	644 } 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	645 rightLeftRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	646 } else if (ASSERT) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	647 Assert.isTrue(false);
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	652 * 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	653 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	654 * @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	655 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	656 private void rebalanceAfterInsertionLeft(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	657 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	658 if (node.balance is -1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	659 singleRightRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	660 } 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	661 leftRightRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	662 } else if (ASSERT) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	663 Assert.isTrue(false);
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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	668 * @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	669 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	670 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	671 if (ASSERT) checkTree();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	672
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	673 // 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	674 int remaining= offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	675 Node first= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	676 int firstNodeOffset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	677
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	678 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	679 if (first is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	680 fail(offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	681
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	682 if (remaining < first.offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	683 first= first.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	684 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	685 remaining -= first.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	686 if (remaining < first.length
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	687 \|\| 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	688 firstNodeOffset= offset - remaining;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	689 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	690 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	691 remaining -= first.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	692 first= first.right;
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 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	695 // Inline nodeByOffset end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	696 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	697
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	698 Node last;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	699 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	700 last= first;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	701 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	702 last= nodeByOffset(offset + length);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	703 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	704
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	705 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	706 if (first is last)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	707 replaceInternal(first, text, length, firstLineDelta);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	708 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	709 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	710
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	711 if (ASSERT) checkTree();
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	715 * 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	716 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	717 * @param node the affected node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	718 * @param text the added text
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	719 * @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	720 * @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	721 * <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	722 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	723 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	724 // 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	725
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	726 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	727
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	728 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	729 // 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	730 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	731 updateLength(node, added - length);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	732 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	733 // 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	734 // 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	735 int remainder= firstLineDelta - length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	736 String remDelim= node.delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	737
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	738 // 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	739 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	740 int delta= consumed - firstLineDelta;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	741 updateLength(node, delta);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	742 node.delimiter= info.delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	743
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	744 // Inline addlines start
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	745 info= nextDelimiterInfo(text, consumed);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	746 while (info !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	747 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	748 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	749 consumed += lineLen;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	750 info= nextDelimiterInfo(text, consumed);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	751 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	752 // Inline addlines end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	753
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	754 // 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	755 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	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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	760 * 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	761 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	762 * @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	763 * @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	764 * @param text the added text
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	765 * @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	766 * @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	767 * 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	768 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	769 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	770 // 2) modification covers several lines
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	771
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	772 // delete intermediate nodes
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	773 // 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	774 // to reduce re-balancing
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	775 Node successor_= successor(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	776 while (successor_ !is last) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	777 length -= successor_.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	778 Node toDelete= successor_;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	779 successor_= successor(successor_);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	780 updateLength(toDelete, -toDelete.length);
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
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	783 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	784
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	785 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	786 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	787
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	788 // 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	789 join(node, last, added - length);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	790
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	791 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	792
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	793 // 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	794 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	795 updateLength(node, consumed - firstLineDelta);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	796 node.delimiter= info.delimiter;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	797 length -= firstLineDelta;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	798
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	799 // Inline addLines start
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	800 info= nextDelimiterInfo(text, consumed);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	801 while (info !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	802 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	803 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	804 consumed += lineLen;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	805 info= nextDelimiterInfo(text, consumed);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	806 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	807 // Inline addLines end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	808
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	809 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	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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	814 * 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	815 * 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	816 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	817 * @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	818 * @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	819 * @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	820 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	821 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	822 int oneLength= one.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	823 updateLength(one, -oneLength);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	824 updateLength(two, oneLength + delta);
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	828 * 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	829 * <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	830 * 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	831 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	832 * @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	833 * @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	834 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	835 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	836 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	837
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	838 // update the node itself
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	839 node.length += delta;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	840
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	841 // check deletion
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	842 int lineDelta;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	843 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	844 if (delete__)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	845 lineDelta= -1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	846 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	847 lineDelta= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	848
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	849 // update parent chain
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	850 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	851 updateParentChain(node, delta, lineDelta);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	852
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	853 if (delete__)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	854 delete_(node);
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	858 * 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	859 * <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	860 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	861 * @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	862 * @param deltaLength the character delta
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	863 * @param deltaLines the line delta
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	864 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	865 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	866 updateParentChain(node, null, deltaLength, deltaLines);
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	870 * 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	871 * <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	872 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	873 * @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	874 * @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	875 * @param deltaLength the character delta
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	876 * @param deltaLines the line delta
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	877 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	878 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	879 Node parent= from.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	880 while (parent !is to) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	881 // 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	882 if (from is parent.left) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	883 parent.offset += deltaLength;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	884 parent.line += deltaLines;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	885 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	886 from= parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	887 parent= from.parent;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	892 * 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	893 * 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	894 * 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	895 * {@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	896 * node.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	897 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	898 * @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	899 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	900 private void delete_(Node node) {
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 !is null);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	902 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	903
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	904 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	905 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	906 bool lostLeftChild;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	907 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	908
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	909 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	910 // 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	911 // 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	912 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	913 setChild(parent, replacement, isLeftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	914 toUpdate= parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	915 lostLeftChild= isLeftChild;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	916 // 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	917 } 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	918 // 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	919 // 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	920 Node replacement= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	921 setChild(parent, replacement, isLeftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	922 setChild(replacement, node.left, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	923 replacement.line= node.line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	924 replacement.offset= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	925 replacement.balance= node.balance;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	926 toUpdate= replacement;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	927 lostLeftChild= false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	928 // } 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	929 // // 2b) symmetric case
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	930 // Node replacement= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	931 // set_child(parent, replacement, isLeftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	932 // 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	933 // replacement.balance= node.balance;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	934 // toUpdate= replacement;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	935 // lostLeftChild= true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	936 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	937 // 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	938 Node successor_= successor(node);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	939
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	940 // 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	941 if (ASSERT) Assert.isNotNull(successor_);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	942 // 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	943 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	944 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	945 // 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	946 // hence the real successor)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	947 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	948 // 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	949 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	950
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	951 toUpdate= successor_.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	952 lostLeftChild= true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	953
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	954 // update relative indices
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	955 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	956
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	957 // 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	958 setChild(toUpdate, successor_.right, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	959
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	960 // 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	961 setChild(successor_, node.right, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	962 setChild(successor_, node.left, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	963
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	964 // 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	965 setChild(parent, successor_, isLeftChild);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	966
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	967 // update the successor
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	968 successor_.line= node.line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	969 successor_.offset= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	970 successor_.balance= node.balance;
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
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	973 updateParentBalanceAfterDeletion(toUpdate, lostLeftChild);
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	977 * 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	978 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	979 * @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	980 * @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	981 * 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	982 * subtree
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	983 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	984 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	985 while (node !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	986 if (wasLeftChild)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	987 node.balance++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	988 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	989 node.balance--;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	990
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	991 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	992 if (parent !is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	993 wasLeftChild= node is parent.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	994
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	995 switch (node.balance) {
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 case -1:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	998 return; // done, no tree change
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	999 case -2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1000 if (rebalanceAfterDeletionRight(node.left))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1001 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1002 break; // propagate up
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1003 case 2:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1004 if (rebalanceAfterDeletionLeft(node.right))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1005 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1006 break; // propagate up
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1007 case 0:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1008 break; // propagate up
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1009 default:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1010 if (ASSERT)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1011 Assert.isTrue(false);
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
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1014 node= parent;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1019 * 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	1020 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1021 * @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	1022 * @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	1023 * <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	1024 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1025 private bool rebalanceAfterDeletionLeft(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1026 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1027 if (node.balance is 1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1028 singleLeftRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1029 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1030 } 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	1031 rightLeftRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1032 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1033 } 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	1034 rotateLeft(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1035 node.balance= -1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1036 parent.balance= 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1037 return true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1038 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1039 if (ASSERT) Assert.isTrue(false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1040 return true;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1045 * 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	1046 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1047 * @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	1048 * @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	1049 * <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	1050 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1051 private bool rebalanceAfterDeletionRight(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1052 Node parent= node.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1053 if (node.balance is -1) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1054 singleRightRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1055 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1056 } 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	1057 leftRightRotation(node, parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1058 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1059 } 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	1060 rotateRight(parent);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1061 node.balance= 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1062 parent.balance= -1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1063 return true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1064 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1065 if (ASSERT) Assert.isTrue(false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1066 return true;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1071 * 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	1072 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1073 * @param node a node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1074 * @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	1075 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1076 private Node successor(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1077 if (node.right !is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1078 return successorDown(node.right);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1079
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1080 return successorUp(node);
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1084 * 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	1085 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1086 * @param node a node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1087 * @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	1088 * 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	1089 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1090 private Node successorUp(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1091 Node child= node;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1092 Node parent= child.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1093 while (parent !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1094 if (child is parent.left)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1095 return parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1096 child= parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1097 parent= child.parent;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1098 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1099 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	1100 return null;
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1104 * 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	1105 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1106 * @param node a node
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1107 * @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	1108 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1109 private Node successorDown(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1110 Node child= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1111 while (child !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1112 node= child;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1113 child= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1114 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1115 return node;
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
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1118 /* miscellaneous */
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1121 * Throws an exception.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1122 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1123 * @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	1124 * @throws BadLocationException always
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1125 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1126 private void fail(int offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1127 throw new BadLocationException();
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1131 * 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	1132 * 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	1133 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1134 * @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	1135 * @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	1136 * @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	1137 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1138 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	1139
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1140 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1141 * @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	1142 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1143 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	1144 Node node= nodeByLine(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1145 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	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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1149 * @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	1150 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1151 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	1152 int count= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1153 int start= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1154 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	1155 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	1156 ++count;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1157 start= delimiterInfo.delimiterIndex + delimiterInfo.delimiterLength;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1158 delimiterInfo= nextDelimiterInfo(text, start);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1159 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1160 return count;
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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1164 * @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	1165 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1166 public final int getNumberOfLines() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1167 // TODO track separately?
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1168 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1169 int lines= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1170 while (node !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1171 lines += node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1172 node= node.right;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1173 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1174 return lines;
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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1178 * @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	1179 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1180 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	1181 if (length is 0)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1182 return 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1183
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1184 int startLine= lineByOffset(offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1185 int endLine= lineByOffset(offset + length);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1186
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1187 return endLine - startLine + 1;
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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1191 * @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	1192 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1193 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	1194 return offsetByLine(line);
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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1198 * @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	1199 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1200 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	1201 Node node= nodeByLine(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1202 return node.length;
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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1206 * @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	1207 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1208 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	1209 return lineByOffset(offset);
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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1213 * @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	1214 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1215 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	1216 // 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	1217 int remaining= offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1218 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1219 int lineOffset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1220
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1221 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1222 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1223 fail(offset);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1224
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1225 if (remaining < node.offset) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1226 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1227 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1228 remaining -= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1229 if (remaining < node.length
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1230 \|\| 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	1231 lineOffset= offset - remaining;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1232 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1233 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1234 remaining -= node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1235 node= node.right;
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 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1238 // Inline nodeByOffset end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1239 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	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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1243 * @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	1244 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1245 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	1246 try {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1247 // Inline nodeByLine start
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1248 int remaining= line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1249 int offset= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1250 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1251
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1252 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1253 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1254 fail(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1255
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1256 if (remaining is node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1257 offset += node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1258 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1259 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1260 if (remaining < node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1261 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1262 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1263 remaining -= node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1264 offset += node.offset + node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1265 node= node.right;
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 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1268 // Inline nodeByLine end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1269 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	1270 } catch (BadLocationException x) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1271 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1272 * 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	1273 * 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	1274 * LineTrackerTest3#testFunnyLastLineCompatibility().
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1275 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1276 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	1277 line= line - 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1278 // Inline nodeByLine start
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1279 int remaining= line;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1280 int offset= 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1281 Node node= fRoot;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1282
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1283 while (true) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1284 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1285 fail(line);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1286
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1287 if (remaining is node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1288 offset+= node.offset;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1289 break;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1290 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1291 if (remaining < node.line) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1292 node= node.left;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1293 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1294 remaining -= node.line + 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1295 offset += node.offset + node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1296 node= node.right;
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 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1299 Node last= node;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1300 // Inline nodeByLine end
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1301 if (last.length > 0)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1302 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	1303 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1304 throw x;
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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1309 * @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	1310 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1311 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	1312 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	1313 try {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1314 replace(0, 0, text);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1315 } catch (BadLocationException x) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1316 throw new AssertException(__FILE__,__LINE__);
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 /*
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1321 * @see java.lang.Object#toString()
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1322 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1323 public override String toString() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1324 int depth= computeDepth(fRoot);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1325 int WIDTH= 30;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1326 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	1327 int width= WIDTH * leaves;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1328 String empty= "."; //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1329
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1330 List roots= new LinkedList();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1331 roots.add(fRoot);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1332 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	1333 int nodes= 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1334 int indents= leaves;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1335 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	1336 Arrays.fill(space, ' ');
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1337 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	1338 // compute indent
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1339 indents /= 2;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1340 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	1341 // print nodes
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1342 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	1343 // pad before
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1344 buf.append(space[ 0 .. spaces]);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1345
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1346 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	1347 String box;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1348 // 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	1349 if (node is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1350 it.add(cast(Object)null);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1351 box= empty;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1352 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1353 it.set(node.left);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1354 it.add(node.right);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1355 box= node.toString();
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
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1358 // 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	1359 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	1360 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	1361 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	1362 buf.append(box);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1363 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	1364
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1365 // pad after
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1366 buf.append(space[ 0 .. spaces]);
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
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1369 buf.append('\n');
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1370 nodes *= 2;
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
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1373 return buf.toString();
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1377 * 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	1378 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1379 * @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	1380 * @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	1381 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1382 private byte computeDepth(Node root) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1383 if (root is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1384 return 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1385
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1386 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	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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1390 * 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	1391 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1392 private void checkTree() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1393 checkTreeStructure(fRoot);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1394
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1395 try {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1396 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	1397 } catch (BadLocationException x) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1398 throw new AssertException(__FILE__,__LINE__);
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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1403 * 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	1404 * 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	1405 * information is correct.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1406 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1407 * @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	1408 * @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	1409 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1410 private byte checkTreeStructure(Node node) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1411 if (node is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1412 return 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1413
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1414 byte leftDepth= checkTreeStructure(node.left);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1415 byte rightDepth= checkTreeStructure(node.right);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1416 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	1417 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	1418 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	1419
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1420 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	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 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1424 * 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	1425 * <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	1426 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1427 * @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	1428 * @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	1429 * <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	1430 * <code>node</code>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1431 * @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	1432 * @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	1433 * 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	1434 * 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	1435 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1436 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	1437 if (node is last)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1438 return offLen;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1439
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1440 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	1441 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	1442
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1443 if (node.right !is null) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1444 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	1445 offLen[0] += result[0];
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1446 offLen[1] += result[1];
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
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1449 offLen[0] += node.length;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1450 offLen[1]++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1451 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	1452 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1453 }

Mercurial > projects > dwt2

annotate org.eclipse.text/src/org/eclipse/jface/text/TreeLineTracker.d @ 14:5feec68b4556