this repo has no description
dekker.one
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
34namespace Gecode { namespace Int {
35
36 /*
37 * Value sets
38 *
39 */
40 forceinline
41 ValSet::ValSet(void)
42 : fst(nullptr), lst(nullptr), n(0) {}
43
44 forceinline void
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
80 ValSet::size(void) const {
81 return n;
82 }
83
84 forceinline bool
85 ValSet::empty(void) const {
86 return n == 0;
87 }
88
89 forceinline int
90 ValSet::min(void) const {
91 return fst->min();
92 }
93
94 forceinline int
95 ValSet::max(void) const {
96 return lst->max();
97 }
98
99 forceinline void
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
120 ValSet::flush(void) {
121 fst = lst = nullptr;
122 }
123
124 forceinline void
125 ValSet::dispose(Space& home) {
126 if (fst != nullptr)
127 fst->dispose(home,lst);
128 }
129
130 forceinline
131 ValSet::Ranges::Ranges(const ValSet& vs)
132 : c(vs.fst) {}
133
134 forceinline bool
135 ValSet::Ranges::operator ()(void) const {
136 return c != nullptr;
137 }
138
139 forceinline void
140 ValSet::Ranges::operator ++(void) {
141 c = c->next();
142 }
143
144 forceinline int
145 ValSet::Ranges::min(void) const {
146 return c->min();
147 }
148 forceinline int
149 ValSet::Ranges::max(void) const {
150 return c->max();
151 }
152
153 forceinline unsigned int
154 ValSet::Ranges::width(void) const {
155 return c->width();
156 }
157
158 template<class View>
159 forceinline Iter::Ranges::CompareStatus
160 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
170 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