Scala::PriorityQueue => 更新特定项的优先级

Question

我已经实现了从头部提取项目的例程，更新其优先级并使用像这样的非阻塞方法将其放回队列(使用 AtomicReference)

def head(): Entry = {
  def takeAndUpdate(e: Entry, success: Boolean): Entry = {
    if (success) {
      return e
    }
    val oldQueue = queueReference.get()
    val newQueue = oldQueue.clone()
    val item = newQueue.dequeue().increase()
    newQueue += item
    takeAndUpdate(item.e, queueReference.compareAndSet(oldQueue, newQueue))
  }
  takeAndUpdate(null, false)
}

现在我需要找出队列中的任意条目，更改其优先级并将其放回队列。 PriorityQueue 似乎不支持这一点，那么我应该使用哪个类来完成所需的行为？

与 Change priority of items in a priority queue 相关

Answer 1

使用不可变的树形图 ( immutable.TreeMap ) 来完成此操作。您必须以某种方式找到您想要的条目 - 最好的方法是将用于查找条目的信息部分 ( Key ) 与键关联起来，以及您希望返回的实际条目与值在 map 中(将此称为 Entry )。

重命名queueReference与 treeReference 。在创建集合的代码部分中，使用 immutable.TreeMap[Key, Entry](<list of elements>) .

然后修改代码如下:

def updateKey(k: Key) {
  @annotation.tailrec def update(): (Key, Entry) = {
    val oldTree = treeReference.get()
    val entry = oldTree(k)
    val newPair = modifyHoweverYouWish(k, entry)
    val newTree = (oldTree - k) + newPair
    if (treeReference.compareAndSet(oldTree, newTree)) newPair
    else update()
  }
  update()
}

如果compareAndSet失败，您必须像在源代码中所做的那样重复。最好用@tailrec如上所示，确保函数尾递归并防止潜在的堆栈溢出。

或者，您可以使用 immutable.TreeSet - 如果您知道您的 Entry 的确切引用对象，您可以通过 - 使用它来删除元素如上所述，然后在调用 increase() 后添加回来。代码几乎是一样的。