Generated on for Gecode by doxygen 1.17.0
growable-int-set.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main author:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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
34namespace Gecode { namespace Int {
35
38 : _ranges(nullptr), _count(0), _capacity(0) {}
39
40 forceinline unsigned int
41 GrowableIntSet::max_capacity(void) {
42 return static_cast<unsigned int>(std::min(
43 static_cast<size_t>(std::numeric_limits<unsigned int>::max()),
44 static_cast<size_t>(std::numeric_limits<ptrdiff_t>::max()) /
45 sizeof(Range)));
46 }
47
48 inline void
49 GrowableIntSet::reserve(Space& home, unsigned int required) {
50 if (required <= _capacity)
51 return;
52 const unsigned int limit = max_capacity();
53 if (required > limit)
54 throw MemoryExhausted();
55 const unsigned int extra = _capacity / 2U + _capacity % 2U;
56 const unsigned int grown = (_capacity == 0) ? 2U :
57 ((_capacity > limit-extra) ? limit : _capacity+extra);
58 const unsigned int capacity = std::max(required,grown);
59 Range* ranges = home.alloc<Range>(capacity);
60 for (unsigned int i=0; i<_count; i++)
61 ranges[i] = _ranges[i];
62 if (_ranges != nullptr)
63 home.free<Range>(_ranges,_capacity);
64 _ranges = ranges;
65 _capacity = capacity;
66 }
67
68 forceinline unsigned int
69 GrowableIntSet::first_max_ge(int value) const {
70 unsigned int first = 0;
71 unsigned int after = _count;
72 while (first < after) {
73 const unsigned int middle = first + (after-first)/2U;
74 if (_ranges[middle].max < value)
75 first = middle+1U;
76 else
77 after = middle;
78 }
79 return first;
80 }
81
82 forceinline bool
83 GrowableIntSet::in(int value) const {
84 const unsigned int i = first_max_ge(value);
85 return (i < _count) && (_ranges[i].min <= value);
86 }
87
88 inline void
89 GrowableIntSet::add(Space& home, int min, int max) {
90 const unsigned int first = first_max_ge(min-1);
91 unsigned int after = first;
92 while ((after < _count) && (_ranges[after].min <= max+1))
93 ++after;
94 if (first < after) {
95 _ranges[first].min = std::min(min,_ranges[first].min);
96 _ranges[first].max = std::max(max,_ranges[after-1U].max);
97 if (after > first+1U) {
98 unsigned int out = first+1U;
99 for (unsigned int i=after; i<_count; i++)
100 _ranges[out++] = _ranges[i];
101 _count = out;
102 }
103 return;
104 }
105 if (_count == max_capacity())
106 throw MemoryExhausted();
107 reserve(home,_count+1U);
108 for (unsigned int i=_count; i>first; --i)
109 _ranges[i] = _ranges[i-1U];
110 _ranges[first].min = min;
111 _ranges[first].max = max;
112 ++_count;
113 }
114
115 template<class I>
116 inline void
117 GrowableIntSet::add_r(Space& home, I added) {
118 if (!added())
119 return;
120 I remaining(added);
121 ++remaining;
122 if (!remaining()) {
123 add(home,added.min(),added.max());
124 return;
125 }
126 const unsigned int limit = max_capacity()-_count;
127 unsigned int n = 1;
128 for (; remaining(); ++remaining) {
129 if (n >= limit)
130 throw MemoryExhausted();
131 ++n;
132 }
133 const unsigned int first = first_max_ge(added.min()-1);
134 reserve(home,_count+n);
135 // The hole protects unread old ranges while the union is written forward.
136 for (unsigned int i=_count; i>first; --i)
137 _ranges[i+n-1U] = _ranges[i-1U];
138 unsigned int read = first+n;
139 const unsigned int end = _count+n;
140 unsigned int out = first;
141 while (added() || (read < end)) {
142 Range next;
143 if (added() && ((read == end) ||
144 (added.min() < _ranges[read].min))) {
145 next.min = added.min();
146 next.max = added.max();
147 ++added;
148 } else {
149 next = _ranges[read++];
150 }
151 if ((out > first) && (next.min <= _ranges[out-1U].max+1)) {
152 _ranges[out-1U].max = std::max(_ranges[out-1U].max,next.max);
153 } else {
154 _ranges[out++] = next;
155 }
156 }
157 _count = out;
158 }
159
160 inline void
161 GrowableIntSet::update(Space& home, const GrowableIntSet& source) {
162 const unsigned int count = source._count;
163 Range* ranges = (count == 0) ? nullptr : home.alloc<Range>(count);
164 for (unsigned int i=0; i<count; i++)
165 ranges[i] = source._ranges[i];
166 if (_ranges != nullptr)
167 home.free<Range>(_ranges,_capacity);
168 _ranges = ranges;
169 _count = count;
170 _capacity = count;
171 }
172
173 forceinline void
175 if (_ranges != nullptr)
176 home.free<Range>(_ranges,_capacity);
177 _ranges = nullptr;
178 _count = 0;
179 _capacity = 0;
180 }
181
184 : current(set._ranges),
185 end((set._count == 0) ? set._ranges : set._ranges+set._count) {}
186
187 forceinline bool
189 return current != end;
190 }
191
192 forceinline void
194 ++current;
195 }
196
197 forceinline int
199 return current->min;
200 }
201
202 forceinline int
204 return current->max;
205 }
206
207 forceinline unsigned int
209 return static_cast<unsigned int>(current->max) -
210 static_cast<unsigned int>(current->min) + 1U;
211 }
212
213}}
214
215// STATISTICS: int-other
GrowableIntSetRanges(const GrowableIntSet &set)
A Space-owned set of integer values with growable canonical range storage.
void dispose(Space &home)
Return allocated storage to home.
void update(Space &home, const GrowableIntSet &source)
Copy exactly the live ranges into independent storage in home.
bool in(int value) const
Test membership.
void add_r(Space &home, I added)
Add the ranges from a copyable, independent canonical iterator.
GrowableIntSet(void)
Initialize an empty set.
Exception: Memory exhausted
Definition exception.hpp:63
Computation spaces.
Definition core.hpp:1787
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2973
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition core.hpp:2999
const int capacity[n_warehouses]
Capacity of a single warehouse.
Finite domain integers.
Definition lastval.hh:52
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
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 .
#define forceinline
Definition config.hpp:144