#include "sets2.h"
#include <iostream.h>
#include <stdlib.h>

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

const int MaxSetElement = 100;

int checkSetContents (const Set& s, const int* 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;
}



void generateSet (int numElements, Set& s, int *expected)
{
  int elements[MaxSetElement];
  

  for (int i = 0; i < MaxSetElement; i++)
    {
      elements[i] = i;
      expected[i] = 0;
    }
  

  // 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]] = 1;
    }
}
  
  
int testSet1 (const Set& s, const int *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
  int noneExpected[MaxSetElement] = {0};
  s1.clear();
  if (!checkSetContents(s1, noneExpected)) {
    s1.clear();
    delete &s1;
    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())) {
	s1.clear();
	delete &s1;
        return 0;
      }
    }
  else
    {
      // ...that is not in s results in a new member and larger extent
      s1.add(x);
      int moreExpected[MaxSetElement];
      for (int ii = 0; ii < MaxSetElement; ii++)
	moreExpected[ii] = expected[ii];
      
      moreExpected[x] = 1;
      if ((!checkSetContents(s1, moreExpected))
	  || (s.extent() != s1.extent()-1)) {
	s1.clear();
	delete &s1;
        return 0;
      }
    }
  s1.clear();
  delete &s1;
  return 1;
  
}

//================================//

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

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

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




  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;
    


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