--=============================================================================
--|
--| TASK NAME: numbers.search.(do_search_type)
--|
--| ALGORITHM/STRATEGY: Wait for call to either entry enter_start_search or
--|    entry enter_start_search_from_checkpoint.  In the former case, a call
--|    is made to procedure start_search to begin the search, after which the
--|    wait is resumed.  If enter_start_search_from_checkpoint is called,
--|    the checkpoint file is read, and procedure start_search is called with
--|    restarting=true.
--|
--| NOTES: Task normally terminates using a terminate option in select
--|    statement.
--|
--=============================================================================

WITH other_io;
WITH sequential_io;
WITH text_io;
WITH timekeeper;

SEPARATE (numbers.search)

TASK BODY do_search_type IS

   -- Range of count of digit positions in number
   SUBTYPE number_of_occurrences_range IS natural
      RANGE 0 .. maximum_number_length;

   -- To hold counts of number of occurrences of each digit for checkpoint
   TYPE wide_select_vector_type        IS ARRAY(radix_digit) OF
      number_of_occurrences_range;

   -- Definition of type to record checkpoint
   TYPE checkpoint_record              IS 
      RECORD

         -- Order of checkpointed search
         order               : natural;

         -- Length of PDI sought in checkpointed search
         search_length       : digit_range;

         -- Value of smin at checkpoint (see start_search)
         smin                : number;

         -- Number of digits not yet determined at checkpoint
         free                : number_of_occurrences_range;

         -- Distribution of digits already selected at checkpoint
         select_vector       : wide_select_vector_type;

         -- Next digit to be added to distribution
         digit_to_place      : radix_digit;

         -- Elapsed time of search prior to checkpoint
         elapsed_time        : duration;

         -- Number of combinations tested prior to checkpoint
         combinations_tested : natural;

      END RECORD;

   -- Package to perform I/O of checkpoint records
   PACKAGE checkpoint_io IS NEW sequential_io (element_type =>
      checkpoint_record);

   -- Checkpoint record
   checkpoint                : checkpoint_record;
   -- Checkpoint file
   checkpoint_file           : checkpoint_io.file_type;
   -- One second
   second                    : CONSTANT duration := 1.0;
   -- Time between checkpoints
   checkpoint_interval       : duration := 3600*second;
   -- Flag to tell start_search if search is being restarted from a
   -- checkpoint (true if it is)
   restarting                : Boolean := false;

   -- Uninitialized time value imported from package timekeeper
   uninitialized_time        : CONSTANT timekeeper.time :=
                               timekeeper.uninitialized_time;
   -- Search start time or time of last checkpoint
   t0                        : timekeeper.time := uninitialized_time;
   -- Current time
   t1                        : timekeeper.time;

   -- Exception raised for any error related to opening input file
   file_open_error           : EXCEPTION;

   --==========================================================================
   --|
   --| PROCEDURE NAME: numbers.search.(do_search_type).start_search
   --|
   --| PURPOSE: To perform PDI search.
   --|
   --| PROGRAMMER: Lionel Deimel              DATE WRITTEN: 6/11/90
   --| DATE OF LAST REVISION: 8/9/90          VERSION: 1.2
   --| 
   --| PARAMETERS:
   --|    radix                      (in) radix of PDIs sought
   --|
   --|    order                      (in) order of PDIs sought
   --|
   --|    search_length              (in) length of PDIs sought
   --|
   --| INPUT: None.
   --|
   --| OUTPUT: (To default file) Information about the search before
   --|    and after it is completed.  Procedure select_digits prints out
   --|    PDIs found and other intermediate information.
   --|
   --| ASSUMPTIONS/LIMITATIONS: None.  Search may fail due to inadequate
   --|    storage allocation.
   --|
   --| ALGORITHM/STRATEGY: The real search is carried on by select_digits.
   --|    This procedure merely initializes the search and outputs a summary
   --|    at the end.
   --|
   --| ERROR CHECKS/RESPONSES: None.
   --|
   --| NOTES: In a length-search_length search, any combination of
   --|    search_length base-radix digits is a potential PDI.  To
   --|    determine if it is actually a PDI, all we need do is raise each
   --|    digit to the order power and sum the result.  If the sum
   --|    has the same combination of digits we began with, then we have found
   --|    a PDI.  Procedure select_digits builds up a candidate combination
   --|    of digits by selecting the number of radix-1 digits in
   --|    the combination, then the number of radix-2 digits, etc.  The
   --|    array select_vector keeps track of how many of each digit have been
   --|    put in the trial combination (select_vector(i) is the number of
   --|    occurrences of digit i).  Variable smin holds the minimum possible
   --|    value of any PDI found using the current combination of digits,
   --|    that is, the sum of the order powers of all the digits so far
   --|    placed in the trial digit combination.  Table look-up is used
   --|    in the computation of smin.  Array sum_table(i, j) contains the
   --|    the sum of i instances of j raised to the order power.
   --|
   --==========================================================================

   PROCEDURE start_search (radix : IN radix_range; order : IN natural;
      search_length : IN digit_range) IS

      -- Number of complete digit combinations tested in PDI search
      combinations_tested    : natural;

      -- Default and current number of calls to procedure select_digits
      -- between checks of whether the user has requested service from the
      -- keyboard (see select_digits)
      default_max_calls_to_select_digits
                             : CONSTANT natural := 3000;
      current_max_calls_to_select_digits
                             : natural := default_max_calls_to_select_digits;

      -- Number of calls to select_digits since check was made for keyboard
      -- interrupt
      calls_to_select_digits : natural := 0;

      -- Valid digits in base-radix
      SUBTYPE numeral               IS radix_digit RANGE 0 .. radix - 1;

      -- Range of number of occurrences of any digit possible for this search
      SUBTYPE number_of_occurrences IS natural RANGE 0 .. search_length;

      -- To hold information on digit combinations
      TYPE select_vector_type       IS ARRAY(numeral) OF number_of_occurrences;

      -- Characters used to set off related information in output file
      divider                : CONSTANT string := "--------------------";

      -- Current combination of digits selected for consideration
      select_vector          : select_vector_type := (numeral => 0);

      -- Minimum value of PDI possible with combination of digits derived
      -- from current combination specified by select_vector
      smin                   : number;

      -- Table of sums of powers of base-radix digits
      sum_table              : ARRAY(number_of_occurrences, numeral) OF number;

      -- Current time obtained from package timekeeper
      t                      : timekeeper.time;

      -- Import operators from package timekeeper
      FUNCTION "-" (x : timekeeper.time; y : timekeeper.time) RETURN duration 
         RENAMES timekeeper."-";
      FUNCTION "=" (x : timekeeper.time; y : timekeeper.time) RETURN Boolean
         RENAMES timekeeper."=";


      --=======================================================================
      --|
      --| PROCEDURE NAME:
      --|    numbers.search.(do_search_type).start_search.initialize_table
      --|
      --| PURPOSE: To initialize table of sums of powers of base-radix digits.
      --|
      --| PROGRAMMER: Lionel Deimel              DATE WRITTEN: 6/11/90
      --| DATE OF LAST REVISION: 8/8/90          VERSION: 1.1
      --| 
      --| PARAMETERS:
      --|    radix                      (in) radix of PDIs sought
      --|
      --|    order                      (in) order of PDIs sought
      --|
      --| INPUT/OUTPUT: None.
      --|
      --| ASSUMPTIONS/LIMITATIONS: It is assumed that initialization of
      --|    sum_table proceeds without overflow.
      --|
      --| ALGORITHM/STRATEGY: The initialization is straightforward, using
      --|    the operations on multiple-precision integers defined in package
      --|    numbers.
      --|
      --| ERROR CHECKS/RESPONSES: None.
      --|
      --| NOTES: See description of sum_table in start_search.
      --|
      --=======================================================================

      PROCEDURE initialize_table (radix : IN radix_range; 
         order : IN natural) IS

      BEGIN -- initialize_table

         -- Initialize sums (all 0) for any number of 0 digits
         FOR count IN number_of_occurrences LOOP
            sum_table(count, 0) := make_number(radix, 0);
            END LOOP;

         -- Initialize sums (all 0) for 0 instances of any other digit
         FOR digit IN 1 .. radix - 1 LOOP
            sum_table(0, digit) := make_number(radix, 0);
            END LOOP;

         -- Initialize sum (1) for 1 instance of 1 digit 
         sum_table(1, 1) := make_number(radix, 1);

         -- Initialize entries of row 1 of sum_table that have not yet been
         -- given values
         FOR digit IN 2 .. radix - 1 LOOP
            sum_table(1, digit) := make_number(radix, digit);
            FOR power IN 2 .. order LOOP
               sum_table(1, digit) := digit * sum_table(1, digit);
            END LOOP;
         END LOOP;

         -- Initialize entries in remaining rows of sum_table that have not
         -- yet been given values
         FOR count IN 2 .. search_length LOOP
            FOR digit IN 1 .. radix - 1 LOOP
               sum_table(count, digit) := sum_table(count-1, digit) + 
                  sum_table(1, digit);  
            END LOOP;
         END LOOP;      

      END initialize_table;

      --=======================================================================
      --|
      --| FUNCTION NAME: numbers.search.(do_search_type).start_search.is_pdi
      --|
      --| PURPOSE: To determine if a number is a PDI.
      --|
      --| PROGRAMMER: Lionel Deimel              DATE WRITTEN: 6/11/90
      --| DATE OF LAST REVISION: 8/8/90          VERSION: 1.1
      --| 
      --| PARAMETERS:
      --|    smin                       (in) sum of powers of digits
      --|                               specified by select_vector
      --|                               (candidate PDI)
      --|
      --|    select_vector              (in) combination of digits in smin
      --|
      --| RETURNS: True if smin is a PDI, false otherwise.
      --|
      --| INPUT/OUTPUT: None.
      --|
      --| ASSUMPTIONS/LIMITATIONS: None.
      --|
      --| ALGORITHM/STRATEGY: Check if the combination of digits in smin
      --|    is the same as in select_vector.
      --|
      --| ERROR CHECKS/RESPONSES: None.
      --|
      --| NOTES: None.
      --|
      --=======================================================================

      FUNCTION is_pdi (smin : IN number; select_vector : IN select_vector_type)
         RETURN Boolean IS

         -- Base-smin.radix digit from smin
         digit : numeral;

         -- Variable in which digit combination of smin is computed
         tally : select_vector_type := (numeral => 0);

      BEGIN -- is_pdi

         -- Compute digit combination in smin
         FOR position IN 1 .. smin.high_order_digit LOOP
            digit := smin.digit(position);
            tally(digit) := tally(digit) + 1;
         END LOOP;

         -- Return true smin has same digit combination as that specified by
         -- select_vector
         RETURN (tally = select_vector);

      END is_pdi;

      --=======================================================================
      --|
      --| PROCEDURE NAME: 
      --|    numbers.search.(do_search_type).start_search.report_pdi
      --|
      --| PURPOSE: To announce a number as a PDI.
      --|
      --| PROGRAMMER: Lionel Deimel              DATE WRITTEN: 6/11/90
      --| DATE OF LAST REVISION: 8/8/90          VERSION: 1.2
      --| 
      --| PARAMETERS:
      --|    pdi                        (in) PDI to be output
      --|
      --| INPUT: None.
      --|
      --| OUTPUT: (To default file) number, identification, elapsed time,
      --|    and number of combinations tested.
      --|
      --| ASSUMPTIONS/LIMITATIONS: No provision is made for too short an
      --|    output line.
      --|
      --| ALGORITHM/STRATEGY: Function numbers.convert_to_string is used to 
      --|    obtain a representation of pdi to be output.
      --|
      --| ERROR CHECKS/RESPONSES: None.
      --|
      --| NOTES: Identifies number as PDI or PPDI.
      --|
      --=======================================================================

      PROCEDURE report_pdi (pdi : IN number) IS

         -- Character representation of pdi
         pdi_string : dynamic_string;

      BEGIN -- report_pdi

         -- Obtain and output character representation of pdi
         pdi_string := convert_to_string(pdi);
         text_io.put (pdi_string.char(1 .. pdi_string.length));
         text_io.new_line;

         -- Output its identification
         text_io.put ("is an order-");
         other_io.natural_io.put (order, width => 1);
         IF (order=search_length) THEN
            text_io.put (" PPDI.");
         ELSE
            text_io.put (", length-");
            other_io.natural_io.put (length_of_number(pdi), width => 1);
            text_io.put (" PDI.");
         END IF;
         text_io.new_line;

         -- Output elapsed time of search
         text_io.put ("Found after: ");         
         timekeeper.elapsed_time;
         text_io.new_line;

         -- Output number of combinations of digits tested
         text_io.put ("Number of combinations tested: ");
         other_io.natural_io.put (combinations_tested, width => 1);
         text_io.new_line(2);

      END report_pdi;

      --=======================================================================
      --|
      --| PROCEDURE NAME: 
      --|    numbers.search.(do_search_type).start_search.print_state
      --|
      --| PURPOSE: To display the current state of the PDI search.
      --|
      --| PROGRAMMER: Lionel Deimel              DATE WRITTEN: 6/11/90
      --| DATE OF LAST REVISION: 8/9/90          VERSION: 1.2
      --| 
      --| PARAMETERS:
      --|    smin                       (in) current value of smin (see
      --|                               start_search)
      --|
      --|    digit_to_place             (in) next digit to be selected for
      --|                               trial digit combination
      --|
      --|    select_vector              (in) current digits in trial
      --|                               combination
      --|
      --| INPUT: None.
      --|
      --| OUTPUT: (To default file) number, identification, elapsed time,
      --|    and number of combinations tested.
      --|
      --| ASSUMPTIONS/LIMITATIONS: No provision is made for too short an
      --|    output line.
      --|
      --| ALGORITHM/STRATEGY: Function numbers.convert_to_string is used to 
      --|    obtain a representation of smin to be output.
      --|
      --| ERROR CHECKS/RESPONSES: None.
      --|
      --| NOTES: None.
      --|
      --=======================================================================

      PROCEDURE print_state (smin : IN number; digit_to_place : IN numeral;
         select_vector : IN select_vector_type) IS

         -- Character representation of smin
         smin_string : dynamic_string;

      BEGIN -- print_state 

         -- Obtain and output character representation of smin 
         smin_string := convert_to_string(smin);
         text_io.put_line ("smin:");
         text_io.put (smin_string.char(1 .. smin_string.length));
         text_io.new_line;

         -- Output next digit to be selected in digit combination
         text_io.put ("digit_to_place: ");
         other_io.natural_io.put (digit_to_place, width => 1);
         text_io.new_line;

         -- Output current digit combination
         text_io.put_line ("select_vector:");         
         FOR position IN REVERSE numeral LOOP
            text_io.put ("(");
            other_io.natural_io.put (position,
               width => maximum_radix_length);
            text_io.put (") = ");
            other_io.natural_io.put (select_vector(position), 
               width => 2);
            text_io.new_line;
         END LOOP;

      END print_state;

      --=======================================================================
      --|
      --| PROCEDURE NAME: 
      --|    numbers.search.(do_search_type).start_search.record_checkpoint
      --|
      --| PURPOSE: Output checkpoint information to default output file and
      --|    write checkpoint record to checkpoint file.
      --|
      --| PROGRAMMER: Lionel Deimel              DATE WRITTEN: 6/11/90
      --| DATE OF LAST REVISION: 8/8/90          VERSION: 1.1
      --| 
      --| PARAMETERS:
      --|    order                      (in) order of PDIs sought
      --|
      --|    search_length              (in) length of PDIs sought
      --|
      --|    smin                       (in) current value of smin (see
      --|                               start_search)
      --|
      --|    free                       (in) number of digits yet to be 
      --|                               selected
      --|
      --|    select_vector              (in) current digits in trial
      --|                               combination
      --|    
      --|    digit_to_place             (in) next digit to be selected for
      --|                               trial digit combination
      --|
      --| INPUT: None.
      --|
      --| OUTPUT: (To default file) checkpoint information (time, elapsed
      --|    time, number of combinations tested, smin, digit_to_place,
      --|    and select_vector) and, if necessary, an error message to
      --|    the effect that the checkpoint file cannot be written.
      --|
      --|    (To file "pdi.ckp") checkpoint record.
      --|
      --| ASSUMPTIONS/LIMITATIONS: No provision is made for too short an
      --|    output line.
      --|
      --| ALGORITHM/STRATEGY: Procedure print_state is used to output
      --|    smin, digit_to_place, and select_vector.
      --|
      --| ERROR CHECKS/RESPONSES: If the checkpoint file cannot be written
      --|    for any reason, an error message is output to the default file
      --|    and the procedure continues.
      --|
      --| NOTES: None.
      --|
      --=======================================================================

      PROCEDURE record_checkpoint (order : IN natural; search_length : IN
         digit_range; smin : IN number; free : IN number_of_occurrences;
         select_vector : IN select_vector_type; digit_to_place : IN numeral) IS

         -- Checkpoint record to be written
         checkpoint         : checkpoint_record;

         -- Current time
         checkpoint_time    : timekeeper.time;

         -- Current digits in trial combination in format for checkpoint 
         -- record
         wide_select_vector : wide_select_vector_type := (radix_digit => 0);

      BEGIN -- record_checkpoint 

         -- Output header and divider
         text_io.put_line ("CHECKPOINT");
         text_io.put_line (divider);

         -- Output time and elapsed time
         timekeeper.time_stamp;
         text_io.new_line;
         text_io.put ("Elapsed time: ");
         timekeeper.get_time (checkpoint_time);
         timekeeper.elapsed_time (checkpoint_time);
         text_io.new_line;

         -- Output number of combinations tested
         text_io.put ("Number of combinations tested: ");
         other_io.natural_io.put (combinations_tested, width => 1);
         text_io.new_line;

         -- Output smin, digit_to_place, and select_vector
         print_state (smin, digit_to_place, select_vector);

         -- Change representation of digit combination for writing checkpoint
         FOR digit IN numeral LOOP
            wide_select_vector(digit) := select_vector(digit);
         END LOOP;

         BEGIN

            -- Create and write checkpoint record
            checkpoint := (order, search_length, smin, free,
               wide_select_vector, digit_to_place, checkpoint_time - t,
               combinations_tested);
            checkpoint_io.create (file => checkpoint_file, mode =>
               checkpoint_io.out_file, name => "pdi.ckp");
            checkpoint_io.write (file => checkpoint_file, item =>
               checkpoint);
            checkpoint_io.close (file => checkpoint_file);

         EXCEPTION

            WHEN OTHERS =>
               text_io.new_line;
               text_io.put_line ("Cannot write to checkpoint file; " &
                  "checkpoint ignored");
               text_io.new_line;

         END;

         -- Output divider
         text_io.put_line (divider);
         text_io.new_line;

      END record_checkpoint;

      --=======================================================================
      --|
      --| PROCEDURE NAME: 
      --|    numbers.search.(do_search_type).start_search.select_digits
      --|
      --| PURPOSE: To construct combinations of digits, test them as possible
      --|    PDIs, and report PDIs found.  Also interacts with task synchronize
      --|    to fulfill user requests for information and changes to operating
      --|    parameters.
      --|    
      --|
      --| PROGRAMMER: Lionel Deimel              DATE WRITTEN: 6/11/90
      --| DATE OF LAST REVISION: 8/9/90          VERSION: 3.1
      --| 
      --| PARAMETERS:
      --|    smin                       (in) current value of smin (see
      --|                               start_search)
      --|
      --|    free                       (in) number of digits yet to be 
      --|                               selected
      --|
      --|    select_vector              (in) current digits in trial
      --|                               combination
      --|    
      --|    digit_to_place             (in) next digit to be selected for
      --|                               trial digit combination
      --|
      --| INPUT: None.
      --|
      --| OUTPUT: (To default file) search status information, including
      --|    checkpoint information and PDIs found.
      --|
      --|    (To file "pdi.ckp") checkpoint record (through call to
      --|    record checkpoint).
      --|
      --| ASSUMPTIONS/LIMITATIONS: No provision is made for too short an
      --|    output line.  On entry, it is assumed that select_vector
      --|    represents a combination of digits in the range {radix-1 ...
      --|    digit_to_place-1}.  The sum of these digits, each raised to 
      --|    the appropriate order power, is assumed to be in smin.  On entry,
      --|    it is assumed that free digits remain to be selected.
      --|
      --| ALGORITHM/STRATEGY: Select_digits finds all PDIs that can be
      --|    constructed from the combination of digits in select_vector
      --|    and digits in the range {digit_to_place ... 0}.  It does so by
      --|    calling itself recursively.  Tests are made to prune the search
      --|    tree by not considering digit combinations whose corresponding
      --|    smin will have too many or too few digits.  Through judicious
      --|    use of Boolean restarting, select_digits can reconstruct its
      --|    parameters at the time of a checkpoint, as well as its call
      --|    stack.  (It does this when it is called with restarting=true.)
      --|    At appropriate intervals, checkpoint records are written
      --|    through calls to record_checkpoint.  Also at appropriate
      --|    intervals, calls are made to synchronize.check_interrupts in
      --|    order to process user requests while searches are in progress.
      --|
      --| ERROR CHECKS/RESPONSES: None.
      --|
      --| NOTES: None.
      --|
      --=======================================================================

      PROCEDURE select_digits (smin : IN number; free : IN
         number_of_occurrences;  select_vector : IN select_vector_type;
         digit_to_place : IN numeral) IS

         -- Flag to return status from synchronize.check_interrupts
         flag              : interrupt_flag_type;
         -- New checkpoint interval from synchronize.check_interrupts
         interval          : duration;
         -- New maximum number of calls between checks for user interaction
         -- from synchronize.check_interrupts
         max_calls         : natural;

         -- Updated smin to be used in call to select_digits
         new_smin          : number;
         -- Updated select_vector to be used in calls to select_digits
         new_select_vector : select_vector_type;

      BEGIN -- select_digits

         IF restarting THEN

            -- Setting up to restart PDI search from checkpoint

            IF (digit_to_place /= smin.radix-1) AND THEN 
               (select_vector(digit_to_place+1) /= 
               checkpoint.select_vector(digit_to_place+1)) THEN

               -- Return if not placing first digit and previous digit
               -- has not yet been selected the right number of times
               RETURN;

            ELSIF (select_vector(digit_to_place) =
               checkpoint.select_vector(digit_to_place)) AND THEN
               (digit_to_place = checkpoint.digit_to_place) THEN

               -- Have completed setup for restart

               -- Clear restarting flag for normal operation
               restarting := false;

               -- Output state at beginning of restart
               text_io.put_line ("RESTARTING");
               text_io.put_line (divider);
               timekeeper.start_time (t0);
               timekeeper.time_stamp (t0);
               text_io.new_line;
               text_io.put ("Elapsed time before restart: ");
               timekeeper.print_elapsed_time (checkpoint.elapsed_time);
               text_io.new_line;
               text_io.put ("Number of combinations tested before restart: ");
               other_io.natural_io.put (checkpoint.combinations_tested,
                  width => 1);
               text_io.new_line;
               print_state (smin, digit_to_place, select_vector);
               text_io.put_line (divider);
               text_io.new_line;

            END IF;

         ELSE

            -- Beginning or continuing PDI search

            -- Get current time and initialize start time if at start of
            -- search
            timekeeper.get_time (t1);
            IF (t0 = uninitialized_time) THEN
               t0 := t1;
            END IF;

            -- Record checkpoint if time since last checkpoint or start of
            -- search is greater than specified time between checkpoints
            IF (t1-t0 >= checkpoint_interval) THEN
               record_checkpoint (order, search_length, smin, free, 
                  select_vector, digit_to_place);
               t0 := t1;
            END IF;

         END IF;

         -- Tally additional call to select_digits and, if sufficient calls
         -- have been made, handle requests for user interaction, if any
         calls_to_select_digits := calls_to_select_digits + 1;
         IF (calls_to_select_digits >= current_max_calls_to_select_digits) THEN

            -- Reset tally of calls to select_digits
            calls_to_select_digits := 0;

            -- Handle any user interaction
            synchronize.check_interrupts (flag, interval, max_calls);

            -- Process returned flag
            CASE flag IS

               WHEN checkpoint_change =>

                  -- Set new time between checkpoints
                  checkpoint_interval := interval;
                  synchronize.clear_keyboard;
  
               WHEN max_calls_change =>

                  -- Set new number of calls between checks for user input
                  -- request
                  current_max_calls_to_select_digits := max_calls;
                  synchronize.clear_keyboard;

               WHEN status =>

                  -- Output search status
                  text_io.new_line;
                  text_io.put_line ("STATUS");
                  text_io.put_line (divider);
                  text_io.put ("Performing order-");
                  other_io.natural_io.put (order, width => 1);
                  IF (order = search_length) THEN
                     text_io.put (" P");
                  ELSE
                     text_io.put (", length-");
                     other_io.natural_io.put (search_length, width => 1);
                     text_io.put (" ");
                  END IF;

                  text_io.put ("PDI search in base ");
                  other_io.natural_io.put (radix, width => 1);
                  text_io.new_line;
                  text_io.put ("Checkpoint interval: ");
                  other_io.duration_io.put (checkpoint_interval, 
                     fore =>6, aft => 1);
                  text_io.put_line (" seconds");
                  text_io.put ("Calls to select_digits between polling" &
                     " of keyboard: ");
                  other_io.natural_io.put (current_max_calls_to_select_digits,
                     width => 1);
                  text_io.new_line;
                  timekeeper.time_stamp;
                  text_io.new_line;
                  text_io.put ("Elapsed time: ");
                  timekeeper.elapsed_time;
                  text_io.new_line;
                  text_io.put ("Number of combinations tested: ");
                  other_io.natural_io.put (combinations_tested, width => 1);
                  text_io.new_line;
                  print_state (smin, digit_to_place, select_vector);
                  text_io.put_line (divider);
                  text_io.new_line;
                  synchronize.clear_keyboard;

               WHEN continue =>

                  -- Resume search
                  synchronize.clear_keyboard;

               WHEN no_interrupt =>

                  -- Resume search (no user interaction request)
                  null;

            END CASE;

         END IF;

         -- Abandon search if smallest possible PDI has too many digits
         IF (length_of_number(smin) > search_length) THEN 
            RETURN;         
         END IF;

         -- Copy current digit distribution
         new_select_vector := select_vector;
     
         IF (digit_to_place = 0) THEN

            -- Selecting number of instances of digit 0

            -- Another complete combination has been tested
            combinations_tested := combinations_tested + 1;

            -- Must select free instances of digit 0
            new_select_vector(digit_to_place) := free;

            -- Test for PDI and report if one has been found
            IF is_pdi(smin, new_select_vector) THEN
               report_pdi(smin);
            END IF;

         ELSE

            -- Selecting number of instances of some digit other than 0

            IF (free = 0) THEN

               -- No more digits can be selected; fill out digit combination
               -- with zeroes
               FOR digit IN REVERSE 0 .. digit_to_place LOOP
                  new_select_vector(digit) := 0;
               END LOOP;

               -- Test for PDI and report if one has been found
               IF is_pdi(smin, new_select_vector) THEN 
                  report_pdi(smin);
               END IF;

            ELSE

               -- Additional digits can be selected

               IF (length_of_number(smin) = search_length) THEN

                  -- Smallest possible PDI is right length; try every
                  -- possible number of instances of the next digit to place
                  FOR count IN REVERSE 0 .. free LOOP
                     new_select_vector(digit_to_place) := count;
                     select_digits (smin + sum_table(count, digit_to_place),
                        free - count, new_select_vector, digit_to_place - 1);
                  END LOOP;

               ELSIF (length_of_number(smin) < search_length) THEN

                  -- Digits selected in combination so far cannot make a
                  -- sufficiently long PDI; begin trying possible numbers
                  -- of instances of the next digit to place, starting with
                  -- greatest possible number and quitting if some number of
                  -- instances cannot possibly lead to finding a PDI 
                  FOR count IN REVERSE 0 .. free LOOP
                     new_smin := smin + sum_table(count, digit_to_place);
                     IF (length_of_number(new_smin + sum_table(free - count,
                        digit_to_place -1)) >= search_length) THEN
                        new_select_vector(digit_to_place) := count;
                        select_digits (new_smin, free - count,
                           new_select_vector, digit_to_place -1);
                     ELSE
                        EXIT;
                     END IF;
                  END LOOP;

               END IF;

            END IF;

         END IF;

      END select_digits;

   BEGIN -- start_search

      -- Output information about search, including whether it is a PDI or
      -- PPDI search
      text_io.new_line;
      text_io.put ("Begin order-");
      other_io.natural_io.put (order, width => 1);
      IF (order = search_length) THEN
        text_io.put (" P");
      ELSE
        text_io.put (", length-");
        other_io.natural_io.put (search_length, width => 1);
        text_io.put (" ");
      END IF;
      text_io.put ("PDI search in base ");
      other_io.natural_io.put (radix, width => 1);
      text_io.new_line;

      -- Output current date and time
      timekeeper.start_time (t);
      timekeeper.time_stamp (t);
      text_io.new_line (2);

      -- Perform initializations for search
      initialize_table (radix, order);
      smin := make_number(radix, 0);
      combinations_tested := 0;

      -- Perform actual search
      select_digits (smin, search_length, select_vector, radix - 1);

      -- Output time of search
      text_io.put ("End search after ");
      timekeeper.elapsed_time;
      text_io.new_line;

      -- Output number of combinations tested
      text_io.put ("Number of combinations tested: ");
      other_io.natural_io.put (combinations_tested, width => 1);
      text_io.new_line (2);

   END start_search;

   BEGIN -- do_search_type

      LOOP

         SELECT   

            -- Wait for call to perform PDI search
            ACCEPT enter_start_search (radix : IN radix_range;
               order : IN natural; search_length : IN digit_range) DO

               -- Perform search
               start_search (radix, order, search_length);

            END enter_start_search;

         OR

            -- Wait for call to restart search from checkpoint
            ACCEPT enter_start_search_from_checkpoint;

            BEGIN

               -- Get search parameters from  checkpoint file
               checkpoint_io.open (file => checkpoint_file, 
                  mode => checkpoint_io.in_file, name => "pdi.ckp");
               checkpoint_io.read (file => checkpoint_file, 
                  item => checkpoint);
               checkpoint_io.close (file => checkpoint_file);

            EXCEPTION

               WHEN checkpoint_io.name_error =>
                  text_io.new_line;
                  text_io.put_line ("Cannot find file ""pdi.ckp""");
                  RAISE file_open_error;

               WHEN checkpoint_io.use_error =>
                  text_io.new_line;
                  text_io.put_line ("Cannot open file ""pdi.ckp""");
                  RAISE file_open_error;

               WHEN checkpoint_io.end_error =>
                  text_io.new_line;
                  text_io.put_line ("End-of-file error reading file" &
                     " ""pdi.ckp""");
                  RAISE file_open_error;

               WHEN OTHERS =>
                  text_io.new_line;
                  text_io.put_line ("Problem encountered reading file " &
                     """pdi.ckp""");
                  RAISE file_open_error;

            END;

            -- Perform search
            restarting := true;
            start_search (checkpoint.smin.radix, checkpoint.order,
               checkpoint.search_length);

            -- Abort process to allow termination with TERMINATE option of
            -- Select
            ABORT monitor_keyboard; 

         OR

            TERMINATE;

         END SELECT; 
   
      END LOOP;

   EXCEPTION

      WHEN file_open_error =>
         text_io.new_line;
         text_io.put_line ("Terminating program");         
         text_io.new_line;
         ABORT monitor_keyboard;

      WHEN constraint_error | numeric_error =>
         text_io.new_line;
         text_io.put_line ("Numerical error encountered");
         text_io.new_line;
         text_io.put_line ("Terminating program");         
         text_io.new_line;
         ABORT monitor_keyboard;

      WHEN storage_error =>
         text_io.new_line;
         text_io.put_line("Storage error encountered");
         text_io.new_line;
         text_io.put_line ("Terminating program");         
         text_io.new_line;
         ABORT monitor_keyboard;

      WHEN OTHERS =>
         text_io.new_line;
         text_io.put_line("Program error encountered");
         text_io.new_line;
         text_io.put_line ("Terminating program");         
         text_io.new_line;
         ABORT monitor_keyboard;

   END do_search_type;