Package org.pkl.core.util.paguro

Class RrbTree<E>

java.lang.Object
org.pkl.core.util.paguro.RrbTree<E>
All Implemented Interfaces:
Iterable<E>, Collection<E>, List<E>, SequencedCollection<E>, org.organicdesign.fp.collections.BaseList<E>, org.organicdesign.fp.collections.Sized, org.organicdesign.fp.collections.UnmodCollection<E>, org.organicdesign.fp.collections.UnmodIterable<E>, org.organicdesign.fp.collections.UnmodList<E>, org.organicdesign.fp.collections.UnmodSortedCollection<E>, org.organicdesign.fp.collections.UnmodSortedIterable<E>, org.organicdesign.fp.indent.Indented, org.organicdesign.fp.xform.Transformable<E>
Direct Known Subclasses:
RrbTree.ImRrbt, RrbTree.MutRrbt
public abstract class RrbTree<E> extends Object implements org.organicdesign.fp.collections.BaseList<E>, org.organicdesign.fp.indent.Indented
An RRB Tree is an immutable List (like Clojure's PersistentVector) that also supports random inserts, deletes, and can be split and joined back together in logarithmic time. This is based on the paper, "RRB-Trees: Efficient Immutable Vectors" by Phil Bagwell and Tiark Rompf, with the following differences:
  • The Relaxed nodes can be sized between n/3 and 2n/3 (Bagwell/Rompf specify n and n-1)
  • The Join operation sticks the shorter tree unaltered into the larger tree (except for very small trees which just get concatenated).

Details were filled in from the Cormen, Leiserson, Rivest & Stein Algorithms book entry on B-Trees. Also with an awareness of the Clojure PersistentVector by Rich Hickey. All errors are by Glen Peterson.

History (what little I know):

1972: B-Tree: Rudolf Bayer and Ed McCreight
1998: Purely Functional Data Structures: Chris Okasaki
2007: Clojure's Persistent Vector (and HashMap) implementations: Rich Hickey
2012: RRB-Tree: Phil Bagwell and Tiark Rompf

Compared to other collections (timings summary from 2017-06-11):

  • append() - RrbTree.ImRrbt varies between 90% and 100% of the speed of PersistentVector (biggest difference above 100K). RrbTree.MutRrbt varies between 45% and 80% of the speed of PersistentVector.MutVector (biggest difference from 100 to 1M).
  • get() - varies between 50% and 150% of the speed of PersistentVector (PV wins above 1K) if you build RRB using append(). If you build rrb using random inserts (worst case), it goes from 90% at 10 items down to 15% of the speed of the PV at 1M items.
  • iterate() - is about the same speed as PersistentVector
  • insert(0, item) - beats ArrayList above 1K items (worse than ArrayList below 100 items).
  • insert(random, item) - beats ArrayList above 10K items (worse than ArrayList until then).
  • O(log n) split(), join(), and remove() (not timed yet).

Latest detailed timing results are here.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    RrbTree.ImRrbt<E>
    Immutable version of an RrbTree.
    static class 
    RrbTree.MutRrbt<E>
    Mutable version of an RrbTree.
    protected static interface 
    RrbTree.Node<T>
     
    protected static class 
    RrbTree.SplitNode<T>
    This class is the return type when splitting a node.

    Nested classes/interfaces inherited from interface org.organicdesign.fp.collections.UnmodIterable

    org.organicdesign.fp.collections.UnmodIterable.UnIterable

    Nested classes/interfaces inherited from interface org.organicdesign.fp.collections.UnmodList

    org.organicdesign.fp.collections.UnmodList.AbstractUnmodList<E>

  • Constructor Summary

    Constructors
    Constructor
    Description
    RrbTree()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    abstract RrbTree<E>
    append(E t)
    abstract RrbTree<E>
    appendSome(org.organicdesign.fp.function.Fn0<? extends org.organicdesign.fp.oneOf.Option<E>> supplier)
    static <T> RrbTree.ImRrbt<T>
    empty()
    Returns the empty, immutable RRB-Tree (there is only one)
    static <T> RrbTree.MutRrbt<T>
    emptyMutable()
    Returns the empty, mutable RRB-Tree (there is only one)
    boolean
    equals(Object other)
    abstract E
    get(int i)
    int
    hashCode()
    This implementation is correct and compatible with java.util.AbstractList, but O(n).
    abstract String
    indentedStr(int indent)
    abstract RrbTree<E>
    insert(int idx, E element)
    Inserts an item in the RRB tree pushing the current element at that index and all subsequent elements to the right.
    abstract org.organicdesign.fp.collections.UnmodSortedIterator<E>
    iterator()
    RrbTree<E>
    join(RrbTree<E> that)
    Joins the given tree to the right side of this tree (or this to the left side of that one) in something like O(log n) time.
    protected abstract RrbTree<E>
    makeNew(E[] f, int fi, int fl, RrbTree.Node<E> r, int s)
    Allows removing duplicated code by letting super-class produce new members of subclass types.
    protected abstract RrbTree<E>
    mt()
    Creates a new empty ("M-T") tree of the appropriate (mutable/immutable) type.
    abstract RrbTree<E>
    precat(@Nullable Iterable<? extends E> es)
    Precat is implemented here because it is a very cheap operation on an RRB-Tree.
    abstract RrbTree<E>
    replace(int index, E item)
    abstract int
    size()
    org.organicdesign.fp.tuple.Tuple2<? extends RrbTree<E>,? extends RrbTree<E>>
    split(int splitIndex)
    Divides this RRB-Tree such that every index less-than the given index ends up in the left-hand tree and the indexed item and all subsequent ones end up in the right-hand tree.
    RrbTree<E>
    without(int index)
    Returns a new RrbTree minus the given item (all items to the right are shifted left one) This is O(log n).

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface org.organicdesign.fp.collections.BaseList

    concat, get, head, reverse

    Methods inherited from interface java.util.Collection

    parallelStream, stream, toArray

    Methods inherited from interface java.lang.Iterable

    forEach

    Methods inherited from interface java.util.List

    addFirst, addLast, getFirst, getLast, removeFirst, removeLast, reversed, spliterator

    Methods inherited from interface org.organicdesign.fp.xform.Transformable

    any, toImList, toImMap, toImRrbt, toImSet, toImSortedMap, toImSortedSet, toMutList, toMutMap, toMutRrbt, toMutSet, toMutSortedMap, toMutSortedSet

    Methods inherited from interface org.organicdesign.fp.collections.UnmodIterable

    drop, dropWhile, filter, flatMap, fold, foldUntil, map, take, takeWhile, whereNonNull

    Methods inherited from interface org.organicdesign.fp.collections.UnmodList

    add, add, addAll, addAll, clear, contains, containsAll, indexOf, isEmpty, lastIndexOf, listIterator, listIterator, remove, remove, removeAll, removeIf, replaceAll, retainAll, set, sort, subList, toArray, toArray

  • Constructor Details

    • RrbTree

      public RrbTree()

  • Method Details

    • empty

      public static <T> RrbTree.ImRrbt<T> empty()
      Returns the empty, immutable RRB-Tree (there is only one)

    • emptyMutable

      public static <T> RrbTree.MutRrbt<T> emptyMutable()
      Returns the empty, mutable RRB-Tree (there is only one)

    • append

      public abstract RrbTree<E> append(E t)
      Specified by:
      append in interface org.organicdesign.fp.collections.BaseList<E>

    • appendSome

      public abstract RrbTree<E> appendSome(org.organicdesign.fp.function.Fn0<? extends org.organicdesign.fp.oneOf.Option<E>> supplier)
      Specified by:
      appendSome in interface org.organicdesign.fp.collections.BaseList<E>

    • get

      public abstract E get(int i)
      Specified by:
      get in interface List<E>

    • insert

      public abstract RrbTree<E> insert(int idx, E element)
      Inserts an item in the RRB tree pushing the current element at that index and all subsequent elements to the right.
      Parameters:
      idx - the insertion point
      element - the item to insert
      Returns:
      a new RRB-Tree with the item inserted.

    • iterator

      public abstract org.organicdesign.fp.collections.UnmodSortedIterator<E> iterator()
      Specified by:
      iterator in interface Collection<E>
      Specified by:
      iterator in interface Iterable<E>
      Specified by:
      iterator in interface List<E>
      Specified by:
      iterator in interface org.organicdesign.fp.collections.UnmodCollection<E>
      Specified by:
      iterator in interface org.organicdesign.fp.collections.UnmodIterable<E>
      Specified by:
      iterator in interface org.organicdesign.fp.collections.UnmodList<E>
      Specified by:
      iterator in interface org.organicdesign.fp.collections.UnmodSortedCollection<E>
      Specified by:
      iterator in interface org.organicdesign.fp.collections.UnmodSortedIterable<E>

    • join

      public RrbTree<E> join(RrbTree<E> that)
      Joins the given tree to the right side of this tree (or this to the left side of that one) in something like O(log n) time.

    • makeNew

      protected abstract RrbTree<E> makeNew(E[] f, int fi, int fl, RrbTree.Node<E> r, int s)
      Allows removing duplicated code by letting super-class produce new members of subclass types.

    • mt

      protected abstract RrbTree<E> mt()
      Creates a new empty ("M-T") tree of the appropriate (mutable/immutable) type.

    • precat

      public abstract RrbTree<E> precat(@Nullable @Nullable Iterable<? extends E> es)
      Precat is implemented here because it is a very cheap operation on an RRB-Tree. It's not implemented on PersistentVector because it is very expensive there.
      Specified by:
      precat in interface org.organicdesign.fp.xform.Transformable<E>
      Specified by:
      precat in interface org.organicdesign.fp.collections.UnmodIterable<E>

    • replace

      public abstract RrbTree<E> replace(int index, E item)
      Specified by:
      replace in interface org.organicdesign.fp.collections.BaseList<E>

    • size

      public abstract int size()
      Specified by:
      size in interface Collection<E>
      Specified by:
      size in interface List<E>
      Specified by:
      size in interface org.organicdesign.fp.collections.Sized

    • split

      public org.organicdesign.fp.tuple.Tuple2<? extends RrbTree<E>,? extends RrbTree<E>> split(int splitIndex)
      Divides this RRB-Tree such that every index less-than the given index ends up in the left-hand tree and the indexed item and all subsequent ones end up in the right-hand tree.
      Parameters:
      splitIndex - the split point (excluded from the left-tree, included in the right one)
      Returns:
      two new sub-trees as determined by the split point. If the point is 0 or this.size() one tree will be empty (but never null).

    • without

      public RrbTree<E> without(int index)
      Returns a new RrbTree minus the given item (all items to the right are shifted left one) This is O(log n).

    • equals

      public boolean equals(Object other)
      Specified by:
      equals in interface Collection<E>
      Specified by:
      equals in interface List<E>
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      This implementation is correct and compatible with java.util.AbstractList, but O(n).
      Specified by:
      hashCode in interface Collection<E>
      Specified by:
      hashCode in interface List<E>
      Overrides:
      hashCode in class Object

    • indentedStr

      public abstract String indentedStr(int indent)
      Specified by:
      indentedStr in interface org.organicdesign.fp.indent.Indented