view.icc

00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2005
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-08-24 11:25:05 +0200 (Thu, 24 Aug 2006) $ by $Author: schulte $
00010  *     $Revision: 3559 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include <iostream>
00023 
00024 namespace Gecode {
00025 
00030   class ConstantViewBase {
00031   public:
00033 
00034 
00035     bool modified(void) const;
00037     unsigned int degree(void) const;
00039     static bool varderived(void);
00041     VarBase* variable(void) const;
00043   private:
00044     static void* operator new(size_t);
00045     static void operator delete(void*);
00046   };
00047 
00048 
00049 
00054   template <class Var>
00055   class VariableViewBase {
00056   protected:
00058     Var* var;
00060     VariableViewBase(void);
00062     VariableViewBase(Var* x);
00063 
00064   public:
00066 
00067 
00068     static bool varderived(void);
00070     Var* variable(void) const;
00072     bool modified(void) const;
00074     unsigned int degree(void) const;
00076 
00078 
00079 
00080     static ModEvent     pme(const Propagator* p);
00082     static PropModEvent pme(ModEvent me);
00084     static ModEvent     combine(ModEvent me1, ModEvent me2);
00086 
00088 
00089 
00096     void subscribe(Space*, Propagator* p, PropCond pc, bool process=true);
00098     void cancel(Space* home, Propagator* p, PropCond pc);
00100   private:
00101     static void* operator new(size_t);
00102     static void operator delete(void*);
00103   };
00104 
00109 
00110   template <class Var>
00111   bool same(const VariableViewBase<Var>& x, const VariableViewBase<Var>& y);
00113   template <class Var>
00114   bool before(const VariableViewBase<Var>& x, const VariableViewBase<Var>& y);
00116 
00117 
00118 
00128   template <class View>
00129   class ViewVarTraits {};
00130 
00135   template <class View>
00136   class DerivedViewBase {
00137   protected:
00139     View view;
00141     DerivedViewBase(void);
00143     DerivedViewBase(const View& x);
00144 
00145   public:
00147     typedef typename ViewVarTraits<View>::Var Var;
00148 
00150 
00151 
00152     static bool varderived(void);
00154     Var* variable(void) const;
00156     View base(void) const;
00158     bool modified(void) const;
00160     unsigned int degree(void) const;
00162 
00163   private:
00164     static void* operator new(size_t);
00165     static void operator delete(void*);
00166   };
00167 
00168 
00173   bool shared(const ConstantViewBase&, const ConstantViewBase&);
00178   template <class Var>
00179   bool shared(const VariableViewBase<Var>&, const ConstantViewBase&);
00184   template <class ViewA>
00185   bool shared(const DerivedViewBase<ViewA>&, const ConstantViewBase&);
00190   template <class Var>
00191   bool shared(const ConstantViewBase&, const VariableViewBase<Var>&);
00196   template <class ViewA>
00197   bool shared(const ConstantViewBase&, const DerivedViewBase<ViewA>&);
00202   template <class VarA, class VarB>
00203   bool shared(const VariableViewBase<VarA>&,
00204               const VariableViewBase<VarB>&);
00209   template <class VarA, class ViewB>
00210   bool shared(const VariableViewBase<VarA>&,
00211               const DerivedViewBase<ViewB>&);
00216   template <class ViewA, class VarB>
00217   bool shared(const DerivedViewBase<ViewA>&,
00218               const VariableViewBase<VarB>&);
00223   template <class ViewA, class ViewB>
00224   bool shared(const DerivedViewBase<ViewA>&,
00225               const DerivedViewBase<ViewB>&);
00226 
00227 
00236   template <class View, unsigned int n>
00237   class ViewTuple {
00238   private:
00240     View x[n];
00241   public:
00243 
00244 
00245     ViewTuple(void);
00247 
00249 
00250 
00251     View& operator[](unsigned int i);
00253     const View& operator[](unsigned int i) const;
00255 
00257 
00258 
00265     void subscribe(Space*, Propagator* p, PropCond pc, bool process=true);
00267     void cancel(Space* home, Propagator* p, PropCond pc);
00269 
00271 
00272 
00273     void update(Space* home, bool share, ViewTuple& xs);
00275 
00276   private:
00277     static void* operator new(size_t);
00278     static void operator delete(void*);
00279   };
00280 
00286 
00287   template <class View, unsigned int n>
00288   bool same(const ViewTuple<View,n>& x, const ViewTuple<View,n>& y);
00290   template <class View, unsigned int n>
00291   bool before(const ViewTuple<View,n>& x, const ViewTuple<View,n>& y);
00293 
00294 }
00295 
00300 template <class View, unsigned int n>
00301 std::ostream&
00302 operator<<(std::ostream& os, const Gecode::ViewTuple<View,n>& xy);
00303 
00304 
00305 namespace Gecode {
00306 
00307   /*
00308    * Constant view: has no variable implementation
00309    *
00310    */
00311   forceinline bool
00312   ConstantViewBase::modified(void) const {
00313     return true;
00314   }
00315   forceinline unsigned int
00316   ConstantViewBase::degree(void) const {
00317     return 0;
00318   }
00319   forceinline bool
00320   ConstantViewBase::varderived(void) {
00321     return false;
00322   }
00323   forceinline VarBase*
00324   ConstantViewBase::variable(void) const {
00325     return NULL;
00326   }
00327 
00328 
00329   /*
00330    * Variable view: contains a pointer to a variable implementation
00331    *
00332    */
00333   template <class Var>
00334   forceinline
00335   VariableViewBase<Var>::VariableViewBase(void) {}
00336   template <class Var>
00337   forceinline
00338   VariableViewBase<Var>::VariableViewBase(Var* x)
00339     : var(x) {}
00340   template <class Var>
00341   forceinline bool
00342   VariableViewBase<Var>::varderived(void) {
00343     return true;
00344   }
00345   template <class Var>
00346   forceinline Var*
00347   VariableViewBase<Var>::variable(void) const {
00348     return var;
00349   }
00350   template <class Var>
00351   forceinline bool
00352   VariableViewBase<Var>::modified(void) const {
00353     return var->modified();
00354   }
00355   template <class Var>
00356   forceinline unsigned int
00357   VariableViewBase<Var>::degree(void) const {
00358     return var->degree();
00359   }
00360   template <class Var>
00361   forceinline void
00362   VariableViewBase<Var>::subscribe(Space* home, Propagator* p, PropCond pc,
00363                                    bool process) {
00364     var->subscribe(home,p,pc,process);
00365   }
00366   template <class Var>
00367   forceinline void
00368   VariableViewBase<Var>::cancel(Space* home, Propagator* p, PropCond pc) {
00369     var->cancel(home,p,pc);
00370   }
00371   template <class Var>
00372   forceinline ModEvent
00373   VariableViewBase<Var>::pme(const Propagator* p) {
00374     return Var::pme(p);
00375   }
00376   template <class Var>
00377   forceinline PropModEvent
00378   VariableViewBase<Var>::pme(ModEvent me) {
00379     return Var::pme(me);
00380   }
00381   template <class Var>
00382   forceinline ModEvent
00383   VariableViewBase<Var>::combine(ModEvent me1, ModEvent me2) {
00384     return Var::combine(me1,me2);
00385   }
00386 
00387   template <class Var>
00388   forceinline bool
00389   same(const VariableViewBase<Var>& x, const VariableViewBase<Var>& y) {
00390     return x.variable() == y.variable();
00391   }
00392   template <class Var>
00393   forceinline bool
00394   before(const VariableViewBase<Var>& x, const VariableViewBase<Var>& y) {
00395     return x.variable() < y.variable();
00396   }
00397 
00398   /*
00399    * Derived view: contain the base view from which they are derived
00400    *
00401    */
00402 
00403   template <class View>
00404   forceinline
00405   DerivedViewBase<View>::DerivedViewBase(void) {}
00406 
00407   template <class View>
00408   forceinline
00409   DerivedViewBase<View>::DerivedViewBase(const View& x)
00410     : view(x) {}
00411 
00412   template <class View>
00413   forceinline bool
00414   DerivedViewBase<View>::varderived(void) {
00415     return View::varderived();
00416   }
00417 
00418   template <class View>
00419   forceinline typename ViewVarTraits<View>::Var*
00420   DerivedViewBase<View>::variable(void) const {
00421     return view.variable();
00422   }
00423 
00424   template <class View>
00425   forceinline View
00426   DerivedViewBase<View>::base(void) const {
00427     return view;
00428   }
00429 
00430   template <class View>
00431   forceinline bool
00432   DerivedViewBase<View>::modified(void) const {
00433     return view.modified();
00434   }
00435 
00436   template <class View>
00437   forceinline unsigned int
00438   DerivedViewBase<View>::degree(void) const {
00439     return view.degree();
00440   }
00441 
00442 
00443   /*
00444    * Testing whether two views share the same variable
00445    *
00446    */
00447 
00448   forceinline bool
00449   shared(const ConstantViewBase&, const ConstantViewBase&) {
00450     return false;
00451   }
00452 
00453   template <class Var>
00454   forceinline bool
00455   shared(const VariableViewBase<Var>&, const ConstantViewBase&) {
00456     return false;
00457   }
00458 
00459   template <class View>
00460   forceinline bool
00461   shared(const DerivedViewBase<View>&, const ConstantViewBase&) {
00462     return false;
00463   }
00464 
00465   template <class Var>
00466   forceinline bool
00467   shared(const ConstantViewBase&, const VariableViewBase<Var>&) {
00468     return false;
00469   }
00470 
00471   template <class View>
00472   forceinline bool
00473   shared(const ConstantViewBase&, const DerivedViewBase<View>&) {
00474     return false;
00475   }
00476 
00477   template <class VarA, class VarB>
00478   forceinline bool
00479   shared(const VariableViewBase<VarA>& x,
00480          const VariableViewBase<VarB>& y) {
00481     return (static_cast<VarBase*>(x.variable()) ==
00482             static_cast<VarBase*>(y.variable()));
00483   }
00484   template <class VarA, class ViewB>
00485   forceinline bool
00486   shared(const VariableViewBase<VarA>& x,
00487          const DerivedViewBase<ViewB>& y) {
00488     return (ViewB::varderived() &&
00489             static_cast<VarBase*>(x.variable()) ==
00490             static_cast<VarBase*>(y.variable()));
00491   }
00492   template <class ViewA, class VarB>
00493   forceinline bool
00494   shared(const DerivedViewBase<ViewA>& x,
00495          const VariableViewBase<VarB>& y) {
00496     return (ViewA::varderived() &&
00497             static_cast<VarBase*>(x.variable()) ==
00498             static_cast<VarBase*>(y.variable()));
00499   }
00500   template <class ViewA, class ViewB>
00501   forceinline bool
00502   shared(const DerivedViewBase<ViewA>& x,
00503          const DerivedViewBase<ViewB>& y) {
00504     return (ViewA::varderived() && ViewB::varderived() &&
00505             static_cast<VarBase*>(x.variable()) ==
00506             static_cast<VarBase*>(y.variable()));
00507   }
00508 
00509 
00510   /*
00511    * Tuple of views
00512    *
00513    */
00514   template <class View, unsigned int n>
00515   forceinline
00516   ViewTuple<View,n>::ViewTuple(void) {}
00517 
00518   template <class View, unsigned int n>
00519   forceinline const View&
00520   ViewTuple<View,n>::operator[](unsigned int i) const {
00521     assert((i>=0)&&(i<n));
00522     return x[i];
00523   }
00524   template <class View, unsigned int n>
00525   forceinline View&
00526   ViewTuple<View,n>::operator[](unsigned int i) {
00527     assert((i>=0)&&(i<n));
00528     return x[i];
00529   }
00530 
00531   template <class View, unsigned int n>
00532   forceinline void
00533   ViewTuple<View,n>::subscribe(Space* home, Propagator* p, PropCond pc,
00534                                bool process) {
00535     for (unsigned int i=0; i<n; i++)
00536       x[i].subscribe(home,p,pc,process);
00537   }
00538   template <class View, unsigned int n>
00539   forceinline void
00540   ViewTuple<View,n>::cancel(Space* home, Propagator* p, PropCond pc) {
00541     for (unsigned int i=0; i<n; i++)
00542       x[i].cancel(home,p,pc);
00543   }
00544   template <class View, unsigned int n>
00545   forceinline void
00546   ViewTuple<View,n>::update(Space* home, bool share, ViewTuple& xs) {
00547     for (unsigned int i=0; i<n; i++)
00548       x[i].update(home,share,xs.x[i]);
00549   }
00550 
00551   template <class View, unsigned int n>
00552   forceinline bool
00553   same(const ViewTuple<View,n>& x, const ViewTuple<View,n>& y) {
00554     for (unsigned int i=0; i<n; i++)
00555       if (!same(x[i],y[i]))
00556         return false;
00557     return true;
00558   }
00559   template <class View, unsigned int n>
00560   forceinline bool
00561   before(const ViewTuple<View,n>& x, const ViewTuple<View,n>& y){
00562     for (unsigned int i=0; i<n; i++)
00563       if (before(x[i],y[i])) {
00564         return true;
00565       } else if (before(y[i],x[i])) {
00566         return false;
00567       }
00568     return false;
00569   }
00570 
00571 }
00572 
00573 template <class View, unsigned int n>
00574 inline std::ostream&
00575 operator<<(std::ostream& os, const Gecode::ViewTuple<View,n>& xs) {
00576   os << "[";
00577   for (unsigned int i=0; i<n-1; i++)
00578     os << xs[i] << ",";
00579   return os << xs[n-1] << "]";
00580 }
00581 
00582 
00583 // STATISTICS: kernel-other