/* Ċ Ġ* ĠCopyright Ġ 2 0 2 0 ĠThe ĠAndroid ĠOpen ĠSource ĠProject Ċ Ġ* Ċ Ġ* Ġ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 Ġandroidx . collection Ċ Ċ import Ġkotlin . jvm . Jvm Over loads Ċ Ċ class ĠArray Set < E > Ċ @ Jvm Over loads Ġconstructor ( ĊĠĠĠ Ġcapacity : ĠInt Ġ= Ġ 0 Ċ ) Ġ: ĠMutable Collection < E >, ĠMutable Set < E > Ġ{ ĊĠĠĠ Ġconstructor ( set : ĠArray Set < out ĠE > ?) Ġ: Ġthis ( 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( set Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġadd All ( set ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġconstructor ( set : ĠCollection < E > ?) Ġ: Ġthis ( 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( set Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġadd All ( set ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġvar Ġhashes : ĠInt Array ĊĠĠĠ Ġprivate Ġvar Ġvalues : ĠArray < E ?> ĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( capacity Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhashes Ġ= ĠEMPTY _ INT S ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ@ Suppress (" UN CHECK ED _ CAST ") Ġ// ĠEmpty Ġarray . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalues Ġ= ĠEMPTY _ OBJECTS Ġas ĠArray < E ?> ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhashes Ġ= ĠInt Array ( capacity ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ@ Suppress (" UN CHECK ED _ CAST ") Ġ// ĠWe Ġonly Ġget / set Ġ" E " s Ġand Ġnull s . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalues Ġ= ĠarrayOf Null s < Any >( capacity ) Ġas ĠArray < E ?> ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġvar Ġ_ size : ĠInt Ġ= Ġ 0 ĊĊĠĠĠ Ġ@ Suppress (" NON _ FINAL _ MEMBER _ IN _ FINAL _ CLASS ") Ġ// ĠFor Ġj ap icmp . ĊĠĠĠ Ġopen Ġoverride Ġval Ġsize : ĠInt Ġget () Ġ= Ġ_ size ĊĊĠĠĠ Ġoverride Ġfun ĠisEmpty (): ĠBoolean Ġ= Ġ_ size Ġ== Ġ 0 ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġ@ throws ĠConcurrent Modification Exception Ġif Ġthe Ġset Ġhas Ġbeen Ġconcurrent ly Ġmodified . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Suppress (" NON _ FINAL _ MEMBER _ IN _ FINAL _ CLASS ") Ġ// ĠFor Ġj ap icmp . ĊĠĠĠ Ġopen Ġfun Ġensure Capacity ( minimum Capacity : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġold Size Ġ= Ġ_ size ĊĠĠĠĠĠĠĠ Ġif Ġ( hashes . size Ġ< Ġminimum Capacity ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhashes Ġ= Ġhashes . copyOf ( minimum Capacity ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalues Ġ= Ġvalues . copyOf ( minimum Capacity ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ(_ size Ġ!= Ġold Size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠConcurrent Modification Exception () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Suppress (" NON _ FINAL _ MEMBER _ IN _ FINAL _ CLASS ") Ġ// ĠFor Ġj ap icmp . ĊĠĠĠ Ġopen Ġfun ĠindexOf ( element : ĠE ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( element Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠindexOf Null () ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠindexOf ( element , Ġelement . hashCode ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġbinary Search ( hash : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġtry Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġhashes . binary Search ( size , Ġhash ) ĊĠĠĠĠĠĠĠ Ġ} Ġcatch Ġ(_ : ĠIndex OutOfBoundsException ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠConcurrent Modification Exception () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun ĠindexOf ( element : ĠE , Ġhash : ĠInt ) Ġ= ĠindexOf ( hash ) Ġ{ Ġit Ġ== Ġelement Ġ} ĊĠĠĠ Ġprivate Ġfun ĠindexOf Null () Ġ= ĠindexOf ( 0 ) Ġ{ Ġit Ġ== Ġnull Ġ} ĊĊĠĠĠ Ġprivate Ġinline Ġfun ĠindexOf ( hash : ĠInt , Ġpredicate : Ġ( E ?) Ġ-> ĠBoolean ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsize Ġ= Ġ_ size ĊĠĠĠĠĠĠĠ Ġif Ġ( size Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠImport ant Ġfast Ġcase : Ġif Ġnothing Ġis Ġin Ġhere , Ġnothing Ġto Ġlook Ġfor . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ 0 . inv () ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġbinary Search ( hash ) ĊĠĠĠĠĠĠĠ Ġif Ġ( index Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġindex Ġ// ĠNot Ġfound . ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( predicate ( values [ index ])) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġindex Ġ// ĠFound ! ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠSearch Ġmatching Ġhashes Ġafter Ġthe Ġindex . ĊĠĠĠĠĠĠĠ Ġvar Ġend Ġ= Ġindex Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( end Ġ< Ġsize Ġ&& Ġhashes [ end ] Ġ== Ġhash ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( predicate ( values [ end ])) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġend ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġend ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠSearch Ġmatching Ġhashes Ġbefore Ġthe Ġindex . ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġindex Ġ- Ġ 1 Ġdown To Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( hashes [ i ] Ġ!= Ġhash ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( predicate ( values [ i ])) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġi ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠKey Ġnot Ġfound Ġ-- Ġreturn Ġnegative Ġvalue Ġindicating Ġwhere Ġa ĊĠĠĠĠĠĠĠ Ġ// Ġnew Ġentry Ġfor Ġthis Ġkey Ġshould Ġgo . Ġ ĠWe Ġuse Ġthe Ġend Ġof Ġthe ĊĠĠĠĠĠĠĠ Ġ// Ġhash Ġchain Ġto Ġreduce Ġthe Ġnumber Ġof Ġarray Ġentries Ġthat Ġwill ĊĠĠĠĠĠĠĠ Ġ// Ġneed Ġto Ġbe Ġcopied Ġwhen Ġinserting . ĊĠĠĠĠĠĠĠ Ġreturn Ġend . inv () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Suppress (" NON _ FINAL _ MEMBER _ IN _ FINAL _ CLASS ") Ġ// ĠFor Ġj ap icmp . ĊĠĠĠ Ġopen Ġfun Ġvalue At ( index : ĠInt ): ĠE ? Ġ= Ġvalues [ index ] ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġ@ throws ĠConcurrent Modification Exception Ġif Ġthe Ġset Ġhas Ġbeen Ġconcurrent ly Ġmodified . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġadd ( element : ĠE ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġold Size Ġ= Ġ_ size ĊĊĠĠĠĠĠĠĠ Ġval Ġhash : ĠInt ĊĠĠĠĠĠĠĠ Ġvar Ġindex : ĠInt ĊĠĠĠĠĠĠĠ Ġif Ġ( element Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhash Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġindex Ġ= ĠindexOf Null () ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhash Ġ= Ġelement . hashCode () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġindex Ġ= ĠindexOf ( element , Ġhash ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( index Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġindex Ġ= Ġindex . inv () ĊĊĠĠĠĠĠĠĠ Ġ// ĠGrow Ġthe Ġarray Ġif Ġneeded . ĊĠĠĠĠĠĠĠ Ġif Ġ( old Size Ġ== Ġhashes . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Size Ġ= Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Size Ġ>= ĠBASE _ SIZE _ 2 X Ġ-> Ġold Size Ġ+ Ġ( old Size Ġshr Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Size Ġ>= ĠBASE _ SIZE Ġ-> ĠBASE _ SIZE _ 2 X ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> ĠBASE _ SIZE ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhashes Ġ= Ġhashes . copyOf ( new Size ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalues Ġ= Ġvalues . copyOf ( new Size ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠShift Ġthe Ġarray Ġif Ġneeded . ĊĠĠĠĠĠĠĠ Ġif Ġ( index Ġ< Ġold Size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhashes . copy Into ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhashes , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdestination Offset Ġ= Ġindex Ġ+ Ġ 1 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstartIndex Ġ= Ġindex , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend Index Ġ= Ġold Size ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalues . copy Into ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalues , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdestination Offset Ġ= Ġindex Ġ+ Ġ 1 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstartIndex Ġ= Ġindex , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend Index Ġ= Ġold Size ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( old Size Ġ!= Ġ_ size Ġ|| Ġindex Ġ>= Ġhashes . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠConcurrent Modification Exception () ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġhashes [ index ] Ġ= Ġhash ĊĠĠĠĠĠĠĠ Ġvalues [ index ] Ġ= Ġelement ĊĊĠĠĠĠĠĠĠ Ġ_ size ++ ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġadd All ( elements : ĠCollection < E >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġensure Capacity (_ size Ġ+ Ġelements . size ) ĊĠĠĠĠĠĠĠ Ġvar Ġadded Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġfor Ġ( element Ġin Ġelements ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġadded Ġ= Ġadded Ġor Ġadd ( element ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġadded ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Suppress (" NON _ FINAL _ MEMBER _ IN _ FINAL _ CLASS ") Ġ// ĠFor Ġj ap icmp . ĊĠĠĠ Ġopen Ġfun Ġadd All ( elements : ĠArray Set < E >) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġarray Size Ġ= Ġelements ._ size ĊĠĠĠĠĠĠĠ Ġif Ġ(_ size Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( array Size Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhashes Ġ= Ġelements . hashes . copyOf () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalues Ġ= Ġelements . values . copyOf () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ_ size Ġ= Ġarray Size ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġarray Size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadd ( elements . value At ( i ) !! ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġremove ( element : ĠE ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= ĠindexOf ( element ) ĊĠĠĠĠĠĠĠ Ġif Ġ( index Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġremove At ( index ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġ@ throws ĠConcurrent Modification Exception Ġif Ġthe Ġset Ġhas Ġbeen Ġconcurrent ly Ġmodified . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Suppress (" NON _ FINAL _ MEMBER _ IN _ FINAL _ CLASS ") Ġ// ĠFor Ġj ap icmp . ĊĠĠĠ Ġopen Ġfun Ġremove At ( index : ĠInt ): ĠE ? Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġold Size Ġ= Ġ_ size ĊĠĠĠĠĠĠĠ Ġval Ġvalue Ġ= Ġvalues [ index ] ĊĊĠĠĠĠĠĠĠ Ġ// ĠTODO Ġassert Ġold Size Ġ> Ġ 0 , Ġsafe Ġbecause Ġwe Ġwould Ġhave ĠIO OB E 'd Ġabove ĊĠĠĠĠĠĠĠ Ġif Ġ( old Size Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġclear () ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Size Ġ= Ġold Size Ġ- Ġ 1 ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġold Hashes Ġ= Ġhashes ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġold Values Ġ= Ġvalues ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġold Storage Size Ġ= Ġold Hashes . size ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( old Storage Size Ġ> ĠBASE _ SIZE _ 2 X Ġ&& Ġold Size Ġ< Ġold Storage Size Ġ/ Ġ 3 ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠSh rink ing Ġenough Ġto Ġreduce Ġsize Ġof Ġarrays . Ġ ĠWe Ġdon 't Ġallow Ġit Ġto ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġshrink Ġsmaller Ġthan ĠBASE _ SIZE _ 2 X Ġto Ġavoid Ġfl apping Ġbetween Ġthat Ġand ĠBASE _ SIZE . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Storage Size Ġ= Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Size Ġ> ĠBASE _ SIZE _ 2 X Ġ-> Ġold Size Ġ+ Ġ( old Size Ġshr Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> ĠBASE _ SIZE _ 2 X ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Hashes Ġ= ĠInt Array ( new Storage Size ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ@ Suppress (" UN CHECK ED _ CAST ") Ġ// ĠWe Ġonly Ġget / set Ġ" E " s Ġand Ġnull s . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Values Ġ= ĠarrayOf Null s < Any ? >( new Storage Size ) Ġas ĠArray < E ?> ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( index Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Hashes . copy Into ( new Hashes , Ġend Index Ġ= Ġindex ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Values . copy Into ( new Values , Ġend Index Ġ= Ġindex ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( index Ġ< Ġnew Size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Hashes . copy Into ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnew Hashes , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdestination Offset Ġ= Ġindex , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstartIndex Ġ= Ġindex Ġ+ Ġ 1 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend Index Ġ= Ġold Size ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Values . copy Into ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnew Values , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdestination Offset Ġ= Ġindex , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstartIndex Ġ= Ġindex Ġ+ Ġ 1 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend Index Ġ= Ġold Size ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhashes Ġ= Ġnew Hashes ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalues Ġ= Ġnew Values ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( index Ġ< Ġnew Size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Hashes . copy Into ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Hashes , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdestination Offset Ġ= Ġindex , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstartIndex Ġ= Ġindex Ġ+ Ġ 1 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend Index Ġ= Ġold Size ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Values . copy Into ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Values , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdestination Offset Ġ= Ġindex , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠstartIndex Ġ= Ġindex Ġ+ Ġ 1 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġend Index Ġ= Ġold Size ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġold Values [ new Size ] Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( old Size Ġ!= Ġ_ size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠConcurrent Modification Exception () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ size Ġ= Ġnew Size ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġvalue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġremove All ( elements : ĠCollection < E >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġremoved Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġfor Ġ( element Ġin Ġelements ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġremoved Ġ= Ġremoved Ġor Ġremove ( element ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġremoved ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Suppress (" NON _ FINAL _ MEMBER _ IN _ FINAL _ CLASS ") Ġ// ĠFor Ġj ap icmp . ĊĠĠĠ Ġopen Ġfun Ġremove All ( elements : ĠArray Set < out ĠE >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠTODO : ĠIf Ġarray Ġis Ġsufficient ly Ġlarge , Ġa Ġmarking Ġapproach Ġmight Ġbe Ġbene f icial . ĠIn Ġa Ġfirst ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġpass , Ġuse Ġthe Ġproperty Ġthat Ġthe Ġsets Ġare Ġsorted Ġby Ġhash Ġto Ġmake Ġthis Ġlinear Ġpasses ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġ( except Ġfor Ġhash Ġcollisions , Ġwhich Ġmeans Ġworst Ġcase Ġstill Ġn * m ), Ġthen Ġdo Ġone Ġcollection ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġpass Ġinto Ġa Ġnew Ġarray . ĠThis Ġavoids Ġbinary Ġsearches Ġand Ġexcess ive Ġmemcpy . ĊĊĠĠĠĠĠĠĠ Ġval Ġelements Size Ġ= Ġelements ._ size ĊĠĠĠĠĠĠĠ Ġval Ġoriginal Size Ġ= Ġ_ size ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġelements Size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġremove ( elements . value At ( i ) !! ) Ġ// ĠTODO Ġunsafe Cast ? ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġoriginal Size Ġ!= Ġ_ size ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġclear () Ġ{ ĊĠĠĠĠĠĠĠ Ġhashes Ġ= ĠEMPTY _ INT S ĊĠĠĠĠĠĠĠ Ġ@ Suppress (" UN CHECK ED _ CAST ") Ġ// ĠEmpty Ġarray . ĊĠĠĠĠĠĠĠ Ġvalues Ġ= ĠEMPTY _ OBJECTS Ġas ĠArray < E ?> ĊĠĠĠĠĠĠĠ Ġ_ size Ġ= Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġretain All ( elements : ĠCollection < E >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġremoved Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġ_ size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( values [ i ] Ġ! in Ġelements ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġremove At ( i ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġremoved Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġremoved ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġcontains ( element : ĠE ): ĠBoolean Ġ= ĠindexOf ( element ) Ġ>= Ġ 0 ĊĊĠĠĠ Ġoverride Ġfun Ġcontains All ( elements : ĠCollection < E >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġelements . all Ġ{ Ġit Ġin Ġthis Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġiterator (): ĠMutable Iterator < E > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠIterator (_ size ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġinner Ġclass ĠIterator ( size : ĠInt ) Ġ: ĠIndex Based Mutable Iterator < E >( size ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ@ Suppress (" UN CHECK ED _ CAST ") Ġ// ĠAssume Ġbase Ġiterator Ġonly Ġaccessing Ġvalid Ġindices . ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġget ( index : ĠInt ) Ġ= Ġvalues [ index ] Ġas ĠE ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġremove ( index : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġremove At ( index ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠBASE _ SIZE Ġ= Ġ 4 ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠBASE _ SIZE _ 2 X Ġ= ĠBASE _ SIZE Ġ* Ġ 2 ĊĠĠĠ Ġ} Ċ } Ċ