alvinalexander.com | career | drupal | java | mac | mysql | perl | scala | uml | unix  

Scala example source code file (FingerTree.scala)

This example Scala source code file (FingerTree.scala) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Scala by Example" TM.

Learn more about this Scala project at its project page.

Java - Scala tags/keywords

fingertree, four, indseq, need, one, reducer, three, two

The FingerTree.scala Scala example source code

package scalaz

import collection.Iterator
import syntax.Ops
import std.option._

/**View of the left end of a sequence.*/
sealed abstract class ViewL[S[_], A] {
  def fold[B](b: => B, f: (=> A, => S[A]) => B): B
  def headOption: Option[A] = fold(None, (a, sa) => Some(a))
  def tailOption: Option[S[A]] = fold(None, (a, sa) => Some(sa))
  def head: A = headOption.getOrElse(sys.error("Head on empty view"))
  def tail: S[A] = tailOption.getOrElse(sys.error("Tail on empty view"))
}

/**View of the right end of a sequence.*/
sealed abstract class ViewR[S[_], A] {
  def fold[B](b: => B, f: (=> S[A], => A) => B): B
  def lastOption: Option[A] = fold(None, (sa, a) => Some(a))
  def initOption: Option[S[A]] = fold(None, (sa, a) => Some(sa))
  def last: A = lastOption.getOrElse(sys.error("Last on empty view"))
  def init: S[A] = initOption.getOrElse(sys.error("Init on empty view"))
}

import FingerTree._
import std.option._

sealed abstract class Finger[V, A] {
  def foldMap[B](f: A => B)(implicit m: Semigroup[B]): B

  /**
   * Append the given element to the right
   *
   * @throws if the finger is `Four`.
   */
  def +:(a: A): Finger[V, A]

  /**
   * Prepends the given element to the left
   *
   * @throws if the finger is `Four`.
   */
  def :+(a: A): Finger[V, A]

  /** Replaces the first element of this finger with `a` */
  def |-:(a: A): Finger[V, A]

  /** Replaces the last element of this finger with `a` */
  def :-|(a: A): Finger[V, A]

  def lhead: A

  def ltail: Finger[V, A]

  def rhead: A

  def rtail: Finger[V, A]

  def toTree: FingerTree[V, A]

  def map[B, V2](f: A => B)(implicit m: Reducer[B, V2]): Finger[V2, B]

  /** Apply the given side effect to each element. */
  def foreach(f: A => Unit): Unit

  /** An iterator that visits each element. */
  def iterator: Iterator[A]

  /** An iterator that visits each element in reverse order. */
  def reverseIterator: Iterator[A]

  def measure: V

  def toList: List[A] = map(x => x)(Reducer.ListReducer[A]).measure

  private[scalaz] def split1(pred: V => Boolean, accV: V): (Option[Finger[V, A]], A, Option[Finger[V, A]])
}
case class One[V, A](v: V, a1: A)(implicit r: Reducer[A, V]) extends Finger[V, A] {

  def foldMap[B](f: A => B)(implicit m: Semigroup[B]) = f(a1)

  def +:(a: A) = Two(r.cons(a, v), a, a1)

  def :+(a: A) = Two(r.snoc(v, a), a1, a)

  def |-:(a: A) = one(a)

  def :-|(a: A) = one(a)

  def lhead = a1

  def ltail = sys.error("Tail on the digit One")

  def rhead = a1

  def rtail = sys.error("Tail on the digit One")

  def toTree = single(a1)

  def map[B, V2](f: A => B)(implicit r: Reducer[B, V2]) = one(f(a1))

  def foreach(f: A => Unit) {
    f(a1)
  }

  def iterator = Iterator.single(a1)

  def reverseIterator = Iterator.single(a1)

  val measure = v

  private[scalaz] def split1(pred: V => Boolean, accV: V) = (None, a1, None)
}


case class Two[V, A](v: V, a1: A, a2: A)(implicit r: Reducer[A, V]) extends Finger[V, A] {
  def foldMap[B](f: A => B)(implicit m: Semigroup[B]) = m.append(f(a1), f(a2))

  def +:(a: A) = Three(r.cons(a, v), a, a1, a2)

  def :+(a: A) = Three(r.snoc(v, a), a1, a2, a)

  def |-:(a: A) = two(a, a2)

  def :-|(a: A) = two(a1, a)

  def lhead = a1

  def ltail = one(a2)

  def rhead = a2

  def rtail = one(a1)

  def toTree = {
    deep(v, one(a1), empty[V, Node[V, A]], one(a2))
  }

  def map[B, V2](f: A => B)(implicit r: Reducer[B, V2]) = two(f(a1), f(a2))

  def foreach(f: A => Unit) {
    f(a1)
    f(a2)
  }

  def iterator = Iterator(a1, a2)

  def reverseIterator = Iterator(a2, a1)

  val measure = v

  private implicit def sg: Semigroup[V] = r.monoid

  private[scalaz] def split1(pred: V => Boolean, accV: V) = {
    val va1 = r.unit(a1)
    val accVa1 = sg.append(accV, va1)
    if (pred(accVa1))
      (None, a1, Some(one(a2)))
    else
      (Some(One(va1, a1)), a2, None)
  }
}
case class Three[V, A](v: V, a1: A, a2: A, a3: A)(implicit r: Reducer[A, V]) extends Finger[V, A] {
  def foldMap[B](f: A => B)(implicit m: Semigroup[B]) = m.append(m.append(f(a1), f(a2)), f(a3))

  def +:(a: A) = Four(r.cons(a, v), a, a1, a2, a3)

  def :+(a: A) = Four(r.snoc(v, a), a1, a2, a3, a)

  def |-:(a: A) = three(a, a2, a3)

  def :-|(a: A) = three(a1, a2, a)

  def lhead = a1

  def ltail = two(a2, a3)

  def rhead = a3

  def rtail = two(a1, a2)

  def toTree = {
    deep(v, two(a1, a2), empty[V, Node[V, A]], one(a3))
  }

  def map[B, V2](f: A => B)(implicit r: Reducer[B, V2]) = three(f(a1), f(a2), f(a3))

  def foreach(f: A => Unit) {
    f(a1)
    f(a2)
    f(a3)
  }

  def iterator = Iterator(a1, a2, a3)

  def reverseIterator = Iterator(a3, a2, a1)

  val measure = v

  private implicit def sg: Semigroup[V] = r.monoid

  private[scalaz] def split1(pred: V => Boolean, accV: V) = {
    val va1 = r.unit(a1)
    val accVa1 = sg.append(accV, va1)
    if (pred(accVa1))
      (None, a1, Some(two(a2, a3)))
    else {
      val accVa2 = r.snoc(accVa1, a2)
      if (pred(accVa2))
        (Some(One(va1, a1)), a2, Some(one(a3)))
      else
        (Some(two(a1, a2)), a3, None)
    }
  }
}
case class Four[V, A](v: V, a1: A, a2: A, a3: A, a4: A)(implicit r: Reducer[A, V]) extends Finger[V, A] {
  def foldMap[B](f: A => B)(implicit m: Semigroup[B]) = m.append(m.append(f(a1), f(a2)), m.append(f(a3), f(a4)))

  def +:(a: A) = sys.error("Digit overflow")

  def :+(a: A) = sys.error("Digit overflow")

  def |-:(a: A) = four(a, a2, a3, a4)

  def :-|(a: A) = four(a1, a2, a3, a)

  def lhead = a1

  def ltail = three(a2, a3, a4)

  def rhead = a4

  def rtail = three(a1, a2, a3)

  def toTree = {
    deep(v, two(a1, a2), empty[V, Node[V, A]], two(a3, a4))
  }

  def map[B, V2](f: A => B)(implicit r: Reducer[B, V2]) = four(f(a1), f(a2), f(a3), f(a4))

  def foreach(f: A => Unit) {
    f(a1)
    f(a2)
    f(a3)
    f(a4)
  }

  def iterator = Iterator(a1, a2, a3, a4)

  def reverseIterator = Iterator(a4, a3, a2, a1)

  val measure = v

  private implicit def sg: Semigroup[V] = r.monoid

  private[scalaz] def split1(pred: V => Boolean, accV: V) = {
    val va1 = r.unit(a1)
    val accVa1 = sg.append(accV, va1)
    if (pred(accVa1))
      (None, a1, Some(three(a2, a3, a4)))
    else {
      val accVa2 = r.snoc(accVa1, a2)
      if (pred(accVa2))
        (Some(One(va1, a1)), a2, Some(two(a3, a4)))
      else {
        val accVa3 = r.snoc(accVa2, a3)
        if (pred(accVa3))
          (Some(two(a1, a2)), a3, Some(one(a4)))
        else
          (Some(three(a1, a2, a3)), a4, None)
      }
    }
  }
}

sealed abstract class Node[V, A](implicit r: Reducer[A, V]) {
  def fold[B](two: (V, => A, => A) => B, three: (V, => A, => A, => A) => B): B

  def foldMap[B](f: A => B)(implicit m: Semigroup[B]): B = fold(
    (v, a1, a2) => m.append(f(a1), f(a2)),
    (v, a1, a2, a3) => m.append(m.append(f(a1), f(a2)), f(a3)))

  def toDigit = fold(
    (v, a1, a2) => Two(v, a1, a2),
    (v, a1, a2, a3) => Three(v, a1, a2, a3))

  val measure: V

  def map[B, V2](f: A => B)(implicit m: Reducer[B, V2]) = fold(
    (v, a1, a2) => node2(f(a1), f(a2)),
    (v, a1, a2, a3) => node3(f(a1), f(a2), f(a3)))

  def foreach(f: A => Unit) {
    fold(
      (_, a1, a2) => { f(a1); f(a2) },
      (_, a1, a2, a3) => { f(a1); f(a2); f(a3) }
    )}

  def iterator = fold(
    (_, a1, a2) => Iterator(a1, a2),
    (_, a1, a2, a3) => Iterator(a1, a2, a3))

  def reverseIterator = fold(
    (_, a1, a2) => Iterator(a2, a1),
    (_, a1, a2, a3) => Iterator(a3, a2, a1))

  private implicit def sg: Semigroup[V] = r.monoid

  private[scalaz] def split1(pred: V => Boolean, accV: V): (Option[Finger[V, A]], A, Option[Finger[V, A]]) = fold(
    (v, a1, a2) => {
      val va1 = r.unit(a1)
      val accVa1 = sg.append(accV, va1)
      if (pred(accVa1))
        (None, a1, Some(one(a2)))
      else
        (Some(One(va1, a1)), a2, None)
    },
    (v, a1, a2, a3) => {
      val va1 = r.unit(a1)
      val accVa1 = sg.append(accV, va1)
      if (pred(accVa1))
        (None, a1, Some(two(a2, a3)))
      else {
        val accVa2 = r.snoc(accVa1, a2)
        if (pred(accVa2))
          (Some(One(va1, a1)), a2, Some(one(a3)))
        else
          (Some(two(a1, a2)), a3, None)
      }
    })
}

/**
 * Finger trees with leaves of type A and Nodes that are annotated with type V.
 *
 * Finger Trees provide a base for implementations of various collection types,
 * as described in "Finger trees: a simple general-purpose data structure", by
 * Ralf Hinze and Ross Paterson.
 * A gentle introduction is presented in the blog post "Monoids and Finger Trees" by Heinrich Apfelmus.
 *
 * This is done by choosing a a suitable type to annotate the nodes. For example,
 * a binary tree can be implemented by annotating each node with the size of its subtree,
 * while a priority queue can be implemented by labelling the nodes by the minimum priority of its children.
 *
 * The operations on FingerTree enforce the constraint measured (in the form of a Reducer instance).
 *
 * Finger Trees have excellent (amortized) asymptotic performance:
 *
 *  - Access to the first and last elements is `O(1)`
 *  - Appending/prepending a single value is `O(1)`
 *  - Concatenating two trees is `(O lg min(l1, l2))` where `l1` and `l2` are their sizes
 *  - Random access to an element at `n` is `O(lg min(n, l - n))`, where `l` is the size of the tree.
 *  - Constructing a tree with n copies of a value is O(lg n).
 *
 * @tparam V The type of the annotations of the nodes (the '''measure''')
 * @tparam A The type of the elements stored at the leaves
 *
 * @see [[http://www.soi.city.ac.uk/~ross/papers/FingerTree.pdf Finger trees: a simple general-purpose data structure]]
 * @see [[http://apfelmus.nfshost.com/articles/monoid-fingertree.html]]
 */
sealed abstract class FingerTree[V, A](implicit measurer: Reducer[A, V]) {
  def measure: V = fingerTreeMeasure[A, V].unit(this)

  def foldMap[B](f: A => B)(implicit s: Monoid[B]): B =
    fold(v => s.zero, (v, x) => f(x), (v, pr, m, sf) =>
      s.append(s.append(pr.foldMap(f), m.foldMap(x => x.foldMap(f))), sf.foldMap(f)))

  def foldRight[B](z: => B)(f: (A, => B) => B): B = {
    foldMap((a: A) => (Endo.endo(f(a, _: B)))) apply z
  }

  def foldLeft[B](b: B)(f: (B, A) => B): B = {
    fold(v => b,
          (v, a) => f(b, a),
          (v, pr, m, sf) =>
              fingerFoldable[V].foldLeft(sf, m.foldLeft[B](fingerFoldable[V].foldLeft(pr, b)(f))((x, y) => nodeFoldable[V].foldLeft(y, x)(f)))(f))
  }

  /**
   * Fold over the structure of the tree. The given functions correspond to the three possible variations of the finger tree.
   *
   * @param empty if the tree is empty, convert the measure to a `B`
   * @param single if the tree contains a single element, convert the measure and this element to a `B`
   * @param deep otherwise, convert the measure, the two fingers, and the sub tree to a `B`.
   */
  def fold[B](empty: V => B, single: (V, A) => B, deep: (V, Finger[V, A], => FingerTree[V, Node[V, A]], Finger[V, A]) => B): B

  /** Prepends an element to the left of the tree. O(1). */
  def +:(a: => A): FingerTree[V, A] = {
    implicit val nm = nodeMeasure[A, V]
    val az = Need(a)
    fold(
      v => single(measurer.cons(az.value, v), az.value),
      (v, b) => deep(measurer.cons(az.value, v), one(az.value), empty[V, Node[V, A]], one(b)),
      (v, pr, m, sf) => {
        val mz = m
        pr match {
          case Four(vf, b, c, d, e) => deep(measurer.cons(az.value, v), two(az.value, b), node3(c, d, e) +: mz, sf)
          case _ => deep(measurer.cons(az.value, v), az.value +: pr, mz, sf)
      }})
  }

  /** Appends an element to the right of the tree. O(1). */
  def :+(a: => A): FingerTree[V, A] = {
    implicit val nm = nodeMeasure[A, V]
    val az = Need(a)
    fold(
      v => single(measurer.snoc(v, az.value), az.value),
      (v, b) => deep(measurer.snoc(v, az.value), one(b), empty[V, Node[V, A]], one(az.value)),
      (v, pr, m, sf) => {
        val mz = m
        sf match {
          case Four(vf, b, c, d, e) => deep(measurer.snoc(v, az.value), pr, (mz :+ node3(b, c, d)), two(e, az.value))
          case _ => deep(measurer.snoc(v, az.value), pr, mz, sf :+ az.value)
      }})
  }

  /** Replace the first element of the tree with the given value. O(1) */
  def |-:(a: => A): FingerTree[V, A] = {
    val az = Need(a)
    fold(
      v => sys.error("Replacing first element of an empty FingerTree"),
      (v, b) => single(az.value),
      (v, pr, m, sf) => deep(az.value |-: pr, m, sf))
  }

  /** Replace the last element of the tree with the given value. O(1) */
  def :-|(a: => A): FingerTree[V, A] = {
    val az = Need(a)
    fold(
      v => sys.error("Replacing last element of an empty FingerTree"),
      (v, b) => single(az.value),
      (v, pr, m, sf) => deep(pr, m, sf :-| az.value))
  }

  /** Appends the given finger tree to the right of this tree. */
  def <++>(right: => FingerTree[V, A]): FingerTree[V, A] = {
    val rightz = Need(right)
    fold(
      v => rightz.value,
      (v, x) => x +: rightz.value,
      (v1, pr1, m1, sf1) =>
        rightz.value.fold(
          v => this,
          (v, x) => this :+ x,
          (v2, pr2, m2, sf2) => deep(measurer.append(v1, v2), pr1, addDigits0(m1, sf1, pr2, m2), sf2)
        )
    )
  }

  private type ATree = FingerTree[V, A]
  private type AFinger = Finger[V, A]
  private type NodeTree = FingerTree[V, Node[V, A]]

  private implicit def sg: Monoid[V] = measurer.monoid

  def add1(n: A, right: => ATree): ATree = {
    val rightz = Need(right)
    fold(
      v => n +: rightz.value,
      (v, x) => x +: n +: rightz.value,
      (v1, pr1, m1, sf1) =>
        rightz.value.fold(
          v => this :+ n,
          (v, x) => this :+ n :+ x,
          (v2, pr2, m2, sf2) =>
            deep(measurer.append((measurer.snoc(v1, n)), v2), pr1, addDigits1(m1, sf1, n, pr2, m2), sf2)
        )
    )
  }

  def add2(n1t: => A, n2t: => A, right: => ATree): ATree = {
    val rightz = Need(right)
    val n1 = Need(n1t)
    val n2 = Need(n2t)
    fold(
      v => n1.value +: n2.value +: rightz.value,
      (v, x) => x +: n1.value +: n2.value +: rightz.value,
      (v1, pr1, m1, sf1) =>
        rightz.value.fold(
          v => this :+ n1.value :+ n2.value,
          (v, x) => this :+ n1.value :+ n2.value :+ x,
          (v2, pr2, m2, sf2) =>
            deep(measurer.append(measurer.snoc(measurer.snoc(v1, n1.value), n2.value), v2),
              pr1, addDigits2(m1, sf1, n1.value, n2.value, pr2, m2), sf2)
        )
    )
  }

  def add3(n1t: => A, n2t: => A, n3t: => A, right: => ATree): ATree = {
    val rightz = Need(right)
    val n1 = Need(n1t)
    val n2 = Need(n2t)
    val n3 = Need(n3t)
    fold(
      v => n1.value +: n2.value +: n3.value +: rightz.value,
      (v, x) => x +: n1.value +: n2.value +: n3.value +: rightz.value,
      (v1, pr1, m1, sf1) =>
        rightz.value.fold(
           v => this :+ n1.value :+ n2.value :+ n3.value,
           (v, x) => this :+ n1.value :+ n2.value :+ n3.value :+ x,
           (v2, pr2, m2, sf2) =>
             deep(measurer.append(measurer.snoc(measurer.snoc(measurer.snoc(v1, n1.value), n2.value), n3.value), v2),
               pr1, addDigits3(m1, sf1, n1.value, n2.value, n3.value, pr2, m2), sf2)
        )
    )
  }

  def add4(n1t: => A, n2t: => A, n3t: => A, n4t: => A, right: => ATree): ATree = {
    val rightz = Need(right)
    val n1 = Need(n1t)
    val n2 = Need(n2t)
    val n3 = Need(n3t)
    val n4 = Need(n4t)
    fold(
      v => n1.value +: n2.value +: n3.value +: n4.value +: rightz.value,
      (v, x) => x +: n1.value +: n2.value +: n3.value +: n4.value +: rightz.value,
      (v1, pr1, m1, sf1) =>
        rightz.value.fold(
          v => this :+ n1.value :+ n2.value :+ n3.value :+ n4.value,
          (v, x) => this :+ n1.value :+ n2.value :+ n3.value :+ n4.value :+ x,
          (v2, pr2, m2, sf2) =>
            deep(measurer.append(measurer.snoc(measurer.snoc(measurer.snoc(measurer.snoc(v1, n1.value), n2.value), n3.value), n4.value), v2),
              pr1, addDigits4(m1, sf1, n1.value, n2.value, n3.value, n4.value, pr2, m2), sf2)
        )
    )
  }

  def addDigits0(m1: NodeTree, dig1: AFinger, dig2: AFinger, 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: AFinger, xt: => A, d2: AFinger, m2t: => NodeTree): NodeTree = {
    val x = Need(xt)
    val m2 = Need(m2t)
    d1 match {
      case One(_, a) => d2 match {
        case One(_, b) => m1.add1(node3(a,x.value,b), m2.value)
        case Two(_, b,c) => m1.add2(node2(a,x.value), node2(b,c), m2.value)
        case Three(_, b,c,d) => m1.add2(node3(a,x.value,b), node2(c,d), m2.value)
        case Four(_, b,c,d,e) => m1.add2(node3(a,x.value,b), node3(c,d,e), m2.value)
      }
      case Two(_, a,b) => d2 match {
        case One(_, c) => m1.add2(node2(a,b), node2(x.value,c), m2.value)
        case Two(_, c,d) => m1.add2(node3(a,b,x.value), node2(c,d), m2.value)
        case Three(_, c,d,e) => m1.add2(node3(a,b,x.value), node3(c,d,e), m2.value)
        case Four(_, c,d,e,f) => m1.add3(node3(a,b,x.value), node2(c,d), node2(e,f), m2.value)
      }
      case Three(_, a,b,c) => d2 match {
        case One(_, d) => m1.add2(node3(a,b,c), node2(x.value,d), m2.value)
        case Two(_, d,e) => m1.add2(node3(a,b,c), node3(x.value,d,e), m2.value)
        case Three(_, d,e,f) => m1.add3(node3(a,b,c), node2(x.value,d), node2(e,f), m2.value)
        case Four(_, d,e,f,g) => m1.add3(node3(a,b,c), node3(x.value,d,e), node2(f,g), m2.value)
      }
      case Four(_, a,b,c,d) => d2 match {
        case One(_, e) => m1.add2(node3(a,b,c), node3(d,x.value,e), m2.value)
        case Two(_, e,f) => m1.add3(node3(a,b,c), node2(d,x.value), node2(e,f), m2.value)
        case Three(_, e,f,g) => m1.add3(node3(a,b,c), node3(d,x.value,e), node2(f,g), m2.value)
        case Four(_, e,f,g,h) => m1.add3(node3(a,b,c), node3(d,x.value,e), node3(f,g,h), m2.value)
      }
    }
  }

  def addDigits2(m1: NodeTree, d1: AFinger, xt: => A, yt: => A, d2: AFinger, m2t: => NodeTree): NodeTree = {
    val x = Need(xt)
    val y = Need(yt)
    val m2 = Need(m2t)
    d1 match {
      case One(_, a) => d2 match {
        case One(_, b) => m1.add2(node2(a,x.value), node2(y.value,b), m2.value)
        case Two(_, b,c) => m1.add2(node3(a,x.value,y.value), node2(b,c), m2.value)
        case Three(_, b,c,d) => m1.add2(node3(a,x.value,y.value), node3(b,c,d), m2.value)
        case Four(_, b,c,d,e) => m1.add3(node3(a,x.value,y.value), node2(b,c), node2(d,e), m2.value)
      }
      case Two(_, a,b) => d2 match {
        case One(_, c) => m1.add2(node3(a,b,x.value), node2(y.value,c), m2.value)
        case Two(_, c,d) => m1.add2(node3(a,b,x.value), node3(y.value,c,d), m2.value)
        case Three(_, c,d,e) => m1.add3(node3(a,b,x.value), node2(y.value,c), node2(d,e), m2.value)
        case Four(_, c,d,e,f) => m1.add3(node3(a,b,x.value), node3(y.value,c,d), node2(e,f), m2.value)
      }
      case Three(_, a,b,c) => d2 match {
        case One(_, d) => m1.add2(node3(a,b,c), node3(x.value,y.value,d), m2.value)
        case Two(_, d,e) => m1.add3(node3(a,b,c), node2(x.value,y.value), node2(d,e), m2.value)
        case Three(_, d,e,f) => m1.add3(node3(a,b,c), node3(x.value,y.value,d), node2(e,f), m2.value)
        case Four(_, d,e,f,g) => m1.add3(node3(a,b,c), node3(x.value,y.value,d), node3(e,f,g), m2.value)
      }
      case Four(_, a,b,c,d) => d2 match {
        case One(_, e) => m1.add3(node3(a,b,c), node2(d,x.value), node2(y.value,e), m2.value)
        case Two(_, e,f) => m1.add3(node3(a,b,c), node3(d,x.value,y.value), node2(e,f), m2.value)
        case Three(_, e,f,g) => m1.add3(node3(a,b,c), node3(d,x.value,y.value), node3(e,f,g), m2.value)
        case Four(_, e,f,g,h) => m1.add4(node3(a,b,c), node3(d,x.value,y.value), node2(e,f), node2(g,h), m2.value)
      }
    }
  }

  def addDigits3(m1: NodeTree, d1: AFinger, xt: => A, yt: => A, zt: => A, d2: AFinger, m2t: => NodeTree): NodeTree = {
    val x = Need(xt)
    val y = Need(yt)
    val z = Need(zt)
    val m2 = Need(m2t)
    d1 match {
      case One(_, a) => d2 match {
        case One(_, b) => m1.add2(node3(a,x.value,y.value), node2(z.value,b), m2.value)
        case Two(_, b,c) => m1.add2(node3(a,x.value,y.value), node3(z.value,b,c), m2.value)
        case Three(_, b,c,d) => m1.add3(node3(a,x.value,y.value), node2(z.value,b), node2(c,d), m2.value)
        case Four(_, b,c,d,e) => m1.add3(node3(a,x.value,y.value), node3(z.value,b,c), node2(d,e), m2.value)
      }
      case Two(_, a,b) => d2 match {
        case One(_, c) => m1.add2(node3(a,b,x.value), node3(y.value,z.value,c), m2.value)
        case Two(_, c,d) => m1.add3(node3(a,b,x.value), node2(y.value,z.value), node2(c,d), m2.value)
        case Three(_, c,d,e) => m1.add3(node3(a,b,x.value), node3(y.value,z.value,c), node2(d,e), m2.value)
        case Four(_, c,d,e,f) => m1.add3(node3(a,b,x.value), node3(y.value,z.value,c), node3(d,e,f),m2.value)
      }
      case Three(_, a,b,c) => d2 match {
        case One(_, d) => m1.add3(node3(a,b,c), node2(x.value,y.value), node2(z.value,d), m2.value)
        case Two(_, d,e) => m1.add3(node3(a,b,c), node3(x.value,y.value,z.value), node2(d,e), m2.value)
        case Three(_, d,e,f) => m1.add3(node3(a,b,c), node3(x.value,y.value,z.value), node3(d,e,f), m2.value)
        case Four(_, d,e,f,g) => m1.add4(node3(a,b,c), node3(x.value,y.value,z.value), node2(d,e), node2(f,g), m2.value)
      }
      case Four(_, a,b,c,d) => d2 match {
        case One(_, e) => m1.add3(node3(a,b,c), node3(d,x.value,y.value), node2(z.value,e), m2.value)
        case Two(_, e,f) => m1.add3(node3(a,b,c), node3(d,x.value,y.value), node3(z.value,e,f), m2.value)
        case Three(_, e,f,g) => m1.add4(node3(a,b,c), node3(d,x.value,y.value), node2(z.value,e),node2(f,g), m2.value)
        case Four(_, e,f,g,h) => m1.add4(node3(a,b,c), node3(d,x.value,y.value), node3(z.value,e,f), node2(g,h), m2.value)
      }
    }
  }

  def addDigits4(m1: NodeTree, d1: AFinger, xt: => A, yt: => A, zt: => A, wt: => A, d2: AFinger, m2t: => NodeTree): NodeTree = {
      val x = Need(xt)
      val y = Need(yt)
      val z = Need(zt)
      val w = Need(wt)
      val m2 = Need(m2t)
      d1 match {
      case One(_, a) => d2 match {
        case One(_, b) => m1.add2(node3(a,x.value,y.value), node3(z.value,w.value,b), m2.value)
        case Two(_, b,c) => m1.add3(node3(a,x.value,y.value), node2(z.value,w.value), node2(b,c), m2.value)
        case Three(_, b,c,d) => m1.add3(node3(a,x.value,y.value), node3(z.value,w.value,b), node2(c,d), m2.value)
        case Four(_, b,c,d,e) => m1.add3(node3(a,x.value,y.value), node3(z.value,w.value,b), node3(c,d,e), m2.value)
      }
      case Two(_, a,b) => d2 match {
        case One(_, c) => m1.add3(node3(a,b,x.value), node2(y.value,z.value), node2(w.value,c), m2.value)
        case Two(_, c,d) => m1.add3(node3(a,b,x.value), node3(y.value,z.value,w.value), node2(c,d), m2.value)
        case Three(_, c,d,e) => m1.add3(node3(a,b,x.value), node3(y.value,z.value,w.value), node3(c,d,e), m2.value)
        case Four(_, c,d,e,f) => m1.add4(node3(a,b,x.value), node3(y.value,z.value,w.value), node2(c,d), node2(e,f),m2.value)
      }
      case Three(_, a,b,c) => d2 match {
        case One(_, d) => m1.add3(node3(a,b,c), node3(x.value,y.value,z.value), node2(w.value,d), m2.value)
        case Two(_, d,e) => m1.add3(node3(a,b,c), node3(x.value,y.value,z.value), node3(w.value,d,e), m2.value)
        case Three(_, d,e,f) => m1.add4(node3(a,b,c), node3(x.value,y.value,z.value), node2(w.value,d),node2(e,f), m2.value)
        case Four(_, d,e,f,g) => m1.add4(node3(a,b,c), node3(x.value,y.value,z.value), node3(w.value,d,e), node2(f,g), m2.value)
      }
      case Four(_, a,b,c,d) => d2 match {
        case One(_, e) => m1.add3(node3(a,b,c), node3(d,x.value,y.value), node3(z.value,w.value,e), m2.value)
        case Two(_, e,f) => m1.add4(node3(a,b,c), node3(d,x.value,y.value), node2(z.value,w.value), node2(e,f), m2.value)
        case Three(_, e,f,g) => m1.add4(node3(a,b,c), node3(d,x.value,y.value), node3(z.value,w.value,e),node2(f,g), m2.value)
        case Four(_, e,f,g,h) => m1.add4(node3(a,b,c), node3(d,x.value,y.value), node3(z.value,w.value,e), node3(f,g,h), m2.value)
      }
    }
  }

  /**
   * Splits this tree into a pair of subtrees at the point where the given predicate, based on the measure,
   * changes from `true` to `false`. O(log(min(i,n-i)))
   *
   * @return `(as, bs)` `as`: the subtree containing elements before the point where `pred` first holds
   *                    `fs` the subtree containing element at and after the point where `pred` first holds. Empty if `pred` never holds.
   */
  def split(pred: V => Boolean): (FingerTree[V, A], FingerTree[V, A]) =
    if (!isEmpty && pred(measure)) {
      val (l, x, r) = split1(pred)
      (l, x +: r)
    }
    else
      (this, empty)

  /**
   * Like `split`, but returns the element where `pred` first holds separately
   *
   * @throws if the tree is empty.
   */
  def split1(pred: V => Boolean): (FingerTree[V, A], A, FingerTree[V, A]) = split1(pred, measurer.monoid.zero)

  private def split1(pred: V => Boolean, accV: V): (FingerTree[V, A], A, FingerTree[V, A]) = fold(
    v => sys.error("Splitting an empty FingerTree"), // we can never get here
    (v, x) => (empty, x, empty),
    (v, pr, m, sf) => {
      val accVpr = fingerMeasure[A, V].snoc(accV, pr)
      if (pred(accVpr)) {
        val (l, x, r) = pr.split1(pred, accV)
        (cata(l)(_.toTree, empty), x, deepL(r, m, sf))
      } else {
        val accVm = mappendVal(accVpr, m)
        if (pred(accVm)) {
          val (ml, xs, mr) = m.split1(pred, accVpr)
          val (l, x, r) = xs.split1(pred, mappendVal(accVpr, ml))
          (deepR(pr, ml, l), x, deepL(r, mr, sf))
        } else {
          val (l, x, r) = sf.split1(pred, accVm)
          (deepR(pr, m, l), x, cata(r)(_.toTree, empty))
        }
      }
    }
  )

  def isEmpty: Boolean = fold(v => true, (v, x) => false, (v, pr, m, sf) => false)

  def viewl: ViewL[FingerTree[V, ?], A] =
    fold(
      v => EmptyL[FingerTree[V, ?], A],
      (v, x) => OnL[FingerTree[V, ?], A](x, empty[V, A]),
      (v, pr, m, sf) =>
        pr match {
          case One(v, x) => OnL[FingerTree[V, ?], A](x, rotL(m, sf))
          case _ => OnL[FingerTree[V, ?], A](pr.lhead, deep(pr.ltail, m, sf))
        })

  def viewr: ViewR[FingerTree[V, ?], A] =
    fold(
      v => EmptyR[FingerTree[V, ?], A],
      (v, x) => OnR[FingerTree[V, ?], A](empty[V, A], x),
      (v, pr, m, sf) =>
        sf match {
          case One(v, x) => OnR[FingerTree[V, ?], A](rotR(pr, m), x)
          case _ => OnR[FingerTree[V, ?], A](deep(pr, m, sf.rtail), sf.rhead)
        })

  /**
   * Selects the first element in the tree.
   *
   * @throws if the tree is empty
   */
  def head: A = viewl.head

  /**
   * Selects the last element in the tree.
   *
   * @throws if the tree is empty
   */
  def last: A = viewr.last

  /**
   * Selects a subtree containing all elements except the first
   *
   * @throws if the tree is empty
   */
  def tail: FingerTree[V, A] = viewl.tail

  /**
   * Selects a subtree containing all elements except the last
   *
   * @throws if the tree is empty
   */
  def init: FingerTree[V, A] = viewr.init

  /** Maps the given function across the tree, annotating nodes in the resulting tree according to the provided `Reducer`. */
  def map[B, V2](f: A => B)(implicit m: Reducer[B, V2]): FingerTree[V2, B] = {
    implicit val nm = nodeMeasure[B, V2]
    fold(
      v => empty,
      (v, x) => single(f(x)),
      (v, pr, mt, sf) => deep(pr map f, mt.map(x => x.map(f)), sf map f))
  }

  /**
   * Like traverse, but with a more constraint type: we need the additional measure to construct the new tree.
   */
  def traverseTree[F[_], V2, B](f: A => F[B])(implicit ms: Reducer[B, V2], F: Applicative[F]): F[FingerTree[V2, B]] = {
    def mkDeep(pr: Finger[V2, B])(m: FingerTree[V2, Node[V2, B]])(sf: Finger[V2, B]): FingerTree[V2, B] = deep(pr, m, sf)
    fold(_ => F.pure(FingerTree.empty[V2, B]),
         (v, a) => F.map(f(a))(a => single(ms.unit(a), a)),
         (v, pr, m, sf) => {
           //F.ap(traverseFinger(sf)(f))(F.ap(m.traverseTree(n => traverseNode(n)(f)))(F.map(traverseFinger(pr)(f))(pr => mkDeep(pr)_)))
           //the implementation below seems most efficient. The straightforward implementation using F.map3 leads to an explosion of traverseTree calls
           val fmap2 = F.apply2(traverseFinger(pr)(f), m.traverseTree(n => traverseNode(n)(f)))((a,b) => mkDeep(a)(b)_)
           F.ap(traverseFinger(sf)(f))(fmap2)
        })
  }

  private def traverseNode[F[_], V2, B](node: Node[V, A])(f: A => F[B])(implicit ms: Reducer[B, V2], F: Applicative[F]): F[Node[V2, B]] = {
    def mkNode(x: B)(y: B)(z: B): Node[V2, B] = node3(x, y, z)
    node.fold((v, a, b) => F.apply2(f(a), f(b))((x, y) => node2(x, y)),
        (v, a, b, c) =>  {
          F.ap(f(c))(F.ap(f(b))(F.map(f(a))(x => mkNode(x)_)))
        }
    )
  }

  private def traverseFinger[F[_], A, B, V2](digit: Finger[V, A])(f: A => F[B])(implicit ms: Reducer[B, V2], F: Applicative[F]): F[Finger[V2, B]] = {
    def mkTwo(x: B)(y: B): Finger[V2, B] = two(x, y)
    def mkThree(x: B)(y: B)(z: B): Finger[V2, B] = three(x, y, z)
    def mkFour(w: B)(x: B)(y: B)(z: B): Finger[V2, B] = four(w, x, y, z)
    digit match {
      case One(v, a) => F.map(f(a))(x => one(x))
      case Two(v, a, b) => F.ap(f(b))(F.map(f(a))(x => mkTwo(x)_))
      case Three(v, a, b, c) => F.ap(f(c))(F.ap(f(b))(F.map(f(a))(x => mkThree(x)_)))
      case Four(v, a, b, c, d) => F.ap(f(d))(F.ap(f(c))(F.ap(f(b))(F.map(f(a))(x => mkFour(x)_))))
    }
  }

  /** Execute the provided side effect for each element in the tree. */
  def foreach(f: A => Unit) {
    fold(
      _ => {},
      (_, x) => { f(x) },
      (_, pr, m, sf) => { pr.foreach(f); m.foreach(_.foreach(f)); sf.foreach(f) }
    )}

  /** An iterator that visits each element in the tree. */
  def iterator: Iterator[A] = fold(
    _ => Iterator.empty,
    (_, x) => Iterator.single(x),
    (_, pr, m, sf) => pr.iterator ++ m.iterator.flatMap(_.iterator) ++ sf.iterator)

  /** An iterator that visits each element in the tree in reverse order. */
  def reverseIterator: Iterator[A] = fold(
    _ => Iterator.empty,
    (_, x) => Iterator.single(x),
    (_, pr, m, sf) => sf.reverseIterator ++ m.reverseIterator.flatMap(_.reverseIterator) ++ pr.reverseIterator)

  /** Convert the leaves of the tree to a `scala.Stream` */
  def toStream: Stream[A] = map(x => x)(Reducer.StreamReducer[A]).measure

  /** Convert the leaves of the tree to a `scala.List` */
  def toList: List[A] = toStream.toList

  /** Convert the tree to a `String`. Unsafe: this uses `Any#toString` for types `V` and `A` */
  override def toString = {
    val showV = Show.showFromToString[V]
    val showA = Show.showFromToString[A]
    fingerTreeShow(showV, showA).shows(this)
  }
}

sealed abstract class FingerTreeInstances {
  import FingerTree._

  implicit def viewLFunctor[S[_]](implicit s: Functor[S]): Functor[ViewL[S, ?]] =
    new Functor[ViewL[S, ?]] {
      def map[A, B](t: ViewL[S, A])(f: A => B): ViewL[S, B] =
        t.fold(EmptyL[S, B], (x, xs) => OnL(f(x), s.map(xs)(f))) //TODO define syntax for &: and :&
    }

  implicit def viewRFunctor[S[_]](implicit s: Functor[S]): Functor[ViewR[S, ?]] =
    new Functor[ViewR[S, ?]] {
      def map[A, B](t: ViewR[S, A])(f: A => B): ViewR[S, B] =
        t.fold(EmptyR[S, B], (xs, x) => OnR(s.map(xs)(f), f(x)))
    }

  implicit def fingerFoldable[V] =
    new Foldable[Finger[V, ?]] with Foldable.FromFoldMap[Finger[V, ?]] {
      override def foldMap[A, M: Monoid](v: Finger[V, A])(f: A => M) = v.foldMap(f)
    }

  implicit def fingerMeasure[A, V](implicit m: Reducer[A, V]): Reducer[Finger[V, A], V] = {
    implicit val vm = m.monoid
    UnitReducer((a: Finger[V, A]) => a.measure)
  }

  implicit def nodeMeasure[A, V](implicit m: Reducer[A, V]): Reducer[Node[V, A], V] = {
    implicit val vm = m.monoid
    UnitReducer((a: Node[V, A]) => a fold (
            (v, _, _) => v,
            (v, _, _, _) => v))
  }

  implicit def fingerTreeMeasure[A, V](implicit m: Reducer[A, V]): Reducer[FingerTree[V, A], V] = {
    implicit val vm = m.monoid
    UnitReducer((a: FingerTree[V, A]) => a.fold(v => v, (v, x) => v, (v, x, y, z) => v))
  }

  implicit def nodeFoldable[V] =
    new Foldable[Node[V, ?]] {
      def foldMap[A, M: Monoid](t: Node[V, A])(f: A => M): M = t foldMap f
      def foldRight[A, B](v: Node[V, A], z: => B)(f: (A, => B) => B): B =
         foldMap(v)((a: A) => (Endo.endo(f.curried(a)(_: B)))) apply z
    }

  implicit def fingerTreeFoldable[V]: Foldable[FingerTree[V, ?]] =
    new Foldable[FingerTree[V, ?]] {
      override def foldLeft[A, B](t: FingerTree[V, A], b: B)(f: (B, A) => B) = t.foldLeft(b)(f)

      def foldMap[A, M: Monoid](t: FingerTree[V, A])(f: A => M): M = t foldMap(f)

      override def foldRight[A, B](t: FingerTree[V, A], z: => B)(f: (A, => B) => B) = t.foldRight(z)(f)
    }

  implicit def fingerTreeMonoid[V, A](implicit m: Reducer[A, V]): Monoid[FingerTree[V, A]] =
    new Monoid[FingerTree[V, A]] {
      def append(f1: FingerTree[V, A], f2: => FingerTree[V, A]) = f1 <++> f2
      def zero = empty
    }

  implicit def fingerTreeShow[V, A](implicit V: Show[V], A: Show[A]): Show[FingerTree[V,A]] =
    new Show[FingerTree[V,A]] {
      import std.iterable._
      val AS = Show[List[A]]
      import Cord._
      override def show(t: FingerTree[V,A]) = t.fold(
        empty = v => Cord(V.show(v), " []"),
        single = (v, x) => Cord(V.show(v), " [", A.show(x), "]"),
        deep = (v, pf, m, sf) => Cord(V.show(v), " [", AS.show(pf.toList), ", ?, ", AS.show(sf.toList), "]")
      )
    }

  implicit def fingerTreeEqual[V, A : Equal]: Equal[FingerTree[V, A]] =
    new Equal[FingerTree[V, A]] {
      import std.stream._
      def equal(x: FingerTree[V, A], y: FingerTree[V, A]) =
        Equal[Stream[A]].equal(x.toStream, y.toStream)
    }
}

object FingerTree extends FingerTreeInstances {

  def Node2[V, A](v: V, a1: => A, a2: => A)(implicit r: Reducer[A, V]) =
    new Node[V, A] {
      def fold[B](two: (V, => A, => A) => B, three: (V, => A, => A, => A) => B) =
        two(v, a1, a2)
      val measure = v
    }

  def Node3[V, A](v: V, a1: => A, a2: => A, a3: => A)(implicit r: Reducer[A, V]) =
    new Node[V, A] {
      def fold[B](two: (V, => A, => A) => B, three: (V, => A, => A, => A) => B) =
        three(v, a1, a2, a3)
      val measure = v
    }

  def EmptyR[S[_], A]: ViewR[S, A] =
    new ViewR[S, A] {
      def fold[B](b: => B, f: (=> S[A], => A) => B) = b
    }

  def OnR[S[_], A](sa: => S[A], a: => A): ViewR[S, A] =
    new ViewR[S, A] {
      def fold[B](b: => B, f: (=> S[A], => A) => B) = f(sa, a)
    }

  def EmptyL[S[_], A]: ViewL[S, A] =
    new ViewL[S, A] {
      def fold[B](b: => B, f: (=> A, => S[A]) => B) = b
    }

  def OnL[S[_], A](a: => A, sa: => S[A]): ViewL[S, A] =
    new ViewL[S, A] {
      def fold[B](b: => B, f: (=> A, => S[A]) => B) = f(a, sa)
    }

  def one[V, A](a: A)(implicit measure: Reducer[A, V]) =
    One(measure.unit(a), a)

  def two[V, A](a1: A, a2: A)(implicit measure: Reducer[A, V]) =
    Two(measure.snoc(measure.unit(a1), a2), a1, a2)

  def three[V, A](a1: A, a2: A, a3: A)(implicit measure: Reducer[A, V]) =
    Three(measure.snoc(measure.snoc(measure.unit(a1), a2), a3), a1, a2, a3)

  def four[V, A](a1: A, a2: A, a3: A, a4: A)(implicit measure: Reducer[A, V]) =
    Four(measure.snoc(measure.snoc(measure.snoc(measure.unit(a1), a2), a3), a4), a1, a2, a3, a4)

  def node2[V, A](a: A, b: A)(implicit measure: Reducer[A, V]) =
    Node2[V, A](measure.snoc(measure.unit(a), b), a, b)

  def node3[V, A](a: A, b: A, c: A)(implicit measure: Reducer[A, V]) =
    Node3[V, A](measure.snoc(measure.snoc(measure.unit(a), b), c), a, b, c)

  def mappendVal[V, A](v: V, t: FingerTree[V, A])(implicit measure: Reducer[A, V]) =
    t.fold(x => v, (x, y) => fingerTreeMeasure[A, V].snoc(v, t), (x, p, m, s) => fingerTreeMeasure[A, V].snoc(v, t))

  def empty[V, A](implicit ms: Reducer[A, V]) =
    new FingerTree[V, A] {
      def fold[B](b: V => B, s: (V, A) => B, d: (V, Finger[V, A], => FingerTree[V, Node[V, A]], Finger[V, A]) => B): B = b(ms.monoid.zero)
    }

  def single[V, A](a: A)(implicit ms: Reducer[A, V]): FingerTree[V, A] = single(ms.unit(a), a)

  def single[V, A](v: V, a: => A)(implicit ms: Reducer[A, V]): FingerTree[V, A] =
    new FingerTree[V, A] {
      def fold[B](b: V => B, s: (V, A) => B, d: (V, Finger[V, A], => FingerTree[V, Node[V, A]], Finger[V, A]) => B): B = s(v, a)
    }

  def deep[V, A](pr: Finger[V, A], m: => FingerTree[V, Node[V, A]], sf: Finger[V, A])
             (implicit ms: Reducer[A, V]): FingerTree[V, A] = {
    val measure = fingerMeasure[A, V]
    deep(measure.snoc(mappendVal(measure.unit(pr), m), sf), pr, m, sf)
  }

  def deep[V, A](v: V, pr: Finger[V, A], m: => FingerTree[V, Node[V, A]], sf: Finger[V, A])
             (implicit ms: Reducer[A, V]): FingerTree[V, A] =
    new FingerTree[V, A] {
      implicit val nMeasure = nodeMeasure[A, V]
      private[this] val mz = Need(m)
      def fold[B](b: V => B, f: (V, A) => B, d: (V, Finger[V, A], => FingerTree[V, Node[V, A]], Finger[V, A]) => B): B =
        d(v, pr, mz.value, sf)
    }

  def deepL[V, A](mpr: Option[Finger[V, A]], m: => FingerTree[V, Node[V, A]], sf: Finger[V, A])(implicit ms: Reducer[A, V]): FingerTree[V, A] =
    mpr match {
      case None => rotL(m, sf)
      case Some(pr) => deep(pr, m, sf)
    }

  def deepR[V, A](pr: Finger[V, A], m: => FingerTree[V, Node[V, A]], msf: Option[Finger[V, A]])(implicit ms: Reducer[A, V]): FingerTree[V, A] =
    msf match {
      case None => rotR(pr, m)
      case Some(sf) => deep(pr, m, sf)
    }

  def rotL[V, A](m: FingerTree[V, Node[V, A]], sf: Finger[V, A])(implicit ms: Reducer[A, V]): FingerTree[V, A] =
    m.viewl.fold(
      sf.toTree,
      (a, mm) => deep(fingerMeasure[A, V].snoc(m.measure, sf), a.toDigit, mm, sf))

  def rotR[V, A](pr: Finger[V, A], m: FingerTree[V, Node[V, A]])(implicit ms: Reducer[A, V]): FingerTree[V, A] =
    m.viewr.fold(
      pr.toTree,
      (mm, a) => deep(mappendVal(pr.measure, m), pr, mm, a.toDigit))

}

/** Indexed sequences, based on [[scalaz.FingerTree]]
 *
 * The measure is the count of the preceding elements, provided by `UnitReducer((e: Int) => 1)`.
 */
final class IndSeq[A](val self: FingerTree[Int, A]) {

  import std.anyVal._
  import IndSeq.indSeq

  implicit def sizer[A] = UnitReducer((a: A) => 1)
  def apply(i: Int): A =
    self.split(_ > i)._2.viewl.headOption.getOrElse(sys.error("Index " + i + " > " + self.measure))
  def replace(i: Int, a: => A): IndSeq[A] = {
    val (l, r) = self.split(_ > i)
    indSeq(l <++> (a |-: r))
  }
  def split(i: Int): (IndSeq[A], IndSeq[A]) = {
    val (l, r) = self.split(_ > i)
    (indSeq(l), indSeq(r))
  }
  def ++(xs: IndSeq[A]): IndSeq[A] = indSeq(self <++> xs.self)
  def :+(x: => A): IndSeq[A] = indSeq(self :+ x)
  def +:(x: => A): IndSeq[A] = indSeq(x +: self)
  def length: Int = self.measure
  def tail: IndSeq[A] = indSeq(self.tail)
  def init: IndSeq[A] = indSeq(self.init)
  def drop(n: Int): IndSeq[A] = split(n)._2
  def take(n: Int): IndSeq[A] = split(n)._1
  def map[B](f: A => B): IndSeq[B] = indSeq(self map f)

  import FingerTree.fingerTreeFoldable

  def flatMap[B](f: A => IndSeq[B]): IndSeq[B] = indSeq(fingerTreeFoldable.foldLeft(self, empty[Int, B])((ys, x) => ys <++> f(x).self))
}

object IndSeq extends IndSeqInstances {
  private def indSeq[A](v: FingerTree[Int, A]): IndSeq[A] = new IndSeq(v)

  import std.anyVal._

  def apply[A](as: A*) = fromSeq(as)
  def fromSeq[A](as: Seq[A]) = indSeq(as.foldLeft(empty[Int, A](UnitReducer(a => 1)))((x, y) => x :+ y))
}

sealed abstract class IndSeqInstances {

  implicit def indSeqEqual[A: Equal]: Equal[IndSeq[A]] =
    Equal.equalBy(_.self)

  implicit val indSeqInstance: MonadPlus[IndSeq] with Traverse[IndSeq] with IsEmpty[IndSeq] =
    new MonadPlus[IndSeq] with Traverse[IndSeq] with IsEmpty[IndSeq] with IsomorphismFoldable[IndSeq, FingerTree[Int, ?]]{
      def G = implicitly
      override val naturalTrans = new (IndSeq ~> FingerTree[Int, ?]) {
        def apply[A](a: IndSeq[A]) =
          a.self
      }
      def traverseImpl[G[_], A, B](fa: IndSeq[A])(f: A => G[B])(implicit G: Applicative[G]) = {
        import std.anyVal._
        implicit val r = UnitReducer((_: B) => 1)
        G.map(fa.self.traverseTree(f))(new IndSeq(_))
      }
      override def length[A](fa: IndSeq[A]) =
        fa.length
      override def index[A](fa: IndSeq[A], i: Int) =
        if(0 <= i && i < fa.length) Some(fa(i)) else None
      override def isEmpty[A](fa: IndSeq[A]) =
        fa.self.isEmpty
      override def empty[A](fa: IndSeq[A]) =
        fa.self.isEmpty
      def point[A](a: => A) =
        IndSeq(a)
      def bind[A, B](fa: IndSeq[A])(f: A => IndSeq[B]) =
        fa flatMap f
      override def map[A, B](fa: IndSeq[A])(f: A => B) =
        fa map f
      def plus[A](a: IndSeq[A], b: => IndSeq[A]) =
        a ++ b
      def empty[A] =
        IndSeq.apply()
    }
}

/** Ordered sequences, based on [[scalaz.FingerTree]]
 *
 *  `a` has a higher priority than `b` if `Order[A].greaterThan(a, b)`.
 *
 * `insert` and `++` maintains the ordering.
 *
 * The measure is calculated with a `Monoid[Option[A] @@ Last]`, whose `append`
 * operation favours the first argument. Accordingly, the measuer of a node is the
 * item with the highest priority contained recursively below that node.
 */
sealed abstract class OrdSeq[A] extends Ops[FingerTree[LastOption[A], A]] {
  import std.function._
  import std.option._

  implicit val ord: Order[A]

  /**
   * @return (higher, lowerOrEqual) The sub-sequences that contain elements of higher and of lower-than-or-equal
   *                                priority than `a`, and of lower or equal priority respectively.
   */
  def partition(a: A): (OrdSeq[A], OrdSeq[A]) =
  function1Instance.product(OrdSeq.ordSeq[A](_: FingerTree[LastOption[A], A]))(self.split(a1 =>
    Order[LastOption[A]].greaterThanOrEqual(a1, Tags.Last(some(a)))))

  /** Insert `a` at a the first point that all elements to the left are of higher priority */
  def insert(a: A): OrdSeq[A] = partition(a) match {
    case (l, r) => OrdSeq.ordSeq(l <++> (a +: r))
  }

  /** Append `xs` to this sequence, reordering elements to  */
  def ++(xs: OrdSeq[A]): OrdSeq[A] = xs.self.toList.foldLeft(this)(_ insert _)
}

object OrdSeq {
  private def ordSeq[A: Order](t: FingerTree[LastOption[A], A]): OrdSeq[A] = new OrdSeq[A] {
    val self = t
    val ord = Order[A]
  }

  implicit def unwrap[A](t: OrdSeq[A]): FingerTree[LastOption[A], A] = t.self

  def apply[A: Order](as: A*): OrdSeq[A] = {
    val z: OrdSeq[A] = {
      val keyer: Reducer[A, LastOption[A]] = UnitReducer((a: A) => Tags.Last(some(a)))
      ordSeq(empty[LastOption[A], A](keyer))
    }
    as.foldLeft(z)((x, y) => x insert y)
  }
}

Other Scala examples (source code examples)

Here is a short list of links related to this Scala FingerTree.scala source code file:

... this post is sponsored by my books ...

#1 New Release!

FP Best Seller

 

new blog posts

 

Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.