Template Set
A. First Edition
This is an improved version of set which is implemented by template. My intention is to create a
general purpose set class which is independent from its type. You see, set is just set. The operation
of union, intersection, difference should all be the same even you have a different type of element.
So, it is ideal to implement it in a template class.
There are several problems:
1. How to pass user-defined methods for comparison and displaying of elements which may be a class
or a structure etc. My answer is the way I learned from Mr. Shaffer. Using a class which has some
static member function defined by user for each particular type of element.
2. How to define the "Universe" and "Empty" set? Surely it seems an easy question by assuming you
can declare two objects of set class. It is true for normal class, but false for a template class
because you cannot declare an object of template class unless you instantiate it with type.
However, this is the job of user! My way is to declare the pointer instead of object. And I use a
counter to count the total object created for the particular type of class. When the every first
object is created, I try to make some little trick in constructor such that I can dynamically
create both "Universe" and "Empty" objects. The similar trick is done inside destructor. But be
careful! You have to think clearly about what to do here, otherwise you will easily fall in
infinite loop!
3. The last question is crazy and I even sent a email to Mr. Shaffer for help. How to create
"power set" , which is the set of all its sub sets? Got the idea? See following example:
template <class T, class methods>
class MySet
{
private:
T members[MaxMemberSize];
int size;
...
};
What is the type of its power set? T? MySet<T, methods>? No! It is MySet<MySet<T,methods>,methods>
if you manage to use same "methods" class for both classes. But can you do this inside a template
class? It seems that you want to drive compiler to be insane! Can we pass template class itself
for the type parameter of another template class? At least VC++6.0 seems to be negative. However,
it is easy to work around after user instantiate the template class. Or I will try some "special".
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: board.h
#include "cluster.h"
#include "node.h"
class Board
{
friend class Cluster;
private:
int board [BoardSize][BoardSize];
bool map[BoardSize][BoardSize];
bool restrict[BoardSize][BoardSize];
Cluster path;
int size;
void initialize();
bool valid(const Coord& pos);
Direction findDir(const Coord& start, const Coord& end);
Direction findNextDir(const Coord& curr, Direction dir);
bool impasse(const Coord& curr, Direction dir);
bool doPathFinding(const Coord& curr, const Coord& end, Direction dir);
public:
Board(int theSize=BoardSize);
void display();
void displayPath(bool showPath=true);
bool pathFinding(const Coord& start, const Coord& end);
bool pathFinding(const Coord& end);
bool pathFinding2(const Coord& start, const Coord& end);
void setRestrict(const Coord& pos);
void resetRestrict(const Coord& pos);
};
file name: methods.cpp
#ifndef METHODS_H
#define METHODS_H
#include <stdio.h>
#include "myset.h"
class IntMethods
{
public:
static bool eq(int x, int y){ return x==y;}
static void assign(int& target, int operand){ target=operand;}
static void display(int x){printf("%d", x);}
};
class IntSetMethods
{
public:
static bool eq(int x, int y){ return x==y;}
static void assign(int& target, int operand){ target=operand;}
static void display(int x){printf("%d", x);}
static bool eq(const MySet<int, IntSetMethods>& source,
const MySet<int, IntSetMethods>& other);
static void assign(MySet<int, IntSetMethods>& source,
const MySet<int, IntSetMethods>& other);
static void display(const MySet<int, IntSetMethods>& source);
};
bool IntSetMethods::eq(const MySet<int, IntSetMethods>& source,
const MySet<int, IntSetMethods>& other)
{
return source==other;
}
void IntSetMethods::assign(MySet<int, IntSetMethods>& source,
const MySet<int, IntSetMethods>&other)
{
source=other;
}
void IntSetMethods::display(const MySet<int, IntSetMethods>& source)
{
printf("name:%s{ ", source.getName());
source.display();
printf("}");
}
#endif
file name: myset.h
#ifndef MYSET_H
#define MYSET_H
#include <stdio.h>
#include "set.h"
const int MaxSetMember=50;
const int MaxNameLength=30;
const int UniverseIndex=0;
const int EmptyIndex=1;
template<class T, class methods>
class MySet
{
private:
static int setIndex;
static MySet<T, methods>* UNIVERSE;
static MySet<T, methods>* 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, methods> retrieve(const Set& mark);
public:
MySet<T, methods>();
~MySet<T, methods>();
void forEachSubset();
bool eachSub(MySet<T, methods>& dummy);
int getSize(){return size;}
void clear(){ size=0;}
void setName(const char* theName);
const char* getName() const{return name;}
const MySet<T, methods>& remove(const MySet<T, methods>& other);
const MySet<T, methods>& remove(const T& element);
const MySet<T, methods>& add(const T& element);
const MySet<T, methods>& add(const MySet<T, methods>& other);
bool includes(const MySet<T, methods>& other) const;
bool includes(const T& element) const;
bool operator>(const T& element) const;
bool operator>(const MySet<T, methods>& other) const;
bool operator>=(const MySet<T, methods>& other) const;
bool operator<(const MySet<T, methods>& other) const;
bool operator<=(const MySet<T, methods>& other) const;
bool operator ==(const MySet<T, methods>& other) const;
bool operator !=(const MySet<T, methods>& other) const;
const MySet<T, methods>& operator=(const MySet<T, methods>& other);
MySet<T, methods> operator+(const MySet<T, methods>& other);//union
MySet<T, methods> operator-(const MySet<T, methods>& other);//difference
MySet<T, methods> operator*(const MySet<T, methods>& other);//intersection
MySet<T, methods> operator!();
//void calcPower();
//void displayPower();
void display() const;
};
template<class T, class methods>
MySet<T, methods>* MySet<T, methods>::UNIVERSE=NULL;
template<class T, class methods>
MySet<T, methods>* MySet<T, methods>::EMPTY=NULL;
/*
template<class T, class methods>
MySet<T, methods> UNIVERSE;
template<class T, class methods>
MySet<T, methods> EMPTY;
*/
template<class T, class methods>
int MySet<T, methods>::setIndex=-1;
/*
template<class T, class methods>
void MySet<T, methods>::displayPower()
{
power.display();
}
template<class T, class methods>
void MySet<T, methods>::calcPower()
{
MySet<T, methods> dummy;
power.clear();
forEachSubset();
while (eachSub(dummy))
{
power.add(dummy);
}
}
*/
template<class T, class methods>
MySet<T, methods> MySet<T, methods>::retrieve(const Set& mark)
{
MySet<T,methods> result;
int i=0;
i=mark.first();
while (i!=-1)
{
result.add(members[i]);
i=mark.next(i);
}
return result;
}
template<class T, class methods>
void MySet<T,methods>::forEachSubset()
{
marker.setSize(size);
marker.set();//set all to be 1
marker.forEachSubSet(receiver);
}
template<class T, class methods>
bool MySet<T,methods>::eachSub(MySet<T,methods>& dummy)
{
while (marker.eachSub(receiver))
{
dummy= retrieve(receiver);
return true;
}
return false;
}
//* means intersection
template<class T, class methods>
MySet<T, methods> MySet<T, methods>::operator *(const MySet<T, methods>& other)
{
MySet<T, methods> result;
result=UNIVERSE - this->operator!() - !other;
return result;
}
template<class T, class methods>
MySet<T, methods> MySet<T, methods>::operator !()
{
MySet<T, methods> result;
result=UNIVERSE - *this;
return result;
}
template<class T, class methods>
MySet<T, methods> MySet<T, methods>::operator -(const MySet<T, methods>& other)
{
MySet<T, methods> result;
result=*this;
for (int i=0; i<other.size; i++)
{
result=remove(other.members[i]);
}
return result;
}
template<class T, class methods>
const MySet<T, methods>& MySet<T, methods>::remove(const MySet<T, methods>& other)
{
for (int i=0; i<other.size; i++)
{
remove(other.members[i]);
}
return *this;
}
template<class T, class methods>
const MySet<T, methods>& MySet<T, methods>::remove(const T& element)
{
bool found=false;
for (int i=0; i<size; i++)
{
if (!found)
{
if (methods::eq(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]);
}
}
}
else
{
//just shift array
methods::assign(members[i], members[i+1]);
}
}
return *this;
}
template<class T, class methods>
MySet<T, methods> MySet<T, methods>::operator +(const MySet<T, methods>& other)
{
MySet<T, methods> result;
result=*this;
for (int i=0; i<other.size; i++)
{
result.add(other.members[i]);
}
return result;
}
template<class T, class methods>
void MySet<T, methods>::setName(const char* theName)
{
strcpy(name, theName);
}
template<class T, class methods>
const MySet<T, methods>& MySet<T, methods>::operator =(const MySet<T, methods>& other)
{
size=other.size;
for (int i=0; i<size; i++)
{
methods::assign(members[i], other.members[i]);
}
return *this;
}
template<class T, class methods>
bool MySet<T, methods>::operator <(const MySet<T, methods>& other) const
{
//return other.>*this && !this->operator>other;
//return other>*this;
return other.includes(*this)&&!includes(other);
}
template<class T, class methods>
bool MySet<T, methods>::operator <=(const MySet<T, methods>& other) const
{
return other.includes(*this);
}
template<class T, class methods>
bool MySet<T, methods>::operator ==(const MySet<T, methods>& other) const
{
return includes(other)&& other.includes(*this);
}
template<class T, class methods>
bool MySet<T, methods>::operator !=(const MySet<T, methods>& other) const
{
return !this->operator==(other);
}
template<class T, class methods>
bool MySet<T, methods>::operator >(const T& element) const
{
return includes(element);
}
template<class T, class methods>
bool MySet<T, methods>::operator >(const MySet<T, methods>& other) const
{
return includes(other)&&!other.includes(*this);
}
template<class T, class methods>
bool MySet<T, methods>::operator >=(const MySet<T, methods>& other) const
{
return includes(other);
}
template<class T, class methods>
MySet<T, methods>::~MySet<T, methods>()
{
uninitialize();
}
template<class T, class methods>
MySet<T, methods>::MySet<T, methods>()
{
initialize();
}
template<class T, class methods>
void MySet<T, methods>::uninitialize()
{
//MySet<T, methods>* 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, class methods>
void MySet<T, methods>::initialize()
{
//only run once to initialize universe and empty
if (setIndex==-1)
{
setIndex++;
index=EmptyIndex+1;;//set index=2
UNIVERSE=new MySet<T, methods>;
UNIVERSE->setName("UNIVERSE");
UNIVERSE->index=0;
EMPTY=new MySet<T, methods>;
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<class T, class methods>
bool MySet<T, methods>::includes(const T& element) const
{
for (int i=0; i<size; i++)
{
if (methods::eq(members[i], element))
{
return true;
}
}
return false;
}
template<class T, class methods>
bool MySet<T, methods>::includes(const MySet<T, methods>& 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, class methods>
void MySet<T, methods>::internalAdd(const T& element)
{
if (!includes(element))
{
methods::assign(members[size++], element);
}
}
template<class T, class methods>
const MySet<T, methods>& MySet<T, methods>::add(const T& element)
{
if (!includes(element))
{
methods::assign(members[size++], element);
UNIVERSE->internalAdd(element);//make sure it is in universe set
}
return *this;
}
template<class T, class methods>
const MySet<T, methods>& MySet<T, methods>::add(const MySet<T, methods>& other)
{
for (int i=0; i<other.size; i++)
{
add(other.members[i]);
}
return *this;
}
template<class T, class methods>
void MySet<T, methods>::display() const
{
//cout<<name<<":{";
printf("%s\n{", name);
for (int i=0; i<size; i++)
{
methods::display(members[i]);
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;
#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}
the Power set of A
{name:name:no. 5{ name:no. 5
{3}
},name:name:no. 6{ name:no. 6
{2}
},name:name:no. 7{ name:no. 7
{3,2}
},name:name:no. 8{ name:no. 8
{4}
},name:name:no. 9{ name:no. 9
{3,4}
},name:name:no. 10{ name:no. 10
{2,4}
},name:name:no. 11{ name:no. 11
{3,2,4}
},name:name:no. 12{ name:no. 12
{7}
},name:name:no. 13{ name:no. 13
{3,7}
},name:name:no. 14{ name:no. 14
{2,7}
},name:name:no. 15{ name:no. 15
{3,2,7}
},name:name:no. 16{ name:no. 16
{4,7}
},name:name:no. 17{ name:no. 17
{3,4,7}
},name:name:no. 18{ name:no. 18
{2,4,7}
},name:name:no. 19{ name:no. 19
{3,2,4,7}
},name:name:no. 20{ name:no. 20
{1}
},name:name:no. 21{ name:no. 21
{3,1}
},name:name:no. 22{ name:no. 22
{2,1}
},name:name:no. 23{ name:no. 23
{3,2,1}
},name:name:no. 24{ name:no. 24
{4,1}
},name:name:no. 25{ name:no. 25
{3,4,1}
},name:name:no. 26{ name:no. 26
{2,4,1}
},name:name:no. 27{ name:no. 27
{3,2,4,1}
},name:name:no. 28{ name:no. 28
{7,1}
},name:name:no. 29{ name:no. 29
{3,7,1}
},name:name:no. 30{ name:no. 30
{2,7,1}
},name:name:no. 31{ name:no. 31
{3,2,7,1}
},name:name:no. 32{ name:no. 32
{4,7,1}
},name:name:no. 33{ name:no. 33
{3,4,7,1}
},name:name:no. 34{ name:no. 34
{2,4,7,1}
}}
Press any key to continue