Search code examples
javascalascala-collectionstreemaptreeset

Migrating Java TreeMap code to Scala?

I am migrating my Java code base to pure Scala and I am stuck on this one piece of code. I have an implementation of an IntervalMap i.e. a data structures that let's you efficiently map ranges [from,to] to values where the set, delete and get operations are all O(log n) (slightly different from an IntervalTree or a SegmentTree).

This code uses Java's java.util.TreeMaps and while migrating to Scala, I ran into 2 big issues:

  1. Scala has no mutable.TreeMap - I decided to go around it by using mutable.TreeSet (oddly Scala has mutable.TreeSet but no mutable.TreeMap) for storing the keys and storing the values in an auxiliary mutable.Map. This is an unpleasant hack but is there any better way?

  2. Next problem is Scala's mutable.TreeSet has no equivalent of java.util.TreeSet's ceilingKey, floorEntry, pollFirst, pollLast which are all O(log n) operations in Java.

So, how can I best migrate my code to Scala? What are the best practices in these situations? I really do not want to write my own tree implementations. Is there a more idiomatic Scala way of writing IntervalMaps that I am not aware of? Or is there some reputable library out there? Or does Scala just plain suck here with its gimped TreeSet and non-existent TreeMaps. Ofcourse I can just use Java's TreeMap in Scala but that is ugly and I lose all the nice Scala collection features and I might as well use Java then.

Here is my current Java code: https://gist.github.com/pathikrit/5574521

Solution

  • Scala 2.12 has mutable.TreeMap finally: https://github.com/scala/scala/pull/4504