Imported From: https://issues.scala-lang.org/browse/SI-9893?orig=1
Reporter: @SethTisue
Affected Versions: 2.10.6, 2.11.8

@SethTisue said:
There remains an issue of what order we want: are new items inserted at the back or the front?

mutable.ListMap is implemented as a very simple wrapper around scala.collection.immutable.List. As a natural consequence, new items are added to the front.

immutable.ListMap doesn't work that way — it's implemented on top of a private Node class. internally, it adds items on the front, but then it does def iterator = ... .toList.reverseIterator so the externally observable order is forwards. Note that this is expensive, as both toList and reverseIterator copy the whole collection.

@SethTisue said:
So, what is to be done? There are different possibilities, and there are different considerations depending on whether a fix is targeting 2.11.x, 2.12.x, or 2.13.x.

in ascending order of ambitiousness, possibilities include:

• document the existing (gruesome) 2.10/2.11 behavior
• restore the 2.9 behavior (both kinds of ListMap preserve order, but in opposite directions) and document that
• choose a direction and make both kinds of ListMap preserve it, redoing the implementations if necessary

Note that wrapping immutable.List is a really terrible way to implement mutable.ListMap — tons of unnecessary copying.

@Ichoran said (edited on Aug 17, 2016 9:02:39 PM UTC):
ListMap and ListSet have basically zero reason to exist if they don't preserve insertion order. Except there isn't even a mutable.ListSet. I think this suggests that the mutable one should just be deprecated. If you reeeeeally need the functionality of traversal-in-order, there is LinearHashMap/Set, and if you reeeeeeally need speed you should implement your own anyway. In the meantime, before deprecation kicks in, insertion order is probably a good thing to preserve. I have no strong feeling about which order.

For immutable.ListSet/Map, I think either order is okay as long as it is incredibly clear what the expectation is, and it is followed for every operation. That is: head gives you the most recent item and iteration is always from recent to older; or head gives you the oldest item and iteration is always from recent to older. And this property should be maintained through map, flatMap, etc. (which will mean using builders to create the underlying links because otherwise the order will switch every time you map).

Dmytro Kondratiuk (dk14) said (edited on Oct 19, 2016 1:29:07 AM UTC):
I've noticed that LinkedHashMap works as expected, but it also (same as mutable.ListMap) seems to have 0 tests for ordering (https://github.com/scala/scala/blob/2.12.x/test/junit/scala/collection/mutable/LinkedHashMapTest.scala).

scala> val m = collection.mutable.LinkedHashMap[Int, Int]()
m: scala.collection.mutable.LinkedHashMap[Int,Int] = Map()

scala> m += 1 -> 1
res42: m.type = Map(1 -> 1)

scala> m += 2 -> 2
res43: m.type = Map(1 -> 1, 2 -> 2)

scala> m += 3 -> 3
res44: m.type = Map(1 -> 1, 2 -> 2, 3 -> 3)

scala> m += 4 -> 4
res45: m.type = Map(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4)

scala> m += 5 -> 5
res46: m.type = Map(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5)

scala> m -= 99
res47: m.type = Map(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5)

scala> m -= 3
res48: m.type = Map(1 -> 1, 2 -> 2, 4 -> 4, 5 -> 5)

@Ichoran said:
[~dk14] A PR to fix this deficiency in the tests is welcome!

@ruippeixotog said:
Just to add that I recently made some modifications to immutable.ListSet and immutable.ListMap in order to make them behave in a more consistent way. Initially I tried to to make the immutable.ListSet iterator provide the elements in reverse order for performance reasons, but I was forced to do the other way around as it seems the compiler depends on the current iteration order of ListSet for some things. That's the reason why toList.reverseIterator was kept there. The PR is scala/scala#5103.

Apoorv Agarwal (apoorv024) said:
https://issues.scala-lang.org/browse/SI-9893?focusedCommentId=75566&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-75566

I was thinking of adding test cases for ordering here. Are those tests still needed?

@julienrf @szeiger should we deprecate mutable.ListMap in 2.13? People should just use a var immutable.ListMap instead, the current implementation (besides being buggy) doesn't add any value.

I’m happy to deprecate mutable.ListMap