// CS 305 - Computer Algorithms I
// Fall 2003
//
// An array-recursive implementation of star runs.

#include <cassert>
#include <cstdlib>
#include <unistd.h>
#include <string>


static unsigned 
star_run_size(const char * const str, unsigned i, unsigned n) {

  // Return the length of the star run starting at str[i].

  if ((i < 0) or (i >= n) or (str[i] != '*'))
    return 0;
  else
    return 1 + star_run_size(str, i + 1, n);
  }


static int 
left_longest_star_run1(const char * const str, unsigned i, unsigned n) {

  // Return the index of the leftmost longest run of stars in str[i..n-1] or -1
  // if there's no such run.

  // The empty string.

     if (i >= n)
       return -1;

  // The rest of the string.

     const int llsr = left_longest_star_run1(str, i + 1, n);

  // The element.

     const unsigned srs = star_run_size(str, i, n);
     if ((srs > 0) and (srs >= star_run_size(str, llsr, n)))
       return i;
     else
       return llsr;
  }


static int 
left_longest_star_run2(const char * const str, unsigned i, unsigned n) {

  // Return the index of the leftmost longest run of stars in str[i..n-1] or -1
  // if there's no such run.

  unsigned int llsr = 0;
  int llsri = -1;
  
  while (i < n) {
    const unsigned l = star_run_size(str, i, n);
    if (l > llsr) {
      llsr = l;
      llsri = i;
      i += l;
      }
    else
      i++;
    }

  return llsri;
  }


static void
test() {

  // Check left_longest_star_run1() against left_longest_star_run2().

  const unsigned 
    max = 10000,
    n = (random() % max) + 1;

  std::string stars(n, '*');

  for (unsigned i = random() % max; i > 0; i--)
    stars[random() % n] = ' ';

  assert(left_longest_star_run1(stars.c_str(), 0, n) == 
	 left_longest_star_run2(stars.c_str(), 0, n));
  }


int
main() {
  srandom(getpid());
  for (unsigned i = 0; i < 100; i++)
    test();
  }


// $Log: stars.cc,v $
// Revision 1.1  2003/09/19 20:02:15  rclayton
// Initial revision
//
// Revision 1.1  2003/09/19 19:16:34  rclayton
// Initial revision
//