Java > Open Source Codes > org > eclipse > jface > text > TreeLineTracker


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags