This is a reworking of the structure of Queue's in: List[A] to be now a List[A | Many[A]], which allows for enqueueAll operations to be performed in O(1) by simply setting

in = Many(that) :: this.in

When a rotation happens (when a dequeueing occurs which causes us to rotate the in list to the out list, at that point, the in list is flattened to construct the new out list.

The end result is that instead of copying the data twice (copying once into in and again to rotate into out), we only perform one copying of the data, at rotation-time. We avoid the equeueAll-time copying by appending prepending the collection itself as the first element of in.

An other more elaborated description was written here: #8565 (comment)

This is a very early version of this PR and it is definitely not ready for merging.

Also, this one is on pause until at least #8601 is through, since this code somewhat depends on that code to realize performance improvements, so benchmarks compared to the 2.13.x branch are underwhelming or even negative.

TODO

• Run benchmarks to ensure that the expected speedups are indeed worth the complexity, and other operations on queues are not slowed down (by much)

• Write more unit/prop tests for queues

• Implement faster queue.apply(Int) implementation

• Extract iterator class from queue

• Make any necessary changes to Queue scaladocs and if applicable, scala-lang.org