/*******************************************************************************
 * Copyright (c) 2005, 2015 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.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

import org.eclipse.core.runtime.Assert;

import org.eclipse.jface.text.AbstractLineTracker.DelimiterInfo;

/**
 * Abstract implementation of <code>ILineTracker</code>. It lets the definition of line
 * delimiters to subclasses. Assuming that '\n' is the only line delimiter, this abstract
 * implementation defines the following line scheme:
 * <ul>
 * <li> "" -> [0,0]
 * <li> "a" -> [0,1]
 * <li> "\n" -> [0,1], [1,0]
 * <li> "a\n" -> [0,2], [2,0]
 * <li> "a\nb" -> [0,2], [2,1]
 * <li> "a\nbc\n" -> [0,2], [2,3], [5,0]
 * </ul>
 * <p>
 * This class must be subclassed.
 * </p>
 * <p>
 * <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 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
	 *     -> 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= 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.
	 */
	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;

		@Override
		public final 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= Byte.toString(balance);
			}
			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();
		}
	}

	/**
	 * The root node of the tree, never <code>null</code>.
	 */
	private Node fRoot= new Node(0, NO_DELIM);

	/**
	 * Creates a new line tracker.
	 */
	protected TreeLineTracker() {
	}

	/**
	 * Package visible constructor for creating a tree tracker from a list tracker.
	 *
	 * @param tracker the list line tracker
	 */
    TreeLineTracker(ListLineTracker tracker) {
    	final List<Line> lines= tracker.getLines();
    	final int n= lines.size();
    	if (n == 0)
    		return;

    	Line line= lines.get(0);
    	String delim= line.delimiter;
    	if (delim == null)
    		delim= NO_DELIM;
    	int length= line.length;
    	fRoot= new Node(length, delim);
    	Node node= fRoot;

		for (int i= 1; i < n; i++) {
	        line= lines.get(i);
	        delim= line.delimiter;
	        if (delim == null)
	        	delim= NO_DELIM;
	        length= line.length;
			node= insertAfter(node, length, delim);
        }

		if (node.delimiter != NO_DELIM)
			insertAfter(node, 0, NO_DELIM);

		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.
	 * <p>
	 * This means that for offsets smaller than the length, the following holds:
	 * </p>
	 * <p>
	 * <code>line.offset <= offset < line.offset + offset.length</code>.
	 * </p>
	 * <p>
	 * 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) throws BadLocationException {
		/*
		 * Works for any binary search tree.
		 */
		int remaining= offset;
		Node node= fRoot;
		while (true) {
			if (node == null)
				fail(offset);

			if (remaining < node.offset) {
				node= node.left;
			} else {
				remaining -= node.offset;
				if (remaining < node.length
						|| remaining == node.length && node.right == null) { // last line
					break;
				}
				remaining -= node.length;
				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) throws BadLocationException {
		/*
		 * 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) // last line
					return  line;

				remaining -= node.length;
				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) throws BadLocationException {
		/*
		 * Works for any binary search tree.
		 */
		int remaining= line;
		Node node= fRoot;

		while (true) {
			if (node == null)
				fail(line);

			if (remaining == node.line)
				break;
			if (remaining < node.line) {
				node= node.left;
			} else {
				remaining -= node.line + 1;
				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) throws BadLocationException {
		/*
		 * 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)
				return offset + node.offset;

			if (remaining < node.line) {
				node= node.left;
			} else {
				remaining -= node.line + 1;
				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 (ASSERT) Assert.isNotNull(node);
		Node child= node.right;
		if (ASSERT) Assert.isNotNull(child);
		boolean leftChild= node.parent == null || node == 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 (ASSERT) Assert.isNotNull(node);
		Node child= node.left;
		if (ASSERT) Assert.isNotNull(child);
		boolean leftChild= node.parent == null || node == 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
	 *        <code>parent</code>'s right child
	 */
	private void setChild(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;
	}

	/**
	 * 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);
		node.balance= 0;
		parent.balance= 0;
	}

	/**
	 * 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);
		node.balance= 0;
		parent.balance= 0;
	}

	/**
	 * 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;
		rotateRight(node);
		rotateLeft(parent);
		if (child.balance == 1) {
			node.balance= 0;
			parent.balance= -1;
			child.balance= 0;
		} else if (child.balance == 0) {
			node.balance= 0;
			parent.balance= 0;
		} else if (child.balance == -1) {
			node.balance= 1;
			parent.balance= 0;
			child.balance= 0;
		}
	}

	/**
	 * 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;
		rotateLeft(node);
		rotateRight(parent);
		if (child.balance == -1) {
			node.balance= 0;
			parent.balance= 1;
			child.balance= 0;
		} else if (child.balance == 0) {
			node.balance= 0;
			parent.balance= 0;
		} else if (child.balance == 1) {
			node.balance= -1;
			parent.balance= 0;
			child.balance= 0;
		}
	}

	/**
	 * 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 == 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 != 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:
					rebalanceAfterInsertionLeft(node);
					break;
				case 2:
					rebalanceAfterInsertionRight(node);
					break;
				case 0:
					break;
				default:
					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 == 1) {
			singleLeftRotation(node, parent);
		} else if (node.balance == -1) {
			rightLeftRotation(node, parent);
		} 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 == -1) {
			singleRightRotation(node, parent);
		} else if (node.balance == 1) {
			leftRightRotation(node, parent);
		} else if (ASSERT) {
			Assert.isTrue(false);
		}
	}

	@Override
	public final void replace(int offset, int length, String text) throws BadLocationException {
		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 == null)
				fail(offset);

			if (remaining < first.offset) {
				first= first.left;
			} else {
				remaining -= first.offset;
				if (remaining < first.length
						|| remaining == first.length && first.right == null) { // last line
					firstNodeOffset= offset - remaining;
					break;
				}
				remaining -= first.length;
				first= first.right;
			}
		}
		// Inline nodeByOffset end
		if (ASSERT) Assert.isTrue(first != null);

		Node last;
		if (offset + length < firstNodeOffset + first.length)
			last= first;
		else
			last= nodeByOffset(offset + length);
		if (ASSERT) Assert.isTrue(last != null);

		int firstLineDelta= firstNodeOffset + first.length - offset;
		if (first == last)
			replaceInternal(first, text, length, firstLineDelta);
		else
			replaceFromTo(first, last, text, length, firstLineDelta);

		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 == null ? null : nextDelimiterInfo(text, 0);

		if (info == null || info.delimiter == null) {
			// a) trivial case: insert into a single node, no line mangling
			int added= text == null ? 0 : text.length();
			updateLength(node, added - 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 != 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 != last) {
			length -= successor.length;
			Node toDelete= successor;
			successor= successor(successor);
			updateLength(toDelete, -toDelete.length);
		}

		DelimiterInfo info= text == null ? null : nextDelimiterInfo(text, 0);

		if (info == null || info.delimiter == null) {
			int added= text == 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;

			// Inline addLines start
			info= nextDelimiterInfo(text, consumed);
			while (info != null) {
				int lineLen= info.delimiterIndex - consumed + info.delimiterLength;
				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 (ASSERT) Assert.isTrue(node.length  + delta >= 0);

		// update the node itself
		node.length += delta;

		// check deletion
		final int lineDelta;
		boolean delete= node.length == 0 && node.delimiter != NO_DELIM;
		if (delete)
			lineDelta= -1;
		else
			lineDelta= 0;

		// update parent chain
		if (delta != 0 || lineDelta != 0)
			updateParentChain(node, delta, lineDelta);

		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 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 != 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;
		}
	}

	/**
	 * 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 <code>update_length(node, -node.length)</code> to
	 * properly remove a node.
	 *
	 * @param node the node to delete.
	 */
	private void delete(Node node) {
		if (ASSERT) Assert.isTrue(node != null);
		if (ASSERT) Assert.isTrue(node.length == 0);

		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;
			setChild(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;
			setChild(parent, replacement, isLeftChild);
			setChild(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
//			Node replacement= node.left;
//			set_child(parent, replacement, isLeftChild);
//			set_child(replacement, node.right, false);
//			replacement.balance= node.balance;
//			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 (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
			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
	 */
	private void updateParentBalanceAfterDeletion(Node node, boolean wasLeftChild) {
		while (node != null) {
			if (wasLeftChild)
				node.balance++;
			else
				node.balance--;

			Node parent= node.parent;
			if (parent != null)
				wasLeftChild= node == parent.left;

			switch (node.balance) {
				case 1:
				case -1:
					return; // done, no tree change
				case -2:
					if (rebalanceAfterDeletionRight(node.left))
						return;
					break; // propagate up
				case 2:
					if (rebalanceAfterDeletionLeft(node.right))
						return;
					break; // propagate up
				case 0:
					break; // propagate up
				default:
					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 boolean rebalanceAfterDeletionLeft(Node node) {
		Node parent= node.parent;
		if (node.balance == 1) {
			singleLeftRotation(node, parent);
			return false;
		} else if (node.balance == -1) {
			rightLeftRotation(node, parent);
			return false;
		} else if (node.balance == 0) {
			rotateLeft(parent);
			node.balance= -1;
			parent.balance= 1;
			return true;
		} else {
			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 boolean rebalanceAfterDeletionRight(Node node) {
		Node parent= node.parent;
		if (node.balance == -1) {
			singleRightRotation(node, parent);
			return false;
		} else if (node.balance == 1) {
			leftRightRotation(node, parent);
			return false;
		} else if (node.balance == 0) {
			rotateRight(parent);
			node.balance= 1;
			parent.balance= -1;
			return true;
		} else {
			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 != 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) {
		Node child= node;
		Node parent= child.parent;
		while (parent != null) {
			if (child == parent.left)
				return parent;
			child= parent;
			parent= child.parent;
		}
		if (ASSERT) Assert.isTrue(node.delimiter == 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;
		while (child != null) {
			node= child;
			child= node.left;
		}
		return node;
	}

	/* miscellaneous */

	/**
	 * Throws an exception.
	 *
	 * @param offset the illegal character or line offset that caused the exception
	 * @throws BadLocationException always
	 */
	private void fail(int offset) throws BadLocationException {
		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);

	@Override
	public final String getLineDelimiter(int line) throws BadLocationException {
		Node node= nodeByLine(line);
		return node.delimiter == NO_DELIM ? null : node.delimiter;
	}

	@Override
	public final 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;
	}

	@Override
	public final int getNumberOfLines() {
		// TODO track separately?
		Node node= fRoot;
		int lines= 0;
		while (node != null) {
			lines += node.line + 1;
			node= node.right;
		}
		return lines;
	}

	@Override
	public final int getNumberOfLines(int offset, int length) throws BadLocationException {
		if (length == 0)
			return 1;

		int startLine= lineByOffset(offset);
		int endLine= lineByOffset(offset + length);

		return endLine - startLine + 1;
	}

	@Override
	public final int getLineOffset(int line) throws BadLocationException {
		return offsetByLine(line);
	}

	@Override
	public final int getLineLength(int line) throws BadLocationException {
		Node node= nodeByLine(line);
		return node.length;
	}

	@Override
	public final int getLineNumberOfOffset(int offset) throws BadLocationException {
		return lineByOffset(offset);
	}

	@Override
	public final IRegion getLineInformationOfOffset(final int offset) throws BadLocationException {
		// Inline nodeByOffset start as we need both node and offset
		int remaining= offset;
		Node node= fRoot;
		final int lineOffset;

		while (true) {
			if (node == null)
				fail(offset);

			if (remaining < node.offset) {
				node= node.left;
			} else {
				remaining -= node.offset;
				if (remaining < node.length
						|| remaining == node.length && node.right == null) { // last line
					lineOffset= offset - remaining;
					break;
				}
				remaining -= node.length;
				node= node.right;
			}
		}
		// Inline nodeByOffset end
		return new Region(lineOffset, node.pureLength());
	}

	@Override
	public final IRegion getLineInformation(int line) throws BadLocationException {
		try {
			// Inline nodeByLine start
			int remaining= line;
			int offset= 0;
			Node node= fRoot;

			while (true) {
				if (node == null)
					fail(line);

				if (remaining == node.line) {
					offset += node.offset;
					break;
				}
				if (remaining < node.line) {
					node= node.left;
				} else {
					remaining -= node.line + 1;
					offset += node.offset + node.length;
					node= node.right;
				}
			}
			// Inline nodeByLine end
			return new Region(offset, node.pureLength());
		} catch (BadLocationException x) {
			/*
			 * FIXME: this really strange behavior is mandated by the previous line tracker
			 * implementation and included here for compatibility. See
			 * LineTrackerTest3#testFunnyLastLineCompatibility().
			 */
			if (line > 0 && line == getNumberOfLines()) {
				line= line - 1;
				// Inline nodeByLine start
				int remaining= line;
				int offset= 0;
				Node node= fRoot;

				while (true) {
					if (node == null)
						fail(line);

					if (remaining == node.line) {
						offset+= node.offset;
						break;
					}
					if (remaining < node.line) {
						node= node.left;
					} else {
						remaining -= node.line + 1;
						offset += node.offset + node.length;
						node= node.right;
					}
				}
				Node last= node;
				// Inline nodeByLine end
				if (last.length > 0)
					return new Region(offset + last.length, 0);
			}
			throw x;
		}
	}

	@Override
	public final void set(String text) {
		fRoot= new Node(0, NO_DELIM);
		try {
			replace(0, 0, text);
		} catch (BadLocationException x) {
			throw new InternalError();
		}
	}

	@Override
	public String toString() {
		int depth= computeDepth(fRoot);
		int WIDTH= 30;
		int leaves= (int) Math.pow(2, depth - 1);
		int width= WIDTH * leaves;
		String empty= "."; //$NON-NLS-1$

		List<Node> roots= new LinkedList<>();
		roots.add(fRoot);
		StringBuffer buf= new StringBuffer((width + 1) * depth);
		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<Node> it= roots.listIterator(); it.hasNext();) {
				// pad before
				buf.append(space, 0, spaces);

				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');
		}

		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 == null)
			return 0;

		return (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);
		} 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 == null)
			return 0;

		byte leftDepth= checkTreeStructure(node.left);
		byte rightDepth= checkTreeStructure(node.right);
		Assert.isTrue(node.balance == rightDepth - leftDepth);
		Assert.isTrue(node.left == null || node.left.parent == node);
		Assert.isTrue(node.right == null || node.right.parent == node);

		return (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>
	 * @return an <code>int[]</code> of length 2, with the first element being the character
	 *         length of <code>node</code>'s subtree, and the second element the number of lines
	 *         in <code>node</code>'s subtree
	 */
	private int[] checkTreeOffsets(Node node, int[] offLen, Node last) {
		if (node == last)
			return offLen;

		Assert.isTrue(node.offset == offLen[0]);
		Assert.isTrue(node.line == offLen[1]);

		if (node.right != 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);
	}
}