Dependency

A. First edition

This is first edition of my dependency class.

B.The problem

Can you imagine what is a dependency problem? 

1. Suppose you have a sequence of courses to take and each course has 0 or more pre-requisite 

courses. I want you to list all dependency relations.

2. Suppose you are writing a compiler, one of basic part is how to solve the forward references. 

That is A is defined by B, B is defined by C... So, how to book keep the dependency relations. 

3. Suppose you are writing a file to implement the functionality of "makefile". You need to establish

a dependency tree of all files.

It is actually a kind of edge list implementation of graph. Each node of list is actually a struct

which has a string as data, a link list of other strings which depends on it. 

D.The major functions

C.Further improvement

#include <iostream>

using namespace std;

const int MaxListSize=40;

struct Link
{
	int data;
	Link* next;
};

struct Vertex
{
	char* str;
	Link* depend;
};

class Depend
{
private:
	Vertex* lst[MaxListSize];
	int size;
	void addNode(const char* str);
	void addSon(int index, int son);

public:
	Depend();
	~Depend();
	int getSize() { return size;}
	int find(const char* str);
	bool append(const char* str);
	bool remove(const char* str);
	void readFromFile(const char* fileName);
	void addDepend(int index, const char* str);
	void print();

};


int main()
{
	Depend D;
	D.readFromFile("c:\\depend.txt");
	D.print();
	return 0;
}

void Depend::print()
{
	Link* ptr;
	for (int i=0; i<size; i++)
	{
		cout<<"node no."<<i<<":"<<lst[i]->str<<" : ";
		ptr=lst[i]->depend;
		while (ptr!=NULL)
		{
			cout<<lst[ptr->data]->str<<"  ";
			ptr=ptr->next;
		}
		cout<<endl;
	}
}

void Depend::addSon(int index, int son)
{
	Link* ptr;
	ptr= lst[index]->depend;
	if (ptr==NULL)
	{
		ptr=new Link;
		ptr->data= son;
		ptr->next=NULL;
		lst[index]->depend=ptr;
		return;
	}
	while (ptr->next!=NULL)
	{
		if (ptr->next->data==son)
		{
			return;//already there
		}
		ptr=ptr->next;
	} 
	//add new link
	ptr->next= new Link;
	ptr->next->data=son;
	ptr->next->next=NULL;
}

void Depend::addDepend(int index, const char* str)
{
	int pos= find(str);
	Link* ptr;
	if (pos==-1)
	{
		append(str);
		pos=size-1;//size++
		addSon(index, pos);
	}
	else
	{
		addSon(index, pos);
		ptr= lst[pos]->depend;
		while (ptr!=NULL)
		{
			addSon(index, ptr->data);
			ptr=ptr->next;
		} 
	}
}

void Depend::addNode(const char* str)
{
	char buffer[100];
	int index;
	strcpy(buffer, str);
	char* ptr=buffer;
	ptr=strtok(ptr, " :\n");

	index=find(ptr);
	if (index==-1)
	{
		append(ptr);
		index=size-1;
	}
	ptr=NULL;
	ptr=strtok(ptr, " :\n");
	while (ptr!=NULL)
	{
		addDepend(index, ptr);
		ptr=NULL;
		ptr=strtok(ptr, " :\n");
	}
}


void Depend::readFromFile(const char* fileName)
{
	FILE* stream;
	char buffer[100];
	if ((stream=fopen(fileName, "r"))==NULL)
	{
		cout<<"fail to read file "<<fileName<<endl;
		return;
	}
	while (fgets(buffer, 100, stream)!=NULL)
	{
		addNode(buffer);
	}
	fclose(stream);
}

Depend::~Depend()
{
	for (int i=0; i<size; i++)
	{
		delete [] lst[i]->str;
		delete lst[i];
	}
}

Depend::Depend()
{
	size=0;
}

int Depend::find(const char* str)
{
	for (int i=0; i<size; i++)
	{
		if (strcmp(str, lst[i]->str)==0)
		{
			return i;
		}
	}
	return -1;
}


bool Depend::append(const char* str)
{
	if (find(str)!=-1)
	{
		return false;
	}	
	lst[size]=new Vertex;
	lst[size]->depend=NULL;
	lst[size]->str=new char[strlen(str)+1];
	strcpy(lst[size]->str, str);
	size++;
	return true;
}

bool Depend::remove(const char* str)
{
	int index = find(str);
	if (index==-1)
	{
		return false;
	}
	delete [] lst[index]->str;
	lst[index]->str=NULL;
	delete lst[index];
	size--;
	for (int i=index; i<size; i++)
	{
		lst[i]=lst[i+1];
	}
	return true;
}

Here is the result:

node no.0:238 : 228
node no.1:228 :
node no.2:229 : 228 248
node no.3:248 :
node no.4:239 : 238 228
node no.5:249 : 238 228 248
node no.6:352 : 239 238 228 249 248
node no.7:348 : 249 238 228 248
node no.8:335 : 239 238 228 249 248
Press any key to continue

Here is the input file:

238 : 228
229 : 228 248
239 : 238
249 : 238 248
352 : 239 249
348 : 249
335 : 239 249