// PascalSierpinski.java
// Andrew Davison, ad@coe.psu.ac.th, April 2023

/* Generate Pascal's triangle, a triangular array 
   of the binomial coefficients:

                    1
                  1   1
                1   2   1
              1   3   3   1
            1   4   6   4   1
          1   5  10   10  5   1
        1   6  15  20   15  6   1
      1   7  21  35   35  21  7   1
    1   8  28  56  70   56   28  8   1

   https://en.wikipedia.org/wiki/Pascal%27s_triangle

   Unlike PascalTriangle.java, the values are generated 
   using JML's Binomial.binomial(n,k).

   Note: Apache Commons Numbers has BinomialCoefficient.value(n,k),
   but that returns a long while JML's Binomial.binomial(n,k)
   returns a BigInteger.

   In addition to printing the ASCII triangle, it is also
   drawn as an approximation to Sierpinski's
   triangle -- the odd numbers in a row are drawn as
   black spots.

  https://en.wikipedia.org/wiki/Sierpi%C5%84ski_triangle
  
   Usage:
     > compile PascalSierpinski.java
     > run PascalSierpinski <num. rows>
   e.g.
     > run PascalSierpinski 16
     > run PascalSierpinski 64
     > run PascalSierpinski 128

*/

import java.math.*;
import java.util.*;

import de.tilman_neumann.jml.base.BigIntTriangle;
import de.tilman_neumann.jml.combinatorics.Binomial;


public class PascalSierpinski 
{
  private static BigInteger two = BigInteger.valueOf(2);


  public static void main(String[] args) 
  {
    if (args.length != 1) {
      System.out.println("Usage: run PascalSierpinski <num. rows>");
      return;
    }
    int numRows = Math.abs(Nut.parseInt(args[0]));

    BigIntTriangle tri = new BigIntTriangle(); 

    for (int n=0; n < numRows; n++) {
      ArrayList<BigInteger> row = new ArrayList<>();
      for (int k=0; k <= n; k++)
        row.add(Binomial.binomial(n,k));
      tri.addRow(row); 
    }

    System.out.println("Pascal Triangle of Binomial coefs (rows 0-" +
               (numRows-1) + "):\n\n" + tri);
       // print an ASCII version of the triangle


    // draw a Sierpinski triangle
    StdDraw.setScale(0, numRows+2);
    StdDraw.setPenRadius(0.01);
    for (int r =1; r <= numRows; r++) {
      ArrayList<BigInteger> row = tri.getRow(r);
      for (int i=0; i < r; i++) {
        if (isOdd(row.get(i))) {
          double x = (numRows+2)/2 - r/2 + i;
          if (r%2 == 0)   // even row
            x += 0.5; 
          double y = (numRows+2) - r;
          StdDraw.point(x, y);
        }
      }
    }
  } // end of main()


  private static boolean isOdd(BigInteger bi)
  {   return bi.mod(two).equals(BigInteger.ONE);  }

}  // end of PascalSierpinski class