Mercurial > projects > dwt-addons

comparison dwtx/jface/text/TreeLineTracker.d @ 129:eb30df5ca28b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added JFace Text sources
author Frank Benoit <benoit@tionex.de>
date Sat, 23 Aug 2008 19:10:48 +0200
parents
children c4fb132a086c
comparison
equal deleted inserted replaced
128:8df1d4193877 129:eb30df5ca28b
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, &lt; <code>firstLineDelta</code>
658 * @param firstLineDelta the number of characters from the replacement offset to the end of
659 * <code>node</code> &gt; <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, &gt;= <code>firstLineDelta</code>
704 * @param firstLineDelta the number of characters removed from the replacement offset to the end
705 * of <code>node</code>, &lt;= <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 }