Selecting a range in a dictionary

Help! Data Structure
1

Hi, we have the dictionaries rbtree and assoc which holds orderd keys internally. Therefore it should be possible to select a range of keys even if I don’t know the keys exactly. Lets say I have 50 keys inserted: 0, 2, 4, …, 98 and I want only the keys which are in the range between 51 to 55. How can I do this without iterating over all keys sequentially?

Kind regards,
Frank Schwidom

2

Dicts also have their entries ordered by keys in the current implementation.

3

I actually just had the exact same problem; I did a brief write-up of my solution for rbtrees here.

Here’s the code:



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).

Example usage:

?- 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]).