immutable priority queue

you could use a fingertree

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

On 20 Jul 2011, at 14:28, Matthew Pocock wrote:

> 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
>

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

On 20 July 2011 14:31, Sciss <contact@sciss.de> wrote:

you could use a fingertree

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

On 20 Jul 2011, at 14:28, Matthew Pocock wrote:

> 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: turingatemyhamster@gmail.com
> gchat: turingatemyhamster@gmail.com
> msn: matthew_pocock@yahoo.co.uk
> irc.freenode.net: drdozer
> tel: (0191) 2566550
> mob: +447535664143
>

--
Dr Matthew PocockVisitor, School of Computing Science, Newcastle Universitymailto: turingatemyhamster@gmail.com gchat: turingatemyhamster@gmail.commsn: matthew_pocock@yahoo.co.uk irc.freenode.net: drdozertel: (0191) 2566550mob: +447535664143

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.

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

On 21 July 2011 19:52, Donald McLean <dmclean62@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
<turingatemyhamster@gmail.com> wrote:
> Are there any plans to add immutable.PriorityQueue to the scala collections
> library?

--
Dr Matthew PocockVisitor, School of Computing Science, Newcastle Universitymailto: turingatemyhamster@gmail.com gchat: turingatemyhamster@gmail.commsn: matthew_pocock@yahoo.co.uk irc.freenode.net: drdozertel: (0191) 2566550mob: +447535664143

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

On Thu, Jul 21, 2011 at 12:52 PM, 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.

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.

On Thu, Jul 21, 2011 at 1:21 PM, Derek Williams wrote:
> On Thu, Jul 21, 2011 at 12:52 PM, 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.
>
> 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'

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?

On Thursday, July 21, 2011 1:11:11 PM UTC-7, Vlad Patryshev wrote:

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?

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 tothis efficiently, the compiler uses techniques such as structural sharing, etc.  When implementing functional data structures, you haveto 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 Spiewakhttp://ontwik.com/scala/extreme-cleverness-functional-data-structures-in-scala/ 

-----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!

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 <tonymorris@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 PocockVisitor, School of Computing Science, Newcastle Universitymailto: turingatemyhamster@gmail.com gchat: turingatemyhamster@gmail.commsn: matthew_pocock@yahoo.co.uk irc.freenode.net: drdozertel: (0191) 2566550mob: +447535664143

On Thu, Sep 15, 2011 at 2:22 PM, Matthew Pocock <turingatemyhamster@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.

√
 

Matthew

On 21 July 2011 22:05, Tony Morris <tonymorris@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 PocockVisitor, School of Computing Science, Newcastle Universitymailto: turingatemyhamster@gmail.com gchat: turingatemyhamster@gmail.commsn: matthew_pocock@yahoo.co.uk irc.freenode.net: drdozertel: (0191) 2566550mob: +447535664143

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

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

On 15 Sep., 14:22, Matthew Pocock
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 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
> irc.freenode.net: drdozer
> tel: (0191) 2566550
> mob: +447535664143

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:

On Thu, Sryiep 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.

√
 

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 PocockIntegrative Bioinformatics Group, School of Computing Science, Newcastle University mailto: turingatemyhamster@gmail.comgchat: turingatemyhamster@gmail.com msn: matthew_pocock@yahoo.co.ukirc.freenode.net: drdozerskype: matthew.pocock tel: (0191) 2566550mob: +447535664143

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
 

On Mon, Nov 28, 2011 at 4:59 AM, Matthew Pocock <turingatemyhamster@gmail.com> wrote:

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 PocockIntegrative Bioinformatics Group, School of Computing Science, Newcastle University mailto: turingatemyhamster@gmail.comgchat: turingatemyhamster@gmail.com msn: matthew_pocock@yahoo.co.ukirc.freenode.net: drdozerskype: matthew.pocock tel: (0191) 2566550mob: +447535664143

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

On Thu, Sep 15, 2011 at 2:22 PM, Matthew Pocock <turingatemyhamster@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

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

On 28 November 2011 16:05, Vlad Patryshev <vpatryshev@gmail.com> wrote:

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
 

On Mon, Nov 28, 2011 at 4:59 AM, Matthew Pocock <turingatemyhamster@gmail.com> wrote:

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 PocockIntegrative Bioinformatics Group, School of Computing Science, Newcastle University mailto: turingatemyhamster@gmail.comgchat: turingatemyhamster@gmail.com msn: matthew_pocock@yahoo.co.ukirc.freenode.net: drdozerskype: matthew.pocock tel: (0191) 2566550mob: +447535664143

--
Dr Matthew PocockIntegrative Bioinformatics Group, School of Computing Science, Newcastle Universitymailto: turingatemyhamster@gmail.com gchat: turingatemyhamster@gmail.commsn: matthew_pocock@yahoo.co.uk irc.freenode.net: drdozerskype: matthew.pococktel: (0191) 2566550mob: +447535664143

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

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

On Thu, Sep 15, 2011 at 2:22 PM, Matthew Pocock <turingatemyhamster@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?
 

  --Rex

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

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

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

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

On Thu, Sep 15, 2011 at 2:22 PM, Matthew Pocock <turingatemyhamster@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

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

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

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

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

On Thu, Sep 15, 2011 at 2:22 PM, Matthew Pocock <turingatemyhamster@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

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

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

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

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

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

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

On Thu, Sep 15, 2011 at 2:22 PM, Matthew Pocock <turingatemyhamster@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

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.s...

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
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
>
> On 28 November 2011 16:05, Vlad Patryshev wrote:
>
>
>
>
>
>
>
>
>
> > 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
>
> > On Mon, Nov 28, 2011 at 4:59 AM, Matthew Pocock <
> > turingatemyhams...@gmail.com> wrote:
>
> >> 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: 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
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143

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 <seanreque@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/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
>
> On 28 November 2011 16:05, Vlad Patryshev <vpatrys...@gmail.com> wrote:
>
>
>
>
>
>
>
>
>
> > 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
>
> > On Mon, Nov 28, 2011 at 4:59 AM, Matthew Pocock <
> > turingatemyhams...@gmail.com> wrote:
>
> >> 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: 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
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143

--
Dr Matthew PocockIntegrative Bioinformatics Group, School of Computing Science, Newcastle Universitymailto: turingatemyhamster@gmail.com gchat: turingatemyhamster@gmail.commsn: matthew_pocock@yahoo.co.uk irc.freenode.net: drdozerskype: matthew.pococktel: (0191) 2566550mob: +447535664143

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 <turingatemyhamster@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 <seanreque@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/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
>
> On 28 November 2011 16:05, Vlad Patryshev <vpatrys...@gmail.com> wrote:
>
>
>
>
>
>
>
>
>
> > 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
>
> > On Mon, Nov 28, 2011 at 4:59 AM, Matthew Pocock <
> > turingatemyhams...@gmail.com> wrote:
>
> >> 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: 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
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143

--
Dr Matthew PocockIntegrative Bioinformatics Group, School of Computing Science, Newcastle University mailto: turingatemyhamster@gmail.com gchat: turingatemyhamster@gmail.commsn: matthew_pocock@yahoo.co.uk irc.freenode.net: drdozerskype: matthew.pococktel: (0191) 2566550mob: +447535664143

--
Dr Matthew PocockIntegrative Bioinformatics Group, School of Computing Science, Newcastle Universitymailto: turingatemyhamster@gmail.com gchat: turingatemyhamster@gmail.commsn: matthew_pocock@yahoo.co.uk irc.freenode.net: drdozerskype: matthew.pococktel: (0191) 2566550mob: +447535664143

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-

On 29 Nov 2011, at 12:54, Matthew Pocock 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 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 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/Heap.s...
>
> 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
> 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
> >
> > On 28 November 2011 16:05, Vlad Patryshev wrote:
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > 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
> >
> > > On Mon, Nov 28, 2011 at 4:59 AM, Matthew Pocock <
> > > turingatemyhams...@gmail.com> wrote:
> >
> > >> 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: 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
> > irc.freenode.net: drdozer
> > skype: matthew.pocock
> > tel: (0191) 2566550
> > mob: +447535664143
>
>
>

On 29 November 2011 15:19, Sciss <contact@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

best, -sciss-




On 29 Nov 2011, at 12:54, Matthew Pocock 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 <turingatemyhamster@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 <seanreque@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/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
> >
> > On 28 November 2011 16:05, Vlad Patryshev <vpatrys...@gmail.com> wrote:
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > 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
> >
> > > On Mon, Nov 28, 2011 at 4:59 AM, Matthew Pocock <
> > > turingatemyhams...@gmail.com> wrote:
> >
> > >> 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: 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
> > 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: turingatemyhamster@gmail.com
> gchat: turingatemyhamster@gmail.com
> msn: matthew_pocock@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: turingatemyhamster@gmail.com
> gchat: turingatemyhamster@gmail.com
> msn: matthew_pocock@yahoo.co.uk
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143
>

--
Dr Matthew PocockIntegrative Bioinformatics Group, School of Computing Science, Newcastle Universitymailto: turingatemyhamster@gmail.com gchat: turingatemyhamster@gmail.commsn: matthew_pocock@yahoo.co.uk irc.freenode.net: drdozerskype: matthew.pococktel: (0191) 2566550mob: +447535664143

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-

On 29 Nov 2011, at 15:36, Matthew Pocock wrote:

>
>
> On 29 November 2011 15:19, Sciss 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
>
>
> best, -sciss-
>
>
>
>
> On 29 Nov 2011, at 12:54, Matthew Pocock 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 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 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/Heap.s...
> >
> > 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
> > 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
> > >
> > > On 28 November 2011 16:05, Vlad Patryshev wrote:
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > > 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
> > >
> > > > On Mon, Nov 28, 2011 at 4:59 AM, Matthew Pocock <
> > > > turingatemyhams...@gmail.com> wrote:
> > >
> > > >> 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: 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
> > > 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: turingatemyhamster@gmail.com
> > gchat: turingatemyhamster@gmail.com
> > msn: matthew_pocock@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: turingatemyhamster@gmail.com
> > gchat: turingatemyhamster@gmail.com
> > msn: matthew_pocock@yahoo.co.uk
> > irc.freenode.net: drdozer
> > skype: matthew.pocock
> > tel: (0191) 2566550
> > mob: +447535664143
> >
>
>
>
>

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
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 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 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...
>
> >> 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
> >> 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
>
> >> > On 28 November 2011 16:05, Vlad Patryshev wrote:
>
> >> > > 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
>
> >> > > On Mon, Nov 28, 2011 at 4:59 AM, Matthew Pocock <
> >> > > turingatemyhams...@gmail.com> wrote:
>
> >> > >> 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: 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
> >> > 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
> > 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
> irc.freenode.net: drdozer
> skype: matthew.pocock
> tel: (0191) 2566550
> mob: +447535664143