/* This class is for the purpose of computing the minimum and maximum
** elements in a given segment of an array of integers.  It uses threads
** so that the work is done (potentially, at least) in parallel.
**
** Authors: R. McCloskey and < STUDENTS' NAMES >
** Known defects: ...
*/
public class ParallelMinMax implements Runnable {

   // class constant
   // --------------

   private static final int LENGTH_THRESHOLD = 7; // For array segments no 
                                                  // longer than this, all
                                                  // computations are done
                                                  // without threads being
                                                  // created.
   // instance variables
   // ------------------

   private int[] a;       // Array whose min and max values are sought
   private int low, high; // a[low..high) is the segment of the array
                          // for which this object is responsible
   private int minimum;   // minimum value within a[low..high)
   private int maximum;   // maximum value within a[low..high)


   // constructor
   // -----------

   /* Establishes the array segment (namely, ary[low..high)) whose 
   ** minimum and maximum elements are to be identified by this object.
   ** pre: 0 <= low <= high <= a.length
   */
   public ParallelMinMax(int[] ary, int low, int high) {
      this.a = ary; this.low = low; this.high = high;
   }

   /* Establishes that the array segment whose minimum and maximum values
   ** are to be identified by this object is the entire array.
   */
   public ParallelMinMax(int[] ary) { this(ary, 0, ary.length); }


   // observers
   // ---------

   /* Returns the minimum value in a[low..high).
   ** pre: this object's computeMinMax() method has
   **      been called and has completed its execution
   */
   public int minimumOf() { return minimum; }


   /* Returns the maximum value in a[low..high).
   ** pre: this object's computeMinMax() method has
   **      been called and has completed its execution
   */
   public int maximumOf() { return maximum; }


   // run() method
   // ------------

   public void run() { computeMinMax(); }


   /* Identifies the minimum and maximum elements within a[low..high)
   ** and assigns them to the respective instance variables.
   */
   public void computeMinMax() {
      if (high - low <= LENGTH_THRESHOLD) {
         // Compute the min and max of a[low..high), which is a short segment,
         // via a method that does the work sequentially.
         computeMinMaxSequential();

         // Print a message reporting the results computed by this object.
         reportMinMax("SHORT");
      }
      else {
         // For a longer segment, use child threads!

         // compute the index half way between low and high
         int mid = (low + high) / 2;

         // Create two threads (using new objects of this class), one 
         // responsible for finding the min and max within a[low..mid) 
         // and the other responsible for finding the min and max within
         // a[mid..high).

         //    MISSING CODE


         // start the two threads

         //    MISSING CODE


         // wait for each of the two threads to terminate

         //    MISSING CODE


         // Use the just-computed values of the min and max elements of 
         // a[low..mid) and a[mid..high), respectively, to compute the 
         // min and max elements of a[low..high), storing the relevant
         // numbers in the instance variables.

         //    MISSING CODE


         // Print a message reporting the results computed by this object.
         reportMinMax("LONG");
      }
   }

   /* Computes the minimum and maximum values in a[low..high) sequentially
   ** and places those values, respectively, into the instance variables 
   ** 'minimum' and 'maximum'.
   ** pre: 0 <= low < high <= a.length (i.e., a[low..high) is nonempty)
   */
   private void computeMinMaxSequential() {
      this.minimum = -37;  // an arbitrary value
      this.maximum = 512;  // "     "        "

      // STUB!

   }

   /* Prints a message indicating the min and max values that were computed
   ** by this object.
   */
   private void reportMinMax(String remark) {
      System.out.printf("In %s range [%d..%d) ", remark, low, high);
      System.out.printf("the min is %d and the max is %d\n",
                        this.minimumOf(), this.maximumOf());
   }

   /* Applies join() to the given thread, catching InterruptedException 
   ** if it is thrown.
   */
   private void join(Thread t) {
      try {
         t.join();
      }
      catch (InterruptedException e) {
         e.printStackTrace(System.out);
      }
   }

}