Finding key level in mutidimensional array

[Manish]

This is the print_r() for a variable $categories.

$categories ::

Array
(
[1003] =Array
(
[1014] =Array
(
[1006] =Array
(
[1018] =0
[1019] =0
)

[1015] =Array
(
[1017] =0
[1016] =0
)

)

[1008] =Array
(
[1005] =0
)

)

[1004] =Array
(
[1020] =0
)
)

Any key in the array at any level is unique. i.e. key 1003 will not
appear twice.

I want to find out at what level the particular key exists.

Thats,

KeyLevel(1003) = 1
KeyLevel(1008) = 2
KeyLevel(1016) = 4

Please suggest on the coding for function KeyLevel().

Thanks.

Manish

[Benjamin Esham]

Manish wrote:

Any key in the array at any level is unique. i.e. key 1003 will not appear
twice.

I want to find out at what level the particular key exists.

Please suggest on the coding for function KeyLevel().

I'll give you a couple of pointers (partly because this looks like a
homework problem, and partly because I don't want to write and test an
entire function :-)).

Write a function to recursively traverse the array: for each element, call
KeyLevel() on the element. Each time you call KeyLevel(), increment a
counter to record how deep you are; each time an instance of KeyLevel()
returns unsuccessfully, decrement the counter. If the desired key is found,
simply return the counter value; otherwise, keep traversing the array until
you find it.

I'll admit, I'm not an experienced programmer, and algorithms were never my
forte, but this should put you on the right track. By the way, if your
input array is sorted, that should make the algorithm much simpler.

HTH,
--
Benjamin D. Esham
bd*****@gmail.com | AIM: bdesham128 | Jabber: same as e-mail
"Kreacher did not see young master," he said, turning around and
bowing to Fred. Still facing the carpet, he added, perfectly
audibly, "Nasty little brat of a blood traitor it is." — OotP

[Manish]

Thanks for the comment.

I have created a function. Please suggest if it is an efficient one, or
some other efficient variations are also available. Is any in-built
function available. I am using PHP 5.

The following function is giving the correct output as per the provided
array.
function KeyLevel($multilevelarr, $key, $currlevel = 0) {
if(is_array($multilevelarr) && count($multilevelarr)) {
foreach($multilevelarr as $thiskey=>$thisvalue) {
if($thiskey == $key) {
return array(1, ($currlevel + 1));
}
}
foreach($multilevelarr as $thiskey=>$thisvalue) {
if(is_array($thisvalue)) {
list($found, $foundlevel) = KeyLevel($thisvalue, $key, $currlevel +
1);
if($found) {
return array(1, $foundlevel);
}
}
}
}
return array(0, 0);
}

Thanks.

Manish


Benjamin Esham wrote:

Manish wrote:

Any key in the array at any level is unique. i.e. key 1003 will not appear
twice.

I want to find out at what level the particular key exists.

Please suggest on the coding for function KeyLevel().

I'll give you a couple of pointers (partly because this looks like a
homework problem, and partly because I don't want to write and test an
entire function :-)).

Write a function to recursively traverse the array: for each element, call
KeyLevel() on the element. Each time you call KeyLevel(), increment a
counter to record how deep you are; each time an instance of KeyLevel()
returns unsuccessfully, decrement the counter. If the desired key is found,
simply return the counter value; otherwise, keep traversing the array until
you find it.

I'll admit, I'm not an experienced programmer, and algorithms were never my
forte, but this should put you on the right track. By the way, if your
input array is sorted, that should make the algorithm much simpler.

HTH,
--
Benjamin D. Esham
bd*****@gmail.com | AIM: bdesham128 | Jabber: same as e-mail
"Kreacher did not see young master," he said, turning around and
bowing to Fred. Still facing the carpet, he added, perfectly
audibly, "Nasty little brat of a blood traitor it is." - OotP

[Manish]

The array is not sorted.

New category id/sub-category id can be added at any time and to any
existing category. The new id value will be one more than the maximum
value. The datas are in database and after retrieving all the rows from
the table, such an array is created, so that to display the categories
in the folder like structure (javascript), at the page load itself.
Like it is in folder view in the explorer window.

So, all the id's will be needed at once at the page load itself, so
that the javascript tree can be created. Strictly speaking, it is just
table hide/show on click.

Benjamin Esham wrote:

Manish wrote:

Any key in the array at any level is unique. i.e. key 1003 will not appear
twice.

I want to find out at what level the particular key exists.

Please suggest on the coding for function KeyLevel().

I'll give you a couple of pointers (partly because this looks like a
homework problem, and partly because I don't want to write and test an
entire function :-)).

Write a function to recursively traverse the array: for each element, call
KeyLevel() on the element. Each time you call KeyLevel(), increment a
counter to record how deep you are; each time an instance of KeyLevel()
returns unsuccessfully, decrement the counter. If the desired key is found,
simply return the counter value; otherwise, keep traversing the array until
you find it.

I'll admit, I'm not an experienced programmer, and algorithms were never my
forte, but this should put you on the right track. By the way, if your
input array is sorted, that should make the algorithm much simpler.

HTH,
--
Benjamin D. Esham
bd*****@gmail.com | AIM: bdesham128 | Jabber: same as e-mail
"Kreacher did not see young master," he said, turning around and
bowing to Fred. Still facing the carpet, he added, perfectly
audibly, "Nasty little brat of a blood traitor it is." - OotP

[Carl Vondrick]

foreach($multilevelarr as $thiskey=>$thisvalue) {
if($thiskey == $key) {
return array(1, ($currlevel + 1));
}
}
foreach($multilevelarr as $thiskey=>$thisvalue) {
if(is_array($thisvalue)) {
list($found, $foundlevel) = KeyLevel($thisvalue, $key, $currlevel +
1);
if($found) {
return array(1, $foundlevel);
}
}
}

Your complexity here is O(2N), when it could just be O(N). These two
loops are identical. My suggestion:

As you loop through them, check BOTH if the key exists or if it's an
array. If it's an array, start a recursion.

I realize, however, that you may want to search for the key first, then
sub-arrays (the best optimization here pivots on the context of the
problem), but I would still have one master loop that stores the arrays
in a hash.

Alternatively, do you have to be using your array structure like that?
May I suggest a more sane, but perhaps more complicated approach? Try
using a parent-child system, as the keys are all identical anyways.

So, for example:
Array
(
[1003] =Array('parent' =null) // Super element
[1014] =Array('parent' =1003) // Child of the super element
[1006] =Array('parent' =1014) // Child of the child
[1018] =Array('parent' =1006, 'value' =0) // Last
[1015] =Array('parent' =1014) // Child of the child
)

And so on. Then, your system is a lot simpler:
1) Find the base key
2) If parent is not null, then find the key of the parent, increase
counter by 1, and repeat. If it is, return the counter.

All the best,
Carl

[Manish]

Thanks for the comment and suggesting the better approach. As I have
mentioned in my previous post, all the datas are in the database and
the first array I have is as you mentioned,

Array
(
[1003] =Array('parent' =null) // Super element
[1014] =Array('parent' =1003) // Child of the super element
[1006] =Array('parent' =1014) // Child of the child
[1018] =Array('parent' =1006, 'value' =0) // Last
[1015] =Array('parent' =1014) // Child of the child
)

>From this array itself I have created a new multidimensional array, as

depicted in first message.
As mentioned in your example data,

[1018] =Array('parent' =1006, 'value' =0) // Last

value=>'0' is added by me, intentionally as just to set some value. It
will either be an array, for if any sub categories are there, and it is
at last, we can set it as null. It just shows that nothing is there
below that level.

So, this array will also work,

Array
(
[1003] =null // Super element
[1014] =1003 // Child of the super element
[1006] =1014 // Child of the child
[1018] =1006 // Last
[1015] =1014 // Child of the child
)

>From this array itself, new array was created, so that when user clicks

on 1006, both id 1018 and 1019 (table with id 1018, 1019) are to be
made visible/hidden.

[1006] =Array
(
[1018] =0
[1019] =0
)
Now, we have to restrict the category creation after say level 5, so I
want to find the current level, so that whether to enable/disable the
button to create more sub-category and display appropriate message.

Thanks.

Manish
Carl Vondrick wrote:

foreach($multilevelarr as $thiskey=>$thisvalue) {
if($thiskey == $key) {
return array(1, ($currlevel + 1));
}
}
foreach($multilevelarr as $thiskey=>$thisvalue) {
if(is_array($thisvalue)) {
list($found, $foundlevel) = KeyLevel($thisvalue, $key, $currlevel +
1);
if($found) {
return array(1, $foundlevel);
}
}
}

Your complexity here is O(2N), when it could just be O(N). These two
loops are identical. My suggestion:

As you loop through them, check BOTH if the key exists or if it's an
array. If it's an array, start a recursion.

I realize, however, that you may want to search for the key first, then
sub-arrays (the best optimization here pivots on the context of the
problem), but I would still have one master loop that stores the arrays
in a hash.

Alternatively, do you have to be using your array structure like that?
May I suggest a more sane, but perhaps more complicated approach? Try
using a parent-child system, as the keys are all identical anyways.

So, for example:
Array
(
[1003] =Array('parent' =null) // Super element
[1014] =Array('parent' =1003) // Child of the super element
[1006] =Array('parent' =1014) // Child of the child
[1018] =Array('parent' =1006, 'value' =0) // Last
[1015] =Array('parent' =1014) // Child of the child
)

And so on. Then, your system is a lot simpler:
1) Find the base key
2) If parent is not null, then find the key of the parent, increase
counter by 1, and repeat. If it is, return the counter.

All the best,
Carl