@ file : Suppress (" unused ") Ċ Ċ package Ġcom . am ino graphy . radix tree Ċ Ċ import Ġcom . am ino graphy . radix tree . internal . TreeNode Ċ import Ġjava . util .* Ċ import Ġkotlin . collections . ArrayList Ċ Ċ /** Ċ Ġ* ĠA Ġconcrete Ġimplementation Ġfor Ġ[ Mutable Rad ix Tree ]. Ċ Ġ* Ċ Ġ* Ġ@ param ĠT Ġthe Ġtype Ġof Ġthe Ġelements Ġcontained Ġin Ġthe Ġtree . Ċ Ġ* Ċ Ġ* Ġ@ author Ġa mino graphy Ċ Ġ*/ Ċ class ĠMutable Rad ix Tree Impl < T >() Ġ: ĠMutable Rad ix Tree < T > Ġ{ ĊĊĠĠĠ Ġconstructor ( from : ĠRad ix Tree < T >) Ġ: Ġthis () Ġ{ ĊĠĠĠĠĠĠĠ Ġput All ( from ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġthe Ġroot Ġnode Ġof Ġthe Ġtree ĊĠĠĠ Ġprivate Ġvar Ġroot : ĠTreeNode < T > Ġ= ĠTreeNode () ĊĊĠĠĠ Ġoverride Ġvar Ġsize : ĠInt Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġprivate Ġset ĊĊĠĠĠ Ġoverride Ġval Ġvalues : ĠMutable List < T > ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġexplore Children Values Via DFS ( root , Ġ 0 , ĠInt . MAX _ VALUE ) ĊĊĠĠĠ Ġoverride Ġval Ġentries : ĠMutable Set < Mutable Rad ix Tree . Mutable Entry < T >> ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġexplore Children Entries Via DFS ( root , Ġ 0 , ĠInt . MAX _ VALUE ) ĊĊĠĠĠ Ġoverride Ġfun ĠisEmpty (): ĠBoolean Ġ= Ġ( size Ġ== Ġ 0 ) ĊĊĠĠĠ Ġoverride Ġfun Ġcontains Key ( key : ĠString ): ĠBoolean Ġ= Ġ( find Prefix Root ( key )?. value Ġ!= Ġnull ) ĊĊĠĠĠ Ġoverride Ġfun Ġget ( key : ĠString ): ĠT ? Ġ= Ġfind Prefix Root ( key )?. value ĊĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠExplo res Ġthe Ġresult Ġof Ġthe Ġprefix Ġsearch Ġin Ġtwo Ġsteps : ĊĠĠĠĠ Ġ* Ġ 1 . ĠFinds Ġthe Ġfirst Ġnode Ġwhose Ġkey Ġsatisfies Ġthe Ġprefix Ġstring Ġexactly . ĊĠĠĠĠ Ġ* Ġ 2 . ĠExplo res Ġchildren Ġof Ġthe Ġnode Ġthat Ġis Ġfound Ġin Ġstep Ġ 1 . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġprefix Search ( prefix : ĠString , Ġoffset : ĠInt , Ġlimit : ĠInt ): ĠList < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( offset Ġ>= Ġsize Ġ|| Ġlimit Ġ<= Ġ 0 ) Ġreturn ĠlistOf () ĊĠĠĠĠĠĠĠ Ġval Ġt uned Offset Ġ= Ġif Ġ( offset Ġ< Ġ 0 ) Ġ 0 Ġelse Ġoffset ĊĊĠĠĠĠĠĠĠ Ġval Ġprefix Root Ġ= Ġif Ġ( prefix . isEmpty ()) Ġroot Ġelse Ġfind Prefix Root ( prefix ) ĊĠĠĠĠĠĠĠ Ġreturn Ġprefix Root ?. let Ġ{ Ġexplore Children Values Via DFS ( it , Ġt uned Offset , Ġlimit ) Ġ}. or Empty () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠExplo res Ġthe Ġtree Ġand Ġfinds Ġthe Ġfirst Ġnode Ġwhose Ġpath Ġfrom Ġthe Ġroot Ġmatches Ġall Ġthe Ġprefix Ġcharacters Ġin Ġorder . ĊĠĠĠĠ Ġ* ĠTo Ġfind Ġthe Ġtarget Ġnode , Ġthe Ġtree Ġwill Ġbe Ġtra versed Ġby Ġa Ġhe uristic ĠB read th - First ĠSearch Ġ( B FS ) Ġalgorithm . ĠSo Ġthat ĊĠĠĠĠ Ġ* Ġat Ġeach Ġlevel Ġof Ġthe Ġtree , Ġthe Ġalgorithm Ġch oo ses Ġthe Ġnext Ġstep Ġby Ġfinding Ġthe Ġonly Ġchild Ġwhose Ġkey Ġwill Ġmatch Ġthe ĊĠĠĠĠ Ġ* Ġrest Ġof Ġthe Ġinput Ġprefix . ĠSo , Ġthe Ġtime Ġcomplexity Ġfor Ġthis Ġfunction Ġis Ġ` O ( L )` Ġwhere Ġ` L ` Ġis Ġthe Ġlength Ġof Ġthe ĊĠĠĠĠ Ġ* Ġinput Ġprefix . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġfind Prefix Root ( prefix : ĠString ): ĠTreeNode < T >? Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġresult : ĠTreeNode < T >? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġfind Node Via B FS ( prefix ) Ġ{ Ġnode , Ġ_ Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġfind Node Via B FS ( key : ĠString , Ġwhen Found : Ġ( node : ĠTreeNode < T >, Ġparent : ĠTreeNode < T > ?) Ġ-> ĠUnit ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġqueue Ġ= ĠLinkedList < Pair < TreeNode < T > ?, ĠTreeNode < T >> >() ĊĠĠĠĠĠĠĠ Ġqueue . add ( Pair ( null , Ġroot )) ĊĠĠĠĠĠĠĠ Ġvar Ġkey Diff Ġ= Ġkey ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ( parent , Ġnode ) Ġ= Ġqueue . remove () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlcs Ġ= Ġlongest Common Prefix ( node . key , Ġkey Diff ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( lcs Ġ< Ġkey Diff . length Ġ&& Ġlcs Ġ== Ġnode . key . length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġkey Diff Ġ= Ġkey Diff . substring ( lcs ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children ?. let Ġ{ Ġchildren Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( child Ġin Ġchildren ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( child . key [ 0 ] Ġ== Ġkey Diff [ 0 ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue . add ( Pair ( node , Ġchild )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( lcs Ġ== Ġkey Diff . length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Found ( node , Ġparent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠExplo res Ġall Ġof Ġthe Ġnodes Ġin Ġthe Ġsubtree Ġof Ġ[ root ] Ġby Ġusing Ġa ĠDepth - First ĠSearch Ġ( DFS ) Ġalgorithm . ĠThe Ġtraversal ĊĠĠĠĠ Ġ* Ġis Ġin Ġsuch Ġa Ġway Ġthat Ġthe Ġorder Ġof Ġinserting Ġelements Ġgets Ġretained Ġin Ġthe Ġresulting Ġlist . ĠThe Ġtime Ġcomplexity Ġof ĊĠĠĠĠ Ġ* Ġthis Ġfunction Ġis Ġ` O ( V )`, Ġwhere Ġ` V ` Ġstands Ġfor Ġthe Ġnumber Ġof Ġnodes Ġcontaining Ġa Ġvalue . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġexplore Children Values Via DFS ( ĊĠĠĠĠĠĠĠ Ġroot : ĠTreeNode < T >, ĊĠĠĠĠĠĠĠ Ġoffset : ĠInt , ĊĠĠĠĠĠĠĠ Ġlimit : ĠInt ĊĠĠĠ Ġ): ĠArrayList < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= ĠArrayList < T >() ĊĊĠĠĠĠĠĠĠ Ġvar Ġskipped Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġval Ġstack Ġ= ĠStack < TreeNode < T >>() ĊĊĠĠĠĠĠĠĠ Ġstack . push ( root ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( stack . isNotEmpty () Ġ&& Ġresult . size Ġ< Ġlimit ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġstack . pop () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( skipped Ġ< Ġoffset ) Ġskipped ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġresult . add ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġit . size Ġ- Ġ 1 Ġdown To Ġ 0 ) Ġstack . push ( it [ i ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġstack . clear () ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Suppress (" Same Parameter Value ") ĊĠĠĠ Ġprivate Ġfun Ġexplore Children Entries Via DFS ( ĊĠĠĠĠĠĠĠ Ġroot : ĠTreeNode < T >, ĊĠĠĠĠĠĠĠ Ġoffset : ĠInt , ĊĠĠĠĠĠĠĠ Ġlimit : ĠInt ĊĠĠĠ Ġ): ĠMutable Set < Mutable Rad ix Tree . Mutable Entry < T >> Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= Ġmutable Set Of < Mutable Rad ix Tree . Mutable Entry < T >>() ĊĊĠĠĠĠĠĠĠ Ġvar Ġskipped Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġval Ġstack Ġ= ĠStack < Pair < String , ĠTreeNode < T >> >() ĊĊĠĠĠĠĠĠĠ Ġstack . push ( Pair ("", Ġroot )) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( stack . isNotEmpty () Ġ&& Ġresult . size Ġ< Ġlimit ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ( key , Ġnode ) Ġ= Ġstack . pop () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( skipped Ġ< Ġoffset ) Ġskipped ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġresult . add ( Mutable Entry Impl ( key , Ġit )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġit . size Ġ- Ġ 1 Ġdown To Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġchild Ġ= Ġit [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( Pair ( key Ġ+ Ġchild . key , Ġchild )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġstack . clear () ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġput ( key : ĠString , Ġvalue : ĠT ): ĠT ? Ġ= Ġinsert Node ( key , Ġvalue ) ĊĊĠĠĠ Ġoverride Ġfun Ġput ( value : ĠT , Ġkey Transformer : Ġ( T ) Ġ-> ĠString ): ĠT ? Ġ= Ġput ( key Transformer ( value ), Ġvalue ) ĊĊĠĠĠ Ġoverride Ġfun Ġput All ( from : ĠRad ix Tree < T >) Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( entry Ġin Ġfrom . entries ) Ġput ( entry . key , Ġentry . value ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠInser ts Ġthe Ġinput Ġelement Ġinto Ġthe Ġtree Ġat Ġthe Ġright Ġplace Ġaccording Ġto Ġthe Ġcorresponding Ġkey . ĠThe Ġtime ĊĠĠĠĠ Ġ* Ġcomplexity Ġto Ġinsert Ġa Ġnode Ġis Ġ` O ( l )` Ġwhere Ġ` l ` Ġis Ġthe Ġlength Ġof Ġthe Ġkey Ġassociated Ġwith Ġthe Ġvalue . ĠSo , Ġthe ĊĠĠĠĠ Ġ* Ġoverall Ġcomplexity Ġto Ġinserting Ġ` n ` Ġpairs Ġof Ġkey / value Ġis Ġ` O ( L Ġ* Ġn )` Ġwhere Ġ` L ` Ġstands Ġfor Ġthe Ġmaximum Ġlength Ġof ĊĠĠĠĠ Ġ* Ġkeys Ġin Ġthe Ġdataset . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġinsert Node ( key : ĠString , Ġvalue : ĠT ): ĠT ? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( key . isEmpty ()) Ġreturn Ġnull ĊĊĠĠĠĠĠĠĠ Ġsize ++ ĊĠĠĠĠĠĠĠ Ġvar Ġresult : ĠT ? Ġ= Ġnull ĊĊĠĠĠĠĠĠĠ Ġvar Ġkey Res idual Ġ= Ġkey ĊĠĠĠĠĠĠĠ Ġval Ġstack Ġ= ĠStack < TreeNode < T >>() ĊĊĠĠĠĠĠĠĠ Ġstack . push ( root ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( stack . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġstack . pop () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlcs Ġ= Ġlongest Common Prefix ( node . key , Ġkey Res idual ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( lcs Ġ== Ġ 0 Ġ|| Ġ( lcs Ġ< Ġkey Res idual . length Ġ&& Ġlcs Ġ== Ġnode . key . length )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode Ġis Ġroot ĠOR Ġkey Ġof Ġthe Ġnode Ġis Ġa Ġprefix Ġof Ġkey Res idual Ġand Ġshorter Ġthen Ġit . Ġ( so Ġthere Ġare ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġdesc endants Ġto Ġcover Ġit ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġkey Res idual Ġ= Ġkey Res idual . substring ( lcs ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġfound Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children ?. let Ġ{ Ġchildren Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( child Ġin Ġchildren ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( child . key [ 0 ] Ġ== Ġkey Res idual [ 0 ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfound Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( child ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! found ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . addChild ( TreeNode ( key Res idual , Ġvalue )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( lcs Ġ> Ġ 0 Ġ&& Ġlcs Ġ< Ġnode . key . length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġa Ġprefix Ġof Ġkey Ġof Ġthe Ġnode Ġis Ġa Ġprefix Ġof Ġkey Res idual , Ġso Ġthe Ġkey Ġof Ġthe Ġnode Ġmust Ġbe Ġdivided . ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġchild Ġ= ĠTreeNode ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . key . substring ( lcs ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . key Ġ= Ġkey Res idual . substring ( 0 , Ġlcs ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . reset Children () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . addChild ( child ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( lcs Ġ< Ġkey Res idual . length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġkey Res idual Ġ= Ġkey Res idual . substring ( lcs ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . addChild ( TreeNode ( key Res idual , Ġvalue )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( lcs Ġ== Ġkey Res idual . length Ġ&& Ġlcs Ġ== Ġnode . key . length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġa Ġnode Ġexists Ġwith Ġthe Ġexact Ġkey . ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . value Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= Ġnode . value ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsize -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġend Ġof Ġthe Ġtree , Ġadd Ġthe Ġchild Ġas Ġa Ġleaf . ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġchild Ġ= ĠTreeNode ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . key . substring ( lcs ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . key Ġ= Ġkey Res idual ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . addChild ( child ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġremove ( key : ĠString ): ĠT ? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( key . isEmpty ()) Ġreturn Ġnull ĊĊĠĠĠĠĠĠĠ Ġvar Ġresult : ĠT ? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġfind Node Via B FS ( key ) Ġ{ Ġnode , Ġparent Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . value Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= Ġnode . value ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelete Node ( node , Ġparent ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġremove ( key : ĠString , Ġvalue : ĠT ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( key . isEmpty ()) Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġvar Ġresult Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġfind Node Via B FS ( key ) Ġ{ Ġnode , Ġparent Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . value Ġ== Ġvalue ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdelete Node ( node , Ġparent ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġdelete Node ( node : ĠTreeNode < T >, Ġparent : ĠTreeNode < T > ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġwhen Ġ( node . children ?. size Ġ?: Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 Ġ-> Ġ( parent ?. children Ġas ? ĠMutable List )?. remove ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠ 1 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġchild Ġ= Ġnode . children ! ![ 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . key Ġ+= Ġchild . key ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value Ġ= Ġchild . value ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children Ġ= Ġchild . children ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġnode . value Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġreplace ( key : ĠString , Ġvalue : ĠT ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( key . isEmpty ()) Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġfind Prefix Root ( key )?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( it . value Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . value Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġclear () Ġ{ ĊĠĠĠĠĠĠĠ Ġroot . reset Children () ĊĠĠĠĠĠĠĠ Ġsize Ġ= Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠCalculates Ġthe Ġlongest Ġcommon Ġlength Ġbetween Ġtwo Ġstrings Ġstarting Ġfrom Ġtheir Ġzero Ġindices . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġlongest Common Prefix ( first : ĠString , Ġsecond : ĠString ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmax Ġ= Ġfirst . length . coerce At Most ( second . length ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġmax ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( first [ i ] Ġ!= Ġsecond [ i ]) Ġreturn Ġi ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġmax ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠVisual izes Ġtree Ġstructure Ġin Ġconsole , Ġonly Ġfor Ġtesting . ĊĠĠĠĠ Ġ* ĠWARNING ! ĠNotice Ġthat Ġshould Ġnot Ġbe Ġused Ġfor Ġprinting Ġlarge Ġtrees . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġvisualize () Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ(! root . has Children ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ("< empty >") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġtraverse ( node : ĠTreeNode < T > ?, Ġprefix : ĠString ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node ?. has Children Ġ== Ġfalse ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" âķ ´ Ġ${ node . key }" Ġ+ Ġ( node . value ?. let Ġ{ Ġ" Ġ[$ it ]" Ġ} Ġ?: Ġ"")) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" âĶ Ĳ Ġ${ node ?. key }" Ġ+ Ġ( node ?. value ?. let Ġ{ Ġ" Ġ[$ it ]" Ġ} Ġ?: Ġ"")) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( child Ġin Ġnode ?. children ?. drop Last ( 1 ). or Empty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprint ("$ prefix âĶ ľ âĶĢ ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtraverse ( child , Ġ"$ prefix âĶĤ Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprint ("$ prefix âĶĶ âĶĢ ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtraverse ( node ?. children ?. last (), Ġ"$ prefix Ġ Ġ") ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġtraverse ( root , Ġ"") ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġdata Ġclass ĠMutable Entry Impl < T >( ĊĠĠĠĠĠĠĠ Ġoverride Ġval Ġkey : ĠString , ĊĠĠĠĠĠĠĠ Ġoverride Ġvar Ġvalue : ĠT ĊĠĠĠ Ġ) Ġ: ĠMutable Rad ix Tree . Mutable Entry < T > Ġ{ ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠsetValue ( newValue : ĠT ): ĠT Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtemp Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalue Ġ= ĠnewValue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtemp ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }