## Wednesday, December 12, 2012

I spent quick a bit of time to figure out why something that is usually simple to do in Java did not work in Scala: Arrays and ArrayLists with generics.

For some technical reason (type erasure at the JVM level), Array sometimes need a parameter with a ClassManifest !?! a generic type like [T :< Point : ClassManifest] need to be declared instead of simply [T :< Point].

And then the quickSort method somehow does not work if invoked on a generic... like quickSort(points) where points: Array[T]. I could not figure out yet how to do this one, I just casted to points.asInstanceOf[Array[Point]], quite ugly.

In contrast I did not even have to think much to write the Java equivalent. Generics in Scala, while having a nice syntax, are just crazy. This is something that goes beyond generics. Some of the Scala library and syntax is nice, but overall, the IDE integration is still very buggy, and productivity is not higher.

Update Dec 12 2012: here is the actual code (this is kept close to the Java equivalent on purpose):
object Point {
def sortAndRemoveIdenticalPoints[T <: Point : ClassManifest](points : Array[T]) : Array[T] = {
Sorting.quickSort(points.asInstanceOf[Array[Point]])
val l = new ArrayBuffer[T](points.length)
var previous = points(0)
l += points(0)
for (i <- 1 until points.length) {
if(math.abs(points(i).value - previous.value)< Epsilon.MACHINE_EPSILON_SQRT) {
l += points(i)
}
}
return l.toArray
}
return points
}
}

class Point(val value: Double, val isMiddle: Boolean) extends Ordered[Point] {
def compare(that: Point): Int = {
return math.signum(this.value - that.value).toInt
}
}

In Java one can just use Arrays.sort(points) if points is a T[]. And the method can work with a subclass of Point.

1. Why not use

points.sortBy(identity)

or (for more flexibility or if the type of the Points is not Ordered)

points.sortWith{(a,b) => yourBooleanComparisionHere(a,b)}

These methods work on any Seq.

For arrays, there is also an in-place sort as (Ordered version):

util.Sorting.quickSort(points)

2. You should only need ClassManifest when doing things like the equivalent of new T[length], which you can't do in Java. In particular, scala.util.Sorting.quickSort[K](a: Array[K])(implicit arg0: Ordering[K]) doesn't need it (it sorts an existing array in-place).

3. I have added the actual code. points.sortWith would work, but I would like to just use the default compare method.
points.sortBy has the same issue as Sorting.quickSort(points). I could not find a solution without explicit casting.

4. Ah, I see now. The problem isn't with ClassManifest, but with scala.math.Ordering. You have an Ordering[Point], but you don't have an Ordering[T] (same as in Java, a Comparator<Point> isn't a Comparator<T>). [T : ClassManifest : Ordering] should work. Arrays.sort works because it's willing to blow up at the runtime if elements of the array turn out not to be comparable.

5. Thanks Alexey, T :< Point : ClassManifest : Ordering works.

6. But it does not work if you pass a subclass of Point, which was the point of the declaration in the first place. This is I supposed because the subclass SubPoint is an Ordered[Point] and not Ordered[SubPoint].
Not sure how to make this work.

7. Yes. Instead of extending Ordered[Point], you can provide implicit Ordering of desired type in the companion object:

object Point {
implicit def pointOrdering[T <: Point] = new Ordering[T] {
def compare(t1: T, t2: T) {
return math.signum(t1.value - t2.value).toInt
}
}
}

This should work. There is still a slight problem that a new ordering object will be created for every sort call, and I don't see a way to avoid it without a cast :(