# Selecting a range in a dictionary

**URL:** <https://swi-prolog.discourse.group/t/selecting-a-range-in-a-dictionary/8957>\
**Category:** Data Structure\
**Created:** [April 23, 2025, 2:04pm UTC](https://swi-prolog.discourse.group/t/selecting-a-range-in-a-dictionary/8957 "2025-04-23T14:04:47Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Frank\_Schwidom](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/frank_schwidom/32/7662_2.png) [@Frank\_Schwidom](https://swi-prolog.discourse.group/u/Frank_Schwidom)\
**Post date:** [April 23, 2025, 2:04pm UTC](https://swi-prolog.discourse.group/t/selecting-a-range-in-a-dictionary/8957/1 "2025-04-23T14:04:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\
**Post date:** [April 23, 2025, 2:35pm UTC](https://swi-prolog.discourse.group/t/selecting-a-range-in-a-dictionary/8957/2 "2025-04-23T14:35:31Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![jamesnvc](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jamesnvc/32/14_2.png) [@jamesnvc](https://swi-prolog.discourse.group/u/jamesnvc)\
**Post date:** [April 24, 2025, 12:23am UTC](https://swi-prolog.discourse.group/t/selecting-a-range-in-a-dictionary/8957/3 "2025-04-24T00:23:44Z")

</div>

I actually just had the exact same problem; I did a brief write-up of my solution for rbtrees [here](https://occasionallycogent.com/prolog_interval_tree/index.html).

Here’s the code:

```prolog

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:

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

```