Line data Source code
1 : // Author(s): Wieger Wesselink
2 : // Copyright: see the accompanying file COPYING or copy at
3 : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4 : //
5 : // Distributed under the Boost Software License, Version 1.0.
6 : // (See accompanying file LICENSE_1_0.txt or copy at
7 : // http://www.boost.org/LICENSE_1_0.txt)
8 : //
9 : /// \file mcrl2/atermpp/algorithm.h
10 : /// \brief Algorithms for ATerms.
11 :
12 : #ifndef MCRL2_ATERMPP_ALGORITHM_H
13 : #define MCRL2_ATERMPP_ALGORITHM_H
14 :
15 : #include <unordered_map>
16 :
17 : #include "mcrl2/atermpp/builder.h"
18 : #include "mcrl2/atermpp/detail/algorithm_impl.h"
19 :
20 : namespace atermpp
21 : {
22 :
23 : namespace detail
24 : {
25 :
26 : template <template <class> class Builder, class ReplaceFunction>
27 : struct replace_aterm_builder: public Builder<replace_aterm_builder<Builder, ReplaceFunction> >
28 : {
29 : typedef Builder<replace_aterm_builder<Builder, ReplaceFunction> > super;
30 : using super::enter;
31 : using super::leave;
32 : using super::apply;
33 : using super::derived;
34 :
35 : ReplaceFunction f;
36 :
37 9 : replace_aterm_builder(ReplaceFunction f_)
38 5 : : f(f_)
39 9 : {}
40 :
41 : template <class T>
42 18 : void apply(T& result, const aterm_appl& x)
43 : {
44 18 : const T fx(f(x));
45 18 : if (x == fx)
46 : {
47 10 : super::apply(result, x);
48 : }
49 : else
50 : {
51 8 : result = fx;
52 : }
53 18 : }
54 : };
55 :
56 : template <template <class> class Builder, class ReplaceFunction>
57 : replace_aterm_builder<Builder, ReplaceFunction>
58 9 : make_replace_aterm_builder(ReplaceFunction f)
59 : {
60 9 : return replace_aterm_builder<Builder, ReplaceFunction>(f);
61 : }
62 :
63 : template <template <class> class Builder, class ReplaceFunction>
64 : struct partial_replace_aterm_builder: public Builder<partial_replace_aterm_builder<Builder, ReplaceFunction> >
65 : {
66 : typedef Builder<partial_replace_aterm_builder<Builder, ReplaceFunction> > super;
67 : using super::enter;
68 : using super::leave;
69 : using super::apply;
70 : using super::derived;
71 :
72 : ReplaceFunction f;
73 :
74 1 : partial_replace_aterm_builder(ReplaceFunction f_)
75 : : f(f_)
76 1 : {}
77 :
78 : template <class T>
79 1 : void apply(T& result, const aterm_appl& x)
80 : {
81 1 : std::pair<aterm_appl, bool> p = f(x);
82 1 : if (p.second)
83 : {
84 0 : super::apply(result, x);
85 : }
86 : else
87 : {
88 1 : result = p.first;
89 : }
90 1 : }
91 : };
92 :
93 : template <template <class> class Builder, class ReplaceFunction>
94 : partial_replace_aterm_builder<Builder, ReplaceFunction>
95 1 : make_partial_replace_aterm_builder(ReplaceFunction f)
96 : {
97 1 : return partial_replace_aterm_builder<Builder, ReplaceFunction>(f);
98 : }
99 :
100 : template <template <class> class Builder, class ReplaceFunction>
101 : struct bottom_up_replace_aterm_builder: public Builder<bottom_up_replace_aterm_builder<Builder, ReplaceFunction> >
102 : {
103 : typedef Builder<bottom_up_replace_aterm_builder<Builder, ReplaceFunction> > super;
104 : using super::enter;
105 : using super::leave;
106 : using super::apply;
107 : using super::derived;
108 :
109 : ReplaceFunction f;
110 :
111 20010 : bottom_up_replace_aterm_builder(ReplaceFunction f_)
112 20009 : : f(f_)
113 20010 : {}
114 :
115 : template <class T>
116 423463 : void apply(T& result, const aterm_appl& x)
117 : {
118 423463 : aterm_appl t;
119 423463 : super::apply(t, x);
120 423463 : result = static_cast<T>(f(t));
121 423463 : }
122 : };
123 :
124 : template <template <class> class Builder, class ReplaceFunction>
125 : bottom_up_replace_aterm_builder<Builder, ReplaceFunction>
126 20010 : make_bottom_up_replace_aterm_builder(ReplaceFunction f)
127 : {
128 20010 : return bottom_up_replace_aterm_builder<Builder, ReplaceFunction>(f);
129 : }
130 :
131 : template <template <class> class Builder, class ReplaceFunction>
132 : struct cached_bottom_up_replace_aterm_builder: public Builder<cached_bottom_up_replace_aterm_builder<Builder, ReplaceFunction> >
133 : {
134 : typedef Builder<cached_bottom_up_replace_aterm_builder<Builder, ReplaceFunction> > super;
135 : using super::enter;
136 : using super::leave;
137 : using super::apply;
138 : using super::derived;
139 :
140 : ReplaceFunction f;
141 : std::unordered_map<aterm_appl, aterm>& cache;
142 :
143 1 : cached_bottom_up_replace_aterm_builder(ReplaceFunction f_, std::unordered_map<aterm_appl, aterm>& cache_)
144 1 : : f(f_), cache(cache_)
145 1 : {}
146 :
147 : template <class T>
148 6 : void apply(T& result, const aterm_appl& x)
149 : {
150 6 : auto i = cache.find(x);
151 6 : if (i != cache.end())
152 : {
153 2 : result = i->second;
154 2 : return;
155 : }
156 4 : aterm t;
157 4 : super::apply(t, x);
158 4 : result = f(down_cast<aterm_appl>(t));
159 4 : cache[x] = result;
160 4 : }
161 : };
162 :
163 : template <template <class> class Builder, class ReplaceFunction>
164 : cached_bottom_up_replace_aterm_builder<Builder, ReplaceFunction>
165 1 : make_cached_bottom_up_replace_aterm_builder(ReplaceFunction f, std::unordered_map<aterm_appl, aterm>& cache)
166 : {
167 1 : return cached_bottom_up_replace_aterm_builder<Builder, ReplaceFunction>(f, cache);
168 : }
169 :
170 : } // namespace detail
171 :
172 : /// \brief Calls op(elem) for subterms of the term t.
173 : /// \param t A term
174 : /// \param op The operation that is applied to subterms
175 : /// \return a copy of the (internally modified) op.
176 : /// The function op must have the signature bool op(aterm_appl t).
177 : /// When op(t) is false, the children of t are skipped.
178 : template <typename UnaryFunction, typename Term>
179 1 : UnaryFunction for_each(Term t, UnaryFunction op)
180 : {
181 1 : return detail::for_each_impl< typename std::add_lvalue_reference< UnaryFunction >::type >(t, op);
182 : }
183 :
184 : /// \brief Finds a subterm of t that matches a given predicate.
185 : /// \param t A term
186 : /// \param match The predicate that determines if a subterm is a match
187 : /// \return A subterm that matches the given predicate, or aterm_appl() if none was found.
188 : template <typename Term, typename MatchPredicate>
189 1845 : aterm_appl find_if(const Term& t, MatchPredicate match)
190 : {
191 1845 : aterm_appl output;
192 1845 : detail::find_if_impl< typename std::add_lvalue_reference< MatchPredicate >::type >(t, match, output);
193 1845 : return output;
194 0 : }
195 :
196 : /// \brief Finds a subterm of t that matches a given predicate.
197 : /// The term is only partially traversed. If the stop predicate
198 : /// returns true in a subterm, the recursion is not continued.
199 : /// \param t A term
200 : /// \param match The predicate that determines if a subterm is a match
201 : /// \param stop The predicate that determines if the recursion should not be continued in a subterm
202 : /// \return A subterm that matches the given predicate, or aterm_appl() if none was found.
203 : template <typename Term, typename MatchPredicate, typename StopPredicate>
204 2 : aterm_appl partial_find_if(Term t, MatchPredicate match, StopPredicate stop)
205 : {
206 2 : return detail::partial_find_if_impl<typename std::add_lvalue_reference<MatchPredicate>::type>(t, match, stop);
207 : }
208 :
209 : /// \brief Finds all subterms of t that match a given predicate, and writes the found terms
210 : /// to the destination range starting with destBegin.
211 : /// \param t A term
212 : /// \param match The predicate that determines if a subterm is a match
213 : /// \param destBegin The iterator range to which output is written.
214 : template <typename Term, typename MatchPredicate, typename OutputIterator>
215 2 : void find_all_if(const Term& t, MatchPredicate match, OutputIterator destBegin)
216 : {
217 2 : OutputIterator i = destBegin; // we make a copy, since a reference to an iterator is needed
218 2 : detail::find_all_if_impl< typename std::add_lvalue_reference< MatchPredicate >::type >(t, match, i);
219 2 : }
220 :
221 : /// \brief Finds all subterms of t that match a given predicate, and writes the found terms
222 : /// to the destination range starting with destBegin.
223 : /// The term is only partially traversed. If the stop predicate
224 : /// returns true in a subterm, the recursion is not continued.
225 : /// \param t A term
226 : /// \param match The predicate that determines if a subterm is a match
227 : /// \param stop The predicate that determines if the recursion should not be continued in a subterm
228 : /// \param destBegin The iterator range to which output is written.
229 : template <typename Term, typename MatchPredicate, typename StopPredicate, typename OutputIterator>
230 : void partial_find_all_if(Term t, MatchPredicate match, StopPredicate stop, OutputIterator destBegin)
231 : {
232 : OutputIterator i = destBegin; // we make a copy, since a reference to an iterator is needed
233 : detail::partial_find_all_if_impl< typename std::add_lvalue_reference< MatchPredicate >::type,
234 : typename std::add_lvalue_reference< StopPredicate >::type >(t, match, stop, i);
235 : }
236 :
237 : /// \brief Replaces each subterm x of t by r(x). The ReplaceFunction r has
238 : /// the following signature:
239 : /// aterm_appl x;
240 : /// aterm_appl result = r(x);
241 : /// The replacements are performed in top down order.
242 : /// \param t A term
243 : /// \param r The replace function that is applied to subterms.
244 : /// \return The result of the replacement.
245 : template <typename Term, typename ReplaceFunction>
246 9 : Term replace(const Term& t, ReplaceFunction r)
247 : {
248 9 : Term result;
249 9 : detail::make_replace_aterm_builder<atermpp::builder>(r).apply(result,t);
250 9 : return result;
251 0 : }
252 :
253 : /// \brief Replaces each subterm in t that is equal to old_value with new_value.
254 : /// The replacements are performed in top down order. For example,
255 : /// replace(f(f(x)), f(x), x) returns f(x) and not x.
256 : /// \param t A term
257 : /// \param old_value The subterm that will be replaced.
258 : /// \param new_value The value that will be substituted.
259 : /// \return The result of the replacement.
260 : template <typename Term>
261 5 : Term replace(const Term& t, const aterm& old_value, const aterm& new_value)
262 : {
263 10 : return replace(t, [&](const aterm& t) { return t == old_value ? new_value : t; });
264 : }
265 :
266 : /// \brief Replaces each subterm x of t by r(x). The ReplaceFunction r has
267 : /// the following signature:
268 : /// aterm_appl x;
269 : /// aterm_appl result = r(x);
270 : /// The replacements are performed in bottom up order. For example,
271 : /// replace(f(f(x)), f(x), x) returns x.
272 : /// \param t A term
273 : /// \param r The replace function that is applied to subterms.
274 : /// \return The result of the replacement.
275 : template <typename Term, typename ReplaceFunction>
276 20010 : Term bottom_up_replace(Term t, ReplaceFunction r)
277 : {
278 20010 : Term result;
279 20010 : detail::make_bottom_up_replace_aterm_builder<atermpp::builder>(r).apply(result, t);
280 20010 : return result;
281 0 : }
282 :
283 : /// \brief Replaces each subterm in t that is equal to old_value with new_value.
284 : /// The replacements are performed in top down order. For example,
285 : /// replace(f(f(x)), f(x), x) returns f(x) and not x.
286 : /// \param t A term
287 : /// \param old_value The value of the subterm that is replaced.
288 : /// \param new_value The value that is substituted.
289 : /// \return The result of the replacement.
290 : template <typename Term>
291 1 : Term bottom_up_replace(Term t, const aterm_appl& old_value, const aterm_appl& new_value)
292 : {
293 4 : return bottom_up_replace(t, [&](const aterm& t) { return t == old_value ? new_value : t; });
294 : }
295 :
296 : /// \brief Replaces subterms x of t by r(x). The replace function r returns an
297 : /// additional boolean value. This value is used to prevent further recursion.
298 : /// The ReplaceFunction r has the following signature:
299 : /// aterm_appl x;
300 : /// std::pair<aterm_appl, bool> result = r(x);
301 : /// result.first is the result r(x) of the replacement
302 : /// result.second denotes if the recursion should be continued
303 : /// The replacements are performed in top down order.
304 : /// \param t A term
305 : /// \param r The replace function that is applied to subterms.
306 : /// \return The result of the replacement.
307 : template <typename Term, typename ReplaceFunction>
308 1 : Term partial_replace(Term t, ReplaceFunction r)
309 : {
310 1 : Term result;
311 1 : detail::make_partial_replace_aterm_builder<atermpp::builder>(r).apply(result, t);
312 1 : return result;
313 0 : }
314 :
315 : /// \brief Replaces each subterm x of t by r(x). The ReplaceFunction r has
316 : /// the following signature:
317 : /// aterm_appl x;
318 : /// aterm_appl result = r(x);
319 : /// The replacements are performed in bottom up order. For example,
320 : /// replace(f(f(x)), f(x), x) returns x.
321 : /// \param t A term
322 : /// \param r The replace function that is applied to subterms.
323 : /// \param cache A cache for the result of aterm_appl terms.
324 : /// \return The result of the replacement.
325 : template <typename Term, typename ReplaceFunction>
326 1 : Term bottom_up_replace(Term t, ReplaceFunction r, std::unordered_map<aterm_appl, aterm>& cache)
327 : {
328 1 : Term result;
329 1 : detail::make_cached_bottom_up_replace_aterm_builder<atermpp::builder>(r, cache).apply(result, t);
330 1 : return result;
331 0 : }
332 :
333 : } // namespace atermpp
334 :
335 : #endif // MCRL2_ATERMPP_ALGORITHM_H
|
