Optimise immutable.Queue for head/tail

[NthPortal]

Optimise immutable.Queue so that head/tail usage pattern does not cause double traversal of in.

Take the following usage pattern:

var queue: Queue[Int] = ???
while (queue.nonEmpty) {
  val elem = queue.head
  queue = queue.tail
  // do something with `elem` here
}

If out is empty and in is not, val elem = queue.head will require traversing in to find its last element, and queue = queue.tail will require reversing in (which requires traversal).

immutable.Queue's methods should be optimised so that when dequeueing elements, it does not leave out empty (unless in is also empty), and when enqueueing elements, it puts at least one element in out if both in and out are empty (although once you're checking, might as well put everything in out).

---

This change should be binary compatible, as it only requires changes to class internals.

[gi114]

Hi,

I just started looking at places I can contribute to Scala and realized I am quite confused on how Queue in and out lists interchange elements. For example, If I add some element in the in list, do I need to add it to the out list as well ? Otherwise I will not be able to dequeue from out.. So my question is, how do they stay up to date with each other? It seems we have to perform operations twice ?

Thank you for help! Giulia

[szeiger]

They don't. You always add to in and remove from out. The scaladoc comment explains it quite nicely:

Queue is implemented as a pair of Lists, one containing the ''in'' elements and the other the ''out'' elements. Elements are added to the ''in'' list and removed from the ''out'' list. When the ''out'' list runs dry, the queue is pivoted by replacing the ''out'' list by ''in.reverse'', and ''in'' by ''Nil''.

[gi114]

Hi, I updated the PR for this ticket https://github.com/scala/scala/pull/7873

[gi114]

Hi,

It looks like the CI is still checking on my previous pull request which failed. I deleted that (I thought so) and made another PR: https://github.com/scala/scala/pull/7873

Would you be able to help me out and switch the checks on this one?

Thank you in advance!

[NthPortal]

I'm really sorry - I've been really busy (moving, etc.) and not gotten a chance to look at it. I'll try to have a look this weekend.

[gi114]

Hi,

Whenever you can, thanks for that. I thought of cancelling the PR on the branch completely and send one new PR again. Let me know if you think it is better, to clean up

All tests and compilation pass. The rationale of the PR is in the https://github.com/scala/scala/pull/7873 where I explain my updates

Thanks again!

[som-snytt]

I don't really know, but I think head/tail is an anti-pattern, like appending to List.

Maybe we need a linter to detect it and say "Dear user: this is what dequeue is for."

Or: "dequeue is not short for Dairy Queen." A DQ just closed up the street not long ago.

[dwijnand]

Assigning to you, @NthPortal, as you said you might find capacity for it in the future (not a request! if you don't have bandwidth we maybe we could find another volunteer).