mutable.PriorityQueue: leaky type for newBuilder and algorithmic inefficiency

[Chris Okasaki]

I've run across what I believe was an oversight in mutable.PriorityQueue.

The newBuilder method in object PriorityQueue is defined as

   def newBuilder[A](implicit ord: Ordering[A]) = new PriorityQueue[A]

The lack of a return type means that the type in the API comes out as

   def newBuilder[A](implicit ord: Ordering[A]): PriorityQueue[A]

rather than the expected

   def newBuilder[A](implicit ord: Ordering[A]): Builder[A, PriorityQueue[A]]

I ran across this because I was dismayed to discover that creating a new

priority queue takes O(N log N) time when it can easily be done in O(N)

time.  Well, easily in the algorithmic sense anyway.  The codefix is

unnecessarily complicated by this type leak in the API.

Similar algorithmic improvements can be made to improve the running times of

enqueue, ++=, and reverse.

I would be happy to contribute, but the CONTRIBUTING doc says to post here first.

[Rex Kerr]

It would be great to have a fix for this!  Submit a bug report first so we can track it.  Mention as the first comment that you're working on a fix.  (You won't be able to assign the bug to yourself, but that will keep anyone else from duplicating effort.)

  --Rex

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Rex Kerr]

It would be a fix to 2.12, of course.  We can't change the signature in 2.11, and even if you do want to backport it, having a clean fix in 2.12 first would be best.

  --Rex

[Simon Ochsenreither]

Thanks for your report! If you want to go the extra mile it might make sense to do a grep through the code base and check whether any other newBuilder definitions suffer from the same issue?

[martin odersky]

Thanks for the report, Chris! For what it's worth, this class of
problems is fixed in Dotty. Dotty's type propagation will always
prefer an inherited return type over the type of the right hand side
of an implementation.

Cheers

-- Martin

> --
> You received this message because you are subscribed to the Google Groups
> "scala-internals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to scala-interna...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

--

Martin Odersky
EPFL and Lightbend