LCOV - code coverage report
Current view: top level - atermpp/include/mcrl2/atermpp - algorithm.h (source / functions) Hit Total Coverage
Test: mcrl2_coverage.info.cleaned Lines: 58 58 100.0 %
Date: 2020-02-13 00:44:47 Functions: 57 60 95.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13