Return to chapter index

25 The Architecture of Scala Collections

Sample run of chapter's interpreter examples

• 25.1 Factoring out common operations
• 25.2 Integrating new collections
• 25.3 Conclusion

25.1 Factoring out common operations

trait List[A] {
  def map[B](f: A => B): List[B]
}

trait Vector[A] {
  def map[B](f: A => B): Vector[B]
}


trait List[A] {
  def filter(p: A => Boolean): List[A]
}

trait Map[K, V] {
  def filter(p: ((K, V)) => Boolean): Map[K, V]
}


trait IterableOps[+A, +CC[_], +C]


trait IterableOps[+A, +CC[_], +C] {
  def filter(p: A => Boolean): C
  def map[B](f: A => B): CC[B]
}


trait List[+A]
  extends Iterable[A]
    with IterableOps[A, List, List[A]]


trait SetOps[A, +CC[_], +C]
    extends IterableOps[A, CC, C]


trait Set[A] extends Iterable[A] with SetOps[A, Set, Set[A]]


trait MapOps[K, +V, +CC[_, _], +C]
  extends IterableOps[(K, V), Iterable, C] {

  def map[K2, V2](f: ((K, V)) => (K2, V2)): CC[K2, V2]
}


// Inherited from MapOps
def map[K2, V2](f: ((K, V)) => (K2, V2)): Map[K2, V2]

// Inherited from IterableOps
def map[B](f: ((K, V)) => B): Iterable[B]


def map[B](f: A => B)
      (implicit ord: Ordering[B]): SortedSet[B]


trait SortedSetOps[A, +CC[_], +C]
    extends SetOps[A, Set, C] {

  def map[B](f: A => B)(implicit ord: Ordering[B]): CC[B]
}


trait SortedSet[A] extends
    SortedSetOps[A, SortedSet, SortedSet[A]]


// Inherited from SortedSetOps
def map[B](f: A => B)(implicit ord: Ordering[B]): SortedSet[B]

// Inherited from IterableOps, by way of SetOps
def map[B](f: A => B): Set[B]


trait View[+A]
  extends Iterable[A]
    with IterableOps[A, View, View[A]] {
  def iterator: Iterator[A]
}


trait IterableOps[+A, +CC[_], +C] {

  def filter(pred: A => Boolean): C =
    fromSpecific(new View.Filter(this, pred))

  def map[B](f: A => B): CC[B] = 
    from(new View.Map(this, f))

  protected def fromSpecific(source: IterableOnce[A]): C
  protected def from[E](source: IterableOnce[E]): CC[E]
}


def from[E](source: IterableOnce[E]): List[E] = 
  (new ListBuffer[E] ++= source).toList


trait IterableOps[+A, +CC[_], +C] {

  def map[B](f: A => B): CC[B] =
    iterableFactory.from(new View.Map(this, f))

  def iterableFactory: IterableFactory[CC]
}

trait IterableFactory[+CC[_]] {

  def from[A](source: IterableOnce[A]): CC[A]
}


trait MapOps[K, +V, +CC[_, _], +C]
  extends IterableOps[(K, V), Iterable, C] {

  def map[K2, V2](f: ((K, V)) => (K2, V2)): CC[K2, V2] =
    mapFactory.from(new View.Map(this, f))

  def mapFactory: MapFactory[CC]

}

trait MapFactory[+CC[_, _]] {
  def from[K, V](source: IterableOnce[(K, V)]): CC[K, V]
}


package scala.collection.mutable

trait Builder[-A, +C] {

  def addOne(elem: A): this.type

  def result(): C

  def clear(): Unit
}


trait IterableOps[+A, +CC[_], +C] {

  def iterableFactory: IterableFactory[CC]

  protected def fromSpecific(source: IterableOnce[A]): C

  protected def newSpecificBuilder: Builder[A, C]
}

trait IterableFactory[+CC[_]] {

  def from[A](source: IterableOnce[A]): CC[A]

  def newBuilder[A]: Builder[A, CC[A]]
}


  

25.2 Integrating new collections

(xs ++ ys).size == xs.size + ys.size


import scala.collection._

class Capped1[A] private (val capacity: Int, val length: Int,
    offset: Int, elems: Array[Any])
      extends immutable.Iterable[A] { self =>

  def this(capacity: Int) = this(capacity, length = 0,
    offset = 0, elems = Array.ofDim(capacity))

  def appended[B >: A](elem: B): Capped1[B] = {
    val newElems = Array.ofDim[Any](capacity)
    Array.copy(elems, 0, newElems, 0, capacity)
    val (newOffset, newLength) =
      if (length == capacity) {
        newElems(offset) = elem
        ((offset + 1) % capacity, length)
      } else {
        newElems(length) = elem
        (offset, length + 1)
      }
    new Capped1[B](capacity, newLength, newOffset, newElems)
  }

  @inline def :+ [B >: A](elem: B): Capped1[B] = appended(elem)

  def apply(i: Int): A =
    elems((i + offset) % capacity).asInstanceOf[A]

  def iterator: Iterator[A] = new AbstractIterator[A] {
    private var current = 0
    def hasNext = current < self.length
    def next(): A = {
      val elem = self(current)
      current += 1
      elem
    }
  }

  override def className = "Capped1"
}


scala> new Capped1(capacity = 4)
 res0: Capped1[Nothing] = Capped1()

scala> res0 :+ 1 :+ 2 :+ 3
 res1: Capped1[Int] = Capped1(1, 2, 3)

scala> res1.length
 res2: Int = 3

scala> res1.lastOption
 res3: Option[Int] = Some(3)

scala> res1 :+ 4 :+ 5 :+ 6
 res4: Capped1[Int] = Capped1(3, 4, 5, 6)

scala> res4.take(3)
 res5: collection.immutable.Iterable[Int] = List(3, 4, 5)


override def take(count: Int): Capped1 = ...


import scala.collection._

class Capped2[A] private (val capacity: Int, val length: Int,
    offset: Int, elems: Array[Any])
    extends immutable.Iterable[A]
    with IterableOps[A, Capped2, Capped2[A]] { self =>

  def this(capacity: Int) = // as before
  def appended[B >: A](elem: B): Capped2[B] = // as before
  @inline def :+ [B >: A](elem: B): Capped2[B] = // as before
  def apply(i: Int): A = // as before
  def iterator: Iterator[A] = // as before

  override def className = "Capped2"

  override val iterableFactory: IterableFactory[Capped2] =
    new Capped2Factory(capacity)

  override protected def fromSpecific(
      coll: IterableOnce[A]): Capped2[A] =
    iterableFactory.from(coll)

  override protected def newSpecificBuilder:
      mutable.Builder[A, Capped2[A]] =
    iterableFactory.newBuilder

  override def empty: Capped2[A] = iterableFactory.empty
}

class Capped2Factory(capacity: Int) extends
    IterableFactory[Capped2] {

  def from[A](source: IterableOnce[A]): Capped2[A] =
    (newBuilder[A] ++= source).result()

  def empty[A]: Capped2[A] = new Capped2[A](capacity)

  def newBuilder[A]: mutable.Builder[A, Capped2[A]] =
    new mutable.ImmutableBuilder[A, Capped2[A]](empty) {
      def addOne(elem: A): this.type = {
        elems = elems :+ elem
        this
      }
    }
}


scala> object Capped extends Capped2Factory(capacity = 4)
 defined object Capped

scala> Capped(1, 2, 3)
 res0: Capped2[Int] = Capped2(1, 2, 3)

scala> res0.take(2)
 res1: Capped2[Int] = Capped2(1, 2)

scala> res0.filter(x => x % 2 == 1)
 res2: Capped2[Int] = Capped2(1, 3)

scala> res0.map(x => x * x)
 res3: Capped2[Int] = Capped2(1, 4, 9)

scala> List(1, 2, 3, 4, 5).to(Capped)
 res4: Capped2[Int] = Capped2(2, 3, 4, 5)


import scala.collection._

final class Capped[A] private (val capacity: Int, val length: Int,
    offset: Int, elems: Array[Any])
    extends immutable.Iterable[A]
    with IterableOps[A, Capped, Capped[A]]
    with StrictOptimizedIterableOps[A, Capped, Capped[A]] { self =>

  def this(capacity: Int) = this(capacity, length = 0,
    offset = 0, elems = Array.ofDim(capacity))

  def appended[B >: A](elem: B): Capped[B] = {
    val newElems = Array.ofDim[Any](capacity)
    Array.copy(elems, 0, newElems, 0, capacity)
    val (newOffset, newLength) =
      if (length == capacity) {
        newElems(offset) = elem
        ((offset + 1) % capacity, length)
      } else {
        newElems(length) = elem
        (offset, length + 1)
      }
    new Capped[B](capacity, newLength, newOffset, newElems)
  }

  @inline def :+ [B >: A](elem: B): Capped[B] = appended(elem)

  def apply(i: Int): A =
    elems((i + offset) % capacity).asInstanceOf[A]

  // continued in Listing 25.8...


  // ...continued from Listing 25.7
  def iterator: Iterator[A] = view.iterator

  override def view: IndexedSeqView[A] = new IndexedSeqView[A] {
    def length: Int = self.length
    def apply(i: Int): A = self(i)
  }

  override def knownSize: Int = length

  override def className = "Capped"

  override val iterableFactory: IterableFactory[Capped] =
    new CappedFactory(capacity)

  override protected def fromSpecific(coll: IterableOnce[A]):
      Capped[A] = iterableFactory.from(coll)

  override protected def newSpecificBuilder:
      mutable.Builder[A, Capped[A]] =
    iterableFactory.newBuilder

  override def empty: Capped[A] = iterableFactory.empty
}

class CappedFactory(capacity: Int) extends IterableFactory[Capped] {

  def from[A](source: IterableOnce[A]): Capped[A] =
    source match {
      case capped: Capped[A] if capped.capacity == capacity => capped
      case _ => (newBuilder[A] ++= source).result()
    }

  def empty[A]: Capped[A] = new Capped[A](capacity)

  def newBuilder[A]: mutable.Builder[A, Capped[A]] =
    new mutable.ImmutableBuilder[A, Capped[A]](empty) {
      def addOne(elem: A): this.type = {
        elems = elems :+ elem
        this
      }
    }
}


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

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


import collection.mutable
import collection.immutable.{IndexedSeq, IndexedSeqOps}

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

  import RNA1._

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

  override def className = "RNA1"
  override protected def fromSpecific(
      source: IterableOnce[Base]): RNA1 =
    fromSeq(source.iterator.toSeq)
  override protected def newSpecificBuilder:
      mutable.Builder[Base, RNA1] =
    iterableFactory.newBuilder[Base].mapResult(fromSeq)
  override def empty: RNA1 = fromSeq(Seq.empty)
}

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: collection.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> RNA1.fromSeq(List(A, G, U, A))
  res1: RNA1 = RNA1(A, G, U, A)

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


  scala> rna1.take(3)
  res2: RNA1 = RNA1(A, U, G)

  scala> rna1.filter(_ != U)
  res3: RNA1 = RNA1(A, G, G, C)


  scala> rna1.map(base => base)
  res7: IndexedSeq[Base] = Vector(A, U, G, G, C)

  scala> rna1 ++ rna1
  res8: IndexedSeq[Base] = Vector(A, U, G, G, C, A, U, G, G, C)


def map[B](f: A => B): CC[B]


import scala.collection.{View, mutable}
import scala.collection.immutable.{IndexedSeq, IndexedSeqOps}

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

  import RNA2._

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

  override def className = "RNA2"

  override protected def fromSpecific(
    source: IterableOnce[Base]): RNA2 = // as before

  override protected def newSpecificBuilder:
    mutable.Builder[Base, RNA2] = // as before

  override def empty: RNA2 = // as before

  // Overload methods to return RNA2
  def appended(base: Base): RNA2 = fromSpecific(
    new View.Append(this, base))

  def appendedAll(suffix: IterableOnce[Base]): RNA2 =
    concat(suffix)

  def concat(suffix: IterableOnce[Base]): RNA2 =
    fromSpecific(this.iterator ++ suffix.iterator)

  def flatMap(f: Base => IterableOnce[Base]): RNA2 =
    fromSpecific(new View.FlatMap(this, f))

  def map(f: Base => Base): RNA2 =
    fromSpecific(new View.Map(this, f))

  def prepended(base: Base): RNA2 = fromSpecific(
    new View.Prepend(base, this))

  def prependedAll(prefix: IterableOnce[Base]): RNA2 =
    fromSpecific(prefix.iterator ++ this.iterator)

  // symbolic alias for `concat`
  @inline final def ++ (suffix: IterableOnce[Base]): RNA2 =
    concat(suffix)
}


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

  scala> rna1.map(base => base)
  res2: RNA2 = RNA2(A, U, G, G, C)

  scala> rna1 ++ rna1
  res3: RNA2 = RNA2(A, U, G, G, C, A, U, G, G, C)


  scala> val bases: Iterable[Base] = List(A, U, C, C)
  bases: Iterable[Base] = List(A, U, C, C)

  scala> bases.to(RNA2)
                  ^
       error: type mismatch;
        found   : RNA2.type
        required: scala.collection.Factory[Base,?]


import scala.collection.{AbstractIterator,
  SpecificIterableFactory, StrictOptimizedSeqOps,
  View, mutable}
import scala.collection.immutable.{IndexedSeq, IndexedSeqOps}

final class RNA private (val groups: Array[Int],
    val length: Int) extends IndexedSeq[Base]
    with IndexedSeqOps[Base, IndexedSeq, RNA]
    with StrictOptimizedSeqOps[Base, IndexedSeq, RNA] { rna =>

  import RNA._

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

  override def className = "RNA"

  override protected def fromSpecific(
      source: IterableOnce[Base]): RNA =
    RNA.fromSpecific(source)

  override protected def newSpecificBuilder:
      mutable.Builder[Base, RNA] =
    RNA.newBuilder

  override def empty: RNA = RNA.empty

  // Overload methods to return RNA
  def appended(base: Base): RNA =
    (newSpecificBuilder ++= this += base).result()

  def appendedAll(suffix: IterableOnce[Base]): RNA =
    strictOptimizedConcat(suffix, newSpecificBuilder)

  def concat(suffix: IterableOnce[Base]): RNA =
    strictOptimizedConcat(suffix, newSpecificBuilder)

  def flatMap(f: Base => IterableOnce[Base]): RNA =
    strictOptimizedFlatMap(newSpecificBuilder, f)

  // continued in Listing 25.13...


  // ...continued from Listing 25.12
  def map(f: Base => Base): RNA =
    strictOptimizedMap(newSpecificBuilder, f)

  def prepended(base: Base): RNA =
    (newSpecificBuilder += base ++= this).result()

  def prependedAll(prefix: Iterable[Base]): RNA =
    (newSpecificBuilder ++= prefix ++= this).result()

  @inline final def ++ (suffix: IterableOnce[Base]): RNA =
    concat(suffix)

  // Optional re-implementation of iterator,
  // to make it more efficient.
  override def iterator: Iterator[Base] =
    new AbstractIterator[Base] {
      private var i = 0
      private var b = 0
      def hasNext: Boolean = i < rna.length
      def next(): Base = {
        b = if (i % N == 0) groups(i / N) else b >>> S
        i += 1
        Base.fromInt(b & M)
      }
    }
}

object RNA extends SpecificIterableFactory[Base, 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: collection.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)
  }

  // continued in Listing 25.14...


  // ...continued from Listing 25.13

  // Implement factory methods required by
  // SpecificIterableFactory
  def empty: RNA = fromSeq(Seq.empty)

  def newBuilder: mutable.Builder[Base, RNA] =
    mutable.ArrayBuffer.newBuilder[Base].mapResult(fromSeq)

  def fromSpecific(it: IterableOnce[Base]): RNA = it match {
    case seq: collection.Seq[Base] => fromSeq(seq)
    case _ => fromSeq(mutable.ArrayBuffer.from(it))
  }
}


  scala> List(U, A, G, C).to(RNA)
  res0: RNA(U, A, G, C)


import scala.collection._

class PrefixMap[A] extends mutable.Map[String, A]
    with mutable.MapOps[String, A, mutable.Map, PrefixMap[A]]
    with StrictOptimizedIterableOps
    [(String, A), mutable.Iterable, PrefixMap[A]] {

  private var suffixes: immutable.Map[Char, PrefixMap[A]] =
    immutable.Map.empty

  private var value: Option[A] = None

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

  def addOne(kv: (String, A)): this.type = {
    withPrefix(kv._1).value = Some(kv._2)
    this
  }

  def subtractOne(s: String): this.type  = {
    if (s.isEmpty) { val prev = value; value = None; prev }
    else suffixes get (s(0)) flatMap (_.remove(s substring 1))
    this
  }

  def withPrefix(s: String): PrefixMap[A] =
    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)
    }

  // continued in Listing 25.16...


  // ...continued from Listing 25.15

  def iterator: Iterator[(String, A)] =
    (for (v <- value.iterator) yield ("", v)) ++
      (for ((chr, m) <- suffixes.iterator;
            (s, v) <- m.iterator) yield (chr +: s, v))

  override def className = "PrefixMap"

  // Overload methods to return PrefixMap
  def map[B](f: ((String, A)) => (String, B)): PrefixMap[B] =
    strictOptimizedMap(PrefixMap.newBuilder[B], f)

  def flatMap[B](f: ((String, A)) =>
      IterableOnce[(String, B)]): PrefixMap[B] =
    strictOptimizedFlatMap(PrefixMap.newBuilder[B], f)

  // Override concat to refine its return type
  override def concat[B >: A](suffix:
      Iterable[(String, B)]): PrefixMap[B] =
    strictOptimizedConcat(suffix, PrefixMap.newBuilder[B])

  // Members declared in scala.collection.mutable.Clearable
  def clear(): Unit = suffixes = immutable.Map.empty

  // Members declared in scala.collection.IterableOps
  override protected def fromSpecific(
      source: IterableOnce[(String, A)]): PrefixMap[A] =
    PrefixMap.from(coll)

  override protected def newSpecificBuilder:
      mutable.Builder[(String, A), PrefixMap[A]] =
    PrefixMap.newBuilder

  override def empty: PrefixMap[A] = new PrefixMap
}


  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._
import scala.language.implicitConversions

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

  def from[A](source: IterableOnce[(String, A)]): PrefixMap[A] =
    source match {
      case pm: PrefixMap[A] => pm
      case _ => (newBuilder[A] ++= source).result()
    }

  def apply[A](kvs: (String, A)*): PrefixMap[A] = from(kvs)

  def newBuilder[A]: mutable.Builder[(String, A), PrefixMap[A]] =
    new mutable.GrowableBuilder[(String, A), PrefixMap[A]](empty)

  implicit def toFactory[A](
      self: this.type): Factory[(String, A), PrefixMap[A]] =
    new Factory[(String, A), PrefixMap[A]] {
      def fromSpecific(source:
        IterableOnce[(String, A)]): PrefixMap[A] =
        self.from(source)
      def newBuilder: mutable.Builder[(String, A), PrefixMap[A]] =
        self.newBuilder
    }
}


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

scala> res0 += "foo" -> 3
 res1: res0.type = PrefixMap(hello -> 5, hi -> 2, foo -> 3)


  

25.3 Conclusion