ValueTree searching - 'ValueFinder'

Useful Tools and Components
1

This is a little experimental, but I thought I’d share it now anyway.

Source zip: ValueFinder_v01.zip
[EDIT: fixed a bug affecting the main algorithm]
EDIT: Mirror (if dropbox is down)

There are two sets of files here. The base stuff is in ValueFinder.h/cpp. What this provides is a set of base classes for creating a system that can search through a value tree according to some custom configuration. The flow of it is based on XPath (the XML Path language), although the base ValueFinder doesn’t actually implement any real behaviour - it holds the algorithms and types for building sets of nodes and applying filters to get to an end set of results from a given context node.

I’ve only just got that base framework together, so have quickly slapped together a ‘BasicValueFinder’ to demonstrate it. This takes a simple String path to point to a Value or set of ValueTrees from a given starting point.

Set the path with myFinder.setPath(), and then call myFinder.find(tree) with a node from the tree.

e.g. consider this data…

<Rooty>
  <Node>
    <Frog Cardigan="0"/>
  </Node>
  <OTHER>
    <Sub index="0"/>
    <Sub index="1"/>
  </OTHER>
  <NOTHER>
    <T0 index="0"/>
    <T1 index="1"/>
    <T2 index="2"/>
  </NOTHER>
</Rooty>

The path “/OTHER” would return the node that is a child of the root node.
The path “/NOTHER/[1]” would return the node
etc…

if it starts with a ‘/’ it searches from the root, else the current node.
if the path step has a number in square brackets, it means an index
if the last step starts with an ‘@’, it refers to a property [although, tbh, i haven’t tested that yet ;)]
Oh, and the names can use normal wildcards too.

This is uber basic though, and with absolutely minimal checking or effort! :-o

The rules for this particular path parsing system are handled in BasicValueFinder.cpp - if you look at how that works, it should be reasonably straightforward. If you want to understand more about it, have a look at the XPath spec… [fwiw, if you do, what xpath calls ‘predicates’ i’ve called ‘rules’, and the ‘node test’ is what the TreeSelectorStep’s virtual function is doing]

It’s probably got some bugs in, I’ve only just got it working, but it’s got potential to be megauseful so thought I’d share it now. Feel free to start hacking it up or putting together your own more complex path system - there is a hell of a lot you can do with it.

Other thoughts… it’ll be easy to add functionality to the base class so these searches can be performed asynchronously. I actually wrote that part automatically already but took it out for now as i couldn’t be arsed testing any of that yet! :slight_smile:

2

Heh, just realised theres a huge bug in the step-to-step passing of node sets… (just in case anyone noticed ;))

3

… fixed :slight_smile: [updated link in first post]

4

Nice!

What kind of thing are you using for? Just thinking about all the ValueTree work I’m doing at the moment in the jucer, I can’t really think of anywhere that this would be helpful… (Though I guess I’m not really doing much searching of the trees)

5

There are many uses for it :slight_smile: although one key place it can be of particular use is in serialisation [in fact, this is the main reason I wrote it, although there are other times it’d have been useful]. Let’s say a ValueFinder ‘configuration’ (e.g. a path) is called a locator, and I shall continue :slight_smile:

Consider, at the moment there is no way of serialising a ValueTree containing DynamicObjects. I’m developing a visual modular scripting system, where a tree contains multitudes of nodes, most of which have a DynamicObject property describing their function.

When I wish to write this structure to a file, I am faced with the problem of storing information about these objects in the nodes so that they can be retrieved. However, such information is only useful in serialisation - there is no need for it to be present in the structure at runtime. I’d really rather not have to pollute the structure with descriptors about things that are already there, remove the objects (not strictly necessary, but avoids the assert in debug about not being able to serialise them), serialise, replace, then strip the descriptors out.

Now, if I have a means of locating a specific property in a tree, I am able to write a system to help with this.

Let’s say we have a ‘DynamicObjectSerialiser’ base class. A subclass of this can take a DynamicObject*, and create a description of the object; similarly, it can take such a description and use it to return a pointer to a DynamicObject to restore it.

Now, the function to serialise a tree can take a pointer to a DynamicObjectSerialiser. Whenever a DynamicObject property is encountered, the DynamicObjectSerialiser is notified with a Value. A description of the object is generated, along with a locator generated from the Value. The object’s description is stored in a separate ‘object tree’, along with the locator. As serialisation continues, if an object’s instance is used elsewhere, additional locators can be added to the description. Ultimately, there is now a second tree of (serialisable) data, which can be written along with the main tree data.

When the time comes to reload the structure, we first load the normal tree as usual. This doesn’t have any of the objects in, naturally. However, we then load the object tree, via the DynamicObjectSerialiser. This steps through the object descriptions; it returns a pointer to an appropriate DynamicObject for each one, and then uses the locators to find (in the main tree) the Values it should be stored in.

As you can see, it’s really most useful when you need to refer to a point within a ValueTree structure from some point outside of code, but it can also be useful if you have a particularly large data structure and have to search for multiple nodes based on some kind of rule. e.g. ‘select all triangles in this layout of shapes’.

6

Maybe you should have a look to XPath, your implementation sounds XPath a whole lot.

7

Silly billy, i said it’s based on XPath :slight_smile: [except it’s not actually bound to the language]

8

Interesting, thanks!