У меня есть следующий array котором каждый элемент может (или может не зависеть) от другого:
$test = array( 'c' => array( 'depends' => 'b' ), 'a' => array(), 'b' => array( 'depends' => 'a' ), 'd' => array( 'depends' => 'a' ), );
Я хочу переместить (или сделать другой array ) с зависимостями, перемещенными вверху . Сначала a , затем b и d (оба зависят от a ) и, наконец, c который зависит от b . Порядок b и d имеет значения:
$rearranged = array( 'a' => array(), 'b' => array( 'depends' => 'a' ), 'd' => array( 'depends' => 'a' ), 'c' => array( 'depends' => 'b' ), );
Я почти уверен, что это довольно распространенная ситуация, и прежде чем изобретать колесо и тратить время, я хотел бы знать, есть ли какая-либо структура данных, которая может сделать эту работу для меня.
EDIT : забыл сказать, что круговые ссылки должны быть обнаружены ( b зависит от того, что зависит от b не должно быть разрешено).
Это называется топологической сортировкой . Если вы считаете свою структуру графиком, где «a зависит от b» равно направленному ребру от вершины b до вершины a, вы должны просто сделать топологическую сортировку, чтобы получить ответ.
Реализация топологической сортировки может быть выполнена следующим образом:
пусть graph [n] [n] – график, соответствующий вашему массиву (график [i] [j] = 1 означает, что j зависит от i).
array_multisort поможет вам здесь.
<?php $test = array( 'c' => array( 'depends' => 'b' ), 'a' => array(), 'b' => array( 'depends' => 'a' ), 'd' => array( 'depends' => 'a' ) ); function sortArray($array= array()) { $depend = array(); foreach ($array as $key => $value) { if (isset($value['depends'])) { $depend[$key] = $value['depends']; } else { $depend[$key] = null; } } return $depend; } function findCircularReference($array) { foreach($array as $key=>$value) { if(isset($array[$value]) && ($array[$value] == $key)) { return true; } } return false; } $depend = sortArray($test); $checkReference = findCircularReference($depend); if( ! $checkReference) { array_multisort($depend, SORT_ASC, $test); } else { trigger_error("Circular reference", E_USER_ERROR); } print_r($test); ?>
Протестировано и работает:
В основном он проходит через каждый узел и проверяет глубину этого узла с вершины дерева и добавляет значение в новый массив $ar . Затем он сортирует $test на основе уровня глубины каждого узла, хранящегося в $ar используя array_multisort() .
<?php $test = array( 'c' => array( 'depends' => 'b' ), 'a' => array(), 'b' => array( 'depends' => 'a' ), 'd' => array( 'depends' => 'a' ), ); function getNodeLevel($ar,$n,$ref=array()) { if(!isset($ar[$n]['depends'])){return 0;} if(in_array($n,$ref)){return -1;} $ref[]=$n; $r=getNodeLevel($ar,$ar[$n]['depends'],$ref); return ($r==-1?-1:$r+1); } $ar=array(); foreach($test as $i=>$tmp) { $ar[]=getNodeLevel($test,$i); } if(!in_array(-1,$ar)) { array_multisort($ar,SORT_ASC,$test); print_r($test); }else{ trigger_error("Circular reference detected.", E_USER_ERROR); }от<?php $test = array( 'c' => array( 'depends' => 'b' ), 'a' => array(), 'b' => array( 'depends' => 'a' ), 'd' => array( 'depends' => 'a' ), ); function getNodeLevel($ar,$n,$ref=array()) { if(!isset($ar[$n]['depends'])){return 0;} if(in_array($n,$ref)){return -1;} $ref[]=$n; $r=getNodeLevel($ar,$ar[$n]['depends'],$ref); return ($r==-1?-1:$r+1); } $ar=array(); foreach($test as $i=>$tmp) { $ar[]=getNodeLevel($test,$i); } if(!in_array(-1,$ar)) { array_multisort($ar,SORT_ASC,$test); print_r($test); }else{ trigger_error("Circular reference detected.", E_USER_ERROR); }
Я хотел использовать самую основную сортировку зависимостей и иметь это как рабочее решение. Протестировано множество вариаций и работает до сих пор.
private function getSorted($type) { uasort($this->assets[$type], array($this, 'sortDependancies')); return $this->assets[$type]; } /** * Sorting utility function via uasort from getSorted * * @returns sort order */ private function sortDependancies($a, $b) { if ( is_array($b['dependant']) && in_array($a['alias'], $b['dependant'])) return -1; if ( $a['alias'] == $b['dependant'] ) return -1; return 1; }
Я создал это для использования в массиве объектов сбора объектов js и css.
protected $assets = array( 'stylesheets' => array( 'main' => array( 'alias' => 'main', 'path' => 'somepath.less', 'dependant' => 'bootstrap' ), 'bootstrap' => ( 'alias' => 'bootstrap', 'path' => 'bootstrap.css', 'dependant' => NULL ) ), 'javascripts' => array() );
поэтому я бы назвал $ type, т.е. либо «stylesheets», либо «javascripts» в getSorted ()
Я также сделал так, чтобы он мог работать с несколькими зависимостями, используя массив для «зависимого» элемента вместо строки.
Если этот контекст должен быть упрощенным, дайте мне знать, я все же создал его внутри объекта …
Ура!
Я был вдохновлен на странице Википедии «Топологическая сортировка» . Поэтому я сделал несколько алгоритмов.
/** * Class Top * * @package Lib\Sort */ class Top { /** * Unsorted nodes * * @var array */ protected $_nodes = array(); /** * Nodes structure * * @var array */ protected $_structure = array(); /** * Stored nodes * * @var array|null */ protected $_sortedNodes; /** * Stored nodes * * @var array */ protected $_level = 0; /** * Status of mode "single non-edge node" * * @var bool * @see setModeSingleNonEdgeNode() */ protected $_singleNonEdgeNode = true; /** * Get status of "Single non-edge node" mode * * @return boolean * @see setModeSingleNonEdgeNode() */ public function isModeSingleNonEdgeNode() { return $this->_singleNonEdgeNode; } /** * Set status of "Single non-edge node" mode * * This status means that sorting will move only first non-edged node to top. * Rest non-edge nodes will be added according to sorting in _nodes property * In case it will FALSE all nodes will be moved to top. * * @param boolean $flag * @return $this */ public function enableModeSingleNonEdgeNode($flag) { $this->_singleNonEdgeNode = (bool)$flag; return $this; } /** * Add node * * @param string $name * @param array $dependsOn * @throws Exception * @return $this */ public function addNode($name, array $dependsOn = array()) { if (null !== $this->_sortedNodes) { throw new Exception('Nodes already sorted.'); } $this->_nodes[$name] = $name; $this->_structure[$name] = $dependsOn; return $this; } /** * Sort * * @return array */ public function getSortedNodes() { if (null === $this->_sortedNodes) { $this->_sortedNodes = array(); //insert non-edged nodes $this->_performNonEdgedNodes(); //insert edged nodes $this->_performEdgedNodes(); } return $this->_sortedNodes; } /** * Move node into sorted list * * @param string $name * @throws Exception * @return $this */ protected function _moveNodeToSortedList($name) { $node = $this->_takeNode($name); if ($node) { $this->_sortedNodes[] = $node; } else { throw new Exception("The node '$name' has already been taken."); } return $this; } /** * Take node from the list * * @param string $name * @return string|null */ protected function _takeNode($name) { if (!isset($this->_nodes[$name])) { return null; } $node = $this->_nodes[$name]; unset($this->_nodes[$name]); return $node; } /** * Perform node sorting * * @param string $name * @return $this * @throws Exception */ protected function _performNode($name) { $node = $this->_takeNode($name); if (null === $node) { return $this; } foreach ($this->_structure[$node] as $depNode) { $this->_checkCycledEdges($node, $depNode); $this->_performNode($depNode); } $this->_sortedNodes[] = $node; return $this; } /** * Check cycled edges * * @param string $node * @param string $edgeNode * @return bool * @throws Exception */ protected function _checkCycledEdges($node, $edgeNode) { if (in_array($node, $this->_structure[$edgeNode])) { throw new Exception("Cyclic dependencies between $edgeNode and $node."); } return true; } /** * Perform edged nodes * * @return $this */ protected function _performEdgedNodes() { while (!empty($this->_nodes)) { $name = current($this->_nodes); $this->_performNode($name); } return $this; } /** * Perform non-edged nodes * * @return $this */ protected function _performNonEdgedNodes() { foreach ($this->_structure as $name => $edges) { if (!$edges) { $this->_moveNodeToSortedList($name); if ($this->isModeSingleNonEdgeNode()) { //to add only first node and to add rest non-edge nodes according to sorting in _nodes property break; } } } return $this; } }с/** * Class Top * * @package Lib\Sort */ class Top { /** * Unsorted nodes * * @var array */ protected $_nodes = array(); /** * Nodes structure * * @var array */ protected $_structure = array(); /** * Stored nodes * * @var array|null */ protected $_sortedNodes; /** * Stored nodes * * @var array */ protected $_level = 0; /** * Status of mode "single non-edge node" * * @var bool * @see setModeSingleNonEdgeNode() */ protected $_singleNonEdgeNode = true; /** * Get status of "Single non-edge node" mode * * @return boolean * @see setModeSingleNonEdgeNode() */ public function isModeSingleNonEdgeNode() { return $this->_singleNonEdgeNode; } /** * Set status of "Single non-edge node" mode * * This status means that sorting will move only first non-edged node to top. * Rest non-edge nodes will be added according to sorting in _nodes property * In case it will FALSE all nodes will be moved to top. * * @param boolean $flag * @return $this */ public function enableModeSingleNonEdgeNode($flag) { $this->_singleNonEdgeNode = (bool)$flag; return $this; } /** * Add node * * @param string $name * @param array $dependsOn * @throws Exception * @return $this */ public function addNode($name, array $dependsOn = array()) { if (null !== $this->_sortedNodes) { throw new Exception('Nodes already sorted.'); } $this->_nodes[$name] = $name; $this->_structure[$name] = $dependsOn; return $this; } /** * Sort * * @return array */ public function getSortedNodes() { if (null === $this->_sortedNodes) { $this->_sortedNodes = array(); //insert non-edged nodes $this->_performNonEdgedNodes(); //insert edged nodes $this->_performEdgedNodes(); } return $this->_sortedNodes; } /** * Move node into sorted list * * @param string $name * @throws Exception * @return $this */ protected function _moveNodeToSortedList($name) { $node = $this->_takeNode($name); if ($node) { $this->_sortedNodes[] = $node; } else { throw new Exception("The node '$name' has already been taken."); } return $this; } /** * Take node from the list * * @param string $name * @return string|null */ protected function _takeNode($name) { if (!isset($this->_nodes[$name])) { return null; } $node = $this->_nodes[$name]; unset($this->_nodes[$name]); return $node; } /** * Perform node sorting * * @param string $name * @return $this * @throws Exception */ protected function _performNode($name) { $node = $this->_takeNode($name); if (null === $node) { return $this; } foreach ($this->_structure[$node] as $depNode) { $this->_checkCycledEdges($node, $depNode); $this->_performNode($depNode); } $this->_sortedNodes[] = $node; return $this; } /** * Check cycled edges * * @param string $node * @param string $edgeNode * @return bool * @throws Exception */ protected function _checkCycledEdges($node, $edgeNode) { if (in_array($node, $this->_structure[$edgeNode])) { throw new Exception("Cyclic dependencies between $edgeNode and $node."); } return true; } /** * Perform edged nodes * * @return $this */ protected function _performEdgedNodes() { while (!empty($this->_nodes)) { $name = current($this->_nodes); $this->_performNode($name); } return $this; } /** * Perform non-edged nodes * * @return $this */ protected function _performNonEdgedNodes() { foreach ($this->_structure as $name => $edges) { if (!$edges) { $this->_moveNodeToSortedList($name); if ($this->isModeSingleNonEdgeNode()) { //to add only first node and to add rest non-edge nodes according to sorting in _nodes property break; } } } return $this; } }
И сделал тесты для этого класса:
<?php namespace Lib\Sort; /** * Class TopTest * * @package Lib\Sort */ class TopTest extends \PHPUnit_Framework_TestCase { public function testBasicSorting() { $test = new Top(); $test->addNode('A'); $test->addNode('B', array('A', 'F')); $test->addNode('C', array('B', 'D')); $test->addNode('D', array('F')); $test->addNode('E', array('A', 'F')); $test->addNode('F', array('A')); $test->addNode('G'); $this->assertTrue($test->isModeSingleNonEdgeNode()); $actual = $test->getSortedNodes(); $expected = array('A', 'F', 'B', 'D', 'C', 'E', 'G'); $this->assertEquals($expected, $actual); } /** * Test sorting of last node with many edges * * @throws Exception */ public function testLastNodeSorting() { $test = new Top(); $test->addNode('A', array()); $test->addNode('B', array('A', 'F')); $test->addNode('C', array('B', 'D')); $test->addNode('D', array('F')); $test->addNode('E', array('A')); $test->addNode('F', array('A', 'E')); $actual = $test->getSortedNodes(); $expected = array('A', 'E', 'F', 'B', 'D', 'C'); $this->assertEquals($actual, $expected); } /** * Test sorting disabled mode "Single non-edge node" * * @throws Exception */ public function testDisabledSingleNonEdgesSorting() { $test = new Top(); $test->addNode('A'); $test->addNode('B', array('A', 'F')); $test->addNode('C', array('B', 'D')); $test->addNode('D', array('F')); $test->addNode('E', array('A')); $test->addNode('F', array('A', 'E')); $test->addNode('G'); $test->enableModeSingleNonEdgeNode(false); $actual = $test->getSortedNodes(); $expected = array('A', 'G', 'E', 'F', 'B', 'D', 'C'); $this->assertEquals($actual, $expected); } /** * Test exception for cyclic nodes * * @expectedException \Lib\Sort\Exception * @expectedExceptionMessage Cyclic dependencies between E and F. */ public function testCyclicSortingFailure() { $test = new Top(); $test->addNode('A', array()); $test->addNode('B', array('A', 'F')); $test->addNode('C', array('B', 'D')); $test->addNode('D', array('F')); $test->addNode('E', array('A', 'F')); $test->addNode('F', array('A', 'E')); $test->getSortedNodes(); //expected an exception } /** * Test exception for cyclic nodes * * @expectedException \Lib\Sort\Exception * @expectedExceptionMessage Nodes already sorted. */ public function testAddNodeAfterSortingFailure() { $test = new Top(); $test->addNode('A', array()); $test->addNode('B', array('A', 'F')); $test->addNode('C', array('B', 'D')); $test->addNode('D', array('F')); $test->addNode('E', array('A')); $test->addNode('F', array('A', 'E')); $test->getSortedNodes(); $test->addNode('H', array('E')); //expected an exception } }
Может быть, это будет полезно для кого-то.