排序无限深度数组 - php

Question

I have the following array: (ordered by parent_id)

array(9) {
  [1]=>
  array(3) {
    ["name"]=>
    string(6) "Tennis"
    ["parent_id"]=>
    NULL
    ["depth"]=>
    int(0)
  }
  [7]=>
  array(3) {
    ["name"]=>
    string(11) "TOP LEVEL 2"
    ["parent_id"]=>
    NULL
    ["depth"]=>
    int(0)
  }
  [8]=>
  array(3) {
    ["name"]=>
    string(11) "TOP LEVEL 3"
    ["parent_id"]=>
    NULL
    ["depth"]=>
    int(0)
  }
  [2]=>
  array(3) {
    ["name"]=>
    string(5) "Shoes"
    ["parent_id"]=>
    string(1) "1"
    ["depth"]=>
    int(1)
  }
  [3]=>
  array(3) {
    ["name"]=>
    string(5) "Women"
    ["parent_id"]=>
    string(1) "2"
    ["depth"]=>
    int(2)
  }
  [4]=>
  array(3) {
    ["name"]=>
    string(4) "Mens"
    ["parent_id"]=>
    string(1) "2"
    ["depth"]=>
    int(2)
  }
  [5]=>
  array(3) {
    ["name"]=>
    string(12) "Mens Running"
    ["parent_id"]=>
    string(1) "4"
    ["depth"]=>
    int(3)
  }
  [6]=>
  array(3) {
    ["name"]=>
    string(11) "Mens Tennis"
    ["parent_id"]=>
    string(1) "4"
    ["depth"]=>
    int(3)
  }
  [9]=>
  array(3) {
    ["name"]=>
    string(9) "2nd level"
    ["parent_id"]=>
    string(1) "8"
    ["depth"]=>
    int(1)
  }
}

I want to sort it in a way that it can be used in a drop down menu. The format for a drop down menu is:

$categories[$CATEGORY_ID] = str_repeat('  ', $value['depth']).$value['name'];

The above array up top is sorted by parent_id where top levels have a parent_id of NULL.

I need to sort it in such a way that the array is in order. For example:

[1] => 'Tennis';
[2] => ' &nbspShoes'
[3] => '     Womens'
[4] => '     Men'
[5] => '      Mens Running
[6] => '      Mens Tennis
[7] => 'TOP LEVEL 2'
[8] => 'TOP LEVEL 3'
[9] => '  2nd level'

I tried this:

function get_all_categories_and_subcategories($parent_id = NULL, $depth = 0)
{
    $categories = $this->get_all($parent_id, 10000, 0, 'parent_id');

    if (!empty($categories))
    {
        $unique_parent_ids = array();
        foreach($categories as $id => $value)
        {
            $categories[$id]['depth'] = $depth;
            $unique_parent_ids[$id] = TRUE;
        }

        foreach(array_keys($unique_parent_ids) as $id)
        {
            $categories = array_replace($categories, $this->get_all_categories_and_subcategories($id, $depth + 1));
        }

        return $categories;
    }
    else
    {           
        return $categories;
    }
}


function sort_categories($categories)
{
    usort($categories, array('Category','do_sort_categories'));
    return $categories;
}

static function do_sort_categories($a, $b)
{
    $al = strtolower($a['parent_id']);
    $bl = strtolower($b['parent_id']);
    if ($al == $bl) {
            return 0;
    }
    return ($al > $bl) ? +1 : -1;
}


function get_all($parent_id = NULL, $limit=10000, $offset=0,$col='name',$order='asc')
{
    $this->db->from('categories');
    if (!$this->config->item('speed_up_search_queries'))
    {
        $this->db->order_by($col, $order);
    }

    if ($parent_id === NULL)
    {
        $this->db->where('parent_id IS NULL', null, false);
    }
    else if($parent_id)
    {
            $this->db->where('parent_id', $parent_id);
    }

    $this->db->limit($limit);
    $this->db->offset($offset);

    $return = array();

    foreach($this->db->get()->result_array() as $result)
    {
        $return[$result['id']] = array('name' => $result['name'], 'parent_id' => $result['parent_id']);
    }

    return $return;
}

Answer 1

I don't have the possibility to test this code right now, but you could try something like this (and correct from my comments if needed).

Hope it would help a bit.

$objects = array();
// turn to array of objects to make sure our elements are passed by reference
foreach ($array as $k => $v) {
    $node = new StdClass();
    $node->id = $k;
    $node->parent_id = $v['parent_id'];
    $node->name = $v['name'];
    $node->depth = $v['depth'];
    $node->children = [];
    $objects[$k] = $node;
}
// list dependencies parent -> children
foreach ($objects as $node)
{
    $parent_id = $node->parent_id;
    if ($parent_id !== null)
    {
        $object[$parent_id][] = $node;
    }
}
// sort children of each node
foreach ($objects as $node)
{
    usort($node->children, function($a, $b){
        return $a->id < $b->id;
    });
}
// clean the object list to make kind of a tree (we keep only root elements)
$sorted = array_filter($objects, function($node){
    return $node->depth === 0;
});
// flatten recursively
function flatten_node(&$node) {
    return array_merge([$node], flatten($node->children));
}
array_walk($sorted, 'flatten_node');
// $sorted is a sorted list of objects (not array as defined at the beginning).
// You could turn it back to array and remove the 'children' key that was
// only used for sorting purposes.