Tree.php 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194
  1. <?php
  2. namespace app\common;
  3. class Tree
  4. {
  5. /**
  6. * 获取完整的树结构,包含祖先节点
  7. */
  8. const INCLUDE_ANCESTORS = 1;
  9. /**
  10. * 获取部分树,不包含祖先节点
  11. */
  12. const EXCLUDE_ANCESTORS = 0;
  13. /**
  14. * 数据
  15. * @var array
  16. */
  17. protected $data = [];
  18. /**
  19. * 哈希树
  20. * @var array
  21. */
  22. protected $hashTree = [];
  23. /**
  24. * 父级字段名
  25. * @var string
  26. */
  27. protected $pidName = 'pid';
  28. /**
  29. * @param $data
  30. * @param string $pid_name
  31. */
  32. public function __construct($data, string $pid_name = 'pid')
  33. {
  34. $this->pidName = $pid_name;
  35. if (is_object($data) && method_exists($data, 'toArray')) {
  36. $this->data = $data->toArray();
  37. } else {
  38. $this->data = (array)$data;
  39. $this->data = array_map(function ($item) {
  40. if (is_object($item) && method_exists($item, 'toArray')) {
  41. return $item->toArray();
  42. }
  43. return $item;
  44. }, $this->data);
  45. }
  46. $this->hashTree = $this->getHashTree();
  47. }
  48. /**
  49. * 获取子孙节点
  50. * @param array $include
  51. * @param bool $with_self
  52. * @return array
  53. */
  54. public function getDescendant(array $include, bool $with_self = false): array
  55. {
  56. $items = [];
  57. foreach ($include as $id) {
  58. if (!isset($this->hashTree[$id])) {
  59. return [];
  60. }
  61. if ($with_self) {
  62. $item = $this->hashTree[$id];
  63. unset($item['children']);
  64. $items[$item['id']] = $item;
  65. }
  66. foreach ($this->hashTree[$id]['children'] ?? [] as $item) {
  67. unset($item['children']);
  68. $items[$item['id']] = $item;
  69. foreach ($this->getDescendant([$item['id']]) as $it) {
  70. $items[$it['id']] = $it;
  71. }
  72. }
  73. }
  74. return array_values($items);
  75. }
  76. /**
  77. * 获取哈希树
  78. * @param array $data
  79. * @return array
  80. */
  81. protected function getHashTree(array $data = []): array
  82. {
  83. $data = $data ?: $this->data;
  84. $hash_tree = [];
  85. foreach ($data as $item) {
  86. $hash_tree[$item['id']] = $item;
  87. }
  88. foreach ($hash_tree as $index => $item) {
  89. if ($item[$this->pidName] && isset($hash_tree[$item[$this->pidName]])) {
  90. $hash_tree[$item[$this->pidName]]['children'][$hash_tree[$index]['id']] = &$hash_tree[$index];
  91. }
  92. }
  93. return $hash_tree;
  94. }
  95. /**
  96. * 获取树
  97. * @param array $include
  98. * @param int $type
  99. * @return array|null
  100. */
  101. public function getTree(array $include = [], int $type = 1): ?array
  102. {
  103. // $type === static::EXCLUDE_ANCESTORS
  104. if ($type === static::EXCLUDE_ANCESTORS) {
  105. $items = [];
  106. $include = array_unique($include);
  107. foreach ($include as $id) {
  108. if (!isset($this->hashTree[$id])) {
  109. return [];
  110. }
  111. $items[] = $this->hashTree[$id];
  112. }
  113. return static::arrayValues($items);
  114. }
  115. // $type === static::INCLUDE_ANCESTORS
  116. $hash_tree = $this->hashTree;
  117. $items = [];
  118. if ($include) {
  119. $map = [];
  120. foreach ($include as $id) {
  121. if (!isset($hash_tree[$id])) {
  122. continue;
  123. }
  124. $item = $hash_tree[$id];
  125. $max_depth = 100;
  126. while ($max_depth-- > 0 && $item[$this->pidName] && isset($hash_tree[$item[$this->pidName]])) {
  127. $last_item = $item;
  128. $pid = $item[$this->pidName];
  129. $item = $hash_tree[$pid];
  130. $item_id = $item['id'];
  131. if (empty($map[$item_id])) {
  132. $map[$item_id] = 1;
  133. $hash_tree[$pid]['children'] = [];
  134. }
  135. $hash_tree[$pid]['children'][$last_item['id']] = $last_item;
  136. $item = $hash_tree[$pid];
  137. }
  138. $items[$item['id']] = $item;
  139. }
  140. } else {
  141. $items = $hash_tree;
  142. }
  143. $formatted_items = [];
  144. foreach ($items as $item) {
  145. if (!$item[$this->pidName] || !isset($hash_tree[$item[$this->pidName]])) {
  146. $formatted_items[] = $item;
  147. }
  148. }
  149. return static::arrayValues($formatted_items);
  150. }
  151. /**
  152. * 递归重建数组下标
  153. * @param $array
  154. * @return array
  155. */
  156. public static function arrayValues($array): array
  157. {
  158. if (!$array) {
  159. return [];
  160. }
  161. if (!isset($array['children'])) {
  162. $current = current($array);
  163. if (!is_array($current)) {
  164. return $array;
  165. }
  166. $tree = array_values($array);
  167. foreach ($tree as $index => $item) {
  168. $tree[$index] = static::arrayValues($item);
  169. }
  170. return $tree;
  171. }
  172. $array['children'] = array_values($array['children']);
  173. foreach ($array['children'] as $index => $child) {
  174. $array['children'][$index] = static::arrayValues($child);
  175. }
  176. return $array;
  177. }
  178. }