[gecode-users] IntSet question

[Guido Tack]

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/