package Ġorg . open rnd r . extra . k dt ree Ċ Ċ import Ġkotlinx . coroutines . Coroutine Scope Ċ import Ġkotlinx . coroutines . Global Scope Ċ import Ġkotlinx . coroutines . launch Ċ import Ġkotlinx . coroutines . run Blocking Ċ import Ġorg . open rnd r . math . Int Vector 2 Ċ import Ġorg . open rnd r . math . Vector 2 Ċ import Ġorg . open rnd r . math . Vector 3 Ċ import Ġorg . open rnd r . math . Vector 4 Ċ import Ġjava . util .* Ċ import Ġkotlin . IllegalStateException Ċ import Ġkotlin . math . abs Ċ Ċ /** Ġbuilt - in Ġmapper Ġfor Ġ[ Vector 2 ] Ġ*/ Ċ fun Ġvector 2 Mapper ( v : ĠVector 2 , Ġdimension : ĠInt ): ĠDouble Ġ{ ĊĠĠĠ Ġreturn Ġwhen Ġ( dimension ) Ġ{ ĊĠĠĠĠĠĠĠĠ 0 Ġ-> Ġv . x ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġv . y ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġint Vector 2 Mapper ( v : ĠInt Vector 2 , Ġdimension : ĠInt ): ĠDouble Ġ{ ĊĠĠĠ Ġreturn Ġwhen Ġ( dimension ) Ġ{ ĊĠĠĠĠĠĠĠĠ 0 Ġ-> Ġv . x . toDouble () ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġv . y . toDouble () ĊĠĠĠ Ġ} Ċ } ĊĊ Ċ /** Ġbuilt - in Ġmapper Ġfor Ġ[ Vector 3 ] Ġ*/ Ċ fun Ġvector 3 Mapper ( v : ĠVector 3 , Ġdimension : ĠInt ): ĠDouble Ġ{ ĊĠĠĠ Ġreturn Ġwhen Ġ( dimension ) Ġ{ ĊĠĠĠĠĠĠĠĠ 0 Ġ-> Ġv . x ĊĠĠĠĠĠĠĠĠ 1 Ġ-> Ġv . y ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġv . z ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ġbuilt - in Ġmapper Ġfor Ġ[ Vector 4 ] Ġ*/ Ċ fun Ġvector 4 Mapper ( v : ĠVector 4 , Ġdimension : ĠInt ): ĠDouble Ġ{ ĊĠĠĠ Ġreturn Ġwhen Ġ( dimension ) Ġ{ ĊĠĠĠĠĠĠĠĠ 0 Ġ-> Ġv . x ĊĠĠĠĠĠĠĠĠ 1 Ġ-> Ġv . y ĊĠĠĠĠĠĠĠĠ 2 Ġ-> Ġv . z ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġv . w ĊĠĠĠ Ġ} Ċ } Ċ Ċ class ĠK D TreeNode < T > Ġ{ ĊĠĠĠ Ġvar Ġparent : ĠK D TreeNode < T >? Ġ= Ġnull ĊĠĠĠ Ġvar Ġmedian : ĠDouble Ġ= Ġ 0 . 0 ĊĠĠĠ Ġvar Ġdimension : ĠInt Ġ= Ġ 0 ĊĠĠĠ Ġvar Ġchildren : ĠArray < KD TreeNode < T > ?> Ġ= ĠarrayOf Null s ( 2 ) ĊĠĠĠ Ġvar Ġitem : ĠT ? Ġ= Ġnull ĊĊĠĠĠ Ġinternal Ġval Ġis Leaf : ĠBoolean ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġchildren [ 0 ] Ġ== Ġnull Ġ&& Ġchildren [ 1 ] Ġ== Ġnull ĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ" KD TreeNode {" Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" median =" Ġ+ Ġmedian Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ", Ġitem =" Ġ+ Ġitem Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ", Ġdimension =" Ġ+ Ġdimension Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ", Ġchildren =" Ġ+ ĠArrays . toString ( children ) Ġ+ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ"} Ġ" Ġ+ Ġsuper . toString () ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġ< T > Ġinsert Item ( root : ĠK D TreeNode < T >, Ġitem : ĠT , Ġmapper : Ġ( T , ĠInt ) Ġ-> ĠDouble ): ĠK D TreeNode < T > Ġ{ ĊĠĠĠ Ġreturn Ġif Ġ( root . is Leaf ) Ġ{ ĊĠĠĠĠĠĠĠ Ġroot . item Ġ= Ġitem ĊĠĠĠĠĠĠĠ Ġroot ĊĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( mapper ( item , Ġroot . dimension ) Ġ< Ġroot . median ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinsert Item ( root . children [ 0 ] Ġ?: Ġthrow ĠIllegalStateException (" left Ġis Ġnull "), Ġitem , Ġmapper ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinsert Item ( root . children [ 1 ] Ġ?: Ġthrow ĠIllegalStateException (" right Ġis Ġnull "), Ġitem , Ġmapper ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġ< T > Ġbuild KD Tree ( items : ĠMutable List < T >, Ġdimensions : ĠInt , Ġmapper : Ġ( T , ĠInt ) Ġ-> ĠDouble , Ġsilent : ĠBoolean Ġ= Ġfalse ): ĠK D TreeNode < T > Ġ{ ĊĠĠĠ Ġval Ġroot Ġ= ĠK D TreeNode < T >() ĊĊĠĠĠ Ġval Ġstart Ġ= ĠSystem . currentTimeMillis () ĊĠĠĠ Ġfun Ġ< T > Ġbuild Tree Task ( scope : ĠCor outine Scope , Ġnode : ĠK D TreeNode < T >, Ġitems : ĠMutable List < T >, Ġdimensions : ĠInt , Ġlevels : ĠInt , Ġmapper : Ġ( T , ĠInt ) Ġ-> ĠDouble ): ĠK D TreeNode < T > Ġ{ ĊĊĠĠĠĠĠĠĠ Ġif Ġ( items . size Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdimension Ġ= Ġlevels Ġ% Ġdimensions ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġvalues Ġ= ĠArrayList < T >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( item Ġin Ġitems ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalues . add ( item ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . dimension Ġ= Ġdimension ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmedian Ġ= Ġselect N th ( items , Ġitems . size Ġ/ Ġ 2 ) Ġ{ Ġmapper ( it , Ġdimension ) Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġleft Items Ġ= Ġmutable ListOf < T >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġright Items Ġ= Ġmutable ListOf < T >() ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . median Ġ= Ġmapper ( median , Ġdimension ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . item Ġ= Ġmedian ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( item Ġin Ġitems ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( item Ġ=== Ġmedian ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( mapper ( item , Ġdimension ) Ġ< Ġnode . median ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleft Items . add ( item ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġright Items . add ( item ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġvalidate Ġsplit ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( left Items . size Ġ+ Ġright Items . size Ġ+ Ġ 1 Ġ!= Ġitems . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠIllegalStateException (" left : Ġ${ left Items . size }, Ġright : Ġ${ right Items . size }, Ġitems : Ġ${ items . size }") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( left Items . size Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 0 ] Ġ= ĠK D TreeNode () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 0 ]?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . parent Ġ= Ġnode ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġscope . launch Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbuild Tree Task ( scope , Ġit , Ġleft Items , Ġdimensions , Ġlevels Ġ+ Ġ 1 , Ġmapper ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( right Items . size Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 1 ] Ġ= ĠK D TreeNode () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 1 ]?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . parent Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġscope . launch Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbuild Tree Task ( scope , Ġit , Ġright Items , Ġdimensions , Ġlevels Ġ+ Ġ 1 , Ġmapper ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġnode ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġjob Ġ= ĠGlobal Scope . launch Ġ{ ĊĠĠĠĠĠĠĠ Ġbuild Tree Task ( this , Ġroot , Ġitems , Ġdimensions , Ġ 0 , Ġmapper ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġrun Blocking Ġ{ ĊĠĠĠĠĠĠĠ Ġjob . join () ĊĠĠĠ Ġ} ĊĠĠĠ Ġif Ġ(! silent ) Ġprintln (" building Ġtook Ġ${ System . currentTimeMillis ()- start } ms ") ĊĠĠĠ Ġreturn Ġroot Ċ } Ċ Ċ private Ġfun Ġ< T > Ġsq r Distance ( left : ĠT , Ġright : ĠT , Ġdimensions : ĠInt , Ġmapper : Ġ( T , ĠInt ) Ġ-> ĠDouble ): ĠDouble Ġ{ ĊĠĠĠ Ġvar Ġdistance Ġ= Ġ 0 . 0 ĊĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġdimensions ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġmapper ( left , Ġi ) Ġ- Ġmapper ( right , Ġi ) ĊĠĠĠĠĠĠĠ Ġdistance Ġ+= Ġd Ġ* Ġd ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġdistance Ċ } Ċ Ċ fun Ġ< T > ĠfindAll Nodes ( root : ĠK D TreeNode < T >): ĠList < KD TreeNode < T >> Ġ{ ĊĠĠĠ Ġval Ġstack Ġ= ĠStack < KD TreeNode < T >>() ĊĠĠĠ Ġval Ġall Ġ= ĠArrayList < KD TreeNode < T >>() ĊĠĠĠ Ġstack . empty () ĊĠĠĠ Ġstack . push ( root ) ĊĠĠĠ Ġwhile Ġ(! stack . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġstack . pop () Ċ // ĠĠĠĠĠĠĠ Ġif Ġ( node . item Ġ!= Ġnull Ġ/* && Ġ! visited . contains ( node . children [ 1 ]) */) Ġ{ ĊĠĠĠĠĠĠĠ Ġall . add ( node ) Ċ // ĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( node . children [ 0 ] Ġ!= Ġnull Ġ Ġ/* && ! visited . contains ( node . children [ 0 ]) */) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( node . children [ 0 ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( node . children [ 1 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( node . children [ 1 ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġall Ċ } ĊĊ Ċ fun Ġ< T > Ġfind Nearest ( root : ĠK D TreeNode < T >, Ġitem : ĠT , Ġdimensions : ĠInt , Ġmapper : Ġ( T , ĠInt ) Ġ-> ĠDouble ): ĠT ? Ġ{ ĊĠĠĠ Ġvar Ġnearest Ġ= Ġjava . lang . Double . POSITIVE _ INFINITY ĊĠĠĠ Ġvar Ġnearest Arg : ĠK D TreeNode < T >? Ġ= Ġnull ĊĊĠĠĠ Ġfun Ġnearest ( node : ĠK D TreeNode < T > ?, Ġitem : ĠT ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ!= Ġnull ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . item Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġroute : ĠInt Ġ= Ġif Ġ( mapper ( item , Ġnode . dimension ) Ġ< Ġnode . median ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnearest ( node . children [ 0 ], Ġitem ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnearest ( node . children [ 1 ], Ġitem ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdistance Ġ= Ġsq r Distance ( item , Ġnode . item ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ?: Ġthrow ĠIllegalStateException (" item Ġis Ġnull "), Ġdimensions , Ġmapper ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( distance Ġ< Ġnearest ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnearest Ġ= Ġdistance ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnearest Arg Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġabs ( node . median Ġ- Ġmapper ( item , Ġnode . dimension )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( d Ġ* Ġd Ġ< Ġnearest ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnearest ( node . children [ 1 Ġ- Ġroute ], Ġitem ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġnearest ( root , Ġitem ) ĊĠĠĠ Ġreturn Ġnearest Arg ?. item Ċ } Ċ Ċ fun Ġ< T > Ġinsert ( root : ĠK D TreeNode < T >, Ġitem : ĠT , Ġdimensions : ĠInt , Ġmapper : Ġ( T , ĠInt ) Ġ-> ĠDouble ): ĠK D TreeNode < T > Ġ{ ĊĠĠĠ Ġval Ġstack Ġ= ĠStack < KD TreeNode < T >>() ĊĠĠĠ Ġstack . push ( root ) ĊĊĠĠĠ Ġd ive @ Ġwhile Ġ( true ) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġstack . peek () ĊĊĠĠĠĠĠĠĠ Ġval Ġvalue Ġ= Ġmapper ( item , Ġnode . dimension ) ĊĊĠĠĠĠĠĠĠ Ġif Ġ( value Ġ< Ġnode . median ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . children [ 0 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( node . children [ 0 ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsit Ġhere ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 0 ] Ġ= ĠK D TreeNode () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 0 ]?. item Ġ= Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 0 ]?. dimension Ġ= Ġ( node . dimension Ġ+ Ġ 1 ) Ġ% Ġdimensions ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 0 ]?. median Ġ= Ġmapper ( item , Ġ( node . dimension Ġ+ Ġ 1 ) Ġ% Ġdimensions ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 0 ]?. parent Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnode . children [ 0 ] Ġ?: Ġthrow ĠIllegalStateException (" child Ġis Ġnull ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . children [ 1 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( node . children [ 1 ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsit Ġhere ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 1 ] Ġ= ĠK D TreeNode () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 1 ]?. item Ġ= Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 1 ]?. dimension Ġ= Ġ( node . dimension Ġ+ Ġ 1 ) Ġ% Ġdimensions ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 1 ]?. median Ġ= Ġmapper ( item , Ġ( node . dimension Ġ+ Ġ 1 ) Ġ% Ġdimensions ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . children [ 1 ]?. parent Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnode . children [ 1 ] Ġ?: Ġthrow ĠIllegalStateException (" child Ġis Ġnull ") ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġ< T > Ġremove ( to Remove : ĠK D TreeNode < T >, Ġmapper : Ġ( T , ĠInt ) Ġ-> ĠDouble ): ĠK D TreeNode < T >? Ġ{ ĊĠĠĠ Ġ// Ġtrivial Ġcase ĊĠĠĠ Ġif Ġ( to Remove . is Leaf ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġp Ġ= Ġto Remove . parent ĊĠĠĠĠĠĠĠ Ġif Ġ( p Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . children [ 0 ] Ġ=== Ġto Remove Ġ-> Ġp . children [ 0 ] Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . children [ 1 ] Ġ=== Ġto Remove Ġ-> Ġp . children [ 1 ] Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġbroken ! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġto Remove . item Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġstack Ġ= ĠStack < KD TreeNode < T >>() ĊĊĠĠĠĠĠĠĠ Ġvar Ġbranch Ġ= Ġ 0 ĊĊĠĠĠĠĠĠĠ Ġif Ġ( to Remove . children [ 0 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( to Remove . children [ 0 ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġbranch Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( to Remove . children [ 1 ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġbranch Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġvar Ġmin Value : ĠDouble Ġ= Ġjava . lang . Double . POSITIVE _ INFINITY ĊĠĠĠĠĠĠĠ Ġvar ĠmaxValue : ĠDouble Ġ= Ġjava . lang . Double . NEGATIVE _ INFINITY ĊĠĠĠĠĠĠĠ Ġvar Ġmin Arg : ĠK D TreeNode < T >? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġvar Ġmax Arg : ĠK D TreeNode < T >? Ġ= Ġnull ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ(! stack . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġstack . pop () Ġ?: Ġthrow ĠRuntimeException (" null Ġon Ġstack ") ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġvalue Ġ= Ġmapper ( node . item Ġ?: Ġthrow ĠIllegalStateException (" item Ġis Ġnull "), Ġto Remove . dimension ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( value Ġ< Ġmin Value ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmin Value Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmin Arg Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( value Ġ> ĠmaxValue ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠmaxValue Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmax Arg Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . dimension Ġ!= Ġto Remove . dimension ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . children [ 0 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( node . children [ 0 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . children [ 1 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( node . children [ 1 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( branch Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . children [ 0 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( node . children [ 0 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . children [ 1 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( node . children [ 1 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( branch Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . children [ 1 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( node . children [ 1 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . children [ 0 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( node . children [ 0 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĊĠĠĠĠĠĠĠ Ġif Ġ( branch Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġto Remove . item Ġ= Ġmin Arg ?. item ĊĠĠĠĠĠĠĠĠĠĠĠ Ġto Remove . median Ġ= Ġmapper ( min Arg ?. item Ġ?: Ġthrow ĠIllegalStateException (" min Arg Ġis Ġnull "), Ġto Remove . dimension ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġremove ( min Arg , Ġmapper ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( branch Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġto Remove . item Ġ= Ġmax Arg ?. item ĊĠĠĠĠĠĠĠĠĠĠĠ Ġto Remove . median Ġ= Ġmapper ( max Arg ?. item Ġ?: Ġthrow ĠIllegalStateException (" max Arg Ġis Ġnull "), Ġto Remove . dimension ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġremove ( max Arg , Ġmapper ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġnull Ċ } Ċ