Package org.jungrapht.visualization.layout.algorithms.eiglsperger

Class InsertionOrderSplayTree<T>

java.lang.Object

org.jungrapht.visualization.layout.algorithms.eiglsperger.InsertionOrderSplayTree<T>

Type Parameters:

T - key type that is stored in the tree

public class InsertionOrderSplayTree<T>
extends Object

A splay tree for items that are not Comparable. There is no 'insert' method, any new item is appended to the right side of the SplayTree by first finding the 'max' (farthest right), splaying to it, and adding the new Node as its right child

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	InsertionOrderSplayTree.Iterator<V>
static class	InsertionOrderSplayTree.Node<T>

Field Summary

Fields

Modifier and Type	Field	Description
protected InsertionOrderSplayTree.Node<T>	root

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	InsertionOrderSplayTree()
protected	InsertionOrderSplayTree(InsertionOrderSplayTree.Node<T> root)

Method Summary

Modifier and Type	Method	Description
void	append(T key)
boolean	contains(InsertionOrderSplayTree.Node<T> element)
boolean	contains(T value)
static <T> InsertionOrderSplayTree<T>	create()
static <T> InsertionOrderSplayTree<T>	create(InsertionOrderSplayTree.Node<T> root)
void	erase(T key)
InsertionOrderSplayTree.Node<T>	find(int k)
InsertionOrderSplayTree.Node<T>	find(InsertionOrderSplayTree.Node<T> node)
InsertionOrderSplayTree.Node<T>	find(T key)
int	height()
static <T> int	height(InsertionOrderSplayTree.Node<T> node)
void	join(InsertionOrderSplayTree<T> joiner)
static <T> InsertionOrderSplayTree<T>	join(Pair<InsertionOrderSplayTree<T>> trees)
InsertionOrderSplayTree.Node<T>	max()
InsertionOrderSplayTree.Node<T>	min()
protected List<InsertionOrderSplayTree.Node<T>>	nodes()
int	pos(InsertionOrderSplayTree.Node<T> node)
String	printTree()
String	printTree(String note)
String	printTree(InsertionOrderSplayTree.Node<T> node, int d)
int	size()
void	splay(InsertionOrderSplayTree.Node<T> x)
void	splay(T element)
InsertionOrderSplayTree<T>	split(int position)
static <T> Pair<InsertionOrderSplayTree<T>>	split(InsertionOrderSplayTree<T> tree, int position)	first position elements go in left tree, the rest go in right tree.
static <T> Pair<InsertionOrderSplayTree<T>>	split(InsertionOrderSplayTree<T> tree, T key)	find key, make it the root, left children go in first tree, right children go in second tree.
InsertionOrderSplayTree<T>	split(T key)
String	toString()
void	validate()

Methods inherited from class java.lang.Object

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

Field Detail

root

protected InsertionOrderSplayTree.Node<T> root

Constructor Detail

InsertionOrderSplayTree

protected InsertionOrderSplayTree()

InsertionOrderSplayTree

protected InsertionOrderSplayTree(InsertionOrderSplayTree.Node<T> root)

Method Detail

create

public static <T> InsertionOrderSplayTree<T> create()

create

public static <T> InsertionOrderSplayTree<T> create(InsertionOrderSplayTree.Node<T> root)

splay

public void splay(T element)

splay

public void splay(InsertionOrderSplayTree.Node<T> x)

pos

public int pos(InsertionOrderSplayTree.Node<T> node)

max

public InsertionOrderSplayTree.Node<T> max()

min

public InsertionOrderSplayTree.Node<T> min()

append

public void append(T key)

join

public static <T> InsertionOrderSplayTree<T> join(Pair<InsertionOrderSplayTree<T>> trees)

join

public void join(InsertionOrderSplayTree<T> joiner)

find

public InsertionOrderSplayTree.Node<T> find(int k)

split

public static <T> Pair<InsertionOrderSplayTree<T>> split(InsertionOrderSplayTree<T> tree,
                                                         T key)

find key, make it the root, left children go in first tree, right children go in second tree. key is not in either tree

Type Parameters:

T -

Parameters:

tree -

key -

Returns:

split

public InsertionOrderSplayTree<T> split(T key)

split

public static <T> Pair<InsertionOrderSplayTree<T>> split(InsertionOrderSplayTree<T> tree,
                                                         int position)

first position elements go in left tree, the rest go in right tree. No elements are missin

Type Parameters:

T -

Parameters:

tree -

position -

Returns:

split

public InsertionOrderSplayTree<T> split(int position)

find

public InsertionOrderSplayTree.Node<T> find(InsertionOrderSplayTree.Node<T> node)

find

public InsertionOrderSplayTree.Node<T> find(T key)

erase

public void erase(T key)

size

public int size()

height

public int height()

height

public static <T> int height(InsertionOrderSplayTree.Node<T> node)

contains

public boolean contains(InsertionOrderSplayTree.Node<T> element)

contains

public boolean contains(T value)

printTree

public String printTree()

printTree

public String printTree(InsertionOrderSplayTree.Node<T> node,
                        int d)

printTree

public String printTree(String note)

validate

public void validate()

nodes

protected List<InsertionOrderSplayTree.Node<T>> nodes()

toString

public String toString()

Overrides:

toString in class Object