/**
 * utest_selection_sort.c - unit tests for the selection_sort procedure.
 */

// +--------+---------------------------------------------------------
// | Design |
// +--------+

/**
 * We start with a known sorted array, build all permutations,
 * sort each permutation, and check to see if the result matches
 * the original.
 */

// +---------+--------------------------------------------------------
// | Headers |
// +---------+

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "array_utils.h"


// +-----------+------------------------------------------------------
// | Constants |
// +-----------+

/** The size of the largest array we use for testing. */
#ifndef MAX_SIZE
#define MAX_SIZE 8
#endif

/** The function that fills in the ith element of the array. */
#ifndef ITH_VALUE
#define ITH_VALUE(i) (i)
#endif


// +-----------+------------------------------------------------------
// | Variables |
// +-----------+

static int errors = 0;          // A count of errors
static int tests = 0;           // A count of tests conducted


// +---------+--------------------------------------------------------
// | Helpers |
// +---------+

/**
 * Copy an array
 */
void
copy_array (int source[], int target[], int len)
{
  int i;
  for (i = 0; i < len; i++)
    target[i] = source[i];
} // copy_array

/**
 * Print an array
 */
void 
print_array (int a[], int len)
{
  int i;
  if (len == 0)
    printf ("{ }");
  else
    {
      printf ("{ %3d", a[0]);
      for (i = 1; i < len; i++)
        printf (", %3d", a[i]);
      printf (" }");
    }
} // print_array

/**
 * Report a sorting error.
 */
void
report_sorting_error (int original[], int sorted[], int expected[], int len)
{
  printf ("Encountered sorting error.\n");
  printf ("  Original:  ");
  print_array (original, len);
  printf ("\n");
  printf ("  Sorted:    ");
  print_array (sorted, len);
  printf ("\n");
  printf ("  Expected:  ");
  print_array (expected, len);
  printf ("\n");
} // report_sorting_error

/**
 * Procedure:
 *   test_permutations
 * Parameters:
 *   perm, an array of integers
 *   len, an integer
 *   k, in integer
 *   expected, an array of integers
 * Purpose:
 *   Make a bunch of permutations of perm (by permuting the first k
 *   elements), sort each permutation, and then check to see whether
 *   or not it's sorted.
 */
void
test_permutations (int perm[], int len, int k, int expected[])
{
  int i;
  int copy[MAX_SIZE];

  if (k == 0)
    {
      ++tests;
      copy_array (perm, copy, len);
#ifdef PRINT_TESTS
      printf ("Checking: ");
      print_array (perm, len); 
      printf ("\n");
#endif
      selection_sort (copy, len);
      // Check the result
      for (i = 0; i < len; i++)
        {
          if (copy[i] != expected[i])
            {
              ++errors;
              report_sorting_error (perm, copy, expected, len);
              break;
            }
        } // for
    } // if (k == 0)

  else // if (k > 0)
    {
      for (i = 0; i < k; i++)
        {
          copy_array (perm, copy, len);
          swap (copy, i, k-1);
          test_permutations (copy, len, k-1, expected);
        }
    } // if (k > 0)
} // test_permutations



// +------+-----------------------------------------------------------
// | Main |
// +------+

int
main ()
{
  int values[MAX_SIZE];
  int i;

  for (i = 0; i < MAX_SIZE; i++)
     values[i] = ITH_VALUE (i);
 
  for (i = 0; i <= MAX_SIZE; i++)
    test_permutations (values, i, i, values);

#ifdef PRINT_TESTS
  printf ("%d tests conducted.\n", tests);
#endif
  if (errors)
    {
      printf ("%d errors encountered.\n", errors);
      return EXIT_FAILURE;
    }
  else
    {
      return EXIT_SUCCESS;
    }
} // main