Attachment 28916 Details for Bug 114091 – TreeLineTracker.java

TreeLineTracker.java

TreeLineTracker.java (text/x-java), 26.97 KB, created by Tom Hofmann

on 2005-10-28 08:54:33 EDT

(hide)

Description:

Filename:

MIME Type:

Creator: Tom Hofmann

Created: 2005-10-28 08:54:33 EDT

Size: 26.97 KB

patch

obsolete

>/*******************************************************************************
> * Copyright (c) 2005 IBM Corporation and others.
> * All rights reserved. This program and the accompanying materials
> * are made available under the terms of the Eclipse Public License v1.0
> * which accompanies this distribution, and is available at
> * http://www.eclipse.org/legal/epl-v10.html
> *
> * Contributors:
> *     IBM Corporation - initial API and implementation
> *******************************************************************************/
>package org.eclipse.jface.text;
>
>import java.util.ArrayList;
>import java.util.Arrays;
>import java.util.LinkedList;
>import java.util.List;
>import java.util.ListIterator;
>
>
>/**
> * 
> * @since 3.2
> */
>public final class TreeLineTracker implements 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
>	 *     -> clear iteration order, iteration in O(1)
>	 *     -> 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 boolean ASSERT= true;
>	/**
>	 * The empty delimiter of the last line. Only the last line may 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 are represent lines before, all
>	 * nodes under the right subtree lines after the current node.
>	 */
>	private static final class Node {
>		Node(int length, String delimiter) {
>			this.length= length;
>			this.delimiter= delimiter;
>		}
>		/**
>		 * The line index in this node's line tree, or equivalently, the number of lines in the left
>		 * subtree.
>		 */
>		int line;
>		/**
>		 * The line offset in this node's line tree, or equivalently, the number of characters in the left
>		 * subtree.
>		 */
>		int offset;
>		/**
>		 * The number of characters in this line.
>		 */
>		int length;
>		/**
>		 * The line delimiter of this line, needed to answer the delimiter query.
>		 */
>		String delimiter;
>		/**
>		 * The parent node, <code>null</code> if this is the root node.
>		 */
>		Node parent;
>		/**
>		 * The left subtree, possibly <code>null</code>.
>		 */
>		Node left;
>		/**
>		 * The right subtree, possibly <code>null</code>.
>		 */
>		Node right;
>		/**
>		 * The balance factor.
>		 */
>		byte balance;
>		
>		/*
>		 * @see java.lang.Object#toString()
>		 */
>		public String toString() {
>			String bal;
>			switch (balance) {
>				case 0:
>					bal= "="; //$NON-NLS-1$
>					break;
>				case 1:
>					bal="+"; //$NON-NLS-1$
>					break;
>				case 2:
>					bal="++"; //$NON-NLS-1$
>					break;
>				case -1:
>					bal="-"; //$NON-NLS-1$
>					break;
>				case -2:
>					bal="--"; //$NON-NLS-1$
>					break;
>				default:
>					bal= Integer.toString(balance);
>			}
>			return "[" + offset + "+" + (length - delimiter.length()) + "+" + 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();
>		}
>	}
>	
>	/**
>	 * The root node of the tree, never <code>null</code>.
>	 */
>	private Node fRoot= new Node(0, NO_DELIM);
>
>	/*
>	 * Hints storing a line's offset / line index. Replace with a thread-local cache for multi
>	 * threading.
>	 */
>	/**
>	 * The line offset of the line last queried with <code>node_by_offset</code>.
>	 */
>	private int line_hint;
>	/**
>	 * The character offset of the line last queried with <code>node_by_offset</code> or
>	 * <code>node_by_line</code>.
>	 */
>	private int offset_hint;
>
>	/**
>	 * Combines the information of the occurrence of a line delimiter.
>	 * <code>delimiterIndex</code> is the index where a line delimiter
>	 * starts, whereas <code>delimiterLength</code>, indicates the length
>	 * of the delimiter.
>	 */
>	protected static class DelimiterInfo {
>		public int delimiterIndex;
>		public int delimiterLength;
>		public String delimiter;
>	}
>	
>	/** The predefined delimiters of this tracker */
>	public final static String[] DELIMITERS= { "\r", "\n", "\r\n" }; //$NON-NLS-3$ //$NON-NLS-1$ //$NON-NLS-2$
>	/**
>	 * A predefined delimiter information which is always reused when computing replaced line
>	 * information.
>	 */
>	private DelimiterInfo fDelimiterInfo= new DelimiterInfo();
>	private int[] fLengths;
>	private int[] fDelimLengths;
>	private String[] fDelims;
>
>	public TreeLineTracker() {
>	}
>	
>	private Node node_by_offset(final int offset) {
>		/*
>		 * Works for any binary search tree.
>		 */
>		int remaining= offset;
>		Node node= fRoot;
>		int line= 0;
>		
>		while (true) {
>			if (node == null)
>				fail(offset);
>			
>			if (remaining < node.offset) {
>				node= node.left;
>			} else {
>				remaining -= node.offset;
>				line+= node.line;
>				if (remaining < node.length || remaining == node.length && node.right == null) {
>					offset_hint= offset - remaining;
>					line_hint= line;
>					return node;
>				}
>				remaining -= node.length;
>				line ++;
>				node= node.right;
>			}
>		}
>	}
>	
>	private Node node_by_line(final int line) {
>		/*
>		 * Works for any binary search tree.
>		 */
>		int remaining= line;
>		int offset= 0;
>		Node node= fRoot;
>		
>		while (true) {
>			if (node == null)
>				fail(line);
>			
>			if (remaining == node.line) {
>				offset_hint= offset + node.offset;
>				return node;
>			}
>			if (remaining < node.line) {
>				node= node.left;
>			} else {
>				remaining -= node.line + 1;
>				offset += node.offset + node.length;
>				node= node.right;
>			}
>		}
>	}
>	
>	private Node insert_after(Node node, int length, String delimiter) {
>		/*
>		 * An insertion really shifts the key of all succeeding nodes. Hence we search for the node
>		 * at offset and insert a new node between that node and its predecessor.
>		 */
>		/*
>		 * Assumptions:
>		 * - the insertion is already trimmed down to a pure insert. No changes to existing lines here!
>		 */
>		
>		Node added= new Node(length, delimiter);
>		
>		// search the insertion point
>		if (node == null) {
>			fRoot= added;
>		} else if (node.right == null) {
>			// immediate child of the node
>			node.right= added;
>			added.parent= node;
>		} else {
>			// leftmost descendant of the right subtree is the successor of node
>			node= node.right;
>			while (node.left != null)
>				node= node.left;
>			node.left= added;
>			added.parent= node;
>		}
>		
>		// parent chain update
>		update_parent_chain(added, length, 1);
>		update_parent_balance_after_insertion(added);
>		
>		return added;
>	}
>	
>	private void update_parent_balance_after_insertion(Node node) {
>		Node parent= node.parent;
>		while (parent != null) {
>			if (node == parent.left)
>				parent.balance--;
>			else
>				parent.balance++;
>
>			switch (parent.balance) {
>				case 1:
>				case -1:
>					node= parent;
>					parent= node.parent;
>					continue;
>				case -2:
>					rebalance_after_insertion_left(node);
>					break;
>				case 2:
>					rebalance_after_insertion_right(node);
>					break;
>				case 0:
>					break;
>				default:
>					if (ASSERT)	
>						Assert.isTrue(false);
>			}
>			return;
>		}
>	}
>	
>	private void rebalance_after_insertion_right(Node node) {
>		if (node.balance == 1) {
>			rotate_left(node.parent);
>		} else if (node.balance == -1) {
>			Node parent= node.parent;
>			rotate_right(node);
>			rotate_left(parent);
>		} else if (ASSERT) {
>			Assert.isTrue(false);
>		}
>	}
>
>	private void rebalance_after_insertion_left(Node node) {
>		if (node.balance == -1) {
>			rotate_right(node.parent);
>		} else if (node.balance == 1) {
>			Node parent= node.parent;
>			rotate_left(node);
>			rotate_right(parent);
>		} else if (ASSERT) {
>			Assert.isTrue(false);
>		}
>	}
>
>	private void rotate_left(Node node) {
>		Node child= node.right;
>		boolean leftChild= node.parent == null || node == node.parent.left;
>		
>		// restructure
>		set_child(node.parent, child, leftChild);
>		
>		set_child(node, child.left, false);
>		set_child(child, node, true);
>		
>		// update balance
>		node.balance= 0;
>		child.balance= 0;
>		
>		// 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;
>	}
>
>	private void rotate_right(Node node) {
>		Node child= node.left;
>		boolean leftChild= node.parent == null || node == node.parent.left;
>		set_child(node.parent, child, leftChild);
>		
>		set_child(node, child.right, true);
>		set_child(child, node, false);
>		
>		// update balance
>		node.balance= 0;
>		child.balance= 0;
>		
>		// update relative info
>		// node loses its left subtree, except for what it keeps in its new subtree
>		// this is exactly the amount reference in child
>		node.line -= child.line + 1;
>		node.offset -= child.offset + child.length;
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#replace(int, int, java.lang.String)
>	 */
>	public void replace(int offset, int length, String text) {
>		compute_line_lenghts(text);
>		int addIndex= 0;
>		
>		Node first= node_by_offset(offset);
>		if (ASSERT) Assert.isTrue(first != null);
>		int firstNodeOffset= offset_hint;
>		
>		Node last;
>		if (offset + length < firstNodeOffset + first.length)
>			last= first;
>		else
>			last= node_by_offset(offset + length);
>		if (ASSERT) Assert.isTrue(last != null);
>		
>		// 1) modification on a single line
>		if (first == last) {
>			// convert offsets to relative lengths
>			int replaceEnd= offset + length;
>
>			if (fLengths.length == 1) {
>				
>				// a) trivial case: insert into a single node, no line mangling
>				int removeDelta= replaceEnd - offset;
>				int delta= fLengths[0] - removeDelta;
>				update_length(first, delta);
>				
>			} else {
>			
>				// b) more lines to add between two chunks of the first node
>				// remember what we split off the first line
>				int remainder= firstNodeOffset + first.length - offset - length;
>				String remDelim= first.delimiter;
>				
>				// join the first line with the first added
>				int removeDelta= remainder + length;
>				int delta= fLengths[0] - removeDelta;
>				update_length(first, delta);
>				first.delimiter= fDelims[0];
>
>				Node node= addLines(++addIndex, first);
>
>				// add remaining chunk merged with last (incomplete) additional line
>				insert_after(node, remainder + fLengths[fLengths.length - 1], remDelim);
>			}
>			return;
>		}
>		// 2) modification covers several lines
>		
>		// delete intermediate nodes
>		Node successor= successor(first);
>		while (successor != last) {
>			length -= successor.length;
>			Node toDelete= successor;
>			successor= successor(successor);
>			update_length(toDelete, -toDelete.length);
>		}
>		
>		// join the two lines if there are no lines added
>		if (fLengths.length == 1) {
>			join(first, last, fLengths[0] - length);
>			return;
>		}
>		
>		// join the first line with the first added
>		int removeDelta= firstNodeOffset + first.length - offset;
>		int delta= fLengths[0] - removeDelta;
>		length -= removeDelta;
>		update_length(first, delta);
>		first.delimiter= fDelims[0];
>
>		addLines(++addIndex, first);
>		
>		// merge last (incomplete) line with with last node
>		update_length(last, fLengths[fLengths.length - 1] - length);
>
>	}
>
>	private Node addLines(int addIndex, Node node) {
>		while (addIndex < fLengths.length - 1) {
>			node= insert_after(node, fLengths[addIndex], fDelims[addIndex]);
>			addIndex++;
>		}
>		return node;
>	}
>	
>	private void join(Node one, Node two, int delta) {
>		update_length(one, two.length + delta);
>		one.delimiter= two.delimiter;
>		update_length(two, -two.length, true);
>	}
>	
>	private void update_length(Node node, int delta) {
>		update_length(node, delta, false);
>	}
>
>	private void update_length(Node node, int delta, boolean forceDelete) {
>		if (ASSERT) Assert.isTrue(node.length  + delta >= 0);
>		
>		// update the node itself
>		node.length += delta;
>		
>		// check deletion
>		final int lineDelta;
>		boolean delete= node.length == 0 && (forceDelete || successor(node) != null);
>		if (delete)
>			lineDelta= -1;
>		else
>			lineDelta= 0;
>		
>		// update parent chain
>		if (delta != 0 || lineDelta != 0)
>			update_parent_chain(node, delta, lineDelta);
>		
>		if (delete)
>			delete(node);
>	}
>
>	private void update_parent_chain(Node node, int deltaLength, int deltaLines) {
>		// TODO forward to from-to method
>		Node parent= node.parent;
>		while (parent != null) {
>			// only update node if update comes from left subtree
>			if (node == parent.left) {
>				parent.offset += deltaLength;
>				parent.line += deltaLines;
>			}
>			node= parent;
>			parent= node.parent;
>		}
>	}
>	
>	private void update_parent_chain(Node from, Node to, int deltaLength, int deltaLines) {
>		Node parent= from.parent;
>		while (parent != to) {
>			// only update node if update comes from left subtree
>			if (from == parent.left) {
>				parent.offset += deltaLength;
>				parent.line += deltaLines;
>			}
>			from= parent;
>			parent= from.parent;
>		}
>	}
>	
>	private void delete(Node node) {
>		if (ASSERT) Assert.isTrue(node != null);
>		if (ASSERT) Assert.isTrue(node.length == 0);
>		// TODO balancing
>		// TODO update relative offset bookkeeping
>		
>		Node parent= node.parent;
>		Node toUpdate; // the parent of the node that lost a child
>		boolean lostLeftChild;
>		boolean isLeftChild= parent == null || node == parent.left;
>		
>		if (node.left == null || node.right == 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 == null ? node.right : node.left;
>			set_child(parent, replacement, isLeftChild);
>			toUpdate= parent;
>			lostLeftChild= isLeftChild;
>			// no updates to do - subtrees stay as they are
>		} else if (node.right.left == null) {
>			// 2a) node's right child has no left child - replace node with right child, giving node's
>			// left subtree to the right child
>			Node replacement= node.right;
>			set_child(parent, replacement, isLeftChild);
>			set_child(replacement, node.left, true);
>			replacement.line += node.line;
>			replacement.offset += node.offset;
>			replacement.balance= node.balance;
>			toUpdate= replacement;
>			lostLeftChild= false;
>//		} else if (node.left.right == null) {
>//			// 2b) symmetric case
>//			replacement= node.left;
>//			set_child(parent, replacement, isLeftChild);
>//			set_child(replacement, node.right, false);
>//			toUpdate= replacement.parent;
>//			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 (ASSERT) Assert.isNotNull(successor);
>			// successor has no left child (a left child would be the real successor of node)
>			if (ASSERT) Assert.isTrue(successor.left == null);
>			if (ASSERT) Assert.isTrue(successor.line == 0);
>			// successor is the left child of its parent (otherwise parent would be smaller and
>			// hence the real successor)
>			if (ASSERT) Assert.isTrue(successor == successor.parent.left);
>			// successor is not a child of node (would have been covered by 2a)
>			if (ASSERT) Assert.isTrue(successor.parent != node);
>
>			toUpdate= successor.parent;
>			lostLeftChild= true;
>
>			// update relative indices
>			update_parent_chain(successor, node, -successor.length, -1);
>			
>			// delete successor from its current place - like 1)
>			set_child(toUpdate, successor.right, true);
>
>			// move node's subtrees to its successor
>			set_child(successor, node.right, false);
>			set_child(successor, node.left, true);
>			
>			// replace node by successor in its parent
>			set_child(parent, successor, isLeftChild);
>			
>			// update the successor
>			successor.balance= node.balance;
>			successor.offset= node.offset;
>			successor.line= node.line;
>		}
>		
>		update_parent_balance_after_deletion(toUpdate, lostLeftChild);
>
>		node.parent= null;
>		node.left= null;
>		node.right= null;
>	}
>	
>	private void set_child(Node parent, Node child, boolean isLeftChild) {
>		if (parent == null) {
>			if (child == null)
>				fRoot= new Node(0, NO_DELIM);
>			else
>				fRoot= child;
>		} else {
>			if (isLeftChild)
>				parent.left= child;
>			else
>				parent.right= child;
>		}
>		if (child != null)
>			child.parent= parent;
>	}
>	
>	private void update_parent_balance_after_deletion(Node node, boolean wasLeftChild) {
>		while (node != null) {
>			if (wasLeftChild)
>				node.balance++;
>			else
>				node.balance--;
>
>			switch (node.balance) {
>				case 1:
>				case -1:
>					return; // done, no tree change
>				case -2:
>					if (rebalance_after_deletion_left(node.left))
>						return;
>					break; // propagate up
>				case 2:
>					if (rebalance_after_deletion_right(node.right))
>						return;
>					break; // propagate up
>				case 0:
>					break; // propagate up
>				default:
>					if (ASSERT)	
>						Assert.isTrue(false);
>			}
>			
>			Node child= node;
>			node= node.parent;
>			if (node != null)
>				wasLeftChild= child == node.left;
>		}
>	}
>	
>	private boolean rebalance_after_deletion_right(Node node) {
>		if (node.balance == 1) {
>			rotate_left(node.parent);
>			return false;
>		} else if (node.balance == -1) {
>			Node parent= node.parent;
>			rotate_right(node);
>			rotate_left(parent);
>			return false;
>		} else if (node.balance == 0) {
>			rotate_left(node.parent);
>			return true;
>		} else {
>			if (ASSERT) Assert.isTrue(false);
>			return true;
>		}
>	}
>
>	private boolean rebalance_after_deletion_left(Node node) {
>		if (node.balance == -1) {
>			rotate_right(node.parent);
>			return false;
>		} else if (node.balance == 1) {
>			Node parent= node.parent;
>			rotate_left(node);
>			rotate_right(parent);
>			return false;
>		} else if (node.balance == 0) {
>			rotate_right(node.parent);
>			return true;
>		} else {
>			if (ASSERT) Assert.isTrue(false);
>			return true;
>		}
>	}
>
>	private Node successor(Node node) {
>		// TODO using a threaded tree would simplify this
>		// in-order traversal
>		
>		if (node.right != null)
>			return successor_down(node.right);
>		
>		return successor_up(node);
>	}
>	
>	private Node successor_up(Node node) {
>		Node parent= node.parent;
>		while (parent != null) {
>			if (node == parent.left)
>				return parent;
>			node= parent;
>			parent= node.parent;
>		}
>		return null;
>	}
>
>	private Node successor_down(Node node) {
>		Node child= node.left;
>		while (child != null) {
>			node= child;
>			child= node.left;
>		}
>		return node;
>	}
>
>	/* miscellaneous */
>
>	private void fail(int offset) {
>		throw new ArrayIndexOutOfBoundsException(offset);
>	}
>	
>	/* from AbstractLineTracker */
>	
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#computeNumberOfLines(java.lang.String)
>	 */
>	private void compute_line_lenghts(String text) {
>		if (text == null) {
>			fLengths= new int[] { 0 };
>			fDelimLengths= new int[] { 0 };
>			fDelims= new String[] { NO_DELIM };
>			return;
>		}
>		
>		int start= 0;
>		DelimiterInfo delimiterInfo= nextDelimiterInfo(text, start);
>		if (delimiterInfo == null) {
>			fLengths= new int[] { text.length() };
>			fDelimLengths= new int[] { 0 };
>			fDelims= new String[] { NO_DELIM };
>			return;
>		}
>		
>		ArrayList lengths= new ArrayList(2);
>		ArrayList delimLengths= new ArrayList(2);
>		ArrayList delims= new ArrayList(2);
>		while (delimiterInfo != null) {
>			int lastStart= start;
>			start= delimiterInfo.delimiterIndex + delimiterInfo.delimiterLength;
>			lengths.add(new Integer(start - lastStart));
>			delimLengths.add(new Integer(delimiterInfo.delimiterLength));
>			delims.add(new String(delimiterInfo.delimiter));
>			start= delimiterInfo.delimiterIndex + delimiterInfo.delimiterLength;
>			delimiterInfo= nextDelimiterInfo(text, start);
>		}
>		// last line
>		lengths.add(new Integer(text.length() - start));
>		delimLengths.add(new Integer(0));
>		delims.add(NO_DELIM);
>		
>		fLengths= new int[lengths.size()];
>		fDelimLengths= new int[lengths.size()];
>		fDelims= new String[lengths.size()];
>		for (int i= 0; i < fLengths.length; i++) {
>			fLengths[i]= ((Integer) lengths.get(i)).intValue();
>			fDelimLengths[i]= ((Integer) delimLengths.get(i)).intValue();
>			fDelims[i]= (String) delims.get(i);
>		}
>		
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.AbstractLineTracker#nextDelimiterInfo(java.lang.String, int)
>	 */
>	protected DelimiterInfo nextDelimiterInfo(String text, int offset) {
>
>		char ch;
>		int length= text.length();
>		for (int i= offset; i < length; i++) {
>
>			ch= text.charAt(i);
>			if (ch == '\r') {
>
>				if (i + 1 < length) {
>					if (text.charAt(i + 1) == '\n') {
>						fDelimiterInfo.delimiter= DELIMITERS[2];
>						fDelimiterInfo.delimiterIndex= i;
>						fDelimiterInfo.delimiterLength= 2;
>						return fDelimiterInfo;
>					}
>				}
>
>				fDelimiterInfo.delimiter= DELIMITERS[0];
>				fDelimiterInfo.delimiterIndex= i;
>				fDelimiterInfo.delimiterLength= 1;
>				return fDelimiterInfo;
>
>			} else if (ch == '\n') {
>
>				fDelimiterInfo.delimiter= DELIMITERS[1];
>				fDelimiterInfo.delimiterIndex= i;
>				fDelimiterInfo.delimiterLength= 1;
>				return fDelimiterInfo;
>			}
>		}
>
>		return null;
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#getLegalLineDelimiters()
>	 */
>	public String[] getLegalLineDelimiters() {
>		return TextUtilities.copy(DELIMITERS);
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#getLineDelimiter(int)
>	 */
>	public String getLineDelimiter(int line) throws BadLocationException {
>		Node node= node_by_line(line);
>		return node.delimiter;
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#computeNumberOfLines(java.lang.String)
>	 */
>	public int computeNumberOfLines(String text) {
>		int count= 0;
>		int start= 0;
>		DelimiterInfo delimiterInfo= nextDelimiterInfo(text, start);
>		while (delimiterInfo != null && delimiterInfo.delimiterIndex > -1) {
>			++count;
>			start= delimiterInfo.delimiterIndex + delimiterInfo.delimiterLength;
>			delimiterInfo= nextDelimiterInfo(text, start);
>		}
>		return count;
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#getNumberOfLines()
>	 */
>	public int getNumberOfLines() {
>		// TODO track separately
>		Node node= fRoot;
>		int lines= 0;
>		while (node != null) {
>			lines += node.line + 1;
>			node= node.right;
>		}
>		return lines;
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#getNumberOfLines(int, int)
>	 */
>	public int getNumberOfLines(int offset, int length) throws BadLocationException {
>		if (length == 0)
>			return 1;
>		node_by_offset(offset);
>		int startLine= line_hint;
>		node_by_offset(length);
>		int endLine= line_hint;
>		return endLine - startLine + 1;
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#getLineOffset(int)
>	 */
>	public int getLineOffset(int line) throws BadLocationException {
>		node_by_line(line);
>		return offset_hint;
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#getLineLength(int)
>	 */
>	public int getLineLength(int line) throws BadLocationException {
>		Node node= node_by_line(line);
>		return node.length;
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#getLineNumberOfOffset(int)
>	 */
>	public int getLineNumberOfOffset(int offset) throws BadLocationException {
>		node_by_offset(offset);
>		return line_hint;
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#getLineInformationOfOffset(int)
>	 */
>	public IRegion getLineInformationOfOffset(int offset) throws BadLocationException {
>		Node node= node_by_offset(offset);
>		return new Region(offset_hint, node.pureLength());
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#getLineInformation(int)
>	 */
>	public IRegion getLineInformation(int line) throws BadLocationException {
>		Node node= node_by_line(line);
>		return new Region(offset_hint, node.pureLength());
>	}
>
>	/*
>	 * @see org.eclipse.jface.text.ILineTracker#set(java.lang.String)
>	 */
>	public void set(String text) {
>//		set_backward_vine(text);
>//		set_forward_vine(text);
>		set_balanced(text);
>	}
>	
>	private void set_forward_vine(String text) {
>		compute_line_lenghts(text);
>		int addIndex= 0;
>		
>		Node node= null;
>		while (addIndex < fLengths.length) {
>			node= insert_after(node, fLengths[addIndex], fDelims[addIndex]);
>			addIndex++;
>		}
>	}
>	
>	private void set_backward_vine(String text) {
>		compute_line_lenghts(text);
>		
>		// first
>		Node node= insert_after(null, fLengths[0], fDelims[0]);
>		int addIndex= fLengths.length;
>		while (--addIndex > 0) {
>			insert_after(node, fLengths[addIndex], fDelims[addIndex]);
>		}
>	}
>	
>	private void set_balanced(String text) {
>		compute_line_lenghts(text);
>		
>		// first
>		Node node= insert_after(null, fLengths[0], fDelims[0]);
>		set_balanced(node, null, 1, fLengths.length);
>	}
>	
>	private void set_balanced(Node before, Node after, int first, int last) {
>		// last is exclusive
>		// break condition
>		if (first == last)
>			return;
>		
>		// divide
>		int median= (last - first) / 2 + first;
>		Node med= insert_after(before, fLengths[median], fDelims[median]);
>		// conquer
>		set_balanced(before, med, first, median);
>		set_balanced(med, after, median + 1, last);
>	}
>	
>	/*
>	 * @see java.lang.Object#toString()
>	 */
>	public String toString() {
>		int depth= computeDepth(fRoot);
>		int WIDTH= 13;
>		int leaves= (int) Math.pow(2, depth - 1);
>		int width= WIDTH * leaves;
>		String empty= ".";
>		
>		List roots= new LinkedList();
>		roots.add(fRoot);
>		StringBuffer buf= new StringBuffer((width + 1) * depth);
>		int nodes= 1;
>		int indents= leaves;
>		char[] space= new char[leaves * WIDTH / 2];
>		Arrays.fill(space, ' ');
>		for(int d= 0; d < depth; d++) {
>			// compute indent
>			indents /= 2;
>			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= (Node) it.next();
>				String box;
>				// replace the node with its children
>				if (node == null) {
>					it.add(null);
>					box= empty;
>				} 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();
>	}
>
>	private int computeDepth(Node root) {
>		if (root == null)
>			return 0;
>		
>		return Math.max(computeDepth(root.left), computeDepth(root.right)) + 1;
>	}
>}
>

Actions: View

Attachments on bug 114091: 28915 | 28916