edu.cmu.emulator.event
Class ESplayTree

java.lang.Object
  edu.cmu.emulator.event.ESplayTree

public class ESplayTree
extends Object

Implements a top-down splay tree. Note that all "matching" is based on the compareTo method.

Author:

Mark Allen Weiss

Field Summary

private EBNodeFarm	ebnFarm
private static EBinaryNode	header
private static EBinaryNode	newNode
private static EBinaryNode	nullNode
private EBinaryNode	root

Constructor Summary

ESplayTree()
Construct the tree.

Method Summary

EmuEvent	find(EmuEvent x) Find an item in the tree.
EmuEvent	findMax() Find the largest item in the tree.
EmuEvent	findMin() Find the smallest item in the tree.
int	getSize()
private int	getSize(EBinaryNode t)
void	insert(EmuEvent x) Insert into the tree.
boolean	isEmpty() Test if the tree is logically empty.
void	makeEmpty() Make the tree logically empty.
void	printTree() Print the tree contents in sorted order.
private void	printTree(EBinaryNode t) Internal method to print a subtree in sorted order.
void	remove(EmuEvent x) Remove from the tree.
EmuEvent	removeMin()
(package private) static EBinaryNode	rotateWithLeftChild(EBinaryNode k2) Rotate binary tree node with left child.
(package private) static EBinaryNode	rotateWithRightChild(EBinaryNode k1) Rotate binary tree node with right child.
private EBinaryNode	splay(EmuEvent x, EBinaryNode t) Internal method to perform a top-down splay.
ArrayList	toArrayList()
private void	toArrayList(EBinaryNode t, ArrayList aList)

Methods inherited from class java.lang.Object

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

Field Detail

ebnFarm

private EBNodeFarm ebnFarm

root

private EBinaryNode root

nullNode

private static EBinaryNode nullNode

newNode

private static EBinaryNode newNode

header

private static EBinaryNode header

Constructor Detail

ESplayTree

public ESplayTree()

Construct the tree.

Method Detail

insert

public final void insert(EmuEvent x)

Insert into the tree.

Parameters:

x - the item to insert.

remove

public final void remove(EmuEvent x)

Remove from the tree.

Parameters:

x - the item to remove.

findMin

public final EmuEvent findMin()

Find the smallest item in the tree. Not the most efficient implementation (uses two passes), but has correct amortized behavior. A good alternative is to first call Find with parameter smaller than any item in the tree, then call findMin.

Returns:

the smallest item or null if empty.

removeMin

public final EmuEvent removeMin()

findMax

public final EmuEvent findMax()

Find the largest item in the tree. Not the most efficient implementation (uses two passes), but has correct amortized behavior. A good alternative is to first call Find with parameter larger than any item in the tree, then call findMax.

Returns:

the largest item or null if empty.

find

public final EmuEvent find(EmuEvent x)

Find an item in the tree.

Parameters:

x - the item to search for.

Returns:

the matching item or null if not found.

makeEmpty

public final void makeEmpty()

Make the tree logically empty.

isEmpty

public final boolean isEmpty()

Test if the tree is logically empty.

Returns:

true if empty, false otherwise.

printTree

public final void printTree()

Print the tree contents in sorted order.

splay

private final EBinaryNode splay(EmuEvent x,
                                EBinaryNode t)

Internal method to perform a top-down splay. The last accessed node becomes the new root.

Parameters:

x - the target item to splay around.

t - the root of the subtree to splay.

Returns:

the subtree after the splay.

rotateWithLeftChild

static final EBinaryNode rotateWithLeftChild(EBinaryNode k2)

Rotate binary tree node with left child.

rotateWithRightChild

static final EBinaryNode rotateWithRightChild(EBinaryNode k1)

Rotate binary tree node with right child.

printTree

private final void printTree(EBinaryNode t)

Internal method to print a subtree in sorted order. WARNING: This is prone to running out of stack space.

Parameters:

t - the node that roots the tree.

toArrayList

public final ArrayList toArrayList()

toArrayList

private final void toArrayList(EBinaryNode t,
                               ArrayList aList)

getSize

public final int getSize()

getSize

private final int getSize(EBinaryNode t)