Gustavo Gutierrez wrote:
> Probably what I am going to ask is not useful or is just to much particular
> to my case that does not worth have it, however, I wouldn't hesitate to ask
> :).
>
> While writing a propagator I realized that keeping some state in it will
> lower the complexity. This propagator is on a finite set variable and what I
> does is to track "the new elements in the glb" and propagate according with
> its semantics. At the beginning to I was using an std::set to keep the "old
> values" and using it to compute the new elements:
>
> new elements = current glb \ old values
>
> The propagator was performing well but the memory consumption and the time to
> compute the intersection was quite high. After realizing that I start using
> an IntSet instead of a std::set to keep the data. The advantage is that the
> IntSet stores ranges and then is *hopefully* less memory hungry. There is
> also something nice, you can use all the iterators with them (range
> iterators). The only problem is that they are intended to be used only to
> represent variable domains in initializations or when posting constraints and
> this is reflected in the fact that they lack of "modification operations" in
> the API.
>
> In my case I have to copy construct all the time and this is of course time
> consuming but far better than my previous implementation. Now my question,
> sounds it very crazy or stupid to use the IntSet in this way?, if it does
> not, then it would be nice to provide an specialization (via inheritance, for
> instance) that allows this kind of use. What do you think?
Yes, that is very crazy :-) However, there's a different data structure you
can use in exactly the way you describe. It's actually two data structures,
LUBndSet and GLBndSet. The difference is in the available operations: LUBndSet
has intersectI and excludeI operations (i.e., it can shrink), and GLBndSet has
an includeI operation (i.e., it can grow). These sets are used internally for
implementing set variables. In your case, you'd use a GLBndSet (and includeI
the current lower bound after each propagation). There's an iterator called
BndSetRanges that you can use on these sets.
You should have a look at the IntersectionN propagator, it uses a LUBndSet to
remember the intersection of all assigned variables it has seen so far (it will
show you how to initialize and copy these sets).
Cheers,
Guido
--
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
