package Ġkui Ċ Ċ internal Ġfun Ġ< T > Ġdiff ( first : ĠList < T >, Ġsecond : ĠList < T >, Ġeq : Ġ( T , ĠT ) Ġ-> ĠBoolean Ġ= Ġ{ Ġx , Ġy Ġ-> Ġx Ġ== Ġy Ġ}): ĠList < Diff < T >> Ġ{ ĊĠĠĠ Ġval Ġa Ġ= Ġfirst . as Re versed () ĊĠĠĠ Ġval Ġb Ġ= Ġsecond . as Re versed () ĊĠĠĠ Ġval Ġmat Ġ= ĠArray ( a . size ) Ġ{ ĠInt Array ( b . size ) Ġ} ĊĠĠĠ Ġval Ġpts Ġ= ĠArray ( a . size ) Ġ{ Ġ_ Ġ-> ĠArray ( b . size ) Ġ{ ĠPtr . EMPTY Ġ} Ġ} ĊĊĠĠĠ Ġfun Ġmat ( ai : ĠInt , Ġbi : ĠInt ): ĠInt Ġ= Ġif Ġ( ai Ġ< Ġ 0 Ġ|| Ġbi Ġ< Ġ 0 ) Ġ 0 Ġelse Ġmat [ ai ][ bi ] ĊĊĠĠĠ Ġ// Ġbuild Ġmatrix ĊĠĠĠ Ġfor Ġ(( ai , Ġbi ) Ġin Ġa . indices Ġproduct Ġb . indices ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif ( eq ( a [ ai ], Ġb [ bi ])) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmat [ ai ][ bi ] Ġ= Ġmat ( ai Ġ- Ġ 1 , Ġbi Ġ- Ġ 1 ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpts [ ai ][ bi ] Ġ= ĠPtr . DIAG ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġleft Ġ= Ġmat ( ai Ġ- Ġ 1 , Ġbi ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġup Ġ= Ġmat ( ai , Ġbi Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( left Ġ>= Ġup ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmat [ ai ][ bi ] Ġ= Ġleft ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpts [ ai ][ bi ] Ġ= ĠPtr . LEFT ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmat [ ai ][ bi ] Ġ= Ġup ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpts [ ai ][ bi ] Ġ= ĠPtr . UP ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġback track ĊĠĠĠ Ġval Ġresult Ġ= Ġmutable ListOf < Diff < T >>() ĊĊĠĠĠ Ġvar Ġai Ġ= Ġa . last Index ĊĠĠĠ Ġvar Ġbi Ġ= Ġb . last Index ĊĠĠĠ Ġwhile ( ai Ġ>= Ġ 0 Ġ&& Ġbi Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġwhen ( pts [ ai ][ bi ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠPtr . DIAG Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( Un changed ( a [ ai ], Ġb [ bi ])) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġai -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbi -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠPtr . LEFT Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( Removed ( a [ ai ])) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġai -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠPtr . UP Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( Added ( b [ bi ])) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbi -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠPtr . EMPTY Ġ-> Ġerror (" un filled Ġmatrix Ġ$ ai Ġ$ bi ") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġwhile Ġ( ai Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġresult . add ( Removed ( a [ ai ])) ĊĠĠĠĠĠĠĠ Ġai -- ĊĠĠĠ Ġ} ĊĠĠĠ Ġwhile Ġ( bi Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġresult . add ( Added ( b [ bi ])) ĊĠĠĠĠĠĠĠ Ġbi -- ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġresult Ċ } Ċ Ċ internal Ġenum Ġclass ĠPtr Ġ{ ĠEMPTY , ĠUP , ĠLEFT , ĠDI AG Ġ} Ċ Ċ internal Ġsealed Ġclass ĠDiff < T > Ċ internal Ġdata Ġclass ĠAdded < T >( val Ġnew : ĠT ) Ġ: ĠDiff < T >() Ċ internal Ġdata Ġclass ĠRemoved < T >( val Ġold : ĠT ) Ġ: ĠDiff < T >() Ċ internal Ġdata Ġclass ĠUn changed < T >( val Ġold : ĠT , Ġval Ġnew : ĠT ) Ġ: ĠDiff < T >() Ċ Ċ internal Ġin fix Ġfun Ġ< T , ĠU > ĠIterable < T >. product ( that : ĠIterable < U >): ĠList < Pair < T , ĠU >> Ġ{ ĊĠĠĠ Ġval Ġresult Ġ= Ġmutable ListOf < Pair < T , ĠU >>() ĊĠĠĠ Ġfor Ġ( t Ġin Ġthis ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( u Ġin Ġthat ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( t Ġto Ġu ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġresult Ċ } Ċ