import java.util.Scanner;
import java.util.Random;
import java.util.Arrays;

/* An instance of this class includes recursive methods for computing 
** the sum of the elements in an array (or a specified segment thereof).
** It keeps track of the number of calls made to recursive methods
** and the maximum depth to which the recursion descended.  These values
** are accessible via observer methods.
**
** A main() method is included for the purpose of running tests upon
** the methods and comparing their performances.  In particular, it is
** intended to illustrate how two different recursive versions of a 
** method can differ drastically in terms of the depth to which the 
** recursion descends, when applied to the same input.
**
** Author: R. McCloskey and < STUDENTS' NAMES >
** Date: April 2021
** Known defects:
*/


public class ArraySummer {

   // instance variables
   // ------------------

   private int callCntr;       // to keep track of how many calls were made
   private int callDepth;      // to recursive methods and the max depth to
   private int maxCallDepth;   // which the recursion has descended.


   // methods that (recursively) sum the elements of a specified array segment
   // ------------------------------------------------------------------------

   /* Returns the sum of the elements in the given array.
   */
   public int segSumA(int[] ary) { 
      return segSumA(ary, 0, ary.length);
   }

   /* Returns the sum of the elements in the given array segment,
   ** ary[low..high).
   ** pre: 0 <= low <= high <= ary.length
   */
   public int segSumA(int[] ary, int low, int high) {
      entering();
      int result;
      if (low == high) 
         { result = 0; }
      else 
         { result = ary[low] + segSumA(ary, low+1, high); }
      leaving();
      return result;
   }


   /* Returns the sum of the elements in the given array.
   */
   public int segSumB(int[] ary) { 
      return segSumB(ary, 0, ary.length);
   }

   /* Returns the sum of the elements in the given array segment,
   ** ary[low..high).
   ** pre: 0 <= low <= high <= ary.length
   */
   public int segSumB(int[] ary, int low, int high) {
      entering();
      int result = 0;  // the = 0 is only to appease the compiler

      //  < MISSING CODE >

      leaving();
      return result;
   }

   // methods that pertain to the call and depth counters 
   // ---------------------------------------------------

   public int callCount() { return callCntr; }

   public void resetCallCount() { callCntr = 0; }

   /* Returns the current depth of recursion.
   ** Is useful only internally within this class.
   */
   private int currentDepth() { return callDepth; }

   public int maxCallDepth() { return maxCallDepth; }

   public void resetDepth() { 
      callDepth = 0;
      maxCallDepth = 0;
   }

   /* In response to entering a recursive method, updates the global variables
   ** keeping track of the # of such calls made, the current depth of recursion,
   ** and the max depth achieved (since reset() was called).
   */
   private void entering() {
      callCntr++;
      callDepth++;
      if (callDepth > maxCallDepth) 
         { maxCallDepth = callDepth; }
   }

   /* In response to leaving a recursive method, updates the global variables
   ** keeping track of the # of such calls made, the current depth of recursion,
   ** and the max depth achieved (since reset() was called).
   */
   private void leaving() {
      callDepth--;
   }


   // main method (for testing purposes)
   // ----------------------------------

   public static void main(String[] args) {
      System.out.println("Welcome to the Recursive Array Summing Program!");
      ArraySummer summer = new ArraySummer();
      Scanner keyboard = new Scanner(System.in);
      String seedPrompt = "\nEnter integer to be used as seed for Random object:";
      int seed = readInt(keyboard, seedPrompt);
      String lengthPrompt = "Enter desired array length (negative to quit): ";
      int len = readInt(keyboard, lengthPrompt);
      while (len >= 0) {
         int[] ary = randomArray(len, seed, 0, 20);
         System.out.printf("Computing sum of elements in array\n");
         displayArray(ary);
         int resultA = performTest(summer, 'A', ary);
         int resultB = performTest(summer, 'B', ary);
         if (resultA != resultB) {
            System.out.println("** ERROR: segSumA() and segSumB() " +
                               "produced different results!");
         }
         seed = readInt(keyboard, seedPrompt);
         len = readInt(keyboard, lengthPrompt);
      }
      System.out.println("\nGoodbye.");
   }

   private static void displayArray(int[] a) {
      final int LINE_WIDTH = 75;
      final char COMMA = ',';
      String arrayImage = Arrays.toString(a);
      final int N = arrayImage.length();
      int pos = 0;
      while (pos != N) {
         if (pos + LINE_WIDTH >= N) {
            System.out.println(arrayImage.substring(pos));
            pos = N;
         }
         else {
            int endPos = arrayImage.indexOf(COMMA, pos+LINE_WIDTH) + 1;
            if (endPos == 0) {  // unusual case
               System.out.println(arrayImage.substring(pos));
               pos = N;
            }
            else {
               System.out.println(arrayImage.substring(pos, endPos));
               pos = endPos; 
            }
         }
      }
      System.out.println();
   }

   /* Uses the given ArraySummer to compute the sum of the elements in the 
   ** given array, using either segSumA() or segSumB() according to the
   ** value of 'whichMethod'.  Then reports the results and returns the
   ** computed sum to the caller.
   */
   private static int performTest(ArraySummer s, char whichMethod, int[] a) {
      s.resetCallCount();
      s.resetDepth();
      int sum;
      if (whichMethod == 'A')
         { sum = s.segSumA(a); } 
      else  // use method B 
         { sum = s.segSumB(a); }

      System.out.printf("\nsegSum%c():\n", whichMethod);
      System.out.printf("   applied to array of length: %d\n", a.length);
      System.out.printf("   reported sum: %d\n", sum);
      System.out.printf("   call count: %d\n", s.callCount());
      System.out.printf("   max depth of recursion: %d\n", s.maxCallDepth());
      return sum;
   }


   /* Using an instance of the Random class (initialized using the given
   ** seed), creates, fills, and returns an array of the specified length
   ** containing "random" values in the specified range (minVal..maxVal).
   ** pre: len >= 0, minVal <= maxVal
   */
   private static int[] randomArray(int len, int seed, int minVal, int maxVal) {
      int[] result = new int[len];
      Random rand = new Random(seed);
      int minMaxDelta = maxVal - minVal + 1;
      for (int i=0; i != result.length; i++) {
         result[i] = minVal + rand.nextInt(minMaxDelta);
      }
      return result;
   }

   /* Prints the given prompt and returns the integer read by
   ** the given Scanner object.
   */
   private static int readInt(Scanner scanner, String prompt) {
      System.out.print(prompt);
      return scanner.nextInt();
   }

}