Template Set (power set)
A. Second Edition
This is an improved version of original template set.
1. I removed the redundant template parameter which acts as the user-defined comparison, displaying
methods. Why do I need it? I mean only for the very, very base class I need the comparison class.
For all "super set class", they all have my overloaded member function: the overloaded operator ==.
2. However, this is true only if the primitive type of element has a correct comparison function of
"==", like integer, float etc. For the very common "char*", it is obviously not true. So, I need to
"specialize the template class"!!! This cost me a whole evening to figure out!
This kind of question will simply drive me crazy!!!
For a set class with element of type of "T", if the element has already had a correct version of
"operator ==" function to act as comparison function, then, the overloading of "operator =="
function of set class itself will also correctly act as a "set class comparison function". See:
template<T>
class MySet
{
private:
T members[MaxMemberSize];
...
public:
bool operator==(const MySet<T>& other) const;
...
};
Suppose we want to use integer set class---MySet<int>. The member of MySet<int> is of type of
integer. So, the implementation of member function of MySet<int> will be correct for COMPARISON
FUNCTION OF MySet<int>. Therefore, the "power set" class of MySet<int> has also has a correct
comparison function for its member which is of type of "MySet<int>".
What a PERFECT SOLUTION!!!
However, if the base type has a member of type which has incorrect "==" function for comparison
purpose, like "char*", you need to specialize the template class for that particular type!!!
There is one particular detail which cost me more than one hour debugging! It is the type of
"char*" itself which is recognized incorrectly by compiler. You have to "typedef char* charPtr;".
Please be noted that for VC++6.0, there are many, many, many bugs for template!!!!!!!!!!!!!!!
So, if you find something unexpected, try to search in MSDN. Otherwise you might waste your time.
Another little problem is that the compiler try to be clever by assigning all same string with
same addresses. For example,
char* strArray1[DataLength]=
{
"one", "two", "three", "four", "five"
};
char* strArray2[DataLength]=
{
"one", "two", "three", "four", "five"
};
What I found is that strArray1[2] is exactly same address of strArray2[2]. Later I have to use
string copy to make the addresses of each pointer are different.
E.Further improvement
I will try to specialize the template class to remove the "comparison class".
F.File listing
1. set.h
2. set.cpp
3. methods.h
4. myset.h
5. main.cpp
file name: set.h
#ifndef SET_H
#define SET_H
#include <iostream>
#include <bitset>
using namespace std;
const int MaxAttrNumber=50;
class Set
{
//this is a long-pain for me, I have no other way to
//let compiler recognize this "friend" function outside declaration
friend ostream& operator<<(ostream& out, const Set& dummy)
{
for (int i=0; i<dummy.size; i++)
{
if (dummy.theSet.test(i))
{
out<<'1';
}
else
{
out<<'0';
}
}
return out;
}
private:
bitset<MaxAttrNumber> theSet;
int size;
int current;
public:
void setSize(const Set& dummy);
int getSize(){ return size;}
int next(int current) const;
int first() const;
int count() const;
Set intersection(const Set& dummy) const;
Set unionSet(const Set& dummy) const;
Set difference(const Set& dummy) const;
//I am crazy about operator overloading!!!:)
Set operator-(const Set& dummy) const;
Set operator+(const Set& dummy) const;
Set operator*(const Set& dummy) const;
void operator=(const Set& dummy);
bool operator==(const Set& dummy) const;
bool operator!=(const Set& dummy) const;
bool operator>(const Set& dummy) const;
bool operator>=(const Set& dummy) const;
bool operator<(const Set& dummy) const;
bool operator<=(const Set& dummy) const;
void set(int pos);
void forEachSubSet(Set& dummy) const;//must be called before "eachSub()"
bool eachSub(Set& dummy) const;
bool eachSub(Set& dummy, const Set& excluding) const;
void set();
void reset(int pos);
void reset();
bool test(int pos) const;
bool isIn(const Set& dummy) const;
void setSize(int theSize) {size=theSize;}
Set(int theSize=10);
};
#endif
file name: set.cpp
#include "Set.h"
bool Set::isIn(const Set& dummy) const
{
for (int i=0; i<size; i++)
{
if (theSet.test(i))
{
if (!dummy.test(i))//here I use Set.test() instead of set.test()
{
return false;
}
}
}
return true;
}
bool Set::test(int pos) const
{
return (pos<size&&theSet.test(pos));
}
//current=-1;//initialize to -1 to prepare for being called
int Set::next(int current) const
{
for (int i=current+1; i<size; i++)//include situation current>=size
{
if (theSet.test(i))
{
return i;
}
}
return -1;//not found
}
bool Set::operator !=(const Set& dummy)const
{
return !(this->operator ==(dummy));
}
bool Set::operator <(const Set& dummy)const
{
return (this->isIn(dummy)&&this->operator !=(dummy));
}
bool Set::operator <=(const Set& dummy)const
{
return isIn(dummy);
}
bool Set::operator >(const Set& dummy)const
{
return !(this->operator <=(dummy));
}
bool Set::operator >=(const Set& dummy)const
{
return !(this->operator <(dummy));
}
bool Set::operator ==(const Set& dummy)const
{
for (int i=0; i<(size>dummy.size?size:dummy.size); i++)
{
if (test(i)^dummy.test(i))
{
return false;
}
}
return true;
}
void Set::setSize(const Set& dummy)
{
size=dummy.size;
}
void Set::operator =(const Set& dummy)
{
size=dummy.size;
for (int i=0; i<size; i++)
{
if (dummy.test(i))
{
theSet.set(i);
}
else
{
theSet.reset(i);
}
}
}
Set::Set(int theSize)
{
size=theSize;
reset();
}
void Set::reset()
{
for (int i=0; i<size; i++)
{
theSet.reset(i);
}
}
void Set::reset(int pos)
{
if (pos<size)
{
theSet.reset(pos);
}
}
void Set::set()
{
theSet.set();
}
void Set::set(int pos)
{
theSet.set(pos);
}
void Set::forEachSubSet(Set& dummy) const
{
dummy.size=size;
dummy.reset();//emptyset
}
bool Set::eachSub(Set& dummy, const Set& excluding) const
{
int index=first();//starting from very first
while (index!=-1)//not exceeding boundery
{
if (!excluding.test(index))//exluding this set
{
if (dummy.test(index))
{
dummy.reset(index);
}
else
{
dummy.set(index);
//return true;
if (dummy<*this)//only return the proper subset
{
return true;
}
}
}
index=next(index);
}
return false;
}
bool Set::eachSub(Set& dummy) const
{
int index=first();//starting from very first
while (index!=-1)//not exceeding boundery
{
if (dummy.test(index))
{
dummy.reset(index);
index=next(index);
}
else
{
dummy.set(index);
//return true;
if (dummy<*this)
{
return true;
}
}
}
return false;
}
int Set::first()const
{
return next(-1);
}
int Set::count()const
{
return theSet.count();
}
Set Set::unionSet(const Set& dummy) const
{
Set result;
result.size=size>dummy.size?size:dummy.size;
for (int i=0; i<result.size; i++)
{
if (test(i)||dummy.test(i))
{
result.set(i);
}
}
return result;//this is a temparory object;
}
Set Set::difference(const Set& dummy) const
{
Set result;
result.size=size>dummy.size?size:dummy.size;
for (int i=0; i<result.size; i++)
{
if (test(i)&&!dummy.test(i))
{
result.set(i);
}
}
return result;
}
Set Set::operator +(const Set& dummy) const
{
return unionSet(dummy);
}
Set Set::operator -(const Set& dummy) const
{
return difference(dummy);
}
Set Set::intersection(const Set& dummy) const
{
Set result;
result.size=size<dummy.size?size:dummy.size;
for (int i=0; i<result.size; i++)
{
if (test(i)&&dummy.test(i))
{
result.set(i);
}
}
return result;
}
Set Set::operator *(const Set& dummy) const
{
return intersection(dummy);
}
file name: myset.h
#ifndef MYSET_H
#define MYSET_H
#include <stdio.h>
#include "set.h"
typedef char* charPtr;
const int MaxSetMember=50;
const int MaxNameLength=30;
const int UniverseIndex=0;
const int EmptyIndex=1;
template<class T>
class MySet
{
friend ostream& operator<<(ostream& out, MySet<T>& dummy)
{
out<<dummy.name<<":{";
for (int i=0; i<dummy.size; i++)
{
out<<dummy.members[i];
if (i!=dummy.size-1)
{
out<<",";
}
}
out<<"}\n";
return out;
}
//friend ostream& operator<<(ostream& out, MySet<charPtr>& dummy
private:
static int setIndex;
static MySet<T>* UNIVERSE;
static MySet<T>* EMPTY;
int index;
T members[MaxSetMember];
int size;
Set marker;
Set receiver;
//MySet<MySet<T,methods>, methods> power;
char name[MaxNameLength];
void initialize();
void uninitialize();
void internalAdd(const T& element);//specially for UNIVERSE
MySet<T> retrieve(const Set& mark);
public:
MySet<T>();
~MySet<T>();
void forEachSubset();
bool eachSub(MySet<T>& dummy);
int getSize(){return size;}
void clear(){ size=0;}
void setName(const char* theName);
const char* getName() const{return name;}
const MySet<T>& remove(const MySet<T>& other);
const MySet<T>& remove(const T& element);
const MySet<T>& add(const T& element);
const MySet<T>& add(const MySet<T>& other);
bool includes(const MySet<T>& other) const;
bool includes(const T& element) const;
bool operator>(const T& element) const;
bool operator>(const MySet<T>& other) const;
bool operator>=(const MySet<T>& other) const;
bool operator<(const MySet<T>& other) const;
bool operator<=(const MySet<T>& other) const;
bool operator ==(const MySet<T>& other) const;
bool operator !=(const MySet<T>& other) const;
const MySet<T>& operator=(const MySet<T>& other);
MySet<T> operator+(const MySet<T>& other);//union
MySet<T> operator-(const MySet<T>& other);//difference
MySet<T> operator*(const MySet<T>& other);//intersection
MySet<T> operator!();
//void calcPower();
//void displayPower();
//void display() const;
};
/*
template<>
class MySet<char*>
{
private:
//void internalAdd(const char*& element);
public:
const MySet<char*>& remove(const char*& element);
//const MySet<char*>& operator=(const MySet<char*>& other);
bool includes(const char*& element) const;
const MySet<char*>& add(const char*& element);
void display() const;
};
*/
template<class T>
MySet<T>* MySet<T>::UNIVERSE=NULL;
template<class T>
MySet<T>* MySet<T>::EMPTY=NULL;
/*
template<class T>
MySet<T> UNIVERSE;
template<class T>
MySet<T> EMPTY;
*/
template<class T>
int MySet<T>::setIndex=-1;
/*
template<class T>
void MySet<T>::displayPower()
{
power.display();
}
template<class T>
void MySet<T>::calcPower()
{
MySet<T> dummy;
power.clear();
forEachSubset();
while (eachSub(dummy))
{
power.add(dummy);
}
}
*/
template<class T>
MySet<T> MySet<T>::retrieve(const Set& mark)
{
MySet<T> result;
int i=0;
i=mark.first();
while (i!=-1)
{
result.add(members[i]);
i=mark.next(i);
}
return result;
}
template<class T>
void MySet<T>::forEachSubset()
{
marker.setSize(size);
marker.set();//set all to be 1
marker.forEachSubSet(receiver);
}
template<class T>
bool MySet<T>::eachSub(MySet<T>& dummy)
{
while (marker.eachSub(receiver))
{
dummy= retrieve(receiver);
return true;
}
return false;
}
//* means intersection
template<class T>
MySet<T> MySet<T>::operator *(const MySet<T>& other)
{
MySet<T> result;
result=UNIVERSE - this->operator!() - !other;
return result;
}
template<class T>
MySet<T> MySet<T>::operator !()
{
MySet<T> result;
result=UNIVERSE - *this;
return result;
}
template<class T>
MySet<T> MySet<T>::operator -(const MySet<T>& other)
{
MySet<T> result;
result=*this;
for (int i=0; i<other.size; i++)
{
result.remove(other.members[i]);
}
return result;
}
template<class T>
const MySet<T>& MySet<T>::remove(const MySet<T>& other)
{
for (int i=0; i<other.size; i++)
{
remove(other.members[i]);
}
return *this;
}
template<class T>
const MySet<T>& MySet<T>::remove(const T& element)
{
bool found=false;
for (int i=0; i<size; i++)
{
if (!found)
{
//if (methods::eq(members[i], element))
if (members[i]==element)
{
found=true;
size--;//then we have to check if
if (i<size)
{
//even we already shrink the size, still better not to copy
//methods::assign(members[i], members[i+1]);
members[i]=members[i+1];
}
}
}
else
{
//just shift array
//methods::assign(members[i], members[i+1]);
members[i]=members[i+1];
}
}
return *this;
}
template<>
const MySet<charPtr>& MySet<charPtr>::remove(const charPtr& element)
{
bool found=false;
for (int i=0; i<size; i++)
{
if (!found)
{
//if (methods::eq(members[i], element))
if (strcmp(members[i], element)==0)
{
found=true;
size--;//then we have to check if
if (i<size)
{
//even we already shrink the size, still better not to copy
//methods::assign(members[i], members[i+1]);
members[i]=members[i+1];
}
}
}
else
{
//just shift array
//methods::assign(members[i], members[i+1]);
members[i]=members[i+1];
}
}
return *this;
}
template<class T>
MySet<T> MySet<T>::operator +(const MySet<T>& other)
{
MySet<T> result;
result=*this;
for (int i=0; i<other.size; i++)
{
result.add(other.members[i]);
}
return result;
}
template<class T>
void MySet<T>::setName(const char* theName)
{
strcpy(name, theName);
}
template<class T>
const MySet<T>& MySet<T>::operator =(const MySet<T>& other)
{
size=other.size;
for (int i=0; i<size; i++)
{
//methods::assign(members[i], other.members[i]);
members[i]=other.members[i];
}
return *this;
}
template<class T>
bool MySet<T>::operator <(const MySet<T>& other) const
{
//return other.>*this && !this->operator>other;
//return other>*this;
return other.includes(*this)&&!includes(other);
}
template<class T>
bool MySet<T>::operator <=(const MySet<T>& other) const
{
return other.includes(*this);
}
template<class T>
bool MySet<T>::operator ==(const MySet<T>& other) const
{
return includes(other)&& other.includes(*this);
}
template<class T>
bool MySet<T>::operator !=(const MySet<T>& other) const
{
return !this->operator==(other);
}
template<class T>
bool MySet<T>::operator >(const T& element) const
{
return includes(element);
}
template<class T>
bool MySet<T>::operator >(const MySet<T>& other) const
{
return includes(other)&&!other.includes(*this);
}
template<class T>
bool MySet<T>::operator >=(const MySet<T>& other) const
{
return includes(other);
}
template<class T>
MySet<T>::~MySet<T>()
{
uninitialize();
}
template<class T>
MySet<T>::MySet<T>()
{
initialize();
}
template<class T>
void MySet<T>::uninitialize()
{
//MySet<T>* temp;
if (setIndex==EmptyIndex+1)
{
setIndex=-1;
delete UNIVERSE;
delete EMPTY;
}
else
{
if (setIndex!=-1)
{
setIndex--;
}
}
/*
if (UNIVERSE!=NULL)
{
temp=UNIVERSE;
UNIVERSE=NULL;
delete temp;
}
if (EMPTY!=NULL)
{
temp=EMPTY;
EMPTY=NULL;
delete EMPTY;
}
*/
}
template<class T>
void MySet<T>::initialize()
{
//only run once to initialize universe and empty
if (setIndex==-1)
{
setIndex++;
index=EmptyIndex+1;;//set index=2
UNIVERSE=new MySet<T>;
UNIVERSE->setName("UNIVERSE");
UNIVERSE->index=0;
EMPTY=new MySet<T>;
EMPTY->index=1;
EMPTY->setName("EMPTY");
sprintf(name, "name:no. %d", index);
size=0;
setIndex=3;
}
else
{
//when setIndex==0
if (setIndex==UniverseIndex)//these are for universe and empty
{
size=0;
}
else
{
index=setIndex++;
sprintf(name, "name:no. %d", index);
size=0;
}
}
}
template<>
bool MySet<charPtr>::includes(const charPtr& element) const
{
for (int i=0; i<size; i++)
{
//if (methods::eq(members[i], element))
if (strcmp(members[i], element)==0)
{
return true;
}
}
return false;
}
template<class T>
bool MySet<T>::includes(const T& element) const
{
for (int i=0; i<size; i++)
{
//if (methods::eq(members[i], element))
if (members[i]==element)
{
return true;
}
}
return false;
}
template<class T>
bool MySet<T>::includes(const MySet<T>& other) const
{
for (int i=0; i<other.size; i++)
{
if (!includes(other.members[i]))
{
return false;
}
}
return true;
}
//these are what the name suggests, alter the set itself
template<class T>
void MySet<T>::internalAdd(const T& element)
{
if (!includes(element))
{
//methods::assign(members[size++], element);
members[size++]=element;
}
}
template<class T>
const MySet<T>& MySet<T>::add(const T& element)
{
if (!includes(element))
{
//methods::assign(members[size++], element);
members[size++]=element;
UNIVERSE->internalAdd(element);//make sure it is in universe set
}
return *this;
}
template<class T>
const MySet<T>& MySet<T>::add(const MySet<T>& other)
{
for (int i=0; i<other.size; i++)
{
add(other.members[i]);
}
return *this;
}
/*
template<>
void MySet<charPtr>::display() const
{
printf("%s\n{", name);
for (int i=0; i<size; i++)
{
//methods::display(members[i]);
cout<<members[i];
if (i!=size-1)
{
printf(",");
}
}
//cout<<"}\n";
printf("}\n");
}
template<class T>
void MySet<T>::display() const
{
//cout<<name<<":{";
printf("%s\n{", name);
for (int i=0; i<size; i++)
{
//methods::display(members[i]);
members[i].display();
if (i!=size-1)
{
printf(",");
}
}
//cout<<"}\n";
printf("}\n");
}
*/
#endif
file name: main.cpp
#include <iostream>
#include "myset.h"
//#include "methods.h"
using namespace std;
const int DataLength=5;
typedef MySet<charPtr> charSet;
typedef MySet<charSet> charSetSet;
void powerSet(charSet source, charSetSet& result);
/*
#define IntSet MySet<int, IntSetMethods>
#define IntSetSet MySet<IntSet, IntSetMethods>
void calcPower(IntSet& dummy, IntSetSet& result);
*/
int data[DataLength]={3,2,4,7,1,};
char* strArray1[DataLength]=
{
"one", "two", "three", "four", "five"
};
char strArray2[DataLength][10];
int main()
{
//MySet<int, IntSetMethods> A, B, C;
//IntSet A,B,C;
MySet<int> A,B,C;
MySet<char*> X,Y;
charSetSet P;
//MySet<MySet<int, IntSetMethods>, IntSetMethods> P;
//IntSetSet P;
//MySet<MySet<int>> P;
A.setName("set name is A");
B.setName("set name is B");
X.setName("set name is X");
Y.setName("set name is Y");
//P.setName("the Power set of A");
for (int i=0; i<DataLength; i++)
{
strcpy(strArray2[i], strArray1[i]);
A.add(data[i]);
X.add(strArray1[i]);
if (i%2==0)
{
B.add(data[i]);
Y.add(strArray2[i]);
}
}
/*
A.display();
B.display();
X.display();
Y.display();
*/
cout<<A<<B<<X<<Y;
if (X==Y)
{
printf("okoklokkjkk\n");
}
cout<<(X-Y);
powerSet(X, P);
//P.display();
cout<<P;
//calcPower(A, P);
//P.display();
//A.calcPower();
//A.displayPower();
/*
if (A<=B)
{
cout<<"A<=B\n";
}
else
{
if (B<A)
{
cout<<"B<A\n";
}
if (B<=A)
{
cout<<"B<=A\n";
}
if (A==B)
{
cout<<"A==B\n";
}
if (A!=B)
{
cout<<"A!=B\n";
}
}
printf("for each subset\n");
P.clear();
A.forEachSubset();
while (A.eachSub(C))
{
P.add(C);
//C.display();
}
P.display();
*/
return 0;
}
void powerSet(charSet source, charSetSet& result)
{
charSet temp;
result.clear();
source.forEachSubset();
while (source.eachSub(temp))
{
result.add(temp);
}
}
/*
void calcPower(IntSet& dummy, IntSetSet& result)
{
IntSet temp;
result.clear();
dummy.forEachSubset();
while (dummy.eachSub(temp))
{
result.add(temp);
}
}
*/
file name: main.cpp
#include <iostream>
#include "myset.h"
#include "methods.h"
using namespace std;
const int DataLength=5;
#define IntSet MySet<int, IntSetMethods>
#define IntSetSet MySet<IntSet, IntSetMethods>
int data[DataLength]={3,2,4,7,1,};
void calcPower(IntSet& dummy, IntSetSet& result);
int main()
{
//MySet<int, IntSetMethods> A, B, C;
IntSet A,B,C;
//MySet<MySet<int, IntSetMethods>, IntSetMethods> P;
IntSetSet P;
A.setName("set name is A");
B.setName("set name is B");
P.setName("the Power set of A");
for (int i=0; i<DataLength; i++)
{
A.add(data[i]);
if (i%2==0)
{
B.add(data[i]);
}
}
A.display();
B.display();
calcPower(A, P);
P.display();
//A.calcPower();
//A.displayPower();
/*
if (A<=B)
{
cout<<"A<=B\n";
}
else
{
if (B<A)
{
cout<<"B<A\n";
}
if (B<=A)
{
cout<<"B<=A\n";
}
if (A==B)
{
cout<<"A==B\n";
}
if (A!=B)
{
cout<<"A!=B\n";
}
}
printf("for each subset\n");
P.clear();
A.forEachSubset();
while (A.eachSub(C))
{
P.add(C);
//C.display();
}
P.display();
*/
return 0;
}
void calcPower(IntSet& dummy, IntSetSet& result)
{
IntSet temp;
result.clear();
dummy.forEachSubset();
while (dummy.eachSub(temp))
{
result.add(temp);
}
}
The result is like following:
set name is A:{3,2,4,7,1}
set name is B:{3,4,1}
set name is X:{one,two,three,four,five}
set name is Y:{one,three,five}
name:no. 154:{two,four}
name:no. 2:{name:no. 4:{one}
,name:no. 5:{two}
,name:no. 6:{one,two}
,name:no. 7:{three}
,name:no. 8:{one,three}
,name:no. 9:{two,three}
,name:no. 10:{one,two,three}
,name:no. 11:{four}
,name:no. 12:{one,four}
,name:no. 13:{two,four}
,name:no. 14:{one,two,four}
,name:no. 15:{three,four}
,name:no. 16:{one,three,four}
,name:no. 17:{two,three,four}
,name:no. 18:{one,two,three,four}
,name:no. 19:{five}
,name:no. 20:{one,five}
,name:no. 21:{two,five}
,name:no. 22:{one,two,five}
,name:no. 23:{three,five}
,name:no. 24:{one,three,five}
,name:no. 25:{two,three,five}
,name:no. 26:{one,two,three,five}
,name:no. 27:{four,five}
,name:no. 28:{one,four,five}
,name:no. 29:{two,four,five}
,name:no. 30:{one,two,four,five}
,name:no. 31:{three,four,five}
,name:no. 32:{one,three,four,five}
,name:no. 33:{two,three,four,five}
}
Press any key to continue