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#ifndef GECODE_SEARCH_SEQ_PATH_HH
35#define GECODE_SEARCH_SEQ_PATH_HH
36
37#include <algorithm>
38
39#include <gecode/search.hh>
40#include <gecode/search/support.hh>
41#include <gecode/search/worker.hh>
42#include <gecode/search/nogoods.hh>
43
44namespace Gecode { namespace Search { namespace Seq {
45
46 /**
47 * \brief Depth-first path (stack of edges) supporting recomputation
48 *
49 * Maintains the invariant that it contains
50 * the path of the space being currently explored. This
51 * is required to support recomputation, of course.
52 *
53 * The path supports adaptive recomputation controlled
54 * by the value of a_d: only if the recomputation
55 * distance is at least this large, an additional
56 * clone is created.
57 *
58 */
59 template<class Tracer>
60 class GECODE_VTABLE_EXPORT Path : public NoGoods {
61 friend class Search::NoGoodsProp;
62 public:
63 /// Node identity type
64 typedef typename Tracer::ID ID;
65 /// %Search tree edge for recomputation
66 class Edge {
67 protected:
68 /// Space corresponding to this edge (might be nullptr)
69 Space* _space;
70 /// Current alternative
71 unsigned int _alt;
72 /// Choice
73 const Choice* _choice;
74 /// Node identifier
75 ID _nid;
76 public:
77 /// Default constructor
78 Edge(void);
79 /// Edge for space \a s with clone \a c (possibly nullptr)
80 Edge(Space* s, Space* c, unsigned int nid);
81
82 /// Return space for edge
83 Space* space(void) const;
84 /// Set space to \a s
85 void space(Space* s);
86
87 /// Return choice
88 const Choice* choice(void) const;
89
90 /// Return number for alternatives
91 unsigned int alt(void) const;
92 /// Return true number for alternatives (excluding lao optimization)
93 unsigned int truealt(void) const;
94 /// Test whether current alternative is leftmost
95 bool leftmost(void) const;
96 /// Test whether current alternative is rightmost
97 bool rightmost(void) const;
98 /// Move to next alternative
99 void next(void);
100 /// Test whether current alternative was LAO
101 bool lao(void) const;
102
103 /// Return node identifier
104 unsigned int nid(void) const;
105
106 /// Free memory for edge
107 void dispose(void);
108 };
109 protected:
110 /// Stack to store edge information
111 Support::DynamicStack<Edge,Heap> ds;
112 /// Depth limit for no-good generation
113 unsigned int _ngdl;
114 public:
115 /// Initialize with no-good depth limit \a l
116 Path(unsigned int l);
117 /// Return no-good depth limit
118 unsigned int ngdl(void) const;
119 /// Set no-good depth limit to \a l
120 void ngdl(unsigned int l);
121 /// Push space \a c (a clone of \a s or nullptr)
122 const Choice* push(Worker& stat, Space* s, Space* c, unsigned int nid);
123 /// Generate path for next node
124 void next(void);
125 /// Provide access to topmost edge
126 Edge& top(void) const;
127 /// Test whether path is empty
128 bool empty(void) const;
129 /// Return position on stack of last copy
130 int lc(void) const;
131 /// Unwind the stack up to position \a l (after failure)
132 void unwind(int l, Tracer& t);
133 /// Commit space \a s as described by stack entry at position \a i
134 void commit(Space* s, int i) const;
135 /// Recompute space according to path
136 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
137 Tracer& t);
138 /// Recompute space according to path
139 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
140 const Space& best, int& mark,
141 Tracer& t);
142 /// Return number of entries on stack
143 int entries(void) const;
144 /// Reset stack
145 void reset(void);
146 /// Post no-goods
147 virtual void post(Space& home) const;
148 };
149
150}}}
151
152#include <gecode/search/seq/path.hpp>
153
154#endif
155
156// STATISTICS: search-seq