Convert nested set in php for nested array without depth parameter
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
)
);
What is this structure:
<label> [0,9]
<label /> [1,2]
<label> [3,8]
<label /> [4,5]
<label /> [6,7]
</label>
</label>
I'm trying to navigate 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 value
// 'close': the key for the right node value
$arrNested = format::nestedSetToArray( $arrData, 'open', 'close' );
So far I have tried this format, assuming the $ arrData values will always be in ascending order from the left . Uid values are also ok, but they are not relied upon:
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 a child of it
} else if( /* condition for sibling */ ) {
// This is 1 greater than the intLastClosed value - so it a sibling
} else if( /* condition for sibling of ancestor */ ) {
// This starts with a value greater than the parent closing value...hmm
}
}
}
}
Any pointers to take this further would be appreciated.
source to share
This should work
$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 am missing the parameterized open and closed tags, but you can just add them.
EDIT
What's going on here:
$stack
Empty at first , so we skip while()
. Then we assign a link to $arraySet
on $link
as $stack
empty, we click on the first item $link
, which refers to $arraySet
. array_push () return 1 because this is the new length of
$ arraySet
Next we add an element to the
$ stack whit values
('index' => 0, 'close' => 10) `
Next item: Now $stack
has 1 item, but $stack[0]['close']
more than the $arrValues['open']
item, so we skip the while. Again we establish a link to $arraySet
on $link
, but now is an element of $stack
, so we assign a link $link[$stack[0]['index']]["children"]
link $ link, so now $link
indicates $arraySet[0]["children"]
. We are now pushing an element to this child array. $tmp
gives us the size of this child array and we push the corresponding element onto the stack.
Next item: It looks exactly like the second one, but first we pop one item off the stack. So after this iteration, there are two items on the stack
('index' => 0, 'close' => 10)
('index' => 0, 'close' => 8)
Next item: There are two items on the stack, but both have a higher attribute close
, and then $arrValues['open']
, so we skip the while loop. Then in the navigation part:
-
$link
points to$arraySet
- then
$arraySet[0]["children"]
- then
$arraySet[0]["children"][0]["children"]
And we push an item onto this array. Etc...
source to share