tree_amplitude.cpp

#include <iostream>
#include <memory>
#include <utility>
#include <limits>
#include <stack>
#include <vector>
#include <stdexcept>
#include <map>
#include <string>
#include <boost/tuple/tuple.hpp>
#include <boost/format.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>

typedef int prec_t;

struct Node
{
	typedef std::shared_ptr<Node> ptr;
	prec_t value;
	ptr left = nullptr;
	ptr right = nullptr;
};

std::vector<Node::ptr> load_tree()
{
    namespace qi = boost::spirit::qi;
    namespace ascii = boost::spirit::ascii;
    namespace phoenix = boost::phoenix;

    using qi::int_;
    using qi::double_;
    using qi::_1;
    using ascii::space;
    using phoenix::ref;
    
	std::map<unsigned int, boost::tuple<Node::ptr, int, int>> tree_map;
    
	std::string textual;
	unsigned int node_index = 0;
	while (getline(std::cin, textual))
	{
        if (textual.empty()) break;
        
        unsigned int parsed_index;
        double parsed_value;
        int parsed_left = -1;
        int parsed_right = -1;
        
        auto iter = textual.begin();
        auto end = textual.end();
        bool parsed_ok = qi::phrase_parse(
        	iter,
        	end,
        	(
	            int_[ref(parsed_index) = _1]
	            >> ':' >> '{'
	            >> double_[ref(parsed_value) = _1]
		        >> *(',' >> int_[ref(parsed_left) = _1]
		        >> *(',' >> int_[ref(parsed_right) = _1]
		        )) >> '}' >> ';'
        	),
        	space
        );

        if (!parsed_ok || iter != end)
        {
        	auto e = boost::format("Cannot parse string \"%s\" at position %i")
				% textual
				% (end - textual.begin());

        	throw std::runtime_error(boost::str(e));
        }

        std::cout << boost::format("#%i: {value: %d, left: %i, right: %i}")
        	% parsed_index
        	% parsed_value
        	% parsed_left
        	% parsed_right
        	<< std::endl;
        
        Node::ptr node(new Node);
        node->value = parsed_value;
        
        tree_map[parsed_index] = {node, parsed_left, parsed_right};
        
        textual = "";
	}
	
	std::vector<Node::ptr> tree;
	
	for (auto node_pair : tree_map)
	{
		auto node = node_pair.second.get<0>();
		int left_index = node_pair.second.get<1>();
		int right_index = node_pair.second.get<2>();
        
        if (left_index > -1)
        {
        	node->left = tree_map[left_index].get<0>();
        }
        if (right_index > -1)
        {
        	node->right = tree_map[right_index].get<0>();
        }
        
        tree.push_back(node);
	}
	
	return tree;
}

template<typename L>
prec_t walk_tree(Node::ptr root, L&& lambda)
{
	std::stack<Node::ptr> parents;
	parents.push(root);
	
	std::stack<std::pair<prec_t, prec_t>> branches_min_max;
	branches_min_max.push({
		std::numeric_limits<prec_t>::infinity(),
		-std::numeric_limits<prec_t>::infinity()
	});
	
	prec_t max_amp = -std::numeric_limits<prec_t>::infinity();
	
	auto next_node = root;
	bool next_node_is_left = true;
	
	while (!parents.empty())
	{
		auto node = next_node;
		bool node_is_left = next_node_is_left;
		
		prec_t min = node->value < branches_min_max.top().first
			? node->value
			: branches_min_max.top().first;
		prec_t max = node->value > branches_min_max.top().second
			? node->value
			: branches_min_max.top().second;
		
		branches_min_max.top() = {min, max};
		
		std::forward<L>(lambda)(node, min, max, max_amp);
		
		bool node_has_left = node->left != nullptr;
		bool node_has_right = node->right != nullptr;
		bool parent_has_right = parents.top()->right != nullptr;
		
		if (node_has_left)
		{
			next_node = node->left;
			next_node_is_left = true;
			
			if (node_has_right) {
				parents.push(node);
				branches_min_max.push(branches_min_max.top());
			}
			
			continue;
		}
		
		if (!node_has_left)
		{
			prec_t branch_min = branches_min_max.top().first;
			prec_t branch_max = branches_min_max.top().second;
			prec_t branch_amp = branch_max - branch_min;
			
			max_amp = branch_amp > max_amp
				? branch_amp
				: max_amp;
		}
		
		if (parent_has_right)
		{
			next_node = parents.top()->right;
			next_node_is_left = false;
			
			parents.pop();
			branches_min_max.pop();
			
			continue;
		}
	}
	
	return max_amp;
}

int main()
{
	auto tree = load_tree();
	
	prec_t max_amp = walk_tree<>(
		tree[0],
		[tree] (Node::ptr node, prec_t min, prec_t max, prec_t max_amp) 
		{
			unsigned int index = 0;
			for (unsigned int i = 0; i < tree.size(); i++)
			{
				if (node == tree[i])
				{
					index = i;
					break;
				}
			}

	        std::cout << boost::format("#%i: {val: %d, min: %i, max: %i, max amp: %i}")
	        	% index
	        	% node->value
	        	% min
	        	% max
	        	% max_amp
	        	<< std::endl;
		}
	);
	
	std::cout << boost::format("Max amplitude: %i") % max_amp << std::endl;
	
	return 0;
}