Return to chapter index

25 The Architecture of Scala Collections

25.1 Builders

  package scala.collection.generic

  class Builder[-Elem, +To] {
    def +=(elem: Elem): this.type
    def result(): To
    def clear()
    def mapResult[NewTo](f: To => NewTo): Builder[Elem, NewTo]
      = ...
  }


  scala> val buf = new ArrayBuffer[Int]
  buf: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer()

  scala> val bldr = buf mapResult (_.toArray)
  bldr: scala.collection.mutable.Builder[Int,Array[Int]]
    = ArrayBuffer()


  

25.2 Factoring out common operations

  trait TraversableLike[+Elem, +Repr] { ... }


  package scala.collection

  trait TraversableLike[+Elem, +Repr] {
    def newBuilder: Builder[Elem, Repr] // deferred
    def foreach[U](f: Elem => U)        // deferred
            ...
    def filter(p: Elem => Boolean): Repr = {
      val b = newBuilder
      foreach { elem => if (p(elem)) b += elem }
      b.result
    } 
  }


  scala> import collection.immutable.BitSet
  import collection.immutable.BitSet

  scala> val bits = BitSet(1, 2, 3)
  bits: scala.collection.immutable.BitSet = BitSet(1, 2, 3)

  scala> bits map (_ * 2)
  res13: scala.collection.immutable.BitSet = BitSet(2, 4, 6)

  scala> bits map (_.toFloat)
  res14: scala.collection.immutable.Set[Float] =
    Set(1.0, 2.0, 3.0)


    scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => (y, x) }
    res3: scala.collection.immutable.Map[Int,java.lang.String] = 
      Map(1 -> a, 2 -> b)

    scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => y }
    res4: scala.collection.immutable.Iterable[Int] = 
      List(1, 2)


  def map[B, That](f: Elem => B)
      (implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(this)
    for (x <- this) b += f(x)
    b.result
  }


  package scala.collection.generic

  trait CanBuildFrom[-From, -Elem, +To] {
    // Creates a new builder 
    def apply(from: From): Builder[Elem, To] 
  }


  CanBuildFrom[Set[_], A, Set[A]]


  scala> val xs: Iterable[Int] = List(1, 2, 3)
  xs: Iterable[Int] = List(1, 2, 3)

  scala> val ys = xs map (x => x * x)
  ys: Iterable[Int] = List(1, 4, 9)


  

25.3 Integrating new collections

  abstract class Base
  case object A extends Base
  case object T extends Base
  case object G extends Base
  case object U extends Base

  object Base {
    val fromInt: Int => Base = Array(A, T, G, U)
    val toInt: Base => Int = Map(A -> 0, T -> 1, G -> 2, U -> 3)
  }


import collection.IndexedSeqLike
import collection.mutable.{Builder, ArrayBuffer}
import collection.generic.CanBuildFrom

final class RNA1 private (val groups: Array[Int],
    val length: Int) extends IndexedSeq[Base] {

  import RNA1._

  def apply(idx: Int): Base = {
    if (idx < 0 || length <= idx)
      throw new IndexOutOfBoundsException
    Base.fromInt(groups(idx / N) >> (idx % N * S) & M)
  }
}

object RNA1 {

  // Number of bits necessary to represent group
  private val S = 2            

  // Number of groups that fit in an Int
  private val N = 32 / S       

  // Bitmask to isolate a group
  private val M = (1 << S) - 1 

  def fromSeq(buf: Seq[Base]): RNA1 = {
    val groups = new Array[Int]((buf.length + N - 1) / N)
    for (i <- 0 until buf.length)
      groups(i / N) |= Base.toInt(buf(i)) << (i % N * S)
    new RNA1(groups, buf.length)
  }

  def apply(bases: Base*) = fromSeq(bases)
}


  scala> val xs = List(A, G, T, A)
  xs: List[Product with Base] = List(A, G, T, A)

  scala> RNA1.fromSeq(xs)
  res1: RNA1 = RNA1(A, G, T, A)

  scala> val rna1 = RNA1(A, U, G, G, T)
  rna1: RNA1 = RNA1(A, U, G, G, T)


  scala> rna1.length
  res2: Int = 5
  
  scala> rna1.last
  res3: Base = T

  scala> rna1.take(3)
  res4: IndexedSeq[Base] = Vector(A, U, G)


  def take(count: Int): RNA1 = RNA1.fromSeq(super.take(count))


final class RNA2 private (
  val groups: Array[Int],
  val length: Int
) extends IndexedSeq[Base] with IndexedSeqLike[Base, RNA2] {

  import RNA2._
    
  override def newBuilder: Builder[Base, RNA2] = 
    new ArrayBuffer[Base] mapResult fromSeq

  def apply(idx: Int): Base = // as before
}


\mbox{RNA2.scala:5: error: overriding method newBuilder in trait}
\mbox{TraversableLike of type => scala.collection.mutable.Builder[Base,RNA2];}
\mbox{ method newBuilder in trait GenericTraversableTemplate of type}
\mbox{ => scala.collection.mutable.Builder[Base,IndexedSeq[Base]] has}
\mbox{ incompatible type}
\mbox{class RNA2 private (val groups: Array[Int], val length: Int) }
      ^
\mbox{one error found}


  scala> val rna2 = RNA2(A, U, G, G, T)
  rna2: RNA2 = RNA2(A, U, G, G, T)

  scala> rna2 take 3
  res5: RNA2 = RNA2(A, U, G)

  scala> rna2 filter (U !=)
  res6: RNA2 = RNA2(A, G, G, T)


  scala> val rna = RNA(A, U, G, G, T)
  rna: RNA = RNA(A, U, G, G, T)

  scala> rna map { case A => T case b => b }
  res7: RNA = RNA(T, U, G, G, T)


  scala> rna ++ rna
  res8: RNA = RNA(A, U, G, G, T, A, U, G, G, T)


  scala> rna map Base.toInt
  res2: IndexedSeq[Int] = Vector(0, 3, 2, 2, 1)

  scala> rna ++ List("missing", "data")
  res3: IndexedSeq[java.lang.Object] = 
    Vector(A, U, G, G, T, missing, data)


  scala> val rna2 = RNA2(A, U, G, G, T)
  rna2: RNA2 = RNA2(A, U, G, G, T)

  scala> rna2 map { case A => T case b => b }
  res0: IndexedSeq[Base] = Vector(T, U, G, G, T)

  scala> rna2 ++ rna2
  res1: IndexedSeq[Base] = Vector(A, U, G, G, T, A, U, G, G, T)


  def map[B, That](f: Elem => B)
    (implicit cbf: CanBuildFrom[Repr, B, That]): That


final class RNA private (val groups: Array[Int], val length: Int) 
  extends IndexedSeq[Base] with IndexedSeqLike[Base, RNA] {

  import RNA._

  // Mandatory re-implementation of `newBuilder` in `IndexedSeq`
  override protected[this] def newBuilder: Builder[Base, RNA] = 
    RNA.newBuilder

  // Mandatory implementation of `apply` in `IndexedSeq`
  def apply(idx: Int): Base = {
    if (idx < 0 || length <= idx)
      throw new IndexOutOfBoundsException
    Base.fromInt(groups(idx / N) >> (idx % N * S) & M)
  }

  // Optional re-implementation of foreach, 
  // to make it more efficient.
  override def foreach[U](f: Base => U): Unit = {
    var i = 0
    var b = 0
    while (i < length) {
      b = if (i % N == 0) groups(i / N) else b >>> S
      f(Base.fromInt(b & M))
      i += 1
    }
  }
}


object RNA {

  private val S = 2            // number of bits in group
  private val M = (1 << S) - 1 // bitmask to isolate a group
  private val N = 32 / S       // number of groups in an Int

  def fromSeq(buf: Seq[Base]): RNA = {
    val groups = new Array[Int]((buf.length + N - 1) / N)
    for (i <- 0 until buf.length)
      groups(i / N) |= Base.toInt(buf(i)) << (i % N * S)
    new RNA(groups, buf.length)
  }

  def apply(bases: Base*) = fromSeq(bases)

  def newBuilder: Builder[Base, RNA] = 
    new ArrayBuffer mapResult fromSeq

  implicit def canBuildFrom: CanBuildFrom[RNA, Base, RNA] = 
    new CanBuildFrom[RNA, Base, RNA] {
      def apply(): Builder[Base, RNA] = newBuilder
      def apply(from: RNA): Builder[Base, RNA] = newBuilder
    }
}


import collection._

class PrefixMap[T]
extends mutable.Map[String, T] 
   with mutable.MapLike[String, T, PrefixMap[T]] {

  var suffixes: immutable.Map[Char, PrefixMap[T]] = Map.empty
  var value: Option[T] = None

  def get(s: String): Option[T] =
    if (s.isEmpty) value
    else suffixes get (s(0)) flatMap (_.get(s substring 1))

  def withPrefix(s: String): PrefixMap[T] = 
    if (s.isEmpty) this
    else {
      val leading = s(0)
      suffixes get leading match {
        case None =>
          suffixes = suffixes + (leading -> empty)
        case _ =>
      }
      suffixes(leading) withPrefix (s substring 1)
    }

  override def update(s: String, elem: T) =
    withPrefix(s).value = Some(elem)

  override def remove(s: String): Option[T] =
    if (s.isEmpty) { val prev = value; value = None; prev }
    else suffixes get (s(0)) flatMap (_.remove(s substring 1))

  def iterator: Iterator[(String, T)] =
    (for (v <- value.iterator) yield ("", v)) ++
    (for ((chr, m) <- suffixes.iterator; 
          (s, v) <- m.iterator) yield (chr +: s, v))
    
  def += (kv: (String, T)): this.type = { update(kv._1, kv._2); this }

  def -= (s: String): this.type  = { remove(s); this }

  override def empty = new PrefixMap[T]
}


  scala> val m = PrefixMap("abc" -> 0, "abd" -> 1, "al" -> 2, 
    "all" -> 3, "xy" -> 4)
  m: PrefixMap[Int] = Map((abc,0), (abd,1), (al,2), (all,3),
    (xy,4))


  scala> m withPrefix "a"
  res14: PrefixMap[Int] = Map((bc,0), (bd,1), (l,2), (ll,3))


import scala.collection.mutable.{Builder, MapBuilder}
import scala.collection.generic.CanBuildFrom

object PrefixMap {
  def empty[T] = new PrefixMap[T]

  def apply[T](kvs: (String, T)*): PrefixMap[T] = {
    val m: PrefixMap[T] = empty
    for (kv <- kvs) m += kv
    m
  }

  def newBuilder[T]: Builder[(String, T), PrefixMap[T]] = 
    new MapBuilder[String, T, PrefixMap[T]](empty)

  implicit def canBuildFrom[T]
    : CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] = 
      new CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] {
        def apply(from: PrefixMap[_]) = newBuilder[T]
        def apply() = newBuilder[T]
      }
}


  scala> PrefixMap("hello" -> 5, "hi" -> 2)
  res0: PrefixMap[Int] = Map((hello,5), (hi,2))

  scala> PrefixMap.empty[String]
  res2: PrefixMap[String] = Map()


  scala> res0 map { case (k, v) => (k + "!", "x" * v) }
  res8: PrefixMap[String] = Map((hello!,xxxxx), (hi!,xx))


  

25.4 Conclusion