support.convexhull
Class RobotRBTree<K,V>

java.lang.Object
  net.datastructures.LinkedBinaryTree<Entry<K,V>>
      net.datastructures.BinarySearchTree<K,V>
          net.datastructures.RBTree<K,V>
              support.convexhull.RobotRBTree<K,V>

Type Parameters:

K - Key

V - Value

All Implemented Interfaces:

BinaryTree<Entry<K,V>>, Dictionary<K,V>, Tree<Entry<K,V>>

public class RobotRBTree<K,V>
extends RBTree<K,V>

This is a subclass of net.datastructures.RBTree with some additional useful function for implementing Robot. Each 'node', an instance of RBTree.RBNode, is an implementation of Position<Entry<K,V>>.

Nested Class Summary

Nested classes/interfaces inherited from class net.datastructures.RBTree

RBTree.RBNode<K,V>

Nested classes/interfaces inherited from class net.datastructures.BinarySearchTree

BinarySearchTree.BSTEntry<K,V>

Field Summary

static support.convexhull.RobotRBTree.InvalidEntry

BOUNDARY_VIOLATION BOUNDARY_VIOLATION is returned when boundary is violated.

Fields inherited from class net.datastructures.BinarySearchTree

actionPos, C, numEntries

Fields inherited from class net.datastructures.LinkedBinaryTree

root, size

Constructor Summary

RobotRBTree()
Simple constructor

RobotRBTree(Comparator<K> C)
Simple constructor with a Comparator C.

Method Summary

Entry<K,V>	after(Entry<K,V> entry) This takes an Entry and returns the 'next' Entry
Position<Entry<K,V>>	after(Position<Entry<K,V>> current) This returns the Position<Entry<K,V>> which is right after(bigger in Integer case) the current position.
Entry<K,V>	before(Entry<K,V> entry) This takes an Entry and returns the 'previous' Entry
Position<Entry<K,V>>	before(Position<Entry<K,V>> current) This returns the Position<Entry<K,V>> which is right before(bigger in Integer case) the current position.
Entry<K,V>	closestAfter(K key) Takes O(logN) time -- traverses the height of the tree once.
Entry<K,V>	closestBefore(K key) Takes O(logN) time -- traverses the height of the tree once.
Entry<K,V>	first() Takes O(log N) time to traverse the height of the tree where N is the number of locators in the tree and O(logN) is the height of the tree
protected void	inorderPositions(Position<Entry<K,V>> v, PositionList<Position<Entry<K,V>>> pos) takes PositionList and add all elements of the tree in inorder.
Iterator<Entry<K,V>>	iterator()
Entry<K,V>	last() Takes O(log N) time to traverse the height of the tree where N is the number of locators in the tree and O(logN) is the height of the tree

Methods inherited from class net.datastructures.RBTree

createNode, hasRedChild, insert, isPosRed, redChild, remedyDoubleBlack, remedyDoubleRed, remove, setBlack, setColor, setRed, swap, swapColor

Methods inherited from class net.datastructures.BinarySearchTree

addAll, checkEntry, checkKey, entries, entry, find, findAll, insertAtExternal, isEmpty, key, removeExternal, replaceEntry, restructure, size, treeSearch, value

Methods inherited from class net.datastructures.LinkedBinaryTree

addRoot, attach, checkPosition, children, expandExternal, hasLeft, hasRight, insertLeft, insertRight, isExternal, isInternal, isRoot, left, parent, positions, preorderPositions, remove, removeAboveExternal, replace, right, root, sibling, swapElements

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.datastructures.Dictionary

entries, find, findAll, isEmpty, size

Field Detail

BOUNDARY_VIOLATION

public static support.convexhull.RobotRBTree.InvalidEntry BOUNDARY_VIOLATION

BOUNDARY_VIOLATION is returned when boundary is violated. ex) calling 'before' of the smallest element

Constructor Detail

RobotRBTree

public RobotRBTree()

Simple constructor

RobotRBTree

public RobotRBTree(Comparator<K> C)

Simple constructor with a Comparator C.
ex) RobotRBTree rbt = new RobotRBTree(new IntegerComparator());

Parameters:

C - A comparator to be used to compare keys

Method Detail

closestBefore

public Entry<K,V> closestBefore(K key)
                         throws InvalidKeyException

Takes O(logN) time -- traverses the height of the tree once. returns closest Entry which is before(smaller in Integer case) the key.

Parameters:

key -

Returns:

Entry with pair Key, Value of which the key is "closestBefore"

Throws:

InvalidKeyException

closestAfter

public Entry<K,V> closestAfter(K key)
                        throws InvalidKeyException

Takes O(logN) time -- traverses the height of the tree once. returns closest Entry which is after(bigger in Integer case) the key.

Parameters:

key -

Returns:

Entry with pair Key, Value of which the key is "closestAfter"

Throws:

InvalidKeyException

after

public Position<Entry<K,V>> after(Position<Entry<K,V>> current)
                           throws BoundaryViolationException

This returns the Position<Entry<K,V>> which is right after(bigger in Integer case) the current position.

Parameters:

current -

Returns:

the Position<Entry<K,V>> which is right after the current

Throws:

BoundaryViolationException

before

public Position<Entry<K,V>> before(Position<Entry<K,V>> current)
                            throws BoundaryViolationException

This returns the Position<Entry<K,V>> which is right before(bigger in Integer case) the current position.

Parameters:

current -

Returns:

the Position<Entry<K,V>> right before the current

Throws:

BoundaryViolationException

first

public Entry<K,V> first()

Takes O(log N) time to traverse the height of the tree where N is the number of locators in the tree and O(logN) is the height of the tree

Returns:

the first Entry of the tree

last

public Entry<K,V> last()

Takes O(log N) time to traverse the height of the tree where N is the number of locators in the tree and O(logN) is the height of the tree

Returns:

the last Entry of the class

iterator

public Iterator<Entry<K,V>> iterator()

Specified by:

iterator in interface Tree<Entry<K,V>>

Overrides:

iterator in class LinkedBinaryTree<Entry<K,V>>

inorderPositions

protected void inorderPositions(Position<Entry<K,V>> v,
                                PositionList<Position<Entry<K,V>>> pos)
                         throws InvalidPositionException

takes PositionList and add all elements of the tree in inorder.

Overrides:

inorderPositions in class LinkedBinaryTree<Entry<K,V>>

Parameters:

v - root

pos - PositionList to be stored

Throws:

InvalidPositionException

after

public Entry<K,V> after(Entry<K,V> entry)

This takes an Entry and returns the 'next' Entry

Parameters:

entry -

Returns:

the Entry which is right after the 'entry'

before

public Entry<K,V> before(Entry<K,V> entry)

This takes an Entry and returns the 'previous' Entry

Parameters:

entry -

Returns:

the Entry which is right before the 'entry'