/* Ċ Ġ* ĠCopyright ĠÂ© Ġ 2 0 2 1 ĠE no ve a Ġ( fab ien . me ur isse @ en ove a . net ) Ċ Ġ* Ċ Ġ* Ġ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 Ġdil iv ia . s 2 . index . point Ċ Ċ import Ġcom . google . common . collect . Sorted Multi set Ċ import Ġcom . google . common . collect . Tree Multi set Ċ import Ġdil iv ia . s 2 . S 2 CellId Ċ import Ġdil iv ia . s 2 . S 2 Point Ċ import Ġdil iv ia . s 2 . S 2 Random Ċ import Ġdil iv ia . s 2 . region . S 2 Cell Union Ċ import Ġmu . Kotlin Logging Ċ import Ġorg . assertj . core . api . Assertions . assertThat Ċ import Ġorg . junit . jupiter . api . Test ĊĊ Ċ class ĠS 2 Point Index UnitTest Ġ{ ĊĊĠĠĠ Ġprivate Ġval Ġlogger Ġ= ĠKotlin Logging . logger Ġ{ Ġ} ĊĊĠĠĠ Ġprivate Ġval Ġindex : ĠS 2 Point Index < Int > Ġ= ĠS 2 Point Index () ĊĠĠĠ Ġprivate Ġval Ġcontents : ĠSorted Multi set < Point Data < Int >> Ġ= ĠTree Multi set . create () ĊĊĊĠĠĠ Ġfun Ġadd ( point : ĠS 2 Point , Ġdata : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġindex . add ( point , Ġdata ) ĊĠĠĠĠĠĠĠ Ġcontents . add ( Point Data ( point , Ġdata )) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġremove ( point : ĠS 2 Point , Ġdata : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠIf Ġthere Ġare Ġmultiple Ġcopies , Ġremove Ġonly Ġone . ĊĠĠĠĠĠĠĠ Ġcontents . remove ( Point Data ( point , Ġdata )) ĊĠĠĠĠĠĠĠ Ġreturn Ġindex . remove ( point , Ġdata ) Ġ Ġ// ĠInvalid ates Ġ" point ". ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġverify () Ġ{ ĊĠĠĠĠĠĠĠ Ġverify Contents () ĊĠĠĠĠĠĠĠ Ġverify Iterator Methods () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġverify Contents () Ġ{ ĊĠĠĠĠĠĠĠ Ġlogger . debug Ġ{ Ġ" Contents : Ġ${ contents . size } Ġelements " Ġ} ĊĠĠĠĠĠĠĠ Ġlogger . debug Ġ{ Ġ" Index : Ġ${ index . num Points ()} Ġelements " Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġremaining Ġ= ĠTree Multi set . create ( contents ) ĊĠĠĠĠĠĠĠ Ġval Ġiter Ġ= ĠS 2 Point Index . Iterator ( index ) ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ(! iter . done ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcurrent Point Data Ġ= Ġiter . point Data () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlogger . debug Ġ{ Ġ" Iteration Ġ$ i " Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlogger . debug Ġ{ Ġ" Current Ġpoint Ġ: Ġ$ current Point Data " Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlogger . debug Ġ{ Ġ" Point Ġremaining Ġocc uren ces : Ġ${ remaining . count ( current Point Data )}" Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġremoved Ġ= Ġremaining . remove ( current Point Data ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlogger . debug Ġ{ Ġ" Removed Ġfrom Ġremaining : Ġ$ removed " Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlogger . debug Ġ{ Ġ" Point Ġremaining Ġocc uren ces Ġafter Ġremoval : Ġ${ remaining . count ( current Point Data )}" Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlogger . debug Ġ{ Ġ" Remaining : Ġ${ remaining . size }" Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( removed ). isTrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġiter . next () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ++ i ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ ĠassertThat ( remaining . isEmpty ()). isTrue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġverify Iterator Methods () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġiter Ġ= Ġindex . iterator () ĊĠĠĠĠĠĠĠ ĠassertThat ( iter . prev ()). isFalse ĊĠĠĠĠĠĠĠ Ġiter . finish () ĊĠĠĠĠĠĠĠ ĠassertThat ( iter . done ()). isTrue ĊĊĠĠĠĠĠĠĠ Ġ// ĠIterate Ġthrough Ġall Ġthe Ġcells Ġin Ġthe Ġindex . ĊĠĠĠĠĠĠĠ Ġvar Ġprev _ cell id Ġ= ĠS 2 CellId . none ĊĠĠĠĠĠĠĠ Ġvar Ġmin _ cell id Ġ= ĠS 2 CellId . begin ( S 2 CellId . k Max Level ) ĊĠĠĠĠĠĠĠ Ġiter . begin () ĊĠĠĠĠĠĠĠ Ġwhile Ġ(! iter . done ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcell id Ġ= Ġiter . id () ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( S 2 CellId . from Point ( iter . point ())). isEqualTo ( cell id ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( cell id Ġ>= Ġprev _ cell id ). isTrue () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġiter 2 Ġ= Ġindex . iterator () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cell id Ġ== Ġprev _ cell id ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġiter 2 . seek ( cell id ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠGenerate Ġa Ġcell union Ġthat Ġcovers Ġthe Ġrange Ġof Ġempty Ġleaf Ġcells Ġbetween ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġlast Ġcell Ġand Ġthis Ġone . Ġ ĠThen Ġmake Ġsure Ġthat Ġsee king Ġto Ġany Ġof ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthose Ġcells Ġtakes Ġus Ġto Ġthe Ġimmediately Ġfollowing Ġcell . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cell id Ġ> Ġprev _ cell id ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( skipped Ġin ĠS 2 Cell Union . from Begin End ( min _ cell id , Ġcell id )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġiter 2 . seek ( skipped ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( iter 2 . id ()). isEqualTo ( cell id ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠTest ĠPre v (), ĠNext (), Ġand ĠSeek (). ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( prev _ cell id . isValid ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġiter 2 . seek ( iter . id ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( iter 2 . prev ()). isTrue () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( iter 2 . id ()). isEqualTo ( prev _ cell id ); ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġiter 2 . next (); ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( iter 2 . id ()). isEqualTo ( cell id ); ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġiter 2 . seek ( prev _ cell id ); ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( iter 2 . id ()). isEqualTo ( prev _ cell id ); ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprev _ cell id Ġ= Ġcell id ; ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmin _ cell id Ġ= Ġcell id . next () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġiter . next () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠ Ġ@ Test ĊĠĠĠ Ġfun Ġno Points () Ġ{ ĊĠĠĠĠĠĠĠ Ġverify () ĊĠĠĠ Ġ} ĊĊĠ Ġ@ Test ĊĠĠĠ Ġfun Ġduplicate Points () Ġ{ ĊĠĠĠĠĠĠĠ Ġrepeat ( 1 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġadd ( S 2 Point ( 1 , Ġ 0 , Ġ 0 ), Ġ 1 2 3 ); Ġ Ġ// ĠAll Ġpoints Ġhave Ġsame ĠData Ġargument . ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ ĠassertThat ( index . num Points ()). isEqualTo ( 1 0 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( contents . size ). isEqualTo ( 1 0 ) ĊĠĠĠĠĠĠĠ Ġverify () ĊĠĠĠĠĠĠĠ Ġ// ĠNow Ġremove Ġhalf Ġof Ġthe Ġpoints . ĊĠĠĠĠĠĠĠ Ġrepeat ( 5 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertThat ( remove ( S 2 Point ( 1 , Ġ 0 , Ġ 0 ), Ġ 1 2 3 )). isTrue () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġverify () ĊĠĠĠĠĠĠĠ ĠassertThat ( index . num Points ()). isEqualTo ( 5 ) ĊĠĠĠ Ġ} ĊĊĠ Ġ@ Test ĊĠĠĠ Ġfun Ġrandom Points () Ġ{ ĊĠĠĠĠĠĠĠ Ġrepeat ( 1 0 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġadd ( S 2 Random . random Point (), ĠS 2 Random . random Int ( 1 0 0 )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġverify (); ĊĠĠĠĠĠĠĠ Ġ// ĠNow Ġremove Ġsome Ġof Ġthe Ġpoints . ĊĠĠĠĠĠĠĠ Ġrepeat ( 1 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġiter Ġ= Ġindex . iterator () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġiter . seek ( S 2 Random . random CellId ( S 2 CellId . k Max Level )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( iter . done ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġremove ( iter . point (), Ġiter . data ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġverify (); ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠ Ġ@ Test ĊĠĠĠ Ġfun Ġempty Data () Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠVerify Ġthat Ġwhen ĠData Ġis Ġan Ġempty Ġclass , Ġno Ġspace Ġis Ġused . ĊĠĠĠĠĠĠĠ Ġ// assertEquals ( sizeof ( S 2 Point ), Ġsizeof ( S 2 Point Index < >:: Point Data )); ĊĊĠĠĠĠĠĠĠ Ġ// ĠVerify Ġthat Ġpoints Ġcan Ġbe Ġadded Ġand Ġremoved Ġwith Ġan Ġempty ĠData Ġclass . ĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= ĠS 2 Point Index < Int >() ĊĠĠĠĠĠĠĠ Ġindex . add ( S 2 Point ( 1 , Ġ 0 , Ġ 0 ), Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġindex . remove ( S 2 Point ( 1 , Ġ 0 , Ġ 0 ), Ġ 1 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( index . num Points ()). isEqualTo ( 0 ) ĊĠĠĠ Ġ} Ċ Ċ } Ċ