network.cpp

A C++ code for generating sorting networks with n lines and m comparators as input parameters.

#include "Network.h"

Network::Network(void)
{
}

Network::Network(int n, int m)
{
	this->n=n;
	this->m=m;

	startLines=new int[m];
	endLines=new int[m];
}

//verifica daca secventa de n numere de la intrare este sortata corect la iesire
bool Network::isOrdered(int* s, int n1)
{
	for(int i=0; i<n1-1;i++)
		if (s[i] > s[i+1])
			return false;

	return true;

}

void Network::print()
{
	cout<<"Reteaua cu "<<n<<" linii si "<<m<<" comparatoare(sub forma (start line, end line, position)):\n";
	for(int i=0; i<m; i++)
	{
		cout<<"("<<startLines[i]<<", "<<endLines[i]<<", "<<i<<")   ";
	}
	cout<<endl;


}

//b este un sir binar
//functia de mai jos incrementeaza valoarea sirului cu 1
//functia nu trateaza depasirea de capacitate, deci trebuie sa ne asiguram ca nu se va ajunge la indicele -1
void Network::incrementBinary(int* b, int n1)
{
	bool transport=true;
	int i=n1-1;
	while(transport)
	{
		if(b[i]==0)
		{
			b[i]=1;
			transport=false;
		} else {
			b[i]=0;
			i--;
		}
	}
}


//s esteun sir de lungime n(pentru ca sunt n linii in retea)
void Network::sort(int* s)
{
	//aplicam fiecare comparator in ordinea lor
	int aux, sl, el;
	for(int i=0; i<m;i++)
	{
		//luam liniile comparatorului
		sl=startLines[i];
		el=endLines[i];

		//aplicam comparatorul cu numarul i
		if(s[sl]>s[el])
		{
			aux=s[sl];
			s[sl]=s[el];
			s[el]=aux;
		}
	}
}

bool Network::isSortNetwork()
{
	//verificam daca reteaua generata este o retea de sortare
	//generam toate combinatiile de 0 si 1, le sortam si verificam daca sunt sortate corect	
	
	//combinatia initiala(doar zerouri)
	int* b=new int[n];
	for(int i=0; i<n;i++)
		b[i]=0;
	
	//verificam si incrementam succesiv pana la valoarea maxima 111...1 -1
	int limit=pow((double)2, (double)n);
	int* b1= new int[n];
	for(int i=1; i<limit;i++)
	{		
		incrementBinary(b, n);

		//copiem sirul b intr-unul temporar(b1)		
		for(int j=0; j<n; j++)
			b1[j]=b[j];
		//sortam sirul b1 folosind reteaua		
		sort(b1);
		if(!isOrdered(b1, n))
		{
			/**cout<<"Sortare gresita-->la intrare: ";
			for(int j=0; j<n; j++)
			{
				cout<<b[j]<<" ";
			}

			cout<<"\nSortare gresita-->la iesire: ";
			for(int j=0; j<n; j++)
			{
				cout<<b1[j]<<" ";
			}*/

			return false;
		}
	}

	return true;
}

Network::~Network(void)
{
	delete[] startLines;
	startLines=0;
	delete[] endLines;
	endLines=0;
}