We have a data structure where each item stores -- among other things -- its depth. Its parent the closest previous item which has a smaller depth: To show an example:

A:depth 0
B:depth 1
C:depth 1
D:depth 2
E:depth 1
F:depth 2
G:depth 0
H:depth 1
I:depth 1

The parents in this case is

• A: root
• B: A
• C: A
• D: C
• E: A
• F: E
• G: root
• H: G
• J: G

My code is:

<?php
  function parentItems(\ArrayAccess|\Traversable $items, object $root_object): \SplObjectStorage {
    $parent_stack =  new \SplStack();
    $parent_items = new \SplObjectStorage();
    // The tree starts with the root.
    $previous_item = $root_object;
    // Top level items have a depth of 0 and the root needs to be even less
    // deep.
    $previous_depth = -1;
    foreach ($items as $item) {
      $depth = (int) $item->getDepth();
      // if the current depth is higher than the previous one then the
      // previous item is the current parent.
      if ($depth > $previous_depth) {
        $parent_stack->push($previous_item);
      }
      // On the other hand, if the current element is less deep than the
      // previous one, then the previous parents are no longer needed.
      elseif ($depth < $previous_depth) {
        for ($i = 0; $i < $previous_depth - $depth; $i  ) {
          $parent_stack->pop();
        }
      }
      // At this point, the stack top contains the current parent.
      $parent_items[$item] = $parent_stack->top();
      $previous_depth = $depth;
      $previous_item = $item;
    }
    return $parent_items;
  }
// Example dataset
$depths = [0,1,2,1,2,2,3,1,1,1,0,1,2,0,0,0,1,2,1,1,0,1,0,1,1,0,1,2,2,1,0,1,1,0,1,1,0,1,1,1,0,1,2,3,3,0,0,0,];
$a = new ArrayObject();
foreach ($depths as $depth) {
  $a[] = new class($depth) {
    protected $depth;
    function __construct($depth) { $this->depth = $depth; }
    function getDepth() { return $this->depth; }
  };
}
parentItems($a);
?>

While this looks relatively straightforward and it does work, keeping the previous item around makes me unhappy, not quite sure why, but it feels wrong. Could we do without it? While arrays have prev() iterators AFAIK do not.

CodePudding user response：

Oh, ok, for that case I have another idea. We can use depth as index to array $lastItemsByDepth, because the parent of the item is the last item with the depth-1 so we keep it in the $lastItemsByDepth array and access it by the items depth. And rewrite previous array element or add new one every step. So, maybe my answer is not correct, because OP wanted not to keep the previous item, but here we are keeping an item to every depth. But this solution seems to be more simple.

$lastItemsByDepth[0] = $root_object;

foreach ($items as $item) {
    $parents_items[$item] = $lastItemsByDepth[(int)$item->getDepth()];
    $lastItemsByDepth[(int)$item->getDepth() 1] = $item;
}