Scala，Collection.searching 具有用户定义的隐式排序[]

Question

我需要对自定义案例数组执行二进制搜索 class。这应该像调用 scala.collection.Searching:

中定义的 search 函数一样简单

如您所见，如果我调用搜索方法的集合是索引序列，则执行二进制搜索。

现在，我需要创建我的自定义 Ordering[B] 参数，我想将它显式传递给 search 函数（我不希望它采用从上下文推断的任何隐式参数).

我有以下代码：

// File 1
case class Person(name: String, id: Int)
object Person{ 
  val orderingById: Ordering[Person] = Ordering.by(e => e.id)
}

// File 2 (same package)
for(i <- orderedId.indices) {
  // orderedId is an array of Int
  // listings is an array of Person
  val listingIndex = listings.search(orderedId(i))(Person.orderingById)
  ...
}

我收到以下错误：

Type mismatch. Required: Ordering[Any], found: Ordering[Nothing]

因此，我尝试以这种方式更改实现：

// file 1
object Person{
  implicit def orderingById[A <: Person] : Ordering[A] = {
      Ordering.by(e => e.id)
  }
}
//file 2 as before

这次出现以下错误：

Type mismatch. Required: Ordering[Any], found: Ordering[Person]

为什么会这样？至少在第二种情况下，它应该从 Any 转换为 Person 吗？

Answer 1

遵循类型规范。

如果你想 .search() 在 Person 元素的集合上，那么第一个 search 参数应该是 Person（或超级 class）。

val listingIndex =
  listings.search(Person("",orderedId(i)))(Person.orderingById)

或者，将其置于更完整和简洁的上下文中：

import scala.collection.Searching.SearchResult

case class Person(name: String, id: Int)

val listings: Array[Person] = ...
val orderedId: Array[Int]   = ...

for(id <- orderedId) {
  val listingIndex: SearchResult =
    listings.search(Person("",id))(Ordering.by(_.id))
}

Answer 2

我将添加一些内容来详细说明您的错误。首先，请注意 Searching.search 已弃用，弃用信息为：

Search methods are defined directly on SeqOps and do not require scala.collection.Searching any more.

search is now defined on IndexedSeqOps。来看看签名：

final def search[B >: A](elem: B)(implicit ord: Ordering[B])

当你打电话时：

listings.search(orderedId(i))(Person.orderingById)

orderedId(i)的结果是Int。因此，上面签名中的B就是Int。 Int的定义是：

final abstract class Int private extends AnyVal

A 是 Person，因为 listing 是 Array[Person] 类型。因此，search 正在寻找 Int 和 Person 的共同根。此公共根是 Any，因此您会收到此错误。克服它的一种方法是定义从 Int 到 Person:

的隐式转换

object Person{
  val orderingById: Ordering[Person] = Ordering.by(e => e.id)

  implicit def apply(id: Int): Person = {
    Person("not defined", id)
  }
}

然后是：

val listings = Array(Person("aa", 1), Person("bb", 2), Person("dd", 4))
val orderedId = 1.to(6).toArray

for(i <- orderedId.indices) {
  // orderedId is an array of Int
  // listings is an array of Person
  listings.search[Person](orderedId(i))(Person.orderingById) match {
    case Found(foundIndex) =>
      println("foundIndex: " + foundIndex)
    case InsertionPoint(insertionPoint) =>
      println("insertionPoint: " + insertionPoint)
  }
}

将产生：

foundIndex: 0
foundIndex: 1
insertionPoint: 2
foundIndex: 2
insertionPoint: 3
insertionPoint: 3

Scastie 中的代码运行。

Scala，Collection.searching 具有用户定义的隐式排序[]

Scala, Collection.searching with user-defined implicit Ordering[]

arrays

scala

sorting

search

implicit