[eclipse-users] Creating an interval tree data structure with prolog

Hi All,

I am attempting to create an interval tree data structure with
eclipse-clp.  You can see what one is at:

http://en.wikipedia.org/wiki/Interval_tree

In a simple case, the intervals do not overlap and they can be
inserted into a simple binary tree and queried in O(log n) time.

The part of the code I have written already is this:

empty(void).

% Insert(+TreeIn, +Key, +Data, -TreeOut).
% Insert data Data with key Key into the TreeIn.

insert(void, K, D, (K, D, void, void)).
insert((RK, RD, L, R), K, D, (RK, RD, TL, R)):- K @< RK, !, insert(L, K, D, TL).
insert((RK, RD, L, R), K, D, (RK, RD, L, TR)):- insert(R, K, D, TR).

select((K, D, _, _), K, D).
select((RK, _, L, _), K, D):- K @< RK, !, select(L, K, D).
select((_, _, _, R), K, D):- select(R, K, D).



I then try the following goal:

insert(void, 1, (1,5), Tree1), insert(Tree1, 8, (8,14), Tree2),
select(Tree2, X, D), writeln(X), writeln(D).

This gives output:

Tree1 = 1, (1, 5), void, void
Tree2 = 1, (1, 5), void, 8, (8, 14), void, void
X = 1
D = 1, 5
Yes (0.00s cpu, solution 1, maybe more)
No (0.02s cpu)


Basically I inserted 2 nodes, one with a key value of 1 and a data
value of an interval of [1..5], and a second node with key 8 and an
interval of [8..14].  If I was trying to search for all intervals that
intersect with the range [0..20] I am having a very hard time figuring
out how to do this with prolog code.  Any ideas?

-Tim