immutable priority queue

[Matthew Pocock]

Hi,

Is there an immutable priority queue? I can't find one and could do with one for a molecular reaction simulator where I need to be able to roll back and fork the simulation and constantly cloning a mutable queue is very expensive.

Thanks,

Matthew

--

Dr Matthew Pocock

Visitor, School of Computing Science, Newcastle University

mailto: turingate...@gmail.com

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

irc.freenode.net: drdozer

tel: (0191) 2566550

mob: +447535664143

[Sciss]

you could use a fingertree

https://github.com/scalaz/scalaz/blob/master/core/src/main/scala/scalaz/FingerTree.scala
https://github.com/Sciss/FingerTree

[Matthew Pocock]

Are there any plans to add immutable.PriorityQueue to the scala collections library?

Matthew

[Donald McLean]

Wouldn't an immutable PriorityQueue be an oxymoron under most
circumstances? The whole point of a priority heap, after all, is
adding elements and then removing them in a defined order.

[Matthew Pocock]

On 21 July 2011 19:52, Donald McLean <dmcl...@gmail.com> wrote:

Wouldn't an immutable PriorityQueue be an oxymoron under most
circumstances?

Not really.

 

The whole point of a priority heap, after all, is
adding elements and then removing them in a defined order.

Yes. I don't see why this implies mutability. The enqueue and dequeue operations would simply return new priority queues. For example, something like:

class PriorityQueue[T] {

  /** Return a new priority queue with an item enqueued into it */

  def enqueue(t: T): PriorityQueue[T] = ...

  /** Return the highest priority element of the priority queue and a new priority queue containing all remaining elements */

  def dequeue: (t, PriorityQueue[T]) = ...

}

Matthew

 

On Thu, Jul 21, 2011 at 2:12 PM, Matthew Pocock
<turingate...@gmail.com> wrote:
> Are there any plans to add immutable.PriorityQueue to the scala collections
> library?

[marc]

Here is a gist I found for immutable priority queues in scala:

https://gist.github.com/757142

I have not used or tested this.

It is based on ideas from the great thesis Purely Functional Data Structures by Okasaki

[Derek Williams]

On Thu, Jul 21, 2011 at 12:52 PM, Donald McLean <dmcl...@gmail.com> wrote:
> Wouldn't an immutable PriorityQueue be an oxymoron under most
> circumstances? The whole point of a priority heap, after all, is
> adding elements and then removing them in a defined order.

We actually almost have an immutable priority queue with SortedSet:

import scala.collection.SortedSet

case class Item(name: String, importance: Int)

var pq = SortedSet.empty[A](Ordering by ((_: Item).importance))

pq += Item("Item 1", 5)
pq += Item("Item 2", 1)
pq += Item("Item 3", 7)
pq += Item("Item 4", 3)

println(pq.last) // prints: Item("Item 3"), 7)
pq = pq.init
println(pq.last) // prints: Item("Item 1"), 5)
pq = pq.init

There are of course issues with using this though since it is a set,
but it does show that it can work.

--
Derek Williams

[Derek Williams]

On Thu, Jul 21, 2011 at 1:21 PM, Derek Williams <de...@nebvin.ca> wrote:
> On Thu, Jul 21, 2011 at 12:52 PM, Donald McLean <dmcl...@gmail.com> wrote:
>> Wouldn't an immutable PriorityQueue be an oxymoron under most
>> circumstances? The whole point of a priority heap, after all, is
>> adding elements and then removing them in a defined order.
>
> We actually almost have an immutable priority queue with SortedSet:
>
> import scala.collection.SortedSet
>
> case class Item(name: String, importance: Int)
>
> var pq = SortedSet.empty[A](Ordering by ((_: Item).importance))

Of course that 'A' should be 'Item'

--
Derek Williams

[Vlad Patryshev]

Not really.

 

The whole point of a priority heap, after all, is
adding elements and then removing them in a defined order.

Yes. I don't see why this implies mutability. The enqueue and dequeue operations would simply return new priority queues.

Which one is mutable then? :) The old one or the new one?

[marc]

All of them are immutable.  The trick is that you return a new object each time, but the old object remains valid and unchanged.  To to

this efficiently, the compiler uses techniques such as structural sharing, etc.  When implementing functional data structures, you have

to be careful with efficiency, but in general through amortization you can achieve similar performance to mutable data structures.

Here is a great talk on Functional Data structures by Daniel Spiewak

http://ontwik.com/scala/extreme-cleverness-functional-data-structures-in-scala/ 

[marc]

Oh wait, was this a joke.  If so, you got me! ;-)

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 22/07/11 04:52, Donald McLean wrote:
> Wouldn't an immutable PriorityQueue be an oxymoron under most
> circumstances? The whole point of a priority heap, after all, is
> adding elements and then removing them in a defined order.

No, I can think of many possible implementations of a pure functional
priority queue. So can Chris Okasaki for that matter -- I recommend
him. Reader's exercise!

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk4olJkACgkQmnpgrYe6r63IDgCdEUIwhSHQ9UO2s0cZFh0nVeQg
R28AoJhxYVKxz2rt4t1GeLQGF6KNfa3q
=iLdh
-----END PGP SIGNATURE-----

[Matthew Pocock]

Hi,

I'm starting yet another project, and yet again it needs an immutable priority queue. Pretty please, can someone chalk this up as a class that needs adding to scala.collections.immutable?

Matthew

[√iktor Ҡlang]

On Thu, Sep 15, 2011 at 2:22 PM, Matthew Pocock <turingate...@gmail.com> wrote:

Hi,

I'm starting yet another project, and yet again it needs an immutable priority queue. Pretty please, can someone chalk this up as a class that needs adding to scala.collections.immutable?

I need a high-performance, threadsafe, mutable non-blocking bi-map.

√
 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

[Daniel D.]

You can use the sorted method of Queue providing an implicit Ordering.




On 15 Sep., 14:22, Matthew Pocock <turingatemyhams...@gmail.com>
wrote:

> Hi,
>
> I'm starting yet another project, and yet again it needs an immutable
> priority queue. Pretty please, can someone chalk this up as a class that
> needs adding to scala.collections.immutable?
>
> Matthew
>

> On 21 July 2011 22:05, Tony Morris <tonymor...@gmail.com> wrote:
>
>
>
>
>
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA1
>
> > On 22/07/11 04:52, Donald McLean wrote:
> > > Wouldn't an immutable PriorityQueue be an oxymoron under most
> > > circumstances? The whole point of a priority heap, after all, is
> > > adding elements and then removing them in a defined order.
>
> > No, I can think of many possible implementations of a pure functional
> > priority queue. So can Chris Okasaki for that matter -- I recommend
> > him. Reader's exercise!
>
> > - --
> > Tony Morris
> >http://tmorris.net/
>
> > -----BEGIN PGP SIGNATURE-----
> > Version: GnuPG v1.4.10 (GNU/Linux)

> > Comment: Using GnuPG with Mozilla -http://enigmail.mozdev.org/

>
> > iEYEARECAAYFAk4olJkACgkQmnpgrYe6r63IDgCdEUIwhSHQ9UO2s0cZFh0nVeQg
> > R28AoJhxYVKxz2rt4t1GeLQGF6KNfa3q
> > =iLdh
> > -----END PGP SIGNATURE-----
>
> --
> Dr Matthew Pocock
> Visitor, School of Computing Science, Newcastle University

> mailto: turingatemyhams...@gmail.com
> gchat: turingatemyhams...@gmail.com
> msn: matthew_poc...@yahoo.co.uk

[Patrick Logan]

Not the most diplomatic response one might hope to see from the company that's trying to get Scala ready for enterprise adoption...

On Thursday, September 15, 2011 6:08:25 AM UTC-7, √iktor Klang wrote:

[Matthew Pocock]

H,

2 months on, and I need an immutable priority queue again. I've dusted off my old special-case code, and it doesn't seem to have grown extra bugs in the mean time. However, could we please have something like this in the standard lib? I can't believe I'm unique in needing this data structure regularly, and I can't face integrating this with the scala collections library. Also, there may be other abstractions (e.g. splitting A up into an explicit element/priority) that make better sense, 

/**

 * A priority queue.

 *

 * Concrete implementations will supply strategies to decompose A into a key and priority. Keys are

 * stored at most once. If an already-present key is inserted, it is stored at the highest of the

 * old and new priority.

 *

 * @tparam A  the element type, encapsulating both the 'key' and 'priority'

 */

trait PriorityQueue[A] {

  def enqueue(a: A): PriorityQueue[A]

  def dequeue: (PriorityQueue[A], A)

  def peek: A

  def size: Int

  def isEmpty: Boolean

}

object PriorityQueue {

  /**

   * An empty priority queue that ranks items in priority order using `ord` and checks if the

   * queue already contains an equivalent key using `equ`. It holds at most one equivalent element,

   * at the highest priority.

   *

   * @tparam A  the element type

   * @param ord the element ordering by priority - items will be nearer the front of the queue if

   *            the priority is higher

   * @param equ the element equivalence - items will appear once in the queue according to their

   *            equivalence

   */

  def apply[A](implicit ord: Ordering[A], equ: Equiv[A]): PriorityQueue[A] = empty

  private def empty[A](implicit ord: Ordering[A], equ: Equiv[A]): PriorityQueue[A] = new PriorityQueue[A] {

    def enqueue(a: A): PriorityQueue[A] = one(a)(ord, equ)

    def dequeue: (PriorityQueue[A], A) = throw new NoSuchElementException("Can not dequeue an empty queue")

    def peek: A = throw new NoSuchElementException("Can not peek an empty queue")

    def size: Int = 0

    def isEmpty: Boolean = true

  }

  private def one[A](a1: A)(ord: Ordering[A], equ: Equiv[A]): PriorityQueue[A] = new PriorityQueue[A] {

    def enqueue(a: A): PriorityQueue[A] = many(List(a1), a)(ord, equ)

    def dequeue: (PriorityQueue[A], A) = (empty(ord, equ), a1)

    def peek: A = a1

    def size: Int = 1

    def isEmpty: Boolean = false

  }

  private class ManyQueue[A](items: List[A])(ord: Ordering[A], equ: Equiv[A]) extends PriorityQueue[A] {

    if(items.isEmpty) throw new IllegalArgumentException("Can't create a ManyQueue from an empty list")

    if(items.lengthCompare(1) == 0) throw new IllegalArgumentException("Can't create a ManyQueue from a list of length 1")

    def enqueue(a: A): PriorityQueue[A] = many(items, a)(ord, equ)

    def dequeue: (PriorityQueue[A], A) = items match {

      case h::t::Nil => (one(t)(ord, equ), h)

      case h::ts => (new ManyQueue(ts)(ord, equ), h)

    }

    val peek: A = items.head

    lazy val size: Int = items.length

    def isEmpty: Boolean = false

  }

  private def many[A](as: List[A], toQueue: A)(ord: Ordering[A], equ: Equiv[A]): PriorityQueue[A] = {

    // brute-force insertion sort and then linear scan for same-key entries

    // this can probably be improved

    def insert(as: List[A]): List[A] = as match {

      case x::xs if(equ.equiv(x, toQueue)) => // we are trying to enqueue an item when it's already queued with a higher priority - do nothing

        as

      case x::xs if(ord.gt(x, toQueue)) => // x is ranked higher than the item we're inserting, so try to enqueue it further down

        x::(insert(xs))

      case x::xs => // insert here, and remove all equivalent items from the tail

        toQueue::x::(xs filterNot (i => equ.equiv(i, toQueue)))

      case Nil => // if empty, insert it

        toQueue::Nil

    }

    insert(as) match {

      case a::Nil => one(a)(ord, equ)

      case newAs => new ManyQueue(newAs)(ord, equ)

    }

  }

}

Matthew

--

Dr Matthew Pocock

Integrative Bioinformatics Group, School of Computing Science, Newcastle University

mailto: turingate...@gmail.com

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

irc.freenode.net: drdozer

skype: matthew.pocock

[Vlad Patryshev]

Hmm, PriorityQueue is basically a trait; and there's a bunch of implementations much more efficient than the one using a single list. You can just look up wikipedia, and see if binary heap, Binary heap may be not a good solution for copy-on-update, but others are pretty efficient, I believe; way more efficient than a single-list-based one.

Thanks,
-Vlad

[Rex Kerr]

2011/9/15 √iktor Ҡlang <viktor...@gmail.com>

On Thu, Sep 15, 2011 at 2:22 PM, Matthew Pocock <turingate...@gmail.com> wrote:

Hi,

I'm starting yet another project, and yet again it needs an immutable priority queue. Pretty please, can someone chalk this up as a class that needs adding to scala.collections.immutable?

I need a high-performance, threadsafe, mutable non-blocking bi-map.

√

Primitive or generic?  Block-on-write, nonblocking-on-read?

  --Rex

[√iktor Ҡlang]

2011/11/28 Rex Kerr <ich...@gmail.com>

Generic. Do you mean RW-lock semantics or do you means that writers block writers but readers never block?
 

  --Rex

[Matthew Pocock]

Yeah, my implementation probably isn't so efficient. That's not really the point. It's just one of the reasons I'd prefer a priority queue to be in the standard lib. Others include having it fit into the collections framework and not having to maintain it myself, and that it is obviously missing.

I did initially try to implement it over SortedSet, but that didn't work so well as I need to be able to enqueue the same item multiple times with independent priorities, and ensure that it it is only ever in the queue at most once, under the highest priority.

Matthew

[Rex Kerr]

2011/11/28 √iktor Ҡlang <viktor...@gmail.com>

2011/11/28 Rex Kerr <ich...@gmail.com>

2011/9/15 √iktor Ҡlang <viktor...@gmail.com>

On Thu, Sep 15, 2011 at 2:22 PM, Matthew Pocock <turingate...@gmail.com> wrote:

Hi,

I'm starting yet another project, and yet again it needs an immutable priority queue. Pretty please, can someone chalk this up as a class that needs adding to scala.collections.immutable?

I need a high-performance, threadsafe, mutable non-blocking bi-map.

√

Primitive or generic?  Block-on-write, nonblocking-on-read?

Generic. Do you mean RW-lock semantics or do you means that writers block writers but readers never block?

Well, I'm almost positive that what I have is so far away that it would be faster to start from scratch; it's primitive only (actually, small integers or mappable-to-small-integers only since it doesn't handle collisions); writers block writers (some of the time) and readers never block, but readers have no guarantee of the bidirectionality of the map: it is possible for them to see that a->b has appeared in the map but b->a has not (yet).

I think you need a tree-based rather than an array-based implementation to get apparently atomic bidirectionality without locking everyone on write.

  --Rex

[√iktor Ҡlang]

2011/11/28 Rex Kerr <ich...@gmail.com>

2011/11/28 √iktor Ҡlang <viktor...@gmail.com>

2011/11/28 Rex Kerr <ich...@gmail.com>

2011/9/15 √iktor Ҡlang <viktor...@gmail.com>

On Thu, Sep 15, 2011 at 2:22 PM, Matthew Pocock <turingate...@gmail.com> wrote:

Hi,

I'm starting yet another project, and yet again it needs an immutable priority queue. Pretty please, can someone chalk this up as a class that needs adding to scala.collections.immutable?

I need a high-performance, threadsafe, mutable non-blocking bi-map.

√

Primitive or generic?  Block-on-write, nonblocking-on-read?

Generic. Do you mean RW-lock semantics or do you means that writers block writers but readers never block?

Well, I'm almost positive that what I have is so far away that it would be faster to start from scratch; it's primitive only (actually, small integers or mappable-to-small-integers only since it doesn't handle collisions); writers block writers (some of the time) and readers never block, but readers have no guarantee of the bidirectionality of the map: it is possible for them to see that a->b has appeared in the map but b->a has not (yet).

So you're keeping 2 mappings per entry?
 

I think you need a tree-based rather than an array-based implementation to get apparently atomic bidirectionality without locking everyone on write.

Yeah, I just have -3467264789234 time to do any researchy stuff right now.

Cheers,
√
 

  --Rex

[Rex Kerr]

2011/11/28 √iktor Ҡlang <viktor...@gmail.com>

2011/11/28 Rex Kerr <ich...@gmail.com>

2011/11/28 √iktor Ҡlang <viktor...@gmail.com>

2011/11/28 Rex Kerr <ich...@gmail.com>

2011/9/15 √iktor Ҡlang <viktor...@gmail.com>

On Thu, Sep 15, 2011 at 2:22 PM, Matthew Pocock <turingate...@gmail.com> wrote:

Hi,

I'm starting yet another project, and yet again it needs an immutable priority queue. Pretty please, can someone chalk this up as a class that needs adding to scala.collections.immutable?

I need a high-performance, threadsafe, mutable non-blocking bi-map.

√

Primitive or generic?  Block-on-write, nonblocking-on-read?

Generic. Do you mean RW-lock semantics or do you means that writers block writers but readers never block?

Well, I'm almost positive that what I have is so far away that it would be faster to start from scratch; it's primitive only (actually, small integers or mappable-to-small-integers only since it doesn't handle collisions); writers block writers (some of the time) and readers never block, but readers have no guarantee of the bidirectionality of the map: it is possible for them to see that a->b has appeared in the map but b->a has not (yet).

So you're keeping 2 mappings per entry?

Of course.  O(1) lookup is very tempting in exchange for less-than-doubling the constant term on write (which is also O(1)).  Classic time/space tradeoff.  (Assuming low write contention.  Having to lock the whole thing or acquire dual locks is a problem in a high-write situation.)
 

 

I think you need a tree-based rather than an array-based implementation to get apparently atomic bidirectionality without locking everyone on write.

Yeah, I just have -3467264789234 time to do any researchy stuff right now.

This is a common problem.

  --Rex

[sreque]

What about the immutable priority queue implemented as part of scalaz?
http://scalaz.github.com/scalaz/scalaz-2.9.1-6.0.2/doc.sxr/scalaz/Heap.scala.html

The header comment describes it as follows:

/** An efficient, asymptotically optimal, implementation of priority
queues
* extended with support for efficient size.
*
* The implementation of 'Heap' is based on bootstrapped skew
binomial heaps
* as described by:
* G. Brodal and C. Okasaki , "Optimal Purely Functional Priority
Queues",
* Journal of Functional Programming 6:839-857 (1996),
*
* Based on the heaps Haskell library by Edward Kmett
*
*/

I saw someone else mentioned Scalaz's finger trees, but not this
PriorityQueue directly, which is not based on finger trees.
On Nov 28, 10:29 am, Matthew Pocock <turingatemyhams...@gmail.com>
wrote:

> Yeah, my implementation probably isn't so efficient. That's not really the
> point. It's just one of the reasons I'd prefer a priority queue to be in
> the standard lib. Others include having it fit into the collections
> framework and not having to maintain it myself, and that it is obviously
> missing.
>
> I did initially try to implement it over SortedSet, but that didn't work so
> well as I need to be able to enqueue the same item multiple times with
> independent priorities, and ensure that it it is only ever in the queue at
> most once, under the highest priority.
>
> Matthew
>

> >>  mailto: turingatemyhams...@gmail.com
> >> gchat: turingatemyhams...@gmail.com
> >> msn: matthew_poc...@yahoo.co.uk

> >> irc.freenode.net: drdozer
> >> skype: matthew.pocock
> >>  tel: (0191) 2566550
> >> mob: +447535664143
>
> --
> Dr Matthew Pocock
> Integrative Bioinformatics Group, School of Computing Science, Newcastle
> University

> mailto: turingatemyhams...@gmail.com
> gchat: turingatemyhams...@gmail.com
> msn: matthew_poc...@yahoo.co.uk

[Matthew Pocock]

Hi,

I've had a try at using this heap implementation, but it has been hard-going - I couldn't find any examples using Google, and there where no use examples in the scaladoc. I'm confused by .insert taking an Order - surely the same ordering must be used throughout the lifetime of the heap, or very bad things will happen? Would it not make more sense for the Order instance to be intimately associated with the heap?

Is there anything out there that shows real-world or tutorial examples?

Matthew

mailto: turingate...@gmail.com

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

[Matthew Pocock]

Also, the scalaz heap doesn't do what I need. If you enque the same item multiple times under multiple priorities, it seems to be present in the queue at each of these priorities, not just the highest priority. This is fatal to my use-case.

Matthew

[Sciss]

but how would you expect a data-structure to find your item when you push it repeatedly with different priorities? that's like complaining that you get multiple entries in a map if you put a value under several keys

val x = "hallo"
var m = Map( 0 -> x )
m += 1 -> x
m // Map(0 -> hallo, 1 -> hallo)

why don't you just remove the item before re-inserting it with other priority?

best, -sciss-

[Matthew Pocock]

On 29 November 2011 15:19, Sciss <con...@sciss.de> wrote:

but how would you expect a data-structure to find your item when you push it repeatedly with different priorities? that's like complaining that you get multiple entries in a map if you put a value under several keys

Take a graph lowest-cost-first search, for example. You want to process each node at the highest priority only. Of course you can check each thing you pull off against a 'seen' set, which works in practice, but this means your queue gets quite a lot bigger - a constant factor memory overhead proportional to the average node connectivity. Perhaps this is a good trade-off against reduced cost of insert and lookup. I guess you'd have to actually profile it to see.

val x = "hallo"
var m = Map( 0 -> x )
m += 1 -> x
m  // Map(0 -> hallo, 1 -> hallo)

why don't you just remove the item before re-inserting it with other priority?

How do you remove it? Does the removal (of the item, remember, not the priority) have linear cost in a heap structured by priority? You can conceptualize a priority queue by analogy to a map either with the priorities as keys or values. Since it's common for multiple items to share the same priority, I tend to prefer viewing them as values. However, all analogies break down, and a priority queue isn't in reality a map.

Matthew

[Sciss]

for example SortedMap has logarithmic costs for `+`, `-`, and `head` (better verify that this is true for `last`, too). (do you need constant `head`?)

import collection.immutable.SortedMap

type Prio[ A, B ] = (SortedMap[ A, B ], Map[ B, A ])

object Prio {
def empty[ A : Ordering, B ] : Prio[ A, B ] = (SortedMap.empty, Map.empty)
}

implicit def prioOps[ A, B ]( tup: Prio[ A, B ]) = new PrioOps( tup )

final class PrioOps[ A, B ]( peer: Prio[ A, B ]) {
type Pr = Prio[ A, B ]

def +( entry: (A, B) ) : Pr = {
(peer._2.get( entry._2 ).map( peer._1 - _ ).getOrElse( peer._1 ) + entry,
peer._2 + entry.swap)
}

def pop : (B, Pr) = {
val (k, v) = peer._1.last
(v, (peer._1 - k, peer._2 - v))
}
}

// test

var prio = Prio.empty[ Int, String ]
prio += 1 -> "hallo"
prio += 2 -> "welt"
prio += 3 -> "hallo"

val (max, prio1) = prio.pop

of course, if you require that several items can have the same priority, you would need to massage this a bit, like use SortedMap[ A, Set[ B]] instead.

best, -sciss-

[sreque]

I could be wrong, but I don't think any normal priority queue can do
what you want it to. Just as with balanced binary trees, heaps use the
priority of an object to figure out where to place it sub-linear time.
If two objects are the same, then they must yield the same priority,
or else there is no way to guarantee that when inserting one object
you encounter the other one along the insertion path. The same idea is
behind the requirement that equal objects must generate the same hash
code.

If you look at the definition of a method in the scalaz Heap that
deletes all duplicate values, you'll notice that it expects equal
objects to be right next to each other in the heap, or, in other
words, to have the same priority.

def nub: Heap[A] = fold(Empty[A], (_, leq, t) => {
val x = t.rootLabel.value
val xs = deleteMin
val zs = xs.dropWhile(leq(_, x))
zs.nub.insertWith(leq, x)
})

Another thing to note about priority queues is that the they are
usually designed to be efficient at insertion and at removal of the
top value (top based on priority). On the other hand, they usually
don't support efficient removal of arbitrary elements, which would
make them infeasible to meet your need of deleting duplicate objects
with differing priorities on insertion.

It sounds like you need another data structure!

On Nov 29, 6:54 am, Matthew Pocock <turingatemyhams...@gmail.com>
wrote:

> Also, the scalaz heap doesn't do what I need. If you enque the same item
> multiple times under multiple priorities, it seems to be present in the
> queue at each of these priorities, not just the highest priority. This is
> fatal to my use-case.
>
> Matthew
>

> On 29 November 2011 12:50, Matthew Pocock <turingatemyhams...@gmail.com>wrote:
>
>
>
>
>
>
>
>
>
> > Hi,
>
> > I've had a try at using this heap implementation, but it has been
> > hard-going - I couldn't find any examples using Google, and there where no
> > use examples in the scaladoc. I'm confused by .insert taking an Order -
> > surely the same ordering must be used throughout the lifetime of the heap,
> > or very bad things will happen? Would it not make more sense for the Order
> > instance to be intimately associated with the heap?
>
> > Is there anything out there that shows real-world or tutorial examples?
>
> > Matthew
>

> > On 29 November 2011 05:20, sreque <seanre...@yahoo.com> wrote:
>
> >> What about the immutable priority queue implemented as part of scalaz?
>

> >>http://scalaz.github.com/scalaz/scalaz-2.9.1-6.0.2/doc.sxr/scalaz/Hea...

[Nicholas Sterling]

I want to expand on Derek's last point about there being issues since this is a set, because we tried using a SortedSet as an immutable PriorityQueue and those issues bit us.  The issues are more severe than you might think.

Try executing Derek's snippet (you'll need to replace A with Item, or say "type A = Item" at some point) and then adding

pq += Item("Item 5", 3)

pq += Item("Item 6", 7)

Then display pq.  You'll see that items 3 and 4 are no longer in the set, having been replaced by 6 and 5.  The problem is that the Ordering's compare method is being used to determine whether or not the Item is already in the set (rather than equals()), so the set will only keep one Item of each importance.

Nicholas