-- Item :      Contingous List Searching Test Driver
-- Reference : Data Structures and Program Design, Pascal, p 247
-- Author :    Kruse, recoded by Paul Stachour, stachour@winternet.com
-- Version :   1.1, 1999/Jan/29
-- For :       ICS340, Winter 199, Metro State, Minnesota
-- Style :     Ada95, in a pascalish style, to match the textbook.
-- Protection: Original copyright 1994, Prentice Hall
-- Derivation: Derivation by permission; see P. Stachour for details
-- Disclaimer: This routine has not been tested, only translated


with ch7_sr; use ch7_sr;
with Text_IO; use Text_IO;
with Ada.Numerics.Discrete_Random;
procedure ch7_ts is

use ch7_sr.key_cl;   -- The list created in serach package

Search_List: ch7_sr.key_cl.list;


procedure TestSearch( L: in out list; Look: searchmethod) is
 
-- Pre:  The searching method Look exists.
-- Post: A test of the searching method Look has been completed, including
--       CPU timing and key comparison count.
-- Uses: CC is the global comparison count, initialized here and incremented
--       by each searching procedure. searchcount is a global value used
--       to determine the number of repeated searches to do.



  i: integer;
  found: Boolean;
  location: position;
  average: float;
  target : Key_Type;
  cc : integer; -- dummy
  how_long: duration;
  searchcount: integer := ListSize(L); --searchcount is  nunber of searches
  subtype RI_Range is natural range 1 .. ListSize(L);
  package Random_Int is new Ada.Numerics.Discrete_Random(RI_Range);
  G: Random_Int.Generator;
  

begin                    --procedure TestSearch
    ch7_sr.Reset_Counts; --Initialize the comparison count & timer
   
    if not ListEmpty(L) then
    begin
      --Test with successful searches.
      for i in 1 .. searchcount loop 
                                     
        target := key_type(2 * Random_Int.Random(G) - 1); --must be odd number
        --Put_Line("Searching: Key " & integer'image(integer(target)) );
        Look(L, target, found, location);

        if not found then
          Put_Line("Error: Key " & integer'image(integer(target)) & " not found.");
        end if;
      end loop;
      ch7_sr.Get_Counts( Comparisons => CC, Interval => How_Long );
      average := float(CC)/float(searchcount);
    end;

    else
      average := 0.0;
    end if;
    Put_Line(" Successful search: " & float'image(average) & " comparisons.");
    Put_Line(" The elapsed time to complete " & integer'image(searchcount) &
            " searches is " & duration'image(how_long));

    ch7_sr.Reset_Counts; --Initialize the comparison count & timer
    if not ListEmpty(L) then
      --Test with unsuccessful searches.
      for i in 1 .. searchcount loop  
        target := key_type(2 * Random_Int.Random(G));  --must be even number}
        -- Put_Line("Searching: Key " & integer'image(integer(target)) );
        Look(L, target, found, location);

        if found then
          Put_line("Error: Key " & integer'image(integer(target)) & " found improperly.");
        end if;
      end loop;
      ch7_sr.Get_Counts( Comparisons => CC, Interval => How_Long );
      average := float(CC)/float(searchcount);
    else
      average := 0.0;
    end if;
    Put_Line(" Unsuccessful search: " & float'image(average) & " comparisons.");
    Put_Line(" The elapsed time to complete " & integer'image(searchcount) &
            " searches is " & duration'image(how_long));

end TestSearch;

begin
  -- Fill the list
  for I in Search_List.Data'Range loop
    Search_List.Data(I).Key := Key_Type(2*I -1);
  end loop;

  Put_Line("Sequential Searches: " );
  Put_Line("Size = 10 " );
  Search_list.Count := 10;
  TestSearch( L => Search_List, Look => SequentialSearch'access );
  Put_Line("Size = 100 " );
  Search_list.Count := 100;
  TestSearch( L => Search_List, Look => SequentialSearch'access );
  Put_Line("Size = 1000 " );
  Search_list.Count := 1_000;
  TestSearch( L => Search_List, Look => SequentialSearch'access );
  Put_Line("Size = 10000 " );
  Search_list.Count := 10_000;
  TestSearch( L => Search_List, Look => SequentialSearch'access );
  
  Put_Line("Binary Searches: " );
  Put_Line("Size = 10 " );
  Search_list.Count := 10;
  TestSearch( L => Search_List, Look => Binary1Search'access );
  Put_Line("Size = 100 " );
  Search_list.Count := 100;
  TestSearch( L => Search_List, Look => Binary1Search'access );
  Put_Line("Size = 1000 " );
  Search_list.Count := 1_000;
  TestSearch( L => Search_List, Look => Binary1Search'access );
  Put_Line("Size = 10000 " );
  Search_list.Count := 10_000;
  TestSearch( L => Search_List, Look => Binary1Search'access );
  
end ch7_ts;