package Ġcom . ext ol lit . g aming . ai . path . model Ċ Ċ import Ġcom . ext ol lit . g aming . ai . path . node . Node Ċ import Ġcom . ext ol lit . g aming . ai . path . vector . Three Dimension al Int Vector Ċ import Ġjava . util .* Ċ import Ġkotlin . math . ceil Ċ import Ġkotlin . math . sqrt Ċ Ċ /** Ċ Ġ* ĠA Ġqueue Ġof Ġ[ Node ] s Ċ Ġ*/ Ċ class ĠSorted Node Queue Ġ{ ĊĠĠĠ Ġprivate Ġval Ġlist Ġ= ĠArrayList < Node >( 8 ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdds Ġa Ġnode Ġto Ġthis Ġsorted Ġqueue Ġwithout Ġthe Ġoverhead Ġof Ġchecks . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġnode ĠThe Ġ[ Node ] Ġto Ġadd Ġto Ġthis Ġlist ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ return ĠIf Ġadding Ġthis Ġnode Ġto Ġthis Ġsorted Ġqueue Ġwas Ġsuccessful ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġfast Add ( node : ĠNode ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ(! node . index ( list . size )) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġlist . add ( node ) ĊĠĠĠĠĠĠĠ Ġsort Back ( node . index (). toInt ()) ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdds Ġa Ġnode Ġto Ġthis Ġsorted Ġqueue / ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġpoint ĠThe Ġ[ Node ] Ġto Ġadd Ġto Ġthis Ġlist ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ return ĠIf Ġadding Ġthis Ġnode Ġwas Ġsuccessful ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ see Ġ[ fast Add ] Ġfor Ġadding Ġnodes Ġwithout Ġthe Ġextra Ġconditional Ġoverhead . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġadd ( point : ĠNode ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġcheck (! point . assigned ()) Ġ{ Ġ" Point Ġis Ġalready Ġassigned " Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( fast Add ( point )) Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġval Ġlist Ġ= Ġlist ĊĠĠĠĠĠĠĠ Ġval Ġsize Ġ= Ġsize ĊĠĠĠĠĠĠĠ Ġval Ġi Ġ= Ġlist . list Iterator ( size ) ĊĠĠĠĠĠĠĠ Ġvar Ġamount Ġ= Ġceil (( size . toFloat () Ġ* ĠC ULL _ THRESHOLD ). toDouble ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. toInt () ĊĠĠĠĠĠĠĠ Ġwhile Ġ( amount Ġ> Ġ 0 Ġ&& Ġi . has Previous ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi . previous (). un assign () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi . remove () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ-- amount ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġfast Add ( point ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemoves Ġall Ġelements Ġfrom Ġthis Ġqueue ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġclear () Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( node Ġin Ġlist ) Ġnode . un assign () ĊĠĠĠĠĠĠĠ Ġlist . clear () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠChecks Ġif Ġthis Ġqueue Ġis Ġempty . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval ĠisEmpty : ĠBoolean ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġlist . isEmpty () ĊĊĠĠĠ Ġfun Ġtrim From ( source : ĠNode ): ĠNode Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( source . orphan ed ()) Ġreturn Ġsource ĊĠĠĠĠĠĠĠ Ġval Ġroot 0 Ġ= Ġsource . root () ĊĠĠĠĠĠĠĠ Ġval Ġdd Ġ= Ġsource . coordinates . sub Of ( root 0 . coordinates ) ĊĠĠĠĠĠĠĠ Ġval Ġlist : ĠMutable List < Node > Ġ= Ġlist ĊĠĠĠĠĠĠĠ Ġval Ġlength 0 Ġ= Ġsource . length () ĊĠĠĠĠĠĠĠ Ġval Ġpath Ġ= ĠStack < Node ?> () ĊĠĠĠĠĠĠĠ Ġval Ġtree Trans itional Ġ= ĠTree Trans itional ( source ) ĊĠĠĠĠĠĠĠ Ġval Ġi Ġ= Ġlist . list Iterator () ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhead Ġ= Ġi . next () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġpoint Ġ= Ġhead ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ(! point . orphan ed ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠSafe Ġto Ġcall Ġ-- Ġparent Ġis Ġnot Ġan Ġorphan . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoint Ġ= Ġpoint . parent !! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpath . push ( point ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( point Ġ=== Ġsource ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ(! path . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠTODO Ġcheck Ġif Ġsafe ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoint Ġ= Ġpath . pop () !! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlength Ġ= Ġpoint . length () Ġ- Ġlength 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoint . length ( length ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlength Ġ= Ġhead . length () Ġ- Ġlength 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhead . length ( length ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhead . index ( i . previous Index ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġroot : ĠNode ? Ġ= Ġif Ġ( path . isEmpty ()) Ġhead Ġelse Ġpath . pop () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( head Ġ=== Ġpoint Ġ|| Ġhead . coordinates . sub Of ( point . coordinates ). dot ( dd ) Ġ<= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhead . dirty ( true ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ(! path . isEmpty ()) Ġpath . pop () !!. dirty ( true ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtree Trans itional . queue ( head , Ġroot ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhead . index ( i . previous Index ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! path . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbranch Ġ= Ġpath . pop () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbranch !!. dirty ( true ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtree Trans itional . queue ( branch , Ġroot ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi . remove () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpath . clear () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhead . un assign () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhead . visited ( false ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġtree Trans itional . finish ( this ) ĊĠĠĠĠĠĠĠ Ġreturn Ġroot 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġc ull Branch ( ancestor : ĠNode ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġlist : ĠMutable List < Node > Ġ= Ġlist ĊĠĠĠĠĠĠĠ Ġval Ġstack Ġ= ĠStack < Node >() ĊĠĠĠĠĠĠĠ Ġval Ġi Ġ= Ġlist . list Iterator () ĊĠĠĠĠĠĠĠ Ġval Ġcul led : ĠMutable List < Node > Ġ= ĠLinkedList () ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhead Ġ= Ġi . next () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġpoint Ġ= Ġhead ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ(! point . orphan ed () Ġ&& Ġpoint Ġ!== Ġancestor ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠSafe Ġto Ġcall Ġ-- Ġthe Ġpoint Ġhas Ġa Ġparent , Ġits Ġnot Ġan Ġorphan . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoint Ġ= Ġpoint . parent !! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstack . push ( point ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( point Ġ!== Ġancestor ) Ġhead . index ( i . previous Index ()) Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi . remove () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhead . un assign () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcul led . add ( head ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcul led . addAll ( stack ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstack . clear () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( node Ġin Ġcul led ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . reset () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . visited ( false ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGets Ġan ĠUn modifiable ĠList Ġof Ġall Ġnodes Ġin Ġthis Ġqueue . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ return Ġun modifiable Ġlist Ġof Ġall Ġnodes Ġin Ġthis Ġsorted Ġqueue . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġview (): ĠList < Node ?> Ġ= ĠCollections . unmodifiable List ( list ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠGets Ġthe Ġnode Ġon Ġthe Ġtop Ġof Ġthis Ġstack . ĊĠĠĠĠ Ġ* ĠThis Ġnode Ġwas Ġalso Ġthe Ġfirst Ġto Ġenter Ġthis Ġstack Ġout Ġof Ġevery Ġother Ġstack . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġnode Ġat Ġthe Ġtop Ġof Ġthe Ġstack . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġtop (): ĠNode Ġ= Ġlist [ 0 ] ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemoves Ġand Ġreturns Ġthe Ġoldest Ġelement Ġin Ġthis Ġstack . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ return ĠThe Ġoldest Ġelement Ġ( most Ġwaiting Ġelement ) Ġin Ġthis Ġstack . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġde queue (): ĠNode Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġlist Ġ= Ġlist ĊĠĠĠĠĠĠĠ Ġval Ġpoint : ĠNode ? ĊĠĠĠĠĠĠĠ Ġif Ġ( list . size Ġ== Ġ 1 ) Ġpoint Ġ= Ġlist . remove At ( 0 ) Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpoint Ġ= Ġlist . set ( 0 , Ġlist . remove At ( list . size Ġ- Ġ 1 )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsort Forward ( 0 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġpoint . un assign () ĊĠĠĠĠĠĠĠ Ġreturn Ġpoint ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġnext Contains ( ancestor : ĠNode ?): ĠBoolean Ġ= ĊĠĠĠĠĠĠĠ Ġlist [ 0 ]. contains ( ancestor ) ĊĊĠĠĠ Ġprivate Ġfun Ġsort Back ( index : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġmutable Index Ġ= Ġindex ĊĠĠĠĠĠĠĠ Ġval Ġlist Ġ= Ġlist ĊĠĠĠĠĠĠĠ Ġval Ġoriginal Point Ġ= Ġlist [ mutable Index ] ĊĠĠĠĠĠĠĠ Ġval Ġdistance Remaining Ġ= Ġoriginal Point . jo urney (). toInt () ĊĠĠĠĠĠĠĠ Ġval Ġoriginal Pass ibility Ġ= Ġoriginal Point . pass ibility () ĊĠĠĠĠĠĠĠ Ġwhile Ġ( mutable Index Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġi Ġ= Ġmutable Index Ġ- Ġ 1 Ġshr Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpoint Ġ= Ġlist [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpass ibility Ġ= Ġpoint . pass ibility () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( distance Remaining Ġ>= Ġpoint . jo urney () Ġ&& Ġoriginal Pass ibility Ġ== Ġpass ibility Ġ|| Ġoriginal Pass ibility . w orse Than ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpass ibility ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlist [ mutable Index ] Ġ= Ġpoint ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpoint . index ( mutable Index ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmutable Index Ġ= Ġi ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġlist [ mutable Index ] Ġ= Ġoriginal Point ĊĠĠĠĠĠĠĠ Ġoriginal Point . index ( mutable Index ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġsort Forward ( index : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġmutable Index Ġ= Ġindex ĊĠĠĠĠĠĠĠ Ġval Ġlist Ġ= Ġlist ĊĠĠĠĠĠĠĠ Ġval Ġoriginal Point Ġ= Ġlist [ mutable Index ] ĊĠĠĠĠĠĠĠ Ġval Ġdistance Remaining Ġ= Ġoriginal Point . jo urney (). toInt () ĊĠĠĠĠĠĠĠ Ġval Ġoriginal Pass ibility Ġ= Ġoriginal Point . pass ibility () ĊĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġi Ġ= Ġ 1 Ġ+ Ġ( mutable Index Ġshl Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġj Ġ= Ġi Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( i Ġ>= Ġlist . size ) Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpoint Alpha Ġ= Ġlist [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdist Alpha Ġ= Ġpoint Alpha . jo urney (). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpass ibility Alpha Ġ= Ġpoint Alpha . pass ibility () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpoint Beta : ĠNode ? ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdist Beta : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpass ibility Beta : ĠPass ibility ? ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( j Ġ>= Ġlist . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoint Beta Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdist Beta Ġ= ĠInt . MIN _ VALUE ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpass ibility Beta Ġ= ĠPass ibility . Pass ible ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoint Beta Ġ= Ġlist [ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdist Beta Ġ= Ġpoint Beta . jo urney (). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpass ibility Beta Ġ= Ġpoint Beta . pass ibility () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( dist Alpha Ġ< Ġdist Beta Ġ&& Ġpass ibility Alpha Ġ== Ġpass ibility Beta ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ|| Ġpass ibility Alpha . better Than ( pass ibility Beta ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( dist Alpha Ġ>= Ġdistance Remaining Ġ&& Ġpass ibility Alpha Ġ== Ġoriginal Pass ibility ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ|| Ġpass ibility Alpha . w orse Than ( original Pass ibility ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlist [ mutable Index ] Ġ= Ġpoint Alpha ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoint Alpha . index ( mutable Index ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmutable Index Ġ= Ġi ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( point Beta Ġ== Ġnull Ġ|| Ġdist Beta Ġ>= Ġdistance Remaining Ġ&& Ġpass ibility Alpha Ġ== Ġoriginal Pass ibility ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ|| Ġpass ibility Beta . w orse Than ( original Pass ibility ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlist [ mutable Index ] Ġ= Ġpoint Beta ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoint Beta . index ( mutable Index ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmutable Index Ġ= Ġj ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( true ) ĊĠĠĠĠĠĠĠ Ġlist [ mutable Index ] Ġ= Ġoriginal Point ĊĠĠĠĠĠĠĠ Ġoriginal Point . index ( mutable Index ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġappend To ( point : ĠNode , Ġparent : ĠNode , Ġtarget Point : ĠThree Dimension al Int Vector ): ĠBoolean Ġ= ĊĠĠĠĠĠĠĠ Ġappend To ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpoint , Ġparent , Ġsqrt ( Node . square Delta ( point , Ġtarget Point ). toDouble ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. toInt () ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠ Ġfun Ġappend To ( point : ĠNode , Ġparent : ĠNode , Ġremaining : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsquare Delta : ĠInt Ġ= ĠNode . square Delta ( parent , Ġpoint ) ĊĠĠĠĠĠĠĠ Ġval Ġlength Ġ= Ġpoint . length () ĊĠĠĠĠĠĠĠ Ġif Ġ(! point . assigned () Ġ|| Ġparent . length () Ġ+ Ġsquare Delta Ġ< Ġlength Ġ* Ġlength Ġ&& Ġ! point . pass ibility (). better Than ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġparent . pass ibility () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdistance 0 Ġ= Ġpoint . jo urney () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( point . appendTo ( parent , Ġsqrt ( square Delta . toDouble ()). toInt (), Ġremaining )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġres ort ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoint , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdistance 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġpoint . orphan () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġadd Length ( point : ĠNode , Ġdiff : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġjourney 0 Ġ= Ġpoint . jo urney () ĊĠĠĠĠĠĠĠ Ġpoint . add Length ( diff ) ĊĠĠĠĠĠĠĠ Ġreturn Ġres ort ( point , Ġjourney 0 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġres ort ( point : ĠNode ?, Ġjourney 0 : ĠByte ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġjourney Ġ= Ġpoint !!. jo urney (). toInt () ĊĊĠĠĠĠĠĠĠ Ġif Ġ( point . assigned ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( jo urney Ġ< Ġjourney 0 ) Ġsort Back ( point . index (). toInt ()) Ġelse Ġsort Forward ( point . index (). toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġadd ( point ) ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĠThe Ġsize Ġof Ġthis Ġ[ Sorted Node Queue ] Ġ*/ ĊĠĠĠ Ġval Ġsize : ĠInt ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġlist . size ĊĊĠĠĠ Ġval Ġroots : ĠSet < Node > ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġlist . map To ( HashSet ( 1 ), ĠNode :: root ) ĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ= Ġ"$ list " ĊĊĠĠĠ Ġoverride Ġfun Ġequals ( other : ĠAny ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( this Ġ=== Ġother ) Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġif Ġ( other Ġ== Ġnull Ġ|| Ġjava Class Ġ!= Ġother . java Class ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġval Ġthat Ġ= Ġother Ġas ĠSorted Node Queue ĊĠĠĠĠĠĠĠ Ġreturn Ġlist Ġ== Ġthat . list ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠhashCode (): ĠInt Ġ= Ġlist . hashCode () ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠC ULL _ THRESHOLD Ġ= Ġ 0 . 1 f ĊĠĠĠ Ġ} Ċ }