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

[Peter Vanhee]

Thanks Martin, 

this is very helpful.

I modified my code to use std::set as well with your range iterator, and I have a huge speed increase.
Note that I used narrow_r instead of inter_r.

Thanks!
Peter

On 19 Mar 2010, at 15:58, Martin Mann wrote:

> 
> 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/
> /*
> *  Main authors:
> *     Martin Mann http://www.bioinf.uni-freiburg.de/~mmann/
> *
> *  Contributing authors:
> *     Sebastian Will http://www.bioinf.uni-freiburg.de/~will/
> *
> *  Copyright:
> *     Martin Mann, 2007
> *
> *  This file is part of the CPSP-tools package:
> *     http://www.bioinf.uni-freiburg.de/sw/cpsp/
> *
> *  See the file "LICENSE" for information on usage and
> *  redistribution of this file, and for a
> *     DISCLAIMER OF ALL WARRANTIES.
> *
> */
> 
> #ifndef GC_STLSETRANGEITERATOR_HH_
> #define GC_STLSETRANGEITERATOR_HH_
> 
> 
> #include <set>
> #include <iostream>
> 	
>  		/**
>  		 * Provides a constant Gecode RangeIterator of a std::set<int> that 
>  		 * calculates the ranges on demand.
>  		 */
> 	class GC_StlSetRangeIterator
> 	{
> 	private:
> 		const std::set<int>* data;
> 		std::set<int>::const_iterator actElem;
> 		
> 		bool noFurtherRange;
> 		
> 		int nextMin, nextMax;
> 		
> 			//! searchs for the next range and sets the inner members
> 		void getNextRange();
> 	public:
> 		GC_StlSetRangeIterator();
> 		GC_StlSetRangeIterator(const std::set<int>* data_);
> 		virtual ~GC_StlSetRangeIterator();
> 		
> 		void init(const std::set<int>* const data_) {
> 			data = data_;
> 			noFurtherRange = false;
> 			if (data != NULL) 
> 				actElem = data->begin();
> 			getNextRange();
> 		}
> 		
> 		bool operator()(void) const { return !noFurtherRange; }
> 		void operator++(void) { getNextRange(); }
> 		
> 		int min(void) const { return nextMin; }
> 		int max(void) const { return nextMax; }
> 		unsigned int width(void) { return nextMax-nextMin+1; }
> 		
> 		
> 	};
> 	
> 
> #endif /*GC_STLSETRANGEITERATOR_HH_*/
> /*
> *  Main authors:
> *     Martin Mann http://www.bioinf.uni-freiburg.de/~mmann/
> *
> *  Contributing authors:
> *     Sebastian Will http://www.bioinf.uni-freiburg.de/~will/
> *
> *  Copyright:
> *     Martin Mann, 2007
> *
> *  This file is part of the CPSP-tools package:
> *     http://www.bioinf.uni-freiburg.de/sw/cpsp/
> *
> *  See the file "LICENSE" for information on usage and
> *  redistribution of this file, and for a
> *     DISCLAIMER OF ALL WARRANTIES.
> *
> */
> 
> #include "cpsp/GC_StlSetRangeIterator.hh"
> 
>  	
>  	GC_StlSetRangeIterator::GC_StlSetRangeIterator() :
>  		data(NULL), noFurtherRange(true)
>  	{
>  		getNextRange();
>  	}
>  		
> 	GC_StlSetRangeIterator::GC_StlSetRangeIterator(const std::set<int>* data_) :
> 		data(data_), noFurtherRange(false)
> 	{
> 		if (data != NULL) 
> 			actElem = data->begin();
> 		getNextRange();
> 	}
> 	
> 	GC_StlSetRangeIterator::~GC_StlSetRangeIterator()
> 	{
> 	}
> 	
> 	void
> 	GC_StlSetRangeIterator::getNextRange() {
> 		if (data==NULL || actElem == data->end()) {
> 			noFurtherRange = true;
> 			return;
> 		}
> 			// find next range
> 		nextMin = *actElem;
> 		nextMax = nextMin;
> 			// build up new upper bound until end of set reached or gap in 
> 			// sequence
> 		while ( (++actElem != data->end()) && (*actElem == (nextMax+1))) {
> 			nextMax++;
> 		}
> 	}
>