package Ġdev . f rit z 2 . utils Ċ Ċ import Ġdev . f rit z 2 . binding . Patch Ċ import Ġdev . f rit z 2 . l enses . Id Provider Ċ import Ġkotlinx . coroutines . flow . Flow Ċ Ċ /** Ċ Ġ* ĠImplementation Ġof ĠMy er 's Ġdiff Ġalgorithm Ġon Ġtwo Ġ[ List ] s Ġcreating Ġa Ġ[ Flow ] Ġof Ġ[ Patch ] es . Ċ Ġ*/ Ċ object ĠMy er Ġ{ ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġdiffs Ġto Ġversions Ġof Ġa Ġ[ List ] Ġby Ġproviding Ġan Ġ[ Id Provider ]. ĊĠĠĠĠ Ġ* ĠThe Ġdefinition Ġof Ġan Ġid Ġto Ġidentify Ġthe Ġsame Ġobject Ġin Ġboth Ġ[ List ] s Ġmakes Ġit Ġpossible Ġto Ġdetect , ĊĠĠĠĠ Ġ* Ġif Ġan Ġobject Ġis Ġmoved Ġfrom Ġone Ġposition Ġto Ġanother . ĊĠĠĠĠ Ġ* ĠAlso Ġthis Ġmethod Ġdoes Ġnot Ġemit Ġa Ġ[ Patch ] Ġif Ġvalues Ġwithin Ġan Ġelement Ġchange . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġold List Ġold Ġversion Ġof Ġthe Ġ[ List ] ĊĠĠĠĠ Ġ* Ġ@ param Ġnew List Ġnew Ġversion Ġof Ġthe Ġ[ List ] ĊĠĠĠĠ Ġ* Ġ@ return Ġa Ġ[ List ] Ġof Ġ[ Patch ] es Ġneeded Ġto Ġtransform Ġthe Ġold Ġlist Ġinto Ġthe Ġnew Ġone ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġ< T , ĠI > Ġdiff ( old List : ĠList < T >, Ġnew List : ĠList < T >, Ġid Provider : ĠId Provider < T , ĠI >): ĠList < Patch < T >> Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġis Same Ġ= Ġ{ Ġa : ĠT , Ġb : ĠT Ġ-> Ġid Provider ( a ) Ġ== Ġid Provider ( b ) Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġtrace Ġ= Ġshortest Edit ( old List , Ġnew List , Ġis Same ) ĊĠĠĠĠĠĠĠ Ġreturn Ġbuild List Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġback track < T >( trace , Ġold List , Ġnew List , Ġis Same ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġdiffs Ġto Ġversions Ġof Ġa Ġ[ List ] Ġwith Ġan Ġ[ Id Provider ]. ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġold List Ġold Ġversion Ġof Ġthe Ġ[ List ] ĊĠĠĠĠ Ġ* Ġ@ param Ġnew List Ġnew Ġversion Ġof Ġthe Ġ[ List ] ĊĠĠĠĠ Ġ* Ġ@ return Ġa Ġ[ List ] Ġof Ġ[ Patch ] es Ġneeded Ġto Ġtransform Ġthe Ġold Ġlist Ġinto Ġthe Ġnew Ġone ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġ< T > Ġdiff ( old List : ĠList < T >, Ġnew List : ĠList < T >): ĠList < Patch < T >> Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġis Same Ġ= Ġ{ Ġa : ĠT , Ġb : ĠT Ġ-> Ġa Ġ== Ġb Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġtrace Ġ= Ġshortest Edit ( old List , Ġnew List , Ġis Same ) ĊĠĠĠĠĠĠĠ Ġreturn Ġbuild List Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġback track < T >( trace , Ġold List , Ġnew List , Ġis Same ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġinline Ġfun Ġ< T > ĠMutable List < Patch < T >> . back track ( ĊĠĠĠĠĠĠĠ Ġtrace : ĠList < Circular Array >, ĊĠĠĠĠĠĠĠ Ġold List : ĠList < T >, ĊĠĠĠĠĠĠĠ Ġnew List : ĠList < T >, ĊĠĠĠĠĠĠĠ Ġis Same : Ġ( a : ĠT , Ġb : ĠT ) Ġ-> ĠBoolean ĊĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġx Ġ= Ġold List . size ĊĠĠĠĠĠĠĠ Ġvar Ġy Ġ= Ġnew List . size ĊĊĠĠĠĠĠĠĠ Ġvar Ġlast Patch : ĠPatch < T >? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġfor Ġ(( d , Ġv ) Ġin Ġtrace . with Index (). reversed ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġk Ġ= Ġx Ġ- Ġy ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġprev K Ġ= Ġif Ġ( k Ġ== Ġ- d Ġ|| Ġ( k Ġ!= Ġd Ġ&& Ġv . get ( k Ġ- Ġ 1 ) Ġ< Ġv . get ( k Ġ+ Ġ 1 ))) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġk Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġk Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġprev X Ġ= Ġv . get ( prev K ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġprev Y Ġ= Ġprev X Ġ- Ġprev K ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( x Ġ> Ġprev X Ġ&& Ġy Ġ> Ġprev Y ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx Ġ-= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġy Ġ-= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( d Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( prev X Ġ< Ġx ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġelement Ġ= Ġold List [ prev X ] ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġtry Ġto Ġcombine ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( last Patch Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcombine Ġadjacent Ġdeletes ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( last Patch Ġis ĠPatch . Delete Ġ&& Ġlast Patch . start Ġ== Ġprev X Ġ+ Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Patch Ġ= ĠPatch . Delete ( prev X , Ġlast Patch . count Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcombine Ġdirectly Ġfollowing Ġinsert Ġand Ġdelete Ġof Ġsame Ġelement Ġas Ġmove ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġif Ġ( last Patch Ġis ĠPatch . Insert Ġ&& Ġis Same ( last Patch . element , Ġelement )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Patch Ġ= ĠPatch . Move ( prev X , Ġlast Patch . index ) Ġ// Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadd ( last Patch ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Patch Ġ= ĠPatch . Delete ( prev X , Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// nothing Ġthere Ġto Ġcombine ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Patch Ġ= ĠPatch . Delete ( prev X , Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( prev Y Ġ< Ġy ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġelement Ġ= Ġnew List [ prev Y ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġx ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġtry Ġto Ġcombine ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( last Patch Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcombine Ġadjacent Ġinserts ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( last Patch Ġis ĠPatch . Insert Ġ&& Ġlast Patch . index Ġ== Ġindex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// turn Ġoder Ġof Ġelements ! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Patch Ġ= ĠPatch . Insert Many ( listOf ( last Patch . element , Ġelement ), Ġlast Patch . index ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( last Patch Ġis ĠPatch . Insert Many Ġ&& Ġlast Patch . index Ġ== Ġindex ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// turn Ġoder Ġof Ġelements ! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Patch Ġ= ĠPatch . Insert Many ( last Patch . elements Ġ+ Ġelement , Ġlast Patch . index ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcombine Ġdirectly Ġfollowing Ġinsert Ġand Ġdelete Ġof Ġsame Ġelement Ġas Ġmove ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġif Ġ( last Patch Ġis ĠPatch . Delete Ġ&& Ġlast Patch . count Ġ== Ġ 1 Ġ&& Ġis Same ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold List [ last Patch . start ], ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelement ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Patch Ġ= ĠPatch . Move ( last Patch . start , Ġindex ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadd ( last Patch ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Patch Ġ= ĠPatch . Insert ( element , Ġx ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// nothing Ġthere Ġto Ġcombine ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlast Patch Ġ= ĠPatch . Insert ( element , Ġx ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġx Ġ= Ġprev X ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy Ġ= Ġprev Y ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( last Patch Ġ!= Ġnull ) Ġadd ( last Patch ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġinline Ġfun Ġ< T > Ġshortest Edit ( ĊĠĠĠĠĠĠĠ Ġold List : ĠList < T >, ĊĠĠĠĠĠĠĠ Ġnew List : ĠList < T >, ĊĠĠĠĠĠĠĠ Ġis Same : Ġ( a : ĠT , Ġb : ĠT ) Ġ-> ĠBoolean ĊĠĠĠ Ġ): ĠList < Circular Array > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmax Ġ= Ġold List . size Ġ+ Ġnew List . size ĊĊĠĠĠĠĠĠĠ Ġ// init Ġarray ĊĠĠĠĠĠĠĠ Ġval Ġv Ġ= ĠCircular Array ( max ) ĊĠĠĠĠĠĠĠ Ġv . set ( 1 , Ġ 0 ) ĊĊĠĠĠĠĠĠĠ Ġreturn Ġbuild List Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġouter Loop @ Ġfor Ġ( d Ġin Ġ 0 .. max ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadd ( v . copyOf ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( k Ġin Ġ- d .. d Ġstep Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// walk Ġright Ġor Ġdown ? ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġx Ġ= Ġif Ġ(( k Ġ== Ġ- d ) Ġ|| Ġ( k Ġ!= Ġd Ġ&& Ġv . get ( k Ġ- Ġ 1 ) Ġ< Ġv . get ( k Ġ+ Ġ 1 ))) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġv . get ( k Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġv . get ( k Ġ- Ġ 1 ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġy Ġ= Ġx Ġ- Ġk ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// walk Ġdiagonal Ġis Ġpossible Ġas Ġfar Ġas Ġpossible ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( x Ġ< Ġold List . size Ġ&& Ġy Ġ< Ġnew List . size Ġ&& Ġis Same ( old List [ x ], Ġnew List [ y ])) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx Ġ+= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġy Ġ+= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġv . set ( k , Ġx ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( x Ġ>= Ġold List . size Ġ&& Ġy Ġ>= Ġnew List . size ) Ġbreak @ outer Loop ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġ} Ċ } Ċ Ċ internal Ġclass ĠCircular Array ( private Ġval Ġmax : ĠInt , Ġprivate Ġval Ġbuffer : ĠInt Array Ġ= ĠInt Array ( 2 Ġ* Ġmax Ġ+ Ġ 1 )) Ġ{ ĊĠĠĠ Ġfun Ġget ( index : ĠInt ) Ġ= Ġbuffer [ index Ġ+ Ġmax ] ĊĠĠĠ Ġfun Ġset ( index : ĠInt , Ġvalue : ĠInt ) Ġ= Ġbuffer . set ( index Ġ+ Ġmax , Ġvalue ) ĊĊĠĠĠ Ġfun Ġcopy Of (): ĠCircular Array Ġ= ĠCircular Array ( max , Ġbuffer . copyOf ()) ĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġbuffer . toString () ĊĠĠĠ Ġ} Ċ } Ċ