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

/* Generate a table of
        a^i (mod m)      // the modPow function)
   where
       each row is a different a = 1 to m-1;
       each column is a different i = 1 to m-1
   and m is supplied by the user.

   Note, that we do not display cells for when a or i are 0.

   The most interesting tables are obtained when m is prime.
   
   Aside from the table, rows containing primitive roots are
   marked with a "*", and a grayscale image of the table is
   drawn in a separate window.

   The grayscale visualization was inspired by:
     "A Course in Computational Number Theory"
     David Bressoud, Stan Wagon, Wiley, 2000
     Section 2.3, 'PowerMod Patterns'

   But I've reversed the mapping so that 
      black == 1 ,...  white == n-1 (modulo n)

   Usage:
     > compile ModPowerTable.java
     > run ModPowerTable <modulo>
   e.g.
     > run ModPowerTable 11
     > run ModPowerTable 13

*/

import java.awt.Color;
import java.util.*;
import java.math.*;

import de.tilman_neumann.jml.base.NumberGrid;


public class ModPowerTable
{

  public static void main(String[] args)
  {
    if (args.length != 1) {
      System.out.println("Usage: run ModPowerTable <modulo>");
      return;
    }
    int modulo = Math.abs(Nut.parseInt(args[0]));
    System.out.println(modulo + " is prime? " + Nut.isPrime(modulo));
    BigInteger mod = BigInteger.valueOf(modulo);

    NumberGrid<Integer> grid = new NumberGrid<>("a", 1, "i", 1);

    Color[] grays = new Color[modulo];
    for (int i=1; i < modulo; i++) {  // don't use cell 0
       float level = (1.0f/(modulo-2))*(i-1);
       grays[i] = new Color( level, level, level);
    }

    StdDraw.setScale(1, modulo);

    // build table, grid, and gray squares
    System.out.print("\na\\i ");
    for (int i = 1; i < modulo; i++)
       System.out.printf("%3d", i);
    System.out.println("\n    " + "---".repeat(modulo-1));

    boolean[] valsUsed = new boolean[modulo];

    for (int a = 1; a < modulo; a++) {  // don't print cell 0
      BigInteger ai = BigInteger.valueOf(a);
      System.out.printf("%2d. ", a);

      Arrays.fill(valsUsed, false);
      valsUsed[0] = true;   //  since uses 1 to modulo-1

      List<Integer> rowList = new ArrayList<>();
      for (int i = 1; i < modulo; i++) {   // don't print cell 0
        BigInteger mp = ai.modPow(BigInteger.valueOf(i), mod);
        int mpInt = mp.intValue();
        valsUsed[mpInt] = true; 
        rowList.add(mpInt);
        System.out.printf("%3d", mpInt);

        StdDraw.setPenColor(StdDraw.BLUE);
        StdDraw.square(((double)i)+0.5, ((double)(modulo-a))+0.5, 0.5);
        StdDraw.setPenColor(grays[mpInt]);
        StdDraw.filledSquare(((double)i)+0.5, ((double)(modulo-a))+0.5, 0.5);
      }
      grid.add(rowList);

      if (allUsed(valsUsed))
        System.out.print("  *");   // row contains primitive roots 
      System.out.println();
    }
    System.out.println();

    // System.out.println(grid);

  } /* main */


  private static boolean allUsed(boolean[] bs)
  {
    for (boolean b : bs) 
      if (!b) 
        return false;
    return true;
  }

}  // end of ModPowerTable class