PHP:通过递归迭代构建邻接表 [英] PHP: Building an Adjacency List through Recursive Iteration
本文介绍了PHP:通过递归迭代构建邻接表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我正在尝试构建一个扁平化的数组，该数组可以保留来自CodeIgniter项目中一个视图的非常棘手的数组中的元数据.元数据就是标识符，深度和父节点之类的东西.
数据来自查询构建器JavaScript库，该库允许用户生成将在业务逻辑中使用的规则.我需要保留这些数据，并且用来表示这些规则的树状性质的模型是一个邻接表.
这是我所拥有的，它在大多数情况下都可以使用，但是很难看，它是由泡泡糖和胶带制成的，而且大多数"情况并非全部"情况.阅读了SPL文档之后，我怀疑RecursiveIteratorIterator可能更适合该问题.
很抱歉，这篇文章篇幅长，但是我很确定我的方法很烂.有什么建议吗?
以下是输入内容(例如，我不想去的地方)，示例图片也显示了它的作用:
stdClass Object
(
[condition] => OR
[rules] => Array
(
[0] => stdClass Object
(
[id] => Any
[field] => Any
[type] => string
[input] => select
[operator] => not equal
[value] => Any
)
[1] => stdClass Object
(
[condition] => AND
[rules] => Array
(
[0] => stdClass Object
(
[id] => Place
[field] => Place
[type] => string
[input] => select
[operator] => equal
[value] => France
)
[1] => stdClass Object
(
[id] => Month
[field] => Month
[type] => string
[input] => select
[operator] => equal
[value] => January
)
)
)
[2] => stdClass Object
(
[condition] => AND
[rules] => Array
(
[0] => stdClass Object
(
[id] => Place
[field] => Place
[type] => string
[input] => select
[operator] => equal
[value] => Rio
)
[1] => stdClass Object
(
[id] => Month
[field] => Month
[type] => string
[input] => select
[operator] => equal
[value] => August
)
)
)
[3] => stdClass Object
(
[condition] => AND
[rules] => Array
(
[0] => stdClass Object
(
[id] => Place
[field] => Place
[type] => string
[input] => select
[operator] => equal
[value] => Liberia
)
[1] => stdClass Object
(
[id] => Month
[field] => Month
[type] => string
[input] => select
[operator] => equal
[value] => July
)
[2] => stdClass Object
(
[condition] => OR
[rules] => Array
(
[0] => stdClass Object
(
[id] => Year
[field] => Year
[type] => string
[input] => select
[operator] => equal
[value] => 2014
)
[1] => stdClass Object
(
[id] => Year
[field] => Year
[type] => string
[input] => select
[operator] => equal
[value] => 2015
)
)
)
)
)
)
)
这是持久性所需的输出. (有关元数据的重要位，请参见每个条目最右边的值).
Array
(
stdClass Object ( [id] => Any [field] => Any [type] => string [input] => select [operator] => not equal [value] => Any [condition] => OR [subgroup] => 0 [parent_subgroup] => )
stdClass Object ( [id] => Place [field] => Place [type] => string [input] => select [operator] => equal [value] => France) [condition] => AND [subgroup] => 1 [parent_subgroup] => 0 )
stdClass Object ( [id] => Month [field] => Month [type] => string [input] => select [operator] => equal [value] => January [condition] => AND [subgroup] => 1 [parent_subgroup] => 0 )
stdClass Object ( [id] => Place [field] => Place [type] => string [input] => select [operator] => equal [value] => Rio [condition] => AND [subgroup] => 2 [parent_subgroup] => 0 )
stdClass Object ( [id] => Month [field] => Month [type] => string [input] => select [operator] => equal [value] => August[condition] => AND [subgroup] => 2 [parent_subgroup] => 0 )
stdClass Object ( [id] => Place [field] => Place [type] => string [input] => select [operator] => equal [value] => Liberia [condition] => AND [subgroup] => 3 [parent_subgroup] => 0 )
stdClass Object ( [id] => Month [field] => Month [type] => string [input] => select [operator] => equal [value] => July[condition] => AND [subgroup] => 3 [parent_subgroup] => 0 )
stdClass Object ( [id] => Year [field] => Year [type] => string [input] => select [operator] => equal [value] => 2014 [condition] => OR [subgroup] => 4 [parent_subgroup] => 3 )
stdClass Object ( [id] => Year [field] => Year [type] => string [input] => select [operator] => equal [value] => 2015 [condition] => OR [subgroup] => 4 [parent_subgroup] => 3 )
)
注意:正确解析.如果我更改了第2组和第3组的顺序，则会出现问题，因为第3组的子组具有规则(Year = 2014或Year = 2015)的嵌套级别不同，并且严重干扰了我的递归.
这是我的代码:
function deserialize_criteria_group($criteria, $subgroup = null) {
$array = array();
if ($subgroup == null) {
$first_run = true;
$subgroup = 0;
$condition = $criteria->condition;
$criteria = $criteria->rules;
}
foreach ($criteria as $rule) {
if ($rule->rules) {
$subgroup++;
$children = $this->deserialize_criteria_group($rule->rules, $subgroup);
foreach($children as $child) {
if ($child->condition == null) {
$child->condition = $rule->condition;
}
if ($child->parent_subgroup == null) {
$child->parent_subgroup = $first_run ? 0 : $subgroup - 1;
}
array_push($array, $child);
}
} else {
$rule->condition = $condition;
$rule->subgroup = $subgroup;
$rule->parent_subgroup = null;
array_push($array, $rule);
}
}
if ($first_run) {
//Ensure a root node exists, if not stub one out.
$criteria_group = json_decode(json_encode($array), true);
$root_encountered = $criteria_group[0]['subgroup'] > 0 ? false : true;
if (!$root_encountered) {
$root = array( 'subgroup' => 0,
'parent_subgroup' => null,
'condition' => $condition);
array_unshift($criteria_group, $root);
array_unshift($array, $root);
}
//Ensure the ALM is not broken.
$subgroup = 0;
foreach($criteria_group as $c) {
if($c['subgroup'] > $subgroup + 1) {
$msg = "Bad Order. Halting execution.";
print $msg;
log_message('error', $msg);
log_message('debug', 'expected: ' . $subgroup . ' actual: ' . $c['subgroup']);
log_message('debug', print_r($criteria_group, true));
die;
}
$subgroup = $c['subgroup'];
}
}
return $array;
}
解决方案
感谢Rocket Hazmat的协助.
好像我在那儿错过了一些代码，很抱歉.
这种方法还会引起一些其他问题.我在下面显示更正.
解决方案:
<?php
class CriteriaIterator implements RecursiveIterator{
private $data, $counter, $condition, $subgroup, $parent_subgroup;
public function __construct($criteriaGroup, $condition, $parent_subgroup=null){
$this->condition = $condition;
$this->subgroup = $GLOBALS['highest_subgroup'];
$this->parent_subgroup = $parent_subgroup;
$this->data = is_array($criteriaGroup) ? $criteriaGroup : array($criteriaGroup);
}
public function current(){
$row = $this->data[$this->counter];
if ($row->id) {
return (object) array(
'id' => $row->id,
'field' => $row->id,
'operator' => $row->operator,
'value' => $row->value,
'condition'=> $this->condition,
'subgroup' => $GLOBALS['highest_subgroup'],
'parent_subgroup' => $this->parent_subgroup
);
}
}
public function key(){
return $this->counter;
}
public function next(){
$this->counter++;
}
public function rewind(){
$this->counter = 0;
}
public function valid(){
return $this->counter < count($this->data);
}
public function hasChildren(){
$row = $this->data[$this->counter];
return isset($row->rules);
}
public function getChildren(){
$GLOBALS['highest_subgroup']++;
$row = $this->data[$this->counter];
return new self($row->rules, $row->condition, $this->subgroup);
}
}
随后调用并清理如下:(最后有点懒了，改装到运行PHP 5.3的CodeIgniter中)
$records = new RecursiveIteratorIterator(
new CriteriaIterator($a['criteria_group'], $a['criteria_group']->condition),
RecursiveIteratorIterator::SELF_FIRST);
$criteria = array();
$parent_encountered = false;
// cleanup
foreach($records as $row) {
if($row != null) {
$row->parent_subgroup = $row->parent_subgroup == - 1 ? null : $row->parent_subgroup;
if($row->parent_subgroup === null) {
$parent_encountered = true;
}
array_push($criteria, $row);
}
}
if(!$parent_encountered) {
$row = array(
'subgroup' => 0,
'parent_subgroup' => null,
'condition' => $a['criteria_group']->condition
);
array_unshift($criteria, json_decode(json_encode($row)));
}
与此有关的问题出现在小组成员上.我的检索方法使用广度优先搜索来创建json对象以传递到脚本中.不幸的是，有了嵌套级别，重新保存时事情就一发不可收拾.
这是可能导致混淆的设置示例之一.值之前的天数显示预期的子组.
也许可以修复递归迭代器类，但是Rocket Hazmat建议使该类非常简单.我在清理过程中实施了一个修复程序:
$records = new RecursiveIteratorIterator(
new CriteriaIterator($a['criteria_group'], $a['criteria_group']->condition),
RecursiveIteratorIterator::SELF_FIRST);
$criteria = array();
$root_encountered = false;
// cleanup
foreach($records as $row) {
if($row != null) {
if($row->parent_subgroup == - 1) {
$row->parent_subgroup = null;
$row->subgroup = 0;
}
if($row->parent_subgroup === null) {
$root_encountered = true;
}
array_push($criteria, $row);
}
}
if(!$root_encountered) {
$row = (object) array(
'subgroup' => 0,
'parent_subgroup' => null,
'condition' => $a['criteria_group']->condition
);
array_unshift($criteria, $row);
}
//strategy: keep a record keyed by subgroups of where they are rooted.
//if an entry exists for a previous subgroup but the parent subgroup conflicts
//use the subgroup of the LAST subgroup rooted there.
//else update array
$adjacency = array(0 => null); //parent
foreach($criteria as $row) {
if (isset($adjacency[$row->subgroup]) && $adjacency[$row->subgroup] != $row->parent_subgroup) {
$preserved = array_reverse($adjacency, true); //need LAST subgroup rooted there
foreach($preserved as $key=>$val) {
if ($val == $row->parent_subgroup) {
$row->subgroup = $key;
break;
}
}
} else {
$adjacency[$row->subgroup] = $row->parent_subgroup;
}
}
I'm trying to build a flattened array that preserves metadata from a pretty tricky array coming from a view in my CodeIgniter project. That metadata is things like an identifier, depth, and parent node.
The data is from a query builder JavaScript library that allows a user to generate rules that will be used in business logic. I need to persist this data, and the model I've gone with to represent the tree-like nature of these rules is an adjacency list.
Here's what I have, and it does work for most cases, but it's ugly, it's made of bubble gum and duct tape, and 'most' cases are not 'all' cases. After reading the SPL docs, I suspect a RecursiveIteratorIterator may be more suited to the problem.
Sorry for the long winded post, but I'm pretty sure my approach sucks. Any advice?
Here's the input (e.g., places I would rather not be), sample image showing it in action too:
stdClass Object
(
[condition] => OR
[rules] => Array
(
[0] => stdClass Object
(
[id] => Any
[field] => Any
[type] => string
[input] => select
[operator] => not equal
[value] => Any
)
[1] => stdClass Object
(
[condition] => AND
[rules] => Array
(
[0] => stdClass Object
(
[id] => Place
[field] => Place
[type] => string
[input] => select
[operator] => equal
[value] => France
)
[1] => stdClass Object
(
[id] => Month
[field] => Month
[type] => string
[input] => select
[operator] => equal
[value] => January
)
)
)
[2] => stdClass Object
(
[condition] => AND
[rules] => Array
(
[0] => stdClass Object
(
[id] => Place
[field] => Place
[type] => string
[input] => select
[operator] => equal
[value] => Rio
)
[1] => stdClass Object
(
[id] => Month
[field] => Month
[type] => string
[input] => select
[operator] => equal
[value] => August
)
)
)
[3] => stdClass Object
(
[condition] => AND
[rules] => Array
(
[0] => stdClass Object
(
[id] => Place
[field] => Place
[type] => string
[input] => select
[operator] => equal
[value] => Liberia
)
[1] => stdClass Object
(
[id] => Month
[field] => Month
[type] => string
[input] => select
[operator] => equal
[value] => July
)
[2] => stdClass Object
(
[condition] => OR
[rules] => Array
(
[0] => stdClass Object
(
[id] => Year
[field] => Year
[type] => string
[input] => select
[operator] => equal
[value] => 2014
)
[1] => stdClass Object
(
[id] => Year
[field] => Year
[type] => string
[input] => select
[operator] => equal
[value] => 2015
)
)
)
)
)
)
)
Here is the desired output for persistence. (See the values at the far right of each entry for the important bits of metadata).
Array
(
stdClass Object ( [id] => Any [field] => Any [type] => string [input] => select [operator] => not equal [value] => Any [condition] => OR [subgroup] => 0 [parent_subgroup] => )
stdClass Object ( [id] => Place [field] => Place [type] => string [input] => select [operator] => equal [value] => France) [condition] => AND [subgroup] => 1 [parent_subgroup] => 0 )
stdClass Object ( [id] => Month [field] => Month [type] => string [input] => select [operator] => equal [value] => January [condition] => AND [subgroup] => 1 [parent_subgroup] => 0 )
stdClass Object ( [id] => Place [field] => Place [type] => string [input] => select [operator] => equal [value] => Rio [condition] => AND [subgroup] => 2 [parent_subgroup] => 0 )
stdClass Object ( [id] => Month [field] => Month [type] => string [input] => select [operator] => equal [value] => August[condition] => AND [subgroup] => 2 [parent_subgroup] => 0 )
stdClass Object ( [id] => Place [field] => Place [type] => string [input] => select [operator] => equal [value] => Liberia [condition] => AND [subgroup] => 3 [parent_subgroup] => 0 )
stdClass Object ( [id] => Month [field] => Month [type] => string [input] => select [operator] => equal [value] => July[condition] => AND [subgroup] => 3 [parent_subgroup] => 0 )
stdClass Object ( [id] => Year [field] => Year [type] => string [input] => select [operator] => equal [value] => 2014 [condition] => OR [subgroup] => 4 [parent_subgroup] => 3 )
stdClass Object ( [id] => Year [field] => Year [type] => string [input] => select [operator] => equal [value] => 2015 [condition] => OR [subgroup] => 4 [parent_subgroup] => 3 )
)
Note: parses this correctly. Problems would arise if I had changed the order of subgroups 2 and 3, as the subgroup of group 3, the one that has rules (Year = 2014 OR Year = 2015) has a different nesting level and severely messes up my recursion.
Here is my code:
function deserialize_criteria_group($criteria, $subgroup = null) {
$array = array();
if ($subgroup == null) {
$first_run = true;
$subgroup = 0;
$condition = $criteria->condition;
$criteria = $criteria->rules;
}
foreach ($criteria as $rule) {
if ($rule->rules) {
$subgroup++;
$children = $this->deserialize_criteria_group($rule->rules, $subgroup);
foreach($children as $child) {
if ($child->condition == null) {
$child->condition = $rule->condition;
}
if ($child->parent_subgroup == null) {
$child->parent_subgroup = $first_run ? 0 : $subgroup - 1;
}
array_push($array, $child);
}
} else {
$rule->condition = $condition;
$rule->subgroup = $subgroup;
$rule->parent_subgroup = null;
array_push($array, $rule);
}
}
if ($first_run) {
//Ensure a root node exists, if not stub one out.
$criteria_group = json_decode(json_encode($array), true);
$root_encountered = $criteria_group[0]['subgroup'] > 0 ? false : true;
if (!$root_encountered) {
$root = array( 'subgroup' => 0,
'parent_subgroup' => null,
'condition' => $condition);
array_unshift($criteria_group, $root);
array_unshift($array, $root);
}
//Ensure the ALM is not broken.
$subgroup = 0;
foreach($criteria_group as $c) {
if($c['subgroup'] > $subgroup + 1) {
$msg = "Bad Order. Halting execution.";
print $msg;
log_message('error', $msg);
log_message('debug', 'expected: ' . $subgroup . ' actual: ' . $c['subgroup']);
log_message('debug', print_r($criteria_group, true));
die;
}
$subgroup = $c['subgroup'];
}
}
return $array;
}
解决方案
Thanks to Rocket Hazmat for the assist.
EDIT: Looks like I missed some code there, apologies.
EDIT2: There were some additional issues that arose with this approach. I show the corrections below.
Solution:
<?php
class CriteriaIterator implements RecursiveIterator{
private $data, $counter, $condition, $subgroup, $parent_subgroup;
public function __construct($criteriaGroup, $condition, $parent_subgroup=null){
$this->condition = $condition;
$this->subgroup = $GLOBALS['highest_subgroup'];
$this->parent_subgroup = $parent_subgroup;
$this->data = is_array($criteriaGroup) ? $criteriaGroup : array($criteriaGroup);
}
public function current(){
$row = $this->data[$this->counter];
if ($row->id) {
return (object) array(
'id' => $row->id,
'field' => $row->id,
'operator' => $row->operator,
'value' => $row->value,
'condition'=> $this->condition,
'subgroup' => $GLOBALS['highest_subgroup'],
'parent_subgroup' => $this->parent_subgroup
);
}
}
public function key(){
return $this->counter;
}
public function next(){
$this->counter++;
}
public function rewind(){
$this->counter = 0;
}
public function valid(){
return $this->counter < count($this->data);
}
public function hasChildren(){
$row = $this->data[$this->counter];
return isset($row->rules);
}
public function getChildren(){
$GLOBALS['highest_subgroup']++;
$row = $this->data[$this->counter];
return new self($row->rules, $row->condition, $this->subgroup);
}
}
Invoked and cleaned up afterwards like so: (got a little lazy around the end, retrofitting into CodeIgniter running PHP 5.3)
$records = new RecursiveIteratorIterator(
new CriteriaIterator($a['criteria_group'], $a['criteria_group']->condition),
RecursiveIteratorIterator::SELF_FIRST);
$criteria = array();
$parent_encountered = false;
// cleanup
foreach($records as $row) {
if($row != null) {
$row->parent_subgroup = $row->parent_subgroup == - 1 ? null : $row->parent_subgroup;
if($row->parent_subgroup === null) {
$parent_encountered = true;
}
array_push($criteria, $row);
}
}
if(!$parent_encountered) {
$row = array(
'subgroup' => 0,
'parent_subgroup' => null,
'condition' => $a['criteria_group']->condition
);
array_unshift($criteria, json_decode(json_encode($row)));
}
The problems arose with this on the subgroup member. My retrieval method uses a breadth first search to create the json object to pass into the script. Unfortunately, with the nesting levels things got out of hand when resaving.
Here is one example of settings that would result in a mix up. The days before value shows the expected subgroup.
It may have been possible to fix in the recursive iterator class, but Rocket Hazmat suggested leaving that class very simple. I implemented a fix during the cleanup:
$records = new RecursiveIteratorIterator(
new CriteriaIterator($a['criteria_group'], $a['criteria_group']->condition),
RecursiveIteratorIterator::SELF_FIRST);
$criteria = array();
$root_encountered = false;
// cleanup
foreach($records as $row) {
if($row != null) {
if($row->parent_subgroup == - 1) {
$row->parent_subgroup = null;
$row->subgroup = 0;
}
if($row->parent_subgroup === null) {
$root_encountered = true;
}
array_push($criteria, $row);
}
}
if(!$root_encountered) {
$row = (object) array(
'subgroup' => 0,
'parent_subgroup' => null,
'condition' => $a['criteria_group']->condition
);
array_unshift($criteria, $row);
}
//strategy: keep a record keyed by subgroups of where they are rooted.
//if an entry exists for a previous subgroup but the parent subgroup conflicts
//use the subgroup of the LAST subgroup rooted there.
//else update array
$adjacency = array(0 => null); //parent
foreach($criteria as $row) {
if (isset($adjacency[$row->subgroup]) && $adjacency[$row->subgroup] != $row->parent_subgroup) {
$preserved = array_reverse($adjacency, true); //need LAST subgroup rooted there
foreach($preserved as $key=>$val) {
if ($val == $row->parent_subgroup) {
$row->subgroup = $key;
break;
}
}
} else {
$adjacency[$row->subgroup] = $row->parent_subgroup;
}
}
这篇关于PHP:通过递归迭代构建邻接表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
