harris.pc@… — Tue, 02 Aug 2016 08:45:21 GMT

Oh, and to use the property tree, you declare:

   typedef boost::property_tree::basic_ptree<PathString, NodeData> Nodes;

anonymous — Wed, 03 Aug 2016 01:14:01 GMT

Some bugs in the original posted code, see attached file which tests the path_of component. Let me know if you would like me to help make a proper example.

attachment set

harris.pc@… — Wed, 03 Aug 2016 01:14:36 GMT

attachment → main.cpp

bugfixed version, simple version

harris.pc@… — Tue, 10 Jan 2017 07:01:44 GMT

I have some more utilities that I wrote along the way to work with the ptree. Might be useful for someone...

For just visiting every node in the tree:

   // helper, note that visitor is NOT returned,
   // its designed to call the visitor ONCE per node,
   // and then copy that visitor for the children of the node.
   // A "finishing" stage can be done in the visitor's destructor, as it unwinds back up the tree.
   //
   // Note that 'path' passed by reference and maintained during the walk.
   template <class Key, class Data, class Compare, class Visitor>
   void visit_ptree_inner( Key & path, boost::property_tree::basic_ptree<Key,Data,Compare> & tree, Visitor visitor, Key const& key )
   {
      // the key passed is our parent's name for me
      // add to the path, and be prepared to take me off the path when we are done at the end.
      size_t before_path_size = path.size();
      path /= key;   // add our name to the path
      // visit self first
      visitor(path, tree.data());
      // note: visit in order of Compare
      // typedef typename boost::property_tree::basic_ptree<Key,Data,Compare>::iterator It;
      // It end = tree.end();
      typedef typename boost::property_tree::basic_ptree<Key,Data,Compare>::assoc_iterator It;
      const It end = tree.not_found();
      for (It begin = tree.ordered_begin(); begin != end; ++begin)
         visit_ptree_inner(path, begin->second, visitor, begin->first);
      assert(before_path_size <= path.size());
      path.resize(before_path_size);
   }
   template <class Key, class Data, class Compare, class Visitor>
   void visit_ptree( boost::property_tree::basic_ptree<Key,Data,Compare> & tree, Visitor visitor, Key const& key = Key(), Key init_path = Key() )
   {
      visit_ptree_inner(init_path, tree, visitor, key);
   }

I found it annoying to find and edit, or create, nodes in the tree and avoid copies.

So I wrote get_create_ptree() which you can also pass a special Creator function if your node requires some special construction if it doesn't already exist.

You can do things like

NodeData & data = get_create_ptree( TREE, PATH ).second;

   // creates node if it doesn't exist,
   // returns true-flag if node already existed.
   // if it creates the edge-node, it will use the 'creator' visitor to build.
   template <class Key, class Data, class Compare, class CreateEdgeNode>
   pair<bool, Data&> get_create_ptree(
         boost::property_tree::basic_ptree<Key,Data,Compare> & tree,
         typename boost::property_tree::path_of<Key>::type path,
         CreateEdgeNode creator
         )
   {
      typedef boost::property_tree::basic_ptree<Key,Data,Compare> Tree;
      typedef typename Tree::assoc_iterator It;
      typedef typename Tree::value_type Value;
      bool existed = true;
      Tree * parent = &tree;
      while (not path.empty())
      {
         Key fragment = path.reduce(); // this also updates 'path' - shortens it by removing front fragment
         It found_child = parent->find(fragment);
         if (found_child != parent->not_found())
         {
            parent = &found_child->second;
         }
         else
         {
            existed = false;
            // while we haven't been through all the parents...
            while (not path.empty())
            {
               // create a parent node
               parent = &parent->push_back(Value(fragment, Tree()))->second;
               fragment = path.reduce(); // this reduces the path
            }
            parent = &parent->push_back(Value(fragment, Tree(creator())))->second;
            break; // all done
         }
      }
      return pair<bool, Data&>(existed, parent->data());
   }
   template <class T>
   struct Visitor_create_node_default
   {
      T operator()() const { return T(); }
   };
   template <class Key, class Data, class Compare>
   pair<bool, Data&> get_create_ptree(
         boost::property_tree::basic_ptree<Key,Data,Compare> & tree,
         typename boost::property_tree::path_of<Key>::type path
         )
   {
      typedef boost::property_tree::basic_ptree<Key,Data,Compare> Tree;
      return get_create_ptree(tree, path, Visitor_create_node_default<Tree>());
   }

And the most complex one of this post, the 'mirror_ptree()' function.

It traverses two trees at once, the "out_tree" and "in_tree". It has options to create or delete nodes that are missing/extra in the out_tree,

And for each corresponding node, the visitor's methods are called like so:

   struct Example_visitor_mirror
   {
      // called when source is missing AND mirror_ptree() has delete_missing=false
      void operator()( Path const& path, OutTreeNode & out ) const
      {
      }
      // called to copy source to destination (out <-- in)
      void operator()( Path const& path, OutTreeNode & out, InTreeNode const& in ) const
      {
      }
      // only called when mirror_ptree() has insert_missing=true
      OutTreeNode create_missing( Path const& path ) const
      {
         return OutTreeNode(construction etc);
      }
   };

   template <class Key, class DataIn, class DataOut, class Compare, class Visitor>
   void mirror_ptree_inner(
                      Key & path,
                      boost::property_tree::basic_ptree<Key,DataOut,Compare> & out_tree,
                      boost::property_tree::basic_ptree<Key,DataIn,Compare> const& in_tree,
                      bool insert_missing, bool delete_missing,
                      Visitor visitor, Key const& key
                      )
   {
      // the key passed is our parent's name for me
      // add to the path, and be prepared to take me off the path when we are done at the end.
      size_t before_path_size = path.size();
      path /= key;
      // copy across the data for this node
      visitor(path, out_tree.data(), in_tree.data());
      typedef boost::property_tree::basic_ptree<Key,DataOut,Compare> OutTree;
      typedef typename OutTree::assoc_iterator It;
      typedef typename OutTree::value_type Value;
      typedef typename boost::property_tree::basic_ptree<Key,DataIn,Compare>::const_assoc_iterator CIt;
      const CIt in_end = in_tree.not_found();
      if (not in_tree.empty())
      {
         CIt a = in_tree.ordered_begin();
         CIt b = a; ++b;
         for (; b != in_tree.not_found(); ++a, ++b)
            assert(a->first != b->first);
      }
      Compare lessthan;
      CIt in = in_tree.ordered_begin();
      It out = out_tree.ordered_begin();
      while (true) // in != in_end or out != out_tree.not_found())
      {
         // erase out_tree that are missing from in_tree
         if (
               out != out_tree.not_found()
               and (
                  in == in_end
                  or
                  lessthan(out->first, in->first)
                  )
               )
         {
            // erase and increment 'out'
            if (delete_missing)
               out_tree.erase( out_tree.to_iterator(out++) );
            else
            {
               // recurse to visit all of the subitems,
               // we aren't deleting or inserting so it can be a plain visit.
               visit_ptree_inner( path, out->second, visitor, out->first );
               ++out;
            }
         }
         // insert in_tree that are missing
         else if (
               in != in_end
               and (
                  out == out_tree.not_found()
                  or
                  lessthan(in->first, out->first)
                  )
               )
         {
            if (insert_missing)
            {
               size_t before_path_size2 = path.size();
               path /= in->first;   // build the path of this child now
               out_tree.push_back( Value(in->first, OutTree(visitor.create_missing(path))) ); // insert empty node
               path.resize(before_path_size2);  // and go back to our path
               out = out_tree.find(in->first); // find our new location
               assert(out != out_tree.not_found());  // must find!
               // recurse!
               mirror_ptree_inner(
                     path,
                     out->second, in->second,
                     insert_missing, delete_missing,
                     visitor, out->first
                     );
               ++in;
               ++out;
            }
            else
            {
               ++in;
            }
         }
         else if (
               in != in_end
               and
               out != out_tree.not_found()
               )
         {
            // must match if we are here
            assert(not lessthan(in->first, out->first));
            assert(not lessthan(out->first, in->first));
            assert(in->first == out->first); // not always a possible comparison
            // recurse!
            mirror_ptree_inner(
                  path,
                  out->second, in->second,
                  insert_missing, delete_missing,
                  visitor, out->first
                  );
            ++in;
            ++out;
         }
         else
         {
            // if we are here, must have finished both
            assert(in == in_end and out == out_tree.not_found());
            break;
         }
      }
      // and reset path to previous size
      assert(before_path_size <= path.size());
      path.resize(before_path_size);
   }
   template <class Key, class DataIn, class DataOut, class Compare, class Visitor>
   void mirror_ptree( boost::property_tree::basic_ptree<Key,DataOut,Compare> & out_tree,
                      boost::property_tree::basic_ptree<Key,DataIn,Compare> const& in_tree,
                      bool insert_missing, bool delete_missing,
                      Visitor visitor, Key const& key = Key(), Key init_path = Key()
                      )
   {
      mirror_ptree_inner( init_path, out_tree, in_tree, insert_missing, delete_missing, visitor, key );
   }

And here is a kind of for_each for ptree, but you can use it in a plain loop so no functors or closures etc etc. It handles the path efficiently and uses a vector<> stack instead of recursion.

The switch_type stuff is so that you can use it with a const tree.

   // This is a simple stack-based walker that can be used like so:
   //
   // Visits recursively in order of the key,
   // but does not indicate whether you are going deeper or moving up the tree.
   //
   // Will always visit at least once (the base node).
   //
   // for (PTreeWalker it(changes); not it.finished(); it.next())
   // {
   //    path to node = it.path();
   //    nodes data = it.data();
   // }
   //
   // Note: could be extended to match the interface of fs::recursive_directory_iterator
   //
   template <class Choice, class Yes, class No> struct switch_type;
   template <class Yes, class No> struct switch_type<boost::true_type,  Yes, No> { typedef Yes type; };
   template <class Yes, class No> struct switch_type<boost::false_type, Yes, No> { typedef No  type; };
   template <class PTree>
   class PTreeWalker : noncopyable
                       // only noncopyable to help detect incorrect usage,
                       // but could be copied to save loop state
   {
      typedef typename PTree::key_type Key;
      typedef typename boost::is_const<PTree>::type TreeIsConst;
      typedef typename switch_type<
         TreeIsConst,
         typename boost::add_const<typename PTree::data_type>::type,
         typename PTree::data_type
            >::type Data;
      typedef typename switch_type<
         TreeIsConst,
         typename PTree::const_assoc_iterator,
         typename PTree::assoc_iterator
            >::type It;
      // maintains this, appending and resizing as required
      Key m_path;
      struct Level
      {
         Level() : path_len(), subtree(), cursor() {}
         Level(size_t path_len, PTree & tree) :
            path_len(path_len),
            subtree(&tree),
            cursor(tree.ordered_begin())
         {}
         size_t path_len;
         PTree * subtree;  // ALWAYS valid, only a pointer due to vector<> requirements
         It cursor;
      };
      vector<Level> stack;
   public:
      PTreeWalker( PTree & tree, Key init_path = Key() ) :
         m_path(init_path)
      {
         stack.push_back( Level(m_path.size(), tree) );
      }
      Key const& path() const { return m_path; }
      Data & data() { return stack.back().subtree->data(); }
      bool finished() { return stack.empty(); }
      void next()
      {
         // are we finished at this level?  then, go up.
         while (not stack.empty() and stack.back().cursor == stack.back().subtree->not_found())   // aka ::ordered_end();
            stack.pop_back();
         // we fix-up the path in the next step
         // not finished here?
         // then go down a level.
         if (stack.empty())
         {
            m_path.resize(0);
         }
         else
         {
            Level & current = stack.back();
            m_path.resize(current.path_len);
            assert(current.cursor != current.subtree->not_found());
            // note: ++ : remember we have visited this item on this level
            It target = current.cursor++;
            m_path /= target->first;
            stack.push_back( Level(m_path.size(), target->second) );
         }
      }
   };

Boost C++ Libraries: Ticket #12368: Improve property_tree documentation for path_of

attachment set