Generated on Thu Apr 11 13:59:13 2019 for Gecode by doxygen 1.6.3

view-val-graph.hh

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2002
00009  *     Guido Tack, 2004
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #ifndef __GECODE_INT_VIEW_VAL_GRAPH_HH__
00037 #define __GECODE_INT_VIEW_VAL_GRAPH_HH__
00038 
00039 #include <gecode/int.hh>
00040 
00045 namespace Gecode { namespace Int { namespace ViewValGraph {
00046 
00053   template<class T>
00054   class CombPtrFlag {
00055   private:
00057     ptrdiff_t cpf;
00058   public:
00060     CombPtrFlag(T* p1, T* p2);
00062     void init(T* p1, T* p2);
00064     T* ptr(T* p) const;
00066     int is_set(void) const;
00068     void set(void);
00070     void unset(void);
00071   };
00072 
00074   class BiLink {
00075   private:
00077     BiLink* _prev;
00079     BiLink* _next;
00080   public:
00082     BiLink(void);
00084     BiLink* prev(void) const;
00086     BiLink* next(void) const;
00088     void prev(BiLink* l);
00090     void next(BiLink* l);
00092     void add(BiLink* l);
00094     void unlink(void);
00096     void mark(void);
00098     bool marked(void) const;
00100     bool empty(void) const;
00101   };
00102 
00103 
00104   template<class View> class Edge;
00105 
00115   template<class View>
00116   class Node : public BiLink {
00117   public:
00119     Edge<View>* iter;
00121     unsigned int low, min, comp;
00123     Node(void);
00125     Edge<View>* edge_fst(void) const;
00127     Edge<View>* edge_lst(void) const;
00128 
00130     static void* operator new(size_t, Space&);
00132     static void  operator delete(void*, size_t);
00134     static void  operator delete(void*,Space&);
00135   };
00136 
00141   template<class View>
00142   class ValNode : public Node<View> {
00143   protected:
00145     const int      _val;
00147     Edge<View>*    _matching;
00149     ValNode<View>* _next_val;
00150   public:
00152     ValNode(int v);
00154     ValNode(int v, ValNode<View>* n);
00156     int val(void) const;
00158     void matching(Edge<View>* m);
00160     Edge<View>* matching(void) const;
00162     ValNode<View>** next_val_ref(void);
00164     ValNode<View>* next_val(void) const;
00166     void next_val(ValNode<View>* v);
00167   };
00168 
00173   template<class View>
00174   class ViewNode : public Node<View> {
00175   protected:
00177     unsigned int _size;
00179     View        _view;
00181     Edge<View>* _val_edges;
00182   public:
00184     ViewNode(void);
00186     ViewNode(View x);
00188     Edge<View>*  val_edges(void) const;
00190     Edge<View>** val_edges_ref(void);
00192     bool fake(void) const;
00194     View view(void) const;
00196     void update(void);
00198     bool changed(void) const;
00200     bool matched(void) const;
00201   };
00202 
00207   template<class View>
00208   class Edge : public BiLink {
00209   protected:
00211     Edge<View>* _next_edge;
00213     CombPtrFlag<Node<View> > sd;
00214   public:
00216     Edge(ValNode<View>* v, ViewNode<View>* x);
00218     Edge(ValNode<View>* v, ViewNode<View>* x, Edge<View>* n);
00220     Node<View>* dst(Node<View>* s) const;
00221 
00223     ViewNode<View>* view(ValNode<View>* v) const;
00225     ValNode<View>* val(ViewNode<View>* x) const;
00226 
00228     bool used(Node<View>* v) const;
00230     void use(void);
00232     void free(void);
00233 
00235     void revert(Node<View>* d);
00236 
00238     Edge<View>*  next_edge(void) const;
00240     Edge<View>** next_edge_ref(void);
00242     Edge<View>* next(void) const;
00243 
00245     static void* operator new(size_t, Space&);
00247     static void  operator delete(void*, size_t);
00249     static void  operator delete(void*,Space&);
00250   };
00251 
00253   template<class View>
00254   class IterPruneVal {
00255   protected:
00257     ViewNode<View>* x;
00259     Edge<View>* e;
00260   public:
00262 
00263 
00264     IterPruneVal(ViewNode<View>* x);
00266 
00268 
00269 
00270     bool operator ()(void) const;
00272     void operator ++(void);
00274 
00276 
00277 
00278     int val(void) const;
00280   };
00281 
00282 }}}
00283 
00284 #include <gecode/int/view-val-graph/comb-ptr-flag.hpp>
00285 #include <gecode/int/view-val-graph/bi-link.hpp>
00286 #include <gecode/int/view-val-graph/edge.hpp>
00287 #include <gecode/int/view-val-graph/node.hpp>
00288 #include <gecode/int/view-val-graph/iter-prune-val.hpp>
00289 
00290 namespace Gecode { namespace Int { namespace ViewValGraph {
00291 
00293   template<class View>
00294   class Graph {
00295   protected:
00297     ViewNode<View>** view;
00299     ValNode<View>* val;
00301     int n_view;
00303     int n_val;
00305     unsigned int count;
00307     typedef Support::StaticStack<ViewNode<View>*,Region> ViewNodeStack;
00309     void init(Space& home, ViewNode<View>* x);
00311     bool match(ViewNodeStack& m, ViewNode<View>* x);
00313     void scc(void);
00314   public:
00316     Graph(void);
00318     operator bool(void) const;
00320     void purge(void);
00321   };
00322 
00323 }}}
00324 
00325 #include <gecode/int/view-val-graph/graph.hpp>
00326 
00327 #endif
00328 
00329 // STATISTICS: int-prop
00330