Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
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 
36 namespace Gecode {
37 
38  /*
39  * Integer sets
40  *
41  */
43  IntSet::IntSet(void) {}
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<>
77  class IntSetInit<IntSet> {
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[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[i].first <= r[i].second) {
137  dr[j].min=r[i].first; dr[j].max=r[i].second; j++;
138  }
139  normalize(&dr[0],j);
140  }
141  }
142 
144  IntSet::IntSet(int n, int m) {
145  init(n,m);
146  }
147 
148  forceinline int
149  IntSet::min(int i) const {
150  assert(object() != NULL);
151  return static_cast<IntSetObject*>(object())->r[i].min;
152  }
153 
154  forceinline int
155  IntSet::max(int i) const {
156  assert(object() != NULL);
157  return static_cast<IntSetObject*>(object())->r[i].max;
158  }
159 
160  forceinline unsigned int
161  IntSet::width(int i) const {
162  assert(object() != NULL);
163  IntSetObject* o = static_cast<IntSetObject*>(object());
164  return static_cast<unsigned int>(o->r[i].max-o->r[i].min)+1;
165  }
166 
167  forceinline int
168  IntSet::ranges(void) const {
169  IntSetObject* o = static_cast<IntSetObject*>(object());
170  return (o == NULL) ? 0 : o->n;
171  }
172 
173  forceinline bool
174  IntSet::in(int n) const {
175  IntSetObject* o = static_cast<IntSetObject*>(object());
176  if ((o == NULL) || (n < o->r[0].min) || (n > o->r[o->n-1].max))
177  return false;
178  else
179  return o->in(n);
180  }
181 
182  forceinline int
183  IntSet::min(void) const {
184  IntSetObject* o = static_cast<IntSetObject*>(object());
185  return (o == NULL) ? Int::Limits::max : o->r[0].min;
186  }
187 
188  forceinline int
189  IntSet::max(void) const {
190  IntSetObject* o = static_cast<IntSetObject*>(object());
191  return (o == NULL) ? Int::Limits::min : o->r[o->n-1].max;
192  }
193 
194  forceinline unsigned int
195  IntSet::size(void) const {
196  IntSetObject* o = static_cast<IntSetObject*>(object());
197  return (o == NULL) ? 0U : o->size;
198  }
199 
200  forceinline unsigned int
201  IntSet::width(void) const {
202  IntSetObject* o = static_cast<IntSetObject*>(object());
203  return (o == NULL) ? 0U : static_cast<unsigned int>(max()-min()+1);
204  }
205 
206  forceinline bool
207  IntSet::operator ==(const IntSet& s) const {
208  IntSetObject* o1 = static_cast<IntSetObject*>(object());
209  IntSetObject* o2 = static_cast<IntSetObject*>(s.object());
210  if (o1 == o2)
211  return true;
212  if ((o1 == nullptr) || (o2 == nullptr))
213  return false;
214  if ((o1->size != o2->size) || (o1->n != o2->n))
215  return false;
216  return o1->equal(*o2);
217  }
218 
219  forceinline bool
220  IntSet::operator !=(const IntSet& s) const {
221  return !(*this == s);
222  }
223 
224 
225  /*
226  * Range iterator for integer sets
227  *
228  */
229 
233  void
235  int n = s.ranges();
236  if (n > 0) {
237  i = &static_cast<IntSet::IntSetObject*>(s.object())->r[0]; e = i+n;
238  } else {
239  i = e = NULL;
240  }
241  }
243  IntSetRanges::IntSetRanges(const IntSet& s) { init(s); }
244 
245 
246  forceinline void
248  i++;
249  }
250  forceinline bool
252  return i<e;
253  }
254 
255  forceinline int
256  IntSetRanges::min(void) const {
257  return i->min;
258  }
259  forceinline int
260  IntSetRanges::max(void) const {
261  return i->max;
262  }
263  forceinline unsigned int
264  IntSetRanges::width(void) const {
265  return static_cast<unsigned int>(i->max - i->min) + 1;
266  }
267 
268  /*
269  * Value iterator for integer sets
270  *
271  */
274 
277  IntSetRanges r(s);
279  }
280 
281  forceinline void
283  IntSetRanges r(s);
285  }
286 
287  template<class Char, class Traits>
288  std::basic_ostream<Char,Traits>&
289  operator <<(std::basic_ostream<Char,Traits>& os, const IntSet& is) {
290  std::basic_ostringstream<Char,Traits> s;
291  s.copyfmt(os); s.width(0);
292  s << '{';
293  for (int i = 0; i < is.ranges(); ) {
294  int min = is.min(i);
295  int max = is.max(i);
296  if (min == max)
297  s << min;
298  else
299  s << min << ".." << max;
300  i++;
301  if (i < is.ranges())
302  s << ',';
303  }
304  s << '}';
305  return os << s.str();
306  }
307 
308 }
309 
310 // STATISTICS: int-var
311 
bool operator==(const IntSet &s) const
Return whether s is equal.
Definition: int-set-1.hpp:207
int max(void) const
Return maximum of entire set.
Definition: int-set-1.hpp:189
void init(I &i)
Initialize with values from range iterator i.
Range iterator for integer sets.
Definition: int.hh:292
IntSetValues(void)
Default constructor.
Definition: int-set-1.hpp:273
void operator++(void)
Move iterator to next range (if possible)
Definition: int-set-1.hpp:247
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:386
unsigned int width(int i) const
Return width of range at position i.
Definition: int-set-1.hpp:161
void init(const IntSet &s)
Initialize with values for s.
Definition: int-set-1.hpp:282
Array with arbitrary number of elements.
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int-set-1.hpp:251
Handle to region.
Definition: region.hpp:55
#define forceinline
Definition: config.hpp:185
const int max
Largest allowed integer value.
Definition: int.hh:116
void init(const IntSet &s)
Initialize with ranges for set s.
Definition: int-set-1.hpp:234
const int min
Smallest allowed integer value.
Definition: int.hh:118
static void init(IntSet &s, const IntSet &i)
Definition: int-set-1.hpp:79
Gecode::IntSet d(v, 7)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
static void init(IntSet &s, I &i)
Initialize s with iterator i.
Definition: int-set-1.hpp:56
SharedHandle::Object * object(void) const
Access to the shared object.
bool operator!=(const IntSet &s) const
Return whether s is not equal.
Definition: int-set-1.hpp:220
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:195
Integer set initialization.
Definition: int-set-1.hpp:53
Integer sets.
Definition: int.hh:174
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int-set-1.hpp:264
unsigned int width(void) const
Return width of set (distance between maximum and minimum)
Definition: int-set-1.hpp:201
IntSet(void)
Initialize as empty set.
Definition: int-set-1.hpp:43
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
int min(void) const
Return smallest value of range.
Definition: int-set-1.hpp:256
int min(void) const
Return minimum of entire set.
Definition: int-set-1.hpp:183
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:168
int max(void) const
Return largest value of range.
Definition: int-set-1.hpp:260
Gecode toplevel namespace
bool in(int n) const
Return whether n is included in the set.
Definition: int-set-1.hpp:174
IntSetRanges(void)
Default constructor.
Definition: int-set-1.hpp:231