// File: pascals.cpp
// Written by Dr. Spiegel, May 1996, updated Nov. 2007
/*!
 * Example of bi-directional linked list
 * Builds tabel of binomial coefficients
 */

#include <stdio.h>

/*!
 * container of a single coefficient
 */
 struct node {
  float coeff;
  struct node *next;
 };
 typedef struct node NodePtr;

/*!
 * Special node for building the structure.
 * A rowrec has two pointers, one to a rowrec, and one to a node.
 * Each row of the table is anchored by a rowrec
 */
 struct rowrec {
  int num;
  struct rowrec *nextrow;
  NodePtr *thisrow;
 };
 typedef struct rowrec RowPtr;

 RowPtr *start; /**< Global variable is not necessary? */
 int    col,n;

/*!
 * Compute the factorial of an integer.
 * \param	n	the value for whose factorial will be computed
 * \returns	the factorial of n
 */
float fac(int n)
{
 if (n<=1) return(1.0);
 else return(n*fac(n-1));
}

/*! 
 * Compute the binomial coefficient.
 * \param	n	n in C(n,r)
 * \param	r	r in C(n,r)
 * \returns	C(n,r)
 */
float C_n_r(int n,int r)
{return(fac(n)/(fac(n-r)*fac(r)));}

/*!
 * Generate a row of Pascal's Triangle.
 * \param	first	The data structure holding the triangle
 * \param	rownum	Row to generate
 */
void generate_row(NodePtr **first, int rownum)
{int i;
 NodePtr *p,*q;
 for (i=0;i<=rownum;i++) {
  if (*first != NULL) {
   q=new node;
   p->next=q;
   p=q;
  }
  else p=new node;
  if (*first==NULL) *first=p;
  p->coeff=C_n_r(rownum,i);
  p->next=NULL;
 }
}

/*!
 * Create Pascal's triangle
 * \param	n 	Rows to generate
 * \param	start	The data structure holding the triangle
 */
void make_table(int n,RowPtr **start)
{int i;
 RowPtr *p;
 *start=new rowrec;
 (*start)->num=0;
 p=*start;
 p->thisrow=NULL;
 p->nextrow=NULL;
 generate_row(&(p->thisrow),0);
 for (i=1;i<=n;i++) {
  p->nextrow=new rowrec;
  p->nextrow->num=p->num+1;
  p=p->nextrow;
  p->thisrow=NULL;
  generate_row(&(p->thisrow),i);
  p->nextrow=NULL;
 }
}

 /*!
  * Print a single row of the triangle.
  * \param	p	Pointer to first element in row
  */
  void printrow(NodePtr *p)
  {while (p!=NULL) {
    printf("%7.0f   ",p->coeff);
    p=p->next;
   }
  }

/*!
 * Print the entire Triangle
  * \param	start	rowptr heading first row
 */
void print(RowPtr *start)
{float x;
 while (start!=NULL) {
  x=((n-(start->num-1))/2*6)-2;
  /*
  if (start->num % 2 == 0)
    gotoxy(x+2*(n-start->num+3),wherey());
  else gotoxy(x+2*(n-start->num+1),wherey());
  */
  printrow(start->thisrow);
  printf("\n");
  start=start->nextrow;
 }
}

/*!
 * Get #rows and create triangle
 */ 
main()
{start=new rowrec;
 printf(" How many rows (starting from 0) should be generated?");
 printf(" Enter a Number between 0 and 12. Larger values cause");
 printf(" Unreadable Results                      >");
 scanf("%d",&n);
 printf("Pascal""s triangle for N=%d\n",n);
 make_table(n,&start);
 print(start);
}