// If this program produces any other warning or error messages when
// compiled, it probably means you need to fix a problem in your
// matrix class.

using namespace std;

#include "SparseMatrix.hh"

#include <stdlib.h>
#include <strstream.h>
#include <set>
#include <iostream>

// reliably reproducible pseudorandom numbers:
int rnd()               { return int(lrand48()); }
int rnd(int mac)        { return int(drand48() * mac); }

///////////////////////////////////////////////////////////////////////////////

// Normally, this declaration would go in a separate header file.

class ErrorContext                              // displays test results
{
public:
  ErrorContext(ostream &os);                    // write header to stream
  void desc(const char *msg, int line);         // write line/description
  void result(bool good);                       // write test result
  ~ErrorContext();                              // write summary info
  bool ok() const;                              // true iff all tests passed

private:
  ostream &os;                                  // output stream to use
  int passed;                                   // # of tests which passed
  int total;                                    // total # of tests
  int lastline;                                 // line # of most recent test
  set<int> badlines;                            // line #'s of failed tests
  bool skip;                                    // skip a line before title?
};

///////////////////////////////////////////////////////////////////////////////

// Normally, these method implementations would go in a separate source file.

ErrorContext::ErrorContext(ostream &os)
  : os(os), passed(0), total(0), lastline(0), skip(false)
{
  os << "line: ";
  os.width(65);
  os.setf(ios::left, ios::adjustfield);
  os << "description" << " result" << endl;
  os.width(78);
  os.fill('~');
  os << "~" << endl;
  os.fill(' ');
  os.setf(ios::right, ios::adjustfield);
}

void ErrorContext::desc(const char *msg, int line)
{
  if(lastline != 0 || (*msg == '-' && skip))
  {
    os << endl;
  }

  os.width(4);
  os << line << ": ";
  os.width(65);
  os.setf(ios::left, ios::adjustfield);
  os << msg << " ";
  os.setf(ios::right, ios::adjustfield);
  os.flush();

  lastline = line;
  skip = true;
}

#define desc(x) desc(x, __LINE__) // fnord

void ErrorContext::result(bool good)
{
  if(good)
  {
    os << "ok";
    passed++;
  }
  else
  {
    os << "ERROR";
    badlines.insert(lastline);
  }

  os << endl;
  total++;
  lastline = 0;
}

ErrorContext::~ErrorContext()
{
  os << endl << "Passed " << passed << "/" << total << " tests." << endl
     << endl;

  if(badlines.size() > 0)
  {
    os << "For more information, please consult:" << endl;
    for(set<int>::const_iterator it = badlines.begin();
        it != badlines.end(); it++)
    {
      os << "  " << __FILE__ << ", line " << *it << endl;
    }
    os << endl;

    if(badlines.size() > 2)
    {
      os << "We recommend that you fix the topmost failure before going on."
         << endl << endl;
    }
  }
}

bool ErrorContext::ok() const
{
  return passed == total;
}

///////////////////////////////////////////////////////////////////////////////

void empty(ErrorContext &ec)
{
  ec.desc("--- Empty matrices (0 by 0) ---");

  // If this test fails, it means that getrows returned a non-zero value when
  // called on an "empty" (0x0) matrix created with the default constructor.
  ec.desc("default constructor and getrows");

  // construct an empty matrix using the default constructor:
  const SparseMatrix a;

  // make sure "getrows" method returns zero for this matrix:
  ec.result(a.getrows() == 0);


  // same as above, for getcols instead of getrows:
  ec.desc("default constructor and getcols");
  ec.result(a.getcols() == 0);


  // If this test fails, it means that getrows returned a non-zero value when
  // called on an "empty" (0x0) matrix created with the 2-argument constructor.
  ec.desc("two-argument constructor and getrows");

  // construct an empty matrix using the two-argument constructor:
  const SparseMatrix b(0, 0);

  // make sure "getrows" method returns zero for this matrix:
  ec.result(b.getrows() == 0);


  // same as above, for getcols instead of getrows:
  ec.desc("two-argument constructor and getcols");
  ec.result(b.getcols() == 0);
}

void basic(ErrorContext &ec, int level)
{
  const int rows = rnd(level*level) + 1;
  const int cols = rnd(level*level) + 1;

  {
    ostrstream oss;
    oss << "--- Basic operations (" << rows << " by " << cols << " matrix) ---"
        << ends;
    ec.desc(oss.str());

    // make sure getrows and getcols work for non-empty matrices:
    ec.desc("getrows and getcols");
    SparseMatrix a(rows, cols);
    ec.result(a.getrows() == rows && a.getcols() == cols);
  }

  // repeat "level" times:
  for(int pass = 1; pass <= level; pass++)
  {
    // choose a valid matrix position and value:
    const int r = rnd(rows);
    const int c = rnd(cols);
    const int v = rnd();

    // let the user know what we're about to try:
    ostrstream oss;
    oss << "getelem and setelem (1), pass " << pass << ": element (" << r
        << "," << c << ")" << ends;
    ec.desc(oss.str());

    // create a new matrix of the appropriate size:
    SparseMatrix a(rows, cols);

    // set the value:
    a.setelem(r, c, v);

    // verify the value:
    ec.result(a.getelem(r, c) == v);
  }


  // repeat "level" times:
  for(int pass = 1; pass <= level; pass++)
  {
    {
      // If this part (2a) of the test fails, but part (1) succeeded, you
      // might have forgotten to explicitly initialize the contents of
      // your matrix to all-zeroes in your two-argument constructor.  You
      // can do this using a loop which sets each element to zero.

      ostrstream oss;
      oss << "getelem and setelem (2a), pass " << pass << " [read]" << ends;
      ec.desc(oss.str());
    }

    // create a new matrix:
    SparseMatrix a(rows, cols);
  
    // ensure that the matrix initially contains only zeroes:
    bool good = true;
    for(int r = 0; r < rows; r++)
    for(int c = 0; c < cols; c++)
      good &= a.getelem(r, c) == 0;

    ec.result(good);

    {
      // A failure here may be due to a bug in getelem, setelem, or
      // your two-argument constructor.  Did you swap the order of the
      // row and column somewhere?  Did you allocate enough space?

      ostrstream oss;
      oss << "getelem and setelem (2b), pass " << pass << " [write]" << ends;
      ec.desc(oss.str());
    }
    a.setelem(0,0,0);

    // fill the matrix with various exciting values
    for(int r = 0; r < rows; r++)
    for(int c = 0; c < cols; c++)
      a.setelem(r, c, (r - 666*c) * pass);

    // now read the values back out and see if they're all correct
    good = true;
    for(int r = 0; r < rows; r++)
    for(int c = 0; c < cols; c++)
      good &= a.getelem(r, c) == (r - 666*c) * pass;
    
    ec.result(good);
  }
}

void copy(ErrorContext &ec)
{
  ec.desc("--- Copying matrices ---");


  ec.desc("copy constructor: target dimensions");
  // create a largish matrix and fill in some values:
  SparseMatrix a(123, 456);
  for(int r = 0; r < 123; r++)
  for(int c = 0; c < 456; c++)
    a.setelem(r, c, r*(c-246));


  // invoke copy constructor:
 
  const SparseMatrix &ref = a;
  const SparseMatrix b = ref;

  // see if the resulting matrix has the correct size:
  ec.result(b.getrows() == 123 && b.getcols() == 456);


  ec.desc("copy constructor: target values");

  // see if the values were copied correctly:
  bool good = true;
  for(int r = 0; r < 123; r++)
  for(int c = 0; c < 123; c++)
    good &= b.getelem(r, c) == r*(c-246);
  
  ec.result(good);


  ec.desc("copy constructor: source dimensions and values");

  // verify that the original matrix was not changed by the copy:
  good = a.getrows() == 123 && a.getcols() == 456;
  for(int r = 0; r < 123; r++)
  for(int c = 0; c < 123; c++)
    good &= a.getelem(r, c) == r*(c-246);
  
  ec.result(good);


  // This next test should always pass, unless a previous test failed or
  // you foolishly ignored a compiler warning about "const" somewhere.
  ec.desc("copy constructor: depth of copy");

  // systematically eradicate the original values:
  for(int r = 0; r < 123; r++)
  for(int c = 0; c < 123; c++)
    a.setelem(r, c, 23);

  // verify that the original matrix is gone but the copy is still there:
  good = a.getrows() == 123 && a.getcols() == 456
      && b.getrows() == 123 && b.getcols() == 456;
  for(int r = 0; r < 123; r++)
  for(int c = 0; c < 123; c++)
    good &= b.getelem(r, c) == r*(c-246) && a.getelem(r, c) == 23;
  
  ec.result(good);


  // If the previous test fails, this next test may appear to succeed, even
  // if the assignment operator fails to work.
  ec.desc("assignment operator: matrices of equal size");

  // copy the values back using the assignment operator:
  a = b;

  // make sure everything is the way it should be:
  good = a.getrows() == 123 && a.getcols() == 456
      && b.getrows() == 123 && b.getcols() == 456;
  for(int r = 0; r < 123; r++)
  for(int c = 0; c < 123; c++)
    good &= a.getelem(r, c) == r*(c-246) && b.getelem(r, c) == r*(c-246);
  
  ec.result(good);


  ec.desc("assignment operator: matrices of differing size");

  // replace b with a zeroed 23x5 matrix:
  a = SparseMatrix(23, 5);

  // verify the new size and contents of a:
  good = a.getrows() == 23 && a.getcols() == 5;
  for(int r = 0; r < 23; r++)
  for(int c = 0; c <  5; c++)
    good &= a.getelem(r, c) == 0;

  ec.result(good);


  // NOTE: This test may fail to detect a common problem!  But we'll try:
  ec.desc("assignment operator: self-assignment");

  // start out by filling the new 23x5 matrix with some nice 1-heavy garbage:
  for(int r = 0; r < 23; r++)
  for(int c = 0; c <  5; c++)
    a.setelem(r, c, ~(r ^ (c<<16)));

  // assign a to itself in various exciting different ways:
  a = ((a = a = a) = (a = a = a) = (a = a = a)) = a;

  // see how ineffective that really was:
  good = a.getrows() == 23 && a.getcols() == 5;
  for(int r = 0; r < 23; r++)
  for(int c = 0; c <  5; c++)
    good &= a.getelem(r, c) == ~(r ^ (c<<16));

  ec.result(good);
}

void comp(ErrorContext &ec, int level)
{
  ec.desc("--- Comparison operators ---");


  for(int pass = 1; pass <= (level/3) * (level/3); pass++)
  {
    ec.desc("two empty matrices, equality");
    ec.result(SparseMatrix() == SparseMatrix(0, 0));

    ec.desc("two empty matrices, inequality");
    ec.result(!(SparseMatrix(0, 0) != SparseMatrix()));


    const int rows = level + rnd(level);
    const int cols = level + rnd(level * level);
    {
      ostrstream oss;
      oss << "identical " << rows << " by " << cols << " matrices, equality"
          << ends;
      ec.desc(oss.str());
    }

    // create two identical random matrices:
    SparseMatrix a(rows, cols), b(rows, cols);
    for(int r = 0; r < rows; r++)
    for(int c = 0; c < cols; c++)
    {
      int v = rnd();
      a.setelem(r, c, v);
      b.setelem(r, c, v);
    }

    ec.result(a == b && b == a);

    {
      ostrstream oss;
      oss << "identical " << rows << " by " << cols << " matrices, inequality"
          << ends;
      ec.desc(oss.str());
    }

    ec.result(!(a != b || b != a));


    int row = rnd(rows);
    int col = rnd(cols);
    {
      ostrstream oss;
      oss << "matrices differing only at (" << row << "," << col
          << "), equality" << ends;
      ec.desc(oss.str());
    }

    // add 1 to a random element in a:
    a.setelem(row, col, a.getelem(row, col) + 1);

    ec.result(!(a == b || b == a));


    {
      ostrstream oss;
      oss << "matrices differing only at (" << row << "," << col
          << "), inequality" << ends;
      ec.desc(oss.str());
    }

    ec.result(a != b && b != a);


    // ensure that if one dimension is zero, both will be
    if(row == 0 || col == 0)
      row = col = 0;

    {
      ostrstream oss;
      oss << rows << " by " << cols << " vs. " << row << " by " << col
          << ", equality" << ends;
      ec.desc(oss.str());
    }

    // make b into a "subset" of a:
    b = SparseMatrix(row, col);
    for(int r = 0; r < row; r++)
    for(int c = 0; c < col; c++)
      b.setelem(r, c, a.getelem(r, c));

    ec.result(!(a == b || b == a));


    {
      ostrstream oss;
      oss << rows << " by " << cols << " vs. " << row << " by " << col
          << ", inequality" << ends;
      ec.desc(oss.str());
    }

    ec.result(a != b && b != a);
  }
}

void math(ErrorContext &ec, int level)
{
  ec.desc("--- Arithmetic operators ---");

  // Note that these tests depend heavily on previously tested operations!
  // They should not be run unless everything else checks out OK.
  if(!ec.ok())
  {
    ec.desc("one or more previous failures; skipping this section");
    ec.result(false);
    return;
  }

  for(int pass = 1; pass <= level/2; pass++)
  {
    // make up some dimensions for these matrices:
    const int x = pass>1 ? rnd(level)+1 : 0;
    const int y = pass>1 ? rnd(level)+1 : 0;
    const int z = pass>1 ? rnd(level)+1 : 0;

    // these will be three random matrices:
    SparseMatrix a(x, y);
    SparseMatrix b(x, y);
    SparseMatrix c(y, z);

    // these will be the correct results of arithmetic operations:
    SparseMatrix a_plus_b(x, y);
    SparseMatrix a_minus_b(x, y);
    SparseMatrix a_times_c(x, z);

    // fill in the values and results:

    for(int ix = 0; ix < x; ix++)
    for(int iy = 0; iy < y; iy++)
    {
      const int va = rnd();
      const int vb = rnd();

      a.setelem(ix, iy, va);
      b.setelem(ix, iy, vb);

      a_plus_b.setelem(ix, iy, va + vb);
      a_minus_b.setelem(ix, iy, va - vb);
    }

    for(int iy = 0; iy < y; iy++)
    for(int iz = 0; iz < z; iz++)
    {
      const int vc = rnd();
      c.setelem(iy, iz, vc);

      for(int ix = 0; ix < x; ix++)
      {
        a_times_c.setelem(ix, iz, a_times_c.getelem(ix, iz) + vc *
          a.getelem(ix, iy));
      }
    }

    // set up read-only copies of the three reference matrices:
    const SparseMatrix copy_a = a;
    const SparseMatrix copy_b = b;
    const SparseMatrix copy_c = c;

    // check non-destructive addition:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") + (" << x << " by " << y << ")"
          << ", return value" << ends;
      ec.desc(oss.str());
      ec.result(copy_a + copy_b == a_plus_b);
    }

    // ensure arguments were not altered:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") + (" << x << " by " << y << ")"
          << ", side effects" << ends;
      ec.desc(oss.str());
      ec.result(copy_a == a && copy_b == b);
    }

    // check non-destructive subtraction:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") - (" << x << " by " << y << ")"
          << ", return value" << ends;
      ec.desc(oss.str());
      ec.result(copy_a - copy_b == a_minus_b);
    }

    // ensure arguments were not altered:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") - (" << x << " by " << y << ")"
          << ", side effects" << ends;
      ec.desc(oss.str());
      ec.result(copy_a == a && copy_b == b);
    }

    // check non-destructive multiplication:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") * (" << y << " by " << z << ")"
          << ", return value" << ends;
      ec.desc(oss.str());
      ec.result(copy_a * copy_c == a_times_c);
    }

    // ensure arguments were not altered:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") * (" << y << " by " << z << ")"
          << ", side effects" << ends;
      ec.desc(oss.str());
      ec.result(copy_a == a && copy_c == c);
    }

    // check destructive addition:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") += (" << x << " by " << y << ")"
          << ", return value" << ends;
      ec.desc(oss.str());
      ec.result((a_minus_b += copy_b) == copy_a);
    }

    // ensure LHS was altered and RHS was not:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") += (" << x << " by " << y << ")"
          << ", side effects" << ends;
      ec.desc(oss.str());
      ec.result(a_minus_b == copy_a && copy_b == b);
    }

    // check destructive subtraction:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") -= (" << x << " by " << y << ")"
          << ", return value" << ends;
      ec.desc(oss.str());
      ec.result((a_plus_b -= b) == copy_a);
    }

    // ensure LHS was altered and RHS was not:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") -= (" << x << " by " << y << ")"
          << ", side effects" << ends;
      ec.desc(oss.str());
      ec.result(a_plus_b == copy_a && copy_b == b);
    }

    // check destructive multiplication:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") *= (" << y << " by " << z << ")"
          << ", return value" << ends;
      ec.desc(oss.str());
      ec.result((a *= copy_c) == a_times_c);
    }

    // ensure LHS was altered and RHS was not:
    {
      ostrstream oss;
      oss << "(" << x << " by " << y << ") *= (" << y << " by " << z << ")"
          << ", side effects" << ends;
      ec.desc(oss.str());
      ec.result(a == a_times_c && copy_c == c);
    }
  }
}

///////////////////////////////////////////////////////////////////////////////

int main(int argc, const char *argv[])
{
  // use first argument, if any, as level:
  int level = argc > 1 ? atoi(argv[1]) : 0;
  if(level <= 0)
  {
    cout << "Test level may be specified as a positive integer argument."
         << endl
         << "Larger levels yield more tests; smaller levels yield fewer tests."
         << endl << endl;

    level = 5;
  }

  // set everything up:
  cout << "Performing a level " << level << " check of class SparseMatrix." << 
endl
       << endl;
  ErrorContext ec(cout);
  srand48(level);

  // perform the appropriate checks for this level:

  empty(ec);

  if(level >= 2)
    basic(ec, level);

  if(level >= 3)
    copy(ec);

  if(level >= 4)
    comp(ec, level);

  if(level >= 5)
    math(ec, level);

  // return 0 (success) if all the checks passed, 1 otherwise:
  return ec.ok() ? 0 : 1;
}