Package io.vavr.collection
Class RedBlackTreeModule.Node<T>
- java.lang.Object
-
- io.vavr.collection.RedBlackTreeModule.Node<T>
-
- Type Parameters:
T
- Component type
- All Implemented Interfaces:
RedBlackTree<T>
,java.io.Serializable
,java.lang.Iterable<T>
- Enclosing interface:
- RedBlackTreeModule
public static final class RedBlackTreeModule.Node<T> extends java.lang.Object implements RedBlackTree<T>, java.io.Serializable
A non-empty tree node.- See Also:
- Serialized Form
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface io.vavr.collection.RedBlackTree
RedBlackTree.Color
-
-
Field Summary
Fields Modifier and Type Field Description (package private) int
blackHeight
(package private) RedBlackTree.Color
color
(package private) RedBlackTreeModule.Empty<T>
empty
(package private) RedBlackTree<T>
left
(package private) RedBlackTree<T>
right
private static long
serialVersionUID
(package private) int
size
(package private) 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
All Methods Static Methods Instance Methods Concrete Methods 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>,java.lang.Boolean>
blackify(RedBlackTree<T> tree)
RedBlackTree.Color
color()
Return theRedBlackTree.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)
java.util.Comparator<T>
comparator()
Returns the underlyingComparator
of this RedBlackTree.boolean
contains(T value)
Checks, if thisRedBlackTree
contains the givenvalue
.(package private) static <T> Tuple2<? extends RedBlackTree<T>,java.lang.Boolean>
delete(RedBlackTree<T> tree, T value)
private static <T> Tuple3<? extends RedBlackTree<T>,java.lang.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 thisRedBlackTree
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 java.lang.String
toLispString(RedBlackTree<?> tree)
java.lang.String
toString()
Returns a Lisp like representation of this tree.private static <T> Tuple2<RedBlackTreeModule.Node<T>,java.lang.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>,java.lang.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 java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface io.vavr.collection.RedBlackTree
delete, difference, insert, intersection, iterator, max, min, union
-
-
-
-
Field Detail
-
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 Detail
-
Node
Node(RedBlackTree.Color color, int blackHeight, RedBlackTree<T> left, T value, RedBlackTree<T> right, RedBlackTreeModule.Empty<T> empty)
-
-
Method Detail
-
color
public RedBlackTree.Color color()
Description copied from interface:RedBlackTree
Return theRedBlackTree.Color
of this Red/Black Tree node.An empty node is
BLACK
by definition.- Specified by:
color
in interfaceRedBlackTree<T>
- Returns:
- Either
RED
orBLACK
.
-
comparator
public java.util.Comparator<T> comparator()
Description copied from interface:RedBlackTree
Returns the underlyingComparator
of this RedBlackTree.- Specified by:
comparator
in interfaceRedBlackTree<T>
- Returns:
- The comparator.
-
contains
public boolean contains(T value)
Description copied from interface:RedBlackTree
Checks, if thisRedBlackTree
contains the givenvalue
.- Specified by:
contains
in interfaceRedBlackTree<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 interfaceRedBlackTree<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 interfaceRedBlackTree<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 thisRedBlackTree
is empty, i.e. an instance ofLeaf
.- Specified by:
isEmpty
in interfaceRedBlackTree<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 interfaceRedBlackTree<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 interfaceRedBlackTree<T>
- Returns:
- The right child.
-
size
public int size()
Description copied from interface:RedBlackTree
Returns the size of this tree.- Specified by:
size
in interfaceRedBlackTree<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 interfaceRedBlackTree<T>
- Returns:
- The value.
-
toString
public java.lang.String toString()
Description copied from interface:RedBlackTree
Returns a Lisp like representation of this tree.- Specified by:
toString
in interfaceRedBlackTree<T>
- Overrides:
toString
in classjava.lang.Object
- Returns:
- This Tree as Lisp like String.
-
toLispString
private static java.lang.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>,java.lang.Boolean> blackify(RedBlackTree<T> tree)
-
delete
static <T> Tuple2<? extends RedBlackTree<T>,java.lang.Boolean> delete(RedBlackTree<T> tree, T value)
-
deleteMin
private static <T> Tuple3<? extends RedBlackTree<T>,java.lang.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>,java.lang.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>,java.lang.Boolean> unbalancedRight(RedBlackTree.Color color, int blackHeight, RedBlackTree<T> left, T value, RedBlackTree<T> right, RedBlackTreeModule.Empty<T> empty)
-
-