this repo has no description
dekker.one
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
79 /// Sort ranges according to increasing minimum
80 class IntSet::MinInc {
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