join.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_UTILITIES_DETAIL_JOIN_H
#define MCRL2_UTILITIES_DETAIL_JOIN_H
 
#include <iterator>
 
namespace mcrl2
{
 
namespace utilities
{
 
namespace detail
{
 
template <typename T, typename OutputIterator, typename MatchFunction, typename AccessorFunction1, typename AccessorFunction2>
void split(const T& t, OutputIterator i, MatchFunction match, AccessorFunction1 lhs, AccessorFunction2 rhs)
{
  if (match(t))
  {
    split(lhs(t), i, match, lhs, rhs);
    split(rhs(t), i, match, lhs, rhs);
  }
  else
  {
    *i++ = t;
  }
}
 
template <typename T, typename FwdIt, typename BinaryOperation>
T join(FwdIt first, FwdIt last, BinaryOperation op, T empty_sequence_result)
{
  if (first == last)
  {
    return empty_sequence_result;
  }
  T result = *first++;
  while (first != last)
  {
    result = op(result, *first++);
  }
  return result;
}
 
template <typename T, typename RndIt, typename BinaryOperation>
T join_balanced(RndIt first, RndIt last, BinaryOperation op)
{
  auto n = std::distance(first, last);
  if (n == 1)
  {
    return *first;
  }
  if (n == 2)
  {
    return op(*first, *(first + 1));
  }
  auto d = n / 2;
  auto left = join_balanced<T, RndIt, BinaryOperation>(first, first + d, op);
  auto right = join_balanced<T, RndIt, BinaryOperation>(first + d, last, op);
  return op(left, right);
}
 
} // namespace detail
 
} // namespace utilities
 
} // namespace mcrl2
 
#endif // MCRL2_UTILITIES_DETAIL_JOIN_H