Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.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.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
36namespace 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;
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
NNF * l
Left subtree.
int n
Number of negative literals for node type.
Node * x
Pointer to corresponding Boolean expression node.
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition heap.hpp:457
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition heap.hpp:431
Sort ranges according to increasing minimum.
Definition int-set.cpp:80
bool operator()(const Range &x, const Range &y)
Definition int-set.cpp:86
int min(void) const
Return minimum of entire set.
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:43
static const IntSet empty
Empty set.
Definition int.hh:283
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
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
Post propagator for SetVar x
Definition set.hh:767
Gecode::IntArgs i({1, 2, 3, 4})
#define forceinline
Definition config.hpp:187