-- test_heap_sort_2.adb  Ada 83
with TEXT_IO ; use TEXT_IO ;
with Ada.Numerics.Long_Elementary_Functions;
use  Ada.Numerics.Long_Elementary_Functions;
with HEAP_SORT_2 ;
with PERMUTE ;

procedure TEST_HEAP_SORT_2 is
  NMAX : constant := 10;
  type INT_ARRAY is array ( INTEGER range <> ) of INTEGER ;
  WORK_ARRAY : INT_ARRAY ( 1 .. NMAX ) ;
  MY_ARRAY   : INT_ARRAY ( 1 .. NMAX ) ;
  INDEX_MAX  : INT_ARRAY ( 1 .. NMAX ) ;
  SWAP_MAX   : INT_ARRAY ( 1 .. NMAX ) ;
  MY_PERMUTE : INT_ARRAY ( 1 .. NMAX ) ;

  procedure SORT is new HEAP_SORT_2 ( INTEGER , INTEGER , INT_ARRAY ) ;
  DONE : BOOLEAN ;

  procedure NEXT is new PERMUTE ( INTEGER , INTEGER , INT_ARRAY , INT_ARRAY );

  COMPARES , MAX_COMPARES, AVG_COMPARES, SWAPS , MAX_SWAPS, AVG_SWAPS : INTEGER;
  PERMUTATIONS : NATURAL ;
begin
  PUT_LINE ( "Test Heap Sort" ) ;
  for N in 1..NMAX loop
    DONE := FALSE ;
    PERMUTATIONS := 0 ;
    COMPARES := 0 ;
    MAX_COMPARES := -1 ;
    AVG_COMPARES := 0 ;
    SWAPS := 0 ;
    MAX_SWAPS := -1 ;
    AVG_SWAPS := 0 ;
    for I in 1..N loop
      MY_ARRAY(I) := I;
      MY_PERMUTE(I) := N+1;
    end loop;
    while not DONE loop
      NEXT ( MY_ARRAY(1..N) , MY_PERMUTE(1..N) , DONE ) ;
      PERMUTATIONS := PERMUTATIONS + 1 ;
      WORK_ARRAY := MY_ARRAY ;
      COMPARES := 0 ;
      SWAPS := 0 ;
      -- if N <= 3 then -- some debug print to show arrays being sorted
      --   PUT ( "                   WORK_ARRAY " ) ;
      --   for J in 1..N loop
      --     PUT ( INTEGER'IMAGE ( WORK_ARRAY(J) ));
      --   end loop ;
      --     NEW_LINE ;
      -- end if;
      SORT ( WORK_ARRAY(1..N) , COMPARES , SWAPS ) ;
      AVG_COMPARES := AVG_COMPARES + COMPARES;
      if COMPARES > MAX_COMPARES then
        MAX_COMPARES := COMPARES ;
        INDEX_MAX := MY_ARRAY ;
      end if ;
      AVG_SWAPS := AVG_SWAPS + SWAPS;
      if SWAPS > MAX_SWAPS then
        MAX_SWAPS := SWAPS ;
        SWAP_MAX := MY_ARRAY ;
      end if ;
    end loop ;

    PUT ( INTEGER'IMAGE( N )) ;
    put ( " = num, " ) ;
    PUT ( INTEGER'IMAGE( MAX_COMPARES )) ;
    PUT ( " = Max compares  at" ) ;
    for I in 1..N loop
      PUT ( INTEGER'IMAGE( INDEX_MAX( I ))) ;
    end loop ;
    NEW_LINE ;
    PUT ( "          " ) ;
    PUT ( INTEGER'IMAGE( MAX_SWAPS )) ;
    PUT ( " = Max swaps     at" ) ;
    for I in 1..N loop
      PUT ( INTEGER'IMAGE( SWAP_MAX( I ))) ;
    end loop ;
    PUT ( ",  " ) ;
    PUT ( INTEGER'IMAGE( PERMUTATIONS)) ;
    PUT_LINE ( " = permutations" ) ;
    PUT ( "          " ) ;
    PUT ( INTEGER'IMAGE( AVG_COMPARES/PERMUTATIONS )) ;
    PUT ( " = Avg comps, " ) ;
    PUT ( INTEGER'IMAGE( AVG_SWAPS/PERMUTATIONS )) ;
    PUT ( " = Avg swaps, " ) ;
    PUT ( INTEGER'IMAGE ( INTEGER( Long_FLOAT(N) * LOG(Long_FLOAT(N),2.0) ) ) );
    PUT ( " = N log2(N), " ) ;
    PUT ( INTEGER'IMAGE ( (N*(N-1))/2 ) );
    PUT_LINE ( " = N*(N-1)/2" ) ;
    NEW_LINE ;
  end loop;
end TEST_HEAP_SORT_2 ;