Class RedBlackTreeModule.Node<T>

java.lang.Object

io.vavr.collection.RedBlackTreeModule.Node<T>

Type Parameters:

T - Component type

All Implemented Interfaces:

RedBlackTree<T>, Serializable, Iterable<T>

Enclosing interface:

RedBlackTreeModule

public static final class RedBlackTreeModule.Node<T>
extends Object
implements RedBlackTree<T>, Serializable

A non-empty tree node.

See Also:

• Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from interface RedBlackTree

RedBlackTree.Color

Field Summary

Fields

Modifier and Type	Field	Description
(package private) final int	blackHeight
(package private) final RedBlackTree.Color	color
(package private) final RedBlackTreeModule.Empty<T>	empty
(package private) final RedBlackTree<T>	left
(package private) final RedBlackTree<T>	right
private static final long	serialVersionUID
(package private) final int	size
(package private) final T	value

Constructor Summary

Constructors

Constructor	Description
Node(RedBlackTree.Color color, int blackHeight, RedBlackTree<T> left, T value, RedBlackTree<T> right, RedBlackTreeModule.Empty<T> empty)

Method Summary

Modifier and Type	Method	Description
private static <T> RedBlackTreeModule.Node<T>	balanceLeft(RedBlackTree.Color color, int blackHeight, RedBlackTree<T> left, T value, RedBlackTree<T> right, RedBlackTreeModule.Empty<T> empty)
private static <T> RedBlackTreeModule.Node<T>	balanceRight(RedBlackTree.Color color, int blackHeight, RedBlackTree<T> left, T value, RedBlackTree<T> right, RedBlackTreeModule.Empty<T> empty)
private static <T> Tuple2<? extends RedBlackTree<T>, Boolean>	blackify(RedBlackTree<T> tree)
RedBlackTree.Color	color()	Return the RedBlackTree.Color of this Red/Black Tree node.
(package private) RedBlackTreeModule.Node<T>	color(RedBlackTree.Color color)
(package private) static <T> RedBlackTree<T>	color(RedBlackTree<T> tree, RedBlackTree.Color color)
Comparator<T>	comparator()	Returns the underlying Comparator of this RedBlackTree.
boolean	contains(T value)	Checks, if this RedBlackTree contains the given value.
(package private) static <T> Tuple2<? extends RedBlackTree<T>, Boolean>	delete(RedBlackTree<T> tree, T value)
private static <T> Tuple3<? extends RedBlackTree<T>, Boolean, T>	deleteMin(RedBlackTreeModule.Node<T> node)
RedBlackTreeModule.Empty<T>	emptyInstance()	Returns the empty instance of this RedBlackTree.
Option<T>	find(T value)	Finds the value stored in this tree, if exists, by applying the underlying comparator to the tree elements and the given element.
(package private) static <T> RedBlackTreeModule.Node<T>	insert(RedBlackTree<T> tree, T value)
boolean	isEmpty()	Checks if this RedBlackTree is empty, i.e.
private boolean	isLeaf()
private static boolean	isRed(RedBlackTree<?> tree)
(package private) static <T> RedBlackTree<T>	join(RedBlackTree<T> t1, T value, RedBlackTree<T> t2)
private static <T> RedBlackTreeModule.Node<T>	joinGT(RedBlackTreeModule.Node<T> n1, T value, RedBlackTreeModule.Node<T> n2, int h2)
private static <T> RedBlackTreeModule.Node<T>	joinLT(RedBlackTreeModule.Node<T> n1, T value, RedBlackTreeModule.Node<T> n2, int h1)
RedBlackTree<T>	left()	Returns the left child if this is a non-empty node, otherwise throws.
(package private) static <T> T	maximum(RedBlackTreeModule.Node<T> node)
(package private) static <T> RedBlackTree<T>	merge(RedBlackTree<T> t1, RedBlackTree<T> t2)
private static <T> RedBlackTreeModule.Node<T>	mergeEQ(RedBlackTreeModule.Node<T> n1, RedBlackTreeModule.Node<T> n2)
private static <T> RedBlackTreeModule.Node<T>	mergeGT(RedBlackTreeModule.Node<T> n1, RedBlackTreeModule.Node<T> n2, int h2)
private static <T> RedBlackTreeModule.Node<T>	mergeLT(RedBlackTreeModule.Node<T> n1, RedBlackTreeModule.Node<T> n2, int h1)
(package private) static <T> T	minimum(RedBlackTreeModule.Node<T> node)
RedBlackTree<T>	right()	Returns the right child if this is a non-empty node, otherwise throws.
int	size()	Returns the size of this tree.
(package private) static <T> Tuple2<RedBlackTree<T>, RedBlackTree<T>>	split(RedBlackTree<T> tree, T value)
private static String	toLispString(RedBlackTree<?> tree)
String	toString()	Returns a Lisp like representation of this tree.
private static <T> Tuple2<RedBlackTreeModule.Node<T>, Boolean>	unbalancedLeft(RedBlackTree.Color color, int blackHeight, RedBlackTree<T> left, T value, RedBlackTree<T> right, RedBlackTreeModule.Empty<T> empty)
private static <T> Tuple2<RedBlackTreeModule.Node<T>, Boolean>	unbalancedRight(RedBlackTree.Color color, int blackHeight, RedBlackTree<T> left, T value, RedBlackTree<T> right, RedBlackTreeModule.Empty<T> empty)
T	value()	Returns the value of the current tree node or throws if this is empty.

Methods inherited from class Object

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

Methods inherited from interface Iterable

forEach, spliterator

Methods inherited from interface RedBlackTree

delete, difference, insert, intersection, iterator, max, min, union

Field Details

serialVersionUID

private static final long serialVersionUID

See Also:

• Constant Field Values

color

final RedBlackTree.Color color

blackHeight

final int blackHeight

left

final RedBlackTree<T> left

value

final T value

right

final RedBlackTree<T> right

empty

final RedBlackTreeModule.Empty<T> empty

size

final int size

Constructor Details

Node

Node(RedBlackTree.Color color,
 int blackHeight,
 RedBlackTree<T> left,
 T value,
 RedBlackTree<T> right,
 RedBlackTreeModule.Empty<T> empty)

Method Details

color

public RedBlackTree.Color color()

Description copied from interface: RedBlackTree

Return the RedBlackTree.Color of this Red/Black Tree node.

An empty node is BLACK by definition.

Specified by:

color in interface RedBlackTree<T>

Returns:

Either RED or BLACK.

comparator

public Comparator<T> comparator()

Description copied from interface: RedBlackTree

Returns the underlying Comparator of this RedBlackTree.

Specified by:

comparator in interface RedBlackTree<T>

Returns:

The comparator.

contains

public boolean contains(T value)

Description copied from interface: RedBlackTree

Checks, if this RedBlackTree contains the given value.

Specified by:

contains in interface RedBlackTree<T>

Parameters:

value - A value.

Returns:

true, if this tree contains the value, false otherwise.

emptyInstance

public RedBlackTreeModule.Empty<T> emptyInstance()

Description copied from interface: RedBlackTree

Returns the empty instance of this RedBlackTree.

Specified by:

emptyInstance in interface RedBlackTree<T>

Returns:

An empty ReadBlackTree

find

public Option<T> find(T value)

Description copied from interface: RedBlackTree

Finds the value stored in this tree, if exists, by applying the underlying comparator to the tree elements and the given element.

Especially the value returned may differ from the given value, even if the underlying comparator states that both are equal.

Specified by:

find in interface RedBlackTree<T>

Parameters:

value - A value

Returns:

Some value, if this tree contains a value equal to the given value according to the underlying comparator. Otherwise None.

isEmpty

public boolean isEmpty()

Description copied from interface: RedBlackTree

Checks if this RedBlackTree is empty, i.e. an instance of Leaf.

Specified by:

isEmpty in interface RedBlackTree<T>

Returns:

true, if it is empty, false otherwise.

left

public RedBlackTree<T> left()

Description copied from interface: RedBlackTree

Returns the left child if this is a non-empty node, otherwise throws.

Specified by:

left in interface RedBlackTree<T>

Returns:

The left child.

right

public RedBlackTree<T> right()

Description copied from interface: RedBlackTree

Returns the right child if this is a non-empty node, otherwise throws.

Specified by:

right in interface RedBlackTree<T>

Returns:

The right child.

size

public int size()

Description copied from interface: RedBlackTree

Returns the size of this tree.

Specified by:

size in interface RedBlackTree<T>

Returns:

the number of nodes of this tree and 0 if this is the empty tree

value

public T value()

Description copied from interface: RedBlackTree

Returns the value of the current tree node or throws if this is empty.

Specified by:

value in interface RedBlackTree<T>

Returns:

The value.

toString

public String toString()

Description copied from interface: RedBlackTree

Returns a Lisp like representation of this tree.

Specified by:

toString in interface RedBlackTree<T>

Overrides:

toString in class Object

Returns:

This Tree as Lisp like String.

toLispString

private static String toLispString(RedBlackTree<?> tree)

isLeaf

private boolean isLeaf()

color

RedBlackTreeModule.Node<T> color(RedBlackTree.Color color)

color

static <T> RedBlackTree<T> color(RedBlackTree<T> tree,
 RedBlackTree.Color color)

balanceLeft

private static <T> RedBlackTreeModule.Node<T> balanceLeft(RedBlackTree.Color color,
 int blackHeight,
 RedBlackTree<T> left,
 T value,
 RedBlackTree<T> right,
 RedBlackTreeModule.Empty<T> empty)

balanceRight

private static <T> RedBlackTreeModule.Node<T> balanceRight(RedBlackTree.Color color,
 int blackHeight,
 RedBlackTree<T> left,
 T value,
 RedBlackTree<T> right,
 RedBlackTreeModule.Empty<T> empty)

blackify

private static <T>
Tuple2<? extends RedBlackTree<T>, Boolean> blackify(RedBlackTree<T> tree)

delete

static <T>
Tuple2<? extends RedBlackTree<T>, Boolean> delete(RedBlackTree<T> tree,
 T value)

deleteMin

private static <T>
Tuple3<? extends RedBlackTree<T>, Boolean, T> deleteMin(RedBlackTreeModule.Node<T> node)

insert

static <T> RedBlackTreeModule.Node<T> insert(RedBlackTree<T> tree,
 T value)

isRed

private static boolean isRed(RedBlackTree<?> tree)

join

static <T> RedBlackTree<T> join(RedBlackTree<T> t1,
 T value,
 RedBlackTree<T> t2)

joinGT

private static <T> RedBlackTreeModule.Node<T> joinGT(RedBlackTreeModule.Node<T> n1,
 T value,
 RedBlackTreeModule.Node<T> n2,
 int h2)

joinLT

private static <T> RedBlackTreeModule.Node<T> joinLT(RedBlackTreeModule.Node<T> n1,
 T value,
 RedBlackTreeModule.Node<T> n2,
 int h1)

merge

static <T> RedBlackTree<T> merge(RedBlackTree<T> t1,
 RedBlackTree<T> t2)

mergeEQ

private static <T> RedBlackTreeModule.Node<T> mergeEQ(RedBlackTreeModule.Node<T> n1,
 RedBlackTreeModule.Node<T> n2)

mergeGT

private static <T> RedBlackTreeModule.Node<T> mergeGT(RedBlackTreeModule.Node<T> n1,
 RedBlackTreeModule.Node<T> n2,
 int h2)

mergeLT

private static <T> RedBlackTreeModule.Node<T> mergeLT(RedBlackTreeModule.Node<T> n1,
 RedBlackTreeModule.Node<T> n2,
 int h1)

maximum

static <T> T maximum(RedBlackTreeModule.Node<T> node)

minimum

static <T> T minimum(RedBlackTreeModule.Node<T> node)

split

static <T> Tuple2<RedBlackTree<T>, RedBlackTree<T>> split(RedBlackTree<T> tree,
 T value)

unbalancedLeft

private static <T>
Tuple2<RedBlackTreeModule.Node<T>, Boolean> unbalancedLeft(RedBlackTree.Color color,
 int blackHeight,
 RedBlackTree<T> left,
 T value,
 RedBlackTree<T> right,
 RedBlackTreeModule.Empty<T> empty)

unbalancedRight

private static <T>
Tuple2<RedBlackTreeModule.Node<T>, Boolean> unbalancedRight(RedBlackTree.Color color,
 int blackHeight,
 RedBlackTree<T> left,
 T value,
 RedBlackTree<T> right,
 RedBlackTreeModule.Empty<T> empty)