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

LinkedHashMap.keys loses ordering when manipulated #4954

Closed
scabug opened this issue Aug 30, 2011 · 10 comments
Closed

LinkedHashMap.keys loses ordering when manipulated #4954

scabug opened this issue Aug 30, 2011 · 10 comments
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented Aug 30, 2011

LinkedHashMap.keys returns the keys of the map in insertion order, but if that collection is manipulated in any way, it reverts to an unordered Set.

This is somewhat surprising, particularly as keys is Iterable.

Welcome to Scala version 2.9.0.1 (OpenJDK 64-Bit Server VM, Java 1.7.0-internal).
Type in expressions to have them evaluated.
Type :help for more information.

scala> val m = scala.collection.mutable.LinkedHashMap("one" -> 1, "two" -> 2, "three" -> 3, "four" -> 4, "five" -> 5)
m: scala.collection.mutable.LinkedHashMap[java.lang.String,Int] = Map(one -> 1, two -> 2, three -> 3, four -> 4, five -> 5)

scala> m.keys
res0: Iterable[java.lang.String] = Set(one, two, three, four, five)

scala> m.keys.drop(0)
res1: Iterable[java.lang.String] = Set(four, three, two, five, one)
@scabug
Copy link
Author

scabug commented Aug 30, 2011

Imported From: https://issues.scala-lang.org/browse/SI-4954?orig=1
Reporter: @samskivert
Affected Versions: 2.9.0-1, 2.9.1

@scabug
Copy link
Author

scabug commented Aug 30, 2011

@paulp said:
You are being fooled by a (fixed since 2.9.0-1) bug in the repl. If you compile and run this, they are in order.

object Test {
  val m = scala.collection.mutable.LinkedHashMap("one" -> 1, "two" -> 2, "three" -> 3, "four" -> 4, "five" -> 5)
  
  def main(args: Array[String]): Unit = {
    m.keys foreach println
    m.keys drop 1 foreach println
  }
}

The repl has its own logic for printing traversables so Arrays don't get printed as mr. squiggly.

@scabug
Copy link
Author

scabug commented Aug 30, 2011

@paulp said:
I take it back. I got unlucky with "drop 1" there, drop 0 I see the same thing.

@scabug
Copy link
Author

scabug commented Aug 30, 2011

@samskivert said:
I did encounter this bug initially in real code, and just resorted to the repl to isolate it.

I presume it has something to do with the REPR of LinkedHashMap keys as a Set instead of an OrderedSet (or whatever collection has both set and fixed ordering semantics, if such a beast exists).

@scabug
Copy link
Author

scabug commented Aug 30, 2011

@paulp said:
I'm going with this:

scala> scala.collection.mutable.LinkedHashMap().isInstanceOf[scala.collection.generic.Sorted[_, _]]
res0: Boolean = false

Without that, nothing is going to return the same type, i.e. "Sorted".

@scabug
Copy link
Author

scabug commented Aug 30, 2011

@samskivert said:
Is there an equivalent Ordered (rather than Sorted)? LinkedHashMap isn't sorted, just ordered based on insertion order.

@scabug
Copy link
Author

scabug commented Aug 30, 2011

@paulp said:
Yeah, I was just realizing that, although I would say it is sorted: it's sorted and the custom ordering is the insertion order. But it looks to me like nothing beyond the trivial is going to keep happening in insertion order. keys returns DefaultKeySet, which will not be returning ordered sets on derivative operations.

It looks like keysIterator preserves the order btw.

@scabug
Copy link
Author

scabug commented Aug 31, 2011

@paulp said:
Here's another thing which seems less than ideal. I wish I could even find documentation as to what is expected here. If it's intentional that "keySet" stays sorted while "keys" throws it out the window, that should not be difficult information to come by.

scala> scala.collection.immutable.SortedMap(1 to 100 zip (1 to 100) : _*).keys
res0: Iterable[Int] = Set(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100)

scala> res0.getClass
res1: java.lang.Class[_ <: Iterable[Int]] = class scala.collection.immutable.SortedMap$DefaultKeySortedSet

scala> scala.collection.immutable.SortedMap(1 to 100 zip (1 to 100) : _*).keys ++ Set()
res2: Iterable[Int] = Set(69, 88, 5, 10, 56, 42, 24, 37, 25, 52, 14, 20, 46, 93, 57, 78, 29, 84, 61, 89, 1, 74, 6, 60, 85, 28, 38, 70, 21, 33, 92, 65, 97, 9, 53, 77, 96, 13, 41, 73, 2, 32, 34, 45, 64, 17, 22, 44, 59, 27, 71, 12, 54, 49, 86, 81, 76, 7, 39, 98, 91, 66, 3, 80, 35, 48, 63, 18, 95, 50, 67, 16, 31, 11, 72, 43, 99, 87, 40, 26, 55, 23, 8, 75, 58, 82, 36, 30, 51, 19, 4, 79, 94, 47, 15, 68, 62, 90, 83, 100)

@scabug
Copy link
Author

scabug commented Sep 6, 2011

@paulp said:
Need input.

@scabug
Copy link
Author

scabug commented Sep 6, 2011

@paulp said:
Going to pursue a minimal fix for linkedhashmap; we don't want to try to support orderedness in the type system, and linkedhashmap is performance sensitive so shoehorning things so it can use Sorted's machinery to retain ordering is a bust.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants