PROGRAM Time_Ranking
      USE Precision
      USE Sorting_Ranking
      USE Random_Numbers
      USE Simple_Graphics
      USE StopWatch
      IMPLICIT NONE
      
      INTEGER::size_array,min_size,max_size,n_repeated
      INTEGER,DIMENSION(:),ALLOCATABLE::permutation
      INTEGER,DIMENSION(:),ALLOCATABLE::i_array
      REAL,DIMENSION(:),ALLOCATABLE::r_array
      
      TYPE(WATCHTYPE)::timer,timers(10)
      REAL::disorder,elapsed_time,mean,std
      INTEGER::i,j,reps,n_reps,n_calls,n_steps
      LOGICAL::test
      CHARACTER(LEN=1)::distribution,method
      CHARACTER(LEN=25)::buffer,file_name
      REAL,DIMENSION(:,:,:),ALLOCATABLE::timing_matrix
      
      CALL CREATE_WATCH(timer)
      CALL CREATE_WATCH(timers)
      CALL UnpredictableSeeds()
      debug=.FALSE.
      
      WRITE(*,*)"Enter min_size, max_size as LOG10 of actual array size: "
      READ(*,*)min_size,max_size
      WRITE(*,*)"Enter the number of disorders to time (>=2):"
      READ(*,*)n_steps
      WRITE(*,*)"Distribution for random numbers in array ('Uniform' or 'Normal'):"
      READ(*,*)distribution
      ALLOCATE(timing_matrix(6,n_steps,max_size-min_size+1))
      
      OPEN(UNIT=10,FILE="TimeRanking.full.dat",STATUS="REPLACE",ACTION="WRITE")
      OPEN(UNIT=20,FILE="TimeRanking.short.dat",STATUS="REPLACE",ACTION="WRITE")
      OPEN(UNIT=30,FILE="TimeRanking.matrix.dat",STATUS="REPLACE",ACTION="WRITE")
      
      ChangeSize:DO j=min_size,max_size
      size_array=10**j
      ALLOCATE(permutation(size_array),r_array(size_array))
      ChangeDisorder:DO i=1,n_steps
      disorder=REAL(i-1)/REAL(n_steps-1)
      WRITE(*,*)"Now doing arrays of size:",size_array," disorder=",disorder
      WRITE(*,*)"___________________________________________"
      WRITE(10,*)"Now doing arrays of size:",size_array," disorder=",disorder
      WRITE(10,*)"___________________________________________"
      WRITE(20,FMT="(2I3,F10.2,I10)",ADVANCE="NO")i,j,disorder,size_array
      
      IF(distribution=="U")THEN
      CALL RandomUniform(r_array)
      mean=0.5
      std=0.5/SQRT(3.0)
      ELSE
      CALL RandomNormal(r_array)
      mean=0.0
      std=1.0
      END IF
      
      CALL MergeRank(r_array,permutation)
      r_array=r_array(permutation)
      CALL DisorderPermutation(permutation=permutation,&
      disorder=disorder,disorder_distribution='N')
      r_array=r_array(permutation)
      
      
      n_swaps=0
      n_reps=0
      n_calls=MAX(1,10000/size_array)
      CALL RESET_WATCH(timer)
      DO
      n_reps=n_reps+n_calls
      CALL START_WATCH(timer)
      DO reps=1,n_calls
      
      CALL MergeRank(r_array,permutation)
      END DO
      CALL STOP_WATCH(timer)
      CALL READ_WATCH(read_result=elapsed_time,watch=timer,clock="cpu")
      IF(elapsed_time>5.0)EXIT
      END DO
      timing_matrix(1,i,j)=elapsed_time/REAL(n_reps)
      WRITE(*,*)"ORDERPACK's MergeRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(*,*)"Number of swaps=",n_swaps/n_reps
      WRITE(10,*)"ORDERPACK's MergeRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(10,*)"Number of swaps=",n_swaps/n_reps
      WRITE(20,FMT="(E10.3)",ADVANCE="NO")elapsed_time/REAL(n_reps)
      IF(LOG(REAL(size_array))<=-0.65*LOG(disorder+0.01)+9.90)THEN
      
      n_swaps=0
      n_reps=0
      n_calls=MAX(1,10000/size_array)
      CALL RESET_WATCH(timer)
      DO
      n_reps=n_reps+n_calls
      CALL START_WATCH(timer)
      DO reps=1,n_calls
      
      CALL ShellInsertionRank(array=r_array,permutation=permutation,&
      partially_ranked=.FALSE.,method="Insertion")
      END DO
      CALL STOP_WATCH(timer)
      CALL READ_WATCH(read_result=elapsed_time,watch=timer,clock="cpu")
      IF(elapsed_time>5.0)EXIT
      END DO
      timing_matrix(2,i,j)=elapsed_time/REAL(n_reps)
      WRITE(*,*)"InsertionRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(*,*)"Number of swaps=",n_swaps/n_reps
      WRITE(10,*)"InsertionRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(10,*)"Number of swaps=",n_swaps/n_reps
      WRITE(20,FMT="(E10.3)",ADVANCE="NO")elapsed_time/REAL(n_reps)
      ELSE
      
      n_swaps=0
      n_reps=0
      n_calls=MAX(1,10000/size_array)
      CALL RESET_WATCH(timer)
      DO
      n_reps=n_reps+n_calls
      CALL START_WATCH(timer)
      DO reps=1,n_calls
      
      END DO
      CALL STOP_WATCH(timer)
      CALL READ_WATCH(read_result=elapsed_time,watch=timer,clock="cpu")
      IF(elapsed_time>5.0)EXIT
      END DO
      timing_matrix(2,i,j)=elapsed_time/REAL(n_reps)
      WRITE(*,*)"DummyInsertionRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(*,*)"Number of swaps=",n_swaps/n_reps
      WRITE(10,*)"DummyInsertionRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(10,*)"Number of swaps=",n_swaps/n_reps
      WRITE(20,FMT="(E10.3)",ADVANCE="NO")elapsed_time/REAL(n_reps)
      END IF
      IF((disorder<0.5).OR.((disorder>=0.5).AND.(size_array<=1500000)))THEN
      
      n_swaps=0
      n_reps=0
      n_calls=MAX(1,10000/size_array)
      CALL RESET_WATCH(timer)
      DO
      n_reps=n_reps+n_calls
      CALL START_WATCH(timer)
      DO reps=1,n_calls
      
      CALL ShellInsertionRank(array=r_array,permutation=permutation,&
      partially_ranked=.FALSE.,method="Shell",disorder=disorder)
      END DO
      CALL STOP_WATCH(timer)
      CALL READ_WATCH(read_result=elapsed_time,watch=timer,clock="cpu")
      IF(elapsed_time>5.0)EXIT
      END DO
      timing_matrix(3,i,j)=elapsed_time/REAL(n_reps)
      WRITE(*,*)"ShellRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(*,*)"Number of swaps=",n_swaps/n_reps
      WRITE(10,*)"ShellRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(10,*)"Number of swaps=",n_swaps/n_reps
      WRITE(20,FMT="(E10.3)",ADVANCE="NO")elapsed_time/REAL(n_reps)
      ELSE
      
      n_swaps=0
      n_reps=0
      n_calls=MAX(1,10000/size_array)
      CALL RESET_WATCH(timer)
      DO
      n_reps=n_reps+n_calls
      CALL START_WATCH(timer)
      DO reps=1,n_calls
      
      END DO
      CALL STOP_WATCH(timer)
      CALL READ_WATCH(read_result=elapsed_time,watch=timer,clock="cpu")
      IF(elapsed_time>5.0)EXIT
      END DO
      timing_matrix(3,i,j)=elapsed_time/REAL(n_reps)
      WRITE(*,*)"DummyShellRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(*,*)"Number of swaps=",n_swaps/n_reps
      WRITE(10,*)"DummyShellRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(10,*)"Number of swaps=",n_swaps/n_reps
      WRITE(20,FMT="(E10.3)",ADVANCE="NO")elapsed_time/REAL(n_reps)
      END IF
      
      n_swaps=0
      n_reps=0
      n_calls=MAX(1,10000/size_array)
      CALL RESET_WATCH(timer)
      DO
      n_reps=n_reps+n_calls
      CALL START_WATCH(timer)
      DO reps=1,n_calls
      
      CALL QuickRank(array=r_array,permutation=permutation,&
      mean_value=mean,standard_deviation=std,&
      partially_ranked=.FALSE.,pivot_selection=distribution)
      END DO
      CALL STOP_WATCH(timer)
      CALL READ_WATCH(read_result=elapsed_time,watch=timer,clock="cpu")
      IF(elapsed_time>5.0)EXIT
      END DO
      timing_matrix(4,i,j)=elapsed_time/REAL(n_reps)
      WRITE(*,*)"QuickRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(*,*)"Number of swaps=",n_swaps/n_reps
      WRITE(10,*)"QuickRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(10,*)"Number of swaps=",n_swaps/n_reps
      WRITE(20,FMT="(E10.3)",ADVANCE="NO")elapsed_time/REAL(n_reps)
      
      n_swaps=0
      n_reps=0
      n_calls=MAX(1,10000/size_array)
      CALL RESET_WATCH(timer)
      DO
      n_reps=n_reps+n_calls
      CALL START_WATCH(timer)
      DO reps=1,n_calls
      
      CALL HashRank(array=r_array,permutation=permutation,&
      mean_value=mean,standard_deviation=std,&
      partially_ranked=.FALSE.,distribution=distribution)
      END DO
      CALL STOP_WATCH(timer)
      CALL READ_WATCH(read_result=elapsed_time,watch=timer,clock="cpu")
      IF(elapsed_time>5.0)EXIT
      END DO
      timing_matrix(5,i,j)=elapsed_time/REAL(n_reps)
      WRITE(*,*)"HashRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(*,*)"Number of swaps=",n_swaps/n_reps
      WRITE(10,*)"HashRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(10,*)"Number of swaps=",n_swaps/n_reps
      WRITE(20,FMT="(E10.3)",ADVANCE="NO")elapsed_time/REAL(n_reps)
      
      n_swaps=0
      n_reps=0
      n_calls=MAX(1,10000/size_array)
      CALL RESET_WATCH(timer)
      DO
      n_reps=n_reps+n_calls
      CALL START_WATCH(timer)
      DO reps=1,n_calls
      
      CALL RadixRank(array=TRANSFER(r_array,MOLD=1,SIZE=size_array),&
      permutation=permutation,partially_ranked=.FALSE.)
      END DO
      CALL STOP_WATCH(timer)
      CALL READ_WATCH(read_result=elapsed_time,watch=timer,clock="cpu")
      IF(elapsed_time>5.0)EXIT
      END DO
      timing_matrix(6,i,j)=elapsed_time/REAL(n_reps)
      WRITE(*,*)"RadixRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(*,*)"Number of swaps=",n_swaps/n_reps
      WRITE(10,*)"RadixRank"," took (s):",elapsed_time/REAL(n_reps)
      WRITE(10,*)"Number of swaps=",n_swaps/n_reps
      WRITE(20,FMT="(E10.3)",ADVANCE="NO")elapsed_time/REAL(n_reps)
      
      WRITE(*,*)"___________________________________________"
      WRITE(10,*)"___________________________________________"
      WRITE(20,*)
      CALL FLUSH(10);
      CALL FLUSH(20)
      
      END DO ChangeDisorder
      DEALLOCATE(r_array,permutation)
      END DO ChangeSize
      
      WRITE(30,*)SHAPE(timing_matrix)
      WRITE(30,*)timing_matrix
      CLOSE(10)
      CLOSE(20)
      CLOSE(30)
      
      END PROGRAM Time_Ranking