#include "sets.h"
#include <iostream>
#include <stdlib.h>
using namespace std;

unsigned rand (unsigned upperBound)
{
  unsigned long r = rand();
  return r % upperBound;
}

const int MaxSetElement = 100;

void generateSet (int numElements, Set& s, bool *expected)
{
  int elements[MaxSetElement];
  
  for (int i = 0; i < MaxSetElement; i++)
  {
    elements[i] = i;
    expected[i] = false;
  }
  
    // Now scramble the ordering of the elements array
  for (int i = 0; i < MaxSetElement; i++)
  {
    int j = rand(MaxSetElement);
    int t = elements[i];
    elements[i] = elements[j];
    elements[j] = t;
  }

    // Insert the first numElements values into s
  s.clear();
  for (int i = 0; i < numElements; i++)
  {
    s.add(elements[i]);
    expected[elements[i]] = true;
  }
}

int checkSetContents (const Set& s, const bool* expectedMembers)
{
  int expectedSize = 0;
  int discoveredSize = 0;
  int result = 1;

  for (int i = 0; i < MaxSetElement; i++)
  {
    if (expectedMembers[i])
    {
      expectedSize++;
      if (s.member(i))
	      discoveredSize++;
      else
	    {
	      cout << "Set is missing expected element: " << i << endl;
	      result = 0;
	    }
    }
    else
    {
      if (s.member(i))
	    {
	      discoveredSize++;
	      cout << "Set contains unexpected element: " << i << endl;
	      result = 0;
	    }
    }
  }
  if (expectedSize != discoveredSize)
  {
    cout << "Number of elements in set: " << discoveredSize
         <<  " does not match expected number: "
         << expectedSize << endl;
    result = 0;
  }
  if (s.extent() != discoveredSize)
  {
    cout << "Number of elements in set: " << discoveredSize
         <<  " does not match reported number (extent): "
         << s.extent() << endl;
    result = 0;
  }
  return result;
}


int testSet (const Set& s, const bool *expected)
{
  Set s1 = s;

    // Check set for internal consistency
  if (!checkSetContents(s, expected))
    return 0;
  if (!checkSetContents(s1, expected))
    return 0;  
  
    // Axiom 1: After s.clear(), s.extent()==0
  bool noneExpected[MaxSetElement] = {false};
  s1.clear();
  if (!checkSetContents(s1, noneExpected))
    return 0;

    // Axiom 2: adding a member X ...
  s1 = s;
  int x = rand(MaxSetElement);
  if (s1.member(x))
  {  // ...that is already in s results in no change to s
    s1.add(x);
    if ((!checkSetContents(s1, expected))
        || (s.extent() != s1.extent()))
      return 0;
  }
  else
  {  // ...that is not in s results in a new member and larger extent
    s1.add(x);
    bool moreExpected[MaxSetElement];
    for (int ii = 0; ii < MaxSetElement; ii++)
      moreExpected[ii] = expected[ii];
      
    moreExpected[x] = true;
    if ((!checkSetContents(s1, moreExpected))
        || (s.extent() != s1.extent()-1))
      return 0;
  }
  return 1; 
}


int main ()
{
  bool expected[MaxSetElement];
  srand(1);

  int ok = 1;
  cout << "\n\nTesting  sets" << endl;
  for (int testSize = 0; ok && (testSize < MaxSetElement);
       testSize = 2*testSize + 1)
  {
    Set s;
    cout << "Size: " << testSize << endl;
    generateSet (testSize, s, expected);
    ok = testSet (s, expected);
    if (!ok) cout <<" A test has failed !" << endl;
  }

#ifdef TREE
  if (BinTreeNode::counter > 0)
    cout << BinTreeNode::counter
         << " tree nodes constructed but not destroyed." << endl;
  else
    cout << "All tree nodes that were constructed have \
    been successfully destroyed." << endl;
    
#endif

  if (ok)
    cout << "All tests were passed successfully !" << endl;
  else
    cout << "One of the tests has failed !" << endl;

  return 1;
}