[RESOLVED] Condense user matrix with unknown number of nested levels
Page 1 of 2 12 LastLast
Results 1 to 15 of 16

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

  1. #1
    I see what you did there
    Join Date
    Sep 2004
    Location
    Albany, NY
    Posts
    1,889

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

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

    In this scenario, a user can be an owner:

    Code:
    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:

    Code:
    $accounts[$owner][$user] = '';
    on the first pass I run:

    Code:
    	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

    Code:
    user3
    --dog
    --cat
    --orange
    --user2
    ----1
    ----2
    ----3
    ----user1
    ------a
    ------b
    ------c
    ------d
    ------e
    ------f
    user4
    --tree
    --frog
    --leaf
    thank you =)
    ***If your problem has been solved, PLEASE click the RESOLVED LINK under "Thread Tools"***

    Dev Server: Apache 2.4.x | PHP 5.4.x | MySQL 5.x

    PHP Manual | Learn HTML | Validate HTML

  2. #2
    Pedantic Curmudgeon Weedpacket's Avatar
    Join Date
    Aug 2002
    Location
    General Systems Vehicle "Thrilled To Be Here"
    Posts
    21,876
    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.
    THERE IS AS YET INSUFFICIENT DATA FOR A MEANINGFUL ANSWER
    FAQs! FAQs! FAQs! Most forums have them!
    Search - Debugging 101 - Collected Solutions - General Guidelines - Getting help at all

  3. #3
    I see what you did there
    Join Date
    Sep 2004
    Location
    Albany, NY
    Posts
    1,889
    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 =)
    ***If your problem has been solved, PLEASE click the RESOLVED LINK under "Thread Tools"***

    Dev Server: Apache 2.4.x | PHP 5.4.x | MySQL 5.x

    PHP Manual | Learn HTML | Validate HTML

  4. #4
    I see what you did there
    Join Date
    Sep 2004
    Location
    Albany, NY
    Posts
    1,889
    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:

    Code:
    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
    ***If your problem has been solved, PLEASE click the RESOLVED LINK under "Thread Tools"***

    Dev Server: Apache 2.4.x | PHP 5.4.x | MySQL 5.x

    PHP Manual | Learn HTML | Validate HTML

  5. #5
    Pedantic Curmudgeon Weedpacket's Avatar
    Join Date
    Aug 2002
    Location
    General Systems Vehicle "Thrilled To Be Here"
    Posts
    21,876
    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:
    Code:
    array(
    	'user1' => array(a,b,c,d,e),
    	'user2' => array(1,2,3,user1),
    	'user3' => array(dog,cat,orange,user2)
    );
    And you want
    Code:
    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.
    PHP Code:
    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); 

    Quote Originally Posted by scrupulous
    Also, happy t-day
    Huh? Oh ... right. Nope, nothing to do with me, mate.
    THERE IS AS YET INSUFFICIENT DATA FOR A MEANINGFUL ANSWER
    FAQs! FAQs! FAQs! Most forums have them!
    Search - Debugging 101 - Collected Solutions - General Guidelines - Getting help at all

  6. #6
    I see what you did there
    Join Date
    Sep 2004
    Location
    Albany, NY
    Posts
    1,889
    /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:

    Code:
    $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:

    Code:
    $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:

    Code:
    $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 =)
    ***If your problem has been solved, PLEASE click the RESOLVED LINK under "Thread Tools"***

    Dev Server: Apache 2.4.x | PHP 5.4.x | MySQL 5.x

    PHP Manual | Learn HTML | Validate HTML

  7. #7
    Settled 4 red convertible dalecosp's Avatar
    Join Date
    Jul 2002
    Location
    Accelerating Windows at 9.81 m/s....
    Posts
    7,707
    Quote Originally Posted by Weedpacket View Post
    Huh? Oh ... right. Nope, nothing to do with me, mate.
    Happy Late Christchurch Show Day, perhaps?
    /!!\ mysql_ is deprecated --- don't use it! Tell your hosting company you will switch if they don't upgrade! /!!!\ ereg() is deprecated --- don't use it!

    dalecosp "God doesn't play dice." --- Einstein "Perl is hardly a paragon of beautiful syntax." --- Weedpacket

    Getting Help at All --- Collected Solutions to Common Problems --- Debugging 101 --- Unanswered Posts --- OMBE: Office Machines, Business Equipment

  8. #8
    Pedantic Curmudgeon Weedpacket's Avatar
    Join Date
    Aug 2002
    Location
    General Systems Vehicle "Thrilled To Be Here"
    Posts
    21,876
    Quote Originally Posted by scrupul0us
    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.

    Quote Originally Posted by dalecosp
    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.
    THERE IS AS YET INSUFFICIENT DATA FOR A MEANINGFUL ANSWER
    FAQs! FAQs! FAQs! Most forums have them!
    Search - Debugging 101 - Collected Solutions - General Guidelines - Getting help at all

  9. #9
    I see what you did there
    Join Date
    Sep 2004
    Location
    Albany, NY
    Posts
    1,889
    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 =)
    ***If your problem has been solved, PLEASE click the RESOLVED LINK under "Thread Tools"***

    Dev Server: Apache 2.4.x | PHP 5.4.x | MySQL 5.x

    PHP Manual | Learn HTML | Validate HTML

  10. #10
    Settled 4 red convertible dalecosp's Avatar
    Join Date
    Jul 2002
    Location
    Accelerating Windows at 9.81 m/s....
    Posts
    7,707
    Quote Originally Posted by scrupul0us View Post
    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?

    Quote Originally Posted by PHP Manual
    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....
    /!!\ mysql_ is deprecated --- don't use it! Tell your hosting company you will switch if they don't upgrade! /!!!\ ereg() is deprecated --- don't use it!

    dalecosp "God doesn't play dice." --- Einstein "Perl is hardly a paragon of beautiful syntax." --- Weedpacket

    Getting Help at All --- Collected Solutions to Common Problems --- Debugging 101 --- Unanswered Posts --- OMBE: Office Machines, Business Equipment

  11. #11
    I see what you did there
    Join Date
    Sep 2004
    Location
    Albany, NY
    Posts
    1,889
    I blame the Mayans!

    I am using this function:

    PHP Code:
    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:

    PHP Code:
        foreach($accts as $acct)
        {
            
    $user      $acct->getElementsByTagName('user')->item(0)->nodeValue;
            
    $owner     $acct->getElementsByTagName('owner')->item(0)->nodeValue;
            
    $accounts[$owner][$user]='';
        } 
    ***If your problem has been solved, PLEASE click the RESOLVED LINK under "Thread Tools"***

    Dev Server: Apache 2.4.x | PHP 5.4.x | MySQL 5.x

    PHP Manual | Learn HTML | Validate HTML

  12. #12
    Settled 4 red convertible dalecosp's Avatar
    Join Date
    Jul 2002
    Location
    Accelerating Windows at 9.81 m/s....
    Posts
    7,707
    Quote Originally Posted by scrupul0us View Post
    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
    /!!\ mysql_ is deprecated --- don't use it! Tell your hosting company you will switch if they don't upgrade! /!!!\ ereg() is deprecated --- don't use it!

    dalecosp "God doesn't play dice." --- Einstein "Perl is hardly a paragon of beautiful syntax." --- Weedpacket

    Getting Help at All --- Collected Solutions to Common Problems --- Debugging 101 --- Unanswered Posts --- OMBE: Office Machines, Business Equipment

  13. #13
    I see what you did there
    Join Date
    Sep 2004
    Location
    Albany, NY
    Posts
    1,889
    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 =)
    ***If your problem has been solved, PLEASE click the RESOLVED LINK under "Thread Tools"***

    Dev Server: Apache 2.4.x | PHP 5.4.x | MySQL 5.x

    PHP Manual | Learn HTML | Validate HTML

  14. #14
    I see what you did there
    Join Date
    Sep 2004
    Location
    Albany, NY
    Posts
    1,889
    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
    ***If your problem has been solved, PLEASE click the RESOLVED LINK under "Thread Tools"***

    Dev Server: Apache 2.4.x | PHP 5.4.x | MySQL 5.x

    PHP Manual | Learn HTML | Validate HTML

  15. #15
    Settled 4 red convertible dalecosp's Avatar
    Join Date
    Jul 2002
    Location
    Accelerating Windows at 9.81 m/s....
    Posts
    7,707
    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.
    /!!\ mysql_ is deprecated --- don't use it! Tell your hosting company you will switch if they don't upgrade! /!!!\ ereg() is deprecated --- don't use it!

    dalecosp "God doesn't play dice." --- Einstein "Perl is hardly a paragon of beautiful syntax." --- Weedpacket

    Getting Help at All --- Collected Solutions to Common Problems --- Debugging 101 --- Unanswered Posts --- OMBE: Office Machines, Business Equipment

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •