Improve property_tree documentation for path_of

[harris.pc@…]

There is no documentation on the path_of system,

I did find this helpful email: ​http://lists.boost.org/Archives/boost/2009/06/152883.php

It would be great if something like that were in the official documentation.

In the end, I managed to create my own extension for storing a tree of filenames, here is the key code, just in case you feel its a good example for the documentation.

(Code is still not fully tested)

// a custom path-string,
// I am not using fs::path because I need to treat a directory and a file
// differently in terms of the name, where
// a directory has a / on the end of its name.
// This allows me to have a tree with a file and folder existing in the tree
// at the same time (the file may have been replaced with the folder, so one
// is deleted and the other is created).
//
class PathString
{
   string filename;
public:
   PathString( string const& p ) : filename(p) {}

   bool is_dir() const { return not empty() and filename[filename.size()-1] == '/'; }

   string const& str() const { return filename; }

   bool empty() const { return filename.empty(); }

   bool operator<( PathString const& b ) const
   {
      return filename < b.filename;
   }

   bool operator==( PathString const& b ) const
   {
      return filename == b.filename;
   }
};


   

namespace boost {
   namespace property_tree {

      // specialisation of path_of for PathString
      template <>
      struct path_of<PathString>
      {
         struct type
         {
            std::string filename;
            std::string::size_type start, size;

         public:
            type( std::string const& s ) :
               filename(s),
               start(0),
               size(filename.size())
            {}

            std::string dump() const
            {
               return filename.substr(start);
            }

            bool empty() const
            {
               return start == size;
            }

            // aka pop_front() and return the fragment
            // modifies this value
            std::string reduce()
            {
               assert(not empty());

               std::string::size_type next_sep = filename.find('/', start);

               // no separator, or separator found at the end
               if (next_sep == std::string::npos or next_sep+1 == size)
               {
                  std::string part;
                  part.swap(filename);
                  return part;
               }

               // include the trailing separator
               std::string::size_type old_start = start;
               start = next_sep+1;

               return filename.substr(old_start, start-old_start);
            }


            bool single() const
            {
               // will return true if empty, it should not be asked for empty paths anyway

               // it is a "single" path if there is a slash BEFORE the last character.
               // if the last character is /, then it can be a "single" directory.
               //
               // so check if idx < filename.size()-1 --therefore--> idx+1 < filename.size()
               std::string::size_type idx = filename.find('/');
               return idx == std::string::npos or idx+1 < filename.size();
            }
         };
      };

[harris.pc@…]

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

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

[anonymous]

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.

[harris.pc@…]

bugfixed version, simple version

[harris.pc@…]

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) );
         }
      }
   };