Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
283
284 forceinline void
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
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)
bool operator()(void) const
Test whether iterator is still at a range or done.
int max(void) const
Return largest value of range.
void operator++(void)
Move iterator to next range (if possible)
void init(const IntSet &s)
Initialize with ranges for set s.
int min(void) const
Return smallest value of range.
IntSetRanges(void)
Default constructor.
void init(const IntSet &s)
Initialize with values for s.
IntSetValues(void)
Default constructor.
Integer sets.
Definition int.hh:174
int min(void) const
Return minimum of entire set.
unsigned int width(void) const
Return width of set (distance between maximum and minimum)
int min(int i) const
Return minimum of range at position i.
bool in(int n) const
Return whether n is included in the set.
int max(int i) const
Return maximum of range at position i.
int max(void) const
Return maximum of entire set.
int ranges(void) const
Return number of ranges of the specification.
bool operator==(const IntSet &s) const
Return whether s is equal.
unsigned int size(void) const
Return size (cardinality) of set.
IntSet(void)
Initialize as empty set.
Definition int-set-1.hpp:43
bool operator!=(const IntSet &s) const
Return whether s is not equal.
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:773
Archive & operator<<(Archive &e, FloatNumBranch nl)
Definition val-sel.hpp:39
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
#define forceinline
Definition config.hpp:194