Maintaining orderedness during mapping

I have a variable called mySet which is of type Set

mySet : Set = SortedSet(item1, item2, ...)

When I call: myitemToTailoredString( _ ) )

I get back a Set back with no discernible ordering (since the return type is type Set)

If I change the type of mySet to SortedSet i.e.

mySet : SortedSet = SortedSet(item1, item2...)

when I call myitemToTailoredString( _ ) ) I get a sorted set back but sorted lexicographically.

What I would like is to maintain the type of mySet as type Set (not SortedSet) but take each element in turn and apply map to it, returning the order that the elements are stored in. So if mySet happens to be a sortedSet the returned Set from calling map maintains the order the items are called in.

The context is I’m trying to produce a long string with each item taken from mySet (which is a SortedSet) with a method applied to each. I’ve tried flatten but this gives a list of chars - I suppose I could toString the list of chars though. However, I think this has the same problem however of messing up the ordering."") (_ + _)

I presume I would have to use some other method than map to maintain the ordering of the returned values?

You lost me at the part where you seem to say that you want insertion order, yet you want a SortedSet which sorts its elements according to a certain Ordering.

If you want to maintain ordering you want a Seq, not a Set. Part of the contract of Set is that ordering generally isn’t preserved. This is because the data structures that make efficient sets (like Hashtables and BSTs) use ordering as part of what makes them efficient. The Hashtable gives you an ordering that will appear random because of the use of a hash code. The BST uses a natural ordering on the values to make a sorted order.

Of course, the Seq is going to be O(n) for contains operations while the Set is O(log n) or O(1) depending on the implementation. My guess is that if you take your original SortedSet and call toSeq, then map that, you will get what you want as long as you don’t really need set operations on the result.

Yes thank you both. That does it. I effectively wanted to keep a's type below as Set (although instantiate it with a SortedSet) but be able to map across it, and maintain the order of the answers.

val a : Set[Int] = SortedSet(1,2,9,10, 100) gives

res19: scala.collection.mutable.Set[String] = Set(01, 001, 1, 2, 9)
which is bad for me

whereas ) gives

res20: Seq[String] = ArrayBuffer(1, 2, 9, 01, 001)
which is good.

I then want to combine the strings which I presume
res20.foldLeft("")(_ + _) or even res20.mkString("")

Still enjoying learning!

1 Like

Go with mkString if there is any chance that the set will have a lot of elements. It should have an O(n) implementation while the use of + on immutable strings will force the fold to be O(n^2).