<?php

Class Tree_Builder {
	
	function make_tree($data, $sumkey = FALSE) {
		// Принимает массив вида [id] => [данные].
		// Возвращает те же данные, 
		// где элементы расположены 
		// согласно древовидной структуре
		// (КЛЮЧИ СОХРАНЯЮТСЯ):
		//
		// [1] => A ( id = 1, level = 1)
		//   [2] => B (id = 2, parent_id = 1, level = 2)
		//   [3] => C (id = 3, parent_id = 1, level = 2)
		//     [5] => C.1 (id = 5, parent_id = 3, level = 3)
		//     [27] => C.2 (id = 6, parent_id = 3, level = 3)
		//     [34] => C.3 (id = 7, parent_id = 3, level = 3)
		//   [9] => D (id = 8, parent_id = 1, level = 2)
		// [15] => E (id = 15, level = 1)
		//    [16] => F (id = 16, parent_id = 15, level = 2)
		// ...
		// В данные добавляется ключ level,
		// в который записывается 
		// уровень иерархии текущего элементы
		// (уровни начинаются с первого, к которому
		// принадлежат элементы с parent_id = 0)
		$children = $this->list_children($data);
		$tree_ids = $this->tree_ids($children);
		$tree_data = $this->tree_data($data, $tree_ids);
		if ($sumkey)
			$tree_data = $this->aggregate($tree_data, $sumkey); 
		return $tree_data;
	}
	
	function aggregate($tree_data, $sumkey) {
		end($tree_data);
		$sum = 0; $parent_id = 0;
		while( ! is_null($key = key($tree_data))) {
			
			$current = current($tree_data);
			
			if (!isset($current[$sumkey]))
				$current[$sumkey] = 0;
			
			$parent_id = $current['parent_id'];
			
			if (isset($tree_data[$parent_id])) {
				if (!isset($tree_data[$parent_id][$sumkey]))
					$tree_data[$parent_id][$sumkey] = 0;
					
				$tree_data[$parent_id][$sumkey] += $current[$sumkey];
			}
			
			prev($tree_data);
		}
		
		return $tree_data;
	}
	
	function list_children($data) {
		// Поиск прямых потомков
		// для каждой из записей
		// (у которой потомки есть)
		// плюс корневые элементы (parent_id = 0)
		// возвращается в виде массива:
		// [0] => Array(1,15)
		// [1] => Array(2,3,9)
		// [2] => Array(5,27,34)
		// [15] => Array(16, ...)
		// ...
		
		$children = array();
		foreach ($data as $row) {
			$children[$row['parent_id']][] = $row['id'];
		}
		return $children;
	}
	
	function tree_ids($children, $parent_id = 0, $level = 1) {
		// возвращает список элементов
		// в иерархической последовательности
		// в виде массива [id] => [level]
		// (т.е. id - В КЛЮЧАХ!)
		$tree_ids = array();
		$F = __FUNCTION__;
		
		if (
			isset($children[$parent_id])
			AND
			$siblings = $children[$parent_id]
			) {
			
			foreach ($siblings as $id) {
				$tree_ids[$id] = $level;
				
				$tree_ids =  // именно оператор +, а не array_merge(), 
					$tree_ids // т.к. она уничтожает числовые ключи
					+
					$this->$F($children, $id, $level + 1) ;
			}
		}
		
		return $tree_ids;
	}
	
	function tree_data($data, $tree_ids) {
		$tree_data = array();
		foreach ($tree_ids as $id => $level) {
			if (isset($data[$id])) {
				$row = compact('level') + $data[$id];
				$tree_data[$id] = $row;
			}
		}
		return $tree_data;
	}
}

?>