/**
 * utest_sort.c - unit tests for the 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 "sort.h"
#include "swap.h"


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

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


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

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

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

/**
 * Report a sorting error.
 */
void
report_sorting_error (char *original[], char *sorted[], char *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 strings
 *   len, an integer
 *   k, in integer
 *   expected, an array of strings
 * 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 (char *perm[], int len, int k, char *expected[])
{
  int i;
  char *copy[len];

  if (k == 0)
    {
      ++tests;
      copy_array (perm, copy, len);
#ifdef PRINT_TESTS
      printf ("Checking: ");
      print_array (perm, len); 
      printf ("\n");
#endif
      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 ()
{
  char *values[] = { "alpha", "better", "charlie", "deltoids", 
                     "ech-o", "fawks-trot", "gee", "indy go",
                     "jackalope"  };

  int size = sizeof(values) / sizeof(char *);

  int i;
  for (i = 0; i <= 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