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, 2011
8  *
9  *  This file is part of Gecode, the generic constraint
10  *  development environment:
11  *     http://www.gecode.org
12  *
13  *  Permission is hereby granted, free of charge, to any person obtaining
14  *  a copy of this software and associated documentation files (the
15  *  "Software"), to deal in the Software without restriction, including
16  *  without limitation the rights to use, copy, modify, merge, publish,
17  *  distribute, sublicense, and/or sell copies of the Software, and to
18  *  permit persons to whom the Software is furnished to do so, subject to
19  *  the following conditions:
20  *
21  *  The above copyright notice and this permission notice shall be
22  *  included in all copies or substantial portions of the Software.
23  *
24  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/int/bool.hh>
35 
36 namespace Gecode { namespace Int { namespace NValues {
37 
38   template<class VY>
39   forceinline
LqBool(Home home,int status,ViewArray<BoolView> & x,VY y)40   LqBool<VY>::LqBool(Home home, int status, ViewArray<BoolView>& x, VY y)
41     : BoolBase<VY>(home,status,x,y) {}
42 
43   template<class VY>
44   forceinline
LqBool(Space & home,LqBool<VY> & p)45   LqBool<VY>::LqBool(Space& home, LqBool<VY>& p)
46     : BoolBase<VY>(home,p) {}
47 
48   template<class VY>
49   Actor*
copy(Space & home)50   LqBool<VY>::copy(Space& home) {
51     return new (home) LqBool<VY>(home,*this);
52   }
53 
54   template<class VY>
55   inline ExecStatus
post(Home home,ViewArray<BoolView> & x,VY y)56   LqBool<VY>::post(Home home, ViewArray<BoolView>& x, VY y) {
57     if (x.size() == 0) {
58       GECODE_ME_CHECK(y.gq(home,0));
59       return ES_OK;
60     }
61 
62     x.unique();
63 
64     GECODE_ME_CHECK(y.gq(home,1));
65 
66     if (x.size() == 1)
67       return ES_OK;
68 
69     if (y.max() == 1) {
70       assert(y.assigned());
71       ViewArray<BoolView> xc(home,x);
72       return Bool::NaryEq<BoolView>::post(home,xc);
73     }
74 
75     if (y.min() >= 2)
76       return ES_OK;
77 
78     int n = x.size();
79     int status = 0;
80     for (int i=n; i--; )
81       if (x[i].zero()) {
82         if (status & VS_ONE) {
83           GECODE_ME_CHECK(y.gq(home,2));
84           return ES_OK;
85         }
86         x[i] = x[--n];
87         status |= VS_ZERO;
88       } else if (x[i].one()) {
89         if (status & VS_ZERO) {
90           GECODE_ME_CHECK(y.gq(home,2));
91           return ES_OK;
92         }
93         x[i] = x[--n];
94         status |= VS_ONE;
95       }
96 
97     assert(status != (VS_ZERO | VS_ONE));
98     if (n == 0) {
99       assert((status != 0) && (y.min() >= 1));
100       return ES_OK;
101     }
102 
103     x.size(n);
104 
105     (void) new (home) LqBool<VY>(home,status,x,y);
106     return ES_OK;
107   }
108 
109   template<class VY>
110   ExecStatus
propagate(Space & home,const ModEventDelta &)111   LqBool<VY>::propagate(Space& home, const ModEventDelta&) {
112     if (status == (VS_ZERO | VS_ONE)) {
113       GECODE_ME_CHECK(y.gq(home,2));
114       return home.ES_SUBSUMED(*this);
115     }
116 
117     if (c.empty()) {
118       assert((status != 0) && (y.min() >= 1));
119       return home.ES_SUBSUMED(*this);
120     }
121 
122     if (y.max() == 1) {
123       if (status == VS_ZERO) {
124         // Mark that everything is done
125         status = VS_ZERO | VS_ONE;
126         for (Advisors<ViewAdvisor<BoolView> > as(c); as(); ++as)
127           GECODE_ME_CHECK(as.advisor().view().zero(home));
128         return home.ES_SUBSUMED(*this);
129       }
130       if (status == VS_ONE) {
131         // Mark that everything is done
132         status = VS_ZERO | VS_ONE;
133         for (Advisors<ViewAdvisor<BoolView> > as(c); as(); ++as)
134           GECODE_ME_CHECK(as.advisor().view().one(home));
135         return home.ES_SUBSUMED(*this);
136       }
137     }
138 
139     if (y.min() == 2)
140       return home.ES_SUBSUMED(*this);
141 
142     return ES_FIX;
143   }
144 
145 }}}
146 
147 // STATISTICS: int-prop
148