如何定义一个在Scala中使用有序[T]数组的方法？

我正在斯卡拉建立一些基本算法（以下Cormen的书），以更新我对这个主题的想法，并且我正在构建插入排序算法。做这样的，它工作正常：如何定义一个在Scala中使用有序[T]数组的方法？

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) 

    }) 

} 

}

但是，这仅仅是为了诠释，我想用有序[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对象？

编辑

如果有人有兴趣，最后源可用here。

来源

2012-01-06 Maurício Linhares

实际上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>

来源

2012-01-06 04:10:12 Eastsun

是的，就是这样，谢谢！ – 2012-01-06 11:30:00

您可以在类型参数上使用context bound;

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

来源

2012-01-06 08:06:04

如何定义一个在Scala中使用有序[T]数组的方法？

回答

相关问题