Created
January 9, 2021 00:42
-
-
Save jasonrush/e5ed593b0c6f5c60bbb670e9b17aefce to your computer and use it in GitHub Desktop.
PowerShell Diff implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<# | |
Diff implementation based off of https://gist.github.com/adamnew123456/37923cf53f51d6b9af32a539cdfa7cc4 | |
Written by Jason Rush (https://github.com/jasonrush) | |
Returns an arraylist of hashtables. Each hashtable has two properties. | |
The "Action" property will have a value of "Keep", "Insert", or "Remove". | |
The "Line" property will have the value originally passed via $a_lines or $b_lines. | |
While I haven't tested it, technically $a_lines and $b_lines should just be arrays | |
and the values should be able to be anything, not just strings from files as you would | |
typically use diff for. | |
Example: | |
Get-Diff (Get-Content .\file_a.txt) (Get-Content .\file_b.txt) | |
Example: | |
Get-Diff $oldStrings $newStrings | Foreach-Object { | |
if( "Keep" -eq $_.Action ){ | |
" $($_.Line)" | |
}elseif( "Insert" -eq $_.Action ){ | |
"+ $($_.Line)" | |
}elseif( "Remove" -eq $_.Action ){ | |
"- $($_.Line)" | |
} | |
} | |
#> | |
function Get-Diff( $a_lines, $b_lines ){ | |
function DiffKeep( $line ){ | |
@{ | |
Action = "Keep" | |
Line = $line | |
} | |
} | |
function DiffInsert( $line ){ | |
@{ | |
Action = "Insert" | |
Line = $line | |
} | |
} | |
function DiffRemove( $line ){ | |
@{ | |
Action = "Remove" | |
Line = $line | |
} | |
} | |
function Frontier( $x, $history ){ | |
@{ | |
x = $x | |
history = $history # arraylist | |
} | |
} | |
function DiffOne( [int32] $i ){ | |
$i - 1 | |
} | |
$a_max = ($a_lines | Measure-Object).Count | |
$b_max = ($b_lines | Measure-Object).Count | |
$combined_max = [math]::Max(0, $a_max + $b_max) | |
$frontier = @{} | |
for( $i = -$combined_max; $i -le $combined_max; $i++ ){ | |
$frontier[$i] = (Frontier 0 (New-Object -TypeName "System.Collections.ArrayList") ) | |
} | |
for( $d=0; $d -le ($a_max + $b_max + 1); $d++ ){ | |
for( $k=-$d; $k -le $d+1; $k=$k+2 ){ | |
$go_down = ( | |
($k -eq -$d) -or | |
( | |
($k -ne $d) -and | |
($frontier[$k-1].x -lt $frontier[$k+1].x) | |
) | |
) | |
if( $go_down ){ | |
$old_x = $frontier[$k+1].x | |
$history = $frontier[$k+1].history | |
$x = $old_x | |
}else{ | |
$old_x = $frontier[$k-1].x | |
$history = $frontier[$k-1].history | |
$x = $old_x + 1 | |
} | |
$history = $history.clone() | |
$y = $x - $k | |
if( | |
(1 -le $y) -and | |
($y -le $b_max) -and | |
$go_down | |
){ | |
$history.Add( | |
(DiffInsert $b_lines[ (DiffOne $y) ]) | |
) | Out-Null | |
}elseif ( | |
(1 -le $x) -and | |
($x -le $a_max) | |
) { | |
$history.Add( | |
(DiffRemove $a_lines[ (DiffOne $x) ]) | |
) | Out-Null | |
} | |
while( | |
($x -lt $a_max) -and | |
($y -lt $b_max) -and | |
($a_lines[ (DiffOne (1+$x) )] -eq $b_lines[ (DiffOne (1+$y) ) ]) | |
){ | |
$x = $x+1 | |
$y = $y+1 | |
$history.Add( | |
(DiffKeep $a_lines[ (DiffOne $x) ]) | |
) | Out-Null | |
} | |
if( | |
($x -ge $a_max) -and | |
($y -ge $b_max) | |
){ | |
return $history | |
}else{ | |
$frontier[$k] = (Frontier $x $history) | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment