[unix-history] / usr / src / lib / libg++ / tests / tBag.cc

/*
 a test file for Bags
*/


#ifdef PTIMES
const int ptimes = 1;
#else
const int ptimes = 0;
#endif

#include <stream.h>
#include <assert.h>

#define tassert(ex) { cerr << #ex; \
                       if ((ex)) cerr << " OK\n"; \
                       else cerr << " Fail\n"; }

#include "iBag.h"

unsigned int hash(int x) { return multiplicativehash(x) ; }

int SIZE;

int *nums;
int *odds;
int *dups;

void add(int x[], intBag& a)
{
  for (int i = 0; i < SIZE; ++i) a.add(x[i]);
}


#include <MLCG.h>

MLCG randgen;

void permute(int x[])
{
  for (int i = 1; i < SIZE; ++i)
  {
    int j = randgen.asLong() % (i + 1);
    int tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  }
}

void makenums()
{
  for (int i = 0; i < SIZE; ++i) nums[i] = i + 1;
}

void makeodds()
{
  for (int i = 0; i < SIZE; ++i) odds[i] = 2 * i + 1;
  permute(odds);
}

void makedups()
{
  for (int i = 0; i < SIZE; i += 2) dups[i] = dups[i+1] = i/2 + 1;
  permute(dups);
}

void printBag(intBag& a)
{
  int maxprint = 20;
  cout << "[";
  int k = 0;
  for (Pix i = a.first(); i != 0 && k < maxprint; a.next(i),++k) 
    cout << a(i) << " ";
  if (i != 0) cout << "...]\n";
  else cout << "]\n";
}


void generictest(intBag& a, intBag& b, intBag& c)
{
  c.clear();
  assert(c.empty());
  for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  c.del(a(a.first()));
  Pix i = a.first();
  assert(!c.contains(a(i)));
  for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  c.add(a(a.first()));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  assert(c.empty());
  assert(a.OK());
  assert(b.OK());
  assert(c.OK());
}

#include "iXPBag.h"

void XPtest()
{
  intXPBag a(SIZE);
  add(nums, a);
  assert(a.length() == SIZE);
  for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  intXPBag b(SIZE);
  add(odds, b);
  assert(b.length() == SIZE);
  intXPBag c(SIZE);
  add(dups, c); 
  assert(c.length() == SIZE);
  intXPBag d(a);
  add(nums, d);
  assert(d.length() == SIZE*2);
  cout << "a: "; printBag(a);
  cout << "b: "; printBag(b);
  cout << "c: "; printBag(c);
  cout << "d: "; printBag(d);
  for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  d.del(1);
  assert(d.nof(1) == 1);
  d.del(1);
  assert(d.nof(1) == 0);
  d.remove(2);
  assert(!d.contains(2));
  for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  assert(d.length() == SIZE);
  
  c.clear();
  assert(c.empty());
  for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  c.del(a(a.first()));
  Pix i = a.first();
  assert(!c.contains(a(i)));
  for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  c.add(a(a.first()));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  assert(c.empty());
  assert(a.OK());
  assert(b.OK());
  assert(c.OK());

  generictest(a, b, c);
}


#include "iSLBag.h"

void SLtest()
{
  intSLBag a;
  add(nums, a);
  assert(a.length() == SIZE);
  for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  intSLBag b;
  add(odds, b);
  assert(b.length() == SIZE);
  intSLBag c;
  add(dups, c); 
  assert(c.length() == SIZE);
  intSLBag d(a);
  add(nums, d);
  assert(d.length() == SIZE*2);
  cout << "a: "; printBag(a);
  cout << "b: "; printBag(b);
  cout << "c: "; printBag(c);
  cout << "d: "; printBag(d);
  for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  d.del(1);
  assert(d.nof(1) == 1);
  d.del(1);
  assert(d.nof(1) == 0);
  d.remove(2);
  assert(!d.contains(2));
  for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  assert(d.length() == SIZE);
  
  c.clear();
  assert(c.empty());
  for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  c.del(a(a.first()));
  Pix i = a.first();
  assert(!c.contains(a(i)));
  for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  c.add(a(a.first()));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  assert(c.empty());
  assert(a.OK());
  assert(b.OK());
  assert(c.OK());

  generictest(a, b, c);
}


#include "iVHBag.h"

void VHtest()
{
  intVHBag a(SIZE);
  add(nums, a);
  assert(a.length() == SIZE);
  for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  intVHBag b(SIZE);
  add(odds, b);
  assert(b.length() == SIZE);
  intVHBag c(SIZE);
  add(dups, c); 
  assert(c.length() == SIZE);
  intVHBag d(a);
  add(nums, d);
  assert(d.length() == SIZE*2);
  cout << "a: "; printBag(a);
  cout << "b: "; printBag(b);
  cout << "c: "; printBag(c);
  cout << "d: "; printBag(d);
  for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  d.del(1);
  assert(d.nof(1) == 1);
  d.del(1);
  assert(d.nof(1) == 0);
  d.remove(2);
  assert(!d.contains(2));
  for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  assert(d.length() == SIZE);
  
  c.clear();
  assert(c.empty());
  for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  c.del(a(a.first()));
  Pix i = a.first();
  assert(!c.contains(a(i)));
  for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  c.add(a(a.first()));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  assert(c.empty());
  assert(a.OK());
  assert(b.OK());
  assert(c.OK());

  generictest(a, b, c);
}

#include "iCHBag.h"

void CHtest()
{
  intCHBag a(SIZE);
  add(nums, a);
  assert(a.length() == SIZE);
  for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  intCHBag b(SIZE);
  add(odds, b);
  assert(b.length() == SIZE);
  intCHBag c(SIZE);
  add(dups, c); 
  assert(c.length() == SIZE);
  intCHBag d(a);
  add(nums, d);
  assert(d.length() == SIZE*2);
  cout << "a: "; printBag(a);
  cout << "b: "; printBag(b);
  cout << "c: "; printBag(c);
  cout << "d: "; printBag(d);
  for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  d.del(1);
  assert(d.nof(1) == 1);
  d.del(1);
  assert(d.nof(1) == 0);
  d.remove(2);
  assert(!d.contains(2));
  for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  assert(d.length() == SIZE);
  
  c.clear();
  assert(c.empty());
  for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  c.del(a(a.first()));
  Pix i = a.first();
  assert(!c.contains(a(i)));
  for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  c.add(a(a.first()));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  assert(c.empty());
  assert(a.OK());
  assert(b.OK());
  assert(c.OK());

  generictest(a, b, c);
}

#include "iOXPBag.h"

void OXPtest()
{
  intOXPBag a(SIZE);
  add(nums, a);
  assert(a.length() == SIZE);
  for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  intOXPBag b(SIZE);
  add(odds, b);
  assert(b.length() == SIZE);
  intOXPBag c(SIZE);
  add(dups, c); 
  assert(c.length() == SIZE);
  intOXPBag d(a);
  add(nums, d);
  assert(d.length() == SIZE*2);
  cout << "a: "; printBag(a);
  cout << "b: "; printBag(b);
  cout << "c: "; printBag(c);
  cout << "d: "; printBag(d);
  for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  d.del(1);
  assert(d.nof(1) == 1);
  d.del(1);
  assert(d.nof(1) == 0);
  d.remove(2);
  assert(!d.contains(2));
  for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  assert(d.length() == SIZE);
  
  c.clear();
  assert(c.empty());
  for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  c.del(a(a.first()));
  Pix i = a.first();
  assert(!c.contains(a(i)));
  for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  c.add(a(a.first()));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  assert(c.empty());
  assert(a.OK());
  assert(b.OK());
  assert(c.OK());

  generictest(a, b, c);
}


#include "iOSLBag.h"

void OSLtest()
{
  intOSLBag a;
  add(nums, a);
  assert(a.length() == SIZE);
  for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  intOSLBag b;
  add(odds, b);
  assert(b.length() == SIZE);
  intOSLBag c;
  add(dups, c); 
  assert(c.length() == SIZE);
  intOSLBag d(a);
  add(nums, d);
  assert(d.length() == SIZE*2);
  cout << "a: "; printBag(a);
  cout << "b: "; printBag(b);
  cout << "c: "; printBag(c);
  cout << "d: "; printBag(d);
  for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  d.del(1);
  assert(d.nof(1) == 1);
  d.del(1);
  assert(d.nof(1) == 0);
  d.remove(2);
  assert(!d.contains(2));
  for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  assert(d.length() == SIZE);
  
  c.clear();
  assert(c.empty());
  for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  c.del(a(a.first()));
  Pix i = a.first();
  assert(!c.contains(a(i)));
  for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  c.add(a(a.first()));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  assert(c.empty());
  assert(a.OK());
  assert(b.OK());
  assert(c.OK());

  generictest(a, b, c);
}

#include "iSplayBag.h"

void Splaytest()
{
  intSplayBag a;
  add(nums, a);
  assert(a.length() == SIZE);
  for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  intSplayBag b;
  add(odds, b);
  assert(b.length() == SIZE);
  intSplayBag c;
  add(dups, c); 
  assert(c.length() == SIZE);
  intSplayBag d(a);
  add(nums, d);
  assert(d.length() == SIZE*2);
  cout << "a: "; printBag(a);
  cout << "b: "; printBag(b);
  cout << "c: "; printBag(c);
  cout << "d: "; printBag(d);
  for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  d.del(1);
  assert(d.nof(1) == 1);
  d.del(1);
  assert(d.nof(1) == 0);
  d.remove(2);
  assert(!d.contains(2));
  for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  assert(d.length() == SIZE);
  
  c.clear();
  assert(c.empty());
  for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  c.del(a(a.first()));
  Pix i = a.first();
  assert(!c.contains(a(i)));
  for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  c.add(a(a.first()));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  assert(c.empty());
  assert(a.OK());
  assert(b.OK());
  assert(c.OK());

  generictest(a, b, c);
}


double return_elapsed_time ( double );
double start_timer ( void );

main(int argv, char** argc)
{
  if (argv > 1)
  {
    SIZE = abs(atoi(argc[1]));
    SIZE &= ~1;
  }
  else
    SIZE = 100;
  nums = new int[SIZE];
  odds = new int[SIZE];
  dups = new int[SIZE];
  makenums();
  makeodds();
  makedups();
  start_timer();
  cout << "VHtest\n"; VHtest();
  if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  start_timer();
  cout << "CHtest\n"; CHtest();
  if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  start_timer();
  cout << "SLtest\n"; SLtest();
  if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  start_timer();
  cout << "XPtest\n"; XPtest();
  if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  start_timer();
  cout << "Splaytest\n"; Splaytest();
  if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  start_timer();
  cout << "OSLtest\n"; OSLtest();
  if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  start_timer();
  cout << "OXPtest\n"; OXPtest();
  if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
}
Commit	Line	Data
a3408dfb C	1	/*
	2	a test file for Bags
	3	*/
	4
	5
	6	#ifdef PTIMES
	7	const int ptimes = 1;
	8	#else
	9	const int ptimes = 0;
	10	#endif
	11
	12	#include <stream.h>
	13	#include <assert.h>
	14
	15	#define tassert(ex) { cerr << #ex; \
	16	if ((ex)) cerr << " OK\n"; \
	17	else cerr << " Fail\n"; }
	18
	19	#include "iBag.h"
	20
	21	unsigned int hash(int x) { return multiplicativehash(x) ; }
	22
	23	int SIZE;
	24
	25	int *nums;
	26	int *odds;
	27	int *dups;
	28
	29	void add(int x[], intBag& a)
	30	{
	31	for (int i = 0; i < SIZE; ++i) a.add(x[i]);
	32	}
	33
	34
	35	#include <MLCG.h>
	36
	37	MLCG randgen;
	38
	39	void permute(int x[])
	40	{
	41	for (int i = 1; i < SIZE; ++i)
	42	{
	43	int j = randgen.asLong() % (i + 1);
	44	int tmp = x[i]; x[i] = x[j]; x[j] = tmp;
	45	}
	46	}
	47
	48	void makenums()
	49	{
	50	for (int i = 0; i < SIZE; ++i) nums[i] = i + 1;
	51	}
	52
	53	void makeodds()
	54	{
	55	for (int i = 0; i < SIZE; ++i) odds[i] = 2 * i + 1;
	56	permute(odds);
	57	}
	58
	59	void makedups()
	60	{
	61	for (int i = 0; i < SIZE; i += 2) dups[i] = dups[i+1] = i/2 + 1;
	62	permute(dups);
	63	}
	64
65	void printBag(intBag& a)
66	{
67	int maxprint = 20;
68	cout << "[";
69	int k = 0;
70	for (Pix i = a.first(); i != 0 && k < maxprint; a.next(i),++k)
71	cout << a(i) << " ";
72	if (i != 0) cout << "...]\n";
73	else cout << "]\n";
74	}
75
76
77	void generictest(intBag& a, intBag& b, intBag& c)
78	{
79	c.clear();
80	assert(c.empty());
81	for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
82	for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
83	c.del(a(a.first()));
84	Pix i = a.first();
85	assert(!c.contains(a(i)));
86	for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
87	c.add(a(a.first()));
88	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
89	for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
90	for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
91	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
92	for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
93	for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
94	for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
95	assert(c.empty());
96	assert(a.OK());
97	assert(b.OK());
98	assert(c.OK());
99	}
100
101	#include "iXPBag.h"
102
103	void XPtest()
104	{
105	intXPBag a(SIZE);
106	add(nums, a);
107	assert(a.length() == SIZE);
108	for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
109	intXPBag b(SIZE);
110	add(odds, b);
111	assert(b.length() == SIZE);
112	intXPBag c(SIZE);
113	add(dups, c);
114	assert(c.length() == SIZE);
115	intXPBag d(a);
116	add(nums, d);
117	assert(d.length() == SIZE*2);
118	cout << "a: "; printBag(a);
119	cout << "b: "; printBag(b);
120	cout << "c: "; printBag(c);
121	cout << "d: "; printBag(d);
122	for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
123	d.del(1);
124	assert(d.nof(1) == 1);
125	d.del(1);
126	assert(d.nof(1) == 0);
127	d.remove(2);
128	assert(!d.contains(2));
129	for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
130	assert(d.length() == SIZE);
131
132	c.clear();
133	assert(c.empty());
134	for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
135	for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
136	c.del(a(a.first()));
137	Pix i = a.first();
138	assert(!c.contains(a(i)));
139	for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
140	c.add(a(a.first()));
141	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
142	for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
143	for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
144	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
145	for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
146	for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
147	for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
148	assert(c.empty());
149	assert(a.OK());
150	assert(b.OK());
151	assert(c.OK());
152
153	generictest(a, b, c);
154	}
155
156
157	#include "iSLBag.h"
158
159	void SLtest()
160	{
161	intSLBag a;
162	add(nums, a);
163	assert(a.length() == SIZE);
164	for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
165	intSLBag b;
166	add(odds, b);
167	assert(b.length() == SIZE);
168	intSLBag c;
169	add(dups, c);
170	assert(c.length() == SIZE);
171	intSLBag d(a);
172	add(nums, d);
173	assert(d.length() == SIZE*2);
174	cout << "a: "; printBag(a);
175	cout << "b: "; printBag(b);
176	cout << "c: "; printBag(c);
177	cout << "d: "; printBag(d);
178	for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
179	d.del(1);
180	assert(d.nof(1) == 1);
181	d.del(1);
182	assert(d.nof(1) == 0);
183	d.remove(2);
184	assert(!d.contains(2));
185	for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
186	assert(d.length() == SIZE);
187
188	c.clear();
189	assert(c.empty());
190	for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
191	for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
192	c.del(a(a.first()));
193	Pix i = a.first();
194	assert(!c.contains(a(i)));
195	for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
196	c.add(a(a.first()));
197	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
198	for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
199	for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
200	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
201	for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
202	for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
203	for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
204	assert(c.empty());
205	assert(a.OK());
206	assert(b.OK());
207	assert(c.OK());
208
209	generictest(a, b, c);
210	}
211
212
213	#include "iVHBag.h"
214
215	void VHtest()
216	{
217	intVHBag a(SIZE);
218	add(nums, a);
219	assert(a.length() == SIZE);
220	for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
221	intVHBag b(SIZE);
222	add(odds, b);
223	assert(b.length() == SIZE);
224	intVHBag c(SIZE);
225	add(dups, c);
226	assert(c.length() == SIZE);
227	intVHBag d(a);
228	add(nums, d);
229	assert(d.length() == SIZE*2);
230	cout << "a: "; printBag(a);
231	cout << "b: "; printBag(b);
232	cout << "c: "; printBag(c);
233	cout << "d: "; printBag(d);
234	for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
235	d.del(1);
236	assert(d.nof(1) == 1);
237	d.del(1);
238	assert(d.nof(1) == 0);
239	d.remove(2);
240	assert(!d.contains(2));
241	for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
242	assert(d.length() == SIZE);
243
244	c.clear();
245	assert(c.empty());
246	for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
247	for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
248	c.del(a(a.first()));
249	Pix i = a.first();
250	assert(!c.contains(a(i)));
251	for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
252	c.add(a(a.first()));
253	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
254	for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
255	for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
256	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
257	for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
258	for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
259	for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
260	assert(c.empty());
261	assert(a.OK());
262	assert(b.OK());
263	assert(c.OK());
264
265	generictest(a, b, c);
266	}
267
268	#include "iCHBag.h"
269
270	void CHtest()
271	{
272	intCHBag a(SIZE);
273	add(nums, a);
274	assert(a.length() == SIZE);
275	for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
276	intCHBag b(SIZE);
277	add(odds, b);
278	assert(b.length() == SIZE);
279	intCHBag c(SIZE);
280	add(dups, c);
281	assert(c.length() == SIZE);
282	intCHBag d(a);
283	add(nums, d);
284	assert(d.length() == SIZE*2);
285	cout << "a: "; printBag(a);
286	cout << "b: "; printBag(b);
287	cout << "c: "; printBag(c);
288	cout << "d: "; printBag(d);
289	for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
290	d.del(1);
291	assert(d.nof(1) == 1);
292	d.del(1);
293	assert(d.nof(1) == 0);
294	d.remove(2);
295	assert(!d.contains(2));
296	for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
297	assert(d.length() == SIZE);
298
299	c.clear();
300	assert(c.empty());
301	for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
302	for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
303	c.del(a(a.first()));
304	Pix i = a.first();
305	assert(!c.contains(a(i)));
306	for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
307	c.add(a(a.first()));
308	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
309	for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
310	for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
311	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
312	for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
313	for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
314	for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
315	assert(c.empty());
316	assert(a.OK());
317	assert(b.OK());
318	assert(c.OK());
319
320	generictest(a, b, c);
321	}
322
323	#include "iOXPBag.h"
324
325	void OXPtest()
326	{
327	intOXPBag a(SIZE);
328	add(nums, a);
329	assert(a.length() == SIZE);
330	for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
331	intOXPBag b(SIZE);
332	add(odds, b);
333	assert(b.length() == SIZE);
334	intOXPBag c(SIZE);
335	add(dups, c);
336	assert(c.length() == SIZE);
337	intOXPBag d(a);
338	add(nums, d);
339	assert(d.length() == SIZE*2);
340	cout << "a: "; printBag(a);
341	cout << "b: "; printBag(b);
342	cout << "c: "; printBag(c);
343	cout << "d: "; printBag(d);
344	for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
345	d.del(1);
346	assert(d.nof(1) == 1);
347	d.del(1);
348	assert(d.nof(1) == 0);
349	d.remove(2);
350	assert(!d.contains(2));
351	for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
352	assert(d.length() == SIZE);
353
354	c.clear();
355	assert(c.empty());
356	for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
357	for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
358	c.del(a(a.first()));
359	Pix i = a.first();
360	assert(!c.contains(a(i)));
361	for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
362	c.add(a(a.first()));
363	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
364	for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
365	for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
366	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
367	for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
368	for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
369	for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
370	assert(c.empty());
371	assert(a.OK());
372	assert(b.OK());
373	assert(c.OK());
374
375	generictest(a, b, c);
376	}
377
378
379	#include "iOSLBag.h"
380
381	void OSLtest()
382	{
383	intOSLBag a;
384	add(nums, a);
385	assert(a.length() == SIZE);
386	for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
387	intOSLBag b;
388	add(odds, b);
389	assert(b.length() == SIZE);
390	intOSLBag c;
391	add(dups, c);
392	assert(c.length() == SIZE);
393	intOSLBag d(a);
394	add(nums, d);
395	assert(d.length() == SIZE*2);
396	cout << "a: "; printBag(a);
397	cout << "b: "; printBag(b);
398	cout << "c: "; printBag(c);
399	cout << "d: "; printBag(d);
400	for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
401	d.del(1);
402	assert(d.nof(1) == 1);
403	d.del(1);
404	assert(d.nof(1) == 0);
405	d.remove(2);
406	assert(!d.contains(2));
407	for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
408	assert(d.length() == SIZE);
409
410	c.clear();
411	assert(c.empty());
412	for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
413	for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
414	c.del(a(a.first()));
415	Pix i = a.first();
416	assert(!c.contains(a(i)));
417	for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
418	c.add(a(a.first()));
419	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
420	for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
421	for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
422	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
423	for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
424	for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
425	for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
426	assert(c.empty());
427	assert(a.OK());
428	assert(b.OK());
429	assert(c.OK());
430
431	generictest(a, b, c);
432	}
433
434	#include "iSplayBag.h"
435
436	void Splaytest()
437	{
438	intSplayBag a;
439	add(nums, a);
440	assert(a.length() == SIZE);
441	for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
442	intSplayBag b;
443	add(odds, b);
444	assert(b.length() == SIZE);
445	intSplayBag c;
446	add(dups, c);
447	assert(c.length() == SIZE);
448	intSplayBag d(a);
449	add(nums, d);
450	assert(d.length() == SIZE*2);
451	cout << "a: "; printBag(a);
452	cout << "b: "; printBag(b);
453	cout << "c: "; printBag(c);
454	cout << "d: "; printBag(d);
455	for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
456	d.del(1);
457	assert(d.nof(1) == 1);
458	d.del(1);
459	assert(d.nof(1) == 0);
460	d.remove(2);
461	assert(!d.contains(2));
462	for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
463	assert(d.length() == SIZE);
464
465	c.clear();
466	assert(c.empty());
467	for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
468	for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
469	c.del(a(a.first()));
470	Pix i = a.first();
471	assert(!c.contains(a(i)));
472	for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
473	c.add(a(a.first()));
474	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
475	for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
476	for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
477	for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
478	for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
479	for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
480	for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
481	assert(c.empty());
482	assert(a.OK());
483	assert(b.OK());
484	assert(c.OK());
485
486	generictest(a, b, c);
487	}
488
489
490	double return_elapsed_time ( double );
491	double start_timer ( void );
492
493	main(int argv, char** argc)
494	{
495	if (argv > 1)
496	{
497	SIZE = abs(atoi(argc[1]));
498	SIZE &= ~1;
499	}
500	else
501	SIZE = 100;
502	nums = new int[SIZE];
503	odds = new int[SIZE];
504	dups = new int[SIZE];
505	makenums();
506	makeodds();
507	makedups();
508	start_timer();
509	cout << "VHtest\n"; VHtest();
510	if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
511	start_timer();
512	cout << "CHtest\n"; CHtest();
513	if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
514	start_timer();
515	cout << "SLtest\n"; SLtest();
516	if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
517	start_timer();
518	cout << "XPtest\n"; XPtest();
519	if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
520	start_timer();
521	cout << "Splaytest\n"; Splaytest();
522	if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
523	start_timer();
524	cout << "OSLtest\n"; OSLtest();
525	if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
526	start_timer();
527	cout << "OXPtest\n"; OXPtest();
528	if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
529	}