inroder_iterator for syntax tree of markargs

Question

Introduction

It is a spin-off to my compiler creation.

Problem

Traverse the markargs::syntax_tree in order, e.g. first goes left_operand, then operator, then right_operand.

It can be used to collect statistics, run searches, transform some nodes, copy into istreams, etc. In general, it is a good skill to have, in my opinion (although I hate algorithms that are big if-else's). I'm considering moving streaming operator to use this iterator.

Code

inorder_iterator_tests.cpp

#include <sstream>
#include <iterator>
#include <string>
#include <algorithm>
#include <fstream>
#include <iostream>

#include <token.hpp>
#include "syntax_tree.hpp"

void test_one(const std::string& inputline, const std::string& correct_answer)
{
    std::stringstream ss(inputline);
    markargs::syntax_tree tree{std::istream_iterator<markargs::token>(ss), {}};
    std::ostringstream result;

    auto begin = tree.inorder_begin();
    auto end = tree.inorder_end();

    for (; begin != end; ++begin)
    {
        result << begin->payload();
    }

    if (result.str() != correct_answer)
    {
        std::cout << result.str() << '\n';
        throw std::logic_error{"tree was not build correctly for input: "
                               + inputline};
    }
}

void run_tests()
{
    std::ifstream input_file("input.txt");
    std::ifstream answers_file("answers.txt");
    if (!input_file.is_open() || !answers_file.is_open())
    {
        throw std::runtime_error{"either input or answers file cannot be opened"};
    }

    std::string inputline;
    std::string correct_answer;

    std::cout << "starting inorder iterator tests ...\n";
    unsigned int counter = 1;
    while (std::getline(input_file, inputline) && std::getline(answers_file, correct_answer))
    {
        std::cout << "running test #" << counter << '\n';
        test_one(inputline, correct_answer);
        ++counter;
    }

    std::cout << "all tests passed\n\n";
}

int main()
{
    run_tests();
}

syntax_tree.hpp (the iterator is public class of it)

#ifndef COMPILER_PARSE_TREE_HPP
#define COMPILER_PARSE_TREE_HPP

#include <string>
#include <queue>
#include <map>
#include <iosfwd>
#include <stack>

#include <token.hpp>

namespace markargs
{
    class syntax_tree
    {
        struct node
        {
            markargs::token tk;
            node* left_operand;
            node* right_operand;

            explicit node(const markargs::token& tk_,
                          node* left_operand_ = nullptr,
                          node* right_operand_ = nullptr);
        };

        node* root;

        std::map<std::string, int> operator_precedence;
    public:
        class inorder_iterator : public std::iterator<std::forward_iterator_tag, token>
        {
            friend syntax_tree;

            node* current_node;
            std::stack<node*> prev_nodes;
            std::map<node*, bool> visited;
        public:
            inorder_iterator();

            inorder_iterator& operator++();
            inorder_iterator operator++(int);

            token& operator*();
            const token& operator*() const;

            token* operator->();
            const token* operator->() const;

            friend bool operator==(const inorder_iterator lhs, const inorder_iterator rhs);
            friend bool operator!=(const inorder_iterator lhs, const inorder_iterator rhs);

        private:
            inorder_iterator(node* current);
            node* find_leftmost_node(node* from);
        };

        template <typename InputIterator>
        syntax_tree(InputIterator first, InputIterator last):
                root(nullptr),
                operator_precedence
                        {
                {"=", 0},
                {"+", 1},
                {"-", 1}
                        }
        {
            std::queue<token> tokens{std::deque<token>{first, last}};
            parse(tokens);
        }

        syntax_tree(const syntax_tree& other) = delete;
        syntax_tree& operator=(const syntax_tree& other) = delete;

        syntax_tree(syntax_tree&& other) noexcept;
        syntax_tree& operator=(syntax_tree&& other) = delete;

        inorder_iterator inorder_begin();
        inorder_iterator inorder_end();

        ~syntax_tree();

        friend std::ostream& operator<<(std::ostream& os, const syntax_tree& tree);
    private:
        void parse(std::queue<token>& tokens);
        void print(std::ostream& os, const node& n) const;
        void recursive_destruct(node* n);
    };
}

#endif //COMPILER_PARSE_TREE_HPP

inorder_iterator.cpp

#include "syntax_tree.hpp"

namespace markargs
{
    syntax_tree::inorder_iterator::inorder_iterator(node* current) :
            current_node(current)
    {
        current_node = find_leftmost_node(current);
        visited[current_node] = true;
    }

    syntax_tree::node* syntax_tree::inorder_iterator::find_leftmost_node(node* from)
    {
        if (from->left_operand != nullptr)
        {
            prev_nodes.push(from);
            return find_leftmost_node(from->left_operand);
        }

        return from;
    }

    syntax_tree::inorder_iterator::inorder_iterator() :
            current_node(nullptr)
    {}

    syntax_tree::inorder_iterator& syntax_tree::inorder_iterator::operator++()
    {
        if (current_node->left_operand != nullptr && !visited[current_node->left_operand])
        {
            prev_nodes.push(current_node);
            current_node = current_node->left_operand;
            return ++*this; //recurse
        }

        if (!visited[current_node])
        {
            visited[current_node] = true;
            return *this;
        }
        else
        {
            //prev_nodes.pop();
            if (current_node->right_operand != nullptr)
            {
                current_node = current_node->right_operand;
                return ++*this;
            }
            else
            {
                if (!prev_nodes.empty())
                {
                    current_node = prev_nodes.top();
                    prev_nodes.pop();
                    return ++*this;
                }
                else
                {
                    current_node = nullptr;
                    return *this;
                }
            }
        }
    }

    syntax_tree::inorder_iterator syntax_tree::inorder_iterator::operator++(int)
    {
        auto copy = *this;
        ++*this;
        return copy;
    }

    const token& syntax_tree::inorder_iterator::operator*() const
    {
        return current_node->tk;
    }

    token& syntax_tree::inorder_iterator::operator*()
    {
        return current_node->tk;
    }

    const token* syntax_tree::inorder_iterator::operator->() const
    {
        return &current_node->tk;
    }

    token* syntax_tree::inorder_iterator::operator->()
    {
        return &current_node->tk;
    }



    bool operator==(const syntax_tree::inorder_iterator lhs, const syntax_tree::inorder_iterator rhs)
    {
        return lhs.current_node == rhs.current_node;
    }

    bool operator!=(const syntax_tree::inorder_iterator lhs, const syntax_tree::inorder_iterator rhs)
    {
        return !(lhs == rhs);
    }
}

CMakeLists.txt

cmake_minimum_required(VERSION 3.2)
project(compiler)

set(CMAKE_CXX_STANDARD 14)

add_library(syntax_analysis syntax_tree.hpp syntax_tree.cpp inorder_iterator.cpp)
target_include_directories(syntax_analysis PUBLIC ../lexical_analysis/)
target_link_libraries(syntax_analysis lexical_analysis)

add_executable(syntax_analysis_tests
        main.cpp
        syntax_tree.hpp
        )
target_link_libraries(syntax_analysis_tests syntax_analysis)
target_include_directories(syntax_analysis_tests PUBLIC ../lexical_analysis/)

configure_file(./input.txt ${CMAKE_CURRENT_BINARY_DIR}/input.txt COPYONLY)
configure_file(./input.txt ${CMAKE_CURRENT_BINARY_DIR}/answers.txt COPYONLY)
configure_file(./failing_input.txt ${CMAKE_CURRENT_BINARY_DIR}/failing_input.txt COPYONLY)

add_test(syntax-analysis-tests syntax_analysis_tests)

add_executable(inorder_iterator_tests
        inorder_iterator_tests.cpp
        syntax_tree.hpp)

target_link_libraries(inorder_iterator_tests syntax_analysis)

---

Design decisions

• Storing previous nodes as stack.

  The reason behind this is to make it easier to generalize to any binary tree in the future. If you're familiar with markargs syntax and parser's specifications, at any time any node will only have one leaf left child, thus it could be stored by a pointer or optional.

• Storing visited nodes as map.

  I believe I heard it is possible to use stack for this, but I'm not sure. As a result the iterator has insane memory overhead.

• Limiting the iterator to Forward Iterator

  I can't think of the cases Bidirectional Iterator would be useful, so to not elevate complexity I decided to stick with Forward Iterator concept.

• Private constructor

  Since users don't have access to nodes anyway, public constructor won't make much sense. Public default constructor, which constructs end iterator, is very useful though. End iterator is almost like a functor, since it just checks if the other one set current_node to nullptr.

---

Concerns

• Control flow complexity. I believe finding next node is expressed in a very non-comprehensive way.

• Memory efficiency. Current design has noticable memory overhead.

• General code quality

• Anything else

---

I know the iterator is deprecated, but since tools are still in development for C++17, I decided to stick with C++14.

Build script

git clone https://github.com/simmplecoder/markargs.git
cd markargs
git checkout 092a5b37f9ab5af480cb3cb4288869770ac8d42f
mkdir build
cd build
cmake ..
make

If you have already cloned it:

#cd to markargs
git remote add origin https://github.com/simmplecoder/markargs
git fetch origin
git checkout 092a5b37f9ab5af480cb3cb4288869770ac8d42f
mkdir build
cd build
cmake ..
make

Answer 1

Is there any benefit using a std::map<node*, bool> rather than a more simple std::set

I would guess that both fulfill the same purpose with the latter beeing more efficient.