org.eclipse.eavp.viz.service.widgets

Class BinarySearchTree

java.lang.Object

org.eclipse.eavp.viz.service.widgets.BinarySearchTree

public class BinarySearchTree
extends java.lang.Object

This class provides a binary search tree of doubles that can be used to find the nearest value in the tree to a specified value in O(log(n)) time. This functionality is totally unique when compared to TreeSets, which can only tell if a value is in the tree but cannot find the nearest value.

This is useful when dealing with user input that may not be exact, as it effectively clamps the input value to the nearest value in the tree.

Note: This tree structure does not currently support inserting or removing values. The tree's contents are strictly tied to a list of input values supplied to the constructor.

Author:

Jordan

Constructor Summary

Constructors

Constructor and Description
BinarySearchTree(java.util.List<java.lang.Double> contents) The default constructor.

Method Summary

Modifier and Type	Method and Description
int	findNearestIndex(double d) Finds the index of the value in the tree closest to the specified value.
double	findNearestValue(double d) Finds the value in the tree closest to the specified value.
double	get(int i) Gets the item at the specified index.
int	size() Gets the size of the tree.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BinarySearchTree

public BinarySearchTree(java.util.List<java.lang.Double> contents)
                 throws java.lang.NullPointerException,
                        java.lang.IllegalArgumentException

The default constructor. Creates a binary search tree from the specified list.

Parameters:

contents - The list of numbers from which to create a binary tree.

Throws:

java.lang.NullPointerException - If the specified list is null.

java.lang.IllegalArgumentException - If the specified list contains zero non-null values.

Method Detail

findNearestIndex

public int findNearestIndex(double d)

Finds the index of the value in the tree closest to the specified value.

Parameters:

d - The value to search for in the tree.

Returns:

The index of the element in the tree closest to the value.

findNearestValue

public double findNearestValue(double d)

Finds the value in the tree closest to the specified value.

Parameters:

d - The value to search for in the tree.

Returns:

The value in the tree closest to the specified value.

get

public double get(int i)
           throws java.lang.IndexOutOfBoundsException

Gets the item at the specified index. Note that the tree contains the times sorted in ascending order.

Parameters:

i - The index of the requested element in the tree.

Returns:

The stored value.

Throws:

java.lang.IndexOutOfBoundsException - If the specified index is invalid.

size

public int size()

Gets the size of the tree. This will always be at least 1.

Returns:

The size of the tree.