-- Item :      Contingous List Searching Package Body
-- Reference : Data Structures and Program Design, Pascal, p 244
-- 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 Ada.Numerics.Discrete_Random;
with Calendar; use Calendar;
package body ch7_sr is 

CC: Natural := 0;  -- Count of Comparisions
CT: Calendar.Time := Calendar.Clock;  -- Calendar Time

procedure Reset_Counts is
begin
  CC := 0;  -- Count of Comparisions
  CT := Calendar.Clock;  -- Calendar Time
end Reset_Counts;

procedure Get_Counts
 (Comparisons : out Natural;
  Interval    : out Duration) is
begin
  Comparisons := CC;
  Interval := Calendar.Clock - CT;  -- Calendar Duration
end Get_Counts;

procedure SequentialSearch( L: in out list; target: Key_Type;
          found: in out Boolean;  location: in out position) is
-- Pre:  The contiguous list L has been created.
-- Post: If an entry in L has key equal to target, then found becomes
--       true and location contains the position of such entry. Otherwise
--       found becomes false and location becomes invalid.


begin                   -- procedure SequentialSearch
  found := false;       -- Initialize
  location :=  1;
  -- Note: The form of the loop was changed because the orginal resulted
  -- in an out-of-bounds index and constraint error at the end of the search
  loop
    CC := CC + 1;  -- Update Comparision Count.
    if L.Data(location).key = target then
      found := true;
      exit;  -- success
    end if;
    if location >= L.count then -- > should not happen, take constraint error
      exit;   -- failure
    end if;
    location := location + 1;  -- try again
  end loop;
end SequentialSearch;


procedure Mixup( L: in out list) is
-- Pre:   L is a list that has been created.
-- Post: The order of the entries in L has been permuted randomly.
-- Uses: Random number package.

  newposition: position;
  temp1, temp2: List_Entry;       -- used for swapping two entries}
  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
  for curposition in  1 .. ListSize(L) - 1 loop
    newposition := Random_Int.Random(G);
    RetrieveList(curposition, temp1, L);
    RetrieveList(newposition, temp2, L);
    ReplaceList(curposition, temp2, L);
    ReplaceList(newposition, temp1, L);
  end loop;
end;
 
procedure InsertOrder(x: List_Entry;  L: in out list) is
-- Pre:  L has been created, is an ordered list, and is not full.
-- Post: The entry x has been inserted into L in a position such that the
-- keys in all entries of L remain in the correct order.

  current: position;
  currententry: List_Entry;
  found:   Boolean;     -- Has the place where x goes been found?}

begin
  current := 1;
  found := false;
  while not found loop
    if current > ListSize(L) then
      found := true;
    else 
      RetrieveList(current, currententry, L);
      if x.key <= currententry.key then
        found := true;
      else
        current := current + 1;
      end if;
    end if;
  end loop;
  InsertList(current, x, L);
end;
 

procedure RecBinary1( L: in out list; target: Key_Type; bottom, top: integer;
                      found: out Boolean;  location: out position) is
-- Pre:  The contiguous list L has been created. bottom and top are the
--      range in the list to search for the target.
-- Post: If an entry in the range from bottom and top in L has key equal
--       to target, then found becomes true and location gets the position
--       of one such entry. Otherwise, found becomes false and location is
--       undefined.
-- Uses: RecBinary1 recursively.

--recursive, forgetful version of binary search}
mid:  integer;

begin                   --procedure RecBinary1
  if bottom < top then          -- more than one entry in sublist}
    mid := (top + bottom) / 2;
    if target > L.Data(mid).key then   --Reduce to the top half of the list.}
      CC := CC + 1;  -- Update Comparision Count.
      RecBinary1(L, target, mid + 1, top, found, location);
    else                             --Reduce to the bottom half of the list.}
      RecBinary1(L, target, bottom, mid, found, location);
    end if;
  elsif top < bottom then
    found := false;                   --empty sublist}
  else                               --top = bottom, one entry sublist}
    found := (target = L.Data(top).key); --Set the output parameters.}
    CC := CC + 1;  -- Update Comparision Count.
    if found then
      location := top;
    end if;
  end if;
end RecBinary1;
 

procedure RecBinary1Search( L: in out list; target: Key_Type; 
 found: in out Boolean;  location: in out position) is
-- Pre:  The contiguous list L has been created.
-- Post: If an entry in L has key equal to target, then found becomes
--       true and location contains the position of such entry. Otherwise
--       found becomes false and location becomes invalid.
-- Uses: RecBinary1.

begin                   --procedure RecBinary1Search}
  RecBinary1(L, target, 1, L.count, found, location);
end;                    --procedure RecBinary1Search}
 

procedure Binary1Search( L: in out list; target: Key_Type;
                   found: in out Boolean;  location: in out position) is
-- Pre:   The contiguous list L has been created.
-- Post: If an entry in L has key equal to target, then found becomes
--       true and location gets the position of one such entry. Otherwise,
--       found becomes false and location is undefined.

              --forgetful version of binary search}
  top,
  bottom,
  mid:  integer;

begin                   --procedure Binary1Search}
  top := L.count;       --Initialize the bounds to encompass the whole list.}
  bottom := 1;

  while top > bottom loop         --Check termination.}
    mid := (top + bottom) / 2;

    if target > L.Data(mid).key then   --Reduce to the top half of the list.}
      CC := CC + 1;  -- Update Comparision Count.
      bottom := mid + 1;
    else                --Reduce to the bottom half of the list.}
      top := mid;
    
    end if; --The preceding if statement guarantees that the invariant still holds.}
  end loop;
  if top = 0 then
    found := false;      --Search of an empty list always fails.}
  else
    found := (target = L.Data(top).key); --Set the output parameters.}
    CC := CC + 1;  -- Update Comparision Count.  
end if;
  if found then
    location := top;
  end if;
end Binary1Search;
 


procedure RecBinary2( L: in out list; target: Key_Type; bottom, top: integer;
                      found: in out Boolean;  location: in out position) is
-- Pre:  The contiguous list L has been created. bottom and top are the
--      range in the list to search for the target.
-- Post: If an entry in the range from bottom and top in L has key equal
--       to target, then found becomes true and location gets the position
--       of one such entry. Otherwise, found becomes false and location is
--       undefined.
-- Uses: RecBinary2 recursively;

mid: integer; -- mid will be location of target if it is found in L.}

begin                   --procedure RecBinary2}
  if bottom > top then
    found := false;
  else 
    mid := (top + bottom) / 2;

    if target = L.Data(mid).key then
                     --Search terminates successfully.}
      found := true;
      location := mid;
   
    elsif target < L.Data(mid).key then --Reduce to bottom half.}
        RecBinary2(L, target, bottom, mid - 1, found, location);

    else                        -- Reduce to the top half of the list.}
        RecBinary2(L, target, mid + 1, top, found, location);
    end if;
  end if;
end     RecBinary2;

 
procedure RecBinary2Search( L: in out list; target: Key_Type;  
       found: in out Boolean; location: in out position) is
-- Pre:  The contiguous list L has been created.
-- Post: If an entry in L has key equal to target, then found becomes
--       true and location contains the position of such entry. Otherwise
--       found becomes false and location becomes invalid.
-- Uses: RecBinary2.

begin                   --procedure RecBinary2Search}
  RecBinary2(L, target, 1, L.count, found, location);
end RecBinary2Search;
 


procedure Binary2Search( L: in out list; target: Key_Type;
                   found: in out Boolean;  location: in out position) is
-- Pre:   The contiguous list L has been created.
-- Post: If an entry in L has key equal to target, then found becomes
--       true and location gets the position of one such entry.
--       Otherwise, found becomes false and location is undefined.



  top,    --The target, if present, will always be between bottom and top.}
  bottom,
  mid:    integer; --mid will be location of target when it is found in L.}

begin                   --procedure Binary2Search}
  top := L.count;      --Establish the initial correctness of the invariant.}
  bottom := 1;
  found := false;

  while (not found) and (bottom <= top) loop      --Check for termination.}
    mid := (top + bottom) / 2;
    if target = L.Data(mid).key then    -- Search terminates successfully.}
      found := true;

    elsif target < L.Data(mid).key then
        top := mid - 1;  --Reduce to the bottom half of the list.}
    else                 --Reduce to the top half of the list.}
        bottom := mid + 1;
    end if;
  end loop;   --This if statement guarantees that the invariant still holds.}
  location := mid;
end Binary2Search;

end ch7_sr;