Finger Trees
Finger Trees are a efficient, general purpose immutable data structures that use recursive type definitions to enforce the valid state of the tree. The “fingers” of the tree structure forms that vary between one and four entries, which allows some critical slack in the data structure and avoids a lot of expensive updates.
This implementation is updated to the 2.6.1 compiler.
package finger; /** Implements Paterson/Hinze Finger Trees -- a general purpose functional data structure. Finger Trees support fast access to the ends of the sequence and O(log N) splits, seeks, etc...see their pages for more details. Written by Ross Judson This work is in the public domain. You may use it for any purpose. Please send comments to ross at (s)oletta.com. If you study the code you'll find a fair number of Scala programming techniques covered, so this serves as reference code. I make no claim that this is the <i>best</i> way to use Scala, though! This is a relatively literal implementation at this time -- here and there I've used polymorphism instead of pattern matching, with the idea being that a method call in the Java VM is usually pretty fast. The append algorithm is slightly modified to <i>roll</i> a shallow Deep object to the left, which results in a more balanced tree if creation is by repeated append. TODO: - sort out the covariant vs. singleton empty object issue - foldRight - measure and determine if any additional implementations of Seq methods would help - see if there's any way to reduce the size of the .class files - determine if Node2 and Node3 are similar enough to Two and Three that they should be merged or have a common base class. - figure out how to add laziness and zipper effects Making this better - get rid of node and digit...just use the tuple classes. - have a trait Sizer, where sizer can be extended to include other things, so carrying is possible (like with the Haskell version) - One[A] becomes (S >: Sizer, A) - Two[A] becomes (S >: Sizer, A, A), and so forth - Can we carry along some notion of dimension, so we don't need to do any nasty instanceof testing or anything like that? Distance can either be carried along with function calls, or it can be embedded in the structure. It's sort of implicit during traversal -- each time we recurse into Deep, we increment the dimension by one. */ object Finger { import collection.mutable.{Buffer, ArrayBuffer}; import xml.{Elem, TopScope, Text, UnprefixedAttribute, Null}; private [finger] val emptyFTSingleton = Empty[Nothing](); private [finger] def empty[A] = emptyFTSingleton.asInstanceOf[Empty[A]]; private val emptySingleton: FingerSeq[Nothing] = new FingerSeq[Nothing](emptyFTSingleton); /** Builds a finger tree from a single element. */ def singleton[A](a: A) = new FingerSeq[A](Single(a)); /** Returns an empty finger tree for items of type A. */ def emptySeq[A]() = emptySingleton.asInstanceOf[FingerSeq[A]]; /** Constructs a finger tree from a sequence of items. */ def build[A](a: A*): FingerSeq[A] = new FingerSeq(buildFrom(a.length, a.elements)) /** Efficiently construct a finger tree from the elements provided by the given iterator. The length must be provided as well, and should exactly match the number of items in the iterator. Only len items will be taken from the iterator. */ def buildFrom[A](len: Int, a: Iterator[A]): FingerTree[A] = { def one = One(a.next) def two = Two(a.next, a.next) def three = Three(a.next, a.next, a.next) def four = Four(a.next, a.next, a.next, a.next) len match { case 0 => emptyFTSingleton.asInstanceOf[FingerTree[A]] case 1 => Single(a.next) case 2 => deep(one, empty[Node[A]], one) case 3 => deep(two, empty[Node[A]], one) case 4 => deep(two, empty[Node[A]], two) case 5 => deep(three, empty[Node[A]], two) case 6 => deep(three, empty[Node[A]], three) case 7 => deep(four, empty[Node[A]], three) case 8 => deep(four, empty[Node[A]], four) case _ => buildFrom(8, a) add buildFrom(len - 8, a) } } /** Assembles a finger tree from a sequence of items. */ def apply[A](a: A*) = build(a:_*); /** Determines the size of the given element. */ private [finger] def sizeOf(a: Any) = a match { case sz: Sized => sz.size; case _ => 1 } /** A type describing the placement of something, usually returned as a result of a find operation. */ type Place[a] = (int,a); def Place[a](x: int, y: a) = (x,y); private [finger] def deep[A](pr: Digit[A], m: FingerTree[Node[A]], sf: Digit[A]) = Deep(pr.size + m.size + sf.size, pr, m, sf); private [finger] def node2[A](a: A, b: A) = new Node2(sizeOf(a) + sizeOf(b), a, b); private [finger] def node3[A](a: A, b: A, c: A) = new Node3(sizeOf(a) + sizeOf(b) + sizeOf(c), a, b, c); private [finger] def streamOf[A](a: A*) = _streamOn(a, 0) private [finger] def streamOn[A](s: Seq[A]) = _streamOn(s, 0) private [finger] def _streamOn[A](s: Seq[A], i: Int): Stream[A] = s.isDefinedAt(i) match { case true => Stream.cons(s(i), _streamOn(s, i+1)) case false => Stream.empty } private [finger] def streamOne[A](a: A) = Stream.cons(a, Stream.empty) private [finger] final val SSERROR = "Cannot create subsequence"; /* def joinIterable[A](pieces: Iterable[A]*): Iterator[A] = pieces.length match { case 0 => Iterator.empty; case 1 => pieces(0).elements; case _ => new Iterator[A] { val pieceIter = pieces.elements; var iter = pieceIter.next.elements; def hasNext: boolean = iter.hasNext || (pieceIter.hasNext && { iter = pieceIter.next.elements; hasNext }); def next = iter.next; } } def convertToXML(x: Any*): scala.xml.NodeSeq = x.toArray.map(_convertToXML) private def _convertToXML(x: Any): xml.Node = x match { case fs: FingerSeq[Nothing] => fs.toXML case ft: FingerTree[Nothing] => ft.toXML case nd: Node[Nothing] => nd.toXML case d: Digit[Nothing] => d.toXML case _ => xml.Text(x.toString()) } */ } import Finger._; import xml.Elem; class FingerSeq[A](val xs: FingerTree[A]) extends Seq[A] { // // Implementations of Seq[A] methods // override def stringPrefix = "FingerSeq"; /** Return the length of this Finger Sequence. */ def length = xs.size; /** Return an iterator over the elements of this Finger Sequence. */ def elements: Iterator[A] = xs.elements; /** Concatenate this sequence with another. If the other is a finger sequence, special processing will make the operation more efficient. */ override def concat[B >: A](that:Iterable[B]) = that match { case f: FingerSeq[B] => this ++ f case _ => super.concat(that) } /** Concatenates two sequences efficiently. TODO: This is clearly cheating, but I don't want to modify the entire FingerTree area just yet. */ override def ++ [B >: A](that: Iterable[B]) = that match { case f: FingerSeq[B] => new FingerSeq[A](xs add f.asInstanceOf[FingerSeq[A]].xs) case _ => super.++(that) } def ++ [B >: A](that: FingerSeq[B]): FingerSeq[A] = new FingerSeq[A](xs add that.asInstanceOf[FingerSeq[A]].xs) /** Returns a subsequence of this finger sequence. The subsequence will share as much structure as possible.*/ override def slice(from: Int, until: Int): FingerSeq[A] = { if (from == 0) { if (until < length) splitAt(until)._1 else if (until == length) this else error(SSERROR) } else if (from >= length) { emptySeq[A]() } else if (from > 0) { val s = splitAt(from)._2 val len = until - from if (len < s.length) s.splitAt(len)._1 else if (len > s.length) error(SSERROR) else s } else { error(SSERROR) } } /** Determines if the predicate holds true for all elements in this sequence. */ override def forall(p: A => Boolean) = xs forall p /** Finds the first element for which the predicate holds true. */ override def find(p: A => Boolean): Option[A] = xs.find(p) match { case Some(x) => Some(x) case _ => None } /** Combines the elements of this sequence together using the binary * operator op, from left to right, and starting with * the value z. * @return op(... (op(op(z,a0),a1) ...), an) if the list * is FingerSeq(a0, a1, ..., an). */ override def foldLeft[B](z: B)(op: (B, A) => B): B = (z /: xs)(op); // Methods that should probably exist if Scala had an immutable list/queue trait /** Push the element on the end of this sequence, returning the new sequence. */ def push(a: A) = append(a); /** Returns the last element in the sequence, throwing an error if the sequence is empty. */ def top = last; /** Returns the first element in the sequence, throwing an error if the sequence is empty. */ def first = xs.first; /** Returns the last element in the sequence, throwing an error if the sequence is empty. */ override def last = xs.last; /** Returns a tuple consisting of the first element in this sequence together with a new sequence minus the first element. */ def dequeue = xs.viewLTree match { case Some((a,t)) => (a,new FingerSeq(t)) case _ => error("empty") } /** Returns a new sequence with the specified element appended to it. */ def enqueue(a: A) = append(a); /** Returns the first element in the sequence, throwing an error if the sequence is empty. */ def front = first; /** Returns a new sequence with the element in the given position altered to x. */ def update(i: int, x: A) = adjust(i, x); // Finger Sequence external methods. /** Creates a stream on the elements in this sequence. */ def stream: Stream[A] = xs.stream; /** Creates a stream on the elements in this sequence, starting from a specified position. NOTE: Not functional yet. */ def streamFrom(i: int): Stream[A] = xs.streamFrom(-i)._2; /** Returns a new sequence with the element at the given position altered. */ def adjust(i: int, x: A) = new FingerSeq(xs.adjust((pos, item) => item, -i)); /** Splits this sequence at the given position. The returned sequences are balanced and contain as much shared structure from this sequence as is possible. */ def splitAt(i: int): (FingerSeq[A], FingerSeq[A]) = { if (length == 0) (this, this) else if (length <= i) (this, emptySeq[A]()) else { val ftpair = xs.split(-i, true, true); (new FingerSeq(ftpair.left), new FingerSeq(ftpair.right \+ ftpair.pivot)) } } /** Appends the specified item to this sequence, returning the new sequence that results. */ def append(a: A) = new FingerSeq(xs append a); /** Prepends the specified item to this sequence, returning the new sequence that results. */ def prepend(a: A) = new FingerSeq(xs \+ a); /** Converts the internal structure of this sequence to XML nodes, for easy examination. */ // def toXML = <FingerSeq size={length.toString()}>{xs.toXML}</FingerSeq> ; /** Returns the element at the specified position, throwing an error if the position is out of bounds. */ def apply(i: int) = if (i >= 0 && i < length) xs.lookup(-i)._2; else error("Index out of bounds") ; /** Returns a new sequence consisting of this one with the given element appended to the end. */ def +(a: A) = append(a); /** Returns a string showing the internal structure of this sequence. */ def structure = xs.toString(); } abstract sealed private[finger] class Sized { def size: int; } abstract sealed private[finger] class FingerTree[A] extends Sized { type FTSplit = Split[FingerTree[A], A] type NodeTree = FingerTree[Node[A]] type ADigit = Digit[A] type ATree = FingerTree[A] type LeftView = Option[(A, FingerTree[A])] type RightView = Option[(FingerTree[A], A)] def fmap[B <: Sized](func: A => B): FingerTree[B]; def find(p: A => boolean): Option[A] = ffind(a => if (p(a)) Some(a) else None); def ffind[B](p: A => Option[B]): Option[B]; def foldLeft[B](z: B)(op: (B, A) => B): B; final def /:[B](z: B)(op: (B, A) => B) = foldLeft(z)(op); def forall(p: A => Boolean): Boolean; def prepend(x: A): ATree; final def \+(x: A) = prepend(x); def append(x: A): ATree; final def +(x: A) = append(x); // def toXML: Elem; def lookup(i: int): Place[A]; def adjust(f: (int, A) => A, i: int): ATree; def elements: Iterator[A]; def stream: Stream[A]; def streamFrom(i: int): Place[Stream[A]]; def split(i: int, left: boolean, right: boolean): FTSplit; def first: A; def last: A; def viewLTree: LeftView; def viewRTree: RightView; // def reverse: ATree; // def appendTree(x: ATree) = appendTree0(x); def add(right: ATree): ATree; def add1(n: A, right: ATree): ATree; def add2(n1: A, n2: A, right: ATree): ATree; def add3(n1: A, n2: A, n3: A, right: ATree): ATree; def add4(n1: A, n2: A, n3: A, n4: A, right: ATree): ATree; def addDigits0(m1: NodeTree, dig1: ADigit, dig2: ADigit, m2: NodeTree): NodeTree = dig1 match { case One(a) => dig2 match { case One(b) => m1.add1( node2(a, b), m2) case Two(b,c) => m1.add1( node3(a,b,c), m2) case Three(b,c,d) => m1.add2( node2(a,b), node2(c,d),m2) case Four(b,c,d,e) => m1.add2( node3(a,b,c), node2(d,e), m2) } case Two(a,b) => dig2 match { case One(c) => m1.add1( node3(a,b,c), m2) case Two(c,d) => m1.add2( node2(a,b), node2(c,d), m2) case Three(c,d,e) => m1.add2( node3(a,b,c), node2(d,e), m2) case Four(c,d,e,f) => m1.add2( node3(a,b,c), node3(d,e,f), m2) } case Three(a,b,c) => dig2 match { case One(d) => m1.add2( node2(a,b), node2(c,d), m2) case Two(d,e) => m1.add2( node3(a,b,c), node2(d,e), m2) case Three(d,e,f) => m1.add2( node3(a,b,c), node3(d,e,f), m2) case Four(d,e,f,g) => m1.add3( node3(a,b,c), node2(d,e), node2(f,g), m2) } case Four(a,b,c,d) => dig2 match { case One(e) => m1.add2( node3(a,b,c), node2(d,e), m2) case Two(e,f) => m1.add2( node3(a,b,c), node3(d,e,f), m2) case Three(e,f,g) => m1.add3( node3(a,b,c), node2(d,e), node2(f,g), m2) case Four(e,f,g,h) => m1.add3( node3(a,b,c), node3(d,e,f), node2(g,h), m2) } } def addDigits1(m1: NodeTree, d1: ADigit, x: A, d2: ADigit, m2: NodeTree): NodeTree = d1 match { case One(a) => d2 match { case One(b) => m1.add1(node3(a,x,b), m2) case Two(b,c) => m1.add2(node2(a,x), node2(b,c), m2) case Three(b,c,d) => m1.add2(node3(a,x,b), node2(c,d), m2) case Four(b,c,d,e) => m1.add2(node3(a,x,b), node3(c,d,e), m2) } case Two(a,b) => d2 match { case One(c) => m1.add2(node2(a,b), node2(x,c), m2) case Two(c,d) => m1.add2(node3(a,b,x), node2(c,d), m2) case Three(c,d,e) => m1.add2(node3(a,b,x), node3(c,d,e), m2) case Four(c,d,e,f) => m1.add3(node3(a,b,x), node2(c,d), node2(e,f), m2) } case Three(a,b,c) => d2 match { case One(d) => m1.add2(node3(a,b,c), node2(x,d), m2) case Two(d,e) => m1.add2(node3(a,b,c), node3(x,d,e), m2) case Three(d,e,f) => m1.add3(node3(a,b,c), node2(x,d), node2(e,f), m2) case Four(d,e,f,g) => m1.add3(node3(a,b,c), node3(x,d,e), node2(f,g), m2) } case Four(a,b,c,d) => d2 match { case One(e) => m1.add2(node3(a,b,c), node3(d,x,e), m2) case Two(e,f) => m1.add3(node3(a,b,c), node2(d,x), node2(e,f), m2) case Three(e,f,g) => m1.add3(node3(a,b,c), node3(d,x,e), node2(f,g), m2) case Four(e,f,g,h) => m1.add3(node3(a,b,c), node3(d,x,e), node3(f,g,h), m2) } } def addDigits2(m1: NodeTree, d1: ADigit, x: A, y: A, d2: ADigit, m2: NodeTree): NodeTree = d1 match { case One(a) => d2 match { case One(b) => m1.add2(node2(a,x), node2(y,b), m2) case Two(b,c) => m1.add2(node3(a,x,y), node2(b,c), m2) case Three(b,c,d) => m1.add2(node3(a,x,y), node3(b,c,d), m2) case Four(b,c,d,e) => m1.add3(node3(a,x,y), node2(b,c), node2(d,e), m2) } case Two(a,b) => d2 match { case One(c) => m1.add2(node3(a,b,x), node2(y,c), m2) case Two(c,d) => m1.add2(node3(a,b,x), node3(y,c,d), m2) case Three(c,d,e) => m1.add3(node3(a,b,x), node2(y,c), node2(d,e), m2) case Four(c,d,e,f) => m1.add3(node3(a,b,x), node3(y,c,d), node2(e,f), m2) } case Three(a,b,c) => d2 match { case One(d) => m1.add2(node3(a,b,c), node3(x,y,d), m2) case Two(d,e) => m1.add3(node3(a,b,c), node2(x,y), node2(d,e), m2) case Three(d,e,f) => m1.add3(node3(a,b,c), node3(x,y,d), node2(e,f), m2) case Four(d,e,f,g) => m1.add3(node3(a,b,c), node3(x,y,d), node3(e,f,g), m2) } case Four(a,b,c,d) => d2 match { case One(e) => m1.add3(node3(a,b,c), node2(d,x), node2(y,e), m2) case Two(e,f) => m1.add3(node3(a,b,c), node3(d,x,y), node2(e,f), m2) case Three(e,f,g) => m1.add3(node3(a,b,c), node3(d,x,y), node3(e,f,g), m2) case Four(e,f,g,h) => m1.add4(node3(a,b,c), node3(d,x,y), node2(e,f), node2(g,h), m2) } } def addDigits3(m1: NodeTree, d1: ADigit, x: A, y: A, z: A, d2: ADigit, m2: NodeTree): NodeTree = d1 match { case One(a) => d2 match { case One(b) => m1.add2(node3(a,x,y), node2(z,b), m2) case Two(b,c) => m1.add2(node3(a,x,y), node3(z,b,c), m2) case Three(b,c,d) => m1.add3(node3(a,x,y), node2(z,b), node2(c,d), m2) case Four(b,c,d,e) => m1.add3(node3(a,x,y), node3(z,b,c), node2(d,e), m2) } case Two(a,b) => d2 match { case One(c) => m1.add2(node3(a,b,x), node3(y,z,c), m2) case Two(c,d) => m1.add3(node3(a,b,x), node2(y,z), node2(c,d), m2) case Three(c,d,e) => m1.add3(node3(a,b,x), node3(y,z,c), node2(d,e), m2) case Four(c,d,e,f) => m1.add3(node3(a,b,x), node3(y,z,c), node3(d,e,f),m2) } case Three(a,b,c) => d2 match { case One(d) => m1.add3(node3(a,b,c), node2(x,y), node2(z,d), m2) case Two(d,e) => m1.add3(node3(a,b,c), node3(x,y,z), node2(d,e), m2) case Three(d,e,f) => m1.add3(node3(a,b,c), node3(x,y,z), node3(d,e,f), m2) case Four(d,e,f,g) => m1.add4(node3(a,b,c), node3(x,y,z), node2(d,e), node2(f,g), m2) } case Four(a,b,c,d) => d2 match { case One(e) => m1.add3(node3(a,b,c), node3(d,x,y), node2(z,e), m2) case Two(e,f) => m1.add3(node3(a,b,c), node3(d,x,y), node3(z,e,f), m2) case Three(e,f,g) => m1.add4(node3(a,b,c), node3(d,x,y), node2(z,e),node2(f,g), m2) case Four(e,f,g,h) => m1.add4(node3(a,b,c), node3(d,x,y), node3(z,e,f), node2(g,h), m2) } } def addDigits4(m1: NodeTree, d1: ADigit, x: A, y: A, z: A, w: A, d2: ADigit, m2: NodeTree): NodeTree = d1 match { case One(a) => d2 match { case One(b) => m1.add2(node3(a,x,y), node3(z,w,b), m2) case Two(b,c) => m1.add3(node3(a,x,y), node2(z,w), node2(b,c), m2) case Three(b,c,d) => m1.add3(node3(a,x,y), node3(z,w,b), node2(c,d), m2) case Four(b,c,d,e) => m1.add3(node3(a,x,y), node3(z,w,b), node3(c,d,e), m2) } case Two(a,b) => d2 match { case One(c) => m1.add3(node3(a,b,x), node2(y,z), node2(w,c), m2) case Two(c,d) => m1.add3(node3(a,b,x), node3(y,z,w), node2(c,d), m2) case Three(c,d,e) => m1.add3(node3(a,b,x), node3(y,z,w), node3(c,d,e), m2) case Four(c,d,e,f) => m1.add4(node3(a,b,x), node3(y,z,w), node2(c,d), node2(e,f),m2) } case Three(a,b,c) => d2 match { case One(d) => m1.add3(node3(a,b,c), node3(x,y,z), node2(w,d), m2) case Two(d,e) => m1.add3(node3(a,b,c), node3(x,y,z), node3(w,d,e), m2) case Three(d,e,f) => m1.add4(node3(a,b,c), node3(x,y,z), node2(w,d),node2(e,f), m2) case Four(d,e,f,g) => m1.add4(node3(a,b,c), node3(x,y,z), node3(w,d,e), node2(f,g), m2) } case Four(a,b,c,d) => d2 match { case One(e) => m1.add3(node3(a,b,c), node3(d,x,y), node3(z,w,e), m2) case Two(e,f) => m1.add4(node3(a,b,c), node3(d,x,y), node2(z,w), node2(e,f), m2) case Three(e,f,g) => m1.add4(node3(a,b,c), node3(d,x,y), node3(z,w,e),node2(f,g), m2) case Four(e,f,g,h) => m1.add4(node3(a,b,c), node3(d,x,y), node3(z,w,e), node3(f,g,h), m2) } } } final private[finger] case class Empty[A]() extends FingerTree[A] { def size = 0; def fmap[B <: Sized](func: A => B) = Empty[B](); def ffind[B](p: A => Option[B]): Option[B] = None; def foldLeft[B](z: B)(op: (B, A) => B) = z; def forall(p: A => Boolean) = true; def apply(i: int): Nothing = error("cannot apply empty"); def prepend(x: A) = Single(x); def append(x: A) = Single(x); // def toXML = <Empty/> ; def lookup(i: int) = error("Index out of bounds"); def adjust(f: (int, A) => A, i: int) = error("Index out of bounds"); def elements = Iterator.empty; def stream: Stream[A] = Stream.empty; def streamFrom(i: int) = error("Index out of bounds"); def split(i: int, left: boolean, right: boolean) = error("Cannot split empty"); def first: A = error("Empty"); def last: A = first; def viewLTree = None; def viewRTree = None; def add(right: ATree): ATree = right; def add1(n: A, right: ATree): ATree = right \+ n; def add2(n1: A, n2: A, right: ATree): ATree = right \+ n2 \+ n1; def add3(n1: A, n2: A, n3: A, right: ATree): ATree = right \+ n3 \+ n2 \+ n1; def add4(n1: A, n2: A, n3: A, n4: A, right: ATree): ATree = right \+ n4 \+ n3 \+ n2 \+ n1; } final private[finger] case class Single[A](a: A) extends FingerTree[A] { def elements = Iterator.single(a); val size = sizeOf(a); def fmap[B <: Sized](func: A => B) = Single(func(a)); def ffind[B](p: A => Option[B]): Option[B] = p(a); def foldLeft[B](z: B)(op: (B, A) => B) = op(z, a); def forall(p: A => Boolean) = p(a); def apply(i: int) = a; def prepend(x: A) = deep(One(x), Empty[Node[A]](), One(a)); def append(x: A) = deep(One(a), Empty[Node[A]](), One(x)); // def toXML = <Single>{convertToXML(a)}</Single> ; def lookup(i: int) = Place(i, a); def adjust(f: (int, A) => A, i: int) = Single(f(i, a)); def streamFrom(i: int) = Place(i, stream); def split(i: int, left: boolean, right: boolean): FTSplit = new Split(Empty[A](), a, Empty[A]()); def stream: Stream[A] = streamOne(a); def first: A = a; def last: A = a; def viewLTree = Some((a, Empty[A]())); def viewRTree = Some((Empty[A](), a)); def reverse: ATree = this; def add(right: ATree) = right match { case Empty() => this case _ => right \+ a } def add1(n: A, right: ATree): ATree = right \+ n \+ a; def add2(n1: A, n2: A, right: ATree): ATree = right \+ n2 \+ n1 \+ a; def add3(n1: A, n2: A, n3: A, right: ATree): ATree = right prepend n3 prepend n2 prepend n1 prepend a; def add4(n1: A, n2: A, n3: A, n4: A, right: ATree): ATree = right \+ n4 \+ n3 \+ n2 \+ n1 \+ a; } final private[finger] case class Deep[A](size: int, pr: Digit[A], m: FingerTree[Node[A]], sf: Digit[A]) extends FingerTree[A] { def elements = stream.elements; def stream: Stream[A] = pr.stream.append(m.stream.flatMap(na => na.stream).append(sf.stream)); def fmap[B <: Sized](func: A => B) = Deep(size, pr fmap func, m fmap (f => f fmap func), sf fmap func); def forall(p: A => Boolean) = pr.forall(p) && sf.forall(p) && m.forall(na => na forall p); def ffind[B](p: A => Option[B]): Option[B] = pr.ffind(p) match { case None => m.ffind(na => na ffind p) match { case None => sf ffind p case s: Some[B] => s } case s: Some[B] => s }; def foldLeft[B](z: B)(op: (B, A) => B) = ((((z/:pr)(op)/:m)((b,na)=>(b/:na)(op)))/:sf)(op); def first: A = pr.first; def last: A = sf.last; def viewLTree = pr match { case One(a) => Some((a, m.viewLTree match { case None => sf.toTree case Some((b,m)) => Deep(size - sizeOf(a), b.toDigit, m, sf) })) case Two(a,b) => Some((a, Deep(size - sizeOf(a), One(b), m, sf))) case Three(a,b,c) => Some((a, Deep(size - sizeOf(a), Two(b,c), m, sf))) case Four(a,b,c,d) => Some((a, Deep(size - sizeOf(a), Three(b,c,d), m, sf))) } def viewRTree = sf match { case One(z) => Some((m.viewRTree match { case None => pr.toTree case Some((m,y)) => Deep(size - sizeOf(z), pr, m, y.toDigit) }, z)) case Two(y,z) => Some((Deep(size - sizeOf(z), pr, m, One(y)), z)) case Three(x,y,z) => Some((Deep(size - sizeOf(z), pr, m, Two(x,y)), z)) case Four(w,x,y,z) => Some((Deep(size - sizeOf(z), pr, m, Three(w,x,y)), z)) } def prepend(a: A) = pr match { case Four(b,c,d,e) => Deep(sizeOf(a) + size, Two(a,b), m \+ node3(c,d,e),sf) case Three(b,c,d) => Deep(sizeOf(a) + size, Four(a,b,c,d), m, sf) case Two(b,c) => Deep(sizeOf(a) + size, Three(a,b,c), m, sf) case One(b) => Deep(sizeOf(a) + size, Two(a,b), m, sf) } def append(x: A) = this match { case Deep(_, One(q), Empty(), Four(a,b,c,d)) => Deep[A](sizeOf(x) + size, Three(q,a,b), Empty(), Three(c,d,x)) case Deep(_, One(q), Single(Node3(_, a,b,c)), Four(d,e,f,g)) => Deep[A](sizeOf(x) + size, Three(q,a,b), Single(node3(c,d,e)), Three(f,g,x)) case _ => sf match { case Four(a,b,c,d) => Deep(sizeOf(x) + size, pr, m.append(node3(a,b,c)), Two(d, x)) case Three(a,b,c) => Deep(sizeOf(x) + size, pr, m, Four(a,b,c,x)) case Two(a,b) => Deep(sizeOf(x) + size, pr, m, Three(a,b,x)) case One(a) => Deep(sizeOf(x) + size, pr, m, Two(a,x)) } } // def toXML = <Deep size={v.toString()}>{List(pr.toXML, m.toXML, sf.toXML)}</Deep> ; def split(i: int, left: boolean, right: boolean): FTSplit = { val vpr = i + pr.size; if (vpr > 0) { val ds = pr.split(i, left, right); new Split(ds.left match { case None => Empty[A]() case Some(d) => d.toTree }, ds.pivot, deepL(ds.right, m, sf)) } else { val vm = vpr + m.size; if (vm > 0) { val ts = m.split(vpr, left, right); val ts2 = ts.pivot.split(vpr + ts.left.size, left, right); new Split(deepR(pr, ts.left, ts2.left), ts2.pivot, deepL(ts2.right, ts.right, sf)) } else { val rs = sf.split(vm, left, right); new Split(deepR(pr, m, rs.left), rs.pivot, rs.right match { case None => Empty[A]() case Some(d) => d.toTree}) } } } def adjust(f: (int, A) => A, i: int) = { val vpr = i + pr.size; if (vpr > 0) { Deep(size, pr.adjust(f, i), m, sf) } else { val vm = vpr + m.size; if (vm > 0) { Deep(size, pr, m.adjust((ni, na) => na.adjust(f, ni), vpr), sf) } else { Deep(size, pr, m, sf.adjust(f, vm)) } } } def lookup(i: int): Place[A] = { // remember that i is negative val vpr = i + pr.size; if (vpr > 0) pr.lookup(i) else { val vm = vpr + m.size; if (vm > 0) { val mp = m.lookup(vpr); mp._2.lookup(mp._1); } else sf.lookup(vm) } } def streamFrom(i: int) = { // remember that i is negative! val vpr = i + pr.size; if (vpr > 0) pr.streamFrom(i) else { val vm = vpr + m.size; if (vm > 0) { val mp = m.streamFrom(vpr); mp._2.head.streamFrom(mp._1); } else sf.streamFrom(vm) } } def add(right: ATree) = right match { case Empty() => this case Single(x) => this+x case Deep(v2, pr2, m2, sf2) => Deep(size+v2, pr, addDigits0(m, sf, pr2, m2), sf2) } def add1(n: A, right: ATree) = right match { case Empty() => this+n case Single(x) => this+n+x case Deep(v2, pr2, m2, sf2) => Deep(size + v2 + sizeOf(n), pr, addDigits1(m, sf, n, pr2, m2), sf2) } def add2(n1: A, n2: A, right: ATree) = right match { case Empty() => this+n1+n2 case Single(x) => this+n1+n2+x case Deep(v2, pr2, m2, sf2) => Deep(v2 + sizeOf(n1) + sizeOf(n2) + size, pr, addDigits2(m, sf, n1, n2, pr2, m2), sf2) } def add3(n1: A, n2: A, n3: A, right: ATree) = right match { case Empty() => this+n1+n2+n3 case Single(x) => this+n1+n2+n3+x case Deep(v2, pr2, m2, sf2) => Deep(v2 + sizeOf(n1) + sizeOf(n2) + sizeOf(n3) + size, pr, addDigits3(m, sf, n1, n2, n3, pr2, m2), sf2) } def add4(n1: A, n2: A, n3: A, n4: A, right: ATree) = right match { case Empty() => this+n1+n2+n3+n4 case Single(x) => this+n1+n2+n3+n4+x case Deep(v2, pr2, m2, sf2) => Deep(v2 + sizeOf(n1) + sizeOf(n2) + sizeOf(n3) + sizeOf(n4) + size, pr, addDigits4(m, sf, n1, n2, n3, n4, pr2, m2), sf2) } def deepL(l: Option[ADigit], c: NodeTree, r: ADigit): ATree = l match { case None => c.viewLTree match { case None => sf.toTree case Some((a,m)) => deep(a.toDigit, m, sf) } case Some(x) => deep(x, c, r) } def deepR(l: ADigit, c: NodeTree, r: Option[ADigit]) = r match { case None => c.viewRTree match { case None => pr.toTree case Some((m,a)) => deep(pr, m, a.toDigit) } case Some(x) => deep(l, c, x) } } /* final case class StreamSingleton[A](h: A) extends Stream[A] { import scala.compat.{StringBuilder => SB} override def isEmpty = false def head = h def tail = Stream.empty def printElems(buf: SB, prefix: String) = buf.append(prefix).append(h) } */ final private[finger] class Split[T,A](val left: T, val pivot: A, val right: T); abstract private[finger] sealed class Node[A] extends Sized { type Splitting = Split[Option[Digit[A]],A] val size: Int; val a, b: A; def stream: Stream[A]; def forall(p: A => Boolean) = p(a) && p(b); def fmap[B <: Sized](func: A => B): Node[B]; def toDigit: Digit[A]; // def toXML: Elem; def lookup(i: int): Place[A]; def adjust(f: (int, A) => A, i: int): Node[A]; def streamFrom(i: int): Place[Stream[A]]; def split(i: int, left: boolean, right: boolean): Splitting; def ffind[B](p: A => Option[B]): Option[B] = p(a) match { case None => p(b) case x @ _ => x }; def foldLeft[B](z: B)(op: (B, A) => B): B; final def /:[B](z: B)(op: (B, A) => B) = foldLeft(z)(op); //def reverse: Node[A]; } final private[finger] class Node2[A](val size: int, val a: A, val b: A) extends Node[A] { def stream = streamOf(a,b); def fmap[B <: Sized](func: A => B) = new Node2(size, func(a), func(b)); def foldLeft[B](z: B)(op: (B, A) => B) = op(op(z,a),b); def toDigit = Two(a,b); // def toXML = <Node2 size={v.toString()}>{ convertToXML(a,b) }</Node2> ; def split(i: int, left: boolean, right: boolean): Splitting = { val va = i + sizeOf(a); if (va > 0) new Split(None, a, Some(One(b))) else new Split(Some(One(a)), b, None) } def lookup(i: int) = { val va = i + sizeOf(a); if (va > 0) { Place(i, a) } else { Place(va, b) } } def adjust(f: (int, A) => A, i: int) = { val va = i + sizeOf(a); if (va > 0) new Node2(size, f(i, a), b) else new Node2(size, a, f(va, b)) } def streamFrom(i: int) = { val va = i + sizeOf(a); if (va > 0) { Place(i, stream) } else { Place(va, streamOne(b)) } } } final private[finger] case class Node3[A](size: int, a: A, b: A, c: A) extends Node[A] { def stream = streamOf(a,b,c); def fmap[B <: Sized](func: A => B) = Node3(size, func(a), func(b), func(c)<