Generated on Sat Feb 7 2015 02:01:26 for Gecode by doxygen 1.8.9.1
unshare.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2007
8  *
9  * Last modified:
10  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13068 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/int/rel.hh>
39 #include <gecode/int/bool.hh>
40 
46 namespace Gecode {
47 
48  namespace Int { namespace Unshare {
49 
51  template<class Var>
52  class VarPtrLess {
53  public:
54  forceinline bool
55  operator ()(const Var* a, const Var* b) {
56  return a->before(*b);
57  }
58  };
59 
60 
63  link(Home home, IntVar** x, int n, IntConLevel icl) {
64  if (n > 2) {
65  ViewArray<IntView> y(home,n);
66  y[0]=*x[0];
67  for (int i=1; i<n; i++)
68  y[i]=*x[i]=IntVar(home,x[0]->min(),x[0]->max());
69  if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
71  } else {
73  }
74  } else if (n == 2) {
75  *x[1]=IntVar(home,x[0]->min(),x[0]->max());
76  if ((icl == ICL_DOM) || (icl == ICL_DEF)) {
78  (home,*x[0],*x[1])));
79  } else {
81  (home,*x[0],*x[1])));
82  }
83  }
84  return ES_OK;
85  }
86 
89  link(Home home, BoolVar** x, int n, IntConLevel) {
90  if (n > 2) {
91  ViewArray<BoolView> y(home,n);
92  y[0]=*x[0];
93  for (int i=1; i<n; i++)
94  y[i]=*x[i]=BoolVar(home,0,1);
96  } else if (n == 2) {
97  *x[1] = BoolVar(home,0,1);
99  }
100  return ES_OK;
101  }
102 
104  template<class Var>
107  int n=x.size();
108  if (n < 2)
109  return ES_OK;
110 
111  Region r(home);
112  Var** y = r.alloc<Var*>(n);
113  for (int i=n; i--; )
114  y[i]=&x[i];
115 
116  VarPtrLess<Var> vpl;
117  Support::quicksort<Var*,VarPtrLess<Var> >(y,n,vpl);
118 
119  // Replace all shared variables with new and equal variables
120  for (int i=0; i<n;) {
121  int j=i++;
122  while ((i<n) && y[j]->same(*y[i]))
123  i++;
124  if (!y[j]->assigned())
125  link(home,&y[j],i-j,icl);
126  }
127  return ES_OK;
128  }
129 
130  }}
131 
132  void
134  if (home.failed()) return;
135  GECODE_ES_FAIL(Int::Unshare::unshare<IntVar>(home,x,icl));
136  }
137 
138  void
140  if (home.failed()) return;
141  GECODE_ES_FAIL(Int::Unshare::unshare<BoolVar>(home,x,ICL_DEF));
142  }
143 
144 }
145 
146 // STATISTICS: int-post
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3446
IntConLevel
Consistency levels for integer propagators.
Definition: int.hh:937
Binary domain consistent equality propagator.
Definition: rel.hh:71
int size(void) const
Return size of array (number of elements)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
Handle to region.
Definition: region.hpp:61
n-ary domain consistent equality propagator
Definition: rel.hh:138
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
ExecStatus link(Home home, IntVar **x, int n, IntConLevel icl)
Return a fresh yet equal integer variable.
Definition: unshare.cpp:63
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
n-ary Boolean equality propagator
Definition: bool.hh:133
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Binary bounds consistent equality propagator.
Definition: rel.hh:107
void unshare(Home home, IntVarArgs &x, IntConLevel icl)
Replace multiple variable occurences in x by fresh variables.
Definition: unshare.cpp:133
Boolean equality propagator.
Definition: bool.hh:105
Passing integer variables.
Definition: int.hh:636
ExecStatus unshare(Home home, VarArgArray< Var > &x, IntConLevel icl)
Replace unassigned shared variables by fresh, yet equal variables.
Definition: unshare.cpp:106
Passing Boolean variables.
Definition: int.hh:690
Boolean integer variables.
Definition: int.hh:491
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Base class for variables.
Definition: var.hpp:44
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Sort order for variables.
Definition: unshare.cpp:52
ExecStatus
Definition: core.hpp:523
Integer variables.
Definition: int.hh:350
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
The default consistency for a constraint.
Definition: int.hh:941
Execution is okay.
Definition: core.hpp:527
n-ary bounds consistent equality propagator
Definition: rel.hh:170
Gecode toplevel namespace
Argument array for variables.
Definition: array.hpp:53
Home class for posting propagators
Definition: core.hpp:717
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:96
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
bool operator()(const Var *a, const Var *b)
Definition: unshare.cpp:55
Domain propagation or consistency.
Definition: int.hh:940