38 : _ranges(nullptr), _count(0), _capacity(0) {}
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()) /
49 GrowableIntSet::reserve(
Space& home,
unsigned int required) {
50 if (required <= _capacity)
52 const unsigned int limit = max_capacity();
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);
60 for (
unsigned int i=0; i<_count; i++)
61 ranges[i] = _ranges[i];
62 if (_ranges !=
nullptr)
63 home.
free<Range>(_ranges,_capacity);
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)
84 const unsigned int i = first_max_ge(value);
85 return (i < _count) && (_ranges[i].min <= value);
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))
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];
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;
123 add(home,added.min(),added.max());
126 const unsigned int limit = max_capacity()-_count;
128 for (; remaining(); ++remaining) {
133 const unsigned int first = first_max_ge(added.min()-1);
134 reserve(home,_count+n);
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)) {
143 if (added() && ((read == end) ||
144 (added.min() < _ranges[read].min))) {
145 next.min = added.min();
146 next.max = added.max();
149 next = _ranges[read++];
151 if ((out > first) && (next.min <= _ranges[out-1U].max+1)) {
152 _ranges[out-1U].max = std::max(_ranges[out-1U].
max,next.max);
154 _ranges[out++] = next;
162 const unsigned int count = source._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);
175 if (_ranges !=
nullptr)
176 home.
free<Range>(_ranges,_capacity);
184 : current(set._ranges),
185 end((set._count == 0) ? set._ranges : set._ranges+set._count) {}
189 return current != end;
209 return static_cast<unsigned int>(current->max) -
210 static_cast<unsigned int>(current->min) + 1U;
GrowableIntSetRanges(const GrowableIntSet &set)
unsigned int width(void) const
bool operator()(void) const
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
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
const int capacity[n_warehouses]
Capacity of a single warehouse.
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
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 .