PHP

Связанный список (одномерный массив) в иерархический массив.

Связный список

Если понадобилось связанный список преобразовывать в многомерный иерархический массив это уже говорит о том, что что-то в архитектуре не так.
Но надо так надо, например у WordPress  функция get_terms возвращает именно связанный список — одномерный массив, мне как раз потребовалось выбрать определённые группы, вместе с предками.
Можно это было сделать и через запрос, но не дело это лишними запросами нагружать базу.
Из нескольких функций получилась почти универсальная для формирования иерархического массива:

/**
 * Пробежимся по всем элементам и составим цепочку родителей - линейный массив айдишников
 * @param unknown_type $item
 * @param unknown_type $items
 * @param unknown_type $levels
 * @return array
 */
function parentis($item, $items, &$levels, $keyID, $keyParent) {
   $item=(array)$item;
   $levels[]=$item[$keyID];
   if ($item[$keyParent]!=0) {
      return parentis($items[$item[$keyParent]], $items, $levels, $keyID, $keyParent);
   }
   $levels[]=0;
   return $levels;
}

/**
 * Уберём более короткие цепочки, которые являются частью более длинных
 * @param unknown_type $items
 */
function sanityzeParentis(&$items) {
   foreach ($items as $ki => $i) {
      foreach ($items as  $kj => $j) {
         if ($ki==$kj) continue;
         $li=count($i);
         $lj=count($j);
         $l=min($li, $lj);
         $match=false;
         for ($m=0; $m<$l; $m++) {
            if ($i[$m]!=$j[$m]) {
               $match=true;
               break;
            }
         }
         if (!$match) {
            if ($l==$li) unset($items[$ki]); else unset($items[$kj]);
         }
      }
   }
}

/**
 * Создадим вложенные массивы по иерархии на основе цепочек
 * @param unknown_type $arr
 * @param unknown_type $hierarchycal
 * @param unknown_type $level
 */
function setChilds(&$arr, $hierarchycal, $items, $level, $keySubChilds, $keyChild) {
   if (count($hierarchycal) < $level) return;
   $h=$hierarchycal[$level-1];
   if (!isset($arr[$h])) $arr[$h]=array($keyChild=>$items[$h], $keySubChilds=>array() );
   setChilds($arr[$h][$keySubChilds], $hierarchycal, $items, $level+1, $keySubChilds, $keyChild);
}

/**
  * Формируем связанный список (одномерный массив) в многомерный массив с иерархиией
  * @param unknown_type $items связанный список
  * @param unknown_type $keyID ключ айдишника элемента связанного списка
  * @param unknown_type $keyParent ключ айдишника предка элемента связанного списка
  * @param unknown_type $keySubChilds ключ, в который будут заноситсья вложенные элементы 
  * @param unknown_type $keyChild  ключ для самого вложенного элемента
  * @param unknown_type $levels с какого уровня начинать, обычно с 1
  * @return array 
  */ 	
function formatHierarchy($items, $keyID, $keyParent, $keySubChilds, $keyChild, $levels ) {
   //-- занесём элементы в массив по ключам - айдишникам
   $level1= array();
   foreach ($items as $item) {
      $item=(array)$item;
      $level1[$item[$keyID]]=$item;
   }

   $hierarchycals=array();
   foreach ($level1 as $item) {
      $hierarchy=array(); 			
      $hierarchy=array_reverse(parentis($item, $level1, $hierarchy, $keyID, $keyParent));
      $hierarchycals[]=$hierarchy;
   }		

   sanityzeParentis($hierarchycals);

   $result=array(); 		
   foreach ($hierarchycals as $hierarchy) {
      setChilds($result, $hierarchy, $level1, $levels, $keySubChilds, $keyChild );
   }	
   return $result;
}
Основная функция - formatHierarchy

Например, имеем связанный список $list у каждого элемента есть поле id, title, parent
Элемент с parent==0 считается корневым!
Пример:
[spoiler]
array (size=10)
  0 => 
    array (size=3)
      'id' => int 1
      'parent' => int 0
      'title' => string 'Элемент 1' (length=16)
  1 => 
    array (size=3)
      'id' => int 2
      'parent' => int 0
      'title' => string 'Элемент 2' (length=16)
  2 => 
    array (size=3)
      'id' => int 3
      'parent' => int 0
      'title' => string 'Элемент 3' (length=16)
  3 => 
    array (size=3)
      'id' => int 4
      'parent' => int 2
      'title' => string 'Вложенный Элемент 4' (length=35)
  4 => 
    array (size=3)
      'id' => int 5
      'parent' => int 2
      'title' => string 'Вложенный Элемент 5' (length=35)
  5 => 
    array (size=3)
      'id' => int 6
      'parent' => int 3
      'title' => string 'Вложенный Элемент 6' (length=35)
  6 => 
    array (size=3)
      'id' => int 7
      'parent' => int 6
      'title' => string 'Дважды вложенный Элемент 7' (length=48)
  7 => 
    array (size=3)
      'id' => int 8
      'parent' => int 3
      'title' => string 'Дважды вложенный Элемент 8' (length=48)
  8 => 
    array (size=3)
      'id' => int 9
      'parent' => int 3
      'title' => string 'Дважды вложенный Элемент 9' (length=48)
  9 => 
    array (size=3)
      'id' => int 10
      'parent' => int 9
      'title' => string 'Трижды вложенный Элемент 10' (length=49)
[/spoiler]

вызываем тогда так:  formatHierarchy($list, ‘id’, ‘parent’,  ‘item’, ‘subitems’, 1);
тогда результирующий иерархический массив получится  такой:

[spoiler]
array (size=1)
  0 => 
    array (size=2)
      'item' => null
      'subitems' => 
        array (size=3)
          1 => 
            array (size=2)
              'item' => 
                array (size=3)
                  'id' => int 1
                  'parent' => int 0
                  'title' => string 'Элемент 1' (length=16)
              'subitems' => 
                array (size=0)
                  empty
          2 => 
            array (size=2)
              'item' => 
                array (size=3)
                  'id' => int 2
                  'parent' => int 0
                  'title' => string 'Элемент 2' (length=16)
              'subitems' => 
                array (size=2)
                  4 => 
                    array (size=2)
                      'item' => 
                        array (size=3)
                          'id' => int 4
                          'parent' => int 2
                          'title' => string 'Вложенный Элемент 4' (length=35)
                      'subitems' => 
                        array (size=0)
                          empty
                  5 => 
                    array (size=2)
                      'item' => 
                        array (size=3)
                          'id' => int 5
                          'parent' => int 2
                          'title' => string 'Вложенный Элемент 5' (length=35)
                      'subitems' => 
                        array (size=0)
                          empty
          3 => 
            array (size=2)
              'item' => 
                array (size=3)
                  'id' => int 3
                  'parent' => int 0
                  'title' => string 'Элемент 3' (length=16)
              'subitems' => 
                array (size=3)
                  6 => 
                    array (size=2)
                      'item' => 
                        array (size=3)
                          'id' => int 6
                          'parent' => int 3
                          'title' => string 'Вложенный Элемент 6' (length=35)
                      'subitems' => 
                        array (size=1)
                          7 => 
                            array (size=2)
                              'item' => 
                                array (size=3)
                                  'id' => int 7
                                  'parent' => int 6
                                  'title' => string 'Дважды вложенный Элемент 7' (length=48)
                              'subitems' => 
                                array (size=0)
                                  empty
                  8 => 
                    array (size=2)
                      'item' => 
                        array (size=3)
                          'id' => int 8
                          'parent' => int 3
                          'title' => string 'Дважды вложенный Элемент 8' (length=48)
                      'subitems' => 
                        array (size=0)
                          empty
                  9 => 
                    array (size=2)
                      'item' => 
                        array (size=3)
                          'id' => int 9
                          'parent' => int 3
                          'title' => string 'Дважды вложенный Элемент 9' (length=48)
                      'subitems' => 
                        array (size=1)
                          10 => 
                            array (size=2)
                              'item' => 
                                array (size=3)
                                  'id' => int 10
                                  'parent' => int 9
                                  'title' => string 'Трижды вложенный Элемент 10' (length=49)
                              'subitems' => 
                                array (size=0)
                                  empty
[/spoiler]

Related posts

Варианты формата даты mysql

REGEXP в MySQL

Получить новое за день, неделю, месяц из MySQL