import Ġjava . util .* Ċ import Ġkotlinx . atomic fu .* Ċ import Ġkotlin . math . max Ċ import Ġkotlin . math . min Ċ Ċ enum Ġclass ĠOperation Ġ{ ĊĠĠĠ ĠPOL L , ĠP EEK , ĠADD , ĠDONE Ċ } Ċ Ċ class ĠNode < E >( val Ġop : ĠOperation , Ġval Ġx : ĠE ?) Ċ Ċ class ĠF CP ri ority Queue < E Ġ: ĠComparable < E >> Ġ{ ĊĠĠĠ Ġprivate Ġval Ġq Ġ= ĠPriority Queue < E >() ĊĠĠĠ Ġprivate Ġval Ġarr Size Ġ= Ġ 2 0 ĊĠĠĠ Ġprivate Ġval Ġlock : ĠAtomic Boolean Ġ= Ġatomic ( false ) ĊĠĠĠ Ġprivate Ġval Ġarray Ġ= Ġatomic ArrayOf Null s < Node < E >>( arr Size ) ĊĠĠĠ Ġprivate Ġval Ġrnd : ĠRandom Ġ= ĠRandom () ĊĊĠĠĠ Ġprivate Ġfun Ġtry Lock (): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġlock . compare AndSet ( false , Ġtrue ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġunlock () Ġ{ ĊĠĠĠĠĠĠĠ Ġlock . get AndSet ( false ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġcombine () Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( ind Ġin Ġ 0 .. ( arr Size Ġ- Ġ 1 )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcur Node Ġ= Ġarray [ ind ]. value ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur Node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ( cur Node . op ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠOperation . POLL Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġans Ġ= Ġq . peek () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( array [ ind ]. compare AndSet ( cur Node , ĠNode ( Operation . DONE , Ġans ))) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq . poll () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠOperation . PE EK Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġans Ġ= Ġq . peek () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġarray [ ind ]. compare AndSet ( cur Node , ĠNode ( Operation . DONE , Ġans )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠOperation . ADD Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( array [ ind ]. compare AndSet ( cur Node , ĠNode ( Operation . DONE , Ġnull ))) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq . add ( cur Node . x ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠOperation . DONE Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġcommon Method ( node : ĠNode < E >): ĠNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġc Ġ= Ġrnd . nextInt ( arr Size ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa Ġ= Ġmax ( c Ġ- Ġ 2 , Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb Ġ= Ġmin ( c Ġ+ Ġ 2 , Ġarr Size Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġa .. b ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( array [ i ]. compare AndSet ( null , Ġnode )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval ĠnewNode Ġ= Ġarray [ i ]. value ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( new Node Ġ!= Ġnull Ġ&& ĠnewNode . op Ġ== ĠOperation . DONE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġarray [ i ]. compare AndSet ( new Node , Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠnewNode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( array [ i ]. compare AndSet ( new Node , Ġnull )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRetrieves Ġthe Ġelement Ġwith Ġthe Ġhighest Ġpriority ĊĠĠĠĠ Ġ* Ġand Ġreturns Ġit Ġas Ġthe Ġresult Ġof Ġthis Ġfunction ; ĊĠĠĠĠ Ġ* Ġreturns Ġ` null ` Ġif Ġthe Ġqueue Ġis Ġempty . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġpoll (): ĠE ? Ġ{ ĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( try Lock ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtry Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcombine () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġq . poll () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġfinally Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġunlock () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= ĠNode < E >( Operation . POLL , Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval ĠnewNode Ġ= Ġcommon Method ( node ) Ġ?: Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠnewNode . x ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġelement Ġwith Ġthe Ġhighest Ġpriority ĊĠĠĠĠ Ġ* Ġor Ġ` null ` Ġif Ġthe Ġqueue Ġis Ġempty . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġpeek (): ĠE ? Ġ{ ĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( try Lock ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtry Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcombine () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġq . peek () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġfinally Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġunlock () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= ĠNode < E >( Operation . PE EK , Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval ĠnewNode Ġ= Ġcommon Method ( node ) Ġ?: Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠnewNode . x ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdds Ġthe Ġspecified Ġelement Ġto Ġthe Ġqueue . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġadd ( element : ĠE ) Ġ{ ĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( try Lock ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtry Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcombine () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq . add ( element ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġfinally Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġunlock () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= ĠNode ( Operation . ADD , Ġelement ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcommon Method ( node ) Ġ?: Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }