Generated on Thu Jan 19 2023 00:00:00 for Gecode by doxygen 1.9.6
int-set-1.hpp
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, 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 */
44
52 template<class I>
53 class IntSetInit {
54 public:
56 static void init(IntSet& s, I& i) {
57 Region 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
76 template<>
78 public:
79 static void init(IntSet& s, const IntSet& i) {
80 s.object(i.object());
81 }
82 };
83
85 template<class I>
87 IntSetInit<I>::init(*this,i);
88 }
89
91 template<class I>
92 IntSet::IntSet(const I& i) {
93 IntSetInit<I>::init(*this,i);
94 }
95
97 IntSet::IntSet(const int r[][2], int n) {
98 if (n > 0)
99 init(r,n);
100 }
101
103 IntSet::IntSet(const int r[], int n) {
104 if (n > 0)
105 init(r,n);
106 }
107
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
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
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() != NULL);
154 return static_cast<IntSetObject*>(object())->r[i].min;
155 }
156
157 forceinline int
158 IntSet::max(int i) const {
159 assert(object() != NULL);
160 return static_cast<IntSetObject*>(object())->r[i].max;
161 }
162
163 forceinline unsigned int
164 IntSet::width(int i) const {
165 assert(object() != NULL);
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 == NULL) ? 0 : o->n;
174 }
175
176 forceinline bool
177 IntSet::in(int n) const {
178 IntSetObject* o = static_cast<IntSetObject*>(object());
179 if ((o == NULL) || (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 == NULL) ? 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 == NULL) ? 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 == NULL) ? 0U : o->size;
201 }
202
203 forceinline unsigned int
204 IntSet::width(void) const {
205 IntSetObject* o = static_cast<IntSetObject*>(object());
206 return (o == NULL) ? 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
236 void
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 = NULL;
243 }
244 }
247
248
249 forceinline void
251 i++;
252 }
253 forceinline bool
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
268 return static_cast<unsigned int>(i->max - i->min) + 1;
269 }
270
271 /*
272 * Value iterator for integer sets
273 *
274 */
277
280 IntSetRanges r(s);
282 }
283
284 forceinline void
286 IntSetRanges r(s);
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
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
static void init(IntSet &s, const IntSet &i)
Definition: int-set-1.hpp:79
Integer set initialization.
Definition: int-set-1.hpp:53
static void init(IntSet &s, I &i)
Initialize s with iterator i.
Definition: int-set-1.hpp:56
Range iterator for integer sets.
Definition: int.hh:292
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int-set-1.hpp:267
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int-set-1.hpp:254
int max(void) const
Return largest value of range.
Definition: int-set-1.hpp:263
void operator++(void)
Move iterator to next range (if possible)
Definition: int-set-1.hpp:250
void init(const IntSet &s)
Initialize with ranges for set s.
Definition: int-set-1.hpp:237
int min(void) const
Return smallest value of range.
Definition: int-set-1.hpp:259
IntSetRanges(void)
Default constructor.
Definition: int-set-1.hpp:234
void init(const IntSet &s)
Initialize with values for s.
Definition: int-set-1.hpp:285
IntSetValues(void)
Default constructor.
Definition: int-set-1.hpp:276
Integer sets.
Definition: int.hh:174
int min(void) const
Return minimum of entire set.
Definition: int-set-1.hpp:186
unsigned int width(void) const
Return width of set (distance between maximum and minimum)
Definition: int-set-1.hpp:204
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:152
bool in(int n) const
Return whether n is included in the set.
Definition: int-set-1.hpp:177
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:158
int max(void) const
Return maximum of entire set.
Definition: int-set-1.hpp:192
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:171
bool operator==(const IntSet &s) const
Return whether s is equal.
Definition: int-set-1.hpp:210
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:198
IntSet(void)
Initialize as empty set.
Definition: int-set-1.hpp:43
bool operator!=(const IntSet &s) const
Return whether s is not equal.
Definition: int-set-1.hpp:223
void init(I &i)
Initialize with values from range iterator i.
Handle to region.
Definition: region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:386
SharedHandle::Object * object(void) const
Access to the shared object.
Array with arbitrary number of elements.
const int min
Smallest allowed integer value.
Definition: int.hh:118
const int max
Largest allowed integer value.
Definition: int.hh:116
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Archive & operator<<(Archive &e, FloatNumBranch nl)
Definition: val-sel.hpp:39
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
#define forceinline
Definition: config.hpp:194