Is there any library in Kotlin or Java land that handles a data structure of ranges / intervals? I’v...

# getting-started

[Kirill Grouchnikov]

Is there any library in Kotlin or Java land that handles a data structure of ranges / intervals? I’ve been playing with https://github.com/lodborg/interval-tree for a bit, but it’s not quite what I’m looking for:

val tree = IntervalTree<Int>()

    tree.add(IntegerInterval(1, 4, Interval.Bounded.CLOSED))
    tree.add(IntegerInterval(6, 8, Interval.Bounded.CLOSED))
    // This ends up with three intervals [0,7], [1,4], [6,8]
    tree.add(IntegerInterval(0, 7, Interval.Bounded.CLOSED))

What I’m looking for is for the data structure to end up holding the “unified” interval of [0,8] after this third operation.

And the same for deletion. If I have a single [0,8] interval and I remove [2,4], it should now have two intervals - [0,2] and [4,8].

[Kirill Grouchnikov]

Can’t seem to find anything in Java / Kotlin for discrete interval trees, which sounds like what I’m looking for

[ephemient]

just yesterday I coded a very simple interval tree for the advent of code puzzle, https://github.com/ephemient/aoc2022/blob/85d5f511994cc0b69a043cf7c39b9a5dfa35dd07[…]/kt/src/commonMain/kotlin/com/github/ephemient/aoc2022/Day15.kt

[ephemient]

didn't need deletion so I didn't code that up, though it should be pretty similar to addition. and of course it's O(# intervals), you'd have to use a different data structure for log n time

[Kirill Grouchnikov]

val ranges = mutableListOf(IntRange(1, 4), IntRange(7, 10))
    ranges.addInterval(IntRange(2, 6))
    println(ranges)

[Kirill Grouchnikov]

This should return a single (1, 10) range

[Kirill Grouchnikov]

Same for

val ranges = mutableListOf(IntRange(1, 5), IntRange(7, 10))
    ranges.addInterval(IntRange(6, 6))

[Kirill Grouchnikov]

https://github.com/jaketodaro/discrete-interval-tree/tree/master/src has a few minor bugs, but other than those, looks like is quite usable after converting the code (with fixes) to Kotlin

[ephemient]

https://pl.kotl.in/olVqZOLGa (adjusting for an off-by-one… the math makes more sense with half-open ranges)

[ephemient]

but yeah, a proper balanced tree would be the way to go if you had lots of intervals

[Michael de Kaste]

I made one for my work at the start of the year; it supports different types of comparable keys and supports mapping it to different values. It might have tons of bugs, but from our testing, it works.

https://pl.kotl.in/VxcKdFBCQ

[Michael de Kaste]

with access to the backingMap you can then see that the values will be

{null=nope, 1=hi, 2=bye, 4=nope}

and you can extract ranges from that.

'deletion' is supported by adding a range with the defaultValue (which can be null for convenience ofc)