// Programming Assignment 3 - Example Solution.
// CS 176, Summer 2001

#include "mas.h"


// This is an array algorithm, and we have a choice of two generic array
// algorithms:
//
//   do_something(a[1..n])		do_something(a[1..n])
//     something(a[1])			  do_something(a[1..n-1])
//     do_something(a[2..n])		  something(a[n])
//
// Both will work for this problem, but the left one is perhaps the easier of
// the two to understand, so we'll start with that.
//
// What does something(a[1]) do?  We need to find the maximal sample in a, and
// this is the only chance we get to look at a[1], so it seems sensible to
// expect something() to involve looking for a maximal sample containing a[1].
// Also, a[1] is the left end of the array, so searching for maximal samples
// containing a[1] requires looking to the right only, which simplifies the
// search.
//
// So much for something(); what does the rest of the program do?
// do_something(a[2..n]) returns the length of the maximal sample in a[2..n];
// something(a[1]) returns the maximal sample containing a[1]; the only thing
// left to do is compare the length of the two maximal samples and return the
// larger.


// A forward declaration for the subroutine implementing someting().

   static int fms(const int a[], int n, int start);


// The implementation of do_something().

sample find_maximal_sample(const int a[], int a_size) {

  // Given the integer array a of a_size elements, find and return a maximal
  // array sample in a.

  sample mas;
  mas.start = 0;
  mas.length = 0;

  // For each element a[start] in a, find the maximal array sample having its
  // left-most element at a[start].  Remember the largest maximal sample found.

     for (int start = 0; start < a_size; start++) {
       const int length = fms(a, a_size, start);
       if (mas.length < length) {
	 mas.start = start;
	 mas.length = length;
	 }
       }

  return mas;
  }


// The implementation of something().

static int fms(const int a[], int n, int start) {

  // Given the integer array a of n elements, find the size of the largest
  // array sample with the left-most array element at a[start].  Return the
  // sample's length.

  // For each element a[s] in the sample starting at a[start] and working
  // right...

     for (int s = start; s < n; s++)

       // Find the first occurence of the value in a[s] to the right of a[s] in
       // the sample.

	  for (int e = s + 1; e < n; e++)
	    if (a[s] == a[e]) {

	      // If found, the sample can be no longer than a[s .. e - 1]
	      // because of the repeated value at a[e]; reset n accordingly and
	      // stop searching for a[s].

		 n = e;
		 break;
  	         }

  // The maximal sample with its left element at a[start] ends at a[n].  Return
  // the sample's length.

  return n - start;
  }


// Now for the second generic array algorithm.  We are going to essentially use
// the same development approach we used for the first generic algorithm,
// except now we're interested in the maximal sample containing a[n] as its
// right-most element.
//
// The big difference between the first and second generic algorithms is that
// the second generic algorithm processes rest of the array first and then
// processes a[n], which means we can have do_something() do some extra work
// for us to simplify the search for the maximal sample containing a[n] as its
// rightmost element.
//
// We use two simple facts about samples in the algorithm:
//
//  1 A piece of a sample is a sample too.
//
//  2 A maximal sample can't grow larger and remain a sample.
//
// The extra work we require of do_something(a[1..n-1]) is to also remember the
// length of the largest sample ending at the right-end of the array.  With
// this length the search for the maximal sample containing a[n] becomes easy:
// one pass through the sample looking for a[n].  If we find a[n] in the
// right-most sample, we chop the sample and fact one assures us we still have
// a sample without anymore scanning; if we don't find it, fact 2 assures us we
// can stop at the end of the sample because adding more elements would make it
// a non-sample.
//
// With these observations, the code follows.


sample find_maximal_sample_two(const int a[], int a_size) {

  // Given the integer array a of a_size elements, find and return a maximal
  // array sample in a.

  // Initially both samples are empty.

     sample mas;
     mas.start = 0;
     mas.length = 0;

     int rightmost_length = 0;

   for (int end = 0; end < a_size; end++) {

     // Scan left from the end element until you hit the start of the rightmost
     // maximal sample or you find a match to the end element in the sample.

	int rightmost_start = end - 1;
	while ((end - rightmost_start <= rightmost_length) && 
	       (a[rightmost_start] != a[end]))
	  rightmost_start--;

     // Where ever the scan stopped is the start of the new rightmost maxiaml
     // sample; compute its length.

	rightmost_length = end - rightmost_start;

     // Compare the length of the rightmost maximal sample to the length of the
     // maximal sample and keep the larger of the two.

	if (mas.length < rightmost_length) {
	  mas.start = end - rightmost_length + 1;
	  mas.length = rightmost_length;
	  }
     }

  return mas;
  }