[gecode-users] iterating/filtering IntView

[Guido Tack]

Mikael Zayenz Lagerkvist wrote:

> A solution that works efficiently in many cases is to store the values
> to remove on a stack, and then remove them after iteration over the
> view is finished. A cheap simple stack can be obtained using the
> GECODE_AUTOARRAY macro and a counter of the number of values on the
> stack.

The other big advantage of this approach (apart from actually  
working) is that it will give you the right runtime! Removing a  
single value may cost linear time in the size of the domain, so your  
original approach had quadratic runtime. If you collect all values  
that are to be removed, then create an iterator for them, and use the  
iterator to do the actual removal, the overall runtime goes down to  
linear!

Cheers,
	Guido

-- 
Guido Tack
Programming Systems Lab, Saarland University, Germany
http://www.ps.uni-sb.de/~tack



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20070515/ae9478dd/attachment.htm>