Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Dylan
branch: master

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
README
RRB_Vector-exports.dylan
RRB_Vector.dylan
RRB_Vector.lid

README

RRB Vector implmentation

A implementation of a Persistent Vector. A Persistent Vector is an immutable Datastructure that has fast random access and fast insertion at the end.

A RRB Vector is an immutable Datastructure that has fast random access and fast insertion at the end, plus fast spliting and joining (meaning reasonably fast random insertions).

Random Accsess: O(log32(n)) 
Insertion: O(log32(n))
Split & Join: O(log(n))


For most practical perposes O(log32(n)) is constant.


My objectives:
- Learn Dylan (polymorthic collection implmentations)
- Give Dylan a better Collections library (specially for the multithreaded world and functional programming)

My implmentation is directly from the paper, with no working code as a example.

Resources

Paper: infoscience.epfl.ch/record/169879/files/RMTrees.pdf?version=1
Video by the Author: http://blip.tv/clojure/phill-bagwell-striving-to-make-things-simple-and-fast-5936145
Something went wrong with that request. Please try again.