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, 2003
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 <sstream>
35
36namespace Gecode {
37
38 /*
39 * Integer sets
40 *
41 */
42 forceinline
43 IntSet::IntSet(void) {}
44
45 /**
46 * \brief Integer set initialization
47 *
48 * Helper class to allow partial specialization of
49 * template member function.
50 *
51 */
52 template<class I>
53 class IntSetInit {
54 public:
55 /// Initialize \a s with iterator \a i
56 static void init(IntSet& s, I& i) {
57 Region reg;
58 Support::DynamicArray<IntSet::Range,Region> d(reg);
59 int n=0;
60 unsigned int size = 0;
61 while (i()) {
62 d[n].min = i.min(); d[n].max = i.max(); size += i.width();
63 ++n; ++i;
64 }
65 if (n > 0) {
66 IntSet::IntSetObject* o = IntSet::IntSetObject::allocate(n);
67 for (int j=0; j<n; j++)
68 o->r[j]=d[j];
69 o->size = size;
70 s.object(o);
71 }
72 }
73 };
74
75 /// Initialize integer set with integer set
76 template<>
77 class IntSetInit<IntSet> {
78 public:
79 static void init(IntSet& s, const IntSet& i) {
80 s.object(i.object());
81 }
82 };
83
84 /// Initialize integer set with iterator
85 template<class I>
86 IntSet::IntSet(I& i) {
87 IntSetInit<I>::init(*this,i);
88 }
89
90 /// Initialize integer set with iterator
91 template<class I>
92 IntSet::IntSet(const I& i) {
93 IntSetInit<I>::init(*this,i);
94 }
95
96 forceinline
97 IntSet::IntSet(const int r[][2], int n) {
98 if (n > 0)
99 init(r,n);
100 }
101
102 forceinline
103 IntSet::IntSet(const int r[], int n) {
104 if (n > 0)
105 init(r,n);
106 }
107
108 /// Initialize with integers from vector \a r
109 template<>
110 inline
111 IntSet::IntSet(const std::vector<int>& r) {
112 int n = static_cast<int>(r.size());
113 if (n > 0) {
114 Region reg;
115 Range* dr = reg.alloc<Range>(n);
116 for (int i=0; i<n; i++)
117 dr[i].min=dr[i].max=r[static_cast<unsigned int>(i)];
118 normalize(&dr[0],n);
119 }
120 }
121
122 /** \brief Initialize with ranges from vector \a r
123 *
124 * The minimum is the first element and the maximum is the
125 * second element.
126 */
127 template<>
128 inline
129 IntSet::IntSet(const std::vector<std::pair<int,int>>& r) {
130 int n = static_cast<int>(r.size());
131 if (n > 0) {
132 Region reg;
133 Range* dr = reg.alloc<Range>(n);
134 int j=0;
135 for (int i=0; i<n; i++)
136 if (r[static_cast<unsigned int>(i)].first <=
137 r[static_cast<unsigned int>(i)].second) {
138 dr[j].min=r[static_cast<unsigned int>(i)].first;
139 dr[j].max=r[static_cast<unsigned int>(i)].second;
140 j++;
141 }
142 normalize(&dr[0],j);
143 }
144 }
145
146 forceinline
147 IntSet::IntSet(int n, int m) {
148 init(n,m);
149 }
150
151 forceinline int
152 IntSet::min(int i) const {
153 assert(object() != nullptr);
154 return static_cast<IntSetObject*>(object())->r[i].min;
155 }
156
157 forceinline int
158 IntSet::max(int i) const {
159 assert(object() != nullptr);
160 return static_cast<IntSetObject*>(object())->r[i].max;
161 }
162
163 forceinline unsigned int
164 IntSet::width(int i) const {
165 assert(object() != nullptr);
166 IntSetObject* o = static_cast<IntSetObject*>(object());
167 return static_cast<unsigned int>(o->r[i].max-o->r[i].min)+1;
168 }
169
170 forceinline int
171 IntSet::ranges(void) const {
172 IntSetObject* o = static_cast<IntSetObject*>(object());
173 return (o == nullptr) ? 0 : o->n;
174 }
175
176 forceinline bool
177 IntSet::in(int n) const {
178 IntSetObject* o = static_cast<IntSetObject*>(object());
179 if ((o == nullptr) || (n < o->r[0].min) || (n > o->r[o->n-1].max))
180 return false;
181 else
182 return o->in(n);
183 }
184
185 forceinline int
186 IntSet::min(void) const {
187 IntSetObject* o = static_cast<IntSetObject*>(object());
188 return (o == nullptr) ? Int::Limits::max : o->r[0].min;
189 }
190
191 forceinline int
192 IntSet::max(void) const {
193 IntSetObject* o = static_cast<IntSetObject*>(object());
194 return (o == nullptr) ? Int::Limits::min : o->r[o->n-1].max;
195 }
196
197 forceinline unsigned int
198 IntSet::size(void) const {
199 IntSetObject* o = static_cast<IntSetObject*>(object());
200 return (o == nullptr) ? 0U : o->size;
201 }
202
203 forceinline unsigned int
204 IntSet::width(void) const {
205 IntSetObject* o = static_cast<IntSetObject*>(object());
206 return (o == nullptr) ? 0U : static_cast<unsigned int>(max()-min()+1);
207 }
208
209 forceinline bool
210 IntSet::operator ==(const IntSet& s) const {
211 IntSetObject* o1 = static_cast<IntSetObject*>(object());
212 IntSetObject* o2 = static_cast<IntSetObject*>(s.object());
213 if (o1 == o2)
214 return true;
215 if ((o1 == nullptr) || (o2 == nullptr))
216 return false;
217 if ((o1->size != o2->size) || (o1->n != o2->n))
218 return false;
219 return o1->equal(*o2);
220 }
221
222 forceinline bool
223 IntSet::operator !=(const IntSet& s) const {
224 return !(*this == s);
225 }
226
227
228 /*
229 * Range iterator for integer sets
230 *
231 */
232
233 forceinline
234 IntSetRanges::IntSetRanges(void) {}
235 forceinline
236 void
237 IntSetRanges::init(const IntSet& s) {
238 int n = s.ranges();
239 if (n > 0) {
240 i = &static_cast<IntSet::IntSetObject*>(s.object())->r[0]; e = i+n;
241 } else {
242 i = e = nullptr;
243 }
244 }
245 forceinline
246 IntSetRanges::IntSetRanges(const IntSet& s) { init(s); }
247
248
249 forceinline void
250 IntSetRanges::operator ++(void) {
251 i++;
252 }
253 forceinline bool
254 IntSetRanges::operator ()(void) const {
255 return i<e;
256 }
257
258 forceinline int
259 IntSetRanges::min(void) const {
260 return i->min;
261 }
262 forceinline int
263 IntSetRanges::max(void) const {
264 return i->max;
265 }
266 forceinline unsigned int
267 IntSetRanges::width(void) const {
268 return static_cast<unsigned int>(i->max - i->min) + 1;
269 }
270
271 /*
272 * Value iterator for integer sets
273 *
274 */
275 forceinline
276 IntSetValues::IntSetValues(void) {}
277
278 forceinline
279 IntSetValues::IntSetValues(const IntSet& s) {
280 IntSetRanges r(s);
281 Iter::Ranges::ToValues<IntSetRanges>::init(r);
282 }
283
284 forceinline void
285 IntSetValues::init(const IntSet& s) {
286 IntSetRanges r(s);
287 Iter::Ranges::ToValues<IntSetRanges>::init(r);
288 }
289
290 template<class Char, class Traits>
291 std::basic_ostream<Char,Traits>&
292 operator <<(std::basic_ostream<Char,Traits>& os, const IntSet& is) {
293 std::basic_ostringstream<Char,Traits> s;
294 s.copyfmt(os); s.width(0);
295 s << '{';
296 for (int i = 0; i < is.ranges(); ) {
297 int min = is.min(i);
298 int max = is.max(i);
299 if (min == max)
300 s << min;
301 else
302 s << min << ".." << max;
303 i++;
304 if (i < is.ranges())
305 s << ',';
306 }
307 s << '}';
308 return os << s.str();
309 }
310
311}
312
313// STATISTICS: int-var
314