// Example solution to Assignment 4.
// CS 509 - Advanced Programming II, Fall 2002

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
#include <sys/time.h>
#include <unistd.h>
#include <vector>
#include <strings.h>
#include <cstdlib>
#include <iterator>
#include "min-3sort.h"


// A set of input vectors.

   struct input_vectors {
     ivec v0, v1, v2;
     };


// The 3-sort procedure signature.

   typedef answer (* min3sort_fun)(ivec, ivec, ivec);


// Don't print too many errors.

   const unsigned err_max = 4;
   static unsigned err_cnt = 0;
 

// Deja vu, c++ style.

   static bool check_times(time_t, time_t);
   static bool run_test(void);
   static void print_time(time_t);
   static answer timed_run(min3sort_fun, const input_vectors &, time_t &);
   static void make_rand_ivec(ivec &);
   static answer min3sort(ivec, ivec, ivec);
   static bool small_answer_check(const input_vectors &);
   std::ostream & operator << (std::ostream &, const answer &);
   std::ostream & operator << (std::ostream &, const ivec &);
   static void print_emsg(const std::string &, const answer &, const answer &);
   static void fill_and_go(
     const input_vectors &, unsigned, unsigned, unsigned, unsigned);


static bool
check_answer(const answer & a, const answer & c) {

  // Compare the computed sort results a to the check sort results c, printing
  // an error message to std-out if anything's wrong.

  if (a.moves > c.moves) {
    print_emsg(
      "calculated move count larger than the check move count", a, c);
    return false;
    }

  if ((a.v1 == a.v2) or (a.v1 == a.v3) or (a.v3 == a.v2)) {
    print_emsg("modulus repeated in computed answer", a, c);
    return false;
    }

  if (((a.v1 != 1) and (a.v1 != 2) and (a.v1 != 0)) or
      ((a.v2 != 1) and (a.v2 != 2) and (a.v2 != 0)) or
      ((a.v3 != 1) and (a.v3 != 2) and (a.v3 != 0))) {
    print_emsg("invalid modulus value in computer answer", a, c);
    return false;
    }

  return true;
  }


static void
check_sort(answer & a, unsigned moduli[], unsigned moduli_cnts[][3]) {

  // Determine the number of moves in a sort in which all residue moduli[0]
  // elements are moved to vector 1, all residue moduli[1] elements are moved
  // to vector 2, and all residue 2 elements are moved to vector 3.  If the
  // sort is better than the results given in a, update a with the new, better
  // results.

  const unsigned moves = 
    moduli_cnts[1][moduli[0]] + moduli_cnts[2][moduli[0]] +
    moduli_cnts[0][moduli[1]] + moduli_cnts[2][moduli[1]] +
    moduli_cnts[0][moduli[2]] + moduli_cnts[1][moduli[2]];

  if (moves < a.moves) {
    a.moves = moves;
    a.v1 = moduli[0];
    a.v2 = moduli[1];
    a.v3 = moduli[2];
    }
  }


static bool
check_times(time_t answert, time_t checkt) { 

  // Compare an answer time to a check time and print a message if the answer
  // time's too slow compared to the check time.  Return true iff the time's
  // are good.

  if (answert > 2*checkt) {
    fprintf(stderr, "\n!!! Computed min-3sort time is");
    print_time(answert);
    fprintf(stderr, " vs. check min-3sort time ");
    print_time(checkt);
    fprintf(stderr, " (x%3.1f).\n",
	    static_cast<double>(answert)/static_cast<double>(checkt));

    return false;
    }

  return true;
  }


static bool
exhaustive_check(const input_vectors & ivecs, unsigned r) {

  // Generate exhaustive 3-sorting tests by adding residue r elements to the
  // given input vectors, unless r is 3, in which case the vectors are full and
  // the sorting should begin.

  if (r == 3)
    return small_answer_check(ivecs);

  unsigned counts[] = { 1, 2, 3 };

  for (unsigned j = 0; j < 4; j++)
    fill_and_go(ivecs, j, j, j, r);

  do {
    fill_and_go(ivecs, counts[0], counts[1], counts[2], r);
    fill_and_go(ivecs, counts[0], counts[1], counts[1], r);
    fill_and_go(ivecs, counts[1], counts[0], counts[1], r);
    fill_and_go(ivecs, counts[1], counts[1], counts[0], r);
    }
  while (std::next_permutation(counts, counts + 3) && (err_cnt < err_max));
  }


static void 
cnt(const ivec & iv, unsigned cnts[3]) {

  // Count the number of elements of residues 0, 1, and 2 in the vector iv,
  // soring the count for residue i in cnts[i].

  cnts[0] = cnts[1] = cnts[2] = 0;
  for (ivec::const_iterator i = iv.begin(); i != iv.end(); i++)
    cnts[*i % 3]++;
  }


static void 
exhaustive_check(void) {

  // Conduct an exhaustive test of the 3-sorting procedure.

  exhaustive_check(input_vectors(), 0);
  }


static void
fill_and_go(const input_vectors & ivecs,
	    unsigned c0, unsigned c1, unsigned c2, 
	    unsigned r) {

  // Fill the input vectors ivecs with numbers having residue r, putting c0
  // numbers in vector v0 and so on.  Then add the next residue.

  if (err_cnt < err_max) {
    const unsigned values[] = { r, r, r };
    input_vectors new_vecs(ivecs);

    new_vecs.v0.insert(new_vecs.v0.end(), values, values + c0);
    new_vecs.v1.insert(new_vecs.v1.end(), values, values + c1);
    new_vecs.v2.insert(new_vecs.v2.end(), values, values + c2);

    exhaustive_check(new_vecs, r + 1);
    }
  }


static void
make_input_vectors(input_vectors & ivecs) {

  // Make a set of random input vectors and store them in ivecs.

  make_rand_ivec(ivecs.v0);
  make_rand_ivec(ivecs.v1);
  make_rand_ivec(ivecs.v2);
  }


static void
make_rand_ivec(ivec & iv) {

  // Make a random input vector and store it in iv.

  unsigned s = random() % 1000000;
  iv.reserve(s);
  while (s-- > 0)
    iv.push_back(random());
  }


int
main(int argc, char * argv[]) {
  
  bool telltime = false;
  unsigned seed = getpid();

  int c;
  extern char *optarg;
  extern int optind;

  while ((c = getopt(argc, argv, "ts:")) != EOF)
     switch (c) {
     case 't':
       telltime = true;
       break;

     case 's':
       seed = atoi(optarg);
       break;

     case '?':
       std::cerr << "Command format is \"" << argv[0] << " [-t] [-sn]\".\n";
       return EXIT_FAILURE;
     }

  if (optind != argc) {
    std::cerr << "Command format is \"" << argv[0] << " [-t] [-sn]\".\n";
    return EXIT_FAILURE;
    }

  exhaustive_check();

  srandom(seed);

  err_cnt = 0;
  for (unsigned i = 0; (i < 20) and (err_cnt < err_max); i++)
    if (!run_test())
      err_cnt++;
  }


static answer
min3sort(ivec iv1, ivec iv2, ivec iv3) {

  // 3-sort the given input vectors using a minimal number of moves.

  answer a;
  unsigned moduli_cnts[3][3];

  cnt(iv1, moduli_cnts[0]);
  cnt(iv2, moduli_cnts[1]);
  cnt(iv3, moduli_cnts[2]);

  a.moves = iv1.size() + iv2.size() + iv3.size();

  unsigned moduli[] = { 0, 1, 2 };

  do check_sort(a, moduli, moduli_cnts);
  while (std::next_permutation(moduli, moduli + 3));

  return a;
  }


std::ostream & 
operator << (std::ostream & os, const answer & a) {

  // Print the answer a to the output stream os, returning os.

  return os << "v1: " << a.v1 << ", v2: " << a.v2 << ", v3: " << a.v3
	    << ", moves: " << a.moves;
  }


std::ostream & 
operator << (std::ostream & os, const ivec & iv) {

  // Print the int vector iv to the output stream os, returning os.

  std::copy(iv.begin(), iv.end(), std::ostream_iterator<unsigned>(os, " "));

  return os;
  }


static void
print_emsg(const std::string & emsg, const answer & a, const answer & c) {

  // Print to std-err the error message given in emsg, including the contents
  // of the computed answer a and the check answer a.

  std::cerr << "\n!!! " << emsg << ".\n";
  std::cerr << "!!! calculated answer " << a << "\n";
  std::cerr << "!!! check answer      " << c << "\n";
  }


static void 
print_time(time_t t) {

  // Convert the micosecond time interval t into a conveniently small number
  // and print it to std-err.

  if (t < 1000)
    fprintf(stderr, "%5u usec", static_cast<unsigned>(t));
  else if (t < 100000)
    fprintf(stderr, "%5.1f msec", static_cast<double>(t)/1000.0);
  else
    fprintf(stderr, "%5.1f  sec", static_cast<double>(t)/1000000.0);
  }


static bool
run_test(void) {

  // Generate a triplit of random input vectors, feed them to the two sorting
  // procedures, and compare the results.

  time_t answert, check_answert;
  input_vectors vecs;

  make_input_vectors(vecs);

  const answer 
    ans = timed_run(min_3sort, vecs, answert),
    check_ans = timed_run(min3sort, vecs, check_answert);

  return check_answer(ans, check_ans) and check_times(answert, check_answert);
  }


static bool
small_answer_check(const input_vectors & ivecs) {

  // Given the set of small (less than ten element) input vectors, run the
  // sorting procedures and compare the results, printing a detailed error
  // message if anything's out of whack.  Return true or false based on the
  // test results.  Also keep track of the number of errors in the global
  // err_cnt to stop testing if there's too many errors.

  const ivec 
    & v1 = ivecs.v0,
    & v2 = ivecs.v1,
    & v3 = ivecs.v2;
  
  if (check_answer(min_3sort(v1, v2, v3), min3sort(v1, v2, v3))) 
    return true;

  std::cerr << "Input vectors were\n"
	    << "v1:  " << v1 << "\n"
            << "v2:  " << v2 << "\n"
            << "v3:  " << v3 << "\n";
  
  err_cnt++;

  return false;
  }


static answer
timed_run(min3sort_fun m3s, const input_vectors & vecs, time_t & et) {

  // Run the 3-sorting procedure m3s against the given input vectors, returning
  // the result returned by the sort.  Also return in et the sorting time in
  // usecs.

  struct timeval s, e;

  gettimeofday(&s, NULL);
  const answer a = m3s(vecs.v0, vecs.v1, vecs.v2);
  gettimeofday(&e, NULL);

  if (s.tv_sec < e.tv_sec) { 
    e.tv_sec--;
    e.tv_usec += 1000000; 
    }
  et = (e.tv_sec - s.tv_sec)*1000000 + (e.tv_usec - s.tv_usec);

  return a;
  }


// $Log: main.cc,v $
// Revision 1.4  2002/11/11 02:52:48  rclayton
// Define an inserter for int vectors.
//
// Revision 1.3  2002/11/11 02:32:03  rclayton
// Put in all the documentation.
//