Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

mutable.PriorityQueue.toString ordering after first element is unpredictable #9424

Closed
scabug opened this issue Jul 30, 2015 · 5 comments
Closed

mutable.PriorityQueue.toString ordering after first element is unpredictable #9424

scabug opened this issue Jul 30, 2015 · 5 comments
Assignees
@Ichoran
Labels
has PR
Milestone
2.11.8

Comments

@scabug
Copy link

scabug commented Jul 30, 2015

Well, the problem is best described by code. Look at the order of the elements after I add the first "3". It seems to be wrong.

scala> import scala.collection._
import scala.collection._

scala> val a = mutable.PriorityQueue.empty[Int](Ordering.by(-_))
a: scala.collection.mutable.PriorityQueue[Int] = PriorityQueue()

scala> a += 2
res0: a.type = PriorityQueue(2)

scala> a += 10
res1: a.type = PriorityQueue(2, 10)

scala> a += 3
res2: a.type = PriorityQueue(2, 10, 3)

scala> a += 3
res3: a.type = PriorityQueue(2, 3, 3, 10)
@scabug
Copy link
Author

scabug commented Jul 30, 2015

Imported From: https://issues.scala-lang.org/browse/SI-9424?orig=1
Reporter: Matthias (t3l)
Affected Versions: 2.11.7

@scabug
Copy link
Author

scabug commented Jul 30, 2015

Matthias (t3l) said:
I just noticed that this is only an issue with the string representation and that the underlying queue/deqeue codes works fine. Anyway, this should be fixed. However, I reduced the priority to "minor".

a.dequeue
res34: Int = 2
a.dequeue
res35: Int = 3
a.dequeue
res36: Int = 10

@scabug
Copy link
Author

scabug commented Aug 2, 2015

@SethTisue said:
I don't think this is a bug. A heap isn't fully sorted; it's only as sorted as it needs to be in order to give right answers.

@scabug
Copy link
Author

scabug commented Aug 3, 2015

Kevin Mas Ruiz (kmruiz) said (edited on Aug 3, 2015 11:14:20 AM UTC):
I don't agree, because that is a implementation detail that the client should ignore. I really think it's a minor bug.

Edit: ------
PriorityQueue is supposed to have, from the client side of the class, always the correct order. If internally it does this incrementally or not is not important for the user.

Also having a simple and reliable inspection method like toString is very useful for assertions when unit testing.

@scabug
Copy link
Author

scabug commented Aug 29, 2015

@Ichoran said:
scala/scala#4715 (documentation change only)

@scabug scabug closed this as completed Sep 2, 2015
@scabug scabug added this to the 2.11.8 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@Ichoran Ichoran

Labels
has PR
Projects
None yet
Milestone
2.11.8
Development

No branches or pull requests
2 participants
@Ichoran @scabug