package stdlib;

/**
 * Provides methods to generate arrays of Integer objects,
 * arrays of doubles in [0.0,1.0), and arrays of characters.
 */
public class ArrayGenerator {
  /**
   * Generate an array of strings from a string.  Each array element will be a string of length one.
   * For example
   * <pre>
   *   fromString("DOG") generates the array { "D", "O", "G" }
   * </pre>
   *
   * @see In#readAllStrings()
   * @see StdIn#readAllStrings()
   */
  public static String[] fromString (String s) {
    int N = s.length();
    String[] a = new String[N];
    for (int i = 0; i < N; i++)
      a[i] = s.substring(i, i+1);
    return a;
  }
  /** 
   * Generate an array of doubles from a string.  The string should include a list of numbers, separated by single spaces. 
   * For example
   * <pre>
   *   doublesFromString("10.3 -Infinity 11)" generates the array { 10.3, -Infinity, 11.0 }
   * </pre>
   * 
   * @see java.lang.Double#parseDouble(java.lang.String)
   */
  public static double[] doublesFromString (String s) {
    if ("".equals (s)) return new double[0]; // empty array is a special case
    String[] nums = s.split (" ");
    double[] result = new double[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
      try {
        result[i] = Double.parseDouble (nums[i]);
      } catch (NumberFormatException e) {
        throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
      }
    }
    return result;
  }
  /** 
   * Generate an array of ints from a string.  The string should include a list of numbers, separated by single spaces. 
   * For example
   * <pre>
   *   doublesFromString("10 11)" generates the array { 10, 11.0 }
   * </pre>
   * 
   * @see java.lang.Integer#parseInt(java.lang.String)
   */
  public static int[] intsFromString (String s) {
    if ("".equals (s)) return new int[0]; // empty array is a special case
    String[] nums = s.split (" ");
    int[] result = new int[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
      try {
        result[i] = Integer.parseInt (nums[i]);
      } catch (NumberFormatException e) {
        throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a int", s, nums[i]));
      }
    }
    return result;
  } 
  /**
   * Generate an array of length N whose values are chosen uniformly from the range [minValue,maxValue).
   */
  public static int[] intRandom (int N, int minValue, int maxValue) {
    if (N < 0) throw new IllegalArgumentException ();
    int[] a = new int[N];
    for (int i = 0; i < N; i++) {
      a[i] = StdRandom.uniform (minValue, maxValue);
    }
    return a;
  }
  /**
   * Generate an array of length N whose values are chosen uniformly from the range [0,numValues).
   */
  public static int[] intRandom (int N, int numValues) {
    if (N < 0) throw new IllegalArgumentException ();
    int[] a = new int[N];
    for (int i = 0; i < N; i++) {
      a[i] = StdRandom.uniform (numValues);
    }
    return a;
  }
  /**
   * Generate an array of length N with values 0, 1, ..., N-1.
   */
  public static int[] intSortedUnique (int N) {
    if (N < 0) throw new IllegalArgumentException ();
    int[] a = new int[N];
    for (int i = 0; i < N; i++) {
      a[i] = i;
    }
    return a;
  }
  /**
   * Generate an array of length N with values N-1, N-2, ... 0.
   */
  public static int[] intReverseSortedUnique (int N) {
    if (N < 0) throw new IllegalArgumentException ();
    int[] a = new int[N];
    for (int i = 0; i < N; i++) {
      a[i] = N - 1 - i;
    }
    return a;
  }
  /**
   * Generate a shuffled array of length N with unique values 0, 1, ... N-1
   */
  public static int[] intRandomUnique (int N) {
    int[] a = intSortedUnique (N);
    StdRandom.shuffle (a);
    return a;
  }
  /**
   * Generate a partially sorted array with unique elements.
   * The number of inversions will be between N and 2N.
   * This algorithm moves random elements an arbitrary amount until the threshold is achieved.
   */
  public static int[] intPartiallySortedUnique (int N) {
    if (N < 6) throw new IllegalArgumentException ("array too small");
    int[] a = intSortedUnique (N);
    int totalDistance = 0; // this is an approximation of the number of inversions
    int range = (int) (Math.sqrt (N));
    while (totalDistance < N) {
      int i = StdRandom.uniform (N);
      int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
      totalDistance += Math.abs (i - r);
      int temp = a[i];
      a[i] = a[r];
      a[r] = temp;
    }
    return a;
  }
  /**
   * Generate a partially sorted array with unique elements.
   * The number of inversions will be between N and 2N.
   * This algorithm moves all elements a small amount.
   */
  public static int[] intPartiallySortedUnique2 (int N) {
    if (N < 6) throw new IllegalArgumentException ("array too small");
    int[] a = intSortedUnique (N);
    int range = 4;
    for (int i=0; i<N; i++) {
      int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
      int temp = a[i];
      a[i] = a[r];
      a[r] = temp;
    }
    return a;
  }

  /**
   * Generate an array of length N whose values are chosen uniformly from the range [minValue,maxValue).
   */
  public static Integer[] integerRandom (int N, int minValue, int maxValue) {
    if (N < 0) throw new IllegalArgumentException ();
    Integer[] a = new Integer[N];
    for (int i = 0; i < N; i++) {
      a[i] = StdRandom.uniform (minValue, maxValue);
    }
    return a;
  }
  /**
   * Generate an array of length N whose values are chosen uniformly from the range [0,numValues).
   */
  public static Integer[] integerRandom (int N, int numValues) {
    if (N < 0) throw new IllegalArgumentException ();
    Integer[] a = new Integer[N];
    for (int i = 0; i < N; i++) {
      a[i] = StdRandom.uniform (numValues);
    }
    return a;
  }
  /**
   * Generate an array of length N with values 0, 1, ..., N-1.
   */
  public static Integer[] integerSortedUnique (int N) {
    if (N < 0) throw new IllegalArgumentException ();
    Integer[] a = new Integer[N];
    for (int i = 0; i < N; i++) {
      a[i] = i;
    }
    return a;
  }
  /**
   * Generate an array of length N with values N-1, N-2, ... 0.
   */
  public static Integer[] integerReverseSortedUnique (int N) {
    if (N < 0) throw new IllegalArgumentException ();
    Integer[] a = new Integer[N];
    for (int i = 0; i < N; i++) {
      a[i] = N - 1 - i;
    }
    return a;
  }
  /**
   * Generate a shuffled array of length N with unique values 0, 1, ... N-1
   */
  public static Integer[] integerRandomUnique (int N) {
    Integer[] a = integerSortedUnique (N);
    StdRandom.shuffle (a);
    return a;
  }
  /**
   * Generate a partially sorted array with unique elements.
   * The number of inversions will be between N and 2N.
   * This algorithm moves random elements an arbitrary amount until the threshold is achieved.
   */
  public static Integer[] integerPartiallySortedUnique (int N) {
    if (N < 6) throw new IllegalArgumentException ("array too small");
    Integer[] a = integerSortedUnique (N);
    int totalDistance = 0; // this is an approximation of the number of inversions
    int range = (int) (Math.sqrt (N));
    while (totalDistance < N) {
      int i = StdRandom.uniform (N);
      int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
      totalDistance += Math.abs (i - r);
      Integer temp = a[i];
      a[i] = a[r];
      a[r] = temp;
    }
    return a;
  }
  /**
   * Generate a partially sorted array with unique elements.
   * The number of inversions will be between N and 2N.
   * This algorithm moves all elements a small amount.
   */
  public static Integer[] integerPartiallySortedUnique2 (int N) {
    if (N < 6) throw new IllegalArgumentException ("array too small");
    Integer[] a = integerSortedUnique (N);
    int range = 4;
    for (int i=0; i<N; i++) {
      int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
      Integer temp = a[i];
      a[i] = a[r];
      a[r] = temp;
    }
    return a;
  }

  //    public static void main (String[] args) {
  //        StdOut.println (java.util.Arrays.toString (integerRandom (20, 1)));
  //        StdOut.println (java.util.Arrays.toString (integerRandom (20, 2)));
  //        StdOut.println (java.util.Arrays.toString (integerRandom (20, 4)));
  //
  //        // This is a unit test for partiallySortedUnique, to ensure that the result has inversions between N and 2N.
  //        int N = 80;
  //        for (int i = 0; i < 100; i++) {
  //            Integer[] a = integerPartiallySortedUnique2 (N);
  //            Integer[] b = integerRandomUnique (N);
  //            StdOut.format ("N = %3d, partiallySorted = %3d, random = %3d\n", N, algs22.XInversions.count (a), algs22.XInversions.count (b));
  //        }
  //        for (int j = 0; j < 12; j++) {
  //            N = N*2;
  //            for (int i = 0; i < 100; i++) {
  //                Integer[] a = integerPartiallySortedUnique2 (N);
  //                int inversions = algs22.XInversions.count (a);
  //                if (inversions < N || inversions > 2*N)
  //                    StdOut.format ("N = %3d, partiallySorted = %3d\n", N, inversions);
  //            }
  //        }
  //    }

  /**
   * Generate an array of length N whose values are chosen uniformly from the range [0,numValues).
   */
  public static double[] doubleRandom (int N, int numValues) {
    if (N < 0) throw new IllegalArgumentException ();
    double[] a = new double[N];
    for (int i = 0; i < N; i++) {
      a[i] = Math.random ();
    }
    return a;
  }
  /**
   * Generate an array of length N with values 0, 1, ..., N-1.
   */
  public static double[] doubleSortedUnique (int N) {
    if (N < 0) throw new IllegalArgumentException ();
    double[] a = new double[N];
    for (int i = 0; i < N; i++) {
      a[i] = i;
    }
    return a;
  }
  /**
   * Generate an array of length N with values N-1, N-2, ... 0.
   */
  public static double[] doubleReverseSortedUnique (int N) {
    if (N < 0) throw new IllegalArgumentException ();
    double[] a = new double[N];
    for (int i = 0; i < N; i++) {
      a[i] = N - 1 - i;
    }
    return a;
  }
  /**
   * Generate a shuffled array of length N with unique values 0, 1, ... N-1
   */
  public static double[] doubleRandomUnique (int N) {
    double[] a = doubleSortedUnique (N);
    StdRandom.shuffle (a);
    return a;
  }
  /**
   * Generate a partially sorted array with unique elements.
   * The number of inversions will be between N and 2N.
   * This algorithm moves random elements an arbitrary amount until the threshold is achieved.
   */
  public static double[] doublePartiallySortedUnique (int N) {
    if (N < 6) throw new IllegalArgumentException ("array too small");
    double[] a = doubleSortedUnique (N);
    int totalDistance = 0; // this is an approximation of the number of inversions
    int range = (int) (Math.sqrt (N));
    while (totalDistance < N) {
      int i = StdRandom.uniform (N);
      int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
      totalDistance += Math.abs (i - r);
      double temp = a[i];
      a[i] = a[r];
      a[r] = temp;
    }
    return a;
  }
  /**
   * Generate a partially sorted array with unique elements.
   * The number of inversions will be between N and 2N.
   * This algorithm moves all elements a small amount.
   */
  public static double[] doublePartiallySortedUnique2 (int N) {
    if (N < 6) throw new IllegalArgumentException ("array too small");
    double[] a = doubleSortedUnique (N);
    int range = 4;
    for (int i=0; i<N; i++) {
      int r = StdRandom.uniform (Math.max (0, i-range), Math.min (N-1, i+range));
      double temp = a[i];
      a[i] = a[r];
      a[r] = temp;
    }
    return a;
  }

  /**
   * Read in and return an array of Strings from fileName.  Input must begin with dimensions.
   *
   * @see In#readAllStrings()
   * @see StdIn#readAllStrings()
   */
  public static String[] readString1D(String fileName) {
    return readString1D (new In(fileName));
  }
  /**
   * Read in and return an array of Strings from in. Input must begin with dimensions.
   *
   * @see In#readAllStrings()
   * @see StdIn#readAllStrings()
   */
  public static String[] readString1D(In in) {
    int N = in.readInt();
    String[] a = new String[N];
    for (int i = 0; i < N; i++) {
      a[i] = in.readString();
    }
    return a;
  }

  /**
   * Print an array of Strings to standard output.
   */
  public static void print(Object[] a) {
    int N = a.length;
    StdOut.println(N);
    for (int i = 0; i < N; i++) {
      StdOut.format("%s ", a[i]);
    }
    StdOut.println();
  }

  /**
   * Read in and return an M-by-N array of Strings from fileName. Input must begin with dimensions.
   */
  public static String[][] readString2D(String fileName) {
    return readString2D (new In(fileName));
  }
  /**
   * Read in and return an M-by-N array of Strings from in. Input must begin with dimensions.
   */
  public static String[][] readString2D(In in) {
    int M = in.readInt();
    int N = in.readInt();
    String[][] a = new String[M][N];
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) {
        a[i][j] = in.readString();
      }
    }
    return a;
  }

  /**
   * Print the M-by-N array of Strings to standard output.
   */
  public static void print(Object[][] a) {
    int M = a.length;
    int N = a[0].length;
    StdOut.println(M + " " + N);
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) {
        StdOut.format("%s ", a[i][j]);
      }
      StdOut.println();
    }
  }

  /**
   * Read in and return an array of doubles from fileName. Input must begin with dimensions.
   *
   * @see In#readAllDoubles()
   * @see StdIn#readAllDoubles()
   */
  public static double[] readDouble1D(String fileName) {
    return readDouble1D (new In(fileName));
  }
  /**
   * Read in and return an array of doubles from in. Input must begin with dimensions.
   *
   * @see In#readAllDoubles()
   * @see StdIn#readAllDoubles()
   */
  public static double[] readDouble1D(In in) {
    int N = in.readInt();
    double[] a = new double[N];
    for (int i = 0; i < N; i++) {
      a[i] = in.readDouble();
    }
    return a;
  }

  /**
   * Print an array of doubles to standard output.
   */
  public static void print(double[] a) {
    int N = a.length;
    StdOut.println(N);
    for (int i = 0; i < N; i++) {
      StdOut.format("%9.5f ", a[i]);
    }
    StdOut.println();
  }


  /**
   * Read in and return an M-by-N array of doubles from fileName. Input must begin with dimensions.
   */
  public static double[][] readDouble2D(String fileName) {
    return readDouble2D (new In(fileName));
  }
  /**
   * Read in and return an M-by-N array of doubles from in. Input must begin with dimensions.
   */
  public static double[][] readDouble2D(In in) {
    int M = in.readInt();
    int N = in.readInt();
    double[][] a = new double[M][N];
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) {
        a[i][j] = in.readDouble();
      }
    }
    return a;
  }

  /**
   * Print the M-by-N array of doubles to standard output.
   */
  public static void print(double[][] a) {
    int M = a.length;
    int N = a[0].length;
    StdOut.println(M + " " + N);
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) {
        StdOut.format("%9.5f ", a[i][j]);
      }
      StdOut.println();
    }
  }


  /**
   * Read in and return an array of ints from fileName. Input must begin with dimensions.
   *
   * @see In#readAllInts()
   * @see StdIn#readAllInts()
   */
  public static int[] readInt1D(String fileName) {
    return readInt1D (new In(fileName));
  }
  /**
   * Read in and return an array of ints from in. Input must begin with dimensions.
   *
   * @see In#readAllInts()
   * @see StdIn#readAllInts()
   */
  public static int[] readInt1D(In in) {
    int N = in.readInt();
    int[] a = new int[N];
    for (int i = 0; i < N; i++) {
      a[i] = in.readInt();
    }
    return a;
  }

  /**
   * Print an array of ints to standard output.
   */
  public static void print(int[] a) {
    int N = a.length;
    StdOut.println(N);
    for (int i = 0; i < N; i++) {
      StdOut.format("%9d ", a[i]);
    }
    StdOut.println();
  }


  /**
   * Read in and return an M-by-N array of ints from fileName. Input must begin with dimensions.
   */
  public static int[][] readInt2D(String fileName) {
    return readInt2D (new In(fileName));
  }
  /**
   * Read in and return an M-by-N array of ints from in. Input must begin with dimensions.
   */
  public static int[][] readInt2D(In in) {
    int M = in.readInt();
    int N = in.readInt();
    int[][] a = new int[M][N];
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) {
        a[i][j] = in.readInt();
      }
    }
    return a;
  }

  /**
   * Print the M-by-N array of ints to standard output.
   */
  public static void print(int[][] a) {
    int M = a.length;
    int N = a[0].length;
    StdOut.println(M + " " + N);
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) {
        StdOut.format("%9d ", a[i][j]);
      }
      StdOut.println();
    }
  }


  /**
   * Read in and return an array of booleans from fileName. Input must begin with dimensions.
   */
  public static boolean[] readBoolean1D(String fileName) {
    return readBoolean1D (new In(fileName));
  }
  /**
   * Read in and return an array of booleans from in. Input must begin with dimensions.
   */
  public static boolean[] readBoolean1D(In in) {
    int N = in.readInt();
    boolean[] a = new boolean[N];
    for (int i = 0; i < N; i++) {
      a[i] = in.readBoolean();
    }
    return a;
  }

  /**
   * Print an array of booleans to standard output.
   */
  public static void print(boolean[] a) {
    int N = a.length;
    StdOut.println(N);
    for (int i = 0; i < N; i++) {
      if (a[i]) StdOut.print("1 ");
      else      StdOut.print("0 ");
    }
    StdOut.println();
  }

  /**
   * Read in and return an M-by-N array of booleans from fileName. Input must begin with dimensions.
   */
  public static boolean[][] readBoolean2D(String fileName) {
    return readBoolean2D (new In(fileName));
  }
  /**
   * Read in and return an M-by-N array of booleans from in. Input must begin with dimensions.
   */
  public static boolean[][] readBoolean2D(In in) {
    int M = in.readInt();
    int N = in.readInt();
    boolean[][] a = new boolean[M][N];
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) {
        a[i][j] = in.readBoolean();
      }
    }
    return a;
  }

  /**
   * Print the  M-by-N array of booleans to standard output.
   */
  public static void print(boolean[][] a) {
    int M = a.length;
    int N = a[0].length;
    StdOut.println(M + " " + N);
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) {
        if (a[i][j]) StdOut.print("1 ");
        else         StdOut.print("0 ");
      }
      StdOut.println();
    }
  }
}