Transforming trees in C++

Question

I have an heterogeneous n-ary tree made by different kind of nodes, for example:

class Node { }

class Subnode1 : public Node
{

}

class Subnode2 : public Node
{
private:
  unique_ptr<Subnode1> child;

public:
  Subnode1* getChild() { return child.get(); }
}

class Subnode4 : public Subnode2 { }

class Subnode3 : public Node
{
private:
  list<unique_ptr<Subnode2>> children;
public:
  // getter
}

// etc

The structure could contain any amount of types of nodes and it will be extended in the future.

I implemented a way to visit the tree which allows me to customize what to do when each node is visited which is basically implemented in this way:

void genericVisit(Node* node) {
  if (dynamic_cast<Subnode2>(node))
    visit(static_cast<Subnode2*>(node));
  // etc
}

virtual void visit(Subnode2* node) {
  if (node->getChild())
    genericVisit(node->getChild());
}

// etc

It works nicely to traverse the tree but now I have the requirement to be able to replace subtrees with other subtrees so I'm thinking about the best approach to follow without altering the structure too much.

The best solution would have been to let getter return directly unique_ptr<Subnode2>& so that I do the visit on the unique pointers and I'm able to change the content of the smart pointer while visiting it. This would work but unique_ptr is not polymorphic, and there is no way to dispatch the call to the most specialized method, eg:

void genericVisit(unique_ptr<Node>& node) { // NON WORKING CODE
  if (dynamic_cast<unique_ptr<Subnode2>&>(node))
    visit(static_cast<unique_ptr<Subnode2>&>(node));
  // etc
}

So I was wondering which could be the best solution to the problem, minding that while traversing the tree, as long as I change the content of the current subtree without changing the reference to that node in the parent, (which would be allowed by using an unique_ptr) I don't see any problem.

Answer 1

Because I thought a comment was not going to be enough to convey all that information:

@Jack you can (Sean Parent: should) use shared_pointer<const Node> there, and copy as required for changes. Immutability for the win! That said, perhaps you can do without the inheritance altogether? Make things simpler and potentially more efficient – sehe 6 hours ago

I thought I'd demonstrate both aspects a little, in reverse order:

1. On using static polymorphism for the trees: let's define a tree where leaf nodes can be strings or userdefined structs:

   struct Data {
       double x,y,z;
   };
   
   using Node = make_recursive_variant<std::string, Data, std::vector<recursive_variant_> >::type;
   using Nodes = std::vector<Node>;
   

   The sample tree used in all the tests below is now defined as:

   Node tree = Nodes {
       "hello",
       Data { 1,2,3 },
       Nodes {
           "more nested",
           Nodes {
               Data { 2,3,4 },
               Data { 3,4,5 },
               Data { 4,5,6 },
           },
           "nodes"
       }
   };
   

   Boost Variant lends itself very naturally for transformation via visitation. For example, let's write a visitor that reverses all nodes in the tree, so including the strings and Data{x,y,z} -> Data{z,y,x}:

   struct reverser : static_visitor<Node> {
       Node operator()(Node const& tree)      const { return apply_visitor(*this, tree); }
       Node operator()(std::string const& s)  const { return std::string(s.rbegin(), s.rend()); }
       Node operator()(Data const& d)         const { return Data {d.z, d.y, d.x}; }
       Node operator()(Nodes const& children) const {
           Nodes revchildren;
           std::transform(children.rbegin(), children.rend(), back_inserter(revchildren), *this);
           return revchildren;
       }
   };
   
   Node reverse(Node const& tree) {
       return reverser()(tree);
   }
   

   See the simplified demo at this stage Live On Coliru

   • I added a print visitor so you can see what the result is
   • It even roundtrip tests the tree (tree == reverse(reverse(tree)))

   ---

2. Now you'll notice that the trees under 1. have value semantics, meaning that the reverse operation results in a completely separate copy of the tree.

   I've went on and added a similar SharedTree:

   using SNode = boost::shared_ptr<
           boost::make_recursive_variant<
               std::string, Data, std::vector<boost::shared_ptr<boost::recursive_variant_>
           > >::type>;
   
   using Node  = SNode::element_type;
   using Nodes = std::vector<SNode>;
   

   When you manipulate copies of these trees, both copies change because they share nodes (the demo program below adds a node to one SharedTree and observes that the other also changes)

3. Now comes the Sean Parent approach: using shared_ptr<T const>

   namespace CowTree {
       using SNode = boost::shared_ptr<
               boost::make_recursive_variant<
                   std::string, Data, std::vector<boost::shared_ptr<boost::recursive_variant_ const>
               > >::type const>;
   
       using Node  = SNode::element_type;
       using Nodes = std::vector<SNode>;
   }
   

   The beauty of this is that it's cheap to make copies, but you cannot possibly modify a node: you always have to deep-copy a subtree to modify any aspect of it's value. To demonstrate this, I've made a transformation that just uppercases string leaf nodes, leaving everything else unchanged:

   template <typename SNode, typename Nodes = std::vector<SNode> >
   struct upper_caser : boost::static_visitor<SNode> {
       SNode operator()(SNode const& tree)            const { 
           return apply_visitor(boost::bind(*this, boost::ref(tree), _1), *tree); 
       }
       // dispatch
       SNode operator()(SNode const&, std::string const& value) const {
           std::string xformed;
           std::transform(value.begin(), value.end(), back_inserter(xformed), [](uint8_t c) { return std::toupper(c); });
           return boost::make_shared<typename SNode::element_type>(xformed);
       }
       SNode operator()(SNode const& node, Nodes const& children)  const {
           Nodes xformed; // TODO optimize
           std::transform(children.begin(), children.end(), back_inserter(xformed), *this);
   
           return (equal(children, xformed))
               ? node
               : boost::make_shared<typename SNode::element_type>(xformed);
       }
       template <typename V> SNode operator()(SNode const& node, V const&) const {
           return node;
       }
   };
   
   template <typename SNode>
   SNode ucase(SNode const& tree) {
       return upper_caser<SNode>()(tree);
   }
   

   As you can see the transformation is completely generic and will work with the SharedTree just as well as the CowTree - because no value is ever mutated. Obviously, using the CowTree is much safer because it guarantees immutability.

   The test program actively checks that

   • the original cow tree doesn't change when we get it's ucased transform.
   • it also checks that the subtrees that haven't changed, are indeed shared (haven't been cloned)

---

Full Program

Live On Coliru

#include <boost/variant.hpp>

namespace Tree {
    struct Data {
        double x,y,z;
    };

    using Node  = boost::make_recursive_variant<std::string, Data, std::vector<boost::recursive_variant_> >::type;
    using Nodes = std::vector<Node>;

    namespace Operations {
        struct reverser : boost::static_visitor<Node> {
            Node operator()(Node const& tree)       const { return apply_visitor(*this, tree); }
            Node operator()(Data const& d)          const { return Data {d.z, d.y, d.x}; }
            Node operator()(std::string const& s)   const { return std::string(s.rbegin(), s.rend()); }
            Node operator()(Nodes const& children)  const {
                Nodes revchildren;
                std::transform(children.rbegin(), children.rend(), back_inserter(revchildren), *this);
                return revchildren;
            }
        };

        Node reverse(Node const& tree) {
            return reverser()(tree);
        }
    }

    using Operations::reverse;
}

// For our demo, let's implement `operator <<` with a manipulator
#include <iostream>
namespace IO {
    namespace detail {
        using namespace boost;

        // this pretty prints the tree as C++ initializer code
        struct print_visitor : static_visitor<void> {
            print_visitor(std::ostream& os, std::string const& indent = "\n") : _os(os), _indent(indent) {}

            // concrete types
            void operator()(std::string const& s)  const { _os << '"' << s << '"'; }
            void operator()(Tree::Data const& d)   const { _os << "Data {" << d.x << "," << d.y << "," << d.z << '}'; }

            // generics to cater for both direct and shared tree nodes
            template <typename T>     void operator()(shared_ptr<T> const& sp)       const { (*this)(*sp); }
            template <typename T>     void operator()(shared_ptr<const T> const& sp) const { (*this)(*sp); }
            template <typename... Ts> void operator()(variant<Ts...> const& tree)    const { apply_visitor(*this, tree); }

            template <typename Node>
            void operator()(std::vector<Node> const& children) const {
                _os << "Nodes {";

                print_visitor subnode(_os, _indent + "  ");
                for(auto& n : children) {
                    _os << subnode._indent;
                    subnode(n);
                    _os << ",";
                }

                _os << _indent << '}';
            }
        private:
            std::ostream& _os;
            mutable std::string _indent;
        };

        template <typename NodeType>
        struct print_manip {
            print_manip(NodeType const& n) : _node(n) {}
            friend std::ostream& operator<<(std::ostream& os, print_manip const& m) {
                return print_visitor(os)(m._node), os << ";";
            }

            private:
            NodeType const& _node;
        };
    }

    template <typename NodeType>
        detail::print_manip<NodeType> print(NodeType const& node) { 
            return node; 
        }
}

#include <boost/make_shared.hpp>

namespace Support {
    namespace detail {
        template <typename SNode, typename Nodes = std::vector<SNode> >
        struct share_visitor : boost::static_visitor<SNode> {
            SNode operator()(Tree::Node const& tree)      const { return apply_visitor(*this, tree); }

            SNode operator()(Tree::Nodes const& children) const {
                Nodes shared;
                std::transform(children.begin(), children.end(), back_inserter(shared), *this);
                return boost::make_shared<typename SNode::element_type>(shared);
            }

            template <typename LeafNode>
            SNode operator()(LeafNode const& v) const { return boost::make_shared<typename SNode::element_type>(v); }
        };
    }
}

#include <boost/bind.hpp>

namespace SharedTree {
    using Tree::Data;

    using SNode = boost::shared_ptr<
            boost::make_recursive_variant<
                std::string, Data, std::vector<boost::shared_ptr<boost::recursive_variant_>
            > >::type>;

    using Node  = SNode::element_type;
    using Nodes = std::vector<SNode>;

    namespace Operations {
        template <typename SNode, typename Nodes = std::vector<SNode> >
        struct upper_caser : boost::static_visitor<SNode> {
            SNode operator()(SNode const& tree)            const { 
                return apply_visitor(boost::bind(*this, boost::ref(tree), _1), *tree); 
            }
            // dispatch
            SNode operator()(SNode const&, std::string const& value) const {
                std::string xformed;
                std::transform(value.begin(), value.end(), back_inserter(xformed), [](uint8_t c) { return std::toupper(c); });
                return boost::make_shared<typename SNode::element_type>(xformed);
            }
            SNode operator()(SNode const& node, Nodes const& children)  const {
                Nodes xformed; // TODO optimize
                std::transform(children.begin(), children.end(), back_inserter(xformed), *this);

                return (equal(children, xformed))
                    ? node
                    : boost::make_shared<typename SNode::element_type>(xformed);
            }
            template <typename V> SNode operator()(SNode const& node, V const&) const {
                return node;
            }
        };

        template <typename SNode>
        SNode ucase(SNode const& tree) {
            return upper_caser<SNode>()(tree);
        }
    }

    using Operations::ucase;

    SNode share(Tree::Node const& tree) {
        return Support::detail::share_visitor<SNode>()(tree);
    }
}

namespace CowTree {
    using Tree::Data;

    using SNode = boost::shared_ptr<
            boost::make_recursive_variant<
                std::string, Data, std::vector<boost::shared_ptr<boost::recursive_variant_ const>
            > >::type const>;

    using Node  = SNode::element_type;
    using Nodes = std::vector<SNode>;

    SNode share(Tree::Node const& tree) {
        return Support::detail::share_visitor<SNode>()(tree);
    }
}

#include <boost/lexical_cast.hpp> // for the roundtrip test

namespace Support {
    template <typename NodeType1, typename NodeType2>
    bool tree_equal(NodeType1 const& a, NodeType2 const& b) {
        using IO::print;
        return boost::lexical_cast<std::string>(print(a)) == 
            boost::lexical_cast<std::string>(print(b));
    }
}

int main() {
    using namespace Tree;
    using IO::print;
    using Support::tree_equal;

    Node tree = Nodes {
        "hello",
        Data { 1,2,3 },
        Nodes {
            "more nested",
            Nodes {
                Data { 2,3,4 },
                Data { 3,4,5 },
                Data { 4,5,6 },
            },
            "nodes"
        }
    };

    std::cout << "Before transformation: \n" << print(tree)          << "\n";
    std::cout << "After transformation:  \n" << print(reverse(tree)) << "\n";

    Node roundtrip = reverse(reverse(tree));
    std::cout << "Roundtrip tree_equal: "    << std::boolalpha       << tree_equal(tree, roundtrip) << "\n";

    std::cout << "//////////////////////////////////////////////////\n";
    std::cout << "// manipulate SharedTree \"copies\"\n";
    auto shared = SharedTree::share(tree);
    std::cout << "Shared: "          << print(shared)            << "\n";
    std::cout << "Equal to source: " << tree_equal(tree, shared) << "\n";

    auto shared2 = shared;

    using boost::get;
    using boost::make_shared;
    get<SharedTree::Nodes>(*shared).push_back(make_shared<SharedTree::Node>("added to a shared tree"));

    std::cout << "Shared2 after changing shared: " << print(shared2)              << "\n";
    std::cout << "Shared trees equal: "            << tree_equal(shared, shared2) << "\n";
    std::cout << "Not equal to source: "           << tree_equal(tree, shared)    << "\n";

    std::cout << "//////////////////////////////////////////////////\n";
    std::cout << "// now let's see about CowTree\n";
    auto cow = CowTree::share(tree);
    std::cout << "Cow: "                 << print(cow)            << "\n";
    std::cout << "Equal to source: "     << tree_equal(tree, cow) << "\n";

    auto ucased = SharedTree::ucase(cow);
    std::cout << "Ucased: "              << print(ucased)           << "\n";
    std::cout << "Equal to cow source: " << tree_equal(ucased, cow) << "\n";

   /*
    *    The 
    *
    *        Nodes {
    *            Data { 2,3,4 },
    *            Data { 3,4,5 },
    *            Data { 4,5,6 },
    *        },
    *
    *    subtree should still be shared, because it wasn't touched:
    */
    std::cout << "Subtree from ucased: " << print(get<CowTree::Nodes>(*get<CowTree::Nodes>(*ucased)[2])[1]) << "\n";
    std::cout << "Subtree from cow: "    << print(get<CowTree::Nodes>(*get<CowTree::Nodes>(*cow   )[2])[1]) << "\n";
    std::cout << "Subtrees match: "      << tree_equal(
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*ucased)[2])[1],
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*cow)   [2])[1])
        << "\n";
    // unchanged nodes should be shared:
    std::cout << "Subtrees shared: " << (
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*ucased)[2])[1].get() ==
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*cow)   [2])[1].get())
        << "\n";
    // changed nodes aren't shared:
    std::cout << "Siblings unshared: " << (
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*ucased)[2])[2].get() !=
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*cow)   [2])[2].get())
        << "\n";
    std::cout << "Parents unshared: " << (
            get<CowTree::Nodes>(*ucased)[2].get() !=
            get<CowTree::Nodes>(*cow)   [2].get())
        << "\n";
    std::cout << "Roots unshared: " << ( ucased.get() != cow.get())
        << "\n";
}

Output:

Before transformation: 
Nodes {
  "hello",
  Data {1,2,3},
  Nodes {
    "more nested",
    Nodes {
      Data {2,3,4},
      Data {3,4,5},
      Data {4,5,6},
    },
    "nodes",
  },
};
After transformation:  
Nodes {
  Nodes {
    "sedon",
    Nodes {
      Data {6,5,4},
      Data {5,4,3},
      Data {4,3,2},
    },
    "detsen erom",
  },
  Data {3,2,1},
  "olleh",
};
Roundtrip tree_equal: true
//////////////////////////////////////////////////
// manipulate SharedTree "copies"
Shared: Nodes {
  "hello",
  Data {1,2,3},
  Nodes {
    "more nested",
    Nodes {
      Data {2,3,4},
      Data {3,4,5},
      Data {4,5,6},
    },
    "nodes",
  },
};
Equal to source: true
Shared2 after changing shared: Nodes {
  "hello",
  Data {1,2,3},
  Nodes {
    "more nested",
    Nodes {
      Data {2,3,4},
      Data {3,4,5},
      Data {4,5,6},
    },
    "nodes",
  },
  "added to a shared tree",
};
Shared trees equal: true
Not equal to source: false
//////////////////////////////////////////////////
// now let's see about CowTree
Cow: Nodes {
  "hello",
  Data {1,2,3},
  Nodes {
    "more nested",
    Nodes {
      Data {2,3,4},
      Data {3,4,5},
      Data {4,5,6},
    },
    "nodes",
  },
};
Equal to source: true
Ucased: Nodes {
  "HELLO",
  Data {1,2,3},
  Nodes {
    "MORE NESTED",
    Nodes {
      Data {2,3,4},
      Data {3,4,5},
      Data {4,5,6},
    },
    "NODES",
  },
};
Equal to cow source: false
Subtree from ucased: Nodes {
  Data {2,3,4},
  Data {3,4,5},
  Data {4,5,6},
};
Subtree from cow: Nodes {
  Data {2,3,4},
  Data {3,4,5},
  Data {4,5,6},
};
Subtrees match: true
Subtrees shared: true
Siblings unshared: true
Parents unshared: true
Roots unshared: true

Answer 2

One way to solve the problem on having to dispatch on unique_ptr<T> is to go back to passing around pointers the way you do in your visitor, but changing the return type to Node*, like this:

// Top-level function stays the same
Node* genericVisit(Node* node) {
    if (dynamic_cast<Subnode2>(node)) {
        return visit(static_cast<Subnode2*>(node));
    }
    // etc
}
// Specialized overloads can return replacements as they go
virtual Node* visit(Subnode2* node) {
    if (mustReplace()) {
        Subnode1 *myReplacement = ...
        return myReplacement;
    }
    if (node->getChild()) {
        Node *replacement = genericVisit(node->getChild());
        // nullptr means no replacement; non-null means we replace the child
        if (replacement) {
            node->setChild(replacement);
        }
    }
    return nullptr;
}

This approach requires implementer to pay attention to what's returned (i.e. nullptr or not) before performing the replacement. On the other hand, it keeps the final decision on performing the replacement in the hands of the function that makes the visitor call, which ultimately translates to more control over the internals, i.e. better encapsulation.