package Ġjp . seo . station . ek is ag as u . search čĊč Ċ import Ġjp . seo . station . ek is ag as u . Station č Ċ import Ġjp . seo . station . ek is ag as u . core . Station Dao č Ċ import Ġkotlinx . coroutines . sync . Mutex č Ċ import Ġkotlinx . coroutines . sync . with Lock č Ċ import Ġkotlin . math . PI č Ċ import Ġkotlin . math . abs č Ċ import Ġkotlin . math . asin č Ċ import Ġkotlin . math . cos č Ċ import Ġkotlin . math . max č Ċ import Ġkotlin . math . sin čĊč Ċ /** čĊ Ġ* Ġ@ author ĠSe o - 4 d 6 9 6 b 7 5 čĊ Ġ* Ġ@ version Ġ 2 0 2 0 / 1 2 / 1 8 . čĊ Ġ* Ġk d - tree ãģ«ãĤĪ ãĤĭ æľĢè¿ĳ åĤ į æİ¢ ç´¢ ãĥĩãĥ¼ãĤ¿ æ§ĭ éĢł . čĊ Ġ* Ġ åĨħéĥ¨ ãģ§ è¨Ī ç®Ĺ ãģĻãĤĭ è·Ŀ éĽ ¢ ãģ® ç¨® é¡ŀ : čĊ Ġ* Ġ( 1 ) Ġsphere Ġ== Ġfalse Ġ ç· ¯ åº¦ çµ Į åº¦ ãĤĴ ãģĿãģ® ãģ¾ ãģ¾ çĽ´ äº¤ åº§ æ¨Ļ ç³» ãģ« æĬķ å½± ãģĹãģŁ å¹³ éĿ¢ çĬ¶ ãģ§ ãģ® ãĥ ¦ ãĥ¼ ãĤ¯ãĥª ãĥĥãĥī è·Ŀ éĽ ¢ čĊ Ġ* Ġ( 2 ) Ġsphere Ġ== Ġtrue Ġ Ġ åľ° çĲĥ ãĤĴ å®Įåħ¨ ãģª çĲĥ ä½ĵ ãģ¨ ä» ® å®ļ ãģĹãģ¦ è¨Ī ç®Ĺ ãģĹãģŁ å¤§ åĨ Ĩ è·Ŀ éĽ ¢ čĊ Ġ*/ č Ċ class ĠK d Tree ( čĊĠĠĠ Ġprivate Ġval Ġdatabase : ĠStation Dao , č Ċ ) Ġ{ čĊčĊĠĠĠ Ġprivate Ġvar Ġ_ root : ĠNode Adapter ? Ġ= Ġnull čĊčĊĠĠĠ Ġ// Ġmutex Ġlock Ġobj Ġwhen Ġchecking Ġand Ġloading Ġtree - segment Ġdata , Ġin Ġorder Ġto Ġavoid Ġduplicated Ġoperations čĊĠĠĠ Ġprivate Ġval Ġlock Ġ= ĠMutex () čĊčĊĠĠĠ Ġprivate Ġsuspend Ġfun Ġget Root (): ĠNode Adapter Ġ= Ġlock . with Lock Ġ{ čĊĠĠĠĠĠĠĠ Ġ_ root Ġ?: Ġrun Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdata Ġ= Ġdatabase . get Tree Segment (" root ") čĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmap : ĠMutable Map < Int , ĠStation Node > Ġ= ĠHashMap () čĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( s Ġin Ġdata . nodes ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmap [ s . code ] Ġ= Ġs čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= ĠNode Adapter ( 0 , Ġdata . root , Ġmap ) čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġnode čĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode čĊĠĠĠĠĠĠĠ Ġ} čĊĠĠĠ Ġ} čĊčĊĠĠĠ Ġprivate Ġdata Ġclass ĠNode ( čĊĠĠĠĠĠĠĠ Ġval Ġdepth : ĠInt , čĊĠĠĠĠĠĠĠ Ġval Ġlat : ĠDouble , čĊĠĠĠĠĠĠĠ Ġval Ġlng : ĠDouble , čĊĠĠĠĠĠĠĠ Ġval Ġcode : ĠInt , čĊĠĠĠĠĠĠĠ Ġval Ġleft : ĠNode Adapter ?, čĊĠĠĠĠĠĠĠ Ġval Ġright : ĠNode Adapter ? čĊĠĠĠ Ġ) čĊčĊĠĠĠ Ġprivate Ġinner Ġclass ĠNode Adapter ( čĊĠĠĠĠĠĠĠ Ġval Ġdepth : ĠInt , čĊĠĠĠĠĠĠĠ Ġval Ġcode : ĠInt , čĊĠĠĠĠĠĠĠ Ġnodes : ĠMap < Int , ĠStation Node > čĊĠĠĠ Ġ) Ġ{ čĊčĊĠĠĠĠĠĠĠ Ġprivate Ġvar Ġ_ node : ĠNode ? Ġ= Ġnull čĊĠĠĠĠĠĠĠ Ġprivate Ġvar Ġsegment Name : ĠString ? Ġ= Ġnull čĊčĊĠĠĠĠĠĠĠ Ġinit Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġbuild ( nodes ) čĊĠĠĠĠĠĠĠ Ġ} čĊčĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġbuild ( nodes : ĠMap < Int , ĠStation Node >) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdata Ġ= Ġnodes . getValue ( code ) čĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( data . segment Ġ!= Ġnull ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsegment Name Ġ= Ġdata . segment čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġleft Ġ= Ġdata . left ?. let Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠNode Adapter ( depth Ġ+ Ġ 1 , Ġit , Ġnodes ) čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġright Ġ= Ġdata . right ?. let Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠNode Adapter ( depth Ġ+ Ġ 1 , Ġit , Ġnodes ) čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlat Ġ= Ġdata . lat Ġ?: Ġthrow ĠRuntimeException (" lat Ġnot Ġfound ") čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlng Ġ= Ġdata . lng Ġ?: Ġthrow ĠRuntimeException (" lng Ġnot Ġfound ") čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis ._ node Ġ= ĠNode ( depth , Ġlat , Ġlng , Ġcode , Ġleft , Ġright ) čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠ Ġ} čĊčĊĠĠĠĠĠĠĠ Ġsuspend Ġfun Ġnode (): ĠNode Ġ= Ġlock . with Lock Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ node Ġ?: Ġkotlin . run Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsegment Ġ= Ġdatabase . get Tree Segment ( čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsegment Name Ġ?: Ġthrow ĠRuntimeException (" segment - name Ġnot Ġfound ") čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( segment . root Ġ!= Ġthis . code ) Ġthrow ĠRuntimeException (" root Ġmismatch Ġname :$ segment Name ") čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmap : ĠMutable Map < Int , ĠStation Node > Ġ= ĠHashMap < Int , ĠStation Node >() čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( s Ġin Ġsegment . nodes ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmap [ s . code ] Ġ= Ġs čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbuild ( map ) čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġ_ node Ġ?: Ġthrow ĠRuntimeException (" node Ġnot Ġinitialized ") čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsegment Name Ġ= Ġnull čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠ Ġ} čĊĠĠĠ Ġ} čĊčĊĠĠĠ Ġprivate Ġdata Ġclass ĠSearch Properties ( čĊĠĠĠĠĠĠĠ Ġval Ġlat : ĠDouble , čĊĠĠĠĠĠĠĠ Ġval Ġlng : ĠDouble , čĊĠĠĠĠĠĠĠ Ġval Ġk : ĠInt , čĊĠĠĠĠĠĠĠ Ġval Ġr : ĠDouble , čĊĠĠĠĠĠĠĠ Ġval Ġsphere : ĠBoolean , čĊĠĠĠ Ġ) Ġ{ čĊĠĠĠĠĠĠĠ Ġval Ġlist : ĠMutable List < Neighbor Node > Ġ= ĠArrayList () čĊĠĠĠ Ġ} čĊčĊĠĠĠ Ġprivate Ġdata Ġclass ĠNe ighbor Node ( čĊĠĠĠĠĠĠĠ Ġval Ġcode : ĠInt , čĊĠĠĠĠĠĠĠ Ġval Ġdist : ĠDouble čĊĠĠĠ Ġ) čĊčĊĠĠĠ Ġclass ĠSearch Result ( čĊĠĠĠĠĠĠĠ Ġval Ġlat : ĠDouble , čĊĠĠĠĠĠĠĠ Ġval Ġlng : ĠDouble , čĊĠĠĠĠĠĠĠ Ġval Ġk : ĠInt , čĊĠĠĠĠĠĠĠ Ġval Ġr : ĠDouble , čĊĠĠĠĠĠĠĠ Ġval Ġstations : ĠList < Station > čĊĠĠĠ Ġ) čĊčĊĠĠĠ Ġsuspend Ġfun Ġsearch ( čĊĠĠĠĠĠĠĠ Ġlat : ĠDouble , čĊĠĠĠĠĠĠĠ Ġlng : ĠDouble , čĊĠĠĠĠĠĠĠ Ġk : ĠInt , čĊĠĠĠĠĠĠĠ Ġr : ĠDouble , čĊĠĠĠĠĠĠĠ Ġsphere : ĠBoolean Ġ= Ġfalse čĊĠĠĠ Ġ): ĠSearch Result Ġ{ čĊĠĠĠĠĠĠĠ Ġval Ġprop Ġ= ĠSearch Properties ( lat , Ġlng , Ġk , Ġr , Ġsphere ) čĊĠĠĠĠĠĠĠ Ġsearch ( getRoot (), Ġprop ) čĊĠĠĠĠĠĠĠ Ġval Ġindices Ġ= Ġprop . list . map Ġ{ Ġn Ġ-> Ġn . code Ġ} čĊĠĠĠĠĠĠĠ Ġval Ġdata Ġ= Ġdatabase . get St ations ( indices ) čĊĠĠĠĠĠĠĠ Ġval Ġstations Ġ= Ġindices . map Ġ{ Ġcode Ġ-> čĊĠĠĠĠĠĠĠĠĠĠĠ Ġdata . find Ġ{ Ġs Ġ-> Ġs . code Ġ== Ġcode Ġ} Ġ?: Ġthrow ĠNoSuch ElementException () čĊĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠ Ġreturn ĠSearch Result ( lat , Ġlng , Ġk , Ġr , Ġstations ) čĊĠĠĠ Ġ} čĊčĊĠĠĠ Ġprivate Ġsuspend Ġfun Ġsearch ( adapter : ĠNode Adapter ?, Ġprop : ĠSearch Properties ) Ġ{ čĊĠĠĠĠĠĠĠ Ġif Ġ( adapter Ġ== Ġnull ) Ġreturn čĊĠĠĠĠĠĠĠ Ġval Ġnode Ġ= Ġadapter . node () čĊĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġmeasure ( prop . lat , Ġprop . lng , Ġnode . lat , Ġnode . lng , Ġprop . sphere ) čĊĠĠĠĠĠĠĠ Ġvar Ġindex Ġ= Ġ- 1 čĊĠĠĠĠĠĠĠ Ġval Ġsize Ġ= Ġprop . list . size čĊĠĠĠĠĠĠĠ Ġif Ġ( size Ġ> Ġ 0 Ġ&& Ġd Ġ< Ġprop . list [ size Ġ- Ġ 1 ]. dist ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġindex Ġ= Ġsize Ġ- Ġ 1 čĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( index Ġ> Ġ 0 ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( d Ġ>= Ġprop . list [ index Ġ- Ġ 1 ]. dist ) Ġbreak čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġindex -- čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( size Ġ== Ġ 0 ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġindex Ġ= Ġ 0 čĊĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠ Ġif Ġ( index Ġ>= Ġ 0 ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġprop . list . add ( index , ĠNe ighbor Node ( node . code , Ġd )) čĊčĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* čĊĠĠĠĠĠĠĠĠĠĠĠ Ġprop . list Ġãģ« è·Ŀ éĽ ¢ æĺ ĩ éłĨ ãģ« æł¼ ç´ į ãģķãĤĮãģŁ çµĲæŀľ ãģ«éĸ¢ ãģĹãģ¦ ãĢģ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( i ) ĠãĤµ ãĤ¤ãĤº ãģĮ Ġk Ġ ä»¥ä¸Ĭ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( ii ) Ġ è·Ŀ éĽ ¢ Ġr Ġä»¥ åĨħ ãģ¯ ãģĻãģ¹ãģ¦ åĲ« ãģ¾ ãĤĮãĤĭ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġãģ® ä¸ ¡ æĿ¡ä»¶ ãĤĴ æº Ģ ãģŁ ãģĻ čĊĠĠĠĠĠĠĠĠĠĠĠĠ Ġ*/ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( size Ġ>= Ġprop . k Ġ&& Ġprop . list [ size ]. dist Ġ> Ġprop . r ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprop . list . remove At ( size ) čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠ Ġval Ġx Ġ= Ġ( node . depth Ġ% Ġ 2 Ġ== Ġ 0 ) čĊĠĠĠĠĠĠĠ Ġval Ġvalue Ġ= Ġif Ġ( x ) Ġprop . lng Ġelse Ġprop . lat čĊĠĠĠĠĠĠĠ Ġval Ġthreshold Ġ= Ġif Ġ( x ) Ġnode . lng Ġelse Ġnode . lat čĊĠĠĠĠĠĠĠ Ġsearch ( if Ġ( value Ġ< Ġthreshold ) Ġnode . left Ġelse Ġnode . right , Ġprop ) čĊĠĠĠĠĠĠĠ Ġ/* čĊĠĠĠĠĠĠĠĠ Ġcalc Ġclosed Ġdistance Ġto Ġboundary , Ġwhich Ġis čĊĠĠĠĠĠĠĠĠĠĠ Ġ( 1 ) Ġx Ġ== Ġtrue ĠĠĠ Ġline Ġof Ġlongitude Ġ= Ġnode . lng čĊĠĠĠĠĠĠĠĠĠĠ Ġ( 2 ) Ġx Ġ== Ġfalse ĠĠ Ġline Ġof Ġlatitude Ġ= Ġnode . lat čĊĠĠĠĠĠĠĠĠ Ġ*/ čĊĠĠĠĠĠĠĠ Ġval Ġclosed Dist Ġ= Ġif Ġ( prop . sphere ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( x ) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ/* čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ çµ Į ç· ļ ãģ¾ãģ§ ãģ® è·Ŀ éĽ ¢ ãģ¯ ç· ¯ ç· ļ ãģ«ãģ¯ ãģª ãĤī ãģªãģĦ ï¼Ī ç· ¯ åº¦ ä¾Ŀ åŃĺ ãģĤãĤĬ ï¼ī čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ çĲĥ éĿ¢ ä¸ī è§Ĵ æ³ķ ãģ§ è¨Ī ç®Ĺ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ*/ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlng Ġ= ĠPI Ġ* Ġabs ( prop . lng Ġ- Ġnode . lng ) Ġ/ Ġ 1 8 0 . 0 čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlat Ġ= ĠPI Ġ* Ġprop . lat Ġ/ Ġ 1 8 0 . 0 čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSP HERE _ RADIUS Ġ* Ġas in ( sin ( lng ) Ġ* Ġcos ( lat )) čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ/* čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ ç· ¯ ç· ļ ãģ¯ æ¥ µ ãĤĴ ä¸Ńå¿ĥ ãģ¨ ãģĻãĤĭ åĨ Ĩ ãģł ãģĭãĤī åº§ æ¨Ļ ( prop . lat , Ġprop . lng ) ãģ¨ æ¥ µ ãĤĴ çµĲ ãģ ¶ çĽ´ ç· ļ ä¸Ĭ ãģ§ ãģ® çĽ® æ¨Ļ ç· ¯ åº¦ ãģ¾ãģ§ ãģ® è·Ŀ éĽ ¢ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ ãģĿãģ® çĽ´ ç· ļ ãģ¯ çµ Į ç· ļ ãģł ãģĭãĤī åįĺ ç´ Ķ ãģ« ç· ¯ åº¦ å·® ãģĮ ä¸Ńå¿ĥ ãĤĴ è¦ĭ è¾¼ ãĤĢ è§Ĵ ãģ« ãģªãĤĭ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ*/ čĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSP HERE _ RADIUS Ġ* ĠPI Ġ* Ġabs ( prop . lat Ġ- Ġnode . lat ) Ġ/ Ġ 1 8 0 . 0 čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} čĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* čĊĠĠĠĠĠĠĠĠĠĠĠ Ġ çĽ´ äº¤ åº§ æ¨Ļ ç³» ãĤĴ ä» ® å®ļ ãģĻãĤĭ åł´åĲĪãģ¯ åįĺ ç´ Ķ ãģª ãĥ ¦ ãĥ¼ ãĤ¯ãĥª ãĥĥãĥī è·Ŀ éĽ ¢ ãģ® å¤§å°ı ãģ§ èĢĥ ãģĪãĤĭ ãģŁãĤģ ãĢģ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġæ¯ Ķ è¼ ĥ åº§ æ¨Ļ åĢ¤ ãģ® å·® ãģ® çµ ¶ å¯¾ åĢ¤ čĊĠĠĠĠĠĠĠĠĠĠĠĠ Ġ*/ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġabs ( value Ġ- Ġthreshold ) čĊĠĠĠĠĠĠĠ Ġ} čĊčĊĠĠĠĠĠĠĠ Ġif Ġ( closed Dist Ġ< Ġmax ( prop . list [ prop . list . size Ġ- Ġ 1 ]. dist , Ġprop . r )) Ġ{ čĊĠĠĠĠĠĠĠĠĠĠĠ Ġsearch ( if Ġ( value Ġ< Ġthreshold ) Ġnode . right Ġelse Ġnode . left , Ġprop ) čĊĠĠĠĠĠĠĠ Ġ} čĊĠĠĠ Ġ} čĊčĊč Ċ } čĊčĊčĊ