module Darcs.Util.Diff.Patience
( getChanges
) where
import Darcs.Prelude
import Data.List ( sort )
import Data.Maybe ( fromJust )
import Data.Array.Unboxed
import Data.Array.ST
import Control.Monad.ST
import qualified Data.Set as S
import qualified Data.ByteString as B ( ByteString, elem )
import qualified Data.ByteString.Char8 as BC ( pack )
import qualified Data.Map.Strict as M
( Map, lookup, insertWith, empty, elems )
import qualified Data.Hashable as H ( hash )
import Darcs.Util.Diff.Myers (initP, aLen, PArray, getSlice)
empty :: HunkMap
empty :: HunkMap
empty = Hunk -> HMap Hunk [(Hunk, ByteString)] -> HunkMap
HunkMapInfo Hunk
0 forall k a. Map k a
M.empty
getChanges :: [B.ByteString] -> [B.ByteString]
-> [(Int,[B.ByteString],[B.ByteString])]
getChanges :: [ByteString]
-> [ByteString] -> [(Hunk, [ByteString], [ByteString])]
getChanges [ByteString]
a [ByteString]
b = PArray -> PArray -> Hunk -> [(Hunk, [ByteString], [ByteString])]
dropStart ([ByteString] -> PArray
initP [ByteString]
a) ([ByteString] -> PArray
initP [ByteString]
b) Hunk
1
dropStart :: PArray -> PArray -> Int
-> [(Int,[B.ByteString],[B.ByteString])]
dropStart :: PArray -> PArray -> Hunk -> [(Hunk, [ByteString], [ByteString])]
dropStart PArray
a PArray
b Hunk
off
| Hunk
off forall a. Ord a => a -> a -> Bool
> forall (a :: * -> * -> *) e. IArray a e => a Hunk e -> Hunk
aLen PArray
a = [(Hunk
off forall a. Num a => a -> a -> a
- Hunk
1, [], PArray -> Hunk -> Hunk -> [ByteString]
getSlice PArray
b Hunk
off (forall (a :: * -> * -> *) e. IArray a e => a Hunk e -> Hunk
aLen PArray
b))]
| Hunk
off forall a. Ord a => a -> a -> Bool
> forall (a :: * -> * -> *) e. IArray a e => a Hunk e -> Hunk
aLen PArray
b = [(Hunk
off forall a. Num a => a -> a -> a
- Hunk
1, PArray -> Hunk -> Hunk -> [ByteString]
getSlice PArray
a Hunk
off (forall (a :: * -> * -> *) e. IArray a e => a Hunk e -> Hunk
aLen PArray
a), [])]
| PArray
aforall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
!Hunk
off forall a. Eq a => a -> a -> Bool
== PArray
bforall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
!Hunk
off = PArray -> PArray -> Hunk -> [(Hunk, [ByteString], [ByteString])]
dropStart PArray
a PArray
b (Hunk
off forall a. Num a => a -> a -> a
+ Hunk
1)
| Bool
otherwise = PArray
-> PArray -> Hunk -> Hunk -> [(Hunk, [ByteString], [ByteString])]
dropEnd PArray
a PArray
b Hunk
off Hunk
0
dropEnd :: PArray -> PArray -> Int -> Int
-> [(Int,[B.ByteString],[B.ByteString])]
dropEnd :: PArray
-> PArray -> Hunk -> Hunk -> [(Hunk, [ByteString], [ByteString])]
dropEnd PArray
a PArray
b Hunk
off Hunk
end
| Hunk
off forall a. Ord a => a -> a -> Bool
> Hunk
alast = [(Hunk
off forall a. Num a => a -> a -> a
- Hunk
1, [], PArray -> Hunk -> Hunk -> [ByteString]
getSlice PArray
b Hunk
off Hunk
blast)]
| Hunk
off forall a. Ord a => a -> a -> Bool
> Hunk
blast = [(Hunk
off forall a. Num a => a -> a -> a
- Hunk
1, PArray -> Hunk -> Hunk -> [ByteString]
getSlice PArray
a Hunk
off Hunk
alast, [])]
| PArray
aforall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
!Hunk
alast forall a. Eq a => a -> a -> Bool
== PArray
bforall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
!Hunk
blast = PArray
-> PArray -> Hunk -> Hunk -> [(Hunk, [ByteString], [ByteString])]
dropEnd PArray
a PArray
b Hunk
off (Hunk
end forall a. Num a => a -> a -> a
+ Hunk
1)
| Bool
otherwise = Hunk
-> [ByteString]
-> [ByteString]
-> [(Hunk, [ByteString], [ByteString])]
getChanges' (Hunk
offforall a. Num a => a -> a -> a
-Hunk
1) (PArray -> Hunk -> Hunk -> [ByteString]
getSlice PArray
a Hunk
off (forall (a :: * -> * -> *) e. IArray a e => a Hunk e -> Hunk
aLen PArray
a forall a. Num a => a -> a -> a
- Hunk
end')) (PArray -> Hunk -> Hunk -> [ByteString]
getSlice PArray
b Hunk
off (forall (a :: * -> * -> *) e. IArray a e => a Hunk e -> Hunk
aLen PArray
b forall a. Num a => a -> a -> a
- Hunk
end'))
where end' :: Hunk
end' = Hunk -> Hunk
addBorings Hunk
end
addBorings :: Hunk -> Hunk
addBorings Hunk
e | Hunk
e forall a. Ord a => a -> a -> Bool
> Hunk
0 Bool -> Bool -> Bool
&& PArray
aforall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
!(forall (a :: * -> * -> *) e. IArray a e => a Hunk e -> Hunk
aLen PArray
a forall a. Num a => a -> a -> a
- (Hunk
eforall a. Num a => a -> a -> a
-Hunk
1)) forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [ByteString]
borings' = Hunk -> Hunk
addBorings (Hunk
eforall a. Num a => a -> a -> a
-Hunk
1)
| Bool
otherwise = Hunk
e
alast :: Hunk
alast = forall (a :: * -> * -> *) e. IArray a e => a Hunk e -> Hunk
aLen PArray
a forall a. Num a => a -> a -> a
- Hunk
end
blast :: Hunk
blast = forall (a :: * -> * -> *) e. IArray a e => a Hunk e -> Hunk
aLen PArray
b forall a. Num a => a -> a -> a
- Hunk
end
getChanges' :: Int -> [B.ByteString] -> [B.ByteString]
-> [(Int, [B.ByteString], [B.ByteString])]
getChanges' :: Hunk
-> [ByteString]
-> [ByteString]
-> [(Hunk, [ByteString], [ByteString])]
getChanges' Hunk
off [ByteString]
o [ByteString]
n = forall {a}.
[(a, [ByteString], [ByteString])]
-> [(a, [Hunk], [Hunk])] -> [(a, [ByteString], [ByteString])]
convertLBS [] forall a b. (a -> b) -> a -> b
$ [[Hunk] -> [[Hunk]]]
-> Hunk -> [Hunk] -> [Hunk] -> [(Hunk, [Hunk], [Hunk])]
genNestedChanges [[Hunk] -> [[Hunk]]
byparagraph, [Hunk] -> [[Hunk]]
bylines] Hunk
off [Hunk]
oh [Hunk]
nh
where
([Hunk]
_,HunkMap
m') = [ByteString] -> HunkMap -> ([Hunk], HunkMap)
listToHunk [ByteString]
borings' HunkMap
empty
([Hunk]
oh,HunkMap
m) = [ByteString] -> HunkMap -> ([Hunk], HunkMap)
listToHunk [ByteString]
o HunkMap
m'
([Hunk]
nh,HunkMap
lmap) = [ByteString] -> HunkMap -> ([Hunk], HunkMap)
listToHunk [ByteString]
n HunkMap
m
convertLBS :: [(a, [ByteString], [ByteString])]
-> [(a, [Hunk], [Hunk])] -> [(a, [ByteString], [ByteString])]
convertLBS [(a, [ByteString], [ByteString])]
ys [] = forall a. [a] -> [a]
reverse [(a, [ByteString], [ByteString])]
ys
convertLBS [(a, [ByteString], [ByteString])]
ys ((a
i,[Hunk]
os,[Hunk]
ns):[(a, [Hunk], [Hunk])]
xs) = [(a, [ByteString], [ByteString])]
-> [(a, [Hunk], [Hunk])] -> [(a, [ByteString], [ByteString])]
convertLBS ((a
i, [Hunk] -> [ByteString]
hunkToBS [Hunk]
os, [Hunk] -> [ByteString]
hunkToBS [Hunk]
ns)forall a. a -> [a] -> [a]
:[(a, [ByteString], [ByteString])]
ys) [(a, [Hunk], [Hunk])]
xs
hunkToBS :: [Hunk] -> [ByteString]
hunkToBS [Hunk]
hs = forall a b. (a -> b) -> [a] -> [b]
map (\Hunk
h -> forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
(!) PArray
harray (forall a. Num a => a -> a
abs Hunk
h)) [Hunk]
hs
harray :: PArray
harray = HunkMap -> PArray
getBArray HunkMap
lmap
type HMap = M.Map
type Hash = Int
type Hunk = Int
data HunkMap = HunkMapInfo Int (HMap Hash [(Hunk, B.ByteString)])
getMap :: HunkMap -> HMap Hash [(Hunk, B.ByteString)]
getMap :: HunkMap -> HMap Hunk [(Hunk, ByteString)]
getMap (HunkMapInfo Hunk
_ HMap Hunk [(Hunk, ByteString)]
m) = HMap Hunk [(Hunk, ByteString)]
m
getSize :: HunkMap -> Int
getSize :: HunkMap -> Hunk
getSize (HunkMapInfo Hunk
s HMap Hunk [(Hunk, ByteString)]
_) = Hunk
s
getBArray :: HunkMap -> Array Hunk B.ByteString
getBArray :: HunkMap -> PArray
getBArray (HunkMapInfo Hunk
size HMap Hunk [(Hunk, ByteString)]
b) = forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
(i, i) -> [(i, e)] -> a i e
array (Hunk
1,Hunk
size) forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map (\(Hunk
x,ByteString
a) -> (forall a. Num a => a -> a
abs Hunk
x, ByteString
a)) forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat forall a b. (a -> b) -> a -> b
$ forall k a. Map k a -> [a]
M.elems HMap Hunk [(Hunk, ByteString)]
b
insert :: Hash -> B.ByteString -> HunkMap -> (Hunk, HunkMap)
insert :: Hunk -> ByteString -> HunkMap -> (Hunk, HunkMap)
insert Hunk
h ByteString
bs HunkMap
hmap = (Hunk
hunknumber, Hunk -> HMap Hunk [(Hunk, ByteString)] -> HunkMap
HunkMapInfo Hunk
newsize (forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
M.insertWith (\[(Hunk, ByteString)]
_ [(Hunk, ByteString)]
o -> (Hunk
hunknumber,ByteString
bs)forall a. a -> [a] -> [a]
:[(Hunk, ByteString)]
o) Hunk
h [(Hunk
hunknumber,ByteString
bs)] forall a b. (a -> b) -> a -> b
$ HunkMap -> HMap Hunk [(Hunk, ByteString)]
getMap HunkMap
hmap))
where hunknumber :: Hunk
hunknumber = if Word8 -> ByteString -> Bool
B.elem Word8
nl ByteString
bs then -Hunk
newsize
else Hunk
newsize
newsize :: Hunk
newsize = HunkMap -> Hunk
getSize HunkMap
hmapforall a. Num a => a -> a -> a
+Hunk
1
nl :: Word8
nl = Word8
10
toHunk' :: HunkMap -> B.ByteString -> (Hunk, HunkMap)
toHunk' :: HunkMap -> ByteString -> (Hunk, HunkMap)
toHunk' HunkMap
lmap ByteString
bs | Maybe [(Hunk, ByteString)]
oldbs forall a. Eq a => a -> a -> Bool
== forall a. Maybe a
Nothing Bool -> Bool -> Bool
|| forall (t :: * -> *) a. Foldable t => t a -> Bool
null [(Hunk, ByteString)]
oldhunkpair = Hunk -> ByteString -> HunkMap -> (Hunk, HunkMap)
insert Hunk
hash ByteString
bs HunkMap
lmap
| Bool
otherwise = (forall a b. (a, b) -> a
fst forall a b. (a -> b) -> a -> b
$ forall a. [a] -> a
head [(Hunk, ByteString)]
oldhunkpair, HunkMap
lmap)
where hash :: Hunk
hash = forall a. Hashable a => a -> Hunk
H.hash ByteString
bs
oldbs :: Maybe [(Hunk, ByteString)]
oldbs = forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup Hunk
hash (HunkMap -> HMap Hunk [(Hunk, ByteString)]
getMap HunkMap
lmap)
oldhunkpair :: [(Hunk, ByteString)]
oldhunkpair = forall a. (a -> Bool) -> [a] -> [a]
filter ((forall a. Eq a => a -> a -> Bool
== ByteString
bs) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> b
snd) forall a b. (a -> b) -> a -> b
$ forall a. HasCallStack => Maybe a -> a
fromJust Maybe [(Hunk, ByteString)]
oldbs
listToHunk :: [B.ByteString] -> HunkMap -> ([Hunk], HunkMap)
listToHunk :: [ByteString] -> HunkMap -> ([Hunk], HunkMap)
listToHunk [] HunkMap
hmap = ([], HunkMap
hmap)
listToHunk (ByteString
x:[ByteString]
xs) HunkMap
hmap = let (Hunk
y, HunkMap
hmap') = HunkMap -> ByteString -> (Hunk, HunkMap)
toHunk' HunkMap
hmap ByteString
x
([Hunk]
ys, HunkMap
hmap'') = [ByteString] -> HunkMap -> ([Hunk], HunkMap)
listToHunk [ByteString]
xs HunkMap
hmap'
in (Hunk
yforall a. a -> [a] -> [a]
:[Hunk]
ys, HunkMap
hmap'')
genNestedChanges :: [[Hunk] -> [[Hunk]]]
-> Int -> [Hunk] -> [Hunk]
-> [(Int, [Hunk], [Hunk])]
genNestedChanges :: [[Hunk] -> [[Hunk]]]
-> Hunk -> [Hunk] -> [Hunk] -> [(Hunk, [Hunk], [Hunk])]
genNestedChanges ([Hunk] -> [[Hunk]]
br:[[Hunk] -> [[Hunk]]]
brs) Hunk
i0 [Hunk]
o0 [Hunk]
n0 = Hunk
-> [[Hunk]] -> [[Hunk]] -> [[Hunk]] -> [(Hunk, [Hunk], [Hunk])]
nc Hunk
i0 (forall a. Ord a => [a] -> [a] -> [a]
lcus [[Hunk]]
ol [[Hunk]]
nl) [[Hunk]]
ol [[Hunk]]
nl
where nl :: [[Hunk]]
nl = [Hunk] -> [[Hunk]]
br [Hunk]
n0
ol :: [[Hunk]]
ol = [Hunk] -> [[Hunk]]
br [Hunk]
o0
nc :: Hunk
-> [[Hunk]] -> [[Hunk]] -> [[Hunk]] -> [(Hunk, [Hunk], [Hunk])]
nc Hunk
i [] [[Hunk]]
o [[Hunk]]
n = forall {t :: * -> *} {t :: * -> *}.
(Foldable t, Foldable t) =>
Hunk -> t [Hunk] -> t [Hunk] -> [(Hunk, [Hunk], [Hunk])]
easydiff Hunk
i [[Hunk]]
o [[Hunk]]
n
nc Hunk
i ([Hunk]
x:[[Hunk]]
xs) [[Hunk]]
o [[Hunk]]
n =
case forall a. (a -> Bool) -> [a] -> ([a], [a])
break (forall a. Eq a => a -> a -> Bool
==[Hunk]
x) [[Hunk]]
o of
([[Hunk]]
oa, [Hunk]
_:[[Hunk]]
ob) ->
case forall a. (a -> Bool) -> [a] -> ([a], [a])
break (forall a. Eq a => a -> a -> Bool
==[Hunk]
x) [[Hunk]]
n of
([[Hunk]]
na, [Hunk]
_:[[Hunk]]
nb) ->
Hunk
i' seq :: forall a b. a -> b -> b
`seq` forall {t :: * -> *} {t :: * -> *}.
(Foldable t, Foldable t) =>
Hunk -> t [Hunk] -> t [Hunk] -> [(Hunk, [Hunk], [Hunk])]
easydiff Hunk
i [[Hunk]]
oa [[Hunk]]
na forall a. [a] -> [a] -> [a]
++ Hunk
-> [[Hunk]] -> [[Hunk]] -> [[Hunk]] -> [(Hunk, [Hunk], [Hunk])]
nc Hunk
i' [[Hunk]]
xs [[Hunk]]
ob [[Hunk]]
nb
where i' :: Hunk
i' = Hunk
i forall a. Num a => a -> a -> a
+ forall (t :: * -> *) a. Foldable t => t a -> Hunk
length (forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[Hunk]]
na) forall a. Num a => a -> a -> a
+ forall (t :: * -> *) a. Foldable t => t a -> Hunk
length [Hunk]
x
([[Hunk]]
_,[]) -> forall a. HasCallStack => [Char] -> a
error [Char]
"impossible case"
([[Hunk]]
_,[]) -> forall a. HasCallStack => [Char] -> a
error [Char]
"impossible case"
easydiff :: Hunk -> t [Hunk] -> t [Hunk] -> [(Hunk, [Hunk], [Hunk])]
easydiff Hunk
i t [Hunk]
o t [Hunk]
n = [[Hunk] -> [[Hunk]]]
-> Hunk -> [Hunk] -> [Hunk] -> [(Hunk, [Hunk], [Hunk])]
genNestedChanges [[Hunk] -> [[Hunk]]]
brs Hunk
i [Hunk]
oo [Hunk]
nn
where ([Hunk]
oo, [Hunk]
nn) = (forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat t [Hunk]
o, forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat t [Hunk]
n)
genNestedChanges [] Hunk
i [Hunk]
o [Hunk]
n = forall a.
Ord a =>
([a] -> Bool) -> Hunk -> [a] -> [a] -> [a] -> [(Hunk, [a], [a])]
mkdiff (forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [Hunk]
borings)) Hunk
i [Hunk]
mylcs [Hunk]
o [Hunk]
n
where mylcs :: [Hunk]
mylcs = forall a. Ord a => [a] -> [a] -> [a]
patientLcs (forall a. (a -> Bool) -> [a] -> [a]
filter (forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` [Hunk]
borings) [Hunk]
o)
(forall a. (a -> Bool) -> [a] -> [a]
filter (forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` [Hunk]
borings) [Hunk]
n)
borings :: [Hunk]
borings :: [Hunk]
borings = forall a b. (a, b) -> a
fst forall a b. (a -> b) -> a -> b
$ [ByteString] -> HunkMap -> ([Hunk], HunkMap)
listToHunk [ByteString]
borings' HunkMap
empty
borings' :: [B.ByteString]
borings' :: [ByteString]
borings' = forall a b. (a -> b) -> [a] -> [b]
map [Char] -> ByteString
BC.pack [[Char]
"", [Char]
"\n", [Char]
" ", [Char]
")", [Char]
"(", [Char]
","]
byparagraph :: [Hunk] -> [[Hunk]]
byparagraph :: [Hunk] -> [[Hunk]]
byparagraph = forall a. [a] -> [a]
reverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map forall a. [a] -> [a]
reverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[Hunk]] -> [Hunk] -> [[Hunk]]
byparagraphAcc []
where byparagraphAcc :: [[Hunk]] -> [Hunk] -> [[Hunk]]
byparagraphAcc [[Hunk]]
xs [] = [[Hunk]]
xs
byparagraphAcc [] (Hunk
a:Hunk
b:Hunk
c:[Hunk]
d)
| Hunk
a forall a. Eq a => a -> a -> Bool
== Hunk
nl Bool -> Bool -> Bool
&& Hunk
c forall a. Eq a => a -> a -> Bool
== Hunk
nl Bool -> Bool -> Bool
&& Hunk
b forall a. Eq a => a -> a -> Bool
== Hunk
hnull = case [Hunk]
d of
[] -> [[Hunk
c,Hunk
b,Hunk
a]]
[Hunk]
_ -> [[Hunk]] -> [Hunk] -> [[Hunk]]
byparagraphAcc [[],[Hunk
c,Hunk
b,Hunk
a]] [Hunk]
d
byparagraphAcc [] (Hunk
a:[Hunk]
as) = [[Hunk]] -> [Hunk] -> [[Hunk]]
byparagraphAcc [[Hunk
a]] [Hunk]
as
byparagraphAcc ([Hunk]
x:[[Hunk]]
xs) (Hunk
a:Hunk
b:Hunk
c:[Hunk]
d)
| Hunk
a forall a. Eq a => a -> a -> Bool
== Hunk
nl Bool -> Bool -> Bool
&& Hunk
c forall a. Eq a => a -> a -> Bool
== Hunk
nl Bool -> Bool -> Bool
&& Hunk
b forall a. Eq a => a -> a -> Bool
== Hunk
hnull = case [Hunk]
d of
[] -> (Hunk
cforall a. a -> [a] -> [a]
:Hunk
bforall a. a -> [a] -> [a]
:Hunk
aforall a. a -> [a] -> [a]
:[Hunk]
x)forall a. a -> [a] -> [a]
:[[Hunk]]
xs
[Hunk]
_ -> [[Hunk]] -> [Hunk] -> [[Hunk]]
byparagraphAcc ([]forall a. a -> [a] -> [a]
:((Hunk
cforall a. a -> [a] -> [a]
:Hunk
bforall a. a -> [a] -> [a]
:Hunk
aforall a. a -> [a] -> [a]
:[Hunk]
x)forall a. a -> [a] -> [a]
:[[Hunk]]
xs)) [Hunk]
d
byparagraphAcc ([Hunk]
x:[[Hunk]]
xs) (Hunk
a:[Hunk]
as) = [[Hunk]] -> [Hunk] -> [[Hunk]]
byparagraphAcc ((Hunk
aforall a. a -> [a] -> [a]
:[Hunk]
x)forall a. a -> [a] -> [a]
:[[Hunk]]
xs) [Hunk]
as
nl :: Hunk
nl = -Hunk
1
hnull :: Hunk
hnull = Hunk
1
bylines :: [Hunk] -> [[Hunk]]
bylines :: [Hunk] -> [[Hunk]]
bylines = forall a. [a] -> [a]
reverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {a}. (Ord a, Num a) => [[a]] -> [a] -> [[a]]
bylinesAcc []
where bylinesAcc :: [[a]] -> [a] -> [[a]]
bylinesAcc ![[a]]
ys [] = [[a]]
ys
bylinesAcc ![[a]]
ys [a]
xs = case forall a. (a -> Bool) -> [a] -> ([a], [a])
break (forall a. Ord a => a -> a -> Bool
<a
0) [a]
xs of
([a]
_,[]) -> [a]
xsforall a. a -> [a] -> [a]
:[[a]]
ys
([a]
a,a
n:[a]
b) -> [[a]] -> [a] -> [[a]]
bylinesAcc (([a]
aforall a. [a] -> [a] -> [a]
++[a
n])forall a. a -> [a] -> [a]
:[[a]]
ys) [a]
b
lcus :: Ord a => [a] -> [a] -> [a]
lcus :: forall a. Ord a => [a] -> [a] -> [a]
lcus [a]
xs0 [a]
ys0 = forall a. Ord a => [a] -> [a] -> [a]
lcs (forall a. (a -> Bool) -> [a] -> [a]
filter (forall a. Ord a => a -> Set a -> Bool
`S.member`Set a
u) [a]
xs0) (forall a. (a -> Bool) -> [a] -> [a]
filter (forall a. Ord a => a -> Set a -> Bool
`S.member`Set a
u) [a]
ys0)
where uxs :: Set a
uxs = forall {a}. Ord a => [a] -> Set a
findUnique [a]
xs0
uys :: Set a
uys = forall {a}. Ord a => [a] -> Set a
findUnique [a]
ys0
u :: Set a
u = forall a. Ord a => Set a -> Set a -> Set a
S.intersection Set a
uxs Set a
uys
findUnique :: [a] -> Set a
findUnique [a]
xs = forall {a}. Ord a => [a] -> Set a
S.fromList forall a b. (a -> b) -> a -> b
$ forall {a}. Eq a => [a] -> [a]
gru forall a b. (a -> b) -> a -> b
$ forall a. Ord a => [a] -> [a]
sort [a]
xs
gru :: [a] -> [a]
gru (a
x:a
x':[a]
xs) | a
x forall a. Eq a => a -> a -> Bool
== a
x' = [a] -> [a]
gru (forall a. (a -> Bool) -> [a] -> [a]
dropWhile (forall a. Eq a => a -> a -> Bool
==a
x) [a]
xs)
gru (a
x:[a]
xs) = a
x forall a. a -> [a] -> [a]
: [a] -> [a]
gru [a]
xs
gru [] = []
mkdiff :: Ord a =>
([a] -> Bool) -> Int -> [a] -> [a] -> [a] -> [(Int,[a],[a])]
mkdiff :: forall a.
Ord a =>
([a] -> Bool) -> Hunk -> [a] -> [a] -> [a] -> [(Hunk, [a], [a])]
mkdiff [a] -> Bool
b Hunk
ny (a
l:[a]
ls) (a
x:[a]
xs) (a
y:[a]
ys)
| a
l forall a. Eq a => a -> a -> Bool
== a
x Bool -> Bool -> Bool
&& a
l forall a. Eq a => a -> a -> Bool
== a
y = forall a.
Ord a =>
([a] -> Bool) -> Hunk -> [a] -> [a] -> [a] -> [(Hunk, [a], [a])]
mkdiff [a] -> Bool
b (Hunk
nyforall a. Num a => a -> a -> a
+Hunk
1) [a]
ls [a]
xs [a]
ys
mkdiff [a] -> Bool
boring Hunk
ny (a
l:[a]
ls) [a]
xs [a]
ys
| [a]
rmd forall a. Eq a => a -> a -> Bool
== [a]
add = forall a.
Ord a =>
([a] -> Bool) -> Hunk -> [a] -> [a] -> [a] -> [(Hunk, [a], [a])]
mkdiff [a] -> Bool
boring (Hunk
nyforall a. Num a => a -> a -> a
+forall (t :: * -> *) a. Foldable t => t a -> Hunk
length [a]
addforall a. Num a => a -> a -> a
+Hunk
1) [a]
ls [a]
restx [a]
resty
| [a] -> Bool
boring [a]
rmd Bool -> Bool -> Bool
&& [a] -> Bool
boring [a]
add =
case forall a. Ord a => [a] -> [a] -> [a]
lcs [a]
rmd [a]
add of
[] -> forall a. Ord a => Hunk -> [a] -> [a] -> [(Hunk, [a], [a])]
prefixPostfixDiff Hunk
ny [a]
rmd [a]
add forall a. [a] -> [a] -> [a]
++
forall a.
Ord a =>
([a] -> Bool) -> Hunk -> [a] -> [a] -> [a] -> [(Hunk, [a], [a])]
mkdiff [a] -> Bool
boring (Hunk
nyforall a. Num a => a -> a -> a
+forall (t :: * -> *) a. Foldable t => t a -> Hunk
length [a]
addforall a. Num a => a -> a -> a
+Hunk
1) [a]
ls [a]
restx [a]
resty
[a]
ll -> forall a.
Ord a =>
([a] -> Bool) -> Hunk -> [a] -> [a] -> [a] -> [(Hunk, [a], [a])]
mkdiff (forall a b. a -> b -> a
const Bool
False) Hunk
ny [a]
ll [a]
rmd [a]
add forall a. [a] -> [a] -> [a]
++
forall a.
Ord a =>
([a] -> Bool) -> Hunk -> [a] -> [a] -> [a] -> [(Hunk, [a], [a])]
mkdiff [a] -> Bool
boring (Hunk
nyforall a. Num a => a -> a -> a
+forall (t :: * -> *) a. Foldable t => t a -> Hunk
length [a]
addforall a. Num a => a -> a -> a
+Hunk
1) [a]
ls [a]
restx [a]
resty
| Bool
otherwise = forall a. Ord a => Hunk -> [a] -> [a] -> [(Hunk, [a], [a])]
prefixPostfixDiff Hunk
ny [a]
rmd [a]
add forall a. [a] -> [a] -> [a]
++
forall a.
Ord a =>
([a] -> Bool) -> Hunk -> [a] -> [a] -> [a] -> [(Hunk, [a], [a])]
mkdiff [a] -> Bool
boring (Hunk
nyforall a. Num a => a -> a -> a
+forall (t :: * -> *) a. Foldable t => t a -> Hunk
length [a]
addforall a. Num a => a -> a -> a
+Hunk
1) [a]
ls [a]
restx [a]
resty
where rmd :: [a]
rmd = forall a. (a -> Bool) -> [a] -> [a]
takeWhile (forall a. Eq a => a -> a -> Bool
/= a
l) [a]
xs
add :: [a]
add = forall a. (a -> Bool) -> [a] -> [a]
takeWhile (forall a. Eq a => a -> a -> Bool
/= a
l) [a]
ys
restx :: [a]
restx = forall a. Hunk -> [a] -> [a]
drop (forall (t :: * -> *) a. Foldable t => t a -> Hunk
length [a]
rmd forall a. Num a => a -> a -> a
+ Hunk
1) [a]
xs
resty :: [a]
resty = forall a. Hunk -> [a] -> [a]
drop (forall (t :: * -> *) a. Foldable t => t a -> Hunk
length [a]
add forall a. Num a => a -> a -> a
+ Hunk
1) [a]
ys
mkdiff [a] -> Bool
_ Hunk
_ [] [] [] = []
mkdiff [a] -> Bool
boring Hunk
ny [] [a]
rmd [a]
add
| [a] -> Bool
boring [a]
rmd Bool -> Bool -> Bool
&& [a] -> Bool
boring [a]
add =
case forall a. Ord a => [a] -> [a] -> [a]
lcs [a]
rmd [a]
add of
[] -> forall a. Ord a => Hunk -> [a] -> [a] -> [(Hunk, [a], [a])]
prefixPostfixDiff Hunk
ny [a]
rmd [a]
add
[a]
ll -> forall a.
Ord a =>
([a] -> Bool) -> Hunk -> [a] -> [a] -> [a] -> [(Hunk, [a], [a])]
mkdiff (forall a b. a -> b -> a
const Bool
False) Hunk
ny [a]
ll [a]
rmd [a]
add
| Bool
otherwise = forall a. Ord a => Hunk -> [a] -> [a] -> [(Hunk, [a], [a])]
prefixPostfixDiff Hunk
ny [a]
rmd [a]
add
prefixPostfixDiff :: Ord a => Int -> [a] -> [a] -> [(Int,[a],[a])]
prefixPostfixDiff :: forall a. Ord a => Hunk -> [a] -> [a] -> [(Hunk, [a], [a])]
prefixPostfixDiff Hunk
_ [] [] = []
prefixPostfixDiff Hunk
ny [] [a]
ys = [(Hunk
ny,[],[a]
ys)]
prefixPostfixDiff Hunk
ny [a]
xs [] = [(Hunk
ny,[a]
xs,[])]
prefixPostfixDiff Hunk
ny (a
x:[a]
xs) (a
y:[a]
ys)
| a
x forall a. Eq a => a -> a -> Bool
== a
y = forall a. Ord a => Hunk -> [a] -> [a] -> [(Hunk, [a], [a])]
prefixPostfixDiff (Hunk
nyforall a. Num a => a -> a -> a
+Hunk
1) [a]
xs [a]
ys
| Bool
otherwise = [(Hunk
ny, forall a. [a] -> [a]
reverse [a]
rxs', forall a. [a] -> [a]
reverse [a]
rys')]
where ([a]
rxs',[a]
rys') = forall {a}. Eq a => [a] -> [a] -> ([a], [a])
dropPref (forall a. [a] -> [a]
reverse (a
xforall a. a -> [a] -> [a]
:[a]
xs)) (forall a. [a] -> [a]
reverse (a
yforall a. a -> [a] -> [a]
:[a]
ys))
dropPref :: [a] -> [a] -> ([a], [a])
dropPref (a
a:[a]
as) (a
b:[a]
bs) | a
a forall a. Eq a => a -> a -> Bool
== a
b = [a] -> [a] -> ([a], [a])
dropPref [a]
as [a]
bs
dropPref [a]
as [a]
bs = ([a]
as,[a]
bs)
{-# SPECIALIZE patientLcs ::[Hunk] -> [Hunk] -> [Hunk] #-}
patientLcs :: Ord a => [a] -> [a] -> [a]
patientLcs :: forall a. Ord a => [a] -> [a] -> [a]
patientLcs [] [a]
_ = []
patientLcs [a]
_ [] = []
patientLcs (a
c1:[a]
c1s) (a
c2:[a]
c2s)
| a
c1 forall a. Eq a => a -> a -> Bool
== a
c2 = a
c1forall a. a -> [a] -> [a]
: forall a. Ord a => [a] -> [a] -> [a]
patientLcs [a]
c1s [a]
c2s
| Bool
otherwise =
forall a. [a] -> [a]
reverse forall a b. (a -> b) -> a -> b
$ forall a. Ord a => [a] -> [a] -> [a]
patientLcs0 (forall a. [a] -> [a]
reverse (a
c1forall a. a -> [a] -> [a]
:[a]
c1s)) (forall a. [a] -> [a]
reverse (a
c2forall a. a -> [a] -> [a]
:[a]
c2s))
patientLcs0 :: Ord a => [a] -> [a] -> [a]
patientLcs0 :: forall a. Ord a => [a] -> [a] -> [a]
patientLcs0 xs0 :: [a]
xs0@(a
cc1:[a]
cc1s) ys0 :: [a]
ys0@(a
cc2:[a]
cc2s)
| a
cc1 forall a. Eq a => a -> a -> Bool
== a
cc2 = a
cc1 forall a. a -> [a] -> [a]
: forall a. Ord a => [a] -> [a] -> [a]
patientLcs0 [a]
cc1s [a]
cc2s
| Bool
otherwise = case (forall a. (a -> Bool) -> [a] -> [a]
filter (forall a. Ord a => a -> Set a -> Bool
`S.member`Set a
uys) [a]
xs0, forall a. (a -> Bool) -> [a] -> [a]
filter (forall a. Ord a => a -> Set a -> Bool
`S.member`Set a
uxs) [a]
ys0) of
([],[a]
_) -> forall a. Ord a => [a] -> [a] -> [a]
lcs [a]
xs0 [a]
ys0
([a]
_,[]) -> forall a. Ord a => [a] -> [a] -> [a]
lcs [a]
xs0 [a]
ys0
([a]
xs',[a]
ys') -> forall {a}. Ord a => [a] -> [a] -> [a] -> [a]
joinU (forall a. Ord a => [a] -> [a] -> [a]
lcs [a]
xs' [a]
ys') [a]
xs0 [a]
ys0
where uxs :: Set a
uxs = forall {a}. Ord a => [a] -> Set a
findUnique [a]
xs0
uys :: Set a
uys = forall {a}. Ord a => [a] -> Set a
findUnique [a]
ys0
joinU :: [a] -> [a] -> [a] -> [a]
joinU [] [a]
x [a]
y = forall a. Ord a => [a] -> [a] -> [a]
lcs [a]
x [a]
y
joinU (a
b:[a]
bs) [a]
cs [a]
ds =
case forall a. (a -> Bool) -> [a] -> ([a], [a])
break (forall a. Eq a => a -> a -> Bool
==a
b) [a]
cs of
([],a
_:[a]
c2) -> a
b forall a. a -> [a] -> [a]
: [a] -> [a] -> [a] -> [a]
joinU [a]
bs [a]
c2 (forall a. Hunk -> [a] -> [a]
drop Hunk
1 forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
dropWhile (forall a. Eq a => a -> a -> Bool
/= a
b) [a]
ds)
([a]
c1,a
_:[a]
c2) -> case forall a. (a -> Bool) -> [a] -> ([a], [a])
break (forall a. Eq a => a -> a -> Bool
==a
b) [a]
ds of
([],a
_:[a]
d2) -> a
b forall a. a -> [a] -> [a]
: [a] -> [a] -> [a] -> [a]
joinU [a]
bs [a]
c2 [a]
d2
([a]
d1,a
_:[a]
d2) -> forall a. Ord a => [a] -> [a] -> [a]
lcs [a]
c1 [a]
d1 forall a. [a] -> [a] -> [a]
++ a
b forall a. a -> [a] -> [a]
: [a] -> [a] -> [a] -> [a]
joinU [a]
bs [a]
c2 [a]
d2
([a], [a])
_ -> forall a. HasCallStack => [Char] -> a
error [Char]
"impossible case"
([a], [a])
_ -> forall a. HasCallStack => [Char] -> a
error [Char]
"impossible case"
findUnique :: [a] -> Set a
findUnique [a]
xs = forall {a}. Ord a => [a] -> Set a
S.fromList forall a b. (a -> b) -> a -> b
$ forall {a}. Eq a => [a] -> [a]
gru forall a b. (a -> b) -> a -> b
$ forall a. Ord a => [a] -> [a]
sort [a]
xs
gru :: [a] -> [a]
gru (a
x:a
x':[a]
xs) | a
x forall a. Eq a => a -> a -> Bool
== a
x' = [a] -> [a]
gru (forall a. (a -> Bool) -> [a] -> [a]
dropWhile (forall a. Eq a => a -> a -> Bool
==a
x) [a]
xs)
gru (a
x:[a]
xs) = a
x forall a. a -> [a] -> [a]
: [a] -> [a]
gru [a]
xs
gru [] = []
patientLcs0 [] [a]
_ = []
patientLcs0 [a]
_ [] = []
{-# SPECIALIZE lcs ::[Hunk] -> [Hunk] -> [Hunk] #-}
lcs :: Ord a => [a] -> [a] -> [a]
lcs :: forall a. Ord a => [a] -> [a] -> [a]
lcs [] [a]
_ = []
lcs [a]
_ [] = []
lcs (a
c1:[a]
c1s) (a
c2:[a]
c2s)
| a
c1 forall a. Eq a => a -> a -> Bool
== a
c2 = a
c1forall a. a -> [a] -> [a]
: forall a. Ord a => [a] -> [a] -> [a]
lcs [a]
c1s [a]
c2s
| Bool
otherwise =
forall a. [a] -> [a]
reverse forall a b. (a -> b) -> a -> b
$ forall a. Ord a => [a] -> [a] -> [a]
lcsSimple (forall a. [a] -> [a]
reverse (a
c1forall a. a -> [a] -> [a]
:[a]
c1s)) (forall a. [a] -> [a]
reverse (a
c2forall a. a -> [a] -> [a]
:[a]
c2s))
lcsSimple :: Ord a => [a] -> [a] -> [a]
lcsSimple :: forall a. Ord a => [a] -> [a] -> [a]
lcsSimple [] [a]
_ = []
lcsSimple [a]
_ [] = []
lcsSimple s1 :: [a]
s1@(a
c1:[a]
c1s) s2 :: [a]
s2@(a
c2:[a]
c2s)
| a
c1 forall a. Eq a => a -> a -> Bool
== a
c2 = a
c1forall a. a -> [a] -> [a]
: forall a. Ord a => [a] -> [a] -> [a]
lcs [a]
c1s [a]
c2s
| Bool
otherwise = forall a. [(a, [Hunk])] -> [a]
hunt forall a b. (a -> b) -> a -> b
$ forall a. [a] -> [[Hunk]] -> [(a, [Hunk])]
pruneMatches [a]
s1 forall a b. (a -> b) -> a -> b
$! forall a. Ord a => [a] -> [a] -> [[Hunk]]
findMatches [a]
s1 [a]
s2
pruneMatches :: [a] -> [[Int]] -> [(a, [Int])]
pruneMatches :: forall a. [a] -> [[Hunk]] -> [(a, [Hunk])]
pruneMatches [a]
_ [] = []
pruneMatches [] [[Hunk]]
_ = []
pruneMatches (a
_:[a]
cs) ([]:[[Hunk]]
ms) = forall a. [a] -> [[Hunk]] -> [(a, [Hunk])]
pruneMatches [a]
cs [[Hunk]]
ms
pruneMatches (a
c:[a]
cs) ([Hunk]
m:[[Hunk]]
ms) = (a
c,[Hunk]
m)forall a. a -> [a] -> [a]
: forall a. [a] -> [[Hunk]] -> [(a, [Hunk])]
pruneMatches [a]
cs [[Hunk]]
ms
type Threshold s a = STArray s Int (Int,[a])
hunt :: [(a, [Int])] -> [a]
hunt :: forall a. [(a, [Hunk])] -> [a]
hunt [] = []
hunt [(a, [Hunk])]
csmatches =
forall a. (forall s. ST s a) -> a
runST ( do Threshold s a
th <- forall s a. Hunk -> Hunk -> ST s (Threshold s a)
emptyThreshold (forall (t :: * -> *) a. Foldable t => t a -> Hunk
length [(a, [Hunk])]
csmatches) Hunk
l
forall a s. [(a, [Hunk])] -> Threshold s a -> ST s ()
huntInternal [(a, [Hunk])]
csmatches Threshold s a
th
forall s a. Threshold s a -> Hunk -> Hunk -> ST s [a]
huntRecover Threshold s a
th (-Hunk
1) Hunk
l )
where l :: Hunk
l = forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum (Hunk
0 forall a. a -> [a] -> [a]
: forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat (forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd [(a, [Hunk])]
csmatches))
huntInternal :: [(a, [Int])] -> Threshold s a -> ST s ()
huntInternal :: forall a s. [(a, [Hunk])] -> Threshold s a -> ST s ()
huntInternal [] Threshold s a
_ = forall (m :: * -> *) a. Monad m => a -> m a
return ()
huntInternal ((a
c,[Hunk]
m):[(a, [Hunk])]
csms) Threshold s a
th = do
forall a s. a -> [Hunk] -> Threshold s a -> ST s ()
huntOneChar a
c [Hunk]
m Threshold s a
th
forall a s. [(a, [Hunk])] -> Threshold s a -> ST s ()
huntInternal [(a, [Hunk])]
csms Threshold s a
th
huntOneChar :: a -> [Int] -> Threshold s a -> ST s ()
huntOneChar :: forall a s. a -> [Hunk] -> Threshold s a -> ST s ()
huntOneChar a
_ [] Threshold s a
_ = forall (m :: * -> *) a. Monad m => a -> m a
return ()
huntOneChar a
c (Hunk
j:[Hunk]
js) Threshold s a
th = do
Maybe Hunk
index_k <- forall s a. Hunk -> Threshold s a -> ST s (Maybe Hunk)
myBs Hunk
j Threshold s a
th
case Maybe Hunk
index_k of
Maybe Hunk
Nothing -> forall (m :: * -> *) a. Monad m => a -> m a
return ()
Just Hunk
k -> do
(Hunk
_, [a]
rest) <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> m e
readArray Threshold s a
th (Hunk
kforall a. Num a => a -> a -> a
-Hunk
1)
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> e -> m ()
writeArray Threshold s a
th Hunk
k (Hunk
j, a
cforall a. a -> [a] -> [a]
:[a]
rest)
forall a s. a -> [Hunk] -> Threshold s a -> ST s ()
huntOneChar a
c [Hunk]
js Threshold s a
th
huntRecover :: Threshold s a -> Int -> Int -> ST s [a]
huntRecover :: forall s a. Threshold s a -> Hunk -> Hunk -> ST s [a]
huntRecover Threshold s a
th Hunk
n Hunk
limit =
do (Hunk
_, Hunk
th_max) <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> m (i, i)
getBounds Threshold s a
th
if Hunk
n forall a. Ord a => a -> a -> Bool
< Hunk
0
then forall s a. Threshold s a -> Hunk -> Hunk -> ST s [a]
huntRecover Threshold s a
th Hunk
th_max Hunk
limit
else if Hunk
n forall a. Eq a => a -> a -> Bool
== Hunk
0 Bool -> Bool -> Bool
|| Hunk
n forall a. Ord a => a -> a -> Bool
> Hunk
th_max
then forall (m :: * -> *) a. Monad m => a -> m a
return []
else do (Hunk
thn, [a]
sn) <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> m e
readArray Threshold s a
th Hunk
n
if Hunk
thn forall a. Ord a => a -> a -> Bool
<= Hunk
limit
then forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. [a] -> [a]
reverse [a]
sn
else forall s a. Threshold s a -> Hunk -> Hunk -> ST s [a]
huntRecover Threshold s a
th (Hunk
nforall a. Num a => a -> a -> a
-Hunk
1) Hunk
limit
emptyThreshold :: Int -> Int -> ST s (Threshold s a)
emptyThreshold :: forall s a. Hunk -> Hunk -> ST s (Threshold s a)
emptyThreshold Hunk
l Hunk
th_max = do
Threshold s a
th <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> e -> m (a i e)
newArray (Hunk
0,Hunk
l) (Hunk
th_maxforall a. Num a => a -> a -> a
+Hunk
1, [])
forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> e -> m ()
writeArray Threshold s a
th Hunk
0 (Hunk
0, [])
forall (m :: * -> *) a. Monad m => a -> m a
return Threshold s a
th
myBs :: Int -> Threshold s a -> ST s (Maybe Int)
myBs :: forall s a. Hunk -> Threshold s a -> ST s (Maybe Hunk)
myBs Hunk
j Threshold s a
th = do (Hunk, Hunk)
bnds <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> m (i, i)
getBounds Threshold s a
th
forall s a.
Hunk -> (Hunk, Hunk) -> Threshold s a -> ST s (Maybe Hunk)
myHelperBs Hunk
j (Hunk, Hunk)
bnds Threshold s a
th
myHelperBs :: Int -> (Int,Int) -> Threshold s a ->
ST s (Maybe Int)
myHelperBs :: forall s a.
Hunk -> (Hunk, Hunk) -> Threshold s a -> ST s (Maybe Hunk)
myHelperBs Hunk
j (Hunk
th_min,Hunk
th_max) Threshold s a
th =
if Hunk
th_max forall a. Num a => a -> a -> a
- Hunk
th_min forall a. Ord a => a -> a -> Bool
> Hunk
1 then do
(Hunk
midth, [a]
_) <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> m e
readArray Threshold s a
th Hunk
th_middle
if Hunk
j forall a. Ord a => a -> a -> Bool
> Hunk
midth
then forall s a.
Hunk -> (Hunk, Hunk) -> Threshold s a -> ST s (Maybe Hunk)
myHelperBs Hunk
j (Hunk
th_middle,Hunk
th_max) Threshold s a
th
else forall s a.
Hunk -> (Hunk, Hunk) -> Threshold s a -> ST s (Maybe Hunk)
myHelperBs Hunk
j (Hunk
th_min,Hunk
th_middle) Threshold s a
th
else do
(Hunk
minth, [a]
_) <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> m e
readArray Threshold s a
th Hunk
th_min
(Hunk
maxth, [a]
_) <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> m e
readArray Threshold s a
th Hunk
th_max
if Hunk
minth forall a. Ord a => a -> a -> Bool
< Hunk
j Bool -> Bool -> Bool
&& Hunk
maxth forall a. Ord a => a -> a -> Bool
> Hunk
j
then forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just Hunk
th_max
else if Hunk
j forall a. Ord a => a -> a -> Bool
< Hunk
minth then forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just Hunk
th_min
else forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
where th_middle :: Hunk
th_middle = (Hunk
th_maxforall a. Num a => a -> a -> a
+Hunk
th_min) forall a. Integral a => a -> a -> a
`div` Hunk
2
findMatches :: Ord a => [a] -> [a] -> [[Int]]
findMatches :: forall a. Ord a => [a] -> [a] -> [[Hunk]]
findMatches [] [] = []
findMatches [] (a
_:[a]
bs) = []forall a. a -> [a] -> [a]
: forall a. Ord a => [a] -> [a] -> [[Hunk]]
findMatches [] [a]
bs
findMatches [a]
_ [] = []
findMatches [a]
a [a]
b =
forall a. [(Hunk, [a])] -> [[a]]
unzipIndexed forall a b. (a -> b) -> a -> b
$ forall a. Ord a => [a] -> [a]
sort forall a b. (a -> b) -> a -> b
$ forall a.
Ord a =>
[(a, Hunk)] -> [(a, Hunk)] -> [a] -> [Hunk] -> [(Hunk, [Hunk])]
findSortedMatches [(a, Hunk)]
indexeda [(a, Hunk)]
indexedb [] []
where indexeda :: [(a, Hunk)]
indexeda = forall a. Ord a => [a] -> [a]
sort forall a b. (a -> b) -> a -> b
$ forall a b. [a] -> [b] -> [(a, b)]
zip [a]
a [Hunk
1..]
indexedb :: [(a, Hunk)]
indexedb = forall a. Ord a => [a] -> [a]
sort forall a b. (a -> b) -> a -> b
$ forall a b. [a] -> [b] -> [(a, b)]
zip [a]
b [Hunk
1..]
unzipIndexed :: [(Int,[a])] -> [[a]]
unzipIndexed :: forall a. [(Hunk, [a])] -> [[a]]
unzipIndexed [(Hunk, [a])]
s = forall {t} {a}. (Eq t, Num t) => t -> [(t, [a])] -> [[a]]
unzipIndexedHelper Hunk
1 [(Hunk, [a])]
s
where unzipIndexedHelper :: t -> [(t, [a])] -> [[a]]
unzipIndexedHelper t
_ [] = []
unzipIndexedHelper t
thisl ((t
l,[a]
c):[(t, [a])]
rest)
| t
thisl forall a. Eq a => a -> a -> Bool
== t
l = [a]
cforall a. a -> [a] -> [a]
: t -> [(t, [a])] -> [[a]]
unzipIndexedHelper (t
lforall a. Num a => a -> a -> a
+t
1) [(t, [a])]
rest
| Bool
otherwise = []forall a. a -> [a] -> [a]
: t -> [(t, [a])] -> [[a]]
unzipIndexedHelper (t
thislforall a. Num a => a -> a -> a
+t
1) ((t
l,[a]
c)forall a. a -> [a] -> [a]
:[(t, [a])]
rest)
findSortedMatches :: Ord a => [(a, Int)] -> [(a, Int)] -> [a] -> [Int]
-> [(Int, [Int])]
findSortedMatches :: forall a.
Ord a =>
[(a, Hunk)] -> [(a, Hunk)] -> [a] -> [Hunk] -> [(Hunk, [Hunk])]
findSortedMatches [] [(a, Hunk)]
_ [a]
_ [Hunk]
_ = []
findSortedMatches [(a, Hunk)]
_ [] [a]
_ [Hunk]
_ = []
findSortedMatches ((a
a,Hunk
na):[(a, Hunk)]
as) ((a
b,Hunk
nb):[(a, Hunk)]
bs) [a]
aold [Hunk]
aoldmatches
| [a
a] forall a. Eq a => a -> a -> Bool
== [a]
aold = (Hunk
na, [Hunk]
aoldmatches) forall a. a -> [a] -> [a]
:
forall a.
Ord a =>
[(a, Hunk)] -> [(a, Hunk)] -> [a] -> [Hunk] -> [(Hunk, [Hunk])]
findSortedMatches [(a, Hunk)]
as ((a
b,Hunk
nb)forall a. a -> [a] -> [a]
:[(a, Hunk)]
bs) [a]
aold [Hunk]
aoldmatches
| a
a forall a. Ord a => a -> a -> Bool
> a
b = forall a.
Ord a =>
[(a, Hunk)] -> [(a, Hunk)] -> [a] -> [Hunk] -> [(Hunk, [Hunk])]
findSortedMatches ((a
a,Hunk
na)forall a. a -> [a] -> [a]
:[(a, Hunk)]
as) [(a, Hunk)]
bs [a]
aold [Hunk]
aoldmatches
| a
a forall a. Ord a => a -> a -> Bool
< a
b = forall a.
Ord a =>
[(a, Hunk)] -> [(a, Hunk)] -> [a] -> [Hunk] -> [(Hunk, [Hunk])]
findSortedMatches [(a, Hunk)]
as ((a
b,Hunk
nb)forall a. a -> [a] -> [a]
:[(a, Hunk)]
bs) [a]
aold [Hunk]
aoldmatches
findSortedMatches ((a
a,Hunk
na):[(a, Hunk)]
as) [(a, Hunk)]
bs [a]
_ [Hunk]
_
= (Hunk
na, [Hunk]
matches) forall a. a -> [a] -> [a]
: forall a.
Ord a =>
[(a, Hunk)] -> [(a, Hunk)] -> [a] -> [Hunk] -> [(Hunk, [Hunk])]
findSortedMatches [(a, Hunk)]
as [(a, Hunk)]
bs [a
a] [Hunk]
matches
where matches :: [Hunk]
matches = forall a. [a] -> [a]
reverse forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
filter ((forall a. Eq a => a -> a -> Bool
==a
a) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> a
fst) [(a, Hunk)]
bs