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>
,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:
-
Nested Class Summary
Nested classes/interfaces inherited from interface io.vavr.collection.RedBlackTree
RedBlackTree.Color
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) final int
(package private) final RedBlackTree.Color
(package private) final RedBlackTreeModule.Empty
<T> (package private) final RedBlackTree
<T> (package private) final RedBlackTree
<T> private static final long
(package private) final int
(package private) final T
-
Constructor Summary
ConstructorsConstructorDescriptionNode
(RedBlackTree.Color color, int blackHeight, RedBlackTree<T> left, T value, RedBlackTree<T> right, RedBlackTreeModule.Empty<T> empty) -
Method Summary
Modifier and TypeMethodDescriptionprivate 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) 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) Returns the underlyingComparator
of this RedBlackTree.boolean
Checks, if thisRedBlackTree
contains the givenvalue
.(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) Returns the empty instance of this RedBlackTree.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) 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) 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) 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) 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 java.lang.Iterable
forEach, spliterator
Methods inherited from interface io.vavr.collection.RedBlackTree
delete, difference, insert, intersection, iterator, max, min, union
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
color
-
blackHeight
final int blackHeight -
left
-
value
-
right
-
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
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
Description copied from interface:RedBlackTree
Returns the underlyingComparator
of this RedBlackTree.- Specified by:
comparator
in interfaceRedBlackTree<T>
- Returns:
- The comparator.
-
contains
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
Description copied from interface:RedBlackTree
Returns the empty instance of this RedBlackTree.- Specified by:
emptyInstance
in interfaceRedBlackTree<T>
- Returns:
- An empty ReadBlackTree
-
find
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
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
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
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
Description copied from interface:RedBlackTree
Returns a Lisp like representation of this tree.- Specified by:
toString
in interfaceRedBlackTree<T>
- Overrides:
toString
in classObject
- Returns:
- This Tree as Lisp like String.
-
toLispString
-
isLeaf
private boolean isLeaf() -
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
-
delete
-
deleteMin
private static <T> Tuple3<? extends RedBlackTree<T>,Boolean, deleteMinT> (RedBlackTreeModule.Node<T> node) -
insert
-
isRed
-
join
-
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
-
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
-
minimum
-
split
-
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)
-