Posted By

obrienm on 08/29/14

Tagged

Versions (?)

Last Edited at 08/29/14 05:21am

Statistics

Viewed 462 times

Favorited by 0 user(s)

Related snippets

Editor Trees - EditTree Class

/ Published in: Java

Data Structures & Algorithm Analysis Project

Highlighted TextExpand

package editortrees;

// A height-balanced binary tree with rank that could be the basis for a text editor.

public class EditTree {

public Node root;
	private int size;
	int totalRotationCount;

/**
	 * Construct an empty tree
	 */
	public EditTree() {
		this.root = Node.NULL_NODE;
		this.size = 0;
		this.totalRotationCount = 0;
	}

/**
	 * Construct a single-node tree whose element is c
	 * 
	 * @param c
	 */
	public EditTree(char c) {
		this.root = new Node(c);
		this.size = 1;
		this.totalRotationCount = 0;
	}

/**
	 * Create an EditTree whose toString is s. This can be done in O(N) time,
	 * where N is the length of the tree (repeatedly calling insert() would be
	 * O(N log N), so you need to find a more efficient way to do this.
	 * 
	 * @param s
	 */
	public EditTree(String s) {
		this.root = new Node('x');
		this.root.buildStringTree(s);
		this.size = this.root.size;
		this.totalRotationCount = 0;
	}

/**
	 * Make this tree be a copy of e, with all new nodes, but the same shape and
	 * contents.
	 * 
	 * @param e
	 */
	public EditTree(EditTree e) {
		if (e.root != Node.NULL_NODE) {
			this.root = new Node();
			this.root.editTreeCopy(e.root);
			this.size = e.size;
			this.totalRotationCount = e.totalRotationCount;
		} else {
			this.root = Node.NULL_NODE;
			this.size = 0;
			this.totalRotationCount = 0;
		}

}

/**
	 * 
	 * @return the height of this tree
	 */
	public int height() {
		return this.root.height; 
	}

/**
	 * 
	 * returns the total number of rotations done in this tree since it was
	 * created. A double rotation counts as two.
	 * 
	 * @return number of rotations since tree was created.
	 */
	public int totalRotationCount() {
		return this.totalRotationCount;
	}

/**
	 * return the string produced by an inorder traversal of this tree
	 */
	@Override
	public String toString() {
		if (this.root == Node.NULL_NODE) {
			return "";
		}
		return this.root.toString();
	}

/**
	 * 
	 * @param pos
	 *            position in the tree
	 * @return the character at that position
	 * @throws IndexOutOfBoundsException
	 */
	public char get(int pos) throws IndexOutOfBoundsException {
		if (pos < 0 || pos >= this.size || this.root == Node.NULL_NODE) {
			throw new IndexOutOfBoundsException();
		}
		return this.root.get(pos).element;
	}

/**
	 * 
	 * @param c
	 *            character to add to the end of this tree.
	 */
	public void add(char c) {
		if (this.root == Node.NULL_NODE) {
			this.root = new Node(c);
			this.size++;
		} else {
			this.add(c, this.size);
		}
	}

/**
	 * 
	 * @param c
	 *            character to add
	 * @param pos
	 *            character added in this inorder position
	 * @throws IndexOutOfBoundsException
	 *             id pos is negative or too large for this tree
	 */
	public void add(char c, int pos) throws IndexOutOfBoundsException {
		if (pos < 0 || pos > this.size) {
			throw new IndexOutOfBoundsException();
		}
		if (this.root == Node.NULL_NODE) {
			this.root = new Node(c);
		} else {
			this.root.add(c, pos, this);
		}
		this.size++;
	}

/**
	 * 
	 * @return the number of nodes in this tree
	 */
	public int size() {
		return this.size;
	}

/**
	 * 
	 * @param pos
	 *            position of character to delete from this tree
	 * @return the character that is deleted
	 * @throws IndexOutOfBoundsException
	 */
	public char delete(int pos) throws IndexOutOfBoundsException {
		if (pos < 0 || pos >= this.size || this.root == Node.NULL_NODE) {
			throw new IndexOutOfBoundsException();
		}
		if (this.size == 1) {
			char temp = this.root.element;
			this.root = Node.NULL_NODE;
			this.size = 0;
			return temp;
		}
		return this.root.get(pos).delete(this);
	}

/**
	 * This method operates in O(length*log N), where N is the size of this
	 * tree.
	 * 
	 * @param pos
	 *            location of the beginning of the string to retrieve
	 * @param length
	 *            length of the string to retrieve
	 * @return string of length that starts in position pos
	 * @throws IndexOutOfBoundsException
	 *             unless both pos and pos+length-1 are legitimate indexes
	 *             within this tree.
	 */
	public String get(int pos, int length) throws IndexOutOfBoundsException {
		if (pos < 0 || (pos + length) > this.size) {
			throw new IndexOutOfBoundsException("The index is out of bounds!");
		}
		Node start = this.root.get(pos);
		return start.getString(length);
	}

/**
	 * This method is provided for you, and should not need to be changed. If
	 * split() and concatenate() are O(log N) operations as required, delete
	 * should also be O(log N)
	 * 
	 * @param start
	 *            position of beginning of string to delete
	 * 
	 * @param length
	 *            length of string to delete
	 * @return an EditTree containing the deleted string
	 * @throws IndexOutOfBoundsException
	 *             unless both start and start+length-1 are in range for this
	 *             tree.
	 */
	public EditTree delete(int start, int length)
			throws IndexOutOfBoundsException {
		if (start < 0 || start + length >= this.size())
			throw new IndexOutOfBoundsException(
					(start < 0) ? "negative first argument to delete"
							: "delete range extends past end of string");
		EditTree t2 = this.split(start);
		EditTree t3 = t2.split(length);
		this.concatenate(t3);
		return t2;
	}

/**
	 * Append (in time proportional to the log of the size of the larger tree)
	 * the contents of the other tree to this one. Other should be made empty
	 * after this operation.
	 * 
	 * @param other
	 * @throws IllegalArgumentException
	 *             if this == other
	 */
	public void concatenate(EditTree other) throws IllegalArgumentException {

if (this == other) {
			throw new IllegalArgumentException("Invalid request!");
		}
		if (other.root == Node.NULL_NODE) {
			// do nothing
		}
		// If the original tree was empty it is just replaced with the other
		// tree.
		else if (this.root == Node.NULL_NODE) {
			this.root = new Node();
			this.root = other.root;
			this.size = other.size;
			other.size = 0;
			other.root = Node.NULL_NODE;
		}
		// If the trees are both of size 1 then the new tree is just the old
		// with the root's right the old root of the other tree.
		else if (this.size == 1 && other.size == 1) {
			this.root.right = other.root;
			this.root.right.parent = this.root;
			this.root.size++;
			this.size++;
			other.size = 0;
			other.root = Node.NULL_NODE;
		}
		// Traverses down to the far left leaf of the tree being concatenated to
		// the old tree and calls the Node concatenate method at that node.
		else {
			Node current = other.root;
			// Finds the far left leaf and adjusts sizes and ranks accordingly.
			while (current.left != Node.NULL_NODE) {
				current.rank--;
				current.size--;
				current = current.left;
			}
			this.root.concatenate(other.root, current);
			if (this.root.parent != Node.NULL_NODE) {
				this.root = this.root.parent;
			}
			// Fixes the trees' sizes and empties the other tree.
			this.size = this.size + other.size;
			other.size = 0;
			other.root = Node.NULL_NODE;
		}
	}

/**
	 * This operation must be done in time proportional to the height of this
	 * tree.
	 * 
	 * @param pos
	 *            where to split this tree
	 * @return a new tree containing all of the elements of this tree whose
	 *         positions are >= position. Their nodes are removed from this
	 *         tree.
	 * @throws IndexOutOfBoundsException
	 */
	public EditTree split(int pos) throws IndexOutOfBoundsException {
		if (pos < 0 || pos >= this.toString().length()) {
			throw new IndexOutOfBoundsException(
					"Invalid request!");
		}
		EditTree[] trees = new EditTree[2];
		trees = this.root.get(pos).split();

this.root = trees[0].root;
		if (this.root != Node.NULL_NODE) {
			this.setTreeSize();
		}
		if (trees[1].root != Node.NULL_NODE) {
			trees[1].setTreeSize();
		}

return trees[1];

}

/**
	 * Don't worry if you can't do this one efficiently.
	 * 
	 * @param s
	 *            the string to look for
	 * @return the position in this tree of the first occurrence of s; -1 if s
	 *         does not occur
	 */
	public int find(String s) {
		if (!this.toString().contains(s)) {
			return -1;
		}
		return this.toString().indexOf(s);
	}

/**
	 * 
	 * @param s
	 *            the string to search for
	 * @param pos
	 *            the position in the tree to begin the search
	 * @return the position in this tree of the first occurrence of s that does
	 *         not occur before position pos; -1 if s does not occur
	 */
	public int find(String s, int pos) {
		String current = this.toString().substring(pos);
		if (!current.contains(s)) {
			return -1;
		}
		return current.indexOf(s) + pos;
	}

/**
	 * @return The root of this tree.
	 */
	public Node getRoot() {
		return this.root;
	}

/**
	 * Sets the tree size.
	 */
	public void setTreeSize() {
		this.size = this.root.left.size + this.root.right.size + 1;
	}

}

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.