18

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:

sebkur
  • 658
  • 2
  • 9
  • 18
GreyCat
  • 16,622
  • 18
  • 74
  • 112
  • Do you need this for arbitrary comparable values, or just for int/long ranges? – Rüdiger Klaehn Aug 14 '14 at 07:53
  • Personally, I would use these for accounting of virtual memory ranges, thus my application would be `long` ranges, but I don't see much point in using non-generic approach here - not like it could offer tremendous performance or space boost. – GreyCat Aug 14 '14 at 09:32
  • Can't you use `map.from(x).firstKey()` as a replacement for `map.floorEntry`? – maaartinus Aug 14 '14 at 11:10
  • @maaartinus: You can, but it still leaves dealing with `immutable. TreeMap` - you end up either rolling out full implementation or emulating it with `mutable.TreeSet` + `mutable.Map` => it heavily impacts memory usage and somewhat impacts performance. Probably doesn't worth the effort. – GreyCat Aug 14 '14 at 11:33
  • What operations do you need to do on this map? Do you need to query with an index and have it return all (or even one) of the ranges that include that index, along with associated values? Because then you probably need an R-tree. All of the various `TreeMap` implementations aren't suitable for that use case. – wingedsubmariner Aug 14 '14 at 15:18
  • @maaartinus Small point, but `map.from(x).firstKey` is equivalent to `ceilingEntry`, not `floorEntry`. `map.to(x).lastKey` is equivalent to `floorEntry`. – wingedsubmariner Aug 14 '14 at 15:24
  • @wingedsubmariner: Thanks, I'll clarify it now in the question. The ranges itselves are non-overlapping, so `TreeMap` is more that sufficient in terms of simplicity. – GreyCat Aug 14 '14 at 15:42

1 Answers1

2

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.

maaartinus
  • 44,714
  • 32
  • 161
  • 320