Tree-like iterator proposal

[puffetto]

Hello,

I am working on a project which requires iterating into the whole JSON document as a tree, I find that others had the same need (see in example #3469) and I need an efficient solution (meaning that, in example, flattening the whole JSON document is not an option in my use-case scenario).

I am thus writing a "tree_iterator", which can be seen as both an iterator and a json_pointer (it is actually a subclass of json_pointer but also meets the requirements of an STL iterator), usable like:

json j = ...;
for(auto& [k, v]: j.tree_items<in>())
  std::cout << k << " is " << v << std:endl;

Which will produce from '{"a":{"b":{"c":[1,2,3]}},"x":"some"}' something like:

/a/b/c/1 is 1
/a/b/c/2 is 2
/a/b/c/3 is 3
/x is some

The template supports three iteration modes: "pre" which iterates also over objects and arrays and returns the object/array before its contents (preorder), "post" which does postorder and "in" which iterate only in leaf values (the closer reasonable thing to "inorder" for a non-binary tree).

So on the same json:

for(auto& [k, v]: j.tree_items<pre>())
  if(v.is_object())
    std::cout << k << " is an object" << std:endl;
  if(v.is_array())
    std::cout << k << " is an array" << std:endl;
  else
    std::cout << k << " is " << v << std:endl;

Will produce:

/a is an object
/a/b is an object
/a/b/c is an array
/a/b/c/1 is 1
/a/b/c/2 is 2
/a/b/c/3 is 3
/x is some

And, to say, flatten could be rewritten as:

json my_flatten(json j) {
 json r;
 for(auto& [k, v]: j.tree_items<in>())
  r[k]=v;
 return r;
}

All methods will be at most O(d * log s), where d is the depth of the "tree" and s is the size of objects; the "tree_iterator" contains simply a JSON pointer and a reference to the JSON object itself, no recursion, the class fails gracefully if the JSON is modified invalidating the pointer.

The code would take some benefit by replacing the escape/unescape functions with linear ones (are currently O(square) for keys like "~~~~~~~~~~"), which I already rewrote and will gladly contribute.

I can integrate this class either as a separate project or by making it an addition to the library; I am wondering if it can be useful to propose it as a PR, as in the second case I will have my project use a fork until the PR kicks in.

So my question is: do you think this "tree iterator" could be a contribution of general benefit to the library?

Thanks,

A.

[nlohmann]

This sounds cool! Yes, please do!

[puffetto]

Will do then,

as I am not much "into" the library internals this will require some time (and possibly some help) to sail into the templates/namespaces complexity; I will start a piece at a time by contributing the "building blocks" I need in the next weeks; thus also giving you a chance to review the code a piece at a time.

Thank you,

A.