Class RedBlackTree<K,​V>


  • public class RedBlackTree<K,​V>
    extends java.lang.Object
    • Field Detail

      • ordering

        private final java.util.Comparator<? super K> ordering
      • 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

      • getOrdering

        public java.util.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)
      • iterator

        public java.util.Iterator<Pair<K,​V>> iterator​(Tree<K,​V> tree)
      • keysIterator

        public java.util.Iterator<K> keysIterator​(Tree<K,​V> tree)
      • valuesIterator

        public java.util.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)
      • delLeft

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

        private Tree<K,​V> delRight​(Tree<K,​V> tree,
                                         K k)
      • 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)
      • 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)