Extending Scala collections: One based Array index exercise

Question

As an exercise, I'd like to extend the Scala Array collection to my own OneBasedArray (does what you'd expect, indexing starts from 1). Since this is an immutable collection, I'd like to have it return the correct type when calling filter/map etc.

I've read the resources here, here and here, but am struggling to understand how to translate this to Arrays (or collections other than the ones in the examples). Am I on the right track with this sort of structure?

class OneBasedArray[T] 
  extends Array[T] 
  with GenericTraversableTemplate[T, OneBasedArray]
  with ArrayLike[T, OneBasedArray]

Are there any further resources that help explain extending collections?

Answer 1

Array isn't a typical Scala collection... It's simply a Java array that's pimped to look like a collection by way of implicit conversions.

Given the messed-up variance of Java Arrays, you really don't want to be using them without an extremely compelling reason, as they're a source of lurking bugs.

(see here: http://www.infoq.com/presentations/Java-Puzzlers)

Creaking a 1-based collection like this isn't really a good idea either, as you have no way of knowing how many other collection methods rely on the assumption that sequences are 0-based. So to do it safely (if you really must) you'll want add a new method that leaves the default one unchanged:

class OneBasedLookup[T](seq:Seq) {
  def atIdx(i:Int) = seq(i-1)
}

implicit def seqHasOneBasedLookup(seq:Seq) = new OneBasedLookup(seq)

// now use `atIdx` on any sequence.

Even safer still, you can create a Map[Int,T], with the indices being one-based

(Iterator.from(1) zip seq).toMap

This is arguably the most "correct" solution, although it will also carry the highest performance cost.

Answer 2

• For a in depth overview of new collections API: The Scala 2.8 Collections API
• For a nice view of the relation between main classes and traits this

By the way I don't think Array is a collection in Scala.

Answer 3

Here is an example of pimping iterables with a method that always returns the expected runtime type of the iterable it operates on:

import scala.collection.generic.CanBuildFrom

trait MapOrElse[A] {
  val underlying: Iterable[A]

  def mapOrElse[B, To]
      (m: A => Unit)
      (pf: PartialFunction[A,B])
      (implicit cbf: CanBuildFrom[Iterable[A], B, To])
      : To = {

    var builder = cbf(underlying.repr)        

    for (a <- underlying) if (pf.isDefinedAt(a)) builder += pf(a) else m(a)

    builder.result
  }
}

implicit def toMapOrElse[A](it: Iterable[A]): MapOrElse[A] =
  new MapOrElse[A] {val underlying = it}

The new function mapOrElse is similar to the collect function but it allows you to pass a method m: A => Unit in addition to a partial function pf that is invoked whenever pf is undefined. m can for example be a logging method.

Answer 4

An Array is not a Traversable -- trying to work with that as a base class will cause all sorts of problems. Also, it is not immutable either, which makes it completely unsuited to what you want. Finally, Array is an implementation -- try to inherit from traits or abstract classes.

Answer 5

Not an array, but here's a one-based immutable IndexedSeq implementation that I recently put together. I followed the example given here where they implement an RNA class. Between that example, the ScalaDocs, and lots of "helpful" compiler errors, I managed to get it set up correctly. The fact that OneBasedSeq is genericized made it a little more complex than the RNA example. Also, in addition to the traits extended and methods overridden in the example, I had to extend IterableLike and override the iterator method, because various methods call that method behind the scenes, and the default iterator is zero-based.

Please pardon any stylistic or idiomadic oddities; I've been programming in Scala for less than 2 months.

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

// OneBasedSeq class
final class OneBasedSeq[T] private (s: Seq[T]) extends IndexedSeq[T]
  with IterableLike[T, OneBasedSeq[T]] with IndexedSeqLike[T, OneBasedSeq[T]]
{
  private val innerSeq = s.toIndexedSeq

  def apply(idx: Int): T = innerSeq(idx - 1)
  def length: Int = innerSeq.length
  override def iterator: Iterator[T] = new OneBasedSeqIterator(this)
  override def newBuilder: Builder[T, OneBasedSeq[T]] = OneBasedSeq.newBuilder
  override def toString = "OneBasedSeq" + super.toString
}

// OneBasedSeq companion object
object OneBasedSeq {
  private def fromSeq[T](s: Seq[T]) = new OneBasedSeq(s)

  def apply[T](vals: T*) = fromSeq(IndexedSeq(vals: _*))

  def newBuilder[T]: Builder[T, OneBasedSeq[T]] =
    new ArrayBuffer[T].mapResult(OneBasedSeq.fromSeq)

  implicit def canBuildFrom[T, U]: CanBuildFrom[OneBasedSeq[T], U, OneBasedSeq[U]] =
    new CanBuildFrom[OneBasedSeq[T], U, OneBasedSeq[U]] {
      def apply() = newBuilder
      def apply(from: OneBasedSeq[T]): Builder[U, OneBasedSeq[U]] = newBuilder[U]
    }
}

// Iterator class for OneBasedSeq
class OneBasedSeqIterator[T](private val obs: OneBasedSeq[T]) extends Iterator[T]
{
  private var index = 1
  def hasNext: Boolean = index <= obs.length

  def next: T = {
    val ret = obs(index)
    index += 1
    ret
  }
}