Convert Nested set in php to nested array without depth parameter

Question

Given an array:

$arrData = array(
 0 => array (
   'uid'   => 1,
   'name'  => 'label',
   'open'  => 0,
   'close' => 9
 ),
 1 => array (
   'uid'   => 2,
   'name'  => 'label',
   'open'  => 1,
   'close' => 2
 ),
 2 => array (
   'uid'   => 3,
   'name'  => 'label',
   'open'  => 3,
   'close' => 8
 ),
 3 => array (
   'uid'   => 4,
   'name'  => 'label',
   'open'  => 4,
   'close' => 5
 ),
 4 => array (
   'uid'   => 5,
   'name'  => 'label',
   'open'  => 6,
   'close' => 7
 )
);

Which represents this structure:

<label>     [0,9]
 <label />  [1,2]
 <label>    [3,8]
  <label /> [4,5]
  <label /> [6,7]
 </label>
</label>

I am trying to get to an array that results in this format:

$arrNesting = array(
 0=>array(
   'item'    => array('uid'=>1, 'name'=>'label', 'open'=>0, 'close'=>9),
   'children' => array(
     0=>array(
       'item'     => array('uid'=>2, 'name'=>'label', 'open'=>1, 'close'=>2),
       'children' => array()
     ),
     1=>array(
       'item'     => array('uid'=>3, 'name'=>'label', 'open'=>3, 'close'=>8),
       'children' => array(
         0=>array(
           'item'     => array('uid'=>2, 'name'=>'label', 'open'=>4, 'close'=>5),
           'children' => array()
         ),
         1=>array(
           'item'     => array('uid'=>3, 'name'=>'label', 'open'=>6, 'close'=>7),
           'children' => array()
         )
       )
     )
   )
 )
);

via a function call like this:

// $arrData: Source Data with keys for denoting the left and right node values
// 'open': the key for the left node's value
// 'close': the key for the right node's value
$arrNested = format::nestedSetToArray( $arrData, 'open', 'close' );

So far, I've tried this format, assuming the $arrData values will always be in left value ascending order. The uid values 'happen' to also be in order, but are not relied upon to be so:

public static function nestedSetToArray( $arrData = array(), $openKey='open', $closeKey='close') {
// Hold the current Hierarchy
$arrSets = array();

// Last parent Index, starting from 0
$intIndex = 0;

// Last Opened and Closed Node Values, and maximum node value in this set
$intLastOpened = 0;
$intLastClosed = null;
$intMaxNodeNum = null;

// loop through $arrData
foreach( $arrData as $intKey=>$arrValues) {
  if( !isset( $arrSets[ $intIndex ] )) {
      // Create a parent if one is not set - should happen the first time through
      $arrSets[ $intIndex ] = array ('item'=>$arrValues,'children'=>array());
      $intLastOpened = $arrValues[ $openKey ];
      $intLastClosed = null; // not sure how to set this for checking 2nd IF below
      $intMaxNodeNum = $arrValues[ $closeKey ];
  } else {
      // The current item in $arrData must be a sibling or child of the last one or sibling of an ancestor
      if( $arrValues[ $openKey ] == $intLastOpened + 1) {
         // This is 1 greater then an opening node, so it's a child of it
      } else if( /* condition for sibling */ ) {
         // This is 1 greater than the intLastClosed value - so it's a sibling
      } else if( /* condition for sibling of ancestor */ ) {
         // This starts with a value greater than the parent's closing value...hmm
      }
  }
}

}

Any pointers to take this further would be appreciated.

abc667 · Accepted Answer · 2013-02-03 21:50:47Z

9

This should works

$stack = array();
$arraySet = array();


foreach( $arrData as $intKey=>$arrValues) {
    $stackSize = count($stack); //how many opened tags?
    while($stackSize > 0 && $stack[$stackSize-1]['close'] < $arrValues['open']) {
            array_pop($stack); //close sibling and his childrens
            $stackSize--;
        }

    $link =& $arraySet;
    for($i=0;$i<$stackSize;$i++) {
        $link =& $link[$stack[$i]['index']]["children"]; //navigate to the proper children array
    }
    $tmp = array_push($link,  array ('item'=>$arrValues,'children'=>array()));
    array_push($stack, array('index' => $tmp-1, 'close' => $arrValues['close']));

}

return $arraySet;

I skip parametrized open and close tags but you can simply add it.

EDIT

What is happening here:

First the $stack is empty so we skip while(). Then we assign reference to $arraySet to the $link, because $stack is empty we push first element to $link which is reference to $arraySet. array_push()return 1 because this is the new length of$arraySetNext we add an element to the$stackwhit values('index' => 0, 'close' => 10)`

Next element: Now $stack has 1 element, but $stack[0]['close'] is greater than $arrValues['open'] for element so we skip while. Again we set reference to $arraySet to $link but now there is on element in $stack so we assign $link[$stack[0]['index']]["children"] reference to $link so now $link is pointing to $arraySet[0]["children"]. Now we push element to this children array. $tmp gives us size of this children array and we push proper element to the stack.

Next element: It looks exactly like second one but at the beginning we pop one element from stack. So after this iteration on stack are two elements

('index' => 0, 'close' => 10)
('index' => 0, 'close' => 8)

Next element: There is two element on stack but both have greater close attribute then $arrValues['open'] so we skip while loop. Then in navigation part:

$link is pointing to $arraySet
then to $arraySet[0]["children"]
then to $arraySet[0]["children"][0]["children"]

And we push element to this array. And so on...

edited Feb 3, 2013 at 21:50

answered Feb 3, 2013 at 19:26

abc667

5144 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

MyStream Over a year ago

I'm going to read through this a few times - I'm not sure what's happening throughout. Then I'll come back!

abc667 Over a year ago

I delete redundant if and add some comments

MyStream Over a year ago

I still can't follow this example :(

abc667 Over a year ago

I add some explanations to the algorithm. My english is not very well so if you have any question please ask.

MyStream Over a year ago

Hi :) I still don't understand how it works, but it does work and solves my problem cleanly. If anyone could help with the wording here, this seems to be compact and efficient. Thanks!

Collectives™ on Stack Overflow

Convert Nested set in php to nested array without depth parameter

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related