note 30642 modified in function.array-diff by vrana
| From: | vrana@php.net | Date: | Tue, 17 Aug 2004 13:57:31 +0000 |
| Subject: | note 30642 modified in function.array-diff by vrana | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-80098@lists.php.net to get a copy of this message | ||
Are you looking for a function which returns an edit script (a set of insert and delete instructions
on how to change one array into another)? At least, that's what I hoped to find here, so
here's some code based on http://www.cs.arizona.edu/people/gene/PAPERS/diff.ps
:
<?php
function diff_rek(&$a1,&$a2,$D,$k,&$vbck)
{
$x=$vbck[$D][$k]; $y=$x-$k;
if ($D==0)
{
if ($x==0) return array(array(),array());
else
return array(array_slice($a1,0,$x),array_fill(0,$x,"b"));
}
$x2=$vbck[$D-1][$k+1];
$y2=$vbck[$D-1][$k-1]-($k-1);
$xdif=$x-$x2; $ydif=$y-$y2;
$l=min($x-$x2,$y-$y2);
$x=$x-$l;
$y=$y-$l;
if ($x==$x2)
{
$res=diff_rek($a1,$a2,$D-1,$k+1,$vbck);
array_push($res[0],$a2[$y-1]);
array_push($res[1],"2");
if ($l>0)
{
$res[0]=array_merge($res[0],array_slice($a2,$y,$l));
$res[1]=array_merge($res[1],array_fill(0,$l,"b"));
}
}
else
{
$res=diff_rek($a1,$a2,$D-1,$k-1,$vbck);
array_push($res[0],$a1[$x-1]);
array_push($res[1],"1");
if ($l>0)
{
$res[0]=array_merge($res[0],array_slice($a1,$x,$l));
$res[1]=array_merge($res[1],array_fill(0,$l,"b"));
}
}
return $res;
}
function arr_diff(&$a1,&$a2)
{
$max=70;
$c1=count($a1);
$c2=count($a2);
$v[1]=0;
for ($D=0; $D<=$max; $D++)
{
for ($k=-$D; $k<=$D; $k=$k+2)
{
if (($k==-$D) || ($k!=$D && $v[$k-1]<$v[$k+1]))
$x=$v[$k+1];
else
$x=$v[$k-1]+1;
$y=$x-$k;
while (($x<$c1)&&($y<$c2)&&($a1[$x]==$a2[$y]))
{
$x++;
$y++;
}
$v[$k]=$x;
if (($x>=$c1)&&($y>=$c2))
{
$vbck[$D]=$v;
return diff_rek($a1,$a2,$D,$c1-$c2,$vbck);
};
}
$vbck[$D]=$v;
};
return -1;
}
?>
This works on arrays of all elements for which the operator "==" is defined.
arr_dif($a1,$a2) returns an array of two arrays:
$result[0] = array of elements from $a1 and $a2
$result[1] = array of chars - one for each element from $result[0]:
"1" : The corresponding element is from $a1
"2" : The corresponding element is from $a2
"b" : The correspondig element is from both source arrays
The function returns -1, when the number of different elements is greater than $max
Example:
$a1=array("hello","world");
$a2=array("good","bye","world");
=> arr_diff($a1,$a2) =
array(array("hello","good","bye","world"),
array("1","2","2","b"));
--was--
Are you looking for a function which returns an edit script (a set of insert and delete instructions
on how to change one array into another)? At least, that's what I hoped to find here, so
here's some code based on http://www.cs.arizona.edu/people/gene/PAPERS/diff.ps
:
function diff_rek(&$a1,&$a2,$D,$k,&$vbck)
{
$x=$vbck[$D][$k]; $y=$x-$k;
if ($D==0)
{
if ($x==0) return array(array(),array());
else
return array(array_slice($a1,0,$x),array_fill(0,$x,"b"));
}
$x2=$vbck[$D-1][$k+1];
$y2=$vbck[$D-1][$k-1]-($k-1);
$xdif=$x-$x2; $ydif=$y-$y2;
$l=min($x-$x2,$y-$y2);
$x=$x-$l;
$y=$y-$l;
if ($x==$x2)
{
$res=diff_rek($a1,$a2,$D-1,$k+1,$vbck);
array_push($res[0],$a2[$y-1]);
array_push($res[1],"2");
if ($l>0)
{
$res[0]=array_merge($res[0],array_slice($a2,$y,$l));
$res[1]=array_merge($res[1],array_fill(0,$l,"b"));
}
}
else
{
$res=diff_rek($a1,$a2,$D-1,$k-1,$vbck);
array_push($res[0],$a1[$x-1]);
array_push($res[1],"1");
if ($l>0)
{
$res[0]=array_merge($res[0],array_slice($a1,$x,$l));
$res[1]=array_merge($res[1],array_fill(0,$l,"b"));
}
}
return $res;
}
function arr_diff(&$a1,&$a2)
{
$max=70;
$c1=count($a1);
$c2=count($a2);
$v[1]=0;
for ($D=0; $D<=$max; $D++)
{
for ($k=-$D; $k<=$D; $k=$k+2)
{
if (($k==-$D) || ($k!=$D && $v[$k-1]<$v[$k+1]))
$x=$v[$k+1];
else
$x=$v[$k-1]+1;
$y=$x-$k;
while (($x<$c1)&&($y<$c2)&&($a1[$x]==$a2[$y]))
{
$x++;
$y++;
}
$v[$k]=$x;
if (($x>=$c1)&&($y>=$c2))
{
$vbck[$D]=$v;
return diff_rek($a1,$a2,$D,$c1-$c2,$vbck);
};
}
$vbck[$D]=$v;
};
return -1;
}
This works on arrays of all elements for which the operator "==" is defined.
arr_dif($a1,$a2) returns an array of two arrays:
$result[0] = array of elements from $a1 and $a2
$result[1] = array of chars - one for each element from $result[0]:
"1" : The corresponding element is from $a1
"2" : The corresponding element is from $a2
"b" : The correspondig element is from both source arrays
The function returns -1, when the number of different elements is greater than $max
Example:
$a1=array("hello","world");
$a2=array("good","bye","world");
=> arr_diff($a1,$a2) =
array(array("hello","good","bye","world"),
array("1","2","2","b"));
http://php.net/manual/en/function.array-diff.php