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/detail/algorithm_impl.h
10 : /// \brief Implementations of algorithms.
11 :
12 : #ifndef MCRL2_ATERMPP_DETAIL_ALGORITHM_IMPL_H
13 : #define MCRL2_ATERMPP_DETAIL_ALGORITHM_IMPL_H
14 :
15 : #include "mcrl2/atermpp/aterm_list.h"
16 :
17 : namespace atermpp
18 : {
19 :
20 : namespace detail
21 : {
22 : /// \brief Applies the function f to all children of a.
23 : /// \param a A term
24 : /// \param f A function on terms
25 : /// \return The transformed term
26 : template <typename Term, typename Function>
27 : aterm_appl appl_apply(const term_appl<Term>& a, const Function f)
28 : {
29 : return term_appl<Term>(a.function(), a.begin(), a.end(), f);
30 : }
31 :
32 : //--- find ----------------------------------------------------------------//
33 :
34 : // we need to use our own traits classes to extract the value type from insert iterators
35 : template <class Iterator>
36 : struct iterator_value
37 : {
38 : typedef typename std::iterator_traits<Iterator>::value_type type;
39 : };
40 :
41 : template <class Container>
42 : struct iterator_value<std::insert_iterator<Container> >
43 : {
44 : typedef typename Container::value_type type;
45 : };
46 :
47 : template <class Container>
48 : struct iterator_value<std::back_insert_iterator<Container> >
49 : {
50 : typedef typename Container::value_type type;
51 : };
52 :
53 : template <class Container>
54 : struct iterator_value<std::front_insert_iterator<Container> >
55 : {
56 : typedef typename Container::value_type type;
57 : };
58 :
59 : /// \internal
60 : // used to abort the recursive find
61 : struct found_term_exception
62 : {
63 : aterm_appl t;
64 :
65 : found_term_exception(const aterm_appl& t_)
66 : : t(t_)
67 : {}
68 : };
69 :
70 : /// \brief Implements the for_each algorithm
71 : /// \param t A term
72 : /// \param op A unary function on terms
73 : /// \return The result of the algorithm
74 : template <typename UnaryFunction>
75 5 : UnaryFunction for_each_impl(aterm t, UnaryFunction op)
76 : {
77 5 : if (t.type_is_list())
78 : {
79 0 : const aterm_list& l = down_cast<aterm_list>(t);
80 0 : for (const aterm& x: l)
81 : {
82 0 : for_each_impl(x, op);
83 : }
84 : }
85 5 : else if (t.type_is_appl())
86 : {
87 5 : const aterm_appl& a = down_cast<aterm_appl>(t);
88 5 : if (op(t))
89 : {
90 14 : for (const aterm& x: a)
91 : {
92 4 : for_each_impl(x, op);
93 : }
94 : }
95 : }
96 5 : return op;
97 : }
98 :
99 : /// \brief Implements the find_if algorithm
100 : /// If the term t is found, it is stored in output and true is returned
101 : /// \param t A term
102 : /// \param match A predicate function on terms
103 : /// \param output The variable to store the match in
104 : /// \return true if a match was found, false otherwise
105 : template <typename MatchPredicate>
106 47471 : bool find_if_impl(const aterm& t, MatchPredicate match, aterm_appl& output)
107 : {
108 47471 : if (t.type_is_appl())
109 : {
110 42236 : const aterm_appl& a = down_cast<aterm_appl>(t);
111 42236 : if (match(a))
112 : {
113 1556 : output = a;
114 1556 : return true;
115 : }
116 115706 : for (const aterm& x: a)
117 : {
118 40358 : if (find_if_impl(x, match, output))
119 6012 : return true;
120 : }
121 : }
122 5235 : else if (t.type_is_list())
123 : {
124 2971 : const aterm_list& l = down_cast<aterm_list>(t);
125 11210 : for (const aterm& x: l)
126 : {
127 5268 : if (find_if_impl(x, match, output))
128 : {
129 0 : return true;
130 : }
131 : }
132 : }
133 39903 : return false;
134 : }
135 :
136 : /// \brief Implements the find_all_if algorithm
137 : /// \param t A term
138 : /// \param op A predicate function on terms
139 : /// \param destBegin The beginning of a range to where the results are written
140 : template <typename MatchPredicate, typename OutputIterator>
141 24 : void find_all_if_impl(const aterm& t, MatchPredicate op, OutputIterator& destBegin)
142 : {
143 : typedef typename iterator_value<OutputIterator>::type value_type;
144 :
145 24 : if (t.type_is_list())
146 : {
147 0 : const aterm_list& l = down_cast<aterm_list>(t);
148 0 : for (const aterm& x: l)
149 : {
150 0 : find_all_if_impl<MatchPredicate>(x, op, destBegin);
151 : }
152 : }
153 24 : else if (t.type_is_appl())
154 : {
155 24 : const aterm_appl& a = down_cast<aterm_appl>(t);
156 24 : if (op(a))
157 : {
158 4 : *destBegin++ = vertical_cast<value_type>(a);
159 : }
160 70 : for (const aterm& x: a)
161 : {
162 22 : find_all_if_impl<MatchPredicate>(x, op, destBegin);
163 : }
164 : }
165 : else
166 : {
167 0 : return;
168 : }
169 : }
170 :
171 : //--- partial find --------------------------------------------------------//
172 :
173 : /// \brief Implements the partial_find_if_impl algorithm
174 : /// \param t A term
175 : /// \param match A predicate function on terms
176 : /// \param stop A predicate function on terms
177 : template <typename MatchPredicate, typename StopPredicate>
178 8 : aterm_appl partial_find_if_impl(const aterm& t, MatchPredicate match, StopPredicate stop)
179 : {
180 8 : if (t.type_is_appl())
181 : {
182 8 : const aterm_appl& a = down_cast<aterm_appl>(t);
183 8 : if (match(a))
184 : {
185 1 : return a; // report the match
186 : }
187 7 : if (stop(a))
188 : {
189 2 : return aterm_appl(); // nothing was found
190 : }
191 20 : for (const aterm& x: a)
192 : {
193 6 : aterm_appl result = partial_find_if_impl<MatchPredicate, StopPredicate>(x, match, stop);
194 6 : if (result != aterm_appl())
195 : {
196 2 : return result;
197 : }
198 : }
199 : }
200 :
201 3 : if (t.type_is_list())
202 : {
203 0 : const aterm_list& l = down_cast<aterm_list>(t);
204 0 : for (const aterm& x: l)
205 : {
206 0 : aterm_appl result = partial_find_if_impl<MatchPredicate, StopPredicate>(x, match, stop);
207 0 : if (result != aterm_appl())
208 : {
209 0 : return result;
210 : }
211 : }
212 : }
213 3 : return aterm_appl();
214 : }
215 :
216 : /// \brief Implements the partial_find_all_if algorithm
217 : /// \param t A term
218 : /// \param match A predicate function on terms
219 : /// \param stop A predicate function on terms
220 : /// \param destBegin The beginning of a range to where the results are written
221 : template <typename MatchPredicate, typename StopPredicate, typename OutputIterator>
222 : void partial_find_all_if_impl(const aterm& t, MatchPredicate match, StopPredicate stop, OutputIterator& destBegin)
223 : {
224 : if (t.type_is_appl())
225 : {
226 : const aterm_appl& a = down_cast<aterm_appl>(t);
227 : if (match(a))
228 : {
229 : *destBegin++ = down_cast<aterm_appl>(t);
230 : }
231 : if (stop(a))
232 : {
233 : return;
234 : }
235 : for (const aterm& x: a)
236 : {
237 : partial_find_all_if_impl<MatchPredicate, StopPredicate>(x, match, stop, destBegin);
238 : }
239 : }
240 :
241 : if (t.type_is_list())
242 : {
243 : const aterm_list& l = down_cast<aterm_list>(t);
244 : for (const aterm& x: l)
245 : {
246 : partial_find_all_if_impl<MatchPredicate, StopPredicate>(x, match, stop, destBegin);
247 : }
248 : }
249 : }
250 :
251 : } // namespace detail
252 :
253 : } // namespace atermpp
254 :
255 : #endif // MCRL2_ATERMPP_DETAIL_ALGORITHM_IMPL_H
|
