到达多维对象数组的底部

Question

I have an SQL connection which outputs an array of objects and it is sorted like so

(
    [0] => listItem Object
        (
            [name] => TV
            [parentId] => 0
            [id] => 1
            [childs] => Array
                (
                    [0] => listItem Object
                        (
                            [name] => mini tv
                            [parentId] => 1
                            [id] => 29
                            [childs] => Array
                                (
                                    [0] => listItem Object
                                        (
                                            [name] => tiny TV
                                            [parentId] => 29
                                            [id] => 548
                                        )

                                )

                        )

                )

        )

    [1] => listItem Object
        (
            [name] => RADIO
            [parentId] => 0
            [id] => 2
            [childs] => Array
                (
                    [0] => listItem Object
                        (
                            [name] => mini radio
                            [parentId] => 2
                            [id] => 30
                        )

                    [1] => listItem Object
                        (
                            [name] => Tiny LCD
                            [parentId] => 2
                            [id] => 551
                        )

                )

        )

    [2] => listItem Object
        (
            [name] => Stereo
            [parentId] => 0
            [id] => 550
        )

    [3] => listItem Object
        (
            [name] => Joe the Plumber
            [parentId] => 0
            [id] => 568
            [childs] => Array
                (
                    [0] => listItem Object
                        (
                            [name] => Joe the Plumber
                            [parentId] => 568
                            [id] => 569
                            [childs] => Array
                                (
                                    [0] => listItem Object
                                        (
                                            [name] => Joe the Plumber
                                            [parentId] => 569
                                            [id] => 570
                                            [childs] => Array
                                                (
                                                    [0] => listItem Object
                                                        (
                                                            [name] => Joe the Plumber
                                                            [parentId] => 570
                                                            [id] => 571
                                                        )

                                                )

                                        )

                                )

                        )

                )

        )

)

I am sorting it this way since I want to output it as a with the proper hierarchy.

I have this function

function buildHTML($tree){
  echo 'building tree';
  foreach($tree as $item){
      $topItem = makeHtmlListItem($item);
       $pos = strpos($topItem, '</li>');
       $newItem = substr($topItem,0 , $pos);
       echo $newItem;
        foreach($item->childs as $subItem){
         echo '<ul>' . makeHtmlListItem($subItem) . '</ul>' ;
        }
echo '</li>';
 }
}

But it only gets to the second level. How do I get to the bottom with an arbitrary depth? I managed to do it with recursion but now I want to do it without recursion and I am going nuts.

Answer 1

You could always use the stack approach, pretty much what you would use before recursion was a possibility — this is all that recursively calling a function is really doing anyway, it's just stacking parameters instead.

The following just uses a stacked array (FILO) to store the current array being dealt with and another stacked array to keep track of the current array index at that level. I've used two arrays for simplicity but you could construct a structure that could store both array and current index in the same object. The following obvsiously will only work for non-associative arrays:

Your base class:

class listItem {
  public $name = '';
  public $parentId = 0;
  public $id = 0;
  public $childs = NULL;
  public function __construct($name, $parentId, $id, $childs = NULL){
    $this->name = $name;
    $this->parentId = $parentId;
    $this->id = $id;
    $this->childs = $childs;
  }
}

Your base data:

$data = array(
  new listItem('TV', 0, 1,
    array(
      new listItem('mini tv', 1, 29,
        array(
          new listItem('tiny tv', 29, 548),
        )
      ),
    )
  ),
  new listItem('RADIO', 0, 2,
    array(
      new listItem('mini radio', 2, 30),
      new listItem('Tiny LCD', 2, 551),
    )
  ),
  new listItem('Stereo', 0, 550),
  new listItem('Joe the Plumber', 0, 568,
    array(
      new listItem('Joe the Plumber', 568, 569,
        array(
          new listItem('Joe the Plumber', 569, 570,
            array(
              new listItem('Joe the Plumber', 570, 571)
            )
          )
        )
      )
    )
  ),
);

A traverse method:

function traverse( $data ){
  $stack = array( $data );
  $place = array( 0 );
  $build = '<ul>';
  while ( $stack ) {
    $a = end($stack);
    $i = end($place);
    $k = key($place);
    $place[$k]++;
    if ( isset($a[$i]) ) {
      $item = $a[$i];
      $build .='<li><span>' . $item->name . '</span>';
      if ( $item->childs ) {
        $build .= '<ul>';
        $stack[] = $item->childs;
        $place[] = 0;
      }
    }
    else {
      array_pop($stack);
      array_pop($place);
      $build .= '</ul>' . ( $stack ? '</li>' : '' );
    }
  }
  return $build;
}

usage:

echo traverse( $data );

with comments:

function traverse( $data ){
  /// prep the stack
  $stack = array( $data );
  $place = array( 0 );
  /// I've tailored the build to be for list items
  $build = '<ul>';
  /// loop until we have no more stack
  while ( $stack ) {
    /// you could improve optimisation at the cost of readability
    /// by storing the end offsets rather than using `end()`.
    $a = end($stack); /// current array
    $i = end($place); /// current offset in that array
    $k = key($place); /// key used to update current offset
    /// update the current levels array index
    $place[$k]++;
    /// if we have an item, investigate
    if ( isset($a[$i]) ) {
      $item = $a[$i];
      /// output our list item
      $build .='<li><span>' . $item->name . '</span>';
      /// if we have children, level up the stack
      if ( $item->childs ) {
        $build .= '<ul>';
        $stack[] = $item->childs; /// adding child array for next iteration
        $place[] = 0; /// start scanning childs from 0 offset
      }
    }
    /// if no more items at this level, level down the stack
    else {
      array_pop($stack);
      array_pop($place);
      /// always output a ul at this point, but not an li at the end
      $build .= '</ul>' . ( $stack ? '</li>' : '' );
    }
  }
  /// the final html returned
  return $build;
}

output:

<ul>
  <li>
    <span>TV</span>
    <ul>
      <li>
        <span>mini tv</span>
        <ul>
          <li><span>tiny tv</span></li>
        </ul>
      </li>
    </ul>
  </li>
  <li>
    <span>RADIO</span>
    <ul>
      <li>
        <span>mini radio</span>
      </li>
      <li>
        <span>Tiny LCD</span>
      </li>
    </ul>
  </li>
  <li>
    <span>Stereo</span>
  </li>
  <li>
    <span>Joe the Plumber</span>
    <ul>
      <li>
        <span>Joe the Plumber</span>
        <ul>
          <li>
            <span>Joe the Plumber</span>
            <ul>
              <li>
                <span>Joe the Plumber</span>
              </li>
            </ul>
          </li>
        </ul>
      </li>
    </ul>
  </li>
</ul>