Re: [eclipse-clp-users] How to expand domain of a variable

On Sat, 5 Nov 2011, Sergey Dymchenko wrote:
> interval - the task is just to say Yes or No. An answer to a query
> must be fast (definitely faster than just checking all intervals one
> by one).
>
> Can this problem be solved effectively in ECLiPSe, or it doesn't look
> as a good problem for CLP paradigm?

If you're expanding the domains of variables other than by backtracking,
then what you're doing isn't the CLP paradigm but something else.  I'm not
even sure how expanding domains would be useful in solving this problem;
what was the algorithm you were hoping to implement that made use of that
operation?

This problem could be solved by a standard interval-query data structure
like the "interval tree."  Wikipedia has a rather confusing article by
that name with references to standard textbooks; the texts would be a good
place to start.  It amounts to building a binary tree on the intervals and
then searching it - fairly standard intro data-structures stuff.  You
could certainly implement the data structure in ECLiPSe, but I think you'd
want to do that by basically procedural code written in ECLiPSe; I don't
think trying to express it as a constraint satisfaction problem per se
would be very convenient, though we can argue from theoretical principles
that it necessarily must be *possible*.
-- 
Matthew Skala
Postdoctoral Fellow, University of Manitoba
mskala_at_cs.umanitoba.ca