projects/dwt-addons: dwtx/jface/text/TreeLineTracker.d comparison

comparison 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

comparison

equal deleted inserted replaced

-:93a6ec48fd28
+:26688fec6d23
 * <strong>Performance:</strong> The query operations perform in <i>O(log n)</i> where <var>n</var>
 * is the number of lines in the document. The modification operations roughly perform in <i>O(l *
 * 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
 *     -> 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.
 *     -> 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
 *        -> replace is O(log n)
 *     -> 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
 * nodes under the right subtree lines after the current node.
 */
 Node left;
 /** The right subtree, possibly <code>null</code>. */
 Node right;
 /** The balance factor. */
 byte balance;
 /*
 * @see java.lang.Object#toString()
 */
 public final String toString() {
 String bal;
 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$
 }
 /**
 * Returns the pure (without the line delimiter) length of this line.
 *
 * @return the pure line length
 */
 int pureLength() {
 return length - delimiter.length();
 }
 /**
 * Creates a new line tracker.
 */
 protected this() {
 }
 /**
 * Package visible constructor for creating a tree tracker from a list tracker.
 *
 * @param tracker
 */
 this(ListLineTracker tracker) {
 final List lines= tracker.getLines();
 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)
 delim= NO_DELIM;
 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;
 if (delim is null)
 delim= NO_DELIM;
 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();
 }
 /**
 * Returns the node (line) including a certain offset. If the offset is between two
 * lines, the line starting at <code>offset</code> is returned.
 * If <code>offset</code> is the document length, then this is true:
 * </p>
 * <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
 */
 private Node nodeByOffset(final int offset)  {
 * Works for any binary search tree.
 */
 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 {
 remaining -= node.offset;
 line+= node.line;
 remaining -= node.length;
 line ++;
 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
 */
 private int lineByOffset(final int offset)  {
 * Works for any binary search tree.
 */
 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 {
 remaining -= node.offset;
 line+= node.line;
 line ++;
 node= node.right;
 }
 }
 }
 /**
 * 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
 */
 private Node nodeByLine(final int line)  {
 * Works for any binary search tree.
 */
 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) {
 node= node.left;
 } else {
 remaining -= node.line + 1;
 offset += node.offset + node.length;
 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
 */
 private int offsetByLine(final int line)  {
 * Works for any binary search tree.
 */
 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;
 if (remaining < node.line) {
 node= node.left;
 offset += node.offset + node.length;
 node= node.right;
 }
 }
 }
 /**
 * 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
 child.line += node.line + 1;
 child.offset += node.offset + node.length;
 }
 /**
 * 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
 node.line -= child.line + 1;
 node.offset -= child.offset + child.length;
 }
 /**
 * 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>
 * @param isLeftChild <code>true</code> if <code>child</code> shall become
 *        <code>parent</code>'s left child, <code>false</code> if it shall become
 parent.right= child;
 }
 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
 */
 private void singleLeftRotation(Node node, Node parent) {
 rotateLeft(parent);
 }
 /**
 * 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
 */
 private void singleRightRotation(Node node, Node parent) {
 rotateRight(parent);
 }
 /**
 * 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
 */
 private void rightLeftRotation(Node node, Node parent) {
 Node child= node.left;
 }
 /**
 * 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
 */
 private void leftRightRotation(Node node, Node parent) {
 Node child= node.right;
 }
 }
 /**
 * 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
 * @return the inserted node
 */
 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
 * 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) {
 Node parent= node.parent;
 while (parent !is null) {
 rebalanceAfterInsertionRight(node);
 break;
 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) {
 Node parent= node.parent;
 if (node.balance is 1) {
 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) {
 Node parent= node.parent;
 if (node.balance is -1) {
 singleRightRotation(node, parent);
 } else if (node.balance is 1) {
 leftRightRotation(node, parent);
-} else if cast(ASSERT) {
+} else if (ASSERT) {
 Assert.isTrue(false);
 }
 }
 /*
 * @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 {
 remaining -= first.offset;
 if (remaining < first.length
 remaining -= first.length;
 first= first.right;
 }
 }
 // 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, &lt; <code>firstLineDelta</code>
 * @param firstLineDelta the number of characters from the replacement offset to the end of
 *        <code>node</code> &gt; <code>length</code>
 */
 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) {
 // a) trivial case: insert into a single node, no line mangling
 int added= text is null ? 0 : text.length();
 } else {
 // b) more lines to add between two chunks of the first node
 // 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
 info= nextDelimiterInfo(text, consumed);
 while (info !is null) {
 int lineLen= info.delimiterIndex - consumed + info.delimiterLength;
 node= insertAfter(node, lineLen, info.delimiter);
 consumed += lineLen;
 info= nextDelimiterInfo(text, consumed);
 }
 // 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
 * @param length the replace length, &gt;= <code>firstLineDelta</code>
 * @param firstLineDelta the number of characters removed from the replacement offset to the end
 *        of <code>node</code>, &lt;= <code>length</code>
 */
 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
 Node successor= successor(node);
 while (successor !is last) {
 if (info is null || info.delimiter is null) {
 int added= text is null ? 0 : text.length();
 // 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);
 node.delimiter= info.delimiter;
 length -= firstLineDelta;
 node= insertAfter(node, lineLen, info.delimiter);
 consumed += lineLen;
 info= nextDelimiterInfo(text, consumed);
 }
 // Inline addLines end
 updateLength(last, text.length() - consumed - length);
 }
 }
 /**
 * 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
 */
 private void join(Node one, Node two, int delta) {
 int oneLength= one.length;
 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;
+bool delete__= node.length is 0 && node.delimiter !is NO_DELIM;
-if (delete)
+if (delete__)
 lineDelta= -1;
 else
 lineDelta= 0;
 // update parent chain
 if (delta !is 0 || lineDelta !is 0)
 updateParentChain(node, delta, lineDelta);
-if (delete)
+if (delete__)
-delete(node);
+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 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 deltaLines the line delta
 */
 private void updateParentChain(Node from, Node to, int deltaLength, int deltaLines) {
 Node parent= from.parent;
 while (parent !is to) {
 }
 from= parent;
 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) {
+private void delete_(Node node) {
-if cast(ASSERT) Assert.isTrue(node !is null);
+if (ASSERT) Assert.isTrue(node !is null);
-if cast(ASSERT) Assert.isTrue(node.length is 0);
+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
 Node replacement= node.left is null ? node.right : node.left;
 setChild(parent, replacement, isLeftChild);
 //          toUpdate= replacement;
 //          lostLeftChild= true;
 } 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 (ASSERT) Assert.isTrue(successor.left is null);
-if cast(ASSERT) Assert.isTrue(successor.line is 0);
+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
 *        subtree
 */
 while (node !is null) {
 if (wasLeftChild)
 node.balance++;
 else
 node.balance--;
 Node parent= node.parent;
 if (parent !is null)
 wasLeftChild= node is parent.left;
 switch (node.balance) {
 return;
 break; // propagate up
 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
 */
 private bool rebalanceAfterDeletionLeft(Node node) {
 rotateLeft(parent);
 node.balance= -1;
 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
 */
 private bool rebalanceAfterDeletionRight(Node node) {
 rotateRight(parent);
 node.balance= 1;
 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
 */
 private Node successorUp(final Node node) {
 if (child is parent.left)
 return parent;
 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
 */
 private Node successorDown(Node node) {
 Node child= node.left;
 /* miscellaneous */
 /**
 * 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.
 *
 * @param text the text to be searched
 * @param offset the offset in the given text
 * @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)
 */
 public final String getLineDelimiter(int line)  {
 Node node= nodeByLine(line);
 if (length is 0)
 return 1;
 int startLine= lineByOffset(offset);
 int endLine= lineByOffset(offset + length);
 return endLine - startLine + 1;
 }
 /*
 * @see dwtx.jface.text.ILineTracker#getLineOffset(int)
 public final IRegion getLineInformationOfOffset(final int offset)  {
 // Inline nodeByOffset start as we need both node and offset
 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 {
 remaining -= node.offset;
 if (remaining < node.length
 try {
 // Inline nodeByLine start
 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;
 }
 if (remaining < node.line) {
 line= line - 1;
 // Inline nodeByLine start
 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;
 }
 if (remaining < node.line) {
 replace(0, 0, text);
 } catch (BadLocationException x) {
 throw new InternalError();
 }
 }
 /*
 * @see java.lang.Object#toString()
 */
 public String toString() {
 int depth= computeDepth(fRoot);
 int WIDTH= 30;
 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);
 int nodes= 1;
 int indents= leaves;
 int spaces= Math.max(0, indents * WIDTH - WIDTH / 2);
 // print nodes
 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
 if (node is null) {
 it.add(null);
 } else {
 it.set(node.left);
 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;
 }
 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
 *        <code>node</code>
 * @param last the last <code>Node</code> to check, may be <code>null</code>
 *         in <code>node</code>'s subtree
 */
 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);
 }
 }

Mercurial > projects > dwt-addons

comparison dwtx/jface/text/TreeLineTracker.d @ 140:26688fec6d23