// Ċ // Ġ( C ) ĠCopyright Ġ 2 0 1 4 - 2 0 2 1 ĠMartin ĠE . ĠN ord berg ĠIII Ċ // ĠApache Ġ 2 . 0 ĠLicense Ċ // Ċ Ċ package Ġbar lom . util . revisions Ċ Ċ //---------------------------------------------------------------- ------------------------------------------------ ----- Ċ Ċ /** Ċ Ġ* ĠA Ġversion - man aging Ġhandle Ġto Ġa Ġhash Ġset Ġwith Ġtransaction al Ġrevisions . Ċ Ġ* Ċ Ġ* Ġ@ param Ġ< T > Ġthe Ġtype Ġof Ġthe Ġvalue Ġthat Ġis Ġheld Ġin Ġthe Ġset Ġ- Ġmust Ġhave Ġa Ġv iable ĠhashCode () Ġfunction . Ċ Ġ*/ Ċ open Ġclass ĠV HashSet < T Ġ: ĠAny >( ĊĊĠĠĠ Ġnominal Table Size : ĠInt Ġ= Ġ 1 0 0 0 Ċ Ċ ) Ġ{ ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġtotal Ġnumber Ġof Ġentries Ġin Ġthe Ġset . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġvar Ġ_ size Ġ= ĠV ( 0 ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġsize Ġof Ġthe Ġtable Ġof Ġlinked Ġlists Ġof Ġentries . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġ_ table Size Ġ= ĊĠĠĠĠĠĠĠ Ġif Ġ( nominal Table Size Ġ<= Ġ 1 2 7 ) Ġ 1 2 7 ĊĠĠĠĠĠĠĠ Ġelse Ġif Ġ( nominal Table Size Ġ<= Ġ 2 5 7 ) Ġ 2 5 7 ĊĠĠĠĠĠĠĠ Ġelse Ġif Ġ( nominal Table Size Ġ<= Ġ 5 0 9 ) Ġ 5 0 9 ĊĠĠĠĠĠĠĠ Ġelse Ġif Ġ( nominal Table Size Ġ<= Ġ 1 0 2 1 ) Ġ 1 0 2 1 ĊĠĠĠĠĠĠĠ Ġelse Ġif Ġ( nominal Table Size Ġ<= Ġ 2 0 5 3 ) Ġ 2 0 5 3 ĊĠĠĠĠĠĠĠ Ġelse Ġif Ġ( nominal Table Size Ġ<= Ġ 4 0 9 9 ) Ġ 4 0 9 9 ĊĠĠĠĠĠĠĠ Ġelse Ġ 8 1 9 1 ĊĠĠĠ Ġ// ĠTODO : Ġbigger Ġsizes Ġas Ġneeded Ġ... ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠArray Ġof Ġlists Ġof Ġentries , Ġto Ġbe Ġindexed Ġby Ġhash Ġcode ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġ_ table Ġ= ĠArray (_ table Size ) Ġ{ ĠV LinkedList < T >() Ġ} ĊĊĊĠĠĠ Ġ/** ĠThe Ġsize Ġof Ġthis Ġset Ġfor Ġthe Ġactive Ġrevision Ġin Ġreview . ĠSize Ġis ĠO ( 1 ). Ġ*/ ĊĠĠĠ Ġval Ġsize : ĠInt ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġ_ size . get () ĊĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdds Ġan Ġitem Ġto Ġthe Ġset . ĠInsert ion Ġis ĠO ( size / table Size ). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġadd ( value : ĠT ) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġget Table Index ( value ) ĊĊĠĠĠĠĠĠĠ Ġif Ġ(!_ table [ index ]. contains ( value )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ table [ index ]. add ( value ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ size . increment () ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠMakes Ġa Ġsnapshot Ġcopy Ġof Ġthe Ġset . ĠCopy ing Ġis ĠO ( n ) ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġas Set (): ĠSet < T > Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= ĠHashSet < T >( size ) ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( list Ġin Ġ_ table ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( entry Ġin Ġlist ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( entry ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġlist . asList (). list Iterator () ĊĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠE mpt ies Ġthe Ġset . ĠO ( table Size ). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġclear () Ġ{ ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġ_ table Size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ table [ i ]. clear () ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ_ size . set ( 0 ) ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠTests Ġwhether Ġthe Ġlist Ġcontains Ġa Ġgiven Ġvalue . ĠSearch Ġis ĠO ( size / table Size ). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġcontains ( value : ĠT ): ĠBoolean Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġget Table Index ( value ) ĊĊĠĠĠĠĠĠĠ Ġreturn Ġ_ table [ index ]. contains ( value ) ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠPerforms Ġthe Ġgiven Ġ[ action ] Ġon Ġeach Ġitem Ġin Ġthe Ġset . ĊĠĠĠĠ Ġ* ĠNote Ġthat Ġthe Ġorder Ġof Ġiteration Ġis Ġunlikely Ġto Ġbe Ġmeaningful Ġsince Ġit Ġis Ġbased Ġon Ġhash Ġcode Ġmodulo Ġtable Ġsize ĊĠĠĠĠ Ġ* Ġand Ġthen Ġby Ġreverse Ġorder Ġof Ġinsertion Ġfor Ġthe Ġsame Ġhash code Ġmodulo Ġtable Ġsize . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun ĠforEach ( action : Ġ( T ) Ġ-> ĠUnit ) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( list Ġin Ġ_ table ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( entry Ġin Ġlist ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġaction ( entry ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĠWhether Ġthe Ġlist Ġis Ġempty . ĠO ( 1 ) Ġ*/ ĊĠĠĠ Ġfun ĠisEmpty (): ĠBoolean Ġ= Ġsize Ġ== Ġ 0 ĊĊĠĠĠ Ġ/** ĠWhether Ġthe Ġlist Ġis Ġnon - empty . ĠO ( 1 ) Ġ*/ ĊĠĠĠ Ġfun Ġis NotEmpty (): ĠBoolean Ġ= Ġsize Ġ> Ġ 0 ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġa Ġlist Ġcontaining Ġthe Ġresults Ġof Ġapplying Ġthe Ġgiven Ġ[ transform ] Ġfunction ĊĠĠĠĠ Ġ* Ġto Ġeach Ġelement Ġin Ġthis Ġlinked Ġlist . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġ< R > Ġmap ( transform : Ġ( T ) Ġ-> ĠR ): ĠSet < R > Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= ĠHashSet < R >( size ) ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( list Ġin Ġ_ table ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( entry Ġin Ġlist ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult . add ( transform ( entry )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemoves Ġan Ġitem Ġfrom Ġthe Ġset . ĠRem oval Ġis ĠO ( size / table Size ). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġremove ( value : ĠT ): ĠBoolean Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġget Table Index ( value ) ĊĊĠĠĠĠĠĠĠ Ġif Ġ(_ table [ index ]. remove ( value )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ size . decrement () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠComputes Ġa Ġtable Ġindex Ġfrom Ġthe Ġhash Ġcode Ġof Ġgiven Ġvalue . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġget Table Index ( value : ĠT ) Ġ= ĊĠĠĠĠĠĠĠ Ġ( value . hashCode () Ġ% Ġ_ table Size Ġ+ Ġ_ table Size ) Ġ% Ġ_ table Size Ċ Ċ } Ċ Ċ //---------------------------------------------------------------- ------------------------------------------------ ----- ĊĊ