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/utilities/detail/join.h
      10             : /// \brief Generic join and split functions.
      11             : 
      12             : #ifndef MCRL2_UTILITIES_DETAIL_JOIN_H
      13             : #define MCRL2_UTILITIES_DETAIL_JOIN_H
      14             : 
      15             : #include <iterator>
      16             : 
      17             : namespace mcrl2
      18             : {
      19             : 
      20             : namespace utilities
      21             : {
      22             : 
      23             : namespace detail
      24             : {
      25             : 
      26             : /// \brief Splits a binary tree T into a sequence, and writes the result to the output range
      27             : /// given by an output iterator.
      28             : /// \param t The tree that has to be split.
      29             : /// \param i The output iterator.
      30             : /// \param match If this functions returns true in a node, the node will be split.
      31             : /// \param lhs Function for getting the left subtree of a node.
      32             : /// \param rhs Function for getting the right subtree of a node.
      33             : template <typename T, typename OutputIterator, typename MatchFunction, typename AccessorFunction1, typename AccessorFunction2>
      34       13235 : void split(const T& t, OutputIterator i, MatchFunction match, AccessorFunction1 lhs, AccessorFunction2 rhs)
      35             : {
      36       13235 :   if (match(t))
      37             :   {
      38        4984 :     split(lhs(t), i, match, lhs, rhs);
      39        4984 :     split(rhs(t), i, match, lhs, rhs);
      40             :   }
      41             :   else
      42             :   {
      43        8251 :     *i++ = t;
      44             :   }
      45       13235 : }
      46             : 
      47             : /// \brief Given a sequence [t1, t2, ..., tn] of elements of type T, returns
      48             : /// op(t1, op(t2, ...), tn)))).
      49             : /// \param empty_sequence_result The value that is returned when the sequence is empty.
      50             : /// \param first [first, last) is the range of elements.
      51             : /// \param last
      52             : /// \param op An operator
      53             : /// \return The joined sequence
      54             : template <typename T, typename FwdIt, typename BinaryOperation>
      55        3858 : T join(FwdIt first, FwdIt last, BinaryOperation op, T empty_sequence_result)
      56             : {
      57        3858 :   if (first == last)
      58             :   {
      59        1705 :     return empty_sequence_result;
      60             :   }
      61        2153 :   T result = *first++;
      62        5531 :   while (first != last)
      63             :   {
      64        3378 :     result = op(result, *first++);
      65             :   }
      66        2153 :   return result;
      67        2153 : }
      68             : 
      69             : /// \brief Given a non-empty sequence [t1, t2, ..., tn] of elements of type T, returns
      70             : /// op(op(t1, op(t2, ...), tn)))). The height of the resulting expression tree is minimal.
      71             : /// \param first [first, last) is the range of elements.
      72             : /// \param last
      73             : /// \param op An operator
      74             : /// \return The joined sequence
      75             : template <typename T, typename RndIt, typename BinaryOperation>
      76         127 : T join_balanced(RndIt first, RndIt last, BinaryOperation op)
      77             : {
      78         127 :   auto n = std::distance(first, last);
      79         127 :   if (n == 1)
      80             :   {
      81          27 :     return *first;
      82             :   }
      83         100 :   if (n == 2)
      84             :   {
      85          37 :     return op(*first, *(first + 1));
      86             :   }
      87          63 :   auto d = n / 2;
      88          63 :   auto left = join_balanced<T, RndIt, BinaryOperation>(first, first + d, op);
      89          63 :   auto right = join_balanced<T, RndIt, BinaryOperation>(first + d, last, op);
      90          63 :   return op(left, right);
      91          63 : }
      92             : 
      93             : } // namespace detail
      94             : 
      95             : } // namespace utilities
      96             : 
      97             : } // namespace mcrl2
      98             : 
      99             : #endif // MCRL2_UTILITIES_DETAIL_JOIN_H