Mercurial > projects > dwt-addons
diff dwtx/jface/text/TreeLineTracker.d @ 140:26688fec6d23
Following dsss compile errors
author | Frank Benoit <benoit@tionex.de> |
---|---|
date | Sun, 24 Aug 2008 03:23:46 +0200 |
parents | 6dcb0baaa031 |
children | 000f9136b8f7 |
line wrap: on
line diff
--- a/dwtx/jface/text/TreeLineTracker.d Sun Aug 24 02:31:41 2008 +0200 +++ b/dwtx/jface/text/TreeLineTracker.d Sun Aug 24 03:23:46 2008 +0200 @@ -185,51 +185,51 @@ * log n)</i> where <var>n</var> is the number of lines in the document and <var>l</var> is the * sum of the number of removed, added or modified lines. * </p> - * + * * @since 3.2 */ abstract class TreeLineTracker : ILineTracker { /* * Differential Balanced Binary Tree - * + * * Assumption: lines cannot overlap => there exists a total ordering of the lines by their offset, * which is the same as the ordering by line number - * + * * Base idea: store lines in a binary search tree * - the key is the line number / line offset * -> lookup_line is O(log n) * -> lookup_offset is O(log n) - * - a change in a line somewhere will change any succeeding line numbers / line offsets + * - a change in a line somewhere will change any succeeding line numbers / line offsets * -> replace is O(n) - * + * * Differential tree: instead of storing the key (line number, line offset) directly, every node * stores the difference between its key and its parent's key * - the sort key is still the line number / line offset, but it remains "virtual" * - inserting a node (a line) really increases the virtual key of all succeeding nodes (lines), but this - * fact will not be realized in the key information encoded in the nodes. + * fact will not be realized in the key information encoded in the nodes. * -> any change only affects the nodes in the node's parent chain, although more bookkeeping - * has to be done when changing a node or balancing the tree + * has to be done when changing a node or balancing the tree * -> replace is O(log n) - * -> line offsets and line numbers have to be computed when walking the tree from the root / + * -> line offsets and line numbers have to be computed when walking the tree from the root / * from a node * -> still O(log n) - * + * * The balancing algorithm chosen does not depend on the differential tree property. An AVL tree * implementation has been chosen for simplicity. */ - + /* * Turns assertions on/off. Don't make this a a debug option for performance reasons - this way * the compiler can optimize the asserts away. */ private static final bool ASSERT= false; - + /** * The empty delimiter of the last line. The last line and only the last line must have this * zero-length delimiter. */ private static final String NO_DELIM= ""; //$NON-NLS-1$ - + /** * A node represents one line. Its character and line offsets are 0-based and relative to the * subtree covered by the node. All nodes under the left subtree represent lines before, all @@ -262,7 +262,7 @@ Node right; /** The balance factor. */ byte balance; - + /* * @see java.lang.Object#toString() */ @@ -292,7 +292,7 @@ /** * Returns the pure (without the line delimiter) length of this line. - * + * * @return the pure line length */ int pureLength() { @@ -310,10 +310,10 @@ */ protected this() { } - + /** * Package visible constructor for creating a tree tracker from a list tracker. - * + * * @param tracker */ this(ListLineTracker tracker) { @@ -321,7 +321,7 @@ final int n= lines.size(); if (n is 0) return; - + Line line= cast(Line) lines.get(0); String delim= line.delimiter; if (delim is null) @@ -329,7 +329,7 @@ int length= line.length; fRoot= new Node(length, delim); Node node= fRoot; - + for (int i= 1; i < n; i++) { line= cast(Line) lines.get(i); delim= line.delimiter; @@ -338,11 +338,11 @@ length= line.length; node= insertAfter(node, length, delim); } - + if (node.delimiter !is NO_DELIM) insertAfter(node, 0, NO_DELIM); - - if cast(ASSERT) checkTree(); + + if (ASSERT) checkTree(); } /** @@ -360,7 +360,7 @@ * <p> * <code>offset= line.offset + line.length</code>. * </p> - * + * * @param offset a document offset * @return the line starting at or containing <code>offset</code> * @throws BadLocationException if the offset is invalid @@ -372,11 +372,11 @@ int remaining= offset; Node node= fRoot; int line= 0; - + while (true) { if (node is null) fail(offset); - + if (remaining < node.offset) { node= node.left; } else { @@ -391,14 +391,14 @@ node= node.right; } } - + return node; } /** * Returns the line number for the given offset. If the offset is between two lines, the line * starting at <code>offset</code> is returned. The last line is returned if * <code>offset</code> is equal to the document length. - * + * * @param offset a document offset * @return the line number starting at or containing <code>offset</code> * @throws BadLocationException if the offset is invalid @@ -410,11 +410,11 @@ int remaining= offset; Node node= fRoot; int line= 0; - + while (true) { if (node is null) fail(offset); - + if (remaining < node.offset) { node= node.left; } else { @@ -429,11 +429,11 @@ } } } - + /** * Returns the node (line) with the given line number. Note that the last line is always * incomplete, i.e. has the {@link #NO_DELIM} delimiter. - * + * * @param line a line number * @return the line with the given line number * @throws BadLocationException if the line is invalid @@ -445,11 +445,11 @@ int remaining= line; int offset= 0; Node node= fRoot; - + while (true) { if (node is null) fail(line); - + if (remaining is node.line) break; if (remaining < node.line) { @@ -460,14 +460,14 @@ node= node.right; } } - + return node; } - + /** * Returns the offset for the given line number. Note that the * last line is always incomplete, i.e. has the {@link #NO_DELIM} delimiter. - * + * * @param line a line number * @return the line offset with the given line number * @throws BadLocationException if the line is invalid @@ -479,11 +479,11 @@ int remaining= line; int offset= 0; Node node= fRoot; - + while (true) { if (node is null) fail(line); - + if (remaining is node.line) return offset + node.offset; @@ -496,25 +496,25 @@ } } } - + /** * Left rotation - the given node is rotated down, its right child is rotated up, taking the * previous structural position of <code>node</code>. - * + * * @param node the node to rotate around */ private void rotateLeft(Node node) { - if cast(ASSERT) Assert.isNotNull(node); + if (ASSERT) Assert.isNotNull(node); Node child= node.right; - if cast(ASSERT) Assert.isNotNull(child); + if (ASSERT) Assert.isNotNull(child); bool leftChild= node.parent is null || node is node.parent.left; - + // restructure setChild(node.parent, child, leftChild); - + setChild(node, child.left, false); setChild(child, node, true); - + // update relative info // child becomes the new parent, its line and offset counts increase as the former parent // moves under child's left subtree @@ -525,20 +525,20 @@ /** * Right rotation - the given node is rotated down, its left child is rotated up, taking the * previous structural position of <code>node</code>. - * + * * @param node the node to rotate around */ private void rotateRight(Node node) { - if cast(ASSERT) Assert.isNotNull(node); + if (ASSERT) Assert.isNotNull(node); Node child= node.left; - if cast(ASSERT) Assert.isNotNull(child); + if (ASSERT) Assert.isNotNull(child); bool leftChild= node.parent is null || node is node.parent.left; - + setChild(node.parent, child, leftChild); - + setChild(node, child.right, true); setChild(child, node, false); - + // update relative info // node loses its left subtree, except for what it keeps in its new subtree // this is exactly the amount in child @@ -548,7 +548,7 @@ /** * Helper method for moving a child, ensuring that parent pointers are set correctly. - * + * * @param parent the new parent of <code>child</code>, <code>null</code> to replace the * root node * @param child the new child of <code>parent</code>, may be <code>null</code> @@ -571,11 +571,11 @@ if (child !is null) child.parent= parent; } - + /** * A left rotation around <code>parent</code>, whose structural position is replaced by * <code>node</code>. - * + * * @param node the node moving up and left * @param parent the node moving left and down */ @@ -588,7 +588,7 @@ /** * A right rotation around <code>parent</code>, whose structural position is replaced by * <code>node</code>. - * + * * @param node the node moving up and right * @param parent the node moving right and down */ @@ -601,7 +601,7 @@ /** * A double left rotation, first rotating right around <code>node</code>, then left around * <code>parent</code>. - * + * * @param node the node that will be rotated right * @param parent the node moving left and down */ @@ -626,7 +626,7 @@ /** * A double right rotation, first rotating left around <code>node</code>, then right around * <code>parent</code>. - * + * * @param node the node that will be rotated left * @param parent the node moving right and down */ @@ -650,7 +650,7 @@ /** * Inserts a line with the given length and delimiter after <code>node</code>. - * + * * @param node the predecessor of the inserted node * @param length the line length of the inserted node * @param delimiter the delimiter of the inserted node @@ -658,28 +658,28 @@ */ private Node insertAfter(Node node, int length, String delimiter) { /* - * An insertion really shifts the key of all succeeding nodes. Hence we insert the added node + * An insertion really shifts the key of all succeeding nodes. Hence we insert the added node * between node and the successor of node. The added node becomes either the right child * of the predecessor node, or the left child of the successor node. */ Node added= new Node(length, delimiter); - + if (node.right is null) setChild(node, added, false); else setChild(successorDown(node.right), added, true); - + // parent chain update updateParentChain(added, length, 1); updateParentBalanceAfterInsertion(added); - + return added; } - + /** * Updates the balance information in the parent chain of node until it reaches the root or * finds a node whose balance violates the AVL constraint, which is the re-balanced. - * + * * @param node the child of the first node that needs balance updating */ private void updateParentBalanceAfterInsertion(Node node) { @@ -705,16 +705,16 @@ case 0: break; default: - if cast(ASSERT) + if (ASSERT) Assert.isTrue(false); } return; } } - + /** * Re-balances a node whose parent has a double positive balance. - * + * * @param node the node to re-balance */ private void rebalanceAfterInsertionRight(Node node) { @@ -723,14 +723,14 @@ singleLeftRotation(node, parent); } else if (node.balance is -1) { rightLeftRotation(node, parent); - } else if cast(ASSERT) { + } else if (ASSERT) { Assert.isTrue(false); } } /** * Re-balances a node whose parent has a double negative balance. - * + * * @param node the node to re-balance */ private void rebalanceAfterInsertionLeft(Node node) { @@ -739,7 +739,7 @@ singleRightRotation(node, parent); } else if (node.balance is 1) { leftRightRotation(node, parent); - } else if cast(ASSERT) { + } else if (ASSERT) { Assert.isTrue(false); } } @@ -748,17 +748,17 @@ * @see dwtx.jface.text.ILineTracker#replace(int, int, java.lang.String) */ public final void replace(int offset, int length, String text) { - if cast(ASSERT) checkTree(); - + if (ASSERT) checkTree(); + // Inlined nodeByOffset as we need both node and offset int remaining= offset; Node first= fRoot; final int firstNodeOffset; - + while (true) { if (first is null) fail(offset); - + if (remaining < first.offset) { first= first.left; } else { @@ -773,27 +773,27 @@ } } // Inline nodeByOffset end - if cast(ASSERT) Assert.isTrue(first !is null); - + if (ASSERT) Assert.isTrue(first !is null); + Node last; if (offset + length < firstNodeOffset + first.length) last= first; else last= nodeByOffset(offset + length); - if cast(ASSERT) Assert.isTrue(last !is null); - + if (ASSERT) Assert.isTrue(last !is null); + int firstLineDelta= firstNodeOffset + first.length - offset; if (first is last) replaceInternal(first, text, length, firstLineDelta); else replaceFromTo(first, last, text, length, firstLineDelta); - if cast(ASSERT) checkTree(); + if (ASSERT) checkTree(); } /** * Replace happening inside a single line. - * + * * @param node the affected node * @param text the added text * @param length the replace length, < <code>firstLineDelta</code> @@ -802,7 +802,7 @@ */ private void replaceInternal(Node node, String text, int length, int firstLineDelta) { // 1) modification on a single line - + DelimiterInfo info= text is null ? null : nextDelimiterInfo(text, 0); if (info is null || info.delimiter is null) { @@ -814,14 +814,14 @@ // remember what we split off the first line int remainder= firstLineDelta - length; String remDelim= node.delimiter; - + // join the first line with the first added int consumed= info.delimiterIndex + info.delimiterLength; int delta= consumed - firstLineDelta; updateLength(node, delta); node.delimiter= info.delimiter; - // Inline addlines start + // Inline addlines start info= nextDelimiterInfo(text, consumed); while (info !is null) { int lineLen= info.delimiterIndex - consumed + info.delimiterLength; @@ -829,16 +829,16 @@ consumed += lineLen; info= nextDelimiterInfo(text, consumed); } - // Inline addlines end + // Inline addlines end // add remaining chunk merged with last (incomplete) additional line insertAfter(node, remainder + text.length() - consumed, remDelim); } } - + /** * Replace spanning from one node to another. - * + * * @param node the first affected node * @param last the last affected node * @param text the added text @@ -848,7 +848,7 @@ */ private void replaceFromTo(Node node, Node last, String text, int length, int firstLineDelta) { // 2) modification covers several lines - + // delete intermediate nodes // TODO could be further optimized: replace intermediate lines with intermediate added lines // to reduce re-balancing @@ -867,9 +867,9 @@ // join the two lines if there are no lines added join(node, last, added - length); - + } else { - + // join the first line with the first added int consumed= info.delimiterIndex + info.delimiterLength; updateLength(node, consumed - firstLineDelta); @@ -885,7 +885,7 @@ info= nextDelimiterInfo(text, consumed); } // Inline addLines end - + updateLength(last, text.length() - consumed - length); } } @@ -893,7 +893,7 @@ /** * Joins two consecutive node lines, additionally adjusting the resulting length of the combined * line by <code>delta</code>. The first node gets deleted. - * + * * @param one the first node to join * @param two the second node to join * @param delta the delta to apply to the remaining single node @@ -903,56 +903,56 @@ updateLength(one, -oneLength); updateLength(two, oneLength + delta); } - + /** * Adjusts the length of a node by <code>delta</code>, also adjusting the parent chain of * <code>node</code>. If the node's length becomes zero and is not the last (incomplete) * node, it is deleted after the update. - * + * * @param node the node to adjust * @param delta the character delta to add to the node's length */ private void updateLength(Node node, int delta) { - if cast(ASSERT) Assert.isTrue(node.length + delta >= 0); - + if (ASSERT) Assert.isTrue(node.length + delta >= 0); + // update the node itself node.length += delta; - + // check deletion final int lineDelta; - bool delete= node.length is 0 && node.delimiter !is NO_DELIM; - if (delete) + bool delete__= node.length is 0 && node.delimiter !is NO_DELIM; + if (delete__) lineDelta= -1; else lineDelta= 0; - + // update parent chain if (delta !is 0 || lineDelta !is 0) updateParentChain(node, delta, lineDelta); - - if (delete) - delete(node); + + if (delete__) + delete_(node); } /** * Updates the differential indices following the parent chain. All nodes from * <code>from.parent</code> to the root are updated. - * + * * @param node the child of the first node to update - * @param deltaLength the character delta + * @param deltaLength the character delta * @param deltaLines the line delta */ private void updateParentChain(Node node, int deltaLength, int deltaLines) { updateParentChain(node, null, deltaLength, deltaLines); } - + /** * Updates the differential indices following the parent chain. All nodes from * <code>from.parent</code> to <code>to</code> (exclusive) are updated. - * + * * @param from the child of the first node to update * @param to the first node not to update - * @param deltaLength the character delta + * @param deltaLength the character delta * @param deltaLines the line delta */ private void updateParentChain(Node from, Node to, int deltaLength, int deltaLines) { @@ -967,25 +967,25 @@ parent= from.parent; } } - + /** * Deletes a node from the tree, re-balancing it if necessary. The differential indices in the * node's parent chain have to be updated in advance to calling this method. Generally, don't * call <code>delete</code> directly, but call * {@link #updateLength(Node, int) update_length(node, -node.length)} to properly remove a * node. - * + * * @param node the node to delete. */ - private void delete(Node node) { - if cast(ASSERT) Assert.isTrue(node !is null); - if cast(ASSERT) Assert.isTrue(node.length is 0); - + private void delete_(Node node) { + if (ASSERT) Assert.isTrue(node !is null); + if (ASSERT) Assert.isTrue(node.length is 0); + Node parent= node.parent; Node toUpdate; // the parent of the node that lost a child bool lostLeftChild; bool isLeftChild= parent is null || node is parent.left; - + if (node.left is null || node.right is null) { // 1) node has one child at max - replace parent's pointer with the only child // also handles the trivial case of no children @@ -1016,46 +1016,46 @@ } else { // 3) hard case - replace node with its successor Node successor= successor(node); - + // successor exists (otherwise node would not have right child, case 1) - if cast(ASSERT) Assert.isNotNull(successor); + if (ASSERT) Assert.isNotNull(successor); // successor has no left child (a left child would be the real successor of node) - if cast(ASSERT) Assert.isTrue(successor.left is null); - if cast(ASSERT) Assert.isTrue(successor.line is 0); + if (ASSERT) Assert.isTrue(successor.left is null); + if (ASSERT) Assert.isTrue(successor.line is 0); // successor is the left child of its parent (otherwise parent would be smaller and // hence the real successor) - if cast(ASSERT) Assert.isTrue(successor is successor.parent.left); + if (ASSERT) Assert.isTrue(successor is successor.parent.left); // successor is not a child of node (would have been covered by 2a) - if cast(ASSERT) Assert.isTrue(successor.parent !is node); + if (ASSERT) Assert.isTrue(successor.parent !is node); toUpdate= successor.parent; lostLeftChild= true; // update relative indices updateParentChain(successor, node, -successor.length, -1); - + // delete successor from its current place - like 1) setChild(toUpdate, successor.right, true); // move node's subtrees to its successor setChild(successor, node.right, false); setChild(successor, node.left, true); - + // replace node by successor in its parent setChild(parent, successor, isLeftChild); - + // update the successor successor.line= node.line; successor.offset= node.offset; successor.balance= node.balance; } - + updateParentBalanceAfterDeletion(toUpdate, lostLeftChild); } - + /** * Updates the balance information in the parent chain of node. - * + * * @param node the first node that needs balance updating * @param wasLeftChild <code>true</code> if the deletion happened on <code>node</code>'s * left subtree, <code>false</code> if it occurred on <code>node</code>'s right @@ -1067,7 +1067,7 @@ node.balance++; else node.balance--; - + Node parent= node.parent; if (parent !is null) wasLeftChild= node is parent.left; @@ -1087,17 +1087,17 @@ case 0: break; // propagate up default: - if cast(ASSERT) + if (ASSERT) Assert.isTrue(false); } - + node= parent; } } - + /** * Re-balances a node whose parent has a double positive balance. - * + * * @param node the node to re-balance * @return <code>true</code> if the re-balancement leaves the height at * <code>node.parent</code> constant, <code>false</code> if the height changed @@ -1116,14 +1116,14 @@ parent.balance= 1; return true; } else { - if cast(ASSERT) Assert.isTrue(false); + if (ASSERT) Assert.isTrue(false); return true; } } /** * Re-balances a node whose parent has a double negative balance. - * + * * @param node the node to re-balance * @return <code>true</code> if the re-balancement leaves the height at * <code>node.parent</code> constant, <code>false</code> if the height changed @@ -1142,27 +1142,27 @@ parent.balance= -1; return true; } else { - if cast(ASSERT) Assert.isTrue(false); + if (ASSERT) Assert.isTrue(false); return true; } } /** * Returns the successor of a node, <code>null</code> if node is the last node. - * + * * @param node a node * @return the successor of <code>node</code>, <code>null</code> if there is none */ private Node successor(Node node) { if (node.right !is null) return successorDown(node.right); - + return successorUp(node); } - + /** * Searches the successor of <code>node</code> in its parent chain. - * + * * @param node a node * @return the first node in <code>node</code>'s parent chain that is reached from its left * subtree, <code>null</code> if there is none @@ -1176,13 +1176,13 @@ child= parent; parent= child.parent; } - if cast(ASSERT) Assert.isTrue(node.delimiter is NO_DELIM); + if (ASSERT) Assert.isTrue(node.delimiter is NO_DELIM); return null; } /** * Searches the left-most node in a given subtree. - * + * * @param node a node * @return the left-most node in the given subtree */ @@ -1199,14 +1199,14 @@ /** * Throws an exception. - * + * * @param offset the illegal character or line offset that caused the exception * @throws BadLocationException always */ private void fail(int offset) { throw new BadLocationException(); } - + /** * Returns the information about the first delimiter found in the given * text starting at the given offset. @@ -1216,7 +1216,7 @@ * @return the information of the first found delimiter or <code>null</code> */ protected abstract DelimiterInfo nextDelimiterInfo(String text, int offset); - + /* * @see dwtx.jface.text.ILineTracker#getLineDelimiter(int) */ @@ -1263,7 +1263,7 @@ int startLine= lineByOffset(offset); int endLine= lineByOffset(offset + length); - + return endLine - startLine + 1; } @@ -1297,11 +1297,11 @@ int remaining= offset; Node node= fRoot; final int lineOffset; - + while (true) { if (node is null) fail(offset); - + if (remaining < node.offset) { node= node.left; } else { @@ -1328,11 +1328,11 @@ int remaining= line; int offset= 0; Node node= fRoot; - + while (true) { if (node is null) fail(line); - + if (remaining is node.line) { offset += node.offset; break; @@ -1359,11 +1359,11 @@ int remaining= line; int offset= 0; Node node= fRoot; - + while (true) { if (node is null) fail(line); - + if (remaining is node.line) { offset+= node.offset; break; @@ -1396,7 +1396,7 @@ throw new InternalError(); } } - + /* * @see java.lang.Object#toString() */ @@ -1406,7 +1406,7 @@ int leaves= cast(int) Math.pow(2, depth - 1); int width= WIDTH * leaves; String empty= "."; //$NON-NLS-1$ - + List roots= new LinkedList(); roots.add(fRoot); StringBuffer buf= new StringBuffer((width + 1) * depth); @@ -1422,7 +1422,7 @@ for (ListIterator it= roots.listIterator(); it.hasNext();) { // pad before buf.append(space, 0, spaces); - + Node node= cast(Node) it.next(); String box; // replace the node with its children @@ -1434,76 +1434,76 @@ it.add(node.right); box= node.toString(); } - + // draw the node, pad to WIDTH int pad_left= (WIDTH - box.length() + 1) / 2; int pad_right= WIDTH - box.length() - pad_left; buf.append(space, 0, pad_left); buf.append(box); buf.append(space, 0, pad_right); - + // pad after buf.append(space, 0, spaces); } - + buf.append('\n'); - nodes *= 2; + nodes *= 2; } - + return buf.toString(); } /** * Recursively computes the depth of the tree. Only used by {@link #toString()}. - * + * * @param root the subtree to compute the depth of, may be <code>null</code> * @return the depth of the given tree, 0 if it is <code>null</code> */ private byte computeDepth(Node root) { if (root is null) return 0; - + return cast(byte) (Math.max(computeDepth(root.left), computeDepth(root.right)) + 1); } - + /** * Debug-only method that checks the tree structure and the differential offsets. */ private void checkTree() { checkTreeStructure(fRoot); - + try { - checkTreeOffsets(nodeByOffset(0), new int[] {0, 0}, null); + checkTreeOffsets(nodeByOffset(0), [0, 0], null); } catch (BadLocationException x) { throw new AssertionError(); } } - + /** * Debug-only method that validates the tree structure below <code>node</code>. I.e. it * checks whether all parent/child pointers are consistent and whether the AVL balance * information is correct. - * + * * @param node the node to validate * @return the depth of the tree under <code>node</code> */ private byte checkTreeStructure(Node node) { if (node is null) return 0; - + byte leftDepth= checkTreeStructure(node.left); byte rightDepth= checkTreeStructure(node.right); Assert.isTrue(node.balance is rightDepth - leftDepth); Assert.isTrue(node.left is null || node.left.parent is node); Assert.isTrue(node.right is null || node.right.parent is node); - + return cast(byte) (Math.max(rightDepth, leftDepth) + 1); } - + /** * Debug-only method that checks the differential offsets of the tree, starting at * <code>node</code> and continuing until <code>last</code>. - * + * * @param node the first <code>Node</code> to check, may be <code>null</code> * @param offLen an array of length 2, with <code>offLen[0]</code> the expected offset of * <code>node</code> and <code>offLen[1]</code> the expected line of @@ -1516,16 +1516,16 @@ private int[] checkTreeOffsets(Node node, int[] offLen, Node last) { if (node is last) return offLen; - + Assert.isTrue(node.offset is offLen[0]); Assert.isTrue(node.line is offLen[1]); - + if (node.right !is null) { int[] result= checkTreeOffsets(successorDown(node.right), new int[2], node); offLen[0] += result[0]; offLen[1] += result[1]; } - + offLen[0] += node.length; offLen[1]++; return checkTreeOffsets(node.parent, offLen, last);