Scala range / interval map structure [closed]

Question

I have almost the same question as mentioned in Data structures that can map a range of keys to a value, but for Scala.

That is, I'd like to have a mutable system of non-overlapping 1D ranges [a[i], b[i]) that would map to some sort of value v[i]. A standard underlying data structure to do this kind of job is a red-black tree.

Operations that I'd like it to have, preferably all of them should have complexity of O(log n):

• Query and get a given range (start, end, stored value) or lack of thereof by specifying any point inside it
• Insert a new range into this structure
• Remove a range from structure

So, I guess so far I see the following variants, all of which have their cons:

• Roll-your-own-container on top of Java's TreeMap - quick & dirty, but probably bad in long term due to lack of proper maintenance
• Use Guava's RangeMap - possible, but would be pretty awkward in Scala collections world
• Try to use Scala's red-black tree implementations and try to roll-your-own, however, I guess that would be pretty hard, given that Scala's TreeMap is immutable-only and misses straightforward lookup methods, such as Java's TreeMap floorEntry

Am I missing something here? Are there any Guava-like well-maintained collections extensions libraries using Scala-centric APIs that extend basic Scala collections?

Strongly related questions:

• Migrating Java TreeMap code to Scala? - mentions to "just use Java's TreeMap" and forget about anything else
• Java versions of this issue:
  • Data structures that can map a range of keys to a value
  • Hashtable key within integer interval
  • Using java map for range searches
  • Java - Suitable data structure for search interval

Answer 1

I'd most probably encapsulate Guava's RangeMap. All you need is a three method class, behind which you can hide the non-scalaish collection.

I was curious how hard it'd be to roll my own Java NavigableMap-based solution, and it's pretty trivial:

• define a class MyValue containing (start, end, stored value)
• use a map mapping the start point to the corresponding MyValue

With only 40 lines in Java with Lombok (and probably fewer in Scala), I wouldn't be afraid of any maintenance. I wrote just a very rudimentary test.