#include <math.h>

#include "configure.h"
#include "types.h"
#include "list.h"
#include "mymath.h"
#include "debug.h"

int mymath_factorial(int n);
void mymath_permut(int n, index_list **out_list);
void mymath_cached_permut(int n, index_list **out_list);
void mymath_generate_n_over_k(int n, int k, index_list **out_list);
void mymath_cached_generate_n_over_k(int n, int k, index_list **out_list);


int mymath_factorial(int n)
{
  /* because we initialized erg to 1 this */
  /* function works also correct for n = 1*/
  /* n = 0 */
  int i;
  int erg = 1; 

  for (i = 2; i <= n; i++)
    erg *= i;

  return erg;
}

void mymath_permut(int n, index_list **out_list)
{
  /*
    We calculate the permutations as follows 
    counter counts from zero to n factorial  
    counter will be interpreted like a number 
    with base n. Then you go digit by digit and
    copy the digits not already copied entry from
    source.

    Example n = 3:
    Position : | 0 | 1 | 2 |
               +-----------+
    Entry    : | 0 | 1 | 2 |

    counter  counter as number 
             of base n           added entry
    ----------------------------------------
    0        000                 0 1 2 (first, first, first)
    1        100                 1 0 2 (second, first, first)
    2        200                 2 0 1 (third, first, first)
    3        010                 0 2 1 (first, second, first)
    4        110                 1 2 0 (second, second, first)
    5        210                 2 1 0 (third, second, first)
  */

  index_list *temp_element;
  BOOLEAN    input_ok = TRUE;
  int        i;
  int        j;
  int        counter;
  int        temp_counter;
  int        n_factorial;
  int        nth;
  int        index;
  index_list *ref_array;
  index_list *remap;

  *out_list = NULL;
  if (n < 1)
    input_ok = FALSE;
  else
    {
      list_new_item(index_list, ref_array);
      list_new_item(index_list, remap);
      for (i = 0; i < n; i++)
	ref_array->value[i] = i;
      memcpy(remap->value, ref_array->value, n * sizeof(int));
      n_factorial = mymath_factorial(n);
      for (counter = 0; counter < n_factorial; counter++)
	{
	  /* restore remap list as the identity 0, 1, 2, 3, 4... */
	  memcpy(remap->value, ref_array->value, n * sizeof(int));
	  /* appand current counter configuration to out_list */
	  list_new_item(index_list, temp_element);
	  temp_counter = counter;
	  for (i = 0; i < n; i++)
	    {
	      nth = temp_counter % (n - i);
	      temp_counter = (temp_counter - nth) / (n - i);
	      index = remap->value[nth];
	      temp_element->value[i] = ref_array->value[index];
	      /* reconfigure the remap array */
	      for (j = nth; j < n - i - 1; j++)
		remap->value[j] = remap->value[j+1];
	    }
	  list_add_element_at_head(index_list, *out_list, temp_element);
	}
    } /* if */
}

void mymath_cached_permut(int n, index_list **out_list)
{
  static BOOLEAN    global_initialized = FALSE;
  static BOOLEAN    calculated[WIDTH];
  static index_list *cache[WIDTH];

  PRE((n - 1) < WIDTH, "n must be less than WIDTH\n");
  if (!global_initialized)
    {
      int i;
      for (i = 0; i < WIDTH; i++)
	{
	  calculated[i] = FALSE;
	  cache[i] = NULL;
	}
    }
  if (calculated[n - 1])
    *out_list = cache[n - 1];
  else
    {
      mymath_permut(n, out_list);
      cache[n - 1] = *out_list;
      calculated[n - 1] = TRUE;
    }
}

void mymath_generate_n_over_k(int n, int k, index_list **out_list)
{
  index_list *counter;
  index_list *temp_element;
  int        i;
  BOOLEAN    proceed = TRUE;
  BOOLEAN    input_ok = TRUE;
  
  *out_list = NULL;
  if ((n < k) || (n < 1) || (k < 1))
    input_ok = FALSE;
  else
    /* if (input_ok) */
    {
      list_new_item(index_list, counter);
      
      for (i = 0; i < k; i++)
	counter->value[i] = i;
      for (i = 0; proceed && (i < k); i++)
	proceed = proceed && (counter->value[i] == (n - k + i));
      proceed = (!proceed);
      while (proceed)
	{
	  /* Append current counter configuration to the outlist */
	  list_new_item(index_list, temp_element);
	  memcpy(temp_element->value, counter->value, k * sizeof(int));
	  list_add_element_at_head(index_list, *out_list, temp_element);
	  /* increment counter in the right order */
	  /* therefor: */
	  /* find first position we can increment */
	  /* (where no overflow occurs) and */
	  for (i = k - 1; (counter->value[i]) == (n - (k - i)); i--);
	  /* increment this position and */
	  counter->value[i]++;
	  /* reinitialize all higher positions */
	  /* with the lowest values that are possible */
	  for (i = i + 1; i < k; i++)
	    counter->value[i] = counter->value[i - 1] + 1;
	  /* check if we have to proceed any more */
	  /* proceed = TRUE; */ /* we won't be here if preceed != TRUE */
	  for (i = 0; proceed && (i < k); i++)
	    proceed = proceed && (counter->value[i] == (n - k + i));
	  proceed = (!proceed);
	}
      /* We forgot to append the last counter configuration */
      /* Because we don't need the counter or the counter's memory */
      /* any longer, we append the counter by itself */
      list_add_element_at_head(index_list, *out_list, counter);
    }
}

void mymath_cached_generate_n_over_k(int n, int k, index_list **out_list)
{
  static BOOLEAN      global_initialized = FALSE;
  static BOOLEAN      calculated[WIDTH][WIDTH];
  static index_list * cache[WIDTH][WIDTH];

  PRE((n - 1) < WIDTH, "n must be less than WIDTH\n");
  PRE((k - 1) < WIDTH, "k must be less than WIDTH\n");
  if (!global_initialized)
    {
      int i;
      int j;

      for (i = 0; i <= WIDTH; i++)
	for (j = 0; j <= WIDTH; j++)
	  {
	    calculated[i][j] = FALSE;
	    cache[i][j] = (index_list *) NULL;
	  }
      global_initialized = TRUE;
    }
  if (TRUE == calculated[n - 1][k - 1])
    { *out_list = cache[n - 1][k - 1]; }
  else 
    {
      mymath_generate_n_over_k(n, k, out_list);
      cache[n - 1][k - 1] = *out_list;
      calculated[n - 1][k - 1] = TRUE;
    }
}