CODEWITHSUNDEEP
algorithmgenericsscala
Maurício Linhares
Maurício Linhares

Reputation: 40333

How can I define a method that takes an Ordered[T] Array in Scala?

I'm building some basic algorithms in Scala (following Cormen's book) to refresh my mind on the subject and I'm building the insertion sort algorithm. Doing it like this, it works correctly:

class InsertionSort extends Sort {

def sort ( items : Array[Int] ) : Unit = {

    if ( items.length < 2 ) {
        throw new IllegalArgumentException( "Array must be bigger than 1" )
    }

    1.until( items.length ).foreach( ( currentIndex ) => {

        val key = items(currentIndex)

        var loopIndex = currentIndex - 1

        while ( loopIndex > -1 && items(loopIndex) > key ) {

            items.update( loopIndex + 1, items(loopIndex) )

            loopIndex -= 1
        }

        items.update( loopIndex + 1, key )

    } )

}

}

But this is for Int only and I would like to use generics and Ordered[A] so I could sort any type that is ordered. When I change the signature to be like this:

def sort( items : Array[Ordered[_]] ) : Unit

The following spec doesn't compile:

"sort correctly with merge sort" in {

  val items = Array[RichInt](5, 2, 4, 6, 1, 3)

  insertionSort.sort( items )

  items.toList === Array[RichInt]( 1, 2, 3, 4, 5, 6 ).toList

}

And the compiler error is:

Type mismatch, expected: Array[Ordered[_]], actual Array[RichInt]

But isn't RichInt an Ordered[RichInt]? How should I define this method signature in a way that it would accept any Ordered object?

EDIT

In case anyone is interested, the final source is available here.

Upvotes: 4

Views: 257

Answers (2)

oxbow_lakes
oxbow_lakes

Reputation: 134330

You can do this with a context bound on the type parameter;

scala> def foo[T : Ordering](arr: Array[T]) = { 
    |    import math.Ordering.Implicits._ 
    |    arr(0) < arr(1) 
    |  }
foo: [T](arr: Array[T])(implicit evidence$1: Ordering[T])Boolean

Such that usage is:

scala> foo(Array(2.3, 3.4))
res1: Boolean = true

The advantage to this is that you don't need the default order of the type if you don't want it:

scala> foo(Array("z", "bc"))
res4: Boolean = false

scala> foo(Array("z", "bc"))(Ordering.by(_.length))
res3: Boolean = true

Upvotes: 6

Eastsun
Eastsun

Reputation: 18869

Actually RichInt is not an Ordered[RichInt] but an Ordered[Int]. However scala.runtime.RichInt <: Ordered[_], but class Array is invariant in type T so Array[RichInt] is not an Array[Ordered[_]].

scala> def f[T <% Ordered[T]](arr: Array[T]) = { arr(0) < arr(1) }
f: [T](arr: Array[T])(implicit evidence$1: T => Ordered[T])Boolean

scala> f(Array(1,2,3))
res2: Boolean = true

scala>

Upvotes: 10

Related Questions