from_network.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. *
 *                                                                      *
 ***************************************************************************/
 
#ifndef __EXTENDED_NEWICK_FORMATTER_H_INCLUDED__
#define __EXTENDED_NEWICK_FORMATTER_H_INCLUDED__
 
#include <algorithm>
#include <concepts>
#include <regex>
#include <stdexcept>
#include <string>
 
namespace quetzal
{
namespace format
{
struct parenthesis
{
};
struct square_bracket
{
};
bool check_if_balanced(const std::string &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<parenthesis>
{
    static bool check(const std::string &s)
    {
        return check_if_balanced(s, '(', ')');
    }
};
template <> struct is_balanced<square_bracket>
{
    static bool check(const std::string &s)
    {
        return check_if_balanced(s, '[', ']');
    }
};
 
namespace newick
{
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> : identity
{
};
template <> struct remove_comments_of_depth<1>
{
    static std::string edit(const std::string &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 Formatter : 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;
    P1 _has_parent;
 
    P2 _has_children;
 
    F1 _label;
 
    F2 _branch_length;
 
    bool has_forbidden_characters(const std::string &s) const
    {
        std::string joined;
        for (const std::string &piece : forbidden_labels)
            joined += piece;
        bool is_forbidden = std::regex_search(s, std::regex("^[^"s + joined + "]"s));
        return is_forbidden;
    }
 
    void _pre_order(const node_type &node) const
    {
        if (std::invoke(_has_children, node))
        {
            _formula += "(";
        }
    }
 
    void _in_order(const node_type &) const
    {
        _formula += ",";
    }
 
    void _post_order(const node_type &node) const
    {
 
        if (std::invoke(_has_children, node))
        {
            _formula.pop_back(); // Remove comma
            _formula += ")";
        }
 
        if (std::invoke(_has_parent, node))
        {
            auto label = std::invoke(_label, node);
 
            if (has_forbidden_characters(remove_comments_of_depth<1>::edit(label)))
            {
                throw std::invalid_argument(std::string("Label with forbidden characters:") + std::string(label));
            }
 
            _formula += label;
 
            auto branch = std::invoke(_branch_length, node);
            if (branch != "")
            {
                _formula += ":";
                _formula += branch;
            }
        }
        else
        {
            _formula += std::invoke(_label, node);
            _formula += policy_type::root_branch_length();
        }
    }
 
  public:
    Formatter(P1 &&has_parent, P2 &&has_children, F1 &&label, F2 &&branch_length)
        : _has_parent(std::forward<P1>(has_parent)), _has_children(std::forward<P2>(has_children)),
          _label(std::forward<F1>(label)), _branch_length(std::forward<F2>(branch_length))
    {
    }
 
    auto pre_order()
    {
        return [this](const node_type &node) { this->_pre_order(node); };
    }
    auto in_order()
    {
        return [this](const node_type &node) { this->_in_order(node); };
    }
    auto post_order()
    {
        return [this](const node_type &node) { this->_post_order(node); };
    }
    void clear()
    {
        _formula.clear();
    }
    formula_type get() const
    {
        // that or expose orders
        // root.visit_by_generic_DFS(preorder, inorder, postorder);
 
        _formula.push_back(this->_end);
 
        _formula = policy_type::treat_comments(_formula);
 
        if (is_balanced<parenthesis>::check(_formula) == false)
        {
            throw std::runtime_error(std::string("Failed: formula parenthesis are not balanced:") + _formula);
        }
 
        if (is_balanced<square_bracket>::check(_formula) == false)
        {
            throw std::runtime_error(std::string("Failed: formula square brackets are not balanced:") + _formula);
        }
 
        return _formula;
    }
}; // end structrure Newick
 
// 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;
 
// Deduction guide: type T is deduced from P1
template <class P1, class P2, class F1, class F2, class Policy = PAUP>
Formatter(P1 &&, P2 &&, F1 &&, F2 &&) -> Formatter<single_function_argument_t<P1>, P1, P2, F1, F2, Policy>;
 
template <class P1, class P2, class F1, class F2, class Policy = PAUP>
auto make_formatter(P1 &&has_parent, P2 &&has_children, F1 &&label, F2 &&branch_length, Policy policy = Policy())
{
    // Use Class template argument deduction (CTAD)
    return Formatter<single_function_argument_t<P1>, P1, P2, F1, F2, Policy>(
        std::forward<P1>(has_parent), std::forward<P2>(has_children), std::forward<F1>(label),
        std::forward<F2>(branch_length));
}
 
template <class T, std::predicate<T> P1, std::predicate<T> P2, Formattable<T> F1, Formattable<T> F2, class Policy>
auto make_formatter(P1 &&has_parent, P2 &&has_children, F1 &&label, F2 &&branch_length, Policy policy = Policy())
{
    // Use Class template argument deduction (CTAD)
    return Formatter<T, P1, P2, F1, F2, Policy>(std::forward<P1>(has_parent), std::forward<P2>(has_children),
                                                std::forward<F1>(label), std::forward<F2>(branch_length));
}
} // end namespace newick
} // end namespace format
} // end namespace quetzal
 
#endif