Generated on Sat Feb 7 2015 02:01:20 for Gecode by doxygen 1.8.9.1
base.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Mikael Lagerkvist <lagerkvist@gecode.org>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * Mikael Lagerkvist, 2007
11  * Christian Schulte, 2008
12  *
13  * Last modified:
14  * $Date: 2012-07-19 08:53:57 +0200 (Thu, 19 Jul 2012) $ by $Author: tack $
15  * $Revision: 12963 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 namespace Gecode { namespace Int { namespace Extensional {
42  /*
43  * The propagator proper
44  *
45  */
46 
47  template<class View, bool subscribe>
50  const TupleSet& t)
51  : Propagator(home), x(x0), tupleSet(t), last_data(NULL) {
52  if (subscribe)
53  x.subscribe(home, *this, PC_INT_DOM);
54 
55  assert(ts()->finalized());
56 
57  init_last(home, ts()->last, ts()->tuple_data);
58 
59  home.notice(*this,AP_DISPOSE);
60  }
61 
62  template<class View, bool subscribe>
65  : Propagator(home,share,p), last_data(NULL) {
66  x.update(home, share, p.x);
67  tupleSet.update(home, share, p.tupleSet);
68 
69  init_last(home, p.last_data, p.ts()->tuple_data);
70  }
71 
72  template<class View, bool subscribe>
73  forceinline void
75  if (last_data == NULL) {
76  int literals = static_cast<int>(ts()->domsize*x.size());
77  last_data = home.alloc<Tuple*>(literals);
78  for (int i = literals; i--; )
79  last_data[i] = ts()->tuple_data+(source[i]-base);
80  }
81  }
82 
83  template<class View, bool subscribe>
86  return tupleSet.implementation();
87  }
88 
89  template<class View, bool subscribe>
90  PropCost
92  return PropCost::quadratic(PropCost::HI,x.size());
93  }
94 
95 #define GECODE_LAST_TUPLE(l) (*(l))
96 
97  template<class View, bool subscribe>
100  return GECODE_LAST_TUPLE(last_data[(i*ts()->domsize) + n]);
101  }
102 
103  template<class View, bool subscribe>
106  assert(last(i,n) != NULL);
107  assert(last(i,n)[i] == n+ts()->min);
108  int pos = (i*static_cast<int>(ts()->domsize)) + n;
109  ++(last_data[pos]);
110  if (last(i,n)[i] != (n+ts()->min))
111  last_data[pos] = ts()->nullpointer;
112  return last(i,n);
113  }
114 
115 
116  template<class View, bool subscribe>
117  forceinline void
119  unsigned int domsize = ts()->domsize;
120  for (int i = x.size(); i--; ) {
121  dom[i].init(home, domsize);
122  for (ViewValues<View> vv(x[i]); vv(); ++vv)
123  dom[i].set(static_cast<unsigned int>(vv.val()-ts()->min));
124  }
125  }
126 
127  template<class View, bool subscribe>
128  forceinline bool
130  for (int i = x.size(); i--; )
131  if (!dom[i].get(static_cast<unsigned int>(t[i]-ts()->min)))
132  return false;
133  return true;
134  }
135 #undef GECODE_LAST_TUPLE
136  template<class View, bool subscribe>
139  Tuple l = last(i,n);
140  while ((l != NULL) && !valid(l, dom))
141  l = last_next(i,n);
142  return l;
143  }
144 
145 
146  template<class View, bool subscribe>
147  forceinline size_t
149  home.ignore(*this,AP_DISPOSE);
150  (void) Propagator::dispose(home);
151  if (subscribe)
152  x.cancel(home,*this,PC_INT_DOM);
153  // take care of last_data
154  unsigned int literals = ts()->domsize*x.size();
155  home.rfree(last_data, sizeof(Tuple*)*literals);
156  (void) tupleSet.~TupleSet();
157  return sizeof(*this);
158  }
159 
160 }}}
161 
162 // STATISTICS: int-prop
163 
TupleSet tupleSet
Definition of constraint.
Definition: extensional.hh:245
NodeType t
Type of node.
Definition: bool-expr.cpp:234
void init_dom(Space &home, Domain dom)
Initialize domain information.
Definition: base.hpp:118
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4032
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
bool valid(const FloatVal &n)
Return whether float n is a valid number.
Definition: limits.hpp:43
Tuple find_support(Domain dom, int i, int n)
Find support for view at position i and value n.
Definition: base.hpp:138
Actor must always be disposed.
Definition: core.hpp:610
void init_last(Space &home, Tuple **source, Tuple *base)
Initialize last support.
Definition: base.hpp:74
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
Basic bitset support.
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
Base-class for propagators.
Definition: core.hpp:755
Expensive.
Definition: core.hpp:564
Tuple last_next(int i, int n)
Find last support for view at position i and value n.
Definition: base.hpp:105
Tuple last(int i, int n)
Find last support for view at position i and value n.
Definition: base.hpp:99
Value iterator for integer views.
Definition: view.hpp:94
Computation spaces.
Definition: core.hpp:1362
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2397
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
TupleSet::Tuple Tuple
Definition: extensional.hh:227
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: base.hpp:148
ViewArray< View > x
Variables.
Definition: extensional.hh:244
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:74
Tuple ** last_data
Last tuple looked at Access real tuple-set.
Definition: extensional.hh:246
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
void init(A &a, unsigned int s, bool setbits=false)
Initialize for s bits and allocator a (only after default constructor)
bool valid(Tuple t, Domain dom)
Check wether tuple is valid for domain.
Definition: base.hpp:129
Data stored for a Table.
Definition: int.hh:2034
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high quadratic)
Definition: base.hpp:91
View arrays.
Definition: array.hpp:234
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:2849
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Class represeting a set of tuples.
Definition: int.hh:2022
void update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
Definition: core.hpp:2656
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Base(Space &home, bool share, Base< View, subscribe > &p)
Constructor for cloning p.
Definition: base.hpp:64
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.cpp:169
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
#define forceinline
Definition: config.hpp:132
#define GECODE_LAST_TUPLE(l)
Definition: base.hpp:95
TupleSet::TupleSetI * ts(void)
Definition: base.hpp:85
Base for domain consistent extensional propagation
Definition: extensional.hh:242
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition: core.hpp:2363