package Ġjp . j ug g ler . sub way to oter . util čĊč Ċ import Ġjava . util . Abstract List č Ċ import Ġjava . util . ArrayList č Ċ import Ġjava . util . NoSuch ElementException č Ċ import Ġjava . util . Random Access čĊč Ċ class ĠBucket List < E > Ġconstructor ( čĊ ĉ val Ġbucket Capacity Ġ: ĠInt Ġ= Ġ 1 0 2 4 č Ċ ) Ġ: ĠAbstract List < E >(), ĠMutable Iterable < E >, ĠRandom Access Ġ{ čĊĉčĊ ĉ comp anion Ġobject Ġ{ čĊĉ ĉ private Ġval Ġpos _ internal Ġ= Ġobject Ġ: ĠThread Local < Bucket Pos >() Ġ{ čĊĉĉ ĉ override Ġfun Ġinitial Value () Ġ: ĠBucket Pos Ġ{ čĊĉĉĉ ĉ return ĠBucket Pos () čĊĉĉ ĉ } čĊĉ ĉ } čĊ ĉ } čĊĉčĊ ĉ override Ġvar Ġsize Ġ: ĠInt Ġ= Ġ 0 čĊĉčĊ ĉ override Ġfun ĠisEmpty () Ġ: ĠBoolean Ġ{ čĊĉ ĉ return Ġ 0 Ġ== Ġsize čĊ ĉ } čĊĉčĊ ĉ private Ġclass ĠBucket < E >( čĊĉ ĉ capacity Ġ: ĠInt , čĊĉ ĉ var Ġtotal _ start Ġ: ĠInt Ġ= Ġ 0 , čĊĉ ĉ var Ġtotal _ end Ġ: ĠInt Ġ= Ġ 0 čĊ ĉ ) Ġ: ĠArrayList < E >( capacity ) čĊĉčĊ ĉ private Ġval Ġgroups Ġ= ĠArrayList < Bucket < E >>() čĊĉčĊ ĉ override Ġfun Ġclear () Ġ{ čĊĉ ĉ groups . clear () čĊĉ ĉ size Ġ= Ġ 0 čĊ ĉ } čĊĉčĊ ĉ private Ġfun Ġupdate Index () Ġ{ čĊĉ ĉ var Ġn Ġ= Ġ 0 čĊĉ ĉ for ( bucket Ġin Ġgroups ) Ġ{ čĊĉĉ ĉ bucket . total _ start Ġ= Ġn čĊĉĉ ĉ n Ġ+= Ġbucket . size čĊĉĉ ĉ bucket . total _ end Ġ= Ġn čĊĉ ĉ } čĊĉ ĉ size Ġ= Ġn čĊ ĉ } čĊĉčĊ ĉ internal Ġclass ĠBucket Pos ( čĊĉ ĉ var Ġgroup _ index Ġ: ĠInt Ġ= Ġ 0 , čĊĉ ĉ var Ġbucket _ index Ġ: ĠInt Ġ= Ġ 0 čĊ ĉ ) Ġ{ čĊĉ ĉ internal Ġfun Ġset ( group _ index Ġ: ĠInt , Ġbucket _ index Ġ: ĠInt ) Ġ: ĠBucket Pos Ġ{ čĊĉĉ ĉ this . group _ index Ġ= Ġgroup _ index čĊĉĉ ĉ this . bucket _ index Ġ= Ġbucket _ index čĊĉĉ ĉ return Ġthis čĊĉ ĉ } čĊ ĉ } čĊĉčĊ ĉ // Ġal local ted ĠãĤĴ æĮĩå®ļ ãģĹãģªãģĦ åł´åĲĪãģ¯ ĠBucket Pos ãĤĴ çĶŁæĪĲ ãģĹãģ¾ãģĻ čĊ ĉ private Ġfun Ġfind Pos ( čĊĉ ĉ total _ index Ġ: ĠInt , čĊĉ ĉ result Ġ: ĠBucket Pos Ġ= Ġpos _ internal . get () !! čĊ ĉ ) Ġ: ĠBucket Pos Ġ{ čĊčĊĉ ĉ if ( total _ index Ġ< Ġ 0 Ġ|| Ġtotal _ index Ġ>= Ġsize ) Ġ{ čĊĉĉ ĉ throw ĠIndex OutOfBoundsException (" find Pos : Ġbad Ġindex =$ total _ index , Ġsize =$ size ") čĊĉ ĉ } čĊĉĉčĊĉ ĉ // Ġbinary Ġsearch čĊĉ ĉ var Ġgs Ġ= Ġ 0 čĊĉ ĉ var Ġge Ġ= Ġgroups . size čĊĉ ĉ while ( true ) Ġ{ čĊĉĉ ĉ val Ġgi Ġ= Ġ( gs Ġ+ Ġge ) Ġshr Ġ 1 čĊĉĉ ĉ val Ġgroup Ġ= Ġgroups [ gi ] čĊĉĉ ĉ when Ġ{ čĊĉĉĉ ĉ total _ index Ġ< Ġgroup . total _ start Ġ-> Ġge Ġ= Ġgi čĊĉĉĉ ĉ total _ index Ġ>= Ġgroup . total _ end Ġ-> Ġgs Ġ= Ġgi Ġ+ Ġ 1 čĊĉĉĉ ĉ else Ġ-> Ġ{ čĊĉĉĉĉ ĉ return Ġresult . set ( gi , Ġtotal _ index Ġ- Ġgroup . total _ start ) čĊĉĉĉ ĉ } čĊĉĉ ĉ } čĊĉ ĉ } čĊ ĉ } čĊĉčĊ ĉ override Ġfun Ġget ( index Ġ: ĠInt ) Ġ: ĠE Ġ{ čĊĉ ĉ val Ġpos Ġ= Ġfind Pos ( index ) čĊĉ ĉ return Ġgroups [ pos . group _ index ][ pos . bucket _ index ] čĊ ĉ } čĊĉčĊ ĉ override Ġfun Ġset ( index Ġ: ĠInt , Ġelement Ġ: ĠE ) Ġ: ĠE Ġ{ čĊĉ ĉ val Ġpos Ġ= Ġfind Pos ( index ) čĊĉ ĉ return Ġgroups [ pos . group _ index ]. set ( pos . bucket _ index , element ) čĊ ĉ } čĊĉčĊ ĉ // Ġ æľ« å°¾ ãģ¸ãģ® è¿½åĬł čĊ ĉ override Ġfun Ġadd All ( elements Ġ: ĠCollection < E >) Ġ: ĠBoolean Ġ{ čĊĉ ĉ val Ġc _ size Ġ= Ġelements . size čĊĉ ĉ if ( c _ size Ġ== Ġ 0 ) Ġreturn Ġfalse čĊĉĉčĊĉ ĉ // Ġ æľĢ å¾Į ãģ® ãĥĲ ãĤ± ãĥĦ ãģ« åı İ ãģ¾ ãĤĭ ãģª ãĤī ãĢģ æľĢ å¾Į ãģ® ãĥĲ ãĤ± ãĥĦ ãģ® ä¸Ń ãģ« è¿½åĬł ãģĻãĤĭ čĊĉ ĉ if ( Ġgroups . isNotEmpty () Ġ) Ġ{ čĊĉĉ ĉ val Ġbucket Ġ= Ġgroups [ groups . size Ġ- 1 ] čĊĉĉ ĉ if ( Ġbucket . size Ġ+ Ġc _ size Ġ<= Ġbucket Capacity ) Ġ{ čĊĉĉĉ ĉ bucket . addAll ( elements ) čĊĉĉĉ ĉ bucket . total _ end Ġ+= Ġc _ size čĊĉĉĉ ĉ size Ġ+= Ġc _ size čĊĉĉĉ ĉ return Ġtrue čĊĉĉ ĉ } čĊĉ ĉ } čĊĉ ĉ // Ġ æĸ°ãģĹãģĦ ãĥĲ ãĤ± ãĥĦ ãĤĴ ä½ľ ãģ£ãģ¦ ãĢģ ãģĿ ãģĵ ãģ« è¿½åĬł ãģĻãĤĭ čĊĉ ĉ val Ġbucket Ġ= ĠBucket < E >( bucket Capacity ) čĊĉ ĉ bucket . addAll ( elements ) čĊĉ ĉ bucket . total _ start Ġ= Ġsize čĊĉ ĉ bucket . total _ end Ġ= Ġsize Ġ+ Ġc _ size čĊĉ ĉ size Ġ+= Ġc _ size čĊĉ ĉ groups . add ( bucket ) čĊĉ ĉ return Ġtrue čĊ ĉ } čĊĉčĊ ĉ // Ġ ä½įç½® ãĤĴæĮĩå®ļ ãģĹãģ¦ æĮ ¿ åħ¥ čĊ ĉ override Ġfun Ġadd All ( index Ġ: ĠInt , Ġelements Ġ: ĠCollection < E >) Ġ: ĠBoolean Ġ{ čĊĉĉčĊĉ ĉ // Ġindex ãģĮ çµĤ ç«¯ ãģª ãĤī ãĢģ çµĤ ç«¯ ãģ« è¿½åĬł ãģĻãĤĭ čĊĉ ĉ // Ġãĥ Ĳ ãĤ± ãĥĦ ãģĮ ãĤ« ãĥ© ãģ® åł´åĲĪ ãĤĤ ãģĵ ãģĵ čĊĉ ĉ if ( index Ġ>= Ġsize ) Ġ{ čĊĉĉ ĉ return Ġadd All ( elements ) čĊĉ ĉ } čĊĉĉčĊĉ ĉ val Ġc _ size Ġ= Ġelements . size čĊĉ ĉ if ( c _ size Ġ== Ġ 0 ) Ġreturn Ġfalse čĊĉĉčĊĉ ĉ val Ġpos Ġ= Ġfind Pos ( index ) čĊĉ ĉ var Ġbucket Ġ= Ġgroups [ pos . group _ index ] čĊĉĉčĊĉ ĉ // Ġ æĮ ¿ åħ¥ ä½įç½® ãģĮ ãĥĲ ãĤ± ãĥĦ ãģ® åħĪ éł Ń ãģ§ãģ¯ ãģªãģĦ ãģĭ ãĢģ ãĥĲ ãĤ± ãĥĦ ãģ® ãĤµ ãĤ¤ãĤº ãģ« åķıé¡Į ãģĮ ãģªãģĦ ãģª ãĤī čĊĉ ĉ if ( pos . bucket _ index Ġ> Ġ 0 Ġ|| Ġbucket . size Ġ+ Ġc _ size Ġ<= Ġbucket Capacity ) Ġ{ čĊĉĉ ĉ // Ġãĥ Ĳ ãĤ± ãĥĦ ãģ® ä¸Ń ãģ« æĮ ¿ åħ¥ ãģĻãĤĭ čĊĉĉ ĉ bucket . addAll ( pos . bucket _ index , Ġelements ) čĊĉ ĉ } Ġelse Ġ{ čĊĉĉ ĉ // Ġ æĸ°ãģĹãģĦ ãĥĲ ãĤ± ãĥĦ ãĤĴ ä½ľ ãģ£ãģ¦ ãĢģ ãģĿ ãģĵ ãģ« è¿½åĬł ãģĻãĤĭ čĊĉĉ ĉ bucket Ġ= ĠBucket ( bucket Capacity ) čĊĉĉ ĉ bucket . addAll ( elements ) čĊĉĉ ĉ groups . add ( pos . group _ index , Ġbucket ) čĊĉ ĉ } čĊĉĉčĊĉ ĉ update Index () čĊĉ ĉ return Ġtrue čĊ ĉ } čĊĉčĊ ĉ override Ġfun Ġremove At ( index Ġ: ĠInt ) Ġ: ĠE Ġ{ čĊĉ ĉ val Ġpos Ġ= Ġfind Pos ( index ) čĊĉ ĉ val Ġbucket Ġ= Ġgroups [ pos . group _ index ] čĊĉ ĉ val Ġdata Ġ= Ġbucket . remove At ( pos . bucket _ index ) čĊĉ ĉ if ( bucket . isEmpty ()) Ġ{ čĊĉĉ ĉ groups . remove At ( pos . group _ index ) čĊĉ ĉ } čĊĉ ĉ update Index () čĊĉ ĉ return Ġdata čĊ ĉ } čĊĉčĊ ĉ inner Ġclass ĠMy Iterator Ġinternal Ġconstructor () Ġ: ĠMutable Iterator < E > Ġ{ čĊĉĉčĊĉ ĉ private Ġval Ġpos Ġ: ĠBucket Pos Ġ// Ġindicates Ġnext Ġread Ġpoint čĊĉĉčĊĉ ĉ init Ġ{ čĊĉĉ ĉ pos Ġ= ĠBucket Pos ( 0 , Ġ 0 ) čĊĉ ĉ } čĊĉĉčĊĉ ĉ override Ġfun Ġhas Next () Ġ: ĠBoolean Ġ{ čĊĉĉ ĉ while ( true ) Ġ{ čĊĉĉĉ ĉ if ( pos . group _ index Ġ>= Ġgroups . size ) Ġ{ čĊĉĉĉĉ ĉ return Ġfalse čĊĉĉĉ ĉ } čĊĉĉĉ ĉ val Ġbucket Ġ= Ġgroups [ pos . group _ index ] čĊĉĉĉ ĉ if ( pos . bucket _ index Ġ>= Ġbucket . size ) Ġ{ čĊĉĉĉĉ ĉ pos . bucket _ index Ġ= Ġ 0 čĊĉĉĉĉ ĉ ++ Ġpos . group _ index čĊĉĉĉĉ ĉ continue čĊĉĉĉ ĉ } čĊĉĉĉ ĉ return Ġtrue čĊĉĉ ĉ } čĊĉ ĉ } čĊĉĉčĊĉ ĉ override Ġfun Ġnext () Ġ: ĠE Ġ{ čĊĉĉ ĉ while ( true ) Ġ{ čĊĉĉĉ ĉ if ( pos . group _ index Ġ>= Ġgroups . size ) Ġ{ čĊĉĉĉĉ ĉ throw ĠNoSuch ElementException () čĊĉĉĉ ĉ } čĊĉĉĉ ĉ val Ġbucket Ġ= Ġgroups [ pos . group _ index ] čĊĉĉĉ ĉ if ( pos . bucket _ index Ġ>= Ġbucket . size ) Ġ{ čĊĉĉĉĉ ĉ pos . bucket _ index Ġ= Ġ 0 čĊĉĉĉĉ ĉ ++ Ġpos . group _ index čĊĉĉĉĉ ĉ continue čĊĉĉĉ ĉ } čĊĉĉĉ ĉ return Ġbucket [ pos . bucket _ index Ġ++ ] čĊĉĉ ĉ } čĊĉ ĉ } čĊĉĉčĊĉ ĉ override Ġfun Ġremove () Ġ{ čĊĉĉ ĉ throw ĠNotImplementedError () čĊĉ ĉ } čĊ ĉ } čĊĉčĊ ĉ override Ġfun Ġiterator () Ġ: ĠMutable Iterator < E > Ġ{ čĊĉ ĉ return ĠMy Iterator () čĊ ĉ } č Ċ } čĊ