[gecode-users] Iterating/filtering IntView in Gecode 3.x

[Martin Mann]

Hi Peter,

I solved that problem for Gecode 1.3.0 (still running for 3.*) by a 
dedicated implementation of a Gecode RangeIterator for a std::set 
(source attached). The source code can be easily adapted for your 
purpose either by sorting the std::vector after filling or by ensuring 
that you fill it with values of increasing order.

Dont know if there is a "native" Gecode support in 3.*, havent checked 
since I wrote it. :)

the application is than quite simple:

////////////////////////////////////////////////////
   std::set<int> data; // fill data
   GC_StlSetRangeIterator dataIt(&data);
   x.inter_r(*home, dataIt);
////////////////////////////////////////////////////

Hope it helps,

Martin



Peter Vanhee schrieb:
> Hey all,
> 
> I have more or less the same problem as mentioned here: http://thread.gmane.org/gmane.comp.lib.gecode.user/919,
> however the solution seems to be outdated for gecode 3.x: e.g. GECODE_AUTOARRAY is not existing anymore etc.
> 
> Within the binary propagator, and when one variable is assigned (x0), I need to filter values in the other variable (x1). 
> What I do right  now is:
> 
> // loop over all values of x1 and push to remove if necessary
> vector<int> remove;
> for (IntVarValues i(*x1); i(); ++i) {
> 	if (!predicate(home, x0->val(), i.val())) remove.push_back(i.val());
> }
> 
> // remove values from domain
> for(vector<int>::iterator i=remove.begin(); i!=remove.end(); ++i) {
> 	GECODE_ME_CHECK(x1->nq(_home, r));
> }
> 
> 
> This is not at all efficient:  90% of the time is spent in Int::IntVarImp::nq_full, and 38% in Int::IntVarImp::RangeList::min().
> How can I change this? 
> 
> I have variables with big domains (into the millions of values) that have few continuous ranges.
> 
> Thanks,
> Peter

-- 
Martin Mann, Dipl. Bioinf.
Bioinformatics - Inst. of Computer Science
Albert-Ludwigs-University Freiburg
Tel: ++49-761-203-8259
Fax: ++49-761-203-7462
http://www.bioinf.uni-freiburg.de/~mmann/
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: GC_StlSetRangeIterator.hh
URL: <http://www.gecode.org/pipermail/users/attachments/20100319/25734037/attachment.asc>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: GC_StlSetRangeIterator.cc
URL: <http://www.gecode.org/pipermail/users/attachments/20100319/25734037/attachment.txt>