Класс зависимости PHP

Что-то вроде:

 class deps{ protected $items = array(); public function add($item, array $deps = array()){ $this->items[$item] = $deps; } protected function checkDependencies($item) { if (!isset($this->items[$item])) { return false; } foreach ($this->items[$item] as $dep) { if (!$this->checkDependencies($dep)) { return false; } } return true; } public function getResolved() { $result = array(); foreach ($this->items as $item => $deps) { if ($this->checkDependencies($item)) { $result[] = $item; } } return $result; } public function getUnresolved() { $result = array(); foreach ($this->items as $item => $deps) { if (!$this->checkDependencies($item)) { $result[] = $item; } } return $result; } } $deps = new deps; $deps->add('item2', array('item1')); // <- depends on item1 $deps->add('item1', array()); // <- no dependency $deps->add('item3', array('item1', 'item5')); // <- depends on item1 and item5 $deps->add('A', array('item3')); // <- on item3 $deps->add('C', array('item2', 'item1')); // ...... print_r($deps->getResolved()); /* Array ( [0] => item2 [1] => item1 [2] => C ) */ print_r($deps->getUnresolved()); /* Array ( [0] => item3 [1] => A ) */ 

http://codepad.org/fSwJjyz5

Бит беспорядочный, но возвращает правильный порядок загрузки (1, 2, C) и нерешен.

 <?php class Dependencies { private $_items; private $_dependencies; public function add($item, $dependencies = array()) { $this->_items[$item] = (count($dependencies) > 0) ? $dependencies : null; foreach($dependencies as $dependency) { $this->_dependencies[$dependency][] = $item; } } public function get_load_order() { $load_order = array(); $seen = array(); foreach($this->_items as $item => $dependencies) { $tmp = $this->get_dependents($item, $seen); if($tmp[2] === false) { $load_order = array_merge($load_order, $tmp[0]); $seen = $tmp[1]; } } return $load_order; } public function get_failed_items() { $failed = array(); $seen = array(); foreach($this->_items as $item => $dependencies) { $tmp = $this->get_dependents($item, $seen); if($tmp[2] !== false) { $failed[] = $item; continue; } $seen = $tmp[1]; } return $failed; } private function get_dependents($item, $seen = array()) { if(array_key_exists($item, $seen)) { return array(array(), $seen, false); } if($this->item_exists($item)) { $order = array(); $failed = array(); $seen[$item] = true; if($this->has_dependents($item)) { foreach($this->_items[$item] as $dependency) { $tmp = $this->get_dependents($dependency, $seen); $order = array_merge($tmp[0], $order); $seen = $tmp[1]; if($tmp[2] !== false) { $failed = array_merge($tmp[2], $failed); } } } $order[] = $item; $failed = (count($failed) > 0) ? $failed : false; return array($order, $seen, $failed); } return array(array(), array(), array($item)); } private function item_exists($item) { if(array_key_exists($item, $this->_items)) { return true; } return false; } private function has_dependents($item) { if($this->item_exists($item) AND is_array($this->_items[$item])) { return true; } return false; } } 

Называется:

 <?php $deps = new Dependencies(); $deps->add('item2', array('item1')); // <- depends on item1 $deps->add('item1'); // <- no dependency $deps->add('item3', array('item1', 'item5')); // <- depends on item1 and item5 $deps->add('A', array('item3')); // <- on item3 $deps->add('C', array('item2', 'item1')); // ...... $load_order = $deps->get_load_order(); $failed_items = $deps->get_failed_items(); echo '<pre>'; echo 'Loaded: '; print_r($load_order); echo 'Failed: '; print_r($failed_items); echo '</pre>'; 

Производит:

 Loaded: Array ( [0] => item1 [1] => item2 [2] => C ) Failed: Array ( [0] => item3 [1] => A ) 

С предоставленными вами данными это сделало трюк для заказа зависимостей.

 function returnOrderedDependencies() { $temporary = $this->items; $dependencies = array(); $isChanged = true; while ($isChanged == true) { $isChanged = false; // Step 1. Search for items without dependencies foreach ($temporary as $item => $deps) { if (empty($deps)) { array_push($dependencies, $item); unset($temporary[$item]); } } // Step 2. Remove resolved items from dependencies foreach ($temporary as $item => $deps) { foreach ($deps as $key => $value) { if (in_array($value, $dependencies)) { $isChanged = true; unset($temporary[$item][$key]); } } } } return $dependencies; } с function returnOrderedDependencies() { $temporary = $this->items; $dependencies = array(); $isChanged = true; while ($isChanged == true) { $isChanged = false; // Step 1. Search for items without dependencies foreach ($temporary as $item => $deps) { if (empty($deps)) { array_push($dependencies, $item); unset($temporary[$item]); } } // Step 2. Remove resolved items from dependencies foreach ($temporary as $item => $deps) { foreach ($deps as $key => $value) { if (in_array($value, $dependencies)) { $isChanged = true; unset($temporary[$item][$key]); } } } } return $dependencies; } с function returnOrderedDependencies() { $temporary = $this->items; $dependencies = array(); $isChanged = true; while ($isChanged == true) { $isChanged = false; // Step 1. Search for items without dependencies foreach ($temporary as $item => $deps) { if (empty($deps)) { array_push($dependencies, $item); unset($temporary[$item]); } } // Step 2. Remove resolved items from dependencies foreach ($temporary as $item => $deps) { foreach ($deps as $key => $value) { if (in_array($value, $dependencies)) { $isChanged = true; unset($temporary[$item][$key]); } } } } return $dependencies; } 

Элементы, оставшиеся в $ временном, являются нерешенными зависимостями, и для ваших данных они были возвращены как ожидалось, но я предполагаю, что это совпадение.

Я не уверен, как упорядочить неразрешенные зависимости, возможно, от того, сколько зависимостей, где не разрешены эти элементы.