package Ġfr . ac in q . phoenix . utils Ċ Ċ /** Ċ Ġ* ĠThe ĠCache Ġimplements Ġa Ġsimple Ġstrict Ġcache . Ċ Ġ* Ċ Ġ* ĠIt Ġmonitor s Ġusage Ġ( both Ġgets Ġ& Ġputs ) Ġso Ġthat Ġe viction Ġis Ġproperly Ġordered . Ċ Ġ* Ċ Ġ* ĠFor Ġexample : Ċ Ġ* ĠIf Ġyou Ġset Ġa Ġsize Limit Ġof Ġ 4 , Ġthen Ġwhen Ġyou Ġadd Ġthe Ġ 5 th Ġitem Ġto Ġthe Ġcache , Ċ Ġ* Ġanother Ġitem Ġis Ġautomatically Ġev ict ed . Ċ Ġ* Ċ Ġ* ĠWhich Ġitem Ġgets Ġev ict ed Ġdepends Ġentirely Ġon Ġusage . Ċ Ġ* ĠThe ĠCache Ġmaintains Ġa Ġdoub ly Ġlinked - list Ġof Ġitems Ġordered Ġby Ġaccess . Ċ Ġ* ĠThe Ġmost Ġrecently Ġaccessed Ġitem Ġis Ġat Ġthe Ġfront Ġof Ġthe Ġlinked - list , Ċ Ġ* Ġand Ġthe Ġleast Ġrecently Ġaccessed Ġitem Ġis Ġat Ġthe Ġback . Ċ Ġ* ĠSo Ġit 's Ġvery Ġquick Ġand Ġefficient Ġto Ġev ict Ġitems Ġbased Ġon Ġrecent Ġusage . Ċ Ġ* ĠIt 's Ġalso Ġefficient Ġto Ġupdate Ġthe Ġlinked - list Ġduring Ġusage . Ċ Ġ*/ Ċ class ĠCache < Key , ĠValue >( size Limit : ĠInt ) Ġ{ ĊĊĠĠĠ Ġprivate Ġclass ĠCache Item < Key , ĠValue >( ĊĠĠĠĠĠĠĠ Ġvar Ġkey : ĠKey , ĊĠĠĠĠĠĠĠ Ġvar Ġvalue : ĠValue ĊĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġprev : ĠCache Item < Key , ĠValue >? Ġ= Ġnull Ġ// Ġlinked - list Ġpointer ĊĠĠĠĠĠĠĠ Ġvar Ġnext : ĠCache Item < Key , ĠValue >? Ġ= Ġnull Ġ// Ġlinked - list Ġpointer ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġvar Ġ_ size Limit : ĠInt ĊĠĠĠ Ġprivate Ġvar Ġ_ map : ĠMutable Map < Key , ĠCache Item < Key , ĠValue >> ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġ_ size Limit Ġ= Ġsize Limit ĊĠĠĠĠĠĠĠ Ġ_ map Ġ= Ġmutable Map Of () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠPointer s Ġto Ġfront Ġ& Ġback Ġof Ġlinked - list ĊĠĠĠ Ġprivate Ġvar Ġmost Recent Cache Item : ĠCache Item < Key , ĠValue >? Ġ= Ġnull ĊĠĠĠ Ġprivate Ġvar Ġleast Recent Cache Item : ĠCache Item < Key , ĠValue >? Ġ= Ġnull ĊĊĠĠĠ Ġval Ġsize : ĠInt Ġget () Ġ= Ġ_ map . size ĊĊĠĠĠ Ġvar Ġsize Limit : ĠInt ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġ_ size Limit ĊĠĠĠĠĠĠĠ Ġset ( newValue ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(_ size Limit Ġ== ĠnewValue ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ// Ġno Ġchanges ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ size Limit Ġ= ĠnewValue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(_ size Limit Ġ> Ġ 0 ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ(_ map . size Ġ> Ġ_ size Limit ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠTo Ġget Ġto Ġthis Ġcode Ġbranch : ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ- Ġ_ count Limit Ġ> Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ- Ġ_ dict . size Ġ> Ġ_ count Limit ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThus : Ġ_ dict . size Ġ>= Ġ 2 , Ġmeaning : ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ- Ġleast Recent Cache Item Ġis Ġnon - null ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ- Ġleast Recent Cache Item . prev Ġis Ġnon - null ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġkey To Ev ict Ġ= Ġleast Recent Cache Item !!. key ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleast Recent Cache Item Ġ= Ġleast Recent Cache Item ?. prev ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleast Recent Cache Item ?. next Ġ= Ġnull ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ_ map . remove ( key To Ev ict ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġ// Ġ</ var Ġsize Limit : ĠInt > ĊĊĠĠĠ Ġfun Ġis Un limited (): ĠBoolean Ġ= Ġ_ size Limit Ġ<= Ġ 0 ĊĠĠĠ Ġfun ĠisEmpty (): ĠBoolean Ġ= Ġ_ map . isEmpty () ĊĠĠĠ Ġfun Ġcontains Key ( key : ĠKey ): ĠBoolean Ġ= Ġ_ map . containsKey ( key ) ĊĊĠĠĠ Ġoperator Ġfun Ġget ( key : ĠKey ): ĠValue ? Ġ{ ĊĊĠĠĠĠĠĠĠ Ġreturn Ġ_ map [ key ]?. let Ġ{ Ġitem Ġ-> ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( item Ġ!== Ġmost Recent Cache Item ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRemove Ġitem Ġfrom Ġcurrent Ġposition Ġin Ġlinked - list . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠSince Ġitem Ġis Ġnon - null , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġknow Ġthere 's Ġa Ġvalid Ġmost Recent Cache Item Ġ& Ġleast Recent Cache Item . ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem . prev ?. next Ġ= Ġitem . next ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( item Ġ=== Ġleast Recent Cache Item ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠWe Ġknow Ġthe Ġitem Ġis ĠNOT Ġthe Ġmost Recent Cache Item . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠWe Ġknow Ġthe Ġitem ĠIS Ġthe Ġleast Recent Cache Item . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThus : Ġthere Ġare Ġat Ġleast Ġ 2 Ġitems Ġin Ġthe Ġlist ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleast Recent Cache Item Ġ= Ġitem . prev ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠWe Ġknow Ġthe Ġitem Ġis ĠNOT Ġthe Ġmost Recent Cache Item . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠWe Ġknow Ġthe Ġitem Ġis ĠNOT Ġthe Ġleast Recent Cache Item . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThus : Ġthere Ġare Ġat Ġleast Ġ 3 Ġitems Ġin Ġthe Ġlist ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem . next ?. prev Ġ= Ġitem . prev ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠMove Ġitem Ġto Ġbeginning Ġof Ġlinked - list ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem . prev Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem . next Ġ= Ġmost Recent Cache Item ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmost Recent Cache Item ?. prev Ġ= Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmost Recent Cache Item Ġ= Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġitem . value ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoperator Ġfun Ġset ( key : ĠKey , Ġvalue : ĠValue ): ĠUnit Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġexisting Item Ġ= Ġ_ map [ key ] ĊĠĠĠĠĠĠĠ Ġif Ġ( existing Item Ġ!= Ġnull ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠUpdate Ġitem Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġexisting Item . value Ġ= Ġvalue ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( existing Item Ġ!== Ġmost Recent Cache Item ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRemove Ġitem Ġfrom Ġcurrent Ġposition Ġin Ġlinked - list ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠNotes : ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠWe Ġfetched Ġthe Ġitem Ġfrom Ġthe Ġlist , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġso Ġwe Ġknow Ġthere 's Ġa Ġvalid Ġmost Recent Cache Item Ġ& Ġleast Recent Cache Item . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠFurthermore , Ġwe Ġknow Ġthe Ġitem Ġisn 't Ġthe Ġmost Recent Cache Item . ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexisting Item . prev ?. next Ġ= Ġexisting Item . next ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( existing Item Ġ=== Ġleast Recent Cache Item ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠWe Ġknow Ġthe Ġitem Ġis ĠNOT Ġthe Ġmost Recent Cache Item . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠWe Ġknow Ġthe Ġitem ĠIS Ġthe Ġleast Recent Cache Item . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThus : Ġthere Ġare Ġat Ġleast Ġ 2 Ġitems Ġin Ġthe Ġlist ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleast Recent Cache Item Ġ= Ġexisting Item . prev ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠWe Ġknow Ġthe Ġitem Ġis ĠNOT Ġthe Ġmost Recent Cache Item . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠWe Ġknow Ġthe Ġitem Ġis ĠNOT Ġthe Ġleast Recent Cache Item . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThus : Ġthere Ġare Ġat Ġleast Ġ 3 Ġitems Ġin Ġthe Ġlist ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexisting Item . next ?. prev Ġ= Ġexisting Item . prev ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠMove Ġitem Ġto Ġbeginning Ġof Ġlinked - list ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexisting Item . prev Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġexisting Item . next Ġ= Ġmost Recent Cache Item ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmost Recent Cache Item ?. prev Ġ= Ġexisting Item ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmost Recent Cache Item Ġ= Ġexisting Item ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ Ġ// Ġexisting Item Ġ== Ġnull ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Item Ġ= ĠCache Item ( key , Ġvalue ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ map [ key ] Ġ= Ġnew Item ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠAdd Ġitem Ġto Ġbeginning Ġof Ġlinked - list ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġnew Item . next Ġ= Ġmost Recent Cache Item ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġmost Recent Cache Item ?. prev Ġ= Ġnew Item ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmost Recent Cache Item Ġ= Ġnew Item ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠEv ict Ġleast Recent Cache Item Ġif Ġneeded ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ((_ size Limit Ġ> Ġ 0 ) Ġ&& Ġ(_ map . size Ġ> Ġ_ size Limit )) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġkey To Ev ict Ġ= Ġleast Recent Cache Item !!. key ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleast Recent Cache Item Ġ= Ġleast Recent Cache Item ?. prev ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleast Recent Cache Item ?. next Ġ= Ġnull ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ_ map . remove ( key To Ev ict ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( least Recent Cache Item Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThere Ġis Ġonly Ġ 1 Ġitem Ġin Ġlist . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġleast Recent Cache Item Ġ=== Ġmost Recent Cache Item Ġ=== Ġnew Item ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleast Recent Cache Item Ġ= Ġnew Item ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġremove ( key : ĠKey ): ĠUnit Ġ{ ĊĊĠĠĠĠĠĠĠ Ġ_ map [ key ]?. let Ġ{ Ġitem Ġ-> ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( most Recent Cache Item Ġ=== Ġitem ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmost Recent Cache Item Ġ= Ġitem . next ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem . prev ?. next Ġ= Ġitem . next ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( least Recent Cache Item Ġ=== Ġitem ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleast Recent Cache Item Ġ= Ġitem . prev ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem . next ?. prev Ġ= Ġitem . prev ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ map . remove ( key ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġclear (): ĠUnit Ġ{ ĊĊĠĠĠĠĠĠĠ Ġvar Ġitem Ġ= Ġleast Recent Cache Item ĊĠĠĠĠĠĠĠ Ġwhile Ġ( item Ġ!= Ġnull ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġprev Ġ= Ġitem . prev ĊĠĠĠĠĠĠĠĠĠĠĠ Ġitem . next Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġitem . prev Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġitem Ġ= Ġprev ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġleast Recent Cache Item Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġmost Recent Cache Item Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġ_ map . clear () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġfiltered Keys ( ĊĠĠĠĠĠĠĠ Ġis Included : Ġ( Key ) Ġ-> ĠBoolean ĊĠĠĠ Ġ): ĠList < Key > Ġ{ ĊĊĠĠĠĠĠĠĠ Ġvar Ġresults Ġ= Ġmutable ListOf < Key >() ĊĊĠĠĠĠĠĠĠ Ġvar Ġitem Ġ= Ġmost Recent Cache Item ĊĠĠĠĠĠĠĠ Ġwhile Ġ( item Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( is Included ( item . key )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresults . add ( item . key ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġitem Ġ= Ġitem . next ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġresults ĊĠĠĠ Ġ} Ċ } Ċ