algorithm.h

Go to the documentation of this file.

// Author(s): Wieger Wesselink
// Copyright: see the accompanying file COPYING or copy at
// https://github.com/mCRL2org/mCRL2/blob/master/COPYING
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//
 
#ifndef MCRL2_ATERMPP_ALGORITHM_H
#define MCRL2_ATERMPP_ALGORITHM_H
 
#include <unordered_map>
 
#include "mcrl2/atermpp/builder.h"
#include "mcrl2/atermpp/detail/algorithm_impl.h"
 
namespace atermpp
{
 
namespace detail
{
 
template <template <class> class Builder, class ReplaceFunction>
struct replace_aterm_builder: public Builder<replace_aterm_builder<Builder, ReplaceFunction> >
{
  typedef Builder<replace_aterm_builder<Builder, ReplaceFunction> > super;
  using super::enter;
  using super::leave;
  using super::apply;
  using super::derived;
 
  ReplaceFunction f;
 
  replace_aterm_builder(ReplaceFunction f_)
    : f(f_)
  {}
 
  template <class T>
  void apply(T& result, const aterm& x)
  {
    const T fx(f(x));
    if (x == fx) 
    {
      super::apply(result, x); 
    }
    else 
    {
      result = fx;
    }
  }
};
 
template <template <class> class Builder, class ReplaceFunction>
replace_aterm_builder<Builder, ReplaceFunction>
make_replace_aterm_builder(ReplaceFunction f)
{
  return replace_aterm_builder<Builder, ReplaceFunction>(f);
}
 
template <template <class> class Builder, class ReplaceFunction>
struct partial_replace_aterm_builder: public Builder<partial_replace_aterm_builder<Builder, ReplaceFunction> >
{
  typedef Builder<partial_replace_aterm_builder<Builder, ReplaceFunction> > super;
  using super::enter;
  using super::leave;
  using super::apply;
  using super::derived;
 
  ReplaceFunction f;
 
  partial_replace_aterm_builder(ReplaceFunction f_)
    : f(f_)
  {}
 
  template <class T>
  void apply(T& result, const aterm& x)
  {
    std::pair<aterm, bool> p = f(x);
    if (p.second)
    { 
      super::apply(result, x);
    } 
    else 
    {
      result = p.first;
    }
  }
};
 
template <template <class> class Builder, class ReplaceFunction>
partial_replace_aterm_builder<Builder, ReplaceFunction>
make_partial_replace_aterm_builder(ReplaceFunction f)
{
  return partial_replace_aterm_builder<Builder, ReplaceFunction>(f);
}
 
template <template <class> class Builder, class ReplaceFunction>
struct bottom_up_replace_aterm_builder: public Builder<bottom_up_replace_aterm_builder<Builder, ReplaceFunction> >
{
  typedef Builder<bottom_up_replace_aterm_builder<Builder, ReplaceFunction> > super;
  using super::enter;
  using super::leave;
  using super::apply;
  using super::derived;
 
  ReplaceFunction f;
 
  bottom_up_replace_aterm_builder(ReplaceFunction f_)
    : f(f_)
  {}
 
  template <class T>
  void apply(T& result, const aterm& x)
  {
    aterm t;
    super::apply(t, x);
    result = static_cast<T>(f(t));
  }
};
 
template <template <class> class Builder, class ReplaceFunction>
bottom_up_replace_aterm_builder<Builder, ReplaceFunction>
make_bottom_up_replace_aterm_builder(ReplaceFunction f)
{
  return bottom_up_replace_aterm_builder<Builder, ReplaceFunction>(f);
}
 
template <template <class> class Builder, class ReplaceFunction>
struct cached_bottom_up_replace_aterm_builder: public Builder<cached_bottom_up_replace_aterm_builder<Builder, ReplaceFunction> >
{
  typedef Builder<cached_bottom_up_replace_aterm_builder<Builder, ReplaceFunction> > super;
  using super::enter;
  using super::leave;
  using super::apply;
  using super::derived;
 
  ReplaceFunction f;
  std::unordered_map<aterm, aterm>& cache;
 
  cached_bottom_up_replace_aterm_builder(ReplaceFunction f_, std::unordered_map<aterm, aterm>& cache_)
    : f(f_), cache(cache_)
  {}
 
  template <class T>
  void apply(T& result, const aterm& x)
  {
    auto i = cache.find(x);
    if (i != cache.end())
    {
      result = i->second;
      return;
    }
    aterm t;
    super::apply(t, x);
    result = f(t);
    cache[x] = result;
  }
};
 
template <template <class> class Builder, class ReplaceFunction>
cached_bottom_up_replace_aterm_builder<Builder, ReplaceFunction>
make_cached_bottom_up_replace_aterm_builder(ReplaceFunction f, std::unordered_map<aterm, aterm>& cache)
{
  return cached_bottom_up_replace_aterm_builder<Builder, ReplaceFunction>(f, cache);
}
 
} // namespace detail
 
template <typename UnaryFunction, typename Term>
UnaryFunction for_each(Term t, UnaryFunction op)
{
  return detail::for_each_impl< typename std::add_lvalue_reference< UnaryFunction >::type >(t, op);
}
 
template <typename Term, typename MatchPredicate>
aterm find_if(const Term& t, MatchPredicate match)
{
  aterm output;
  detail::find_if_impl< typename std::add_lvalue_reference< MatchPredicate >::type >(t, match, output);
  return output;
}
 
template <typename Term, typename MatchPredicate, typename StopPredicate>
aterm partial_find_if(Term t, MatchPredicate match, StopPredicate stop)
{
  return detail::partial_find_if_impl<typename std::add_lvalue_reference<MatchPredicate>::type>(t, match, stop);
}
 
template <typename Term, typename MatchPredicate, typename OutputIterator>
void find_all_if(const Term& t, MatchPredicate match, OutputIterator destBegin)
{
  OutputIterator i = destBegin; // we make a copy, since a reference to an iterator is needed
  detail::find_all_if_impl< typename std::add_lvalue_reference< MatchPredicate >::type >(t, match, i);
}
 
template <typename Term, typename MatchPredicate, typename StopPredicate, typename OutputIterator>
void partial_find_all_if(Term t, MatchPredicate match, StopPredicate stop, OutputIterator destBegin)
{
  OutputIterator i = destBegin; // we make a copy, since a reference to an iterator is needed
  detail::partial_find_all_if_impl< typename std::add_lvalue_reference< MatchPredicate >::type,
         typename std::add_lvalue_reference< StopPredicate >::type >(t, match, stop, i);
}
 
template <typename Term, typename ReplaceFunction>
Term replace(const Term& t, ReplaceFunction r)
{
  Term result;
  detail::make_replace_aterm_builder<atermpp::builder>(r).apply(result,t);
  return result;
}
 
template <typename Term>
Term replace(const Term& t, const aterm& old_value, const aterm& new_value)
{
  return replace(t, [&](const aterm& t) { return t == old_value ? new_value : t; });
}
 
template <typename Term, typename ReplaceFunction>
Term bottom_up_replace(Term t, ReplaceFunction r)
{
  Term result;
  detail::make_bottom_up_replace_aterm_builder<atermpp::builder>(r).apply(result, t);
  return result;
}
 
template <typename Term>
Term bottom_up_replace(Term t, const aterm& old_value, const aterm& new_value)
{
  return bottom_up_replace(t, [&](const aterm& t) { return t == old_value ? new_value : t; });
}
 
template <typename Term, typename ReplaceFunction>
Term partial_replace(Term t, ReplaceFunction r)
{
  Term result;
  detail::make_partial_replace_aterm_builder<atermpp::builder>(r).apply(result, t);
  return result;
}
 
template <typename Term, typename ReplaceFunction>
Term bottom_up_replace(Term t, ReplaceFunction r, std::unordered_map<aterm, aterm>& cache)
{
  Term result;
  detail::make_cached_bottom_up_replace_aterm_builder<atermpp::builder>(r, cache).apply(result, t);
  return result;
}
 
} // namespace atermpp
 
#endif // MCRL2_ATERMPP_ALGORITHM_H