Skip to content

Instantly share code, notes, and snippets.

@sleekweasel

sleekweasel/diff.sh

Last active Jun 13, 2019
Embed
What would you like to do?
diff in oldish bash!
#!/bin/bash
#
# Implementation of https://en.wikipedia.org/wiki/Longest_common_subsequence_problem in old-ish BASH
# because my Android emulator doesn't have diff on it.
# Seriously bogs down on files >100 lines
# Could implement the common head and tail trimming efficiency.
XL=()
XC=()
while IFS= read -r line || [[ "$line" ]] ; do XL+=("$line") ; XC+=($(echo "$line" | cksum | tr ' ' -)) ; done < ${1?First filename required}
SXC=${#XC[@]}
YL=()
YC=()
while IFS= read -r line || [[ "$line" ]] ; do YL+=("$line") ; YC+=($(echo "$line" | cksum | tr ' ' -)); done < ${2?Second filename required}
SYC=${#YC[@]}
WW=$(($SYC + 1))
C=()
ix=0 ; while [ $ix -lt $SXC ] ; do
C[$((ix + 0 * WW))]=$((0))
ix=$((ix + 1))
done
iy=0 ; while [ $iy -lt $SYC ]; do
C[$((0 + iy * WW))]=$((0))
iy=$((iy + 1))
done
ix=1 ; while [ $ix -lt $SXC ] ; do
iy=1 ; while [ $iy -lt $SYC ] ; do
if [ ${XC[ix]} == ${YC[iy]} ] ; then
d=$((${C[(ix - 1) + (iy - 1) * WW]} + 1))
else
d1=${C[ix + (iy - 1) * WW]} ; d1=${d1:--1}
d2=${C[(ix - 1) + iy * WW]} ; d2=${d2:--1}
[ $d1 -lt $d2 ] && d=$d2 || d=$d1
fi
C[$((ix + iy * WW))]=$((d))
iy=$((iy + 1))
done
1>&2 echo -n .$((SXC - ix))
ix=$((ix + 1))
done
echo
pdiff() {
local ix=$(($1))
local iy=$(($2))
local up=${C[$((ix + (iy - 1) * WW))]} ; up=${up:--1}
local left=${C[$((ix - 1 + iy * WW))]} ; left=${left:--1}
if [ $ix -gt 0 ] && [ $iy -gt 0 ] && [ "${XC[$ix]}" = "${YC[$iy]}" ] ; then
pdiff $((ix - 1)) $((iy - 1))
echo "$ix=${XL[$ix]}"
elif [ $iy -gt 0 ] && [ $ix -eq 0 -o $up -ge $left ]; then
pdiff $ix $((iy - 1))
echo "$iy>${YL[$iy]}"
elif [ $ix -gt 0 ] && [ $iy -eq 0 -o $up -lt $left ]; then
pdiff $((ix - 1)) $iy
echo "$ix<${XL[$ix]}"
fi
}
pdiff $SXC $SYC
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment