generator.hpp

// Copyright 2020 Arnaud Becheler    <abechele@umich.edu>
 
/*********************************************************************** * This program is free software; you can
 *redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free
 *Software Foundation; either version 2 of the License, or    * (at your option) any later version. *
 *                                                                      *
 ***************************************************************************/
 
#pragma once
 
#include <algorithm>
#include <concepts>
#include <regex>
#include <stdexcept>
#include <string>
#include <string_view>
 
#include "quetzal/coalescence/graph/k_ary_tree.hpp"
#include <boost/graph/depth_first_search.hpp>
 
namespace quetzal::format::newick
{
 
namespace detail
{
// Replacement for `std::function<T(U)>::argument_type`
template <typename T> struct single_function_argument;
 
template <typename Ret, typename Arg> struct single_function_argument<std::function<Ret(Arg)>>
{
    using type = Arg;
};
 
template <typename P1> struct single_function_argument_impl
{
    using type = typename single_function_argument<decltype(std::function{std::declval<P1>()})>::type;
};
 
template <typename P1> using single_function_argument_t = typename single_function_argument_impl<P1>::type;
 
struct parenthesis
{
};
 
struct square_bracket
{
};
 
bool check_if_balanced(std::string_view input, const char &open = '(', const char &close = ')')
{
    int count = 0;
    for (const auto &ch : input)
    {
        if (ch == open)
            count++;
        if (ch == close)
            count--;
        // if a parenthesis is closed without being opened return false
        if (count < 0)
            return false;
    }
    // in the end the test is passed only if count is zero
    return count == 0;
}
 
struct identity
{
    static std::string edit(const std::string s)
    {
        return s;
    }
};
 
template <class tag> struct is_balanced
{
};
 
template <> struct is_balanced<detail::parenthesis>
{
    static bool check(std::string_view s)
    {
        return check_if_balanced(s, '(', ')');
    }
};
 
template <> struct is_balanced<detail::square_bracket>
{
    static bool check(std::string_view s)
    {
        return check_if_balanced(s, '[', ']');
    }
};
} // namespace detail
 
using namespace std::string_literals;
 
static inline std::vector<std::string> forbidden_labels = {" "s, ","s, ";"s, "("s, ")"s, "["s, "]"s};
 
static inline constexpr char blank = '_';
 
template <unsigned int N> struct remove_comments_of_depth
{
};
 
template <> struct remove_comments_of_depth<0> : detail::identity
{
};
 
template <> struct remove_comments_of_depth<1>
{
    static std::string edit(const std::string s)
    {
        if (s.empty())
            return s;
        return std::regex_replace(s, std::regex(R"(\[[^()]*\])"), "");
    }
};
 
template <> struct remove_comments_of_depth<2>
{
    static std::string edit(const std::string s)
    {
        std::string buffer;
        int counter = 0;
        for (const auto &ch : s)
        {
            if (ch == '[')
                counter++;
            if (ch == ']')
                counter--;
            if (ch == '[' && counter == 2)
                continue; // do nothing, that was the opening
            if (ch == ']' && counter == 1)
                continue; // do nothing, that was the closing
            if (!(counter >= 2 || (counter == 1 && ch == ']')))
                buffer.append(std::string(1, ch));
        }
        return buffer;
    }
};
 
struct PAUP
{
    // return empty string
    static inline std::string root_branch_length()
    {
        return "";
    }
    // do nothing
    static inline std::string treat_comments(std::string &s)
    {
        return s;
    }
};
 
struct TreeAlign
{
    // Set explicit null branch length for root node
    static inline std::string root_branch_length()
    {
        return ":0.0";
    }
    // Remove comments that are nested, keep comments of depth 1
    static inline std::string treat_comments(const std::string s)
    {
        return remove_comments_of_depth<2>::edit(s);
    }
};
 
struct PHYLIP
{
    // Branch length for root node is not explicit.
    static inline std::string root_branch_length()
    {
        return "";
    }
    // Remove comments that are nested, keep comments of depth 1
    static inline std::string treat_comments(std::string &s)
    {
        // Allow comments of depth 1, but does not allow nested comments.
        return remove_comments_of_depth<2>::edit(s);
    }
};
 
template <class F, class... Args>
concept Formattable = std::invocable<F, Args...> && std::convertible_to<std::invoke_result_t<F, Args...>, std::string>;
 
template <class T, std::predicate<T> P1, std::predicate<T> P2, Formattable<T> F1, Formattable<T> F2,
          class Policy = PAUP>
class generator : public Policy
{
  public:
    using node_type = T;
    using formula_type = std::string;
    using policy_type = Policy;
 
  private:
    static inline constexpr char _end = ';';
 
    mutable formula_type _formula;
 
    mutable int _depth = 0;
 
    P1 _has_parent;
 
    P2 _has_children;
 
    F1 _label;
 
    F2 _branch_length;
 
    void _pre_order(const node_type &node) const
    {
        if (std::invoke(_has_children, node))
        {
            _formula += "(";
            _depth += 1;
        }
    }
 
    void _in_order() const
    {
        _formula += ",";
    }
 
    void _post_order(node_type const &node)
    {
        // Not leaf
        if (std::invoke(_has_children, node))
            _formula += ")";
 
        // Not root
        if (std::invoke(_has_parent, node))
        {
            auto const label = std::invoke(_label, node);
            _formula += label;
            std::string const branch(std::invoke(_branch_length, node));
            if (!branch.empty())
                _formula.append(":").append(branch);
        }
        else
        {
            // Is root
            _formula += std::invoke(_label, node);
            _formula += policy_type::root_branch_length();
        }
 
        _depth -= 1;
    }
 
  public:
    generator(P1 has_parent, P2 has_children, F1 label, F2 branch_length, Policy pol = {})
        : policy_type(std::move(pol)), _has_parent(std::move(has_parent)), _has_children(std::move(has_children)),
          _label(std::move(label)), _branch_length(std::move(branch_length))
    {
    }
 
    auto pre_order()
    {
        return [this](const node_type &node) { this->_pre_order(node); };
    }
 
    auto in_order()
    {
        return [this]() { this->_in_order(); };
    }
 
    auto post_order()
    {
        return [this](const node_type &node) { this->_post_order(node); };
    }
 
    bool has_forbidden_characters(const std::string &s) const
    {
        if (s.empty())
            return false;
        std::string forbidden = " ,;()[\\]";
        bool is_forbidden = std::regex_search(s, std::regex("[" + forbidden + "]"));
        return is_forbidden;
    }
 
    void clear()
    {
        _formula.clear();
    }
 
    std::string &&take_result() const
    {
        _formula.push_back(this->_end);
 
        _formula = policy_type::treat_comments(_formula);
 
        if (detail::is_balanced<detail::parenthesis>::check(_formula) == false)
        {
            throw std::runtime_error(std::string("Failed: formula parenthesis are not balanced:") + _formula);
        }
 
        if (detail::is_balanced<detail::square_bracket>::check(_formula) == false)
        {
            throw std::runtime_error(std::string("Failed: formula square brackets are not balanced:") + _formula);
        }
 
        return std::move(_formula);
    }
}; // end structure generator
 
template <class P1, class P2, class F1, class F2, class Policy = PAUP>
generator(P1, P2, F1, F2, Policy pol = {}) -> generator<detail::single_function_argument_t<P1>, P1, P2, F1, F2, Policy>;
 
} // end namespace quetzal::format::newick