Tweet
Ich bastel gerade an einem kleinen Skript was diff in PHP implementiert (Prinzip der längsten zusammenhängenden Teilfolge, Implementationen in C#. Python, Java und C++). Die Basis funktioniert einwandfrei (und produziert die gleichen Ergebnisse wie GNU-diff auf der Konsole).
Bei (gleichen) Zeilen vor einer neuen Zeile gibt es allerdings ein Problem:
Statt wie erwartet (1) ohne Änderung wird die Zeile an der entsprechenden Stelle hinzugefügt (2) und vor der letzten neuen Zeile (2.1) wieder hinzugefügt. Da der Code vom Prinzip her den Implementationen entspricht kann ich das nicht nachvollziehen. Im Anhang die komplette Klasse zum Testen.
PHP-Code:
// Diese Funktion erstellt aus der Tabelle von _longestCommonSubsequence
// einenen diff.
private static function _createDiff ( $table, $x, $y, $i, $j ) {
// Die Ergebnisse werden in ein Array geschrieben welches (je nach Typ)
// dann eine Zeile ergibt, none heißt keine Änderungen,
// add heißt hinzufügen, remove Zeile löschen
if ( $i > 0 and $j > 0 and $x [ $i - 1 ] == $y [ $j - 1 ] ) {
self :: _createDiff ( $table, $x, $y, $i - 1, $j - 1 );
self :: $_result [ ] = array ( 'text' => $x [ $i - 1 ],
'type' => self :: typeNone, 'line' => array ( $i, $j ) );
} else {
if ( $j > 0 and ( $i == 0 or
( !empty ( $table [ $i ] [ $j - 1 ] ) ? $table [ $i ] [ $j - 1 ] : 0 ) >=
( !empty ( $table [ $i - 1 ] [ $j ] ) ? $table [ $i - 1 ] [ $j ] : 0 ) ) ) {
self :: _createDiff ( $table, $x, $y, $i, $j - 1 );
self :: $_result [ ] = array ( 'text' => $y [ $j - 1 ],
'type' => self :: typeAdd, 'line' => $j );
} elseif ( $i > 0 and ( $j == 0 or
( !empty ( $table [ $i ] [ $j - 1 ] ) ? $table [ $i ] [ $j - 1 ] : 0 ) <
( !empty ( $table [ $i - 1 ] [ $j ] ) ? $table [ $i - 1 ] [ $j ] : 0 ) ) ) {
self :: _createDiff ( $table, $x, $y, $i - 1, $j );
self :: $_result [ ] = array ( 'text' => $x [ $i - 1 ],
'type' => self :: typeRemove, 'line' => $i );
}
}
}
// Diese Funktion erstellt eine Tabelle in der die längsten zusammenhängenden Teilfolgen
// makiert werden.
private static function _longestCommonSubsequence( $x, $y ) {
// _getLength gibt die Länge der Variable zurück
//(Unterscheidung zwischen String und Array)
$xLength = self :: _getLength ( $x );
$yLenght = self :: _getLength ( $y );
$table = array ( );
for ( $i = 0; $i < $xLength; $i ++ ) {
for ( $j = 0; $j < $yLenght; $j ++ ) {
if ( $i != 0 and $j != 0 and
trim ( $x [ ( $i - 1 > 0 ) ? $i - 1 : 0 ] ) ==
trim ( $y [ ( $j - 1 > 0 ) ? $j - 1 : 0 ] ) ) {
$table [ $i ] [ $j ] = $table [ ( $i - 1 > 0 ) ? $i - 1 : 0 ]
[ ( $j - 1 > 0 ) ? $j - 1 : 0 ] + 1;
} else {
$table [ $i ] [ $j ] = max ( ( $j == 0 ) ? 0 : $table [ $i ] [ $j - 1 ],
( $i == 0 ) ? 0 : $table [ $i - 1 ] [ $j ] );
}
}
}
return $table;
}
Code:
[i](1)[/i] they have different names. [COLOR=skyblue]+ They both may be called deep and profound.[/COLOR]
Code:
[i](2)[/i] [COLOR=red]+ they have different names.[/COLOR] [COLOR=skyblue]+ They both may be called deep and profound.[/COLOR] ... [COLOR=red]- they have different names.[/COLOR] [i](2.1)[/i] [COLOR=skyblue]+ The door of all subtleties![/COLOR]
Moderator
Kommentar