Generated on for Gecode by doxygen 1.18.0
open.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
34#ifndef GECODE_INT_DISTINCT_OPEN_HPP
35#define GECODE_INT_DISTINCT_OPEN_HPP
36
40#include <limits>
41
42namespace Gecode { namespace Int { namespace Distinct {
43
44 template<class View>
45 class Open : public OpenListPropagator<View> {
46 protected:
51
58
61 active(nullptr), active_count(0), active_capacity(0) {
62 home.notice(*this,AP_DISPOSE);
63 }
64
65 Open(Space& home, Open& p)
66 : OpenListPropagator<View>(home,p),
67 active((p.active_count == 0) ? nullptr :
68 home.alloc<View>(p.active_count)),
70 for (int i=0; i<active_count; i++)
71 active[i].update(home,p.active[i]);
72 assigned.update(home,p.assigned);
73 }
74
76 void
77 reserve_active(Space& home, int required) {
78 if (required <= active_capacity)
79 return;
80 const int limit = static_cast<int>(std::min(
81 static_cast<size_t>(std::numeric_limits<int>::max()),
82 static_cast<size_t>(std::numeric_limits<ptrdiff_t>::max()) /
83 sizeof(View)));
84 if (required > limit)
85 throw MemoryExhausted();
86 const int extra = std::min(active_capacity/2+1,limit-active_capacity);
87 const int capacity = std::max(required,active_capacity+extra);
88 View* views = home.alloc<View>(capacity);
89 for (int i=0; i<active_count; i++)
90 views[i] = active[i];
91 if (active != nullptr)
93 active = views;
95 }
96
98 template<class I>
100 exclude_values(Space& home, I excluded, int first,
101 int* values, int& count) {
102 count = 0;
103 for (int i=active_count; i--; ) {
104 if ((i >= first) && !active[i].assigned()) {
105 I ranges(excluded);
106 GECODE_ME_CHECK(active[i].minus_r(home,ranges,false));
107 }
108 if (active[i].assigned()) {
109 values[count++] = active[i].val();
110 active[i] = active[--active_count];
111 }
112 }
113 return ES_OK;
114 }
115
116 public:
117 virtual PropCost
118 cost(const Space&, const ModEventDelta&) const {
120 active_count+(list.known_length()-processed));
121 }
122
123 virtual Actor*
124 copy(Space& home) {
125 return new (home) Open(home,*this);
126 }
127
128 virtual ExecStatus
130 const int size = list.known_length();
132 const int first_new = active_count;
133 for (int i=processed; i<size; i++) {
134 View x(list[i]);
135 if (x.assigned() && assigned.in(x.val()))
136 return ES_FAILED;
137 active[active_count++] = x;
138 if (!x.assigned())
139 x.subscribe(home,*this,PC_INT_VAL,false);
140 }
141 processed = size;
142
143 Region region;
144 const int capacity = active_count;
145 int* current = region.alloc<int>(capacity);
146 int* next = region.alloc<int>(capacity);
147 int count;
149 GECODE_ES_CHECK(exclude_values(home,history,first_new,current,count));
150
152 while (count > 0) {
153 Support::quicksort(current,count);
154 for (int i=1; i<count; i++)
155 if (current[i-1] == current[i])
156 return ES_FAILED;
157
159 BatchRanges batch(values);
160 int next_count;
161 GECODE_ES_CHECK(exclude_values(home,batch,0,next,next_count));
162 assigned.add_r(home,batch);
163 std::swap(current,next);
164 count = next_count;
165 }
166
167 if (closed()) {
169 for (int i=0; i<x.size(); i++)
170 x[i] = active[i];
171 GECODE_REWRITE(*this,Distinct::Val<View>::post(home(*this),x));
172 }
173 return ES_FIX;
174 }
175
176 virtual void
179 for (int i=0; i<active_count; i++)
180 if (!active[i].assigned())
181 active[i].reschedule(home,*this,PC_INT_VAL);
182 }
183
184 virtual size_t
185 dispose(Space& home) {
186 home.ignore(*this,AP_DISPOSE);
187 for (int i=0; i<active_count; i++)
188 if (!active[i].assigned())
189 active[i].cancel(home,*this,PC_INT_VAL);
190 if (active != nullptr)
192 assigned.dispose(home);
194 return sizeof(*this);
195 }
196
197 static void
199 (void) new (home) Open(home,list);
200 }
201 };
202
203}}}
204
205#endif
206
207// STATISTICS: int-prop
Base-class for both propagators and branchers.
Definition core.hpp:635
Home class for posting propagators
Definition core.hpp:863
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3373
Open(Space &home, Open &p)
Definition open.hpp:65
View * active
Variables whose assigned values have not yet been propagated.
Definition open.hpp:53
static void post(Home home, OpenViewList< View > list)
Definition open.hpp:198
virtual Actor * copy(Space &home)
Create copy.
Definition open.hpp:124
ExecStatus exclude_values(Space &home, I excluded, int first, int *values, int &count)
Exclude a batch from the selected suffix and collect all assignments.
Definition open.hpp:100
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Propagation function.
Definition open.hpp:129
Open(Home home, OpenViewList< View > list)
Definition open.hpp:59
GrowableIntSet assigned
Assigned values to exclude from appended variables.
Definition open.hpp:57
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition open.hpp:185
void reserve_active(Space &home, int required)
Grow geometrically and copy only active views.
Definition open.hpp:77
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition open.hpp:118
virtual void reschedule(Space &home)
Schedule function.
Definition open.hpp:177
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition val.hpp:185
Borrowed forward iterator over a growable set's ranges.
A Space-owned set of integer values with growable canonical range storage.
virtual void reschedule(Space &home)
Schedule function.
OpenListPropagator(Home home, OpenViewList< View > list0)
Value iterator for array of integers
Range iterator from value iterator.
MemoryExhausted(void)
Initialize.
View interface to a space-local list with an open length.
Definition int.hh:1044
Propagation cost.
Definition core.hpp:493
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:5080
friend class Space
Definition core.hpp:1075
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
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
virtual Val val(const Space &home, View x, int i)=0
Return value of view x at position i.
View arrays.
Definition array.hpp:255
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1165
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4321
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:569
Distinct propagators
Finite domain integers.
Definition lastval.hh:52
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value).
Definition var-type.hpp:90
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:484
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
const int capacity[n_warehouses]
Capacity of a single warehouse.