Code Examples for

Programming in Scala, Second Edition

Return to chapter index

25 The Architecture of Scala Collections

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

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

    25.1 Builders


    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()
    package scala.collection class 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 } }

    25.2 Factoring out common operations


    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](p: Elem => B) (implicit bf: CanBuildFrom[B, That, This]): 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)
    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) }

    25.3 Integrating new collections


    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)
    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 }
    def take(count: Int): RNA1 = RNA1.fromSeq(super.take(count))
    \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: A => 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 extends { 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

    For more information about Programming in Scala, Second Edition (the "Stairway Book"), please visit:

    http://www.artima.com/shop/programming_in_scala_2ed

    and:

    http://booksites.artima.com/programming_in_scala_2ed

    Copyright © 2007-2010 Artima, Inc. All rights reserved.

    Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.