Package org.apache.commons.collections4.list

Class TreeList.AVLNode<E>

java.lang.Object

org.apache.commons.collections4.list.TreeList.AVLNode<E>

Enclosing class:

TreeList<E>

static class TreeList.AVLNode<E>
extends java.lang.Object

Implements an AVLNode which keeps the offset updated.

This node contains the real work. TreeList is just there to implement List. The nodes don't know the index of the object they are holding. They do know however their position relative to their parent node. This allows to calculate the index of a node while traversing the tree.

The Faedelung calculation stores a flag for both the left and right child to indicate if they are a child (false) or a link as in linked list (true).

Field Summary

Fields

Modifier and Type	Field	Description
private int	height	How many levels of left/right are below this one.
private TreeList.AVLNode<E>	left	The left child node or the predecessor if leftIsPrevious.
private boolean	leftIsPrevious	Flag indicating that left reference is not a subtree but the predecessor.
private int	relativePosition	The relative position, root holds absolute position.
private TreeList.AVLNode<E>	right	The right child node or the successor if rightIsNext.
private boolean	rightIsNext	Flag indicating that right reference is not a subtree but the successor.
private E	value	The stored element.

Constructor Summary

Constructors

Modifier	Constructor	Description
private	AVLNode(int relativePosition, E obj, TreeList.AVLNode<E> rightFollower, TreeList.AVLNode<E> leftFollower)	Constructs a new node with a relative position.
private	AVLNode(java.util.Collection<? extends E> coll)	Constructs a new AVL tree from a collection.
private	AVLNode(java.util.Iterator<? extends E> iterator, int start, int end, int absolutePositionOfParent, TreeList.AVLNode<E> prev, TreeList.AVLNode<E> next)	Constructs a new AVL tree from a collection.

Method Summary

Modifier and Type	Method	Description
private TreeList.AVLNode<E>	addAll(TreeList.AVLNode<E> otherTree, int currentSize)	Appends the elements of another tree list to this tree list by efficiently merging the two AVL trees.
private TreeList.AVLNode<E>	balance()	Balances according to the AVL algorithm.
(package private) TreeList.AVLNode<E>	get(int index)	Locate the element with the given index relative to the offset of the parent of this node.
private int	getHeight(TreeList.AVLNode<E> node)	Returns the height of the node or -1 if the node is null.
private TreeList.AVLNode<E>	getLeftSubTree()	Gets the left node, returning null if its a faedelung.
private int	getOffset(TreeList.AVLNode<E> node)	Gets the relative position.
private TreeList.AVLNode<E>	getRightSubTree()	Gets the right node, returning null if its a faedelung.
(package private) E	getValue()	Gets the value.
private int	heightRightMinusLeft()	Returns the height difference right - left
(package private) int	indexOf(java.lang.Object object, int index)	Locate the index that contains the specified object.
(package private) TreeList.AVLNode<E>	insert(int index, E obj)	Inserts a node at the position index.
private TreeList.AVLNode<E>	insertOnLeft(int indexRelativeToMe, E obj)
private TreeList.AVLNode<E>	insertOnRight(int indexRelativeToMe, E obj)
private TreeList.AVLNode<E>	max()	Gets the rightmost child of this node.
private TreeList.AVLNode<E>	min()	Gets the leftmost child of this node.
(package private) TreeList.AVLNode<E>	next()	Gets the next node in the list after this one.
(package private) TreeList.AVLNode<E>	previous()	Gets the node in the list before this one.
private void	recalcHeight()	Sets the height by calculation.
(package private) TreeList.AVLNode<E>	remove(int index)	Removes the node at a given position.
private TreeList.AVLNode<E>	removeMax()
private TreeList.AVLNode<E>	removeMin()
private TreeList.AVLNode<E>	removeSelf()	Removes this node from the tree.
private TreeList.AVLNode<E>	rotateLeft()
private TreeList.AVLNode<E>	rotateRight()
private void	setLeft(TreeList.AVLNode<E> node, TreeList.AVLNode<E> previous)	Sets the left field to the node, or the previous node if that is null
private int	setOffset(TreeList.AVLNode<E> node, int newOffest)	Sets the relative position.
private void	setRight(TreeList.AVLNode<E> node, TreeList.AVLNode<E> next)	Sets the right field to the node, or the next node if that is null
(package private) void	setValue(E obj)	Sets the value.
(package private) void	toArray(java.lang.Object[] array, int index)	Stores the node and its children into the array specified.
java.lang.String	toString()	Used for debugging.

Methods inherited from class java.lang.Object

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

Field Detail

left

private TreeList.AVLNode<E> left

The left child node or the predecessor if leftIsPrevious.

leftIsPrevious

private boolean leftIsPrevious

Flag indicating that left reference is not a subtree but the predecessor.

right

private TreeList.AVLNode<E> right

The right child node or the successor if rightIsNext.

rightIsNext

private boolean rightIsNext

Flag indicating that right reference is not a subtree but the successor.

height

private int height

How many levels of left/right are below this one.

relativePosition

private int relativePosition

The relative position, root holds absolute position.

value

private E value

The stored element.

Constructor Detail

AVLNode

private AVLNode(int relativePosition,
                E obj,
                TreeList.AVLNode<E> rightFollower,
                TreeList.AVLNode<E> leftFollower)

Constructs a new node with a relative position.

Parameters:

relativePosition - the relative position of the node

obj - the value for the node

rightFollower - the node with the value following this one

leftFollower - the node with the value leading this one

AVLNode

private AVLNode(java.util.Collection<? extends E> coll)

Constructs a new AVL tree from a collection.

The collection must be nonempty.

Parameters:

coll - a nonempty collection

AVLNode

private AVLNode(java.util.Iterator<? extends E> iterator,
                int start,
                int end,
                int absolutePositionOfParent,
                TreeList.AVLNode<E> prev,
                TreeList.AVLNode<E> next)

Constructs a new AVL tree from a collection.

This is a recursive helper for AVLNode(Collection). A call to this method will construct the subtree for elements start through end of the collection, assuming the iterator e already points at element start.

Parameters:

iterator - an iterator over the collection, which should already point to the element at index start within the collection

start - the index of the first element in the collection that should be in this subtree

end - the index of the last element in the collection that should be in this subtree

absolutePositionOfParent - absolute position of this node's parent, or 0 if this node is the root

prev - the AVLNode corresponding to element (start - 1) of the collection, or null if start is 0

next - the AVLNode corresponding to element (end + 1) of the collection, or null if end is the last element of the collection

Method Detail

getValue

E getValue()

Gets the value.

Returns:

the value of this node

setValue

void setValue(E obj)

Sets the value.

Parameters:

obj - the value to store

get

TreeList.AVLNode<E> get(int index)

Locate the element with the given index relative to the offset of the parent of this node.

indexOf

int indexOf(java.lang.Object object,
            int index)

Locate the index that contains the specified object.

toArray

void toArray(java.lang.Object[] array,
             int index)

Stores the node and its children into the array specified.

Parameters:

array - the array to be filled

index - the index of this node

next

TreeList.AVLNode<E> next()

Gets the next node in the list after this one.

Returns:

the next node

previous

TreeList.AVLNode<E> previous()

Gets the node in the list before this one.

Returns:

the previous node

insert

TreeList.AVLNode<E> insert(int index,
                           E obj)

Inserts a node at the position index.

Parameters:

index - is the index of the position relative to the position of the parent node.

obj - is the object to be stored in the position.

insertOnLeft

private TreeList.AVLNode<E> insertOnLeft(int indexRelativeToMe,
                                         E obj)

insertOnRight

private TreeList.AVLNode<E> insertOnRight(int indexRelativeToMe,
                                          E obj)

getLeftSubTree

private TreeList.AVLNode<E> getLeftSubTree()

Gets the left node, returning null if its a faedelung.

getRightSubTree

private TreeList.AVLNode<E> getRightSubTree()

Gets the right node, returning null if its a faedelung.

max

private TreeList.AVLNode<E> max()

Gets the rightmost child of this node.

Returns:

the rightmost child (greatest index)

min

private TreeList.AVLNode<E> min()

Gets the leftmost child of this node.

Returns:

the leftmost child (smallest index)

remove

TreeList.AVLNode<E> remove(int index)

Removes the node at a given position.

Parameters:

index - is the index of the element to be removed relative to the position of the parent node of the current node.

removeMax

private TreeList.AVLNode<E> removeMax()

removeMin

private TreeList.AVLNode<E> removeMin()

removeSelf

private TreeList.AVLNode<E> removeSelf()

Removes this node from the tree.

Returns:

the node that replaces this one in the parent

balance

private TreeList.AVLNode<E> balance()

Balances according to the AVL algorithm.

getOffset

private int getOffset(TreeList.AVLNode<E> node)

Gets the relative position.

setOffset

private int setOffset(TreeList.AVLNode<E> node,
                      int newOffest)

Sets the relative position.

recalcHeight

private void recalcHeight()

Sets the height by calculation.

getHeight

private int getHeight(TreeList.AVLNode<E> node)

Returns the height of the node or -1 if the node is null.

heightRightMinusLeft

private int heightRightMinusLeft()

Returns the height difference right - left

rotateLeft

private TreeList.AVLNode<E> rotateLeft()

rotateRight

private TreeList.AVLNode<E> rotateRight()

setLeft

private void setLeft(TreeList.AVLNode<E> node,
                     TreeList.AVLNode<E> previous)

Sets the left field to the node, or the previous node if that is null

Parameters:

node - the new left subtree node

previous - the previous node in the linked list

setRight

private void setRight(TreeList.AVLNode<E> node,
                      TreeList.AVLNode<E> next)

Sets the right field to the node, or the next node if that is null

Parameters:

node - the new left subtree node

next - the next node in the linked list

addAll

private TreeList.AVLNode<E> addAll(TreeList.AVLNode<E> otherTree,
                                   int currentSize)

Appends the elements of another tree list to this tree list by efficiently merging the two AVL trees. This operation is destructive to both trees and runs in O(log(m + n)) time.

Parameters:

otherTree - the root of the AVL tree to merge with this one

currentSize - the number of elements in this AVL tree

Returns:

the root of the new, merged AVL tree

toString

public java.lang.String toString()

Used for debugging.

Overrides:

toString in class java.lang.Object