package Ġcombo . sat Ċ Ċ import Ġcombo . util . entry Ċ Ċ object ĠBit Array Factory Ġ: ĠInstance Factory Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġcreate ( size : ĠInt ) Ġ= ĠBit Array ( size ) Ċ } Ċ Ċ /** Ċ Ġ* ĠThis Ġuses Ġa Ġdense Ġint Ġarray Ġas Ġbacking Ġfor Ġ[ Instance ]. Ġ 3 2 Ġbit Ġints Ġare Ġused Ġinstead Ġof Ġ 6 4 Ġbits Ġdue Ġto ĠJavaScript Ċ Ġ* Ġinter oper ability . ĠThe Ġadvantage Ġof Ġbit array Ġis Ġlow Ġsize Ġbut Ġalso Ġfast Ġiteration Ġfor Ġsemi - sp rase Ġdata Ġbecause Ġints Ċ Ġ* Ġwith Ġ 0 - value Ġcan Ġbe Ġskipped Ġentirely . Ċ Ġ*/ Ċ class ĠBit Array Ġconstructor ( override Ġval Ġsize : ĠInt , Ġval Ġfield : ĠInt Array ) Ġ: ĠInstance Ġ{ ĊĊĠĠĠ Ġ// ĠNote Ġthis Ġcode Ġuses Ġa Ġlot Ġof Ġbit Ġsh ifts . ĠThe Ġmost Ġcommon Ġbeing Ġmask ing Ġby Ġ 0 x 1 F Ġand Ġsh ifting Ġright Ġby Ġ 5 . ĊĠĠĠ Ġ// Ġ Ġ- Ġsh ifting Ġby Ġ 5 Ġis Ġequivalent Ġto Ġdiv iding Ġby Ġ 3 2 Ġwhich Ġgives Ġthe Ġint - field Ġto Ġaccess ĊĠĠĠ Ġ// Ġ Ġ- Ġix Ġand Ġ 0 x 1 F Ġis Ġequivalent Ġto Ġmod ulus Ġby Ġ 3 2 Ġwhich Ġgives Ġthe Ġbit Ġin Ġa Ġspecific Ġint ĊĠĠĠ Ġ// ĠHence Ġthese Ġtwo Ġoperations Ġis Ġused Ġin Ġget / set ĊĊĠĠĠ Ġconstructor ( size : ĠInt ) Ġ: Ġthis ( size , ĠInt Array (( size Ġshr Ġ 5 ) Ġ+ Ġif Ġ( size Ġand Ġ 0 x 1 F Ġ> Ġ 0 ) Ġ 1 Ġelse Ġ 0 )) ĊĊĠĠĠ Ġoverride Ġval Ġword Size : ĠInt Ġget () Ġ= Ġthis . field . size ĊĊĠĠĠ Ġoverride Ġfun Ġcopy (): ĠBit Array Ġ= ĠBit Array ( size , Ġfield . copyOf ()) ĊĊĠĠĠ Ġoverride Ġfun ĠisSet ( ix : ĠInt ) Ġ= Ġ( field [ ix Ġshr Ġ 5 ] Ġ ush r Ġ( ix Ġand Ġ 0 x 1 F )) Ġand Ġ 1 Ġ== Ġ 1 ĊĊĠĠĠ Ġoverride Ġfun Ġflip ( ix : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġi Ġ= Ġix Ġshr Ġ 5 ĊĠĠĠĠĠĠĠ Ġfield [ i ] Ġ= Ġfield [ i ] Ġxor Ġ( 1 Ġshl Ġ( ix Ġand Ġ 0 x 1 F )) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġset ( ix : ĠInt , Ġvalue : ĠBoolean ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġi Ġ= Ġix Ġshr Ġ 5 ĊĠĠĠĠĠĠĠ Ġval Ġmask Ġ= Ġ 1 Ġshl Ġ( ix Ġand Ġ 0 x 1 F ) ĊĠĠĠĠĠĠĠ Ġfield [ i ] Ġ= Ġif Ġ( value ) Ġfield [ i ] Ġor Ġmask ĊĠĠĠĠĠĠĠ Ġelse Ġfield [ i ] Ġand Ġmask . inv () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġget Word ( word Ix : ĠInt ) Ġ= Ġfield [ word Ix ] ĊĊĠĠĠ Ġoverride Ġfun Ġset Word ( word Ix : ĠInt , Ġvalue : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfield [ word Ix ] Ġ= Ġvalue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġclear () Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġfield . indices ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfield [ i ] Ġ= Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġiterator (): ĠInt Iterator Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġobject Ġ: ĠInt Iterator () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġfield I : ĠInt Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġfield Value : ĠInt Ġ= Ġif Ġ( field . isEmpty ()) Ġ 0 Ġelse Ġfield [ field I ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġvalue I Ġ= Ġ 0 ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġprivate Ġfun Ġadvance () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( field I Ġ+ Ġ 1 Ġ< Ġfield . size Ġ&& Ġfield Value Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfield I ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( field I Ġ+ Ġ 1 Ġ< Ġfield . size Ġ&& Ġfield [ field I ] Ġ== Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfield I ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalue I Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfield Value Ġ= Ġfield [ field I ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( field Value Ġ!= Ġ 0 Ġ&& Ġfield Value Ġand Ġ 1 Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalue I ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfield Value Ġ= Ġfield Value Ġ ush r Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadvance () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġoverride Ġfun Ġhas Next () Ġ= Ġfield I Ġ+ Ġ 1 Ġ< Ġfield . size Ġ|| Ġfield Value Ġ!= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoverride Ġfun Ġnext Int (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( value I Ġ>= Ġ 3 2 ) Ġthrow ĠNoSuch ElementException () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġret Ġ= Ġ( field I Ġshl Ġ 5 ) Ġ+ Ġvalue I ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalue I ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfield Value Ġ= Ġfield Value Ġ ush r Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadvance () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġret ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġword Iterator () Ġ= Ġobject Ġ: ĠLong Iterator () Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġhas Next () Ġ= Ġi Ġ< Ġfield . size ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġnext Long () Ġ= Ġentry ( i , Ġfield [ i ++ ]) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġequals ( other : ĠAny ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( other Ġis ĠBit Array ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( size Ġ!= Ġother . size ) Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġfield . indices ) Ġif Ġ( field [ i ] Ġ!= Ġother . field [ i ]) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( other Ġis ĠInstance ) Ġdeep Equals ( other ) ĊĠĠĠĠĠĠĠ Ġelse Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠhashCode (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġresult Ġ= Ġsize ĊĠĠĠĠĠĠĠ Ġfor Ġ( l Ġin Ġfield ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= Ġ 3 1 Ġ* Ġresult Ġ+ Ġl ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString () Ġ= Ġdeep ToString () ĊĠĠĠ Ġoverride Ġval Ġsparse : ĠBoolean Ġget () Ġ= Ġfalse Ċ }