ordering categories with php arrays

Question

I have an array of categories:

categories = computers, entertainment, products, graphics cards

The array is sometimes returned in the wrong order BUT each category has a parent which exists in the SAME array.

categories = 
products[parent=0],
entertainment[parent=products],
computers[parent=entertainment],
graphics cards[parent=computers]

How would I use php to sort this array if it was returned in any order?

Unordered Example:

categories = 
computers[parent=entertainment], 
entertainment[parent=products], 
products[parent=0], 
graphics cards[parent=computers]    

Must produce:

categories = products, entertainment, computers, graphics cards

Answer 1

Are you talking about a simple sort like this:

<?php


$categories = array('computers[parent=entertainment]', 
'entertainment[parent=products]', 
'products[parent=0]', 
'graphics cards[parent=computers]');
sort($categories);
echo '<pre>';
print_r($categories);
echo '</pre>';

?>

Answer 2

Looking at your example, I'm assuming you want a topological sort, as Sam Dufel says.

$categories = array(
    "computers" => array("parent" => "entertainment"),
    "entertainment" => array("parent" => "products"),
    "products" => array("parent" => null),
    "graphics cards" => array("parent" => "computers")
);

// Set distances
foreach ($categories as $cat => &$e) {
    $e["dist"] = nodeDistance($cat, $categories);
}

// Before
echo implode(", ", array_keys($categories)) . "\n";
// Sort
uasort($categories, "nodeDistanceSorter");
// After
echo implode(", ", array_keys($categories)) . "\n";

function nodeDistance($node, $categories) {
    // Check cache
    if (array_key_exists("dist", $categories[$node]))
        return $categories[$node]["dist"];
    // Check root
    if (is_null($categories[$node]["parent"]))
        return 0;
    // Traverse
    return nodeDistance($categories[$node]["parent"], $categories) + 1;
}

function nodeDistanceSorter($a, $b) {
    $aDist = $a["dist"];
    $bDist = $b["dist"];
    if ($aDist == $bDist)
        return 0;
    return $aDist - $bDist;
}

Answer 3

categories = 
products[parent=0],
entertainment[parent=products],
computers[parent=entertainment],
graphics cards[parent=computers]

I take it that the array is like this:

$categories = array
(
    'products'=>array('parent'=>0),//poor little orphan
    'entertainment'=>array('parent'=>'products'),
    'computers'=>array('parent'=>'entertainment'),
    'graphics cards'=>array('parent'=>'computers'),
)

here is a solution that I mixed up right now:

Solution 1

$categories = array
(
 'computers'=>array('parent'=>'entertainment'), 
 'entertainment'=>array('parent'=>'products'), 
 'products'=>array('parent'=>0), 
 'graphics cards'=>array('parent'=>'computers')
);  

function addparentfirst(&$original,$array,$name,$data){
    if(isset($data['parent']) && isset($original[$data['parent']])){
        $array = addparentfirst($original,$array,$data['parent'],$original[$data['parent']]);
    }
    $array[$name] = $data;
    unset($original[$name]);
    return $array;
}
foreach($categories as $key=>$value){//goes over each category only once, contrary to what it looks like
    $sortedcategories = addparentfirst($categories,$sortedcategories,$key,$value);
}
$categories = $sortedcategories;//NOW IT'S SORTED

print_r($categories);

Solution 2

//It's interesting that it doesn't loop infinitely
//I like this solution the most

function addparentfirst(&$array,$key){
    if(isset($array[$key]['parent']) && !empty($array[$key]['parent'])){
        addparentfirst($array,$array[$key]['parent']);
    }
    $data = $array[$key];
    unset($array[$key]);
    $array[$key] = $data;
    return $array;
}


foreach($categories as $key=>$value){
    addparentfirst($categories,$key);
}
print_r($categories);

Solution 3

function sortArrayByArray($array,$orderArray) {
    $ordered = array();
    foreach($orderArray as $key) {
        if(isset($array[$key])) {
                $ordered[$key] = $array[$key];
                unset($array[$key]);
        }
    }
    return $ordered + $array;
}



//Usage:
$categories = sortArrayByArray($categories,array('products','entertainment','computers','graphics cards'));
print_r($categories);

as seen here

Solution 4

function get_childless_category_name($array){
    foreach($array as $key=>$value){
        if(isset($value['parent']) && !empty($value['parent'])){
            unset($array[$value['parent']]);
        }
    }
    $names = array_keys($array);//names of all the child free categories
    return array_pop($names);//get the last one (there should only be one)
}
function parent_comes_first(&$array,$key){
    if(isset($array[$key]['parent']) && !empty($array[$key]['parent'])){
        $array = parent_comes_first($array,$array[$key]['parent']);
    }
    $data = $array[$key];
    unset($array[$key]);
    $array[$key] = $data;
    return $array;
}


//Usage:
$childless = get_childless_category_name($categories);
parent_comes_first($categories,$childless);

print_r($categories);