/* Ċ Ġ* ĠCopyright Ġ( c ) Ġ 2 0 1 8 - 2 0 1 9 . Ġdata 2 viz Ġs Ãł rl . Ċ Ġ* Ċ Ġ* Ġ ĠLicensed Ġunder Ġthe ĠApache ĠLicense , ĠVersion Ġ 2 . 0 Ġ( the Ġ" License "); Ċ Ġ* Ġ Ġyou Ġmay Ġnot Ġuse Ġthis Ġfile Ġexcept Ġin Ġcompliance Ġwith Ġthe ĠLicense . Ċ Ġ* Ġ ĠYou Ġmay Ġobtain Ġa Ġcopy Ġof Ġthe ĠLicense Ġat Ċ Ġ* Ċ Ġ* Ġ Ġhttp :// www . apache . org / licenses / LICENSE - 2 . 0 Ċ Ġ* Ċ Ġ* Ġ ĠUnless Ġrequired Ġby Ġapplicable Ġlaw Ġor Ġagreed Ġto Ġin Ġwriting , Ġsoftware Ċ Ġ* Ġ Ġdistributed Ġunder Ġthe ĠLicense Ġis Ġdistributed Ġon Ġan Ġ" AS ĠIS " ĠBASIS , Ċ Ġ* Ġ ĠWITHOUT ĠWARRANTIES ĠOR ĠCONDITIONS ĠOF ĠANY ĠKIND , Ġeither Ġexpress Ġor Ġimplied . Ċ Ġ* Ġ ĠSee Ġthe ĠLicense Ġfor Ġthe Ġspecific Ġlanguage Ġgoverning Ġpermissions Ġand Ċ Ġ* Ġ Ġlimitations Ġunder Ġthe ĠLicense . Ċ Ġ* Ċ Ġ*/ Ċ Ċ package Ġio . data 2 viz . quad tree Ċ Ċ /** Ċ Ġ* ĠRemoves Ġthe Ġspecified Ġdatum Ġto Ġthe Ġquad tree , Ġderiving Ġits Ġcoordinates ĠâŁ ¨ x , y âŁ © Ġusing Ġthe Ġcurrent Ġx - Ġand Ġy - access ors . Ċ Ġ* ĠIf Ġthe Ġspecified Ġdatum Ġdoes Ġnot Ġexist Ġin Ġthis Ġquad tree , Ġthis Ġmethod Ġdoes Ġnothing . Ċ Ġ* ĠTODO Ġ: Ġcheck Ġtests Ġvalue Ġmust Ġbe Ġ=== Ġremoved Ġvalue Ċ Ġ*/ Ċ public Ġfun Ġ< D > ĠQuad tree < D >. remove ( datum : ĠD ) Ġ{ ĊĠĠĠ Ġval Ġx Ġ= Ġx ( datum ) ĊĠĠĠ Ġval Ġy Ġ= Ġy ( datum ) ĊĊĠĠĠ Ġif Ġ( x . isNaN () Ġ|| Ġy . isNaN ()) Ġreturn ĊĊĠĠĠ Ġvar Ġnode Ġ= Ġroot ĊĠĠĠ Ġvar Ġx 0 Ġ= Ġextent . x 0 ĊĠĠĠ Ġvar Ġy 0 Ġ= Ġextent . y 0 ĊĠĠĠ Ġvar Ġx 1 Ġ= Ġextent . x 1 ĊĠĠĠ Ġvar Ġy 1 Ġ= Ġextent . y 1 ĊĊĠĠĠ Ġvar Ġparent : ĠInternal Node < D >? Ġ= Ġnull ĊĠĠĠ Ġvar Ġret ainer : ĠInternal Node < D >? Ġ= Ġnull ĊĠĠĠ Ġvar Ġprevious : ĠQuad tree Node < D >? Ġ= Ġnull ĊĠĠĠ Ġvar Ġindex Ġ= Ġ 0 ĊĠĠĠ Ġvar Ġj n dex Ġ= Ġ 0 ĊĊĊĠĠĠ Ġ// ĠIf Ġthe Ġtree Ġis Ġempty , Ġinitialize Ġthe Ġroot Ġas Ġa Ġleaf . ĊĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn ĊĊĠĠĠ Ġ// ĠFind Ġthe Ġleaf Ġnode Ġfor Ġthe Ġpoint . ĊĠĠĠ Ġ// ĠWhile Ġdescending , Ġalso Ġretain Ġthe Ġdee pe st Ġparent Ġwith Ġa Ġnon - removed Ġsibling . ĊĠĠĠ Ġif Ġ( node Ġis ĠInternal Node ) Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġx m Ġ= Ġ( x 0 Ġ+ Ġx 1 ) Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġval Ġright Ġ= Ġx Ġ>= Ġx m ĊĠĠĠĠĠĠĠ Ġif Ġ( right ) Ġx 0 Ġ= Ġx m Ġelse Ġx 1 Ġ= Ġx m ĊĊĠĠĠĠĠĠĠ Ġval Ġy m Ġ= Ġ( y 0 Ġ+ Ġy 1 ) Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġval Ġbottom Ġ= Ġy Ġ>= Ġy m ĊĠĠĠĠĠĠĠ Ġif Ġ( bottom ) Ġy 0 Ġ= Ġy m Ġelse Ġy 1 Ġ= Ġy m ĊĊĠĠĠĠĠĠĠ Ġparent Ġ= Ġnode Ġas ĠInternal Node < D > ĊĠĠĠĠĠĠĠ Ġindex Ġ= Ġbottom . toInt () Ġshl Ġ 1 Ġor Ġright . toInt () ĊĠĠĠĠĠĠĠ Ġnode Ġ= ĠgetNode From Index ( node , Ġindex ) ĊĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġis ĠLeaf Node ) Ġbreak ĊĊĠĠĠĠĠĠĠ Ġif Ġ( getNode From Index ( parent , Ġ( index Ġ+ Ġ 1 ) Ġand Ġ 3 ) Ġ!= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ|| ĠgetNode From Index ( parent , Ġ( index Ġ+ Ġ 2 ) Ġand Ġ 3 ) Ġ!= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ|| ĠgetNode From Index ( parent , Ġ( index Ġ+ Ġ 3 ) Ġand Ġ 3 ) Ġ!= Ġnull ĊĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġret ainer Ġ= Ġparent ĊĠĠĠĠĠĠĠĠĠĠĠ Ġj n dex Ġ= Ġindex ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠFind Ġthe Ġpoint Ġto Ġremove . ĊĠĠĠ Ġwhile Ġ(!( node Ġis ĠLeaf Node ) Ġ|| Ġnode . data Ġ!= Ġdatum ) Ġ{ ĊĠĠĠĠĠĠĠ Ġprevious Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġnode Ġ= Ġ( node Ġas ĠLeaf Node ). next ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġnext Ġ= Ġnode . next ĊĠĠĠ Ġif Ġ( next Ġ!= Ġnull ) Ġnode . next Ġ= Ġnull ĊĊĠĠĠ Ġ// ĠIf Ġthere Ġare Ġmultiple Ġcoin c ident Ġpoints , Ġremove Ġjust Ġthe Ġpoint . ĊĠĠĠ Ġif Ġ( previous Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( next Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( previous Ġas ĠLeaf Node ). next Ġ= Ġnext ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( previous Ġas ĠLeaf Node ). next Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠIf Ġthis Ġis Ġthe Ġroot Ġpoint , Ġremove Ġit . ĊĠĠĠ Ġif Ġ( parent Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠ Ġroot Ġ= Ġnext ĊĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠRemove Ġthis Ġleaf . ĊĠĠĠ Ġif Ġ( next Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠ Ġset Node From Index ( parent , Ġindex , Ġnext ) ĊĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠ Ġset Node From Index ( parent , Ġindex , Ġnull ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠIf Ġthe Ġparent Ġnow Ġcontains Ġexactly Ġone Ġleaf , Ġcollapse Ġsuper flu ous Ġparents . ĊĠĠĠ Ġval Ġp 0 Ġ= ĠgetNode From Index ( parent , Ġ 0 ) ĊĠĠĠ Ġval Ġp 1 Ġ= ĠgetNode From Index ( parent , Ġ 1 ) ĊĠĠĠ Ġval Ġp 2 Ġ= ĠgetNode From Index ( parent , Ġ 2 ) ĊĠĠĠ Ġval Ġp 3 Ġ= ĠgetNode From Index ( parent , Ġ 3 ) ĊĠĠĠ Ġnode Ġ= Ġif Ġ( p 0 Ġ!= Ġnull ) Ġp 0 Ġelse Ġif Ġ( p 1 Ġ!= Ġnull ) Ġp 1 Ġelse Ġif Ġ( p 2 Ġ!= Ġnull ) Ġp 2 Ġelse Ġp 3 ĊĊĠĠĠ Ġif Ġ( node Ġ!= Ġnull ĊĠĠĠĠĠĠĠ Ġ&& Ġnode Ġ== Ġ( if Ġ( p 3 Ġ!= Ġnull ) Ġp 3 Ġelse Ġif Ġ( p 2 Ġ!= Ġnull ) Ġp 2 Ġelse Ġif Ġ( p 1 Ġ!= Ġnull ) Ġp 1 Ġelse Ġp 0 ) ĊĠĠĠĠĠĠĠ Ġ&& Ġnode Ġis ĠLeaf Node ĊĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( ret ainer Ġ!= Ġnull ) Ġset Node From Index ( ret ainer , Ġj n dex , Ġnode ) ĊĠĠĠĠĠĠĠ Ġelse Ġroot Ġ= Ġnode ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* ĠRemoves Ġthe Ġspecified Ġdata Ġfrom Ġthe Ġquad tree . Ċ Ġ* Ġ@ see ĠQuad tree . remove ( datum ) Ċ Ġ*/ Ċ public Ġfun Ġ< D > ĠQuad tree < D >. removeAll ( data : ĠList < D >): ĠUnit Ġ= Ġdata . forEach Ġ{ Ġdatum Ġ-> Ġremove ( datum ) Ġ}