/* Ċ Ġ* ĠCopyright Ġ 2 0 1 6 - 2 0 1 7 ĠJetBrains Ġs . r . o . Ċ Ġ* Ċ Ġ* Ġ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 Ġkotlinx . coroutines . experimental . internal Ċ Ċ import Ġkotlinx . coroutines . experimental .* Ċ import Ġkotlin . test .* Ċ import Ġjava . util .* Ċ Ċ class ĠThread Safe Heap Test Ġ: ĠTest Base () Ġ{ ĊĠĠĠ Ġclass ĠNode ( val Ġvalue : ĠInt ) Ġ: ĠThread Safe Heap Node , ĠComparable < Node > Ġ{ ĊĠĠĠĠĠĠĠ Ġoverride Ġvar Ġindex Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġcompare To ( other : ĠNode ): ĠInt Ġ= Ġvalue . compareTo ( other . value ) ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġequals ( other : ĠAny ?): ĠBoolean Ġ= Ġother Ġis ĠNode Ġ&& Ġother . value Ġ== Ġvalue ĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠhashCode (): ĠInt Ġ= Ġvalue ĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ= Ġ"$ value " ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest Basic () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġh Ġ= ĠThread Safe Heap < Node >() ĊĠĠĠĠĠĠĠ ĠassertEquals ( null , Ġh . peek ()) ĊĠĠĠĠĠĠĠ Ġval Ġn 1 Ġ= ĠNode ( 1 ) ĊĠĠĠĠĠĠĠ Ġh . add Last ( n 1 ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( n 1 , Ġh . peek ()) ĊĠĠĠĠĠĠĠ Ġval Ġn 2 Ġ= ĠNode ( 2 ) ĊĠĠĠĠĠĠĠ Ġh . add Last ( n 2 ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( n 1 , Ġh . peek ()) ĊĠĠĠĠĠĠĠ Ġval Ġn 3 Ġ= ĠNode ( 3 ) ĊĠĠĠĠĠĠĠ Ġh . add Last ( n 3 ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( n 1 , Ġh . peek ()) ĊĠĠĠĠĠĠĠ Ġval Ġn 4 Ġ= ĠNode ( 4 ) ĊĠĠĠĠĠĠĠ Ġh . add Last ( n 4 ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( n 1 , Ġh . peek ()) ĊĠĠĠĠĠĠĠ Ġval Ġn 5 Ġ= ĠNode ( 5 ) ĊĠĠĠĠĠĠĠ Ġh . add Last ( n 5 ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( n 1 , Ġh . peek ()) ĊĠĠĠĠĠĠĠ ĠassertEquals ( n 1 , Ġh . remove First OrNull ()) ĊĠĠĠĠĠĠĠ ĠassertEquals (- 1 , Ġn 1 . index ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( n 2 , Ġh . peek ()) ĊĠĠĠĠĠĠĠ Ġh . remove ( n 2 ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( n 3 , Ġh . peek ()) ĊĠĠĠĠĠĠĠ Ġh . remove ( n 4 ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( n 3 , Ġh . peek ()) ĊĠĠĠĠĠĠĠ Ġh . remove ( n 3 ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( n 5 , Ġh . peek ()) ĊĠĠĠĠĠĠĠ Ġh . remove ( n 5 ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( null , Ġh . peek ()) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest Random Sort () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġn Ġ= Ġ 1 0 0 0 Ġ* Ġstress Test Multiplier ĊĠĠĠĠĠĠĠ Ġval Ġr Ġ= ĠRandom ( 1 ) ĊĠĠĠĠĠĠĠ Ġval Ġh Ġ= ĠThread Safe Heap < Node >() ĊĠĠĠĠĠĠĠ Ġval Ġa Ġ= ĠInt Array ( n ) Ġ{ Ġr . nextInt () Ġ} ĊĠĠĠĠĠĠĠ Ġrepeat ( n ) Ġ{ Ġh . add Last ( Node ( a [ it ])) Ġ} ĊĠĠĠĠĠĠĠ Ġa . sort () ĊĠĠĠĠĠĠĠ Ġrepeat ( n ) Ġ{ ĠassertEquals ( Node ( a [ it ]), Ġh . remove First OrNull ()) Ġ} ĊĠĠĠĠĠĠĠ ĠassertEquals ( null , Ġh . peek ()) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest Random Remove () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġn Ġ= Ġ 1 0 0 0 Ġ* Ġstress Test Multiplier ĊĠĠĠĠĠĠĠ Ġcheck ( n Ġ% Ġ 2 Ġ== Ġ 0 ) Ġ{ Ġ" Must Ġbe Ġeven " Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġr Ġ= ĠRandom ( 1 ) ĊĠĠĠĠĠĠĠ Ġval Ġh Ġ= ĠThread Safe Heap < Node >() ĊĠĠĠĠĠĠĠ Ġval Ġset Ġ= ĠTree Set < Node >() ĊĠĠĠĠĠĠĠ Ġrepeat ( n ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Ġ= ĠNode ( r . nextInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġh . add Last ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertTrue ( set . add ( node )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġwhile Ġ(! h . isEmpty ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġpick Ġrandom Ġnode Ġto Ġremove ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrnd Node : ĠNode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtail Ġ= Ġset . tail Set ( Node ( r . nextInt ())) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! tail . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrnd Node Ġ= Ġtail . first () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertTrue ( set . remove ( rnd Node )) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertTrue ( h . remove ( rnd Node )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġremove Ġhead Ġand Ġvalidate ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhead Node Ġ= Ġh . remove First OrNull () !! Ġ// Ġmust Ġnot Ġbe Ġnull !!! ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertTrue ( head Node Ġ=== Ġset . first (), Ġ" Expected Ġ${ set . first ()}, Ġbut Ġfound Ġ$ head Node , Ġremaining Ġsize Ġ${ h . size }") ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertTrue ( set . remove ( head Node )) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( set . size , Ġh . size ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }