[RESOLVED] Condense user matrix with unknown number of nested levels

[scrupul0us]

I have a very long list of user and owner pairs.

In this scenario, a user can be an owner:

user1 array(a,b,c,d,e)
user2 array(1,2,3,user1)
user3 array(dog,cat,orange,user2)

My current dump of said users is simply:

$accounts[$owner][$user] = '';

on the first pass I run:

	if(array_key_exists($user,$accounts))
	{
		$accounts[$owner][$user] = $accounts[$user];
		unset($accounts[$user]);
	}
	else
	{
		$accounts[$owner][$user] = '';
	}

now that works, but only grabs the first level of nesting

whats the most efficient way to condense this relationship down into a hierarchical array

user3
--dog
--cat
--orange
--user2
----1
----2
----3
----user1
------a
------b
------c
------d
------e
------f
user4
--tree
--frog
--leaf

thank you =)

[Weedpacket]

The most straightforward method would seem to me to be recursively.

Have the function look at each element of the array. If the value is a user, have the function add the appropriate child array and then call itself to examine the elements of that child array.

You'll get into trouble if there are loops, though.

A more efficient data structure would be to distinguish between users and non-users and keep them separate to begin with; look up child arrays as needed.

[scrupul0us]

I agree, with the better structure however I'm playing with the cards I've been dealt... No aces either...

I'll give array_walk_recursive a try... There are no loops luckily =)

[scrupul0us]

Ok so I'm playing around with array_walk_recursive (which I'll be honest I haven't used much) annnd I'm not getting very far:

function condenseOwnership($item,$key,$accounts)
{
        if(array_key_exists($key,$accounts))
        {
                $key = $accounts[$key];
                unset($accounts[$key]);
        }
}

array_walk_recursive($accounts,'condenseOwnership',$accounts);

I'm getting illegal offset errors during the unset annnnd it's not actually condensing anything.

I tried using '&' to see if maybe I needed to be passing via reference, but that didn't help.

If I simply echo $key I do get every key (user and owner) in my array soooo to me this should be working

Again, new to A_W_R to I'm sure I've made an oversight =)

Also, happy t-day

[Weedpacket]

array_walk_recursive would be more useful if the array were already in the form you're trying to get.

If I understand your sketch of your input data, it looks something like this:

array(
	'user1' => array(a,b,c,d,e),
	'user2' => array(1,2,3,user1),
	'user3' => array(dog,cat,orange,user2)
);

And you want

array(
	'user3' => array('dog'=>'', 'cat'=>'', 'orange'=>'', 
		'user2' => array('1'=>'', '2'=>'', '3'=>'',
			'user1'=> array('a'=>'', 'b'=>'', 'c'=>'', 'd'=>'', 'e'=>'')));
);

I started with a recursive solution, then when I realised it was tail-recursive I unrolled it to work iteratively.

function condenseOwnership($accounts)
{
    $accounts = array_map(function($f)
    {
        return array_fill_keys($f, '');
    }, $accounts);

    do
    {
        $did_something = false;
        foreach($accounts as $user=>$account)
        {
            foreach(array_keys(array_intersect_key($accounts, $account)) as $subaccount)
            {
                $accounts[$user][$subaccount] = $accounts[$subaccount];
                unset($accounts[$subaccount]);
                $did_something = true;
            }
        }
    } while($did_something);

    return $accounts;
}

$accounts = array(
    'user1' => array('a','b','c','d','e'),
    'user2' => array('1','2','3','user1'),
    'user3' => array('dog','cat','orange','user2')
);

condenseOwnership($accounts); 

Also, happy t-day

Huh? Oh ... right. Nope, nothing to do with me, mate.

[scrupul0us]

/me ponders

Well I tried this and aside from having to pull the anonymous function out from array_map it doesn't seem to workie

Not sure you have my source array correct but it is:

$accounts = Array
(
    [user1] => Array
        (
            [a] => 
            [b] => 
            [c] => 
            [d] => 
            [e] => 
            [f] => 			
        )

    [user2] => Array
        (
            [1_value] => 
            [2_value] => 
            [3_value] => 
            [user1] => 			
        )

    [user3] => Array
        (            
			[dog] => 
			[cat] => 
			[orange] => 
			[user2] => 
		)
		
    [user4] => Array
        (            
			[tree] => 
			[frog] => 
			[leaf] => 
		)		
)

Which is built iteratively (word?) via:

$accounts=array();
foreach($accts as $acct)
{
	$user  = $acct->getElementsByTagName('user')->item(0)->nodeValue;
	$owner = $acct->getElementsByTagName('owner')->item(0)->nodeValue;

	$accounts[$owner][$user] = '';
}

Now, I think you have it "wrong" but essentially you are making it that via array_map and array_fill_keys

So, I tried commenting out:

$accounts = array_map(func, $accounts);

...and viola!

Your solution is exactly what I was hoping for but just couldn't mentally get to... To be honest, once I saw the do() while() with the "check bit" I had a total "duh you idiot!" moment...

I had looked briefly at array_intersect_key as well but couldn't wrap my mind around it

For the sake of learning I'll definitely have to mess around more with these "higher level" array functions...

Much appreciated for the assistance... as always =)

[dalecosp]

Huh? Oh ... right. Nope, nothing to do with me, mate.

Happy Late Christchurch Show Day, perhaps?

[Weedpacket]

Not sure you have my source array correct but it is:

Ah; well, my interpretation of your source array description had 'a', 'b', 'orange', etc. as values, and I wanted them as keys (with empty strings for the values). That's what the first line of my function did. If that's already the form it's in, then that line isn't needed.

Happy Late Christchurch Show Day, perhaps?

Just by coincidence a video has surfaced which might be the last such documenting of the city before it changed forever.

[scrupul0us]

So I've had the code in play for a few weeks now and I've found some anomalies I just can't shake.

It works 99.8%...

In some cases the number of users I get after the matrix is condensed, is less than expected, e.g. I know I start with 'x' unique users and in the end, some users are missing completely. I know that there will be loss due to duplicates being removed as part of the condensation, but, afterwards I should still have the same number of unique users.

In some cases the routine fails to merge a partially-condensed matrix into the main matrix, e.g. orphaned accounts, so I end up with one big condensed matrix and one smaller that could have been condensed above.

Now, I'm not sure if this is happening because when we assign an array of users to its found 'parent' and unset it, we are skipping the processing on the users in that array?

That said, this has been wildly successful and immensely helpful.

Any thoughts on the anomalies would be graciously appreciated.

Thanks =)

[dalecosp]

Any thoughts on the anomalies would be graciously appreciated.

Planetary Alignment?

Sun spots?

I'm not sure if I can be serious, but these thoughts have occurred:

1. How are you enforcing uniqueness of ($key) ?
2. Are you using array_intersect_key as Weedpacket suggested? If so, what about this?

array_intersect_key() returns an array containing all the entries of array1 which have keys that are present in all the arguments.

Any chance that some entries have missing keys? So many of these types of bugs seem to have to do with data anomalies....

[scrupul0us]

I blame the Mayans!

I am using this function:

function condenseOwnership($accounts) 
{ 
    do 
    { 
        $did_something = false; 
        foreach($accounts as $user=>$account) 
        { 
            foreach(array_keys(array_intersect_key($accounts, $account)) as $subaccount) 
            { 
                $accounts[$user][$subaccount] = $accounts[$subaccount]; 
                ksort($accounts[$user][$subaccount]);
                unset($accounts[$subaccount]); 
                $did_something = true; 
            }
        } 
    } while($did_something); 

    return $accounts; 
} 

My user data comes from this loop:

    foreach($accts as $acct)
    {
        $user      = $acct->getElementsByTagName('user')->item(0)->nodeValue;
        $owner     = $acct->getElementsByTagName('owner')->item(0)->nodeValue;
        $accounts[$owner][$user]='';
    } 

[dalecosp]

I blame the Mayans!

Yes!

Code: that looks pretty deep. Have you ever tried Xdebug? I finally set it up last week, and actually caught a bug with it a day or so later

[scrupul0us]

I haven't played with xdebug... I'm not sure that would help here...

I can build the data set however needed to best suite the recursion method so I more than open to ideas...

I'm continuing to toy around to see if I can figure something out =)

[scrupul0us]

So in playing around with the API a bit more I am able to return a list of users that OWN other users.

So I think what I may do here is built a skeleton array that holds the base hierarchy and then go through each and attach the users underneath.

This seems a little "uglier" to me as I'll have to make an additional API call, one to get the entire user list and then one for the parents.

Then I'll have to essentially loop (several times) to build the hierarchy and then loop the final array against the entire user set again and unset all users found in the matrix to find all users outside the matrix.

Oye

[dalecosp]

I've only recently started with Xdebug, but I found it really handy dealing with what I *think* are similar problems. As Bradgrafelman was ranting the other day in my Debugging Javascript similes thread (Post #9, if you must ask), it's kind of handing to run through things in order, step by step and hover over variables and such. You occasionally find yourself saying, "What? *That* is Null?!!" and so on, and it *can* help quite a bit at times.