Generated on for Gecode by doxygen 1.17.0
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.dev>
5 *
6 * Contributing authors:
7 * Alexander Shepil <alexander.shepil@sap.com>
8 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
9 *
10 * Copyright:
11 * Christian Schulte, 2003
12 * Alexander Shepil, 2024
13 * Mikael Zayenz Lagerkvist, 2026
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.dev
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40#include <gecode/int.hh>
41
42namespace Gecode {
43
44#ifdef GECODE_HAS_FAULT_INJECTION
45 std::atomic<int> IntSet::IntSetObject::fault_live_objects{0};
46
47 void*
48 IntSet::IntSetObject::operator new(size_t s) {
49 void* p = ::operator new(s);
50 fault_live_objects.fetch_add(1, std::memory_order_relaxed);
51 return p;
52 }
53
54 void
55 IntSet::IntSetObject::operator delete(void* p) {
56 fault_live_objects.fetch_sub(1, std::memory_order_relaxed);
57 ::operator delete(p);
58 }
59
60 void
61 IntSet::fault_reset_allocations(void) {
62 IntSetObject::fault_live_objects.store(0, std::memory_order_relaxed);
63 }
64
65 int
66 IntSet::fault_live_allocations(void) {
67 return IntSetObject::fault_live_objects.load(std::memory_order_relaxed);
68 }
69#endif
70
71 IntSet::IntSetObject*
72 IntSet::IntSetObject::allocate(int n) {
73 IntSetObject* o = new IntSetObject;
74 o->size = 0U;
75 o->n = 0;
76 o->r = nullptr;
77 try {
78 o->r = heap.alloc<Range>(n);
79 } catch (...) {
80 delete o;
81 throw;
82 }
83 o->n = n;
84 return o;
85 }
86
87 bool
88 IntSet::IntSetObject::in(int n) const {
89 int l = 0;
90 int r = this->n - 1;
91
92 while (l <= r) {
93 int m = l + (r - l) / 2;
94 if ((this->r[m].min <= n) && (n <= this->r[m].max)) {
95 return true;
96 } else if (l == r) {
97 return false;
98 } else if (n < this->r[m].min) {
99 r=m-1;
100 } else {
101 l=m+1;
102 }
103 }
104 return false;
105 }
106
107 bool
108 IntSet::IntSetObject::equal(const IntSetObject& iso) const {
109 assert((size == iso.size) || (n == iso.n));
110 for (int i=0; i<n; i++)
111 if ((r[i].min != iso.r[i].min) || (r[i].max != iso.r[i].max))
112 return false;
113 return true;
114 }
115
116 IntSet::IntSetObject::~IntSetObject(void) {
117 if (r != nullptr)
118 heap.free<Range>(r,n);
119 }
120
123 public:
124 bool operator ()(const Range &x, const Range &y);
125 };
126
127 forceinline bool
128 IntSet::MinInc::operator ()(const Range &x, const Range &y) {
129 return x.min < y.min;
130 }
131
132 void
133 IntSet::normalize(Range* r, int n) {
134 if (n > 0) {
135 // Sort ranges
136 {
137 MinInc lt_mi;
138 Support::quicksort<Range>(r, n, lt_mi);
139 }
140 // Conjoin continuous ranges
141 {
142 int min = r[0].min;
143 int max = r[0].max;
144 int i = 1;
145 int j = 0;
146 while (i < n) {
147 if (max+1 < r[i].min) {
148 r[j].min = min; r[j].max = max; j++;
149 min = r[i].min; max = r[i].max; i++;
150 } else {
151 max = std::max(max,r[i].max); i++;
152 }
153 }
154 r[j].min = min; r[j].max = max;
155 n=j+1;
156 }
157 IntSetObject* o = IntSetObject::allocate(n);
158 unsigned int s = 0;
159 for (int i=0; i<n; i++) {
160 s += static_cast<unsigned int>(r[i].max) -
161 static_cast<unsigned int>(r[i].min) + 1U;
162 o->r[i]=r[i];
163 }
164 o->size = s;
165 object(o);
166 }
167 }
168
169 void
170 IntSet::init(const int r[], int n) {
171 assert(n > 0);
172 Region reg;
173 Range* dr = reg.alloc<Range>(n);
174 for (int i=0; i<n; i++) {
175 dr[i].min=r[i]; dr[i].max=r[i];
176 }
177 normalize(&dr[0],n);
178 }
179
180 void
181 IntSet::init(const int r[][2], int n) {
182 assert(n > 0);
183 Region reg;
184 Range* dr = reg.alloc<Range>(n);
185 int j = 0;
186 for (int i=0; i<n; i++)
187 if (r[i][0] <= r[i][1]) {
188 dr[j].min=r[i][0]; dr[j].max=r[i][1]; j++;
189 }
190 normalize(&dr[0],j);
191 }
192
193 IntSet::IntSet(std::initializer_list<int> r) {
194 int n = static_cast<int>(r.size());
195 assert(n > 0);
196 Region reg;
197 Range* dr = reg.alloc<Range>(n);
198 int j=0;
199 for (int k : r) {
200 dr[j].min=dr[j].max=k; j++;
201 }
202 normalize(&dr[0],j);
203 }
204
205 IntSet::IntSet(std::initializer_list<std::pair<int,int>> r) {
206 int n = static_cast<int>(r.size());
207 assert(n > 0);
208 Region reg;
209 Range* dr = reg.alloc<Range>(n);
210 int j=0;
211 for (const std::pair<int,int>& k : r)
212 if (k.first <= k.second) {
213 dr[j].min=k.first; dr[j].max=k.second; j++;
214 }
215 normalize(&dr[0],j);
216 }
217
218
219 void
220 IntSet::init(int n, int m) {
221 if (n <= m) {
222 IntSetObject* o = IntSetObject::allocate(1);
223 o->r[0].min = n; o->r[0].max = m;
224 o->size = static_cast<unsigned int>(m) - static_cast<unsigned int>(n) + 1U;
225 object(o);
226 }
227 }
228
229 const IntSet IntSet::empty;
230
231}
232
233// STATISTICS: int-var
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition heap.hpp:467
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition heap.hpp:441
Sort ranges according to increasing minimum.
Definition int-set.cpp:122
bool operator()(const Range &x, const Range &y)
Definition int-set.cpp:128
int min(int i) const
Return minimum of range at position i.
int max(int i) const
Return maximum of range at position i.
int max(void) const
Return maximum of entire set.
unsigned int size(void) const
Return size (cardinality) of set.
IntSet(void)
Initialize as empty set.
Definition int-set-1.hpp:47
static const IntSet empty
Empty set.
Definition int.hh:302
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.
Heap heap
The single global heap.
Definition heap.cpp:44
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
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 .
Gecode::IntArgs i({1, 2, 3, 4})
const int r[4][2]
Definition dom.cpp:152
#define forceinline
Definition config.hpp:144