Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
int-set.cpp
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 <gecode/int.hh>
35 
36 namespace Gecode {
37 
38  IntSet::IntSetObject*
39  IntSet::IntSetObject::allocate(int n) {
40  IntSetObject* o = new IntSetObject;
41  o->n = n;
42  o->r = heap.alloc<Range>(n);
43  return o;
44  }
45 
46  bool
47  IntSet::IntSetObject::in(int n) const {
48  int l = 0;
49  int r = this->n - 1;
50 
51  while (l <= r) {
52  int m = l + (r - l) / 2;
53  if ((this->r[m].min <= n) && (n <= this->r[m].max)) {
54  return true;
55  } else if (l == r) {
56  return false;
57  } else if (n < this->r[m].min) {
58  r=m-1;
59  } else {
60  l=m+1;
61  }
62  }
63  return false;
64  }
65 
66  bool
67  IntSet::IntSetObject::equal(const IntSetObject& iso) const {
68  assert((size == iso.size) || (n == iso.n));
69  for (int i=0; i<n; i++)
70  if ((r[i].min != iso.r[i].min) || (r[i].max != iso.r[i].max))
71  return false;
72  return true;
73  }
74 
75  IntSet::IntSetObject::~IntSetObject(void) {
76  heap.free<Range>(r,n);
77  }
78 
81  public:
82  bool operator ()(const Range &x, const Range &y);
83  };
84 
85  forceinline bool
86  IntSet::MinInc::operator ()(const Range &x, const Range &y) {
87  return x.min < y.min;
88  }
89 
90  void
91  IntSet::normalize(Range* r, int n) {
92  if (n > 0) {
93  // Sort ranges
94  {
95  MinInc lt_mi;
96  Support::quicksort<Range>(r, n, lt_mi);
97  }
98  // Conjoin continuous ranges
99  {
100  int min = r[0].min;
101  int max = r[0].max;
102  int i = 1;
103  int j = 0;
104  while (i < n) {
105  if (max+1 < r[i].min) {
106  r[j].min = min; r[j].max = max; j++;
107  min = r[i].min; max = r[i].max; i++;
108  } else {
109  max = std::max(max,r[i].max); i++;
110  }
111  }
112  r[j].min = min; r[j].max = max;
113  n=j+1;
114  }
115  IntSetObject* o = IntSetObject::allocate(n);
116  unsigned int s = 0;
117  for (int i=0; i<n; i++) {
118  s += static_cast<unsigned int>(r[i].max-r[i].min+1);
119  o->r[i]=r[i];
120  }
121  o->size = s;
122  object(o);
123  }
124  }
125 
126  void
127  IntSet::init(const int r[], int n) {
128  assert(n > 0);
129  Region reg;
130  Range* dr = reg.alloc<Range>(n);
131  for (int i=0; i<n; i++) {
132  dr[i].min=r[i]; dr[i].max=r[i];
133  }
134  normalize(&dr[0],n);
135  }
136 
137  void
138  IntSet::init(const int r[][2], int n) {
139  assert(n > 0);
140  Region reg;
141  Range* dr = reg.alloc<Range>(n);
142  int j = 0;
143  for (int i=0; i<n; i++)
144  if (r[i][0] <= r[i][1]) {
145  dr[j].min=r[i][0]; dr[j].max=r[i][1]; j++;
146  }
147  normalize(&dr[0],j);
148  }
149 
150  IntSet::IntSet(std::initializer_list<int> r) {
151  int n = static_cast<int>(r.size());
152  assert(n > 0);
153  Region reg;
154  Range* dr = reg.alloc<Range>(n);
155  int j=0;
156  for (int k : r) {
157  dr[j].min=dr[j].max=k; j++;
158  }
159  normalize(&dr[0],j);
160  }
161 
162  IntSet::IntSet(std::initializer_list<std::pair<int,int>> r) {
163  int n = static_cast<int>(r.size());
164  assert(n > 0);
165  Region reg;
166  Range* dr = reg.alloc<Range>(n);
167  int j=0;
168  for (const std::pair<int,int>& k : r)
169  if (k.first <= k.second) {
170  dr[j].min=k.first; dr[j].max=k.second; j++;
171  }
172  normalize(&dr[0],j);
173  }
174 
175 
176  void
177  IntSet::init(int n, int m) {
178  if (n <= m) {
179  IntSetObject* o = IntSetObject::allocate(1);
180  o->r[0].min = n; o->r[0].max = m;
181  o->size = static_cast<unsigned int>(m - n + 1);
182  object(o);
183  }
184  }
185 
186  const IntSet IntSet::empty;
187 
188 }
189 
190 // STATISTICS: int-var
191 
int max(void) const
Return maximum of entire set.
Definition: int-set-1.hpp:189
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:386
bool equal(I &i, J &j)
Check whether range iterators i and j are equal.
Handle to region.
Definition: region.hpp:55
#define forceinline
Definition: config.hpp:185
bool operator()(const Range &x, const Range &y)
Definition: int-set.cpp:86
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:431
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
SharedHandle::Object * object(void) const
Access to the shared object.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Integer sets.
Definition: int.hh:174
static const IntSet empty
Empty set.
Definition: int.hh:283
IntSet(void)
Initialize as empty set.
Definition: int-set-1.hpp:43
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:457
int min(void) const
Return minimum of entire set.
Definition: int-set-1.hpp:183
Heap heap
The single global heap.
Definition: heap.cpp:44
Sort ranges according to increasing minimum.
Definition: int-set.cpp:80
Post propagator for SetVar x
Definition: set.hh:767
Gecode toplevel namespace