org.apache.directory.server.core.avltree.avl

Class AvlTreeSet<T extends java.lang.Comparable<T>>

java.lang.Object

org.apache.directory.server.core.avltree.avl.AvlTreeSet<T>

All Implemented Interfaces:

java.lang.Iterable<T>

public class AvlTreeSet<T extends java.lang.Comparable<T>>
extends java.lang.Object
implements java.lang.Iterable<T>

AVL Tree Set

Field Summary

Fields

Modifier and Type	Field and Description
private java.util.Stack<AvlNode<T>>	freeList
private int	size
private AvlNode<T>	tree
private boolean	useFreeList

Constructor Summary

Constructors

Constructor and Description
AvlTreeSet()
AvlTreeSet(boolean useFreeList)

Method Summary

Modifier and Type	Method and Description
private static <T extends java.lang.Comparable<T>> AvlNode<T>	bigLeftRotation(AvlNode<T> node)
private static <T extends java.lang.Comparable<T>> AvlNode<T>	bigRightRotation(AvlNode<T> node)
boolean	contains(T value)
int	height()
boolean	insert(T value)
java.util.Iterator<T>	iterator()
private AvlNode<T>	newNode(AvlNode<T> parent, T value)
private void	rebalanceUp(AvlNode<T> node)
private void	recycleNode(AvlNode<T> node)
boolean	remove(T value)
int	size()
private static <T extends java.lang.Comparable<T>> AvlNode<T>	smallLeftRotation(AvlNode<T> node)
private static <T extends java.lang.Comparable<T>> AvlNode<T>	smallRightRotation(AvlNode<T> node)
private static <T extends java.lang.Comparable<T>> void	updateHeight(AvlNode<T> node)

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

tree

private AvlNode<T extends java.lang.Comparable<T>> tree

size

private int size

useFreeList

private final boolean useFreeList

freeList

private java.util.Stack<AvlNode<T extends java.lang.Comparable<T>>> freeList

Constructor Detail

AvlTreeSet

public AvlTreeSet()

AvlTreeSet

public AvlTreeSet(boolean useFreeList)

Method Detail

height

public final int height()

size

public final int size()

iterator

public final java.util.Iterator<T> iterator()

Specified by:

iterator in interface java.lang.Iterable<T extends java.lang.Comparable<T>>

insert

public final boolean insert(T value)

newNode

private AvlNode<T> newNode(AvlNode<T> parent,
                           T value)

recycleNode

private void recycleNode(AvlNode<T> node)

rebalanceUp

private void rebalanceUp(AvlNode<T> node)

remove

public final boolean remove(T value)

contains

public final boolean contains(T value)

updateHeight

private static <T extends java.lang.Comparable<T>> void updateHeight(AvlNode<T> node)

smallLeftRotation

private static <T extends java.lang.Comparable<T>> AvlNode<T> smallLeftRotation(AvlNode<T> node)

smallRightRotation

private static <T extends java.lang.Comparable<T>> AvlNode<T> smallRightRotation(AvlNode<T> node)

bigLeftRotation

private static <T extends java.lang.Comparable<T>> AvlNode<T> bigLeftRotation(AvlNode<T> node)

bigRightRotation

private static <T extends java.lang.Comparable<T>> AvlNode<T> bigRightRotation(AvlNode<T> node)