mCRL2
Searching...
No Matches
algorithm.h
Go to the documentation of this file.
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//
6// (See accompanying file LICENSE_1_0.txt or copy at
8//
11
12#ifndef MCRL2_ATERMPP_ALGORITHM_H
13#define MCRL2_ATERMPP_ALGORITHM_H
14
15#include <unordered_map>
16
19
20namespace atermpp
21{
22
23namespace detail
24{
25
26template <template <class> class Builder, class ReplaceFunction>
27struct 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 replace_aterm_builder(ReplaceFunction f_)
38 : f(f_)
39 {}
40
41 template <class T>
42 void apply(T& result, const aterm_appl& x)
43 {
44 const T fx(f(x));
45 if (x == fx)
46 {
47 super::apply(result, x);
48 }
49 else
50 {
51 result = fx;
52 }
53 }
54};
55
56template <template <class> class Builder, class ReplaceFunction>
57replace_aterm_builder<Builder, ReplaceFunction>
59{
61}
62
63template <template <class> class Builder, class ReplaceFunction>
64struct 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
75 : f(f_)
76 {}
77
78 template <class T>
79 void apply(T& result, const aterm_appl& x)
80 {
81 std::pair<aterm_appl, bool> p = f(x);
82 if (p.second)
83 {
84 super::apply(result, x);
85 }
86 else
87 {
88 result = p.first;
89 }
90 }
91};
92
93template <template <class> class Builder, class ReplaceFunction>
94partial_replace_aterm_builder<Builder, ReplaceFunction>
96{
98}
99
100template <template <class> class Builder, class ReplaceFunction>
101struct 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
112 : f(f_)
113 {}
114
115 template <class T>
116 void apply(T& result, const aterm_appl& x)
117 {
118 aterm_appl t;
119 super::apply(t, x);
120 result = static_cast<T>(f(t));
121 }
122};
123
124template <template <class> class Builder, class ReplaceFunction>
125bottom_up_replace_aterm_builder<Builder, ReplaceFunction>
127{
129}
130
131template <template <class> class Builder, class ReplaceFunction>
132struct 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 cached_bottom_up_replace_aterm_builder(ReplaceFunction f_, std::unordered_map<aterm_appl, aterm>& cache_)
144 : f(f_), cache(cache_)
145 {}
146
147 template <class T>
148 void apply(T& result, const aterm_appl& x)
149 {
150 auto i = cache.find(x);
151 if (i != cache.end())
152 {
153 result = i->second;
154 return;
155 }
156 aterm t;
157 super::apply(t, x);
158 result = f(down_cast<aterm_appl>(t));
159 cache[x] = result;
160 }
161};
162
163template <template <class> class Builder, class ReplaceFunction>
164cached_bottom_up_replace_aterm_builder<Builder, ReplaceFunction>
165make_cached_bottom_up_replace_aterm_builder(ReplaceFunction f, std::unordered_map<aterm_appl, aterm>& cache)
166{
168}
169
170} // namespace detail
171
178template <typename UnaryFunction, typename Term>
179UnaryFunction for_each(Term t, UnaryFunction op)
180{
181 return detail::for_each_impl< typename std::add_lvalue_reference< UnaryFunction >::type >(t, op);
182}
183
188template <typename Term, typename MatchPredicate>
189aterm_appl find_if(const Term& t, MatchPredicate match)
190{
191 aterm_appl output;
192 detail::find_if_impl< typename std::add_lvalue_reference< MatchPredicate >::type >(t, match, output);
193 return output;
194}
195
203template <typename Term, typename MatchPredicate, typename StopPredicate>
204aterm_appl partial_find_if(Term t, MatchPredicate match, StopPredicate stop)
205{
206 return detail::partial_find_if_impl<typename std::add_lvalue_reference<MatchPredicate>::type>(t, match, stop);
207}
208
214template <typename Term, typename MatchPredicate, typename OutputIterator>
215void find_all_if(const Term& t, MatchPredicate match, OutputIterator destBegin)
216{
217 OutputIterator i = destBegin; // we make a copy, since a reference to an iterator is needed
218 detail::find_all_if_impl< typename std::add_lvalue_reference< MatchPredicate >::type >(t, match, i);
219}
220
229template <typename Term, typename MatchPredicate, typename StopPredicate, typename OutputIterator>
230void 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
245template <typename Term, typename ReplaceFunction>
246Term replace(const Term& t, ReplaceFunction r)
247{
248 Term result;
249 detail::make_replace_aterm_builder<atermpp::builder>(r).apply(result,t);
250 return result;
251}
252
260template <typename Term>
261Term replace(const Term& t, const aterm& old_value, const aterm& new_value)
262{
263 return replace(t, [&](const aterm& t) { return t == old_value ? new_value : t; });
264}
265
275template <typename Term, typename ReplaceFunction>
276Term bottom_up_replace(Term t, ReplaceFunction r)
277{
278 Term result;
279 detail::make_bottom_up_replace_aterm_builder<atermpp::builder>(r).apply(result, t);
280 return result;
281}
282
290template <typename Term>
291Term bottom_up_replace(Term t, const aterm_appl& old_value, const aterm_appl& new_value)
292{
293 return bottom_up_replace(t, [&](const aterm& t) { return t == old_value ? new_value : t; });
294}
295
307template <typename Term, typename ReplaceFunction>
308Term partial_replace(Term t, ReplaceFunction r)
309{
310 Term result;
311 detail::make_partial_replace_aterm_builder<atermpp::builder>(r).apply(result, t);
312 return result;
313}
314
325template <typename Term, typename ReplaceFunction>
326Term bottom_up_replace(Term t, ReplaceFunction r, std::unordered_map<aterm_appl, aterm>& cache)
327{
328 Term result;
329 detail::make_cached_bottom_up_replace_aterm_builder<atermpp::builder>(r, cache).apply(result, t);
330 return result;
331}
332
333} // namespace atermpp
334
335#endif // MCRL2_ATERMPP_ALGORITHM_H
Implementations of algorithms.
The aterm base class that provides protection of the underlying shared terms.
Definition aterm.h:186
cached_bottom_up_replace_aterm_builder< Builder, ReplaceFunction > make_cached_bottom_up_replace_aterm_builder(ReplaceFunction f, std::unordered_map< aterm_appl, aterm > &cache)
Definition algorithm.h:165
replace_aterm_builder< Builder, ReplaceFunction > make_replace_aterm_builder(ReplaceFunction f)
Definition algorithm.h:58
partial_replace_aterm_builder< Builder, ReplaceFunction > make_partial_replace_aterm_builder(ReplaceFunction f)
Definition algorithm.h:95
bottom_up_replace_aterm_builder< Builder, ReplaceFunction > make_bottom_up_replace_aterm_builder(ReplaceFunction f)
Definition algorithm.h:126
The main namespace for the aterm++ library.
Definition algorithm.h:21
Term replace(const Term &t, ReplaceFunction r)
Replaces each subterm x of t by r(x). The ReplaceFunction r has the following signature: aterm_appl x...
Definition algorithm.h:246
void partial_find_all_if(Term t, MatchPredicate match, StopPredicate stop, OutputIterator destBegin)
Finds all subterms of t that match a given predicate, and writes the found terms to the destination r...
Definition algorithm.h:230
aterm_appl partial_find_if(Term t, MatchPredicate match, StopPredicate stop)
Finds a subterm of t that matches a given predicate. The term is only partially traversed....
Definition algorithm.h:204
aterm_appl find_if(const Term &t, MatchPredicate match)
Finds a subterm of t that matches a given predicate.
Definition algorithm.h:189
UnaryFunction for_each(Term t, UnaryFunction op)
Calls op(elem) for subterms of the term t.
Definition algorithm.h:179
void find_all_if(const Term &t, MatchPredicate match, OutputIterator destBegin)
Finds all subterms of t that match a given predicate, and writes the found terms to the destination r...
Definition algorithm.h:215
Term partial_replace(Term t, ReplaceFunction r)
Replaces subterms x of t by r(x). The replace function r returns an additional boolean value....
Definition algorithm.h:308
Term bottom_up_replace(Term t, ReplaceFunction r)
Replaces each subterm x of t by r(x). The ReplaceFunction r has the following signature: aterm_appl x...
Definition algorithm.h:276
void apply(T &result, const aterm_appl &x)
Definition algorithm.h:116
Builder< bottom_up_replace_aterm_builder< Builder, ReplaceFunction > > super
Definition algorithm.h:103
cached_bottom_up_replace_aterm_builder(ReplaceFunction f_, std::unordered_map< aterm_appl, aterm > &cache_)
Definition algorithm.h:143
void apply(T &result, const aterm_appl &x)
Definition algorithm.h:148
std::unordered_map< aterm_appl, aterm > & cache
Definition algorithm.h:141
Builder< cached_bottom_up_replace_aterm_builder< Builder, ReplaceFunction > > super
Definition algorithm.h:134
Builder< partial_replace_aterm_builder< Builder, ReplaceFunction > > super
Definition algorithm.h:66
void apply(T &result, const aterm_appl &x)
Definition algorithm.h:79
void apply(T &result, const aterm_appl &x)
Definition algorithm.h:42
replace_aterm_builder(ReplaceFunction f_)
Definition algorithm.h:37
Builder< replace_aterm_builder< Builder, ReplaceFunction > > super
Definition algorithm.h:29