Some notes on computer stuff

Range iterator for Boost.PropertyTree items

August 15, 2015
[c++] [boost] [programming]

The other day I was looking for a way to obtain fully qualified names of items in Boost.PropertyTree in sorted order, but basically found only one post on the subject, which demonstrated recursive traversal of a tree in more detail than iteration over all keys. What I wanted is an iterator based solution, which could be employed in C++11 range-based for loop. So I ended up writing one.

Implementation

There are Doxygen comments in the code, which should explain what's going on there. The most interesting part (assuming previous knowledge of writing iterators and range iterators) is probably propsIterator::increment() method which advances to the next leaf of the tree.

As Boost is already used, Boost.Iterator library is used here as well.

It's probably obvious by now, but let's note one more time that this is C++11 code, which should be compiled like:

g++ -std=c++11 code.cpp

The code:

#include <algorithm>
#include <iterator>
#include <sstream>
#include <stack>
#include <string>
#include <utility>

#include <boost/property_tree/ptree.hpp>
#include <boost/range/iterator_range.hpp>

namespace detail {

namespace pt = boost::property_tree;

/**
 * @brief Storage for range iterator data.
 */
class propsRangeData
{
public:
    /**
     * @brief Constructs data out of property tree.
     *
     * @param props Property tree to iterate over.
     */
    explicit propsRangeData(pt::ptree &props)
    {
        it.emplace(props.ordered_begin(), props.not_found());
    }

    /**
     * @brief Holds tree visit iterators as begin-end pairs.
     */
    std::stack<
        std::pair<
            pt::ptree::assoc_iterator,
            pt::ptree::assoc_iterator
        >
    > it;
    /**
     * @brief Names of all parent nodes of the current one.
     */
    std::vector<std::string> parents;
    /**
     * @brief Full name of the current node.
     */
    std::string fullName;
};


/**
 * @brief Iterator for property tree items.
 */
class propsIterator
  : public boost::iterator_facade<
        propsIterator,
        std::string,
        std::input_iterator_tag
    >
{
    friend class boost::iterator_core_access;

public:
    /**
     * @brief Constructs empty iterator ("end" iterator).
     */
    propsIterator() : rd(nullptr)
    {
    }

    /**
     * @brief Constructs non-empty iterator.
     *
     * @param rd Pointer to data storage that outlives the iterator.
     */
    propsIterator(propsRangeData *rd) : rd(rd)
    {
        // Special case of empty property tree.
        if (rd->it.top().first == rd->it.top().second) {
            rd->it.pop();
        }
        increment();
    }

private:
    /**
     * @brief Advances to the next property node.
     */
    void increment()
    {
        // Turn into "end" iterator and boil out if visit stack is empty.
        if (rd->it.empty()) {
            *this = propsIterator();
            return;
        }

        // Go down until a leaf.
        while (!rd->it.top().first->second.empty()) {
            pt::ptree::assoc_iterator &it = rd->it.top().first;

            rd->parents.emplace_back(it->first);
            rd->it.emplace(it->second.ordered_begin(), it->second.not_found());
        }

        // Format full name for the property.
        std::ostringstream oss;
        std::copy(rd->parents.cbegin(), rd->parents.cend(),
                  std::ostream_iterator<std::string>(oss, "."));
        rd->fullName = oss.str() + rd->it.top().first->first;

        // Go up until first unfinished level.
        while (!rd->it.empty() && ++rd->it.top().first == rd->it.top().second) {
            rd->it.pop();
            // Parents vector is empty for top-level elements.
            if (!rd->parents.empty()) {
                rd->parents.pop_back();
            }
        }
    }

    /**
     * @brief Checks whether two iterators are equal.
     *
     * @param that Iterator to compare against @c *this.
     *
     * @returns @c true if equal, @c false otherwise.
     */
    bool equal(const propsIterator &that) const
    {
        return rd == that.rd;
    }

    /**
     * @brief Retrieves value of a valid iterator (not "end" iterator).
     *
     * @returns The value.
     */
    std::string & dereference() const
    {
        return rd->fullName;
    }

private:
    /**
     * @brief Pointer to data storage.
     */
    propsRangeData *rd;
};

using propsRangeBase = boost::iterator_range<propsIterator>;

}

/**
 * @brief Range iterator over names of property tree items.
 *
 * Each element is returned in fully qualified form: dot-separated path of
 * nodes, e.g. "root.middle.end".
 */
class propsRange : private detail::propsRangeData, public detail::propsRangeBase
{
public:
    explicit propsRange(boost::property_tree::ptree &props)
        : detail::propsRangeData(props),
          detail::propsRangeBase(detail::propsIterator(this),
                                 detail::propsIterator())
    {}
};

Usage Example

As an example let's iterate over all keys of a simple data in INFO format and print out associated values (note absence of #include for the code above, so add it at the top or include in some other way):

#include <iostream>
#include <sstream>
#include <string>

#include <boost/property_tree/info_parser.hpp>

namespace pt = boost::property_tree;

int
main()
{
    static const std::string data = R"(
        root1
        {
            middle1
            {
                leaf3 13
                leaf1 666
                leaf0 234
            }
            leaf val
            one_more_leaf 2
        }
        root2
        {
            middle
            {
                leaf_value here
                leaf_again "and here"
            }
        }
    )";

    boost::property_tree::ptree props;
    {
        std::istringstream iss(data);
        read_info(iss, props);
    }

    for (const std::string &key : propsRange(props)) {
        std::cout << key << " = " << props.get<std::string>(key) << '\n';
    }
}

Expected output:

root1.leaf = val
root1.middle1.leaf0 = 234
root1.middle1.leaf1 = 666
root1.middle1.leaf3 = 13
root1.one_more_leaf = 2
root2.middle.leaf_again = and here
root2.middle.leaf_value = here