Boost C++ Libraries: Ticket #12368: Improve property_tree documentation for path_of https://svn.boost.org/trac10/ticket/12368 <p> There is no documentation on the path_of system, </p> <p> I did find this helpful email: <a class="ext-link" href="http://lists.boost.org/Archives/boost/2009/06/152883.php"><span class="icon">​</span>http://lists.boost.org/Archives/boost/2009/06/152883.php</a> </p> <p> It would be great if something like that were in the official documentation. </p> <p> 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. </p> <p> (Code is still not fully tested) </p> <pre class="wiki">// 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&amp; p ) : filename(p) {} bool is_dir() const { return not empty() and filename[filename.size()-1] == '/'; } string const&amp; str() const { return filename; } bool empty() const { return filename.empty(); } bool operator&lt;( PathString const&amp; b ) const { return filename &lt; b.filename; } bool operator==( PathString const&amp; b ) const { return filename == b.filename; } }; namespace boost { namespace property_tree { // specialisation of path_of for PathString template &lt;&gt; struct path_of&lt;PathString&gt; { struct type { std::string filename; std::string::size_type start, size; public: type( std::string const&amp; 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 &lt; filename.size()-1 --therefore--&gt; idx+1 &lt; filename.size() std::string::size_type idx = filename.find('/'); return idx == std::string::npos or idx+1 &lt; filename.size(); } }; }; </pre> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/12368 Trac 1.4.3 harris.pc@… Tue, 02 Aug 2016 08:45:21 GMT <link>https://svn.boost.org/trac10/ticket/12368#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/12368#comment:1</guid> <description> <p> Oh, and to use the property tree, you declare: </p> <pre class="wiki"> typedef boost::property_tree::basic_ptree&lt;PathString, NodeData&gt; Nodes; </pre> </description> <category>Ticket</category> </item> <item> <dc:creator>anonymous</dc:creator> <pubDate>Wed, 03 Aug 2016 01:14:01 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/12368#comment:2 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/12368#comment:2</guid> <description> <p> 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. </p> </description> <category>Ticket</category> </item> <item> <author>harris.pc@…</author> <pubDate>Wed, 03 Aug 2016 01:14:36 GMT</pubDate> <title>attachment set https://svn.boost.org/trac10/ticket/12368 https://svn.boost.org/trac10/ticket/12368 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">main.cpp</span> </li> </ul> <p> bugfixed version, simple version </p> Ticket harris.pc@… Tue, 10 Jan 2017 07:01:44 GMT <link>https://svn.boost.org/trac10/ticket/12368#comment:3 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/12368#comment:3</guid> <description> <p> I have some more utilities that I wrote along the way to work with the ptree. Might be useful for someone... </p> <p> For just visiting every node in the tree: </p> <pre class="wiki"> // 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 &lt;class Key, class Data, class Compare, class Visitor&gt; void visit_ptree_inner( Key &amp; path, boost::property_tree::basic_ptree&lt;Key,Data,Compare&gt; &amp; tree, Visitor visitor, Key const&amp; 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&lt;Key,Data,Compare&gt;::iterator It; // It end = tree.end(); typedef typename boost::property_tree::basic_ptree&lt;Key,Data,Compare&gt;::assoc_iterator It; const It end = tree.not_found(); for (It begin = tree.ordered_begin(); begin != end; ++begin) visit_ptree_inner(path, begin-&gt;second, visitor, begin-&gt;first); assert(before_path_size &lt;= path.size()); path.resize(before_path_size); } template &lt;class Key, class Data, class Compare, class Visitor&gt; void visit_ptree( boost::property_tree::basic_ptree&lt;Key,Data,Compare&gt; &amp; tree, Visitor visitor, Key const&amp; key = Key(), Key init_path = Key() ) { visit_ptree_inner(init_path, tree, visitor, key); } </pre><p> I found it annoying to find and edit, or create, nodes in the tree and avoid copies. </p> <p> 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. </p> <p> You can do things like </p> <pre class="wiki">NodeData &amp; data = get_create_ptree( TREE, PATH ).second; </pre><pre class="wiki"> // 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 &lt;class Key, class Data, class Compare, class CreateEdgeNode&gt; pair&lt;bool, Data&amp;&gt; get_create_ptree( boost::property_tree::basic_ptree&lt;Key,Data,Compare&gt; &amp; tree, typename boost::property_tree::path_of&lt;Key&gt;::type path, CreateEdgeNode creator ) { typedef boost::property_tree::basic_ptree&lt;Key,Data,Compare&gt; Tree; typedef typename Tree::assoc_iterator It; typedef typename Tree::value_type Value; bool existed = true; Tree * parent = &amp;tree; while (not path.empty()) { Key fragment = path.reduce(); // this also updates 'path' - shortens it by removing front fragment It found_child = parent-&gt;find(fragment); if (found_child != parent-&gt;not_found()) { parent = &amp;found_child-&gt;second; } else { existed = false; // while we haven't been through all the parents... while (not path.empty()) { // create a parent node parent = &amp;parent-&gt;push_back(Value(fragment, Tree()))-&gt;second; fragment = path.reduce(); // this reduces the path } parent = &amp;parent-&gt;push_back(Value(fragment, Tree(creator())))-&gt;second; break; // all done } } return pair&lt;bool, Data&amp;&gt;(existed, parent-&gt;data()); } template &lt;class T&gt; struct Visitor_create_node_default { T operator()() const { return T(); } }; template &lt;class Key, class Data, class Compare&gt; pair&lt;bool, Data&amp;&gt; get_create_ptree( boost::property_tree::basic_ptree&lt;Key,Data,Compare&gt; &amp; tree, typename boost::property_tree::path_of&lt;Key&gt;::type path ) { typedef boost::property_tree::basic_ptree&lt;Key,Data,Compare&gt; Tree; return get_create_ptree(tree, path, Visitor_create_node_default&lt;Tree&gt;()); } </pre><p> And the most complex one of this post, the 'mirror_ptree()' function. </p> <p> 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, </p> <p> And for each corresponding node, the visitor's methods are called like so: </p> <pre class="wiki"> struct Example_visitor_mirror { // called when source is missing AND mirror_ptree() has delete_missing=false void operator()( Path const&amp; path, OutTreeNode &amp; out ) const { } // called to copy source to destination (out &lt;-- in) void operator()( Path const&amp; path, OutTreeNode &amp; out, InTreeNode const&amp; in ) const { } // only called when mirror_ptree() has insert_missing=true OutTreeNode create_missing( Path const&amp; path ) const { return OutTreeNode(construction etc); } }; </pre><pre class="wiki"> template &lt;class Key, class DataIn, class DataOut, class Compare, class Visitor&gt; void mirror_ptree_inner( Key &amp; path, boost::property_tree::basic_ptree&lt;Key,DataOut,Compare&gt; &amp; out_tree, boost::property_tree::basic_ptree&lt;Key,DataIn,Compare&gt; const&amp; in_tree, bool insert_missing, bool delete_missing, Visitor visitor, Key const&amp; 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&lt;Key,DataOut,Compare&gt; OutTree; typedef typename OutTree::assoc_iterator It; typedef typename OutTree::value_type Value; typedef typename boost::property_tree::basic_ptree&lt;Key,DataIn,Compare&gt;::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-&gt;first != b-&gt;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-&gt;first, in-&gt;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-&gt;second, visitor, out-&gt;first ); ++out; } } // insert in_tree that are missing else if ( in != in_end and ( out == out_tree.not_found() or lessthan(in-&gt;first, out-&gt;first) ) ) { if (insert_missing) { size_t before_path_size2 = path.size(); path /= in-&gt;first; // build the path of this child now out_tree.push_back( Value(in-&gt;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-&gt;first); // find our new location assert(out != out_tree.not_found()); // must find! // recurse! mirror_ptree_inner( path, out-&gt;second, in-&gt;second, insert_missing, delete_missing, visitor, out-&gt;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-&gt;first, out-&gt;first)); assert(not lessthan(out-&gt;first, in-&gt;first)); assert(in-&gt;first == out-&gt;first); // not always a possible comparison // recurse! mirror_ptree_inner( path, out-&gt;second, in-&gt;second, insert_missing, delete_missing, visitor, out-&gt;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 &lt;= path.size()); path.resize(before_path_size); } template &lt;class Key, class DataIn, class DataOut, class Compare, class Visitor&gt; void mirror_ptree( boost::property_tree::basic_ptree&lt;Key,DataOut,Compare&gt; &amp; out_tree, boost::property_tree::basic_ptree&lt;Key,DataIn,Compare&gt; const&amp; in_tree, bool insert_missing, bool delete_missing, Visitor visitor, Key const&amp; key = Key(), Key init_path = Key() ) { mirror_ptree_inner( init_path, out_tree, in_tree, insert_missing, delete_missing, visitor, key ); } </pre><p> 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&lt;&gt; stack instead of recursion. </p> <p> The switch_type stuff is so that you can use it with a const tree. </p> <pre class="wiki"> // 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 &lt;class Choice, class Yes, class No&gt; struct switch_type; template &lt;class Yes, class No&gt; struct switch_type&lt;boost::true_type, Yes, No&gt; { typedef Yes type; }; template &lt;class Yes, class No&gt; struct switch_type&lt;boost::false_type, Yes, No&gt; { typedef No type; }; template &lt;class PTree&gt; 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&lt;PTree&gt;::type TreeIsConst; typedef typename switch_type&lt; TreeIsConst, typename boost::add_const&lt;typename PTree::data_type&gt;::type, typename PTree::data_type &gt;::type Data; typedef typename switch_type&lt; TreeIsConst, typename PTree::const_assoc_iterator, typename PTree::assoc_iterator &gt;::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 &amp; tree) : path_len(path_len), subtree(&amp;tree), cursor(tree.ordered_begin()) {} size_t path_len; PTree * subtree; // ALWAYS valid, only a pointer due to vector&lt;&gt; requirements It cursor; }; vector&lt;Level&gt; stack; public: PTreeWalker( PTree &amp; tree, Key init_path = Key() ) : m_path(init_path) { stack.push_back( Level(m_path.size(), tree) ); } Key const&amp; path() const { return m_path; } Data &amp; data() { return stack.back().subtree-&gt;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-&gt;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 &amp; current = stack.back(); m_path.resize(current.path_len); assert(current.cursor != current.subtree-&gt;not_found()); // note: ++ : remember we have visited this item on this level It target = current.cursor++; m_path /= target-&gt;first; stack.push_back( Level(m_path.size(), target-&gt;second) ); } } }; </pre> </description> <category>Ticket</category> </item> </channel> </rss>