-- Item :      Contingous List Searching Package Specification
-- Reference : Data Structures and Program Design, Pascal, p 198
-- Author :    Kruse, recoded by Paul Stachour, stachour@winternet.com
-- Version :   1.0, 1999/Jan/21
-- 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 adg_cl;      -- Access the specification of the Continugous List Package
package ch7_sr is 
List_Size: constant := 10_000;  -- How big are our lists?
type Key_Type is new Integer;   -- What do we use as a Key?
type List_Entry is record       -- What are out list entries like?
  Key: Key_Type;
  Info: Natural;
end record;
-- Create the specialized package from the template.
package Key_Cl is new adg_cl(List_Size, List_Entry);  use Key_Cl;

-- Here's the routines that provide the measurement data
procedure Reset_Counts;
-- Pre:  None
-- Post: The count of comparisons has been set to zero, and the timer
--       restarted.

procedure Get_Counts
 (Comparisons : out Natural;
  Interval    : out Duration);
-- Pre:  The counts have not been reset since last started for
--       measurement.
-- Post: The count of comparisons is the natural number indicating
--       how many comparisions have been made since last reset.
--       The interval is the time in seconds and fractions 
--       since last reset.

-- Define the general signature of a search method
type SearchMethod is access procedure(
   L: in out list; target: Key_Type;
   found: in out Boolean;  location: in out position);

procedure SequentialSearch( L: in out list; target: Key_Type;
                          found: in out Boolean;  location: in out position);
-- 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.

procedure Mixup( L: in out list);
-- 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.

 
procedure InsertOrder(x: List_Entry;  L: in out list);
-- 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.


procedure RecBinary1( L: in out list; target: Key_Type; bottom, top: integer;
                      found: out Boolean;  location: out position);
-- 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.



procedure RecBinary1Search( L: in out list; target: Key_Type; 
 found: in out Boolean;  location: in out position);
-- 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.

procedure Binary1Search( L: in out list; target: Key_Type;
                   found: in out Boolean;  location: in out position);
-- 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.


procedure RecBinary2( L: in out list; target: Key_Type; bottom, top: integer;
                      found: in out Boolean;  location: in out position);
-- 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;

 
procedure RecBinary2Search( L: in out list; target: Key_Type;  
       found: in out Boolean; location: in out position);
-- 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.


procedure Binary2Search( L: in out list; target: Key_Type;
                   found: in out Boolean;  location: in out position);
-- 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.

end ch7_sr;