/****************************************************
 *
 * file: gencascade.cc
 *
 *  Program to generate a cascade merge table
 * 
 * The LAST column of the table contains the total runs 
 *   for that row
 *
 ****************************************************/

#include <iostream.h>
#include <iomanip.h>

int main()
{
  long int **p;
  int i,j;
  int r = 20;
  int c = 5;
  long int sum;
  int maxR = r;

 p = new long int*[r];
 for (i = 0; i < r; i++)
   p[i] = new long int[c+1];

 // set first row
 p[0][0] = 1; p[0][c] = 1;
 for ( i = 1; i < c; i++ )
   p[0][i] = 0;

 // generate the rest
 for (i = 1; i < r; i++)
   {
     // last value in row is same as first from previous
     p[i][c-1] = p[i-1][0];
     p[i][c] = p[i][c-1]; // for the sum
     sum = p[i][c];

     for (j = 1; j < c; j++)
       {
	 p[i][c] += p[i-1][j]; // works like running total
	 p[i][c-j-1] = p[i][c];
	 sum += p[i][c];
       }
     p[i][c] = sum;

     // watch out for overflow
     if (sum < 0)
       {
	 maxR = i;
	 break;
       }
   }

 // display:
 for (i = 0; i < maxR; i++ )
   {
     cout << setw(2) << i << ':';
     for (j = 0; j < c+1; j++)
       cout << setw(12) << p[i][j] << "  ";
     cout << endl;
   }

  return(0);
}