Package io.vavr.collection
Interface RedBlackTree<T>
- Type Parameters:
T
- Component type
- All Superinterfaces:
Iterable<T>
- All Known Implementing Classes:
RedBlackTreeModule.Empty
,RedBlackTreeModule.Node
Purely functional Red/Black Tree, inspired by Kazu Yamamoto's Haskell implementation.
Based on
- Chris Okasaki, "Red-Black Trees in a Functional Setting", Journal of Functional Programming, 9(4), pp 471-477, July 1999
- Stefan Kahrs, "Red-black trees with types", Journal of functional programming, 11(04), pp 425-432, July 2001
-
Nested Class Summary
Nested Classes -
Method Summary
Modifier and TypeMethodDescriptioncolor()
Return theRedBlackTree.Color
of this Red/Black Tree node.Returns the underlyingComparator
of this RedBlackTree.boolean
Checks, if thisRedBlackTree
contains the givenvalue
.default RedBlackTree
<T> Deletes a value from this RedBlackTree.default RedBlackTree
<T> difference
(RedBlackTree<T> tree) static <T> RedBlackTree
<T> empty
(Comparator<? super T> comparator) 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.default RedBlackTree
<T> Inserts a new value into this tree.default RedBlackTree
<T> intersection
(RedBlackTree<T> tree) boolean
isEmpty()
Checks if thisRedBlackTree
is empty, i.e.iterator()
Returns an Iterator that iterates elements in the order induced by the underlying Comparator.left()
Returns the left child if this is a non-empty node, otherwise throws.max()
Returns the maximum element of this tree according to the underlying comparator.min()
Returns the minimum element of this tree according to the underlying comparator.static <T> RedBlackTree
<T> of
(Comparator<? super T> comparator, T value) static <T> RedBlackTree
<T> of
(Comparator<? super T> comparator, T... values) static <T> RedBlackTree
<T> ofAll
(Comparator<? super T> comparator, Iterable<? extends T> values) right()
Returns the right child if this is a non-empty node, otherwise throws.int
size()
Returns the size of this tree.toString()
Returns a Lisp like representation of this tree.default RedBlackTree
<T> union
(RedBlackTree<T> tree) Adds all of the elements of the giventree
to this tree, if not already present.value()
Returns the value of the current tree node or throws if this is empty.Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Method Details
-
empty
-
of
-
of
-
ofAll
-
insert
Inserts a new value into this tree.- Parameters:
value
- A value.- Returns:
- A new tree if this tree does not contain the given value, otherwise the same tree instance.
-
color
RedBlackTree.Color color()Return theRedBlackTree.Color
of this Red/Black Tree node.An empty node is
BLACK
by definition.- Returns:
- Either
RED
orBLACK
.
-
comparator
Comparator<T> comparator()Returns the underlyingComparator
of this RedBlackTree.- Returns:
- The comparator.
-
contains
Checks, if thisRedBlackTree
contains the givenvalue
.- Parameters:
value
- A value.- Returns:
- true, if this tree contains the value, false otherwise.
-
delete
Deletes a value from this RedBlackTree.- Parameters:
value
- A value- Returns:
- A new RedBlackTree if the value is present, otherwise this.
-
difference
-
emptyInstance
RedBlackTree<T> emptyInstance()Returns the empty instance of this RedBlackTree.- Returns:
- An empty ReadBlackTree
-
find
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.
- 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.
-
intersection
-
isEmpty
boolean isEmpty()Checks if thisRedBlackTree
is empty, i.e. an instance ofLeaf
.- Returns:
- true, if it is empty, false otherwise.
-
left
RedBlackTree<T> left()Returns the left child if this is a non-empty node, otherwise throws.- Returns:
- The left child.
- Throws:
UnsupportedOperationException
- if this RedBlackTree is empty
-
max
Returns the maximum element of this tree according to the underlying comparator.- Returns:
- Some element, if this is not empty, otherwise None
-
min
Returns the minimum element of this tree according to the underlying comparator.- Returns:
- Some element, if this is not empty, otherwise None
-
right
RedBlackTree<T> right()Returns the right child if this is a non-empty node, otherwise throws.- Returns:
- The right child.
- Throws:
UnsupportedOperationException
- if this RedBlackTree is empty
-
size
int size()Returns the size of this tree.- Returns:
- the number of nodes of this tree and 0 if this is the empty tree
-
union
Adds all of the elements of the giventree
to this tree, if not already present.- Parameters:
tree
- The RedBlackTree to form the union with.- Returns:
- A new RedBlackTree that contains all distinct elements of this and the given
tree
.
-
value
T value()Returns the value of the current tree node or throws if this is empty.- Returns:
- The value.
- Throws:
NoSuchElementException
- if this is the empty node.
-
iterator
Returns an Iterator that iterates elements in the order induced by the underlying Comparator.Internally an in-order traversal of the RedBlackTree is performed.
Example:
Iteration order: 1, 2, 3, 4, 5, 6, 74 / \ 2 6 / \ / \ 1 3 5 7
-
toString
String toString()Returns a Lisp like representation of this tree.
-