package Ġjust 4 fun . kot link it . test Time List ĊĊĊ Ċ interface ĠList Element < E : ĠList Element < E >> : ĠComparable < E > Ġ{ Ċ ĉ val Ġexpires : ĠLong Ċ ĉ var Ġnext : ĠE ? Ċ ĉ override Ġfun Ġcompare To ( other : ĠE ): ĠInt Ġ= Ġexpires . compareTo ( other . expires ) Ċ } ĊĊ Ċ internal Ġobject ĠStub : ĠList Element < Stub > Ġ{ Ċ ĉ override Ġval Ġexpires : ĠLong Ġ= Ġ 0 Ċ ĉ override Ġvar Ġnext : ĠStub ? Ġ= Ġnull Ċ ĉ override Ġfun ĠtoString () Ġ= Ġ" Stub " Ċ } ĊĊ Ċ open Ġclass ĠTime List < E : ĠList Element < E >> Ġ{ Ċ ĉ private Ġvar Ġhead : ĠE ? Ġ= Ġnull Ċ ĉ private Ġvar Ġbookmark Ġ= ĠBook mark (@ Suppress (" UN CHECK ED _ CAST ") Ġ( Stub Ġas ĠE ), Ġ 0 , Ġnull ) Ċ ĉ // Ġmetrics Ċ ĉ private Ġvar Ġtotal Ġ= Ġ 0 Ċ ĉ // ĉ private Ġvar Ġstep Ġ= Ġ 1 Ċ ĉ private Ġvar Ġdefault Size Ġ= Ġ 2 0 // 3 Ċ ĉ private Ġvar Ġmin Total Ġ= Ġdefault Size Ġ* Ġdefault Size Ċ ĉ private Ġvar Ġprev Total Ġ= Ġ 0 Ċ ĉ private Ġvar Ġnext Total Ġ= Ġ 0 Ċ ĉ private Ġvar Ġreal Size Ġ= Ġ 0 Ċ ĉ private Ġvar Ġmin Size Ġ= Ġ 0 Ċ ĉ private Ġvar ĠmaxSize Ġ= Ġ 0 ĊĉĊ ĉ init Ġ{ Ċĉ ĉ set Metrics ( default Size ) Ċ ĉ } ĊĉĊ ĉ private Ġfun Ġupdate ( total Value : ĠInt ) Ġ{ Ċĉ ĉ total Ġ= Ġtotal Value Ċĉ ĉ if Ġ( total Ġ< Ġmin Total ) Ġreturn Ċĉ ĉ if Ġ( total Ġ>= Ġnext Total ) Ġset Metrics ( real Size Ġ+ Ġ 1 0 ) Ċĉ ĉ else Ġif Ġ( total Ġ<= Ġprev Total ) Ġset Metrics ( real Size Ġ- Ġ 1 0 ) Ċ ĉ } ĊĉĊ ĉ private Ġfun Ġre calc ( total Value : ĠInt ) Ġ{ Ċĉ ĉ total Ġ= Ġtotal Value Ċĉ ĉ val Ġnew Size Ġ= ĠStrict Math . sqrt ( total . toDouble ()). toInt () Ġ+ Ġ 1 Ċĉ ĉ set Metrics ( if Ġ( new Size Ġ> Ġdefault Size ) Ġnew Size Ġelse Ġdefault Size ) Ċ ĉ } ĊĉĊ ĉ private Ġfun Ġreset () Ġ{ Ċĉ ĉ total Ġ= Ġ 0 Ċĉ ĉ head Ġ= Ġnull Ċĉ ĉ bookmark . head Ġ= Ġ@ Suppress (" UN CHECK ED _ CAST ") Ġ( Stub Ġas ĠE ) Ċĉ ĉ bookmark . next Ġ= Ġnull Ċĉ ĉ bookmark . size Ġ= Ġ 0 Ċĉ ĉ set Metrics ( default Size ) Ċ ĉ } ĊĉĊ ĉ private Ġfun Ġset Metrics ( size : ĠInt ) Ġ{ Ċĉ ĉ real Size Ġ= Ġsize Ċĉ ĉ next Total Ġ= Ġ( size Ġ+ Ġ 1 ) Ġ* Ġ( size Ġ+ Ġ 1 ) Ċĉ ĉ prev Total Ġ= Ġ( size Ġ- Ġ 1 ) Ġ* Ġ( size Ġ- Ġ 1 ) Ċĉ ĉ min Size Ġ= Ġreal Size Ġ- Ġ 1 // Ġ 2 Ċĉ ĉ maxSize Ġ= Ġreal Size Ġ+ Ġ 1 //* Ġ 2 Ċĉ ĉ if Ġ( total Ġ> Ġ 0 ) Ġbookmark . aj ust Min Size ( null ) Ċ ĉ } ĊĉĊĉĊ ĉ fun Ġsize () Ġ= Ġtotal Ċ ĉ fun ĠisEmpty () Ġ= Ġtotal Ġ== Ġ 0 Ċ ĉ fun Ġnon Empty () Ġ= Ġtotal Ġ> Ġ 0 Ċ ĉ fun Ġhead () Ġ= Ġhead ĊĉĊ ĉ fun Ġadd ( e : ĠE ): ĠE Ġ{ Ċĉ ĉ update ( total Ġ+ Ġ 1 ) Ċĉ ĉ if Ġ( head Ġ== Ġnull ) Ġ{ Ċĉĉ ĉ head Ġ= Ġe Ċĉĉ ĉ bookmark . head Ġ= Ġe Ċĉĉ ĉ bookmark . size Ġ= Ġ 1 Ċĉ ĉ } Ġelse Ġif Ġ( e Ġ< Ġhead !! ) Ġ{ Ċĉĉ ĉ e . next Ġ= Ġhead Ċĉĉ ĉ head Ġ= Ġe Ċĉĉ ĉ bookmark . head Ġ= Ġe Ċĉĉ ĉ bookmark . size ++ Ċĉ ĉ } Ġelse Ġbookmark . add ( e , Ġnull ) Ċĉ ĉ return Ġe Ċ ĉ } ĊĉĊ ĉ fun Ġremove (): ĠE ? Ġ{ Ċĉ ĉ if Ġ( head Ġ== Ġnull ) Ġreturn Ġnull Ċĉ ĉ val Ġh Ġ= Ġhead !! Ċĉ ĉ if Ġ( h . next Ġ== Ġnull ) Ġreset () Ċĉ ĉ else Ġ{ Ċĉĉ ĉ update ( total Ġ- Ġ 1 ) Ċĉĉ ĉ head Ġ= Ġh . next Ċĉĉ ĉ bookmark . head Ġ= Ġhead !! Ċĉĉ ĉ bookmark . size -- Ċĉĉ ĉ h . next Ġ= Ġnull Ċĉĉ ĉ if Ġ( bookmark . size Ġ< Ġmin Size ) Ġbookmark . join ( null ) Ċĉ ĉ } Ċĉ ĉ return Ġh Ċ ĉ } ĊĉĊ ĉ fun Ġremove ( e : ĠE ): ĠBoolean Ġ{ Ċĉ ĉ return Ġif Ġ( head Ġ== Ġnull ) Ġfalse Ċĉ ĉ else Ġif Ġ( e Ġ=== Ġhead ) Ġ{ Ċĉĉ ĉ remove (); Ġtrue Ċĉ ĉ } Ġelse Ġif Ġ( bookmark . remove ( e , Ġnull )) Ġ{ Ċĉĉ ĉ update ( total Ġ- Ġ 1 ); Ġtrue Ċĉ ĉ } Ġelse Ġfalse Ċ ĉ } ĊĉĊ ĉ fun Ġremove After ( kill Time : ĠLong , Ġapply : Ġ( E ) Ġ-> ĠUnit ) Ġ{ Ċĉ ĉ if Ġ( head Ġ== Ġnull ) Ġreturn Ċĉ ĉ if Ġ( head !!. expires Ġ>= Ġkill Time ) Ġclear ( apply ) Ċĉ ĉ else Ġre calc ( bookmark . remove After ( kill Time , Ġnull , Ġapply )) Ċ ĉ } ĊĉĊ ĉ fun Ġclear ( apply : Ġ( E ) Ġ-> ĠUnit ): ĠUnit Ġ{ Ċĉ ĉ var Ġcurr Ġ= Ġhead Ċĉ ĉ while Ġ( curr Ġ!= Ġnull ) Ġ{ Ċĉĉ ĉ apply ( curr ) Ċĉĉ ĉ val Ġnext Ġ= Ġcurr . next Ċĉĉ ĉ curr . next Ġ= Ġnull Ċĉĉ ĉ curr Ġ= Ġnext Ċĉ ĉ } Ċĉ ĉ reset () Ċ ĉ } ĊĉĊ ĉ fun Ġto List (): ĠList < E > Ġ{ Ċĉ ĉ val Ġlist Ġ= Ġmutable ListOf < E >() Ċĉ ĉ var Ġcurr Ġ= Ġhead Ċĉ ĉ while Ġ( curr Ġ!= Ġnull ) Ġ{ Ċĉĉ ĉ list . add ( curr ) Ċĉĉ ĉ curr Ġ= Ġcurr . next Ċĉ ĉ } Ċĉ ĉ return Ġlist Ċ ĉ } ĊĉĊ ĉ fun Ġdump (): ĠString Ġ{ Ċĉ ĉ val Ġbuf Ġ= ĠStringBuilder ("$ prev Total <$ total <$ next Total :$ real Size Ġ Ġ") Ċĉ ĉ var Ġbo om : ĠBook mark ? Ġ= Ġbookmark Ċĉ ĉ var Ġcur : ĠE ? Ġ= Ġbo om !!. head Ċĉ ĉ var Ġcur 2 : ĠE ? Ġ= Ġbo om !!. head Ċĉ ĉ while Ġ( boom Ġ!= Ġnull Ġ&& Ġcur Ġ!= Ġnull ) Ġ{ Ċĉĉ ĉ buf . append ("[ ") Ċĉĉ ĉ // ĉĉ ĉ buf . append ("[ ${ boom . size }> ") Ċĉĉ ĉ for Ġ( n Ġin Ġ 0 Ġuntil Ġbo om . size ) Ġ{ Ċĉĉĉ ĉ if Ġ( n Ġ> Ġ 0 ) Ġbuf . append (",") Ċĉĉĉ ĉ buf . append ( cur ) Ċĉĉĉ ĉ if Ġ( cur Ġ!== Ġcur 2 ) Ġbuf . append (" ($ cur 2 )") Ċĉĉĉ ĉ cur Ġ= Ġcur ?. next Ċĉĉĉ ĉ cur 2 Ġ= Ġcur 2 ?. next Ċĉĉ ĉ } Ċĉĉ ĉ buf . append (" ]") Ċĉĉ ĉ boom Ġ= Ġbo om . next Ċĉĉ ĉ cur Ġ= Ġbo om ?. head Ċĉĉ ĉ if Ġ(( boom Ġ== Ġnull Ġ|| Ġcur Ġ== Ġnull ) Ġ&& Ġcur Ġ!== Ġcur 2 ) Ġbuf . append (" ($ cur 2 )") Ċĉ ĉ } Ċĉ ĉ return Ġbuf . toString () Ċ ĉ } ĊĉĊĉ ĊĉĊĉĊ ĉ /* ĠBO OK MARK Ġ*/ ĊĉĊ ĉ inner Ġclass ĠBook mark ( var Ġhead : ĠE , Ġvar Ġsize : ĠInt , Ġvar Ġnext : ĠBook mark ?) Ġ{ ĊĉĉĊĉ ĉ fun Ġadd ( e : ĠE , Ġprev B mk : ĠBook mark ?) Ġ{ Ċĉĉ ĉ val Ġnext Ġ= Ġnext Ċĉĉ ĉ if Ġ( next Ġ!= Ġnull Ġ&& Ġnext . head Ġ<= Ġe ) Ġreturn Ġnext . add ( e , Ġthis ) Ċĉĉ ĉ // ĉ else Ċĉĉ ĉ size ++ Ċĉĉ ĉ val Ġexpires Ġ= Ġe . expires Ċĉĉ ĉ if Ġ( size Ġ<= ĠmaxSize ) Ġ{ Ċĉĉĉ ĉ val Ġcur Ġ= Ġunless Next ( head ) Ġ{ Ġit . expires Ġ> Ġexpires Ġ} Ċĉĉĉ ĉ e . next Ġ= Ġcur . next ; Ġcur . next Ġ= Ġe Ċĉĉ ĉ } Ġelse Ġ{ Ċĉĉĉ ĉ val Ġmid Ġ= Ġsize Ġ/ Ġ 2 Ċĉĉĉ ĉ var Ġindex Ġ= Ġ 0 Ċĉĉĉ ĉ var Ġcur Ġ= Ġunless Next ( head , Ġ{ Ġif Ġ(++ index Ġ== Ġmid ) Ġsplit ( it , Ġmid ) Ġ}) Ġ{ Ġit . expires Ġ> Ġexpires Ġ} Ċĉĉĉ ĉ e . next Ġ= Ġcur . next ; Ġcur . next Ġ= Ġe Ċĉĉĉ ĉ if Ġ( index Ġ< Ġmid ) Ġ{ Ċĉĉĉĉ ĉ while Ġ(++ index Ġ< Ġmid ) Ġcur Ġ= Ġcur . next !! Ċĉĉĉĉ ĉ split ( cur . next !! , Ġmid ) Ċĉĉĉ ĉ } Ċĉĉ ĉ } Ċĉ ĉ } ĊĉĉĊĉ ĉ fun Ġremove ( e : ĠE , Ġprev B mk : ĠBook mark ?): ĠBoolean Ġ{ Ċĉĉ ĉ val Ġnext Ġ= Ġnext Ċĉĉ ĉ if Ġ( next Ġ!= Ġnull Ġ&& Ġnext . head Ġ< Ġe ) Ġreturn Ġnext . remove ( e , Ġthis ) Ċĉĉ ĉ // ĉ else Ċĉĉ ĉ val Ġexpires Ġ= Ġe . expires Ċĉĉ ĉ // Ġfind Ġbeginning Ġof Ġequal Ġ' run Time Ns ' Ċĉĉ ĉ var Ġcur Ġ= Ġunless Next ( head ) Ġ{ Ġit . expires Ġ>= Ġexpires Ġ} Ċĉĉ ĉ if Ġ( cur . next Ġ== Ġnull Ġ|| Ġcur . next !!. expires Ġ> Ġexpires ) Ġreturn Ġfalse Ċĉĉ ĉ // Ġbeginning Ġof Ġequal Ġ' run Time Ns ' Ċĉĉ ĉ val Ġnext Head Ġ= Ġnext ?. head Ċĉĉ ĉ if Ġ( next Head Ġ!= Ġnull Ġ&& Ġnext Head . expires Ġ== Ġexpires ) Ġ{ Ċĉĉĉ ĉ // Ġequal Ġ' run Time Ns ' Ġcontinue Ġto Ġnext Ġhead Ċĉĉĉ ĉ cur Ġ= Ġunless Next ( cur ) Ġ{ Ġit Ġ=== Ġnext Head Ġ|| Ġit Ġ=== Ġe Ġ} Ċĉĉĉ ĉ if Ġ( cur . next Ġ=== Ġnext Head ) Ġreturn Ġif Ġ( next Head Ġ=== Ġe ) Ġnext !!. remove Head ( cur , Ġthis ) Ġelse Ġnext !!. remove ( e , Ġthis ) Ċĉĉ ĉ } Ġelse Ġ{ Ċĉĉĉ ĉ // Ġequal Ġ' run Time Ns ' Ġbut Ġless Ġthan Ġnext Ġhead Ċĉĉĉ ĉ cur Ġ= Ġunless Next ( cur ) Ġ{ Ġit . expires Ġ!= Ġexpires Ġ|| Ġit Ġ=== Ġe Ġ} Ċĉĉĉ ĉ if Ġ( cur . next Ġ== Ġnull Ġ|| Ġcur . next !!. expires Ġ> Ġexpires ) Ġreturn Ġfalse Ċĉĉ ĉ } Ċĉĉ ĉ cur . next Ġ= Ġe . next Ċĉĉ ĉ e . next Ġ= Ġnull Ċĉĉ ĉ size -- Ċĉĉ ĉ if Ġ( size Ġ< Ġmin Size ) Ġjoin ( prev B mk ) Ċĉĉ ĉ return Ġtrue Ċĉ ĉ } ĊĉĉĊĉ ĉ fun Ġremove Head ( prev : ĠE , Ġprev B mk : ĠBook mark ): ĠBoolean Ġ{ Ċĉĉ ĉ val Ġnew Head Ġ= Ġhead . next Ċĉĉ ĉ prev . next Ġ= Ġnew Head Ċĉĉ ĉ if Ġ( new Head Ġ== Ġnull ) Ġprev B mk . next Ġ= Ġnext Ċĉĉ ĉ else Ġ{ Ċĉĉĉ ĉ head . next Ġ= Ġnull Ċĉĉĉ ĉ head Ġ= Ġnew Head Ċĉĉĉ ĉ size -- Ċĉĉĉ ĉ if Ġ( size Ġ< Ġmin Size ) Ġjoin ( prev B mk ) Ċĉĉ ĉ } Ċĉĉ ĉ return Ġtrue Ċĉ ĉ } ĊĉĉĊĉ ĉ fun Ġremove After ( kill Time : ĠLong , Ġprev B mk : ĠBook mark ?, Ġapply : Ġ( E ) Ġ-> ĠUnit ): ĠInt Ġ{ Ċĉĉ ĉ val Ġnext Ġ= Ġnext Ċĉĉ ĉ if Ġ( next Ġ!= Ġnull Ġ&& Ġnext . head . expires Ġ< Ġkill Time ) Ġreturn Ġsize Ġ+ Ġnext . remove After ( kill Time , Ġthis , Ġapply ) Ċĉĉ ĉ // ĉ else Ċĉĉ ĉ size Ġ= Ġ 1 Ċĉĉ ĉ this . next Ġ= Ġnull Ċĉĉ ĉ val Ġprev Ġ= Ġunless Next ( head , Ġ{ Ġsize ++ Ġ}) Ġ{ Ġit . expires Ġ>= Ġkill Time Ġ} Ċĉĉ ĉ var Ġcur Ġ= Ġprev . next Ċĉĉ ĉ prev . next Ġ= Ġnull Ċĉĉ ĉ while Ġ( cur Ġ!= Ġnull ) Ġ{ Ċĉĉĉ ĉ apply ( cur ) Ċĉĉĉ ĉ val Ġnext Ġ= Ġcur . next Ċĉĉĉ ĉ cur . next Ġ= Ġnull Ċĉĉĉ ĉ cur Ġ= Ġnext Ċĉĉ ĉ } Ċĉĉ ĉ return Ġsize Ċĉ ĉ } ĊĉĉĊĉ ĉ inline Ġfun Ġunless Next ( initial : ĠE , Ġexit Cond : Ġ( next : ĠE ) Ġ-> ĠBoolean ): ĠE Ġ{ Ċĉĉ ĉ var Ġcur Ġ= Ġinitial Ċĉĉ ĉ while Ġ( cur . next Ġ!= Ġnull Ġ&& Ġ! exit Cond ( cur . next !! )) Ġcur Ġ= Ġcur . next !! Ċĉĉ ĉ return Ġcur Ċĉ ĉ } ĊĉĉĊĉ ĉ inline Ġfun Ġunless Next ( initial : ĠE , Ġcond Body : Ġ( next : ĠE ) Ġ-> ĠUnit , Ġexit Cond : Ġ( next : ĠE ) Ġ-> ĠBoolean ): ĠE Ġ{ Ċĉĉ ĉ var Ġcur Ġ= Ġinitial Ċĉĉ ĉ while Ġ( cur . next Ġ!= Ġnull Ġ&& Ġ! exit Cond ( cur . next !! )) Ġ{ Ċĉĉĉ ĉ cond Body ( cur . next !! ) Ċĉĉĉ ĉ cur Ġ= Ġcur . next !! Ċĉĉ ĉ } Ċĉĉ ĉ return Ġcur Ċĉ ĉ } ĊĉĉĊĉ ĉ fun Ġjoin ( prev B mk : ĠBook mark ?): ĠBook mark ? Ġ{ Ċĉĉ ĉ if Ġ( next Ġ== Ġnull ) Ġreturn Ġnull Ċĉĉ ĉ val Ġcur Ġ= Ġif Ġ( prev B mk Ġ== Ġnull Ġ|| Ġprev B mk . size Ġ> Ġnext !!. size ) Ġthis Ġelse Ġprev B mk Ċĉĉ ĉ cur . size Ġ+= Ġcur . next !!. size Ċĉĉ ĉ cur . next Ġ= Ġcur . next !!. next Ċĉĉ ĉ return Ġcur . next Ċĉ ĉ } ĊĉĉĊĉ ĉ fun Ġsplit ( e : ĠE , Ġindex : ĠInt ) Ġ{ Ċĉĉ ĉ next Ġ= ĠBook mark ( e , Ġsize Ġ- Ġindex , Ġnext ) Ċĉĉ ĉ size Ġ= Ġindex Ċĉ ĉ } ĊĉĉĊĉ ĉ fun Ġa just Min Size ( prev B mk : ĠBook mark ?) Ġ{ Ċĉĉ ĉ val Ġn xt Ġ= Ġif Ġ( size Ġ< Ġmin Size ) Ġjoin ( prev B mk ) Ġelse Ġnext Ċĉĉ ĉ nxt ?. aj ust Min Size ( this ) Ċĉ ĉ } Ċ ĉ } Ċ } Ċ