Generated on Sat Apr 10 2021 00:00:00 for Gecode by doxygen 1.9.1
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[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
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  */
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
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
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 FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
const int min
Smallest allowed integer value.
Definition: int.hh:118
const int max
Largest allowed integer value.
Definition: int.hh:116
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
#define forceinline
Definition: config.hpp:192