scala - 索引集合上的二分搜索(已排序的索引序列)

Question

我有一个 索引 某种类型的集合(必须编入索引)A :

var coll: IndexedSeq[A]

我想保留 coll按部分排序 Ordering[A]但我经常在其中添加/删除项目。这样做的明显机制是这样的:

def binarySearch[A : Ordering](a: IndexedSeq[A], elem: A): Int
def add(a: A) {
  val idx = binarySearch(coll, a)
  coll = (coll take idx) :+ a +: (coll drop idx)
}

但是没有 binarySearch在标准库中(奇怪的是，看到有 scala.util.Sorting.quickSort )并且我找不到既索引又排序的数据类型(我猜这是一个低效的结构)。

Answer 1

我想 slice在 TreeSet相当有效(并且您可以将它与一个元素范围一起使用)，但是您是对的——奇怪的是没有索引排序的数据结构。而且它足够高效；如果跟踪 child 的数量，大多数任何排序的树都可以这样使用。我认为这只是一个疏忽，它丢失了。

如果你用一个只允许引用相等的标签包装它们，你总是可以为重复元素使用一个集合，并且你可以确保它们是有序的:

class Tag[A](val value: A)(implicit ord: Ordering[A]) extends Ordered[Tag[A]] {
  def compare(ta: Tag[A]) = {
    val c = ord.compare(value,ta.value)
    if (c != 0) c
    else if (this eq ta) 0
    else System.identityHashCode(this) compare System.identityHashCode(ta)
  }
  override def toString = value.toString+"'"
  override def hashCode = value.hashCode
  override def equals(a: Any) = a.asInstanceOf[AnyRef] eq this
}

scala> collection.immutable.TreeSet[Tag[Int]]() ++ List(1,2,3,2,1).map(i => new Tag(i))
res1: scala.collection.immutable.TreeSet[Tag[Int]] = TreeSet(1', 1', 2', 2', 3')

scala> res1.slice(2,3).head
res2: Tag[Int] = 2'

然而，这确实为相对简单的任务增加了很多开销。