How can I define a method that takes an ordered array [T] in Scala?

Question

I am creating some basic algorithms in Scala (following Cormen's book) to refresh my thoughts on this, and I am creating a sort insertion algorithm. By doing 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 only for Int , and I would like to use generics and Ordered [A] so that I can sort any ordered type. When I change the signature like this:

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

The following specification does not 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:

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

But not RichInt ordered [RichInt]? How to define this method signature so that it accepts any Ordered object?

EDIT

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

Answer 1

In fact, RichInt not Ordered[RichInt] , but << 22>. However, scala.runtime.RichInt <: Ordered[_] , but the Array class is invariant by type T , so Array[RichInt] not 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> 

Answer 2

You can do this with context binding to a 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 use:

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

The advantage of this is that you don't need the default order for 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