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