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 namespace Gecode { namespace Int {
35 
36   /*
37    * Value sets
38    *
39    */
40   forceinline
ValSet(void)41   ValSet::ValSet(void)
42     : fst(nullptr), lst(nullptr), n(0) {}
43 
44   forceinline void
add(Space & home,int v)45   ValSet::add(Space& home, int v) {
46     RangeList*  c = fst;
47     RangeList** p = &fst;
48     while (c != nullptr) {
49       if (v < c->min()) {
50         if (v+1 == c->min()) {
51           c->min(v); n++;
52           return;
53         } else {
54           *p = new (home) RangeList(v,v,c); n++;
55           return;
56         }
57       } else if (v <= c->max()) {
58         // Value already included
59         return;
60       } else if (v == c->max()+1) {
61         if ((c->next() != nullptr) && (v+1 == c->next()->min())) {
62           c->next()->min(c->min());
63           *p = c->next();
64           c->dispose(home,c);
65         } else {
66           c->max(v);
67         }
68         n++;
69         return;
70       } else {
71         p = c->nextRef();
72         c = *p;
73       }
74     }
75     *p = new (home) RangeList(v,v,nullptr); n++;
76     lst = *p;
77   }
78 
79   forceinline int
size(void) const80   ValSet::size(void) const {
81     return n;
82   }
83 
84   forceinline bool
empty(void) const85   ValSet::empty(void) const {
86     return n == 0;
87   }
88 
89   forceinline int
min(void) const90   ValSet::min(void) const {
91     return fst->min();
92   }
93 
94   forceinline int
max(void) const95   ValSet::max(void) const {
96     return lst->max();
97   }
98 
99   forceinline void
update(Space & home,ValSet & vs)100   ValSet::update(Space& home, ValSet& vs) {
101     if (vs.n > 0) {
102       n = vs.n;
103       // Count number of ranges
104       int m = 0;
105       for (RangeList* c = vs.fst; c != nullptr; c = c->next())
106         m++;
107       fst = home.alloc<RangeList>(m);
108       lst = fst + (m-1);
109       int i=0;
110       for (RangeList* c = vs.fst; c != nullptr; c = c->next()) {
111         fst[i].min(c->min()); fst[i].max(c->max());
112         fst[i].next(fst+i+1);
113         i++;
114       }
115       lst->next(nullptr);
116     }
117   }
118 
119   forceinline void
flush(void)120   ValSet::flush(void) {
121     fst = lst = nullptr;
122   }
123 
124   forceinline void
dispose(Space & home)125   ValSet::dispose(Space& home) {
126     if (fst != nullptr)
127       fst->dispose(home,lst);
128   }
129 
130   forceinline
Ranges(const ValSet & vs)131   ValSet::Ranges::Ranges(const ValSet& vs)
132     : c(vs.fst) {}
133 
134   forceinline bool
operator ()(void) const135   ValSet::Ranges::operator ()(void) const {
136     return c != nullptr;
137   }
138 
139   forceinline void
operator ++(void)140   ValSet::Ranges::operator ++(void) {
141     c = c->next();
142   }
143 
144   forceinline int
min(void) const145   ValSet::Ranges::min(void) const {
146     return c->min();
147   }
148   forceinline int
max(void) const149   ValSet::Ranges::max(void) const {
150     return c->max();
151   }
152 
153   forceinline unsigned int
width(void) const154   ValSet::Ranges::width(void) const {
155     return c->width();
156   }
157 
158   template<class View>
159   forceinline Iter::Ranges::CompareStatus
compare(View x) const160   ValSet::compare(View x) const {
161     if (empty() || (x.max() < min()) || (x.min() > max()))
162       return Iter::Ranges::CS_DISJOINT;
163     ValSet::Ranges vsr(*this);
164     ViewRanges<View> xr(x);
165     return Iter::Ranges::compare(xr,vsr);
166   }
167 
168   template<class View>
169   forceinline bool
subset(View x) const170   ValSet::subset(View x) const {
171     if (empty() || (x.min() < min()) || (x.max() > max()))
172       return false;
173     ValSet::Ranges vsr(*this);
174     ViewRanges<View> xr(x);
175     return Iter::Ranges::subset(xr,vsr);
176   }
177 
178 }}
179 
180 // STATISTICS: int-other
181