Generated on Wed Jan 4 17:49:14 2006 for Gecode by doxygen 1.4.6

common.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Gabor Szokoli <szokoli@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Guido Tack, 2004
00011  *     Christian Schulte, 2004
00012  *     Gabor Szokoli, 2004
00013  *
00014  *  Last modified:
00015  *     $Date: 2005-11-08 11:52:21 +0100 (Tue, 08 Nov 2005) $ by $Author: tack $
00016  *     $Revision: 2521 $
00017  *
00018  *  This file is part of Gecode, the generic constraint
00019  *  development environment:
00020  *     http://www.gecode.org
00021  *
00022  *  See the file "LICENSE" for information on usage and
00023  *  redistribution of this file, and for a
00024  *     DISCLAIMER OF ALL WARRANTIES.
00025  *
00026  */
00027 
00028 namespace Gecode { namespace Set { namespace Sequence {
00029 
00030   forceinline
00031   ExecStatus propagateSeq(Space* home,
00032                  bool& modified, ViewArray<SetView>& x) {
00033 
00034     int lastElem = x.size()-1;
00035     int cur_max = BndSet::MAX_OF_EMPTY;
00036     int cur_min = BndSet::MIN_OF_EMPTY;
00037 
00038     for (int i=0; i<lastElem; i++) {
00039       if (x[i].glbSize() > 0) {
00040         int glbMax = x[i].glbMax();
00041         cur_max = std::max(cur_max, glbMax);
00042       }
00043       if (cur_max>=Limits::Set::int_min)
00044         GECODE_ME_CHECK_B(modified,
00045                           x[i+1].exclude(home, Limits::Set::int_min, cur_max));
00046 
00047       if (x[lastElem-i].lubSize() > 0) {
00048         int glbMin = x[lastElem-i].glbMin();
00049         cur_min = std::min(cur_min, glbMin);
00050       }
00051       if (Limits::Set::int_max>=cur_min)
00052         GECODE_ME_CHECK_B(modified,
00053                           x[lastElem-i-1].exclude(home, cur_min,
00054                                                   Limits::Set::int_max));
00055     }
00056     return ES_FIX;
00057   }
00058 
00059   forceinline
00060   ExecStatus propagateSeqUnion(Space* home,
00061                       bool& modified, ViewArray<SetView>& x, SetView& y) {
00062 
00063     GECODE_AUTOARRAY(GlbRanges<SetView>, XLBs,x.size());
00064     for (int i=x.size(); i--; ){
00065       GlbRanges<SetView> lb(x[i]);
00066       XLBs[i]=lb;
00067     }
00068     Iter::Ranges::NaryAppend<GlbRanges<SetView> > u(XLBs,x.size());
00069     GECODE_ME_CHECK_B(modified, y.includeI(home,u));
00070     return ES_FIX;
00071   }
00072 
00073   /* TODO:
00074    * This functionality is needed by the sequenced union propagator to be
00075    * able to eliminate determined variables from its variable vector without
00076    * reordering the remaining variables.
00077    * Proof of concept implementation here,
00078    * let's see if it makes it into a method in the array class.
00079    * (as a more optimised version of course, I'm trying to break the abstraction
00080    * as little as possible here.)
00081    */
00082 
00083   forceinline void eliminateFromArrayPreservingOrder(ViewArray<SetView>& x,
00084                                                      unsigned int n) {
00085     assert(n < (unsigned int)x.size());
00086     SetView temp = x[n];
00087     for (int i=n; i < x.size()-1;i++) {
00088       x[i]=x[i+1];
00089     }
00090     x[x.size()-1] = temp;
00091     x.move_lst(x.size()-1);
00092   }
00093 
00094 }}}
00095 
00096 // STATISTICS: set-prop