Package io.vavr.collection
Interface RedBlackTree<T>
-
- Type Parameters:
T
- Component type
- All Superinterfaces:
java.lang.Iterable<T>
,java.io.Serializable
- All Known Implementing Classes:
RedBlackTreeModule.Empty
,RedBlackTreeModule.Node
interface RedBlackTree<T> extends java.lang.Iterable<T>, java.io.Serializable
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 Modifier and Type Interface Description static class
RedBlackTree.Color
-
Field Summary
Fields Modifier and Type Field Description static long
serialVersionUID
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Default Methods Modifier and Type Method Description RedBlackTree.Color
color()
Return theRedBlackTree.Color
of this Red/Black Tree node.java.util.Comparator<T>
comparator()
Returns the underlyingComparator
of this RedBlackTree.boolean
contains(T value)
Checks, if thisRedBlackTree
contains the givenvalue
.default RedBlackTree<T>
delete(T value)
Deletes a value from this RedBlackTree.default RedBlackTree<T>
difference(RedBlackTree<T> tree)
static <T> RedBlackTree<T>
empty(java.util.Comparator<? super T> comparator)
RedBlackTree<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.default RedBlackTree<T>
insert(T value)
Inserts a new value into this tree.default RedBlackTree<T>
intersection(RedBlackTree<T> tree)
boolean
isEmpty()
Checks if thisRedBlackTree
is empty, i.e.default Iterator<T>
iterator()
Returns an Iterator that iterates elements in the order induced by the underlying Comparator.RedBlackTree<T>
left()
Returns the left child if this is a non-empty node, otherwise throws.default Option<T>
max()
Returns the maximum element of this tree according to the underlying comparator.default Option<T>
min()
Returns the minimum element of this tree according to the underlying comparator.static <T> RedBlackTree<T>
of(java.util.Comparator<? super T> comparator, T value)
static <T> RedBlackTree<T>
of(java.util.Comparator<? super T> comparator, T... values)
static <T> RedBlackTree<T>
ofAll(java.util.Comparator<? super T> comparator, java.lang.Iterable<? extends T> values)
RedBlackTree<T>
right()
Returns the right child if this is a non-empty node, otherwise throws.int
size()
Returns the size of this tree.java.lang.String
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.T
value()
Returns the value of the current tree node or throws if this is empty.
-
-
-
Field Detail
-
serialVersionUID
static final long serialVersionUID
- See Also:
- Constant Field Values
-
-
Method Detail
-
empty
static <T> RedBlackTree<T> empty(java.util.Comparator<? super T> comparator)
-
of
static <T> RedBlackTree<T> of(java.util.Comparator<? super T> comparator, T value)
-
of
@SafeVarargs static <T> RedBlackTree<T> of(java.util.Comparator<? super T> comparator, T... values)
-
ofAll
static <T> RedBlackTree<T> ofAll(java.util.Comparator<? super T> comparator, java.lang.Iterable<? extends T> values)
-
insert
default RedBlackTree<T> insert(T value)
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
java.util.Comparator<T> comparator()
Returns the underlyingComparator
of this RedBlackTree.- Returns:
- The comparator.
-
contains
boolean contains(T value)
Checks, if thisRedBlackTree
contains the givenvalue
.- Parameters:
value
- A value.- Returns:
- true, if this tree contains the value, false otherwise.
-
delete
default RedBlackTree<T> delete(T value)
Deletes a value from this RedBlackTree.- Parameters:
value
- A value- Returns:
- A new RedBlackTree if the value is present, otherwise this.
-
difference
default RedBlackTree<T> difference(RedBlackTree<T> tree)
-
emptyInstance
RedBlackTree<T> emptyInstance()
Returns the empty instance of this RedBlackTree.- Returns:
- An empty ReadBlackTree
-
find
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.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
default RedBlackTree<T> intersection(RedBlackTree<T> tree)
-
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:
java.lang.UnsupportedOperationException
- if this RedBlackTree is empty
-
max
default Option<T> max()
Returns the maximum element of this tree according to the underlying comparator.- Returns:
- Some element, if this is not empty, otherwise None
-
min
default Option<T> 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:
java.lang.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
default RedBlackTree<T> union(RedBlackTree<T> tree)
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:
java.util.NoSuchElementException
- if this is the empty node.
-
iterator
default Iterator<T> 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
- Specified by:
iterator
in interfacejava.lang.Iterable<T>
-
toString
java.lang.String toString()
Returns a Lisp like representation of this tree.- Overrides:
toString
in classjava.lang.Object
- Returns:
- This Tree as Lisp like String.
-
-