Quick Tip: Interval Trees in Prolog

Today I had a need to be able to efficiently look up mappings from a range to a value in Prolog. The initial naïve version looked essentially like this:

find_thing_in_range(Mapping, Key, Value) :-
    member(start_end_value(Start, End, Value), Mapping),
    between(Start, End, Key), !.

Simple, nice and declarative: I build up a list of terms like start_end_value(Start, End, Value) to represent the range and associated value, nice and easy.

Unfortunately, while the runtime wasn’t too bad for the simple testcases I was using, profiling the overall predicate for which this was a small component, this accounted for 80% of the runtime. That wasn’t too surprsing, as using member/2 meant a linear traversal through the list each time and the predicate was getting called quite a bit.

An obvious solution then would be to use a more efficient data structure for searching. Red-black trees (via library(rbtrees)) are usually the go-to, but the normal rb_lookup/3 wouldn’t work for me here. The normal use of the trees assume that you’re searching for a specific key, but here I want the keys to be a range that I will search within.

Fortunately, it was pretty easy to modify rb_lookup/3 to instead search inside a range:

rb_lookup_range(Key, KeyRange, Value, t(_, Tree)) =>
    rb_lookup_range_(Key, KeyRange, Value, Tree).

rb_lookup_range_(_Key, _KeyRange, _Value, black('', _, _, '')) :- !, fail.
rb_lookup_range_(Key, KeyRange, Value, Tree) :-
    arg(2, Tree, Start-End),
    compare(CmpS, Key, Start),
    compare(CmpE, Key, End),
    rb_lookup_range_(t(CmpS, CmpE), Key, Start-End, KeyRange, Value, Tree).

rb_lookup_range_(t(>, <), _, Start-End, KeyRange, Value, Tree) =>
    arg(3, Tree, Value),
    KeyRange = Start-End.
rb_lookup_range_(t(=, _), _, Start-End, KeyRange, Value, Tree) =>
    arg(3, Tree, Value),
    KeyRange = Start-End.
rb_lookup_range_(t(_, =), _, Start-End, KeyRange, Value, Tree) =>
    arg(3, Tree, Value),
    KeyRange = Start-End.
rb_lookup_range_(t(<, _), Key, _, KeyRange, Value, Tree) =>
    arg(1, Tree, NTree),
    rb_lookup_range_(Key, KeyRange, Value, NTree).
rb_lookup_range_(t(_, >), Key, _, KeyRange, Value, Tree) =>
    arg(4, Tree, NTree),
    rb_lookup_range_(Key, KeyRange, Value, NTree).

Use it like this:

?- L = [(0-50)-1, (51-100)-2, (101-150)-3],
   list_to_rbtree(L, Rb),
   rb_lookup_range(5, KR, V, Rb),
   format("Found ~w in range ~w: Value ~q~n", [5, KR, V]).

If you ever need to do something like this, hope this is useful!