Tree.mpp

export module CppUtils.Container.Tree;

import std;
import CppUtils.Type;
import CppUtils.String;

export namespace CppUtils::Container
{
	namespace Tree
	{
		template<class T>
		struct Node final
		{
			using ValueType = T;

			ValueType value;
			std::vector<Node<T>> nodes = {};

			[[nodiscard]] inline constexpr auto find(this auto&& self, const ValueType& key) noexcept -> auto
			{
				return std::ranges::find_if(self.nodes, [&key](const auto& node) -> bool {
					return node.value == key;
				});
			}

			[[nodiscard]] inline constexpr auto exists(const ValueType& key) const noexcept -> bool
			{
				return find(key) != std::cend(nodes);
			}

			[[nodiscard]] inline constexpr auto operator[](this auto&& self, const ValueType& key) -> decltype(auto)
			{
				if (const auto value = self.find(key); value == std::end(self.nodes)) [[unlikely]]
					if constexpr (std::is_const_v<std::remove_reference_t<decltype(self)>>)
						throw std::out_of_range{"The Node does not contain the requested child."};
					else
						return self.nodes.emplace_back(key);
				else
					return *value;
			}

			[[nodiscard]] inline constexpr auto getNodesWithValue(const ValueType& filterValue) const
			{
				return nodes | std::views::filter([&filterValue](const auto& node) { return node.value == filterValue; });
			}
		};

		template<class T>
		[[nodiscard]] inline auto operator==(const Node<T>& lhs, const Node<T>& rhs) -> bool
		{
			return lhs.value == rhs.value and lhs.nodes == rhs.nodes;
		}

		template<class... Types>
		requires std::default_initializable<Type::NthType<0, Types...>>
		using VariantNode = Node<std::variant<Types...>>;

		template<class CharT = char>
		struct TokenTree
		{
			using Node = Tree::Node<Type::Token>;
			Node root = Node{Type::hash(std::basic_string<CharT>{'r', 'o', 'o', 't'})};
			String::HashTable<CharT> hashTable = String::makeHashTable<CharT>(std::basic_string<CharT>{'r', 'o', 'o', 't'});
		};

		template<class CharT = char>
		struct NodeView final
		{
			using Node = Node<Type::Token>;
			std::reference_wrapper<const Node> node;
			std::reference_wrapper<const TokenTree<CharT>> tree;

			inline explicit NodeView(const TokenTree<CharT>& tree):
				node{std::cref(tree.root)},
				tree{std::cref(tree)}
			{}

			inline explicit NodeView(const Node& node, const TokenTree<CharT>& tree):
				node{std::cref(node)},
				tree{std::cref(tree)}
			{}

			[[nodiscard]] inline auto get() const -> const Node&
			{
				return node.get();
			}

			[[nodiscard]] inline auto get(Type::Token token) const -> const Node&
			{
				return get()[token];
			}

			inline auto to(Type::Token token) -> NodeView&
			{
				node = std::cref(get(token));
				return *this;
			}

			[[nodiscard]] inline auto getPrintableValue() const -> auto
			{
				return String::toAscii(String::getNameOrValue(get().value, tree.get().hashTable));
			}
		};

		template<class CharT>
		[[nodiscard]] inline auto operator==(const NodeView<CharT>& lhs, const NodeView<CharT>& rhs) -> bool
		{
			return lhs.get() == rhs.get();
		}

		template<class CharT>
		[[nodiscard]] inline auto operator==(const TokenTree<CharT>& lhs, const NodeView<CharT>& rhs) -> bool
		{
			return NodeView<CharT>{lhs} == rhs;
		}

		template<class CharT>
		[[nodiscard]] inline auto operator==(const TokenTree<CharT>& lhs, const TokenTree<CharT>& rhs) -> bool
		{
			return NodeView<CharT>{lhs} == NodeView<CharT>{rhs};
		}

		template<class CharT>
		[[nodiscard]] inline auto operator==(const NodeView<CharT>& lhs, const typename TokenTree<CharT>::Node& rhs) -> bool
		{
			return lhs.get() == rhs;
		}

		template<class CharT>
		[[nodiscard]] inline auto operator==(const TokenTree<CharT>& lhs, const typename TokenTree<CharT>::Node& rhs) -> bool
		{
			return NodeView<CharT>{lhs} == rhs;
		}
	}

	template<class CharT = char>
	using TokenTree = Tree::TokenTree<CharT>;
	template<class CharT = char>
	using AST = TokenTree<CharT>;
	template<class CharT = char>
	using ASTNode = TokenTree<CharT>::Node;
	template<class CharT = char>
	using ASTNodeView = Tree::NodeView<CharT>;
}

namespace std
{
	template<class T, class CharT>
	requires CppUtils::Type::Specializes<T, CppUtils::Container::Tree::Node> and CppUtils::Type::Printable<typename T::ValueType>
	struct formatter<T, CharT>
	{
		inline constexpr auto parse(std::format_parse_context& context) -> auto
		{
			return std::begin(context);
		}

		template<class FormatContext>
		inline auto format(const T& node, FormatContext& context) const -> decltype(context.out())
		{
			auto&& out = context.out();
			formatNode(node, context);
			return out;
		}

	private:
		template<class FormatContext>
		inline auto formatNode(const T& node, FormatContext& context, const std::basic_string<CharT>& prefix = "") const -> void
		{
			auto&& out = context.out();
			std::format_to(out, "{}\n", node.value);
			const auto nbNodes = std::size(node.nodes);
			for (auto i = 0uz; i < nbNodes; ++i)
			{
				const auto isLastNode = (i == nbNodes - 1);
				std::format_to(out, "{}{}─ ", prefix, isLastNode ? "└" : "├");
				formatNode(node.nodes.at(i), context, prefix + (isLastNode ? " " : "│") + "  ");
			}
		}
	};

	template<class CharT, class OutputCharT>
	struct formatter<CppUtils::Container::ASTNodeView<CharT>, OutputCharT>
	{
		inline constexpr auto parse(std::format_parse_context& context) -> auto
		{
			return std::begin(context);
		}

		template<class FormatContext>
		inline auto format(const CppUtils::Container::ASTNodeView<CharT>& nodeView, FormatContext& context) const -> decltype(context.out())
		{
			auto&& out = context.out();
			formatNode(nodeView, context);
			return out;
		}

	private:
		template<class FormatContext>
		inline auto formatNode(const CppUtils::Container::ASTNodeView<CharT>& nodeView, FormatContext& context, const std::basic_string<OutputCharT>& prefix = "") const -> void
		{
			const auto& [node, tree] = nodeView;
			auto&& out = context.out();
			std::format_to(out, "{}\n", nodeView.getPrintableValue());
			const auto nbNodes = std::size(node.get().nodes);
			for (auto i = 0uz; i < nbNodes; ++i)
			{
				const auto isLastNode = (i == nbNodes - 1);
				std::format_to(out, "{}{}─ ", prefix, isLastNode ? "└" : "├");
				auto child = CppUtils::Container::ASTNodeView<CharT>{node.get().nodes.at(i), tree};
				formatNode(child, context, prefix + (isLastNode ? " " : "│") + "  ");
			}
		}
	};

	template<class CharT, class OutputCharT>
	struct formatter<CppUtils::Container::TokenTree<CharT>, OutputCharT>
	{
		inline constexpr auto parse(std::format_parse_context& context) -> auto
		{
			return std::begin(context);
		}

		template<class FormatContext>
		inline auto format(const CppUtils::Container::TokenTree<CharT>& tree, FormatContext& context) const -> decltype(context.out())
		{
			auto&& out = context.out();
			return std::format_to(out, "{}", typename CppUtils::Container::Tree::NodeView<CharT>{tree});
		}
	};
}