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