如何定义在Scala中采用Ordered [T]数组的方法？

Question

我正在Scala中构建一些基本算法(遵循Cormen的书),以便在主题上刷新我的想法,并且我正在构建插入排序算法.像这样做,它正常工作:

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 )

    } )

}

}    

但这仅适用于Int,我想使用泛型和Ordered [A],所以我可以对任何有序的类型进行排序.当我将签名更改为如下:

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

以下规范不编译:

"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

}

并且编译器错误是:

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

但是RichInt是不是有序[RichInt]？我应该如何以接受任何Ordered对象的方式定义此方法签名？

编辑

如果有人感兴趣,可在此处获得最终来源.

Answer 1

实际上RichInt不是一个Ordered[RichInt]而是一个Ordered[Int].但是scala.runtime.RichInt <: Ordered[_],类Array在类型中是不变的,T所以Array[RichInt]不是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

您可以使用type参数绑定上下文来执行此操作;

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

这种用法是:

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

这样做的好处是,如果您不需要,则不需要该类型的默认顺序:

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

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