Generated on for Gecode by doxygen 1.17.0
choice-expansion.hh
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
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_SEARCH_SEQ_CHOICE_EXPANSION_HH
35#define GECODE_SEARCH_SEQ_CHOICE_EXPANSION_HH
36
38#include <memory>
39#include <utility>
40
41#ifdef GECODE_HAS_EXPERIMENTAL
42namespace Gecode { namespace Search { namespace Seq {
43
46 public:
53
56 std::unique_ptr<Space> space;
59 };
60
63 private:
65 std::unique_ptr<Space> parent;
67 std::unique_ptr<const Choice> choice;
69 unsigned int alternative;
70 public:
72 ChoiceExpansion(void) : alternative(0) {}
74 explicit operator bool(void) const { return static_cast<bool>(parent); }
76 Space& space(void) const { return *parent; }
78 void select(std::unique_ptr<Space> s) {
79 assert(!parent && !choice);
80 parent = std::move(s);
81 alternative = 0;
82 }
83
84 std::unique_ptr<Space> take(void) {
85 assert(!choice);
86 return std::move(parent);
87 }
88
89 void reset(void) {
90 choice.reset();
91 parent.reset();
92 alternative = 0;
93 }
94
101 ExpansionStep next(Worker& worker, unsigned long int depth,
102 unsigned long long int node_revision,
103 const Space* incumbent,
104 unsigned long long int revision) {
105 assert(parent);
106 if (!choice) {
107 SpaceStatus status = parent->status(worker);
108 if (status != SS_BRANCH)
109 return {ExpansionStep::TERMINAL,std::move(parent),status};
110 choice.reset(parent->choice());
111 alternative = 0;
112 }
113 if (alternative == choice->alternatives()) {
114 reset();
115 return {ExpansionStep::EXHAUSTED,nullptr,SS_FAILED};
116 }
117 std::unique_ptr<Space> child;
118 // Keeps the choice alive while committing the last alternative
119 std::unique_ptr<const Choice> last;
120 const Choice* c = choice.get();
121 if (alternative+1 == choice->alternatives()) {
122 child = std::move(parent);
123 last = std::move(choice);
124 } else {
125 child.reset(parent->clone());
126 }
127 child->commit(*c,alternative);
128 if ((incumbent != nullptr) && (node_revision != revision))
129 child->constrain(*incumbent);
130 worker.node++;
131 worker.stack_depth(depth);
132 SpaceStatus status = child->status(worker);
133 alternative++;
134 return {ExpansionStep::CHILD,std::move(child),status};
135 }
136 };
137
138}}}
139
140#endif
141
142#endif
143
144// STATISTICS: search-seq
Choice for performing commit
Definition core.hpp:1430
Space & space(void) const
Return the node.
ExpansionStep next(Worker &worker, unsigned long int depth, unsigned long long int node_revision, const Space *incumbent, unsigned long long int revision)
Commit and propagate the next alternative.
ChoiceExpansion(void)
Initialize without node.
std::unique_ptr< Space > take(void)
Return the node before its choice has been computed.
void select(std::unique_ptr< Space > s)
Take stable node s.
Result of expanding one alternative.
@ EXHAUSTED
Nothing, all alternatives have been expanded.
@ TERMINAL
The node itself, as it does not branch.
SpaceStatus status
Status of the space.
std::unique_ptr< Space > space
The child or node.
unsigned long long int node
Number of nodes expanded.
Definition search.hh:160
Search worker statistics
Definition worker.hh:44
void stack_depth(unsigned long int d)
Record stack depth d.
Definition worker.hh:114
Computation spaces.
Definition core.hpp:1787
SpaceStatus
Space status
Definition core.hpp:1726
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1729
@ SS_FAILED
Space is failed
Definition core.hpp:1727
Search engines
Gecode toplevel namespace