java.lang.Object
com.github.andrewoma.dexx.collection.internal.redblack.RedBlackTree<K,V>

public class RedBlackTree<K,V> extends Object
  • Field Details

  • Constructor Details

  • Method Details

    • getKeyFunction

      public KeyFunction<K,V> getKeyFunction()
    • getOrdering

      public Comparator<? super K> getOrdering()
    • isEmpty

      public boolean isEmpty(Tree<K,V> tree)
    • contains

      public boolean contains(Tree<K,V> tree, K x)
    • get

      public V get(Tree<K,V> tree, K x)
    • lookup

      public Tree<K,V> lookup(Tree<K,V> tree, K x)
    • count

      public static int count(Tree<?,?> tree)
    • update

      public Tree<K,V> update(Tree<K,V> tree, K k, V v, boolean overwrite)
    • delete

      public Tree<K,V> delete(Tree<K,V> tree, K k)
    • range

      public Tree<K,V> range(Tree<K,V> tree, K from, boolean fromInclusive, K until, boolean untilInclusive)
    • from

      public Tree<K,V> from(Tree<K,V> tree, K from, boolean inclusive)
    • until

      public Tree<K,V> until(Tree<K,V> tree, K key, boolean inclusive)
    • drop

      public Tree<K,V> drop(Tree<K,V> tree, int n)
    • take

      public Tree<K,V> take(Tree<K,V> tree, int n)
    • slice

      public Tree<K,V> slice(Tree<K,V> tree, int from, int until)
    • smallest

      public Tree<K,V> smallest(Tree<K,V> tree)
    • greatest

      public Tree<K,V> greatest(Tree<K,V> tree)
    • forEach

      public <U> void forEach(Tree<K,V> tree, Function<Pair<K,V>,U> f)
    • iterator

      public Iterator<Pair<K,V>> iterator(Tree<K,V> tree)
    • keysIterator

      public Iterator<K> keysIterator(Tree<K,V> tree)
    • valuesIterator

      public Iterator<V> valuesIterator(Tree<K,V> tree)
    • isRedTree

      private boolean isRedTree(Tree<?,?> tree)
    • isBlackTree

      private boolean isBlackTree(Tree<?,?> tree)
    • blacken

      private Tree<K,V> blacken(Tree<K,V> t)
    • mkTree

      private Tree<K,V> mkTree(boolean isBlack, K k, V v, Tree<K,V> l, Tree<K,V> r)
    • balanceLeft

      private Tree<K,V> balanceLeft(boolean isBlack, K z, V zv, Tree<K,V> l, Tree<K,V> d)
    • balanceRight

      private Tree<K,V> balanceRight(boolean isBlack, K x, V xv, Tree<K,V> a, Tree<K,V> r)
    • upd

      private Tree<K,V> upd(Tree<K,V> tree, K k, V v, boolean overwrite)
    • updNth

      private Tree<K,V> updNth(Tree<K,V> tree, int idx, K k, V v, boolean overwrite)
    • del

      private Tree<K,V> del(Tree<K,V> tree, K k)
    • balance

      private Tree<K,V> balance(K x, V xv, Tree<K,V> tl, Tree<K,V> tr)
    • subl

      private Tree<K,V> subl(Tree<K,V> t)
    • balLeft

      private Tree<K,V> balLeft(K x, V xv, Tree<K,V> tl, Tree<K,V> tr)
    • balRight

      private Tree<K,V> balRight(K x, V xv, Tree<K,V> tl, Tree<K,V> tr)
    • delLeft

      private Tree<K,V> delLeft(Tree<K,V> tree, K k)
    • delRight

      private Tree<K,V> delRight(Tree<K,V> tree, K k)
    • append

      public Tree<K,V> append(Tree<K,V> tl, Tree<K,V> tr)
    • doFrom

      private Tree<K,V> doFrom(Tree<K,V> tree, K from, boolean inclusive)
    • doUntil

      private Tree<K,V> doUntil(Tree<K,V> tree, K until, boolean inclusive)
    • doRange

      private Tree<K,V> doRange(Tree<K,V> tree, K from, boolean fromInclusive, K until, boolean untilInclusive)
    • doDrop

      private Tree<K,V> doDrop(Tree<K,V> tree, int n)
    • doTake

      private Tree<K,V> doTake(Tree<K,V> tree, int n)
    • doSlice

      private Tree<K,V> doSlice(Tree<K,V> tree, int from, int until)
    • compareDepth

      private Zipper<K,V> compareDepth(Tree<K,V> left, Tree<K,V> right)
    • unzip

      private List<Tree<K,V>> unzip(List<Tree<K,V>> zipper, boolean leftMost)
    • cons

      private <E> List<E> cons(E value, List<E> list)
    • unzipBoth

      private Zipper<K,V> unzipBoth(Tree<K,V> left, Tree<K,V> right, List<Tree<K,V>> leftZipper, List<Tree<K,V>> rightZipper, int smallerDepth)
    • findDepth

      private List<Tree<K,V>> findDepth(List<Tree<K,V>> zipper, int depth)
    • rebalance

      private Tree<K,V> rebalance(Tree<K,V> tree, Tree<K,V> newLeft, Tree<K,V> newRight)