Working with a forest of binary trees stored in a

Question

I have an array like 'var1'=>1.05, 'var2'=>0.76,... and a forest of binary trees stored in a 100+ MB XML file.

<Tree id="1">
<Node id="2">
   <SimplePredicate field="var1" operator="lessOrEqual" value="1.41"/>
   <Node id="4">
     <SimplePredicate field="var2" operator="lessOrEqual" value="1.43"/>
     .......
     </Node>
</Node>
<Node id="3">
   <SimplePredicate field="var1" operator="greaterThan" value="1.41"/>
   .......
</Node>
</Tree>

What I'd like to do in PHP is for each tree to store properties of a leaf in which I'll end up based on the conditions given by each node. So in this example the path will be (2)->(4)->...

Because of the file size it's clear XMLReader is the proper tool for reading each tree. Because the trees are quite small, they can be stored into memory while working with each. What would be the most straightforward way to work with the trees?

Answer 1

You're on the right track with XMLReader. Rather conveniently it includes the method expand() which will return a copy of the current node as a DOMNode. This will let you handle each individual Tree in memory with the DOM API.

As for handling nodes - evaluate and descend recursively.

---

Example:

$data = [
    'var1' => 1.05,
    'var2' => 0.76
];

$dom    = new DOMDocument();
$xpath  = new DOMXPath($dom);
$reader = new XMLReader();
$reader->open('forest.xml');

// Read until reaching the first Tree.
while ($reader->read() && $reader->localName !== 'Tree');

while ($reader->localName === 'Tree') {
    $tree = $dom->importNode($reader->expand(), true);

    echo evaluateTree($data, $tree, $xpath), "\n";

    // Move on to the next.
    $reader->next('Tree');
}

$reader->close();

function evaluateTree(array $data, DOMElement $tree, DOMXPath $xpath)
{
    foreach ($xpath->query('./Node', $tree) as $node) {
        $field    = $xpath->evaluate('string(./SimplePredicate/@field)', $node);
        $operator = $xpath->evaluate('string(./SimplePredicate/@operator)', $node);
        $value    = $xpath->evaluate('string(./SimplePredicate/@value)', $node);

        if (evaluatePredicate($data[$field], $operator, $value)) {
            // Descend recursively.
            return evaluateTree($data, $node, $xpath);
        }
    }

    // Reached the end of the line.
    return $tree->getAttribute('id');
}

function evaluatePredicate($left, $operator, $right)
{
    switch ($operator) {
        case "lessOrEqual":
            return $left <= $right;
        case "greaterThan":
            return $left > $right;
        default:
            return false;
    }
}

---

Output:

4