#include <stdio.h>
#include <time.h>

/************************** Function Prototypes **************************/

int shift(
  int number, 
  int setOneSize,
  int setTwoSize, 
  int subtractionValue, 
  int shiftIteration, 
  int subtractionIteration, 
  int **permutations_next_index);

int subtract(
  int number, 
  int setOneSize,
  int setTwoSize, 
  int subtractionValue, 
  int shiftIteration, 
  int subtractionIteration, 
  int **permutations_next_index);

/************************** Algorithm **************************/

int shift(
  long number, 
  int setOneSize,
  int setTwoSize, 
  int subtractionValue, 
  int shiftIteration, 
  int subtractionIteration, 
  int **permutations_next_index)
{

  int i;
  for (i = 0; i < setOneSize; ++i)
  {
    if (shiftIteration >= setOneSize)
    {
      return 0;
    }
    number = number << 1;
    shiftIteration++;
    *(*permutations_next_index += 1) = number;
    subtractionValue = (subtractionValue << 1) + 1;
    subtract(
      number,
      setOneSize,
      setTwoSize, 
      subtractionValue,
      shiftIteration,
      subtractionIteration,
      permutations_next_index);
  }
  return 0;
}

int subtract(
  long number, 
  int setOneSize,
  int setTwoSize,  
  int subtractionValue, 
  int shiftIteration, 
  int subtractionIteration, 
  int **permutations_next_index)
{

  int i;
  for (i = 0; i < setTwoSize - 1; ++i)
  {
    if (subtractionIteration >= setTwoSize - 1)
    {
      return 0;
    }
    number -= subtractionValue;
    subtractionIteration++;
    subtractionValue = subtractionValue << 1;
    *(*permutations_next_index += 1) = number;
    shift(
      number,
      setOneSize,
      setTwoSize, 
      subtractionValue,
      shiftIteration,
      subtractionIteration,
      permutations_next_index);
  }
  return 0;
}

// unsigned long factorial(unsigned long n)
// {
//   return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
// }

/************************** Main **************************/

int main(int argc, char const *argv[])
{

  if (argc != 4)
  {
    printf("  Usage: ./algorithm4.py [set 1 count] [set 2 count]\n");
    return 0;
  }

  // if (!isdigit(argv[1]) || !isdigit(argv[2]))
  // {
  //   printf("ERROR: invalid parameters.  Please input numbers!");
  //   printf("  Usage: ./algorithm4.py [set 1 count] [set 2 count]\n");
  //   return 0;
  // }

  int setOne = atoi(argv[1]);
  int setTwo = atoi(argv[2]);

  long permutation_count = atoi(argv[3]);

  long permutations[permutation_count];

  // create a pointer to access the next free index of the array
  int *permutations_next_index = &permutations[0];

  // initialize the first position in the array with 0b000011111
  long num = 1;
  int j;
  for (j = 1; j < setTwo; ++j)
  {
    num = (num << 1) + 1;
  }
  permutations[0] = num;


  clock_t begin = clock();

  // call the shift function and begin the algorithm's calculations
  shift(permutations[0], setOne, setTwo, 0, 0, 0, &permutations_next_index);
  
  clock_t end = clock();
  double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

  /* Print out all the permutations (in decimal format) */ 
  // printf("[\n");
  // int i;
  // for (i = 0; i < permutation_count; ++i)
  // {
  //   if (i == (permutation_count - 1))
  //   {
  //     printf("%4d", permutations[i]);
  //   }
  //   else
  //   {
  //     printf("%4d, ", permutations[i]);
  //   }
  // }
  // printf("\n]\n");

  printf("Execution Time: %f seconds\n", time_spent);

  return 0;
}