Class RedBlackTree<K,V>
- java.lang.Object
-
- com.github.andrewoma.dexx.collection.internal.redblack.RedBlackTree<K,V>
-
public class RedBlackTree<K,V> extends java.lang.Object
-
-
Field Summary
Fields Modifier and Type Field Description private static java.util.Comparator
DEFAULT_COMPARATOR
private TreeFactory
factory
private KeyFunction<K,V>
kf
private java.util.Comparator<? super K>
ordering
-
Constructor Summary
Constructors Constructor Description RedBlackTree()
RedBlackTree(TreeFactory factory, java.util.Comparator<? super K> ordering, KeyFunction<K,V> keyFunction)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description Tree<K,V>
append(Tree<K,V> tl, Tree<K,V> tr)
private Tree<K,V>
balance(K x, V xv, Tree<K,V> tl, Tree<K,V> tr)
private Tree<K,V>
balanceLeft(boolean isBlack, K z, V zv, Tree<K,V> l, Tree<K,V> d)
private Tree<K,V>
balanceRight(boolean isBlack, K x, V xv, Tree<K,V> a, Tree<K,V> r)
private Tree<K,V>
balLeft(K x, V xv, Tree<K,V> tl, Tree<K,V> tr)
private Tree<K,V>
balRight(K x, V xv, Tree<K,V> tl, Tree<K,V> tr)
private Tree<K,V>
blacken(Tree<K,V> t)
private Zipper<K,V>
compareDepth(Tree<K,V> left, Tree<K,V> right)
private <E> java.util.List<E>
cons(E value, java.util.List<E> list)
boolean
contains(Tree<K,V> tree, K x)
static int
count(Tree<?,?> tree)
private Tree<K,V>
del(Tree<K,V> tree, K k)
Tree<K,V>
delete(Tree<K,V> tree, K k)
private Tree<K,V>
delLeft(Tree<K,V> tree, K k)
private Tree<K,V>
delRight(Tree<K,V> tree, K k)
private Tree<K,V>
doDrop(Tree<K,V> tree, int n)
private Tree<K,V>
doFrom(Tree<K,V> tree, K from, boolean inclusive)
private Tree<K,V>
doRange(Tree<K,V> tree, K from, boolean fromInclusive, K until, boolean untilInclusive)
private Tree<K,V>
doSlice(Tree<K,V> tree, int from, int until)
private Tree<K,V>
doTake(Tree<K,V> tree, int n)
private Tree<K,V>
doUntil(Tree<K,V> tree, K until, boolean inclusive)
Tree<K,V>
drop(Tree<K,V> tree, int n)
private java.util.List<Tree<K,V>>
findDepth(java.util.List<Tree<K,V>> zipper, int depth)
<U> void
forEach(Tree<K,V> tree, Function<Pair<K,V>,U> f)
Tree<K,V>
from(Tree<K,V> tree, K from, boolean inclusive)
V
get(Tree<K,V> tree, K x)
KeyFunction<K,V>
getKeyFunction()
java.util.Comparator<? super K>
getOrdering()
Tree<K,V>
greatest(Tree<K,V> tree)
private boolean
isBlackTree(Tree<?,?> tree)
boolean
isEmpty(Tree<K,V> tree)
private boolean
isRedTree(Tree<?,?> tree)
java.util.Iterator<Pair<K,V>>
iterator(Tree<K,V> tree)
java.util.Iterator<K>
keysIterator(Tree<K,V> tree)
Tree<K,V>
lookup(Tree<K,V> tree, K x)
private Tree<K,V>
mkTree(boolean isBlack, K k, V v, Tree<K,V> l, Tree<K,V> r)
Tree<K,V>
range(Tree<K,V> tree, K from, boolean fromInclusive, K until, boolean untilInclusive)
private Tree<K,V>
rebalance(Tree<K,V> tree, Tree<K,V> newLeft, Tree<K,V> newRight)
Tree<K,V>
slice(Tree<K,V> tree, int from, int until)
Tree<K,V>
smallest(Tree<K,V> tree)
private Tree<K,V>
subl(Tree<K,V> t)
Tree<K,V>
take(Tree<K,V> tree, int n)
Tree<K,V>
until(Tree<K,V> tree, K key, boolean inclusive)
private java.util.List<Tree<K,V>>
unzip(java.util.List<Tree<K,V>> zipper, boolean leftMost)
private Zipper<K,V>
unzipBoth(Tree<K,V> left, Tree<K,V> right, java.util.List<Tree<K,V>> leftZipper, java.util.List<Tree<K,V>> rightZipper, int smallerDepth)
private Tree<K,V>
upd(Tree<K,V> tree, K k, V v, boolean overwrite)
Tree<K,V>
update(Tree<K,V> tree, K k, V v, boolean overwrite)
private Tree<K,V>
updNth(Tree<K,V> tree, int idx, K k, V v, boolean overwrite)
java.util.Iterator<V>
valuesIterator(Tree<K,V> tree)
-
-
-
Field Detail
-
factory
private final TreeFactory factory
-
ordering
private final java.util.Comparator<? super K> ordering
-
kf
private final KeyFunction<K,V> kf
-
DEFAULT_COMPARATOR
private static final java.util.Comparator DEFAULT_COMPARATOR
-
-
Constructor Detail
-
RedBlackTree
public RedBlackTree()
-
RedBlackTree
public RedBlackTree(TreeFactory factory, java.util.Comparator<? super K> ordering, KeyFunction<K,V> keyFunction)
-
-
Method Detail
-
getKeyFunction
public KeyFunction<K,V> getKeyFunction()
-
getOrdering
public java.util.Comparator<? super K> getOrdering()
-
count
public static int count(Tree<?,?> tree)
-
range
public Tree<K,V> range(Tree<K,V> tree, K from, boolean fromInclusive, K until, boolean untilInclusive)
-
isRedTree
private boolean isRedTree(Tree<?,?> tree)
-
isBlackTree
private boolean isBlackTree(Tree<?,?> tree)
-
balanceRight
private Tree<K,V> balanceRight(boolean isBlack, K x, V xv, Tree<K,V> a, Tree<K,V> r)
-
doRange
private Tree<K,V> doRange(Tree<K,V> tree, K from, boolean fromInclusive, K until, boolean untilInclusive)
-
unzip
private java.util.List<Tree<K,V>> unzip(java.util.List<Tree<K,V>> zipper, boolean leftMost)
-
cons
private <E> java.util.List<E> cons(E value, java.util.List<E> list)
-
unzipBoth
private Zipper<K,V> unzipBoth(Tree<K,V> left, Tree<K,V> right, java.util.List<Tree<K,V>> leftZipper, java.util.List<Tree<K,V>> rightZipper, int smallerDepth)
-
findDepth
private java.util.List<Tree<K,V>> findDepth(java.util.List<Tree<K,V>> zipper, int depth)
-
-