Dependency

Dependency(set)

    A. Second Edition

    This is the second edition of my "dependency" and spend half day to implement a help class "Set" which will

    be intensively used throughout this series.

    B.The problem

"Function dependency" is a very important issue in database theory. And what's more, it is the essence of all.

Because I think it is the key of knowledge: the world is described by relations and relations of relations.

¡¡

C.The idea of program
¡¡
This is a rather old topic. There are some topics I like to write programs over and over, such as DFS,DFA and
¡¡
Sets. Compared with the very, very first approach more than a year ago, I now understand more about set theory.
¡¡
And I am using a rather simple way---bitset which is in the standard template library(STL).
¡¡

    D.The major functions

    There are few points to mention except for the "forEachSubset" function. I think I do it in a similar way like

    "strtok". Do you feel strange that I connect these two together? You first call "forEachSubset" once and then

    repeatedly call "eachSub" function to get an output "Set" parameter which is a "proper subset" of calling object.

    Please note that I ignore the calling set itself which is a trivial subset, but include the "empty set" at last.

    (maybe I should remove the annoying empty set!?)

    The implementation is simple: each existing bit has two choice: either in or not in. And I always do this kind of

    algorithms like ancient Chinese "calculus"---or addition calculator.

    The second feature is that I have become a fanatic about operator-overloading. I have used up the common operators

    for overloading my "set" class.

    ¡¡

    E.Further improvement

    ¡¡

    F.File listing

    1. rules.h

    2. rules.cpp

    3. set.h

    4. set.cpp

    5. main.cpp (main)

    file name: set.h

    #ifndef SET_H
    #define SET_H

    #include <iostream>
    #include <bitset>

    using namespace std;

    const int MaxAttrNumber=20;

    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 next(int current);
    	int first();
    	int count();
    	Set intersection(const Set& dummy);
    	Set unionSet(const Set& dummy);
    	Set difference(const Set& dummy);

    	//I am crazy about operator overloading!!!:)
    	Set operator-(const Set& dummy);
    	Set operator+(const Set& dummy);
    	Set operator*(const Set& dummy);
    	void operator=(const Set& dummy);
    	bool operator==(const Set& dummy);
    	bool operator!=(const Set& dummy);
    	bool operator>(const Set& dummy);
    	bool operator>=(const Set& dummy);
    	bool operator<(const Set& dummy);
    	bool operator<=(const Set& dummy);
    	void set(int pos);
    	void forEachSubSet(Set& dummy);//must be called before "eachSub()"
    	bool eachSub(Set& dummy);
    	void set();
    	void reset(int pos);
    	void reset();
    	bool test(int pos) const;
    	bool isIn(const Set& dummy);
    	void setSize(int theSize) {size=theSize;}
    	Set(int theSize=10);
    };

    #endif

    file name: set.cpp

    #include "Set.h"

    bool Set::isIn(const Set& dummy)
    {
    	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)
    {
    	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)
    {
    	return !(this->operator ==(dummy));
    }

    bool Set::operator <(const Set& dummy)
    {
    	return (this->isIn(dummy)&&this->operator !=(dummy));
    }

    bool Set::operator <=(const Set& dummy)
    {
    	return isIn(dummy);
    }

    bool Set::operator >(const Set& dummy)
    {
    	return !(this->operator <=(dummy));
    }

    bool Set::operator >=(const Set& dummy)
    {
    	return !(this->operator <(dummy));
    }

    bool Set::operator ==(const Set& dummy)
    {
    	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)
    {
    	dummy=*this;
    }

    bool Set::eachSub(Set& dummy)
    {
    	int index=first();//starting from very first

    	while (index!=-1)//not exceeding boundery
    	{
    		if (dummy.test(index))
    		{
    			dummy.reset(index);
    			return true;
    		}
    		else
    		{
    			dummy.set(index);
    			index=next(index);
    		}
    	}
    	return false;
    }

    int Set::first()
    {
    	return next(-1);
    }

    int Set::count()
    {
    	return theSet.count();
    }

    Set Set::unionSet(const Set& dummy)
    {
    	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)
    {
    	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)
    {
    	return unionSet(dummy);
    }

    Set Set::operator -(const Set& dummy)
    {
    	return difference(dummy);
    }

    Set Set::intersection(const Set& dummy)
    {
    	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)
    {
    	return intersection(dummy);
    }

    file name: rules.h

    #include <iostream>
    #include <bitset>
    #include "set.h"

    using namespace std;

    //make it simple, the first line must list all variables or attributes
    //"relation"(A,B,C...)
    const int MaxNameLength=5;
    const int MaxRuleNumber=100;

    class Rule
    {
    	friend class Rules;
    private:
    	Set lhs;
    	Set rhs;
    public:
    	Rule();
    	bool test(int pos, bool isLeft);
    	void lhsSet(int pos);
    	void rhsSet(int pos);
    	void setSize(int theSize);
    	void set(int pos, bool isLeft);
    	void setRule(const Set& left, const Set& right);
    	void operator=(const Rule& dummy);
    };

    class Rules
    {
    private:
    	char attributes[MaxAttrNumber][MaxNameLength+1];
    	char relationName[MaxNameLength+1];
    	int attrCount;
    	int attrFound[MaxAttrNumber];
    	int numberFound;
    	int searchByChar(char ch, int step);
    	void ruleReading(FILE* stream);
    	Rule rules[MaxRuleNumber];
    	int ruleNumber;
    	void displayRule(int index);
    	void split();
    	void addRule(const Set& left, const Set& right);
    	int extractNames(FILE* stream, char* delimeters, char endChar='\n');
    public:
    	void addRule(const Rule& dummy);
    	void readFile(const char* fileName);
    	void display();
    	Rules();
    };

    ¡¡

    file name: rules.cpp

    #include "Rules.h"

    void Rules::display()
    {
    	cout<<"\nnow display\n";
    	cout<<relationName<<"(";
    	for (int i=0; i<attrCount; i++)
    	{
    		cout<<attributes[i];
    		if (i!=attrCount-1)
    		{
    			cout<<",";
    		}
    		else
    		{
    			cout<<");\n";
    		}
    	}
    	for (i=0; i<ruleNumber; i++)
    	{
    		displayRule(i);
    	}
    }

    bool Rule::test(int pos, bool isLeft)
    {
    	if (isLeft)
    	{
    		return lhs.test(pos);
    	}
    	else
    	{
    		return rhs.test(pos);
    	}
    }

    void Rules::displayRule(int index)
    {
    	for (int i=0; i<attrCount; i++)
    	{
    		if (rules[index].test(i, true))
    		{
    			cout<<attributes[i];
    		}
    	}
    	cout<<" -> ";
    	for (i=0; i<attrCount; i++)
    	{
    		if (rules[index].test(i, false))
    		{
    			cout<<attributes[i];
    		}
    	}
    	cout<<";\n";
    }

    void Rule::set(int pos, bool isLeft)
    {
    	if (isLeft)
    	{
    		lhsSet(pos);
    	}
    	else
    	{
    		rhsSet(pos);
    	}
    }

    void Rule::rhsSet(int pos)
    {
    	rhs.set(pos);
    }

    void Rule::lhsSet(int pos)
    {
    	lhs.set(pos);
    }

    Rule::Rule()
    {
    	lhs.reset();
    	rhs.reset();

    }

    void Rules::readFile(const char* fileName)
    {
    	FILE* stream;
    	stream=fopen(fileName, "r");
    	attrCount=extractNames(stream, "=,()", ';');//ignore the first relation name
    	ruleReading(stream);

    }

    void Rules::ruleReading(FILE* stream)
    {
    	char ch;
    	int step=0;
    	ruleNumber=0;//initialize
    	bool isLeft=true;
    	rules[ruleNumber].setSize(attrCount);//do twice!!
    	while (!feof(stream))
    	{
    		ch=fgetc(stream);
    		if (ch==';'||ch==',')
    		{
    			ruleNumber++;
    			rules[ruleNumber].setSize(attrCount);//do twice!!
    			isLeft=true;
    		}
    		else
    		{
    			if (ch=='-'||ch=='>')
    			{
    				isLeft=false;
    			}
    			else
    			{
    				if (isalpha(ch))
    				{
    					searchByChar(ch, step);
    					if (numberFound!=1)
    					{
    						if (step<MaxNameLength)
    						{
    							step++;
    						}
    						else
    						{
    							cout<<"illegal attribute stated!\n";
    							exit(1);
    						}
    					}
    					else
    					{
    						step=0;

    						rules[ruleNumber].set(attrFound[0], isLeft);
    					}
    				}
    			}
    		}
    	}
    }

    void Rule::setSize(int theSize)
    {
    	lhs.setSize(theSize);
    	rhs.setSize(theSize);
    }

    int Rules::searchByChar(char ch, int step)
    {
    	if (step==0)//this is first time, and all attributes are searched
    	{
    		numberFound=0;
    		for (int i=0; i<attrCount; i++)//
    		{
    			if (ch==attributes[i][step])
    			{
    				attrFound[numberFound]=i;
    				numberFound++;
    			}
    		}
    	}
    	else
    	{
    		int number=0;//new 'attrFound' re-counting
    		for (int i=0; i<numberFound; i++)
    		{
    			if (ch==attributes[attrFound[i]][step])
    			{
    				attrFound[number]=i;
    				number++;
    			}
    		}
    		numberFound=number;
    	}
    	return numberFound;
    }

    int findChar(char ch, char* str)
    {
    	int index=0;
    	while (str[index]!='\0')
    	{
    		if (str[index]==ch)
    		{
    			return index;
    		}
    		index++;
    	}
    	return -1;
    }

    //extract names from a line delimetered by various chars, like ',','(',')'....
    int Rules::extractNames(FILE* stream, char* delimeters, char endChar)
    {
    	int findChar(char ch, char* str);
    	char ch;
    	int nameIndex=0;
    	char buffer[MaxNameLength+1];
    	char* ptr=buffer;

    	while (!feof(stream))
    	{
    		ch=getc(stream);
    		if (ch==endChar)
    		{
    			if (ptr!=buffer)
    			{
    				*ptr='\0';
    				strcpy(attributes[nameIndex], buffer);
    			}
    			break;
    		}

    		if (findChar(ch, delimeters)>0)//deli reached
    		{
    			//skip the consecutive deli
    			if (ptr!=buffer)
    			{
    				*ptr='\0';
    				if (ch=='(')//the very first one
    				{
    					strcpy(relationName, buffer);
    				}
    				else
    				{
    					strcpy(attributes[nameIndex], buffer);
    					nameIndex++;
    				}
    				ptr=buffer;//restart
    			}
    		}
    		else
    		{
    			*ptr=ch;
    			ptr++;
    		}
    	}
    	return nameIndex;
    }

    Rules::Rules()
    {
    	numberFound=attrCount=0;
    }

    void Rule::operator =(const Rule& dummy)
    {
    	lhs=dummy.lhs;
    	rhs=dummy.rhs;
    }

    void Rules::addRule(const Rule& dummy)
    {
    	rules[ruleNumber++]=dummy;
    }

    void Rules::addRule(const Set& left, const Set& right)
    {
    	rules[ruleNumber++].setRule(left, right);
    }

    void Rule::setRule(const Set& left, const Set& right)
    {
    	lhs=left;
    	rhs=right;
    }

    void Rules::split()
    {
    	int index;
    	for (int i=0; i<ruleNumber; i++)
    	{
    		if (rules[i].rhs.count()>1)
    		{
    			index=rules[i].rhs.first();
    			index=rules[i].rhs.next(index);//starting from second one
    			while (index!=-1)
    			{
    				Set right;
    				right.setSize(rules[i].rhs);
    				right.set(index);
    				rules[i].rhs.reset(index);//remove from old rule
    				addRule(rules[i].lhs, right);
    				index=rules[i].rhs.next(index);
    			}
    		}
    	}
    }

    ¡¡

    file name: main.cpp (main)

    ¡¡

    #include "Rules.h"
    #include "set.h"

    int main()
    {
    	Rules R;
    	R.readFile("d:\\rules.txt");
    	R.display();

    	return 0;
    }

    ¡¡