Scala :: PriorityQueue => update priority of specific item

Question

I have implemented routine to extract item from head, update it's priority and put it back to the queue with non-blocking approach like this (using 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)
}

Now I need to find out arbitrary Entry in the queue, change it's priority and put it back to the queue. It seems that PriorityQueue doesn't support this, so which class I should use to accomplish desired behavior?

It's related to Change priority of items in a priority queue

Have you tried using a different approach instead: e.g. a `SortedSet` (or `SortedMap`)? — oxbow_lakes, Aug 28 '12 at 10:31
@oxbow_lakes right now I'm trying to implement this with TreeSet — jdevelop, Aug 28 '12 at 10:34

axel22 · Accepted Answer · 2012-08-28T15:03:42.577

Use an immutable tree map (immutable.TreeMap) to accomplish this. You have to find the entry you want somehow - best way to do this is to associate the part of the information (Key) you use to find the entry with a key, and the actual entry that you wish to return with the value in the map (call this Entry).

Rename queueReference with treeReference. In the part of the code where you create the collection, use immutable.TreeMap[Key, Entry](<list of elements>).

Then modify the code like this:

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()
}

If the compareAndSet fails, you have to repeat as you already do in your source. Best to use @tailrec as shown above, to ensure that the function is tail recursive and prevent a potential stack overflow.

Alternatively, you could use an immutable.TreeSet - if you know the exact reference to your Entry object, you can use it to remove the element via - as above and then add it back after calling increase(). The code is almost the same.

Scala :: PriorityQueue => update priority of specific item

1 Answers1