/* Ċ Ġ* ĠThe ĠMIT ĠLicense Ċ Ġ* Ċ Ġ* ĠCopyright Ġ 2 0 1 5 ĠN athan ĠTemp lon . Ċ Ġ* Ċ Ġ* ĠPermission Ġis Ġhereby Ġgranted , Ġfree Ġof Ġcharge , Ġto Ġany Ġperson Ġobtaining Ġa Ġcopy Ċ Ġ* Ġof Ġthis Ġsoftware Ġand Ġassociated Ġdocumentation Ġfiles Ġ( the Ġ" Software "), Ġto Ġdeal Ċ Ġ* Ġin Ġthe ĠSoftware Ġwithout Ġrestriction , Ġincluding Ġwithout Ġlimitation Ġthe Ġrights Ċ Ġ* Ġto Ġuse , Ġcopy , Ġmodify , Ġmerge , Ġpublish , Ġdistribute , Ġsublicense , Ġand / or Ġsell Ċ Ġ* Ġcopies Ġof Ġthe ĠSoftware , Ġand Ġto Ġpermit Ġpersons Ġto Ġwhom Ġthe ĠSoftware Ġis Ċ Ġ* Ġfurnished Ġto Ġdo Ġso , Ġsubject Ġto Ġthe Ġfollowing Ġconditions : Ċ Ġ* ĠThe Ġabove Ġcopyright Ġnotice Ġand Ġthis Ġpermission Ġnotice Ġshall Ġbe Ġincluded Ġin Ċ Ġ* Ġall Ġcopies Ġor Ġsubstantial Ġportions Ġof Ġthe ĠSoftware . Ċ Ġ* Ċ Ġ* ĠTHE ĠSOFTWARE ĠIS ĠPROVIDED Ġ" AS ĠIS ", ĠWITHOUT ĠWARRANTY ĠOF ĠANY ĠKIND , ĠEXPRESS ĠOR Ċ Ġ* ĠIMPLIED , ĠINCLUDING ĠBUT ĠNOT ĠLIMITED ĠTO ĠTHE ĠWARRANTIES ĠOF ĠMERCHANTABILITY , Ċ Ġ* ĠFITNESS ĠFOR ĠA ĠPARTICULAR ĠPURPOSE ĠAND ĠNONINFRINGEMENT . ĠIN ĠNO ĠEVENT ĠSHALL ĠTHE Ċ Ġ* ĠAUTHORS ĠOR ĠCOPYRIGHT ĠHOLDERS ĠBE ĠLIABLE ĠFOR ĠANY ĠCLAIM , ĠDAMAGES ĠOR ĠOTHER Ċ Ġ* ĠLIABILITY , ĠWHETHER ĠIN ĠAN ĠACTION ĠOF ĠCONTRACT , ĠTORT ĠOR ĠOTHERWISE , ĠARISING ĠFROM , Ċ Ġ* ĠOUT ĠOF ĠOR ĠIN ĠCONNECTION ĠWITH ĠTHE ĠSOFTWARE ĠOR ĠTHE ĠUSE ĠOR ĠOTHER ĠDEALINGS ĠIN Ċ Ġ* ĠTHE ĠSOFTWARE . Ċ Ġ* Ċ Ġ*/ Ċ package Ġcom . jupiter . eu rop a . util Ċ Ċ import Ġjava . awt . Rectangle Ċ import Ġjava . util . HashSet Ċ Ċ /** Ċ Ġ* ĠThis Ġclass Ġis Ġstill Ġmostly Ġunt ested ; Ġthat Ġwill Ġhave Ġto Ġwait Ġuntil Ġthere Ġare Ġenough Ġentities Ġrunning Ġaround Ġto Ġdo Ċ Ġ* Ġsomething Ġabout Ġit . ĊĊ Ġ* Ġ@ author ĠN athan ĠTemp lon Ċ Ġ* Ġ* Ċ Ġ* Ġ@ param Ċ Ġ*/ Ċ public Ġclass ĠQuad tree < T Ġ: ĠRect angular Bounded Object >( public Ġval Ġbounds : ĠRectangle ) Ġ{ ĊĊĊĠĠĠ Ġ// ĠFields ĊĠĠĠ Ġprivate Ġval Ġmax Objects Per Leaf : ĠInt ĊĠĠĠ Ġprivate Ġval Ġobjects : ĠMutable Collection < T > ĊĠĠĠ Ġprivate Ġval Ġchildren : ĠArray < Quad tree < T > ?> ĊĊĊĠĠĠ Ġinit Ġ{ ĊĊĠĠĠĠĠĠĠ Ġthis . max Objects Per Leaf Ġ= ĠDEFAULT _ MAX _ OBJECTS _ PER _ LEAF ĊĠĠĠĠĠĠĠ Ġthis . objects Ġ= ĠHashSet < T >() ĊĠĠĠĠĠĠĠ Ġthis . children Ġ= ĠarrayOf Null s < Quad tree < T >>( 4 ) ĊĠĠĠ Ġ} ĊĊĊĠĠĠ Ġ// ĠPublic ĠMethods ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠTemporary Ġimplementation , Ġshould Ġchange Ġto Ġinclude Ġmore Ġcases Ġto Ġprevent Ġre ordering Ġchildren Ġso Ġoften . ĊĊĠĠĠĠ Ġ* Ġ@ param Ġobj ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġpublic Ġfun Ġinsert ( obj : ĠT ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġinsertion Bounds Ġ= Ġobj . get Bounds () ĊĊĠĠĠĠĠĠĠ Ġ// ĠCheck Ġif Ġwe Ġare Ġalready Ġsplit ĊĠĠĠĠĠĠĠ Ġif Ġ( this . children [ 0 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġthis . get IndexOf Container ( insertion Bounds ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( index Ġ!= Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . children [ index ]?. insert ( obj ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠAt Ġthis Ġpoint , Ġwe Ġknow Ġthat Ġeither Ġthe Ġobject Ġdoesn 't Ġfit Ġne at ly Ġinto Ġone Ġof Ġour Ġcontainers , Ġor Ġwe Ġhaven 't Ġsplit Ġyet . ĊĠĠĠĠĠĠĠ Ġthis . objects . add ( obj ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠLet 's Ġsee Ġif Ġwe Ġhave Ġtoo Ġmany Ġobjects Ġavailable ĊĠĠĠĠĠĠĠ Ġif Ġ( this . objects . size () Ġ> Ġthis . max Objects Per Leaf ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( this . children [ 0 ] Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . split () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġto Remove Ġ= ĠHashSet < T >() ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . objects . forEach Ġ{ Ġcurrent Object Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġthis . get IndexOf Container ( current Object . get Bounds ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( index Ġ!= ĠP ARENT _ INDEX ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . children [ index ]?. insert ( current Object ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġto Remove . add ( current Object ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġto Remove . forEach Ġ{ Ġcurrent Object Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . objects . remove ( current Object ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġpublic Ġfun Ġretrieve ( bounds : ĠRectangle ): ĠCollection < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġreturn Objects Ġ= ĠHashSet < T >() ĊĊĠĠĠĠĠĠĠ Ġ// ĠFor Ġeach Ġobject Ġin Ġmy Ġcollection , Ġif Ġit Ġintersect s Ġthe Ġgiven Ġbounds , Ġadd Ġit Ġto Ġthe Ġreturn Ġcollection ĊĠĠĠĠĠĠĠ Ġthis . objects ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. filter Ġ{ Ġcurrent Object Ġ-> Ġbounds . intersect s ( current Object . get Bounds ()) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. forEach Ġ{ Ġcurrent Object Ġ-> Ġreturn Objects . add ( current Object ) Ġ} ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( child Ġin Ġthis . children ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( child Ġ!= Ġnull Ġ&& Ġbounds . intersect s ( child . bounds )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Objects . addAll ( child . retrieve ( bounds )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġreturn Objects ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġpublic Ġfun Ġremove ( obj : ĠT ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( this . objects . contains ( obj )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . objects . remove ( obj ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( child Ġin Ġthis . children ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġchild ?. remove ( obj ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠIf Ġthis Ġtakes Ġour Ġtotal Ġcount Ġto Ġbelow Ġthe Ġmaximum , Ġwe Ġcan Ġcollapse Ġthe Ġchild Ġquad trees ĊĠĠĠĠĠĠĠ Ġif Ġ( this . size () Ġ<= Ġthis . max Objects Per Leaf ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . re combine () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġpublic Ġfun Ġclear () Ġ{ ĊĠĠĠĠĠĠĠ Ġthis . objects . clear () ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġchildren . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġthis . children [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . clear () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . children [ i ] Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġpublic Ġfun Ġsize (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcount Ġ= Ġthis . objects . size () ĊĊĠĠĠĠĠĠĠ Ġif Ġ( this . children [ 0 ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( child Ġin Ġthis . children ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcount Ġ+= Ġchild ?. size () Ġ?: Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġcount ĊĠĠĠ Ġ} ĊĊĊĠĠĠ Ġ// ĠPrivate ĠMethods ĊĠĠĠ Ġprivate Ġfun Ġsplit () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsub Width Ġ= Ġthis . bounds . width Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġval Ġsub Height Ġ= Ġthis . bounds . height Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġval Ġx Ġ= Ġthis . bounds . x ĊĠĠĠĠĠĠĠ Ġval Ġy Ġ= Ġthis . bounds . y ĊĊĠĠĠĠĠĠĠ Ġthis . children [ TOP _ LEFT _ INDEX ] Ġ= ĠQuad tree < T >( Rectangle ( x , Ġy , Ġsub Width , Ġsub Height )) Ġ// ĠTop ĠLeft ĊĠĠĠĠĠĠĠ Ġthis . children [ TOP _ RIGHT _ INDEX ] Ġ= ĠQuad tree < T >( Rectangle ( x Ġ+ Ġsub Width , Ġy , Ġsub Width , Ġsub Height )) Ġ// ĠTop ĠRight ĊĠĠĠĠĠĠĠ Ġthis . children [ BOTTOM _ LEFT _ INDEX ] Ġ= ĠQuad tree < T >( Rectangle ( x , Ġy Ġ+ Ġsub Height , Ġsub Width , Ġsub Height )) Ġ// ĠBottom ĠLeft ĊĠĠĠĠĠĠĠ Ġthis . children [ BOTTOM _ RIGHT _ INDEX ] Ġ= ĠQuad tree < T >( Rectangle ( x Ġ+ Ġsub Width , Ġy Ġ+ Ġsub Height , Ġsub Width , Ġsub Height )) Ġ// ĠBottom ĠRight ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġre combine () Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( this . children [ 0 ] Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġthis . children . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġchild Ġ= Ġthis . children [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . objects . addAll ( child ?. retrieve ( child ?. bounds Ġ?: ĠRectangle ()) Ġ?: Ġset Of ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . children [ i ] Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġget IndexOf Container ( rect : ĠRectangle ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġthis . children . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( this . children [ i ] Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( this . children [ i ]?. bounds ?. contains ( rect ) Ġ?: Ġfalse ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġi ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn ĠP ARENT _ INDEX ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĊĠĠĠĠĠĠĠ Ġ// ĠConstants ĊĠĠĠĠĠĠĠ Ġpublic Ġval ĠDEFAULT _ MAX _ OBJECTS _ PER _ LEAF : ĠInt Ġ= Ġ 1 0 ĊĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠP ARENT _ INDEX Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠTOP _ LEFT _ INDEX Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠTOP _ RIGHT _ INDEX Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠBOTTOM _ LEFT _ INDEX Ġ= Ġ 2 ĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠBOTTOM _ RIGHT _ INDEX Ġ= Ġ 3 ĊĠĠĠ Ġ} Ċ } Ċ