Как рекурсивно сортировать ассоциативный массив - PullRequest
Новая
       23

Как рекурсивно сортировать ассоциативный массив

1 голос
/ 22 мая 2019

Я бы хотел отсортировать следующий ассоциативный массив: 

$tree = [
  "id" => 245974,
  "children" => [
    [
      "id" => 111
    ],
    [
      "id" => 245982,
      "children" => [
        [
          "id" => 246093,
          "children" => [
            [
              "id" => 225892
            ],
            [
              "id" => 225893
            ],
            [
              "id" => 225902
            ]
          ]
        ]
      ]
    ]
  ]
];

Желаемый порядок сортировки после "значения поиска" id => 225902: 

[
  "id" => 245974,
  "children" => [
    [
      "id" => 245982, // <-- this is moved up
      "children" => [
        [
          "id" => 246093,
          "children" => [
            [
              "id" => 225902 // <-- this is moved up
            ],
            [
              "id" => 225892
            ],
            [
              "id" => 225893
            ]
          ]
        ]
      ]
    ],
    [
      "id" => 111
    ]
  ]
];

Что я пробовал: 

<code><?php

$category_id = 225902;

function custom_sort(&$a, &$b) {
  global $category_id;

  if ($a['id'] === $category_id) {
    return -1;
  }

  if ($b['id'] === $category_id) {
    return 1;
  }

  if (array_key_exists('children', $a)) {
    if (usort($a['children'], "custom_sort")) {
      return -1;
    }
  }

  if (array_key_exists('children', $b)) {
    if (usort($b['children'], "custom_sort")) {
      return 1;
    }
  }

  return 0;
}

function reorder_tree($tree) {
  usort($tree['children'], "custom_sort");
  return $tree;
}

echo "<pre>";
var_dump(reorder_tree($tree));
echo "
";

Однако, это возвращает: 

[
  "id" => 245974,
  "children" => [
    [
      "id" => 245982, // <- this is moved up
      "children" => [
        [
          "id" => 246093,
          "children" => [
            [
              "id" => 225892
            ],
            [
              "id" => 225893
            ],
            [
              "id" => 225902 // <- this is *not* moved up
            ]
          ]
        ]
      ]
    ],
    [
      "id" => 111
    ],
  ]
];

Как бы я мог также отсортировать childrenмассивы?

1 Ответ

2 голосов
/ 22 мая 2019

Отличная попытка и очень на правильном пути. Проблема с рекурсией в компараторе заключается в том, что usort не будет вызывать функцию компаратора, когда длина массива равна 1, поэтому независимо от того, исследуете ли вы все дерево или нет, вы хотите получить значение usort. Это оставит ветку дерева id => 245982.

Решение состоит в том, чтобы избежать повторного использования функции сравнения usort напрямую. Вместо этого используйте обычную рекурсивную функцию, которая при необходимости вызывает usort, а именно текущий или дочерний массив содержит целевой идентификатор. Я использую отдельный массив для отслеживания того, какие элементы должны быть перемещены вперед, но вы можете выйти из цикла и соединить / отодвинуть один элемент вперед, если вы предпочитаете.

Мы также можем сделать $category_id параметром для функции.

Вот один из подходов: 

function reorder_tree_r(&$children, $target) {
    $order = [];
    $should_sort = false;

    foreach ($children as $i => &$child) {
        $order[$i] = false;

        if (array_key_exists("children", $child) &&
            reorder_tree_r($child["children"], $target) || 
            $child["id"] === $target) {
            $order[$i] = true;
            $should_sort = true;
        }
    }

    if ($should_sort) {
        $priority = [];
        $non_priority = [];

        for ($i = 0; $i < count($children); $i++) {
            if ($order[$i]) {
                $priority[]= $children[$i];
            }
            else {
                $non_priority[]= $children[$i];
            }
        }

        $children = array_merge($priority, $non_priority);
    }

    return $should_sort;
}

function reorder_tree($tree, $target) {
    if (!$tree || !array_key_exists("children", $tree)) {
        return $tree;
    }

    reorder_tree_r($tree["children"], $target);
    return $tree;
}


var_export(reorder_tree($tree, 225902));

Выход: 

array (
  'id' => 245974,
  'children' => 
  array (
    0 => 
    array (
      'id' => 245982,
      'children' => 
      array (
        0 => 
        array (
          'id' => 246093,
          'children' => 
          array (
            0 => 
            array (
              'id' => 225902,
            ),
            1 => 
            array (
              'id' => 225892,
            ),
            2 => 
            array (
              'id' => 225893,
            ),
          ),
        ),
      ),
    ),
    1 => 
    array (
      'id' => 111,
    ),
  ),
...