// ************************************************************************** //
//                                                                            //
//    eses                   eses                                             //
//   eses                     eses                                            //
//  eses    eseses  esesese    eses   Embedded Systems Group                  //
//  ese    ese  ese ese         ese                                           //
//  ese    eseseses eseseses    ese   Department of Computer Science          //
//  eses   eses          ese   eses                                           //
//   eses   eseses  eseseses  eses    University of Kaiserslautern            //
//    eses                   eses                                             //
//                                                                            //
// ************************************************************************** //
// PeriodicBalanceSortNet implements the periodic balanced sorting network    //
// [DPRS89]. This sorting network has depth log(N)^2 and requires N*log(N)^2  //
// comparators. It is therefore not very efficient; it simply consists of a   //
// sequence of log(N) blocks of the same kind, where each block consists of   //
// log(N) columns where each has N comparators in form of reversed half       //
// cleaners in the single partitions.                                         //
// ************************************************************************** //

[16] nat b;

function exp(nat x, nat y):nat{
	nat h1,i;
        h1 = 1;
   
	if(x!=0){
		for(i=1..y){
			h1 = h1*x;
		}
	}

	return h1; 
}



function PeriodicBalancedSortNet([16]nat a): nat{
nat i,l,d, l1, h, n;
nat aSize,x,y, p;

aSize = 16;

//gather the inputs
	for(i=0..aSize-1){
		b[i]=a[i];
	}

	for(l=0..3){ // 3 = log2 16
		for(d=0..3){
			l1 = exp(2,(4-d));
			n = aSize/l1;
			for(p=0..n-1){ 
				for(i=0..l1/2-1){
					x = p*l1+i;
					y = (p+1)*l1-1-i;
					if(b[x]>b[y]){
						h = b[x];
						b[x]=b[y]; //swap
						b[y]= h;
					}	
				}
			}
		}
	}
	return 1;
}


thread test1{
	nat t;
	[16]nat a;
	nat i;
	bool test1_passed;

	for(i=0..15){
		a[i]=i+1;
	}
	a[5]=9; 
	a[8]=6; 
	a[10]=7;
	a[6]=11;
	test1_passed = true;
	t = PeriodicBalancedSortNet(a);

	for(i=0..15){
        if((b[i]==(i+1)) & (test1_passed != false)){
            test1_passed = true;
        }else{
        test1_passed = false;
        }
    }

}


thread test2{
	nat t;
	[16]nat a;
	nat i;
	bool test2_passed;

	for(i=0..15){
		a[i]=i+1;
	}
	test2_passed = true;
	t = PeriodicBalancedSortNet(a); 

	for(i=0..15){
        if((b[i]==(i+1)) & (test2_passed != false)){
            test2_passed = true;
        }else{
        test2_passed = false;
        }
    }
}

thread test3{
	nat t;
	[16]nat a;
	nat i;
	bool test3_passed;

	for(i=0..15){
		a[i]=16-i;
	}
	test3_passed = true;
	t = PeriodicBalancedSortNet(a);  

	for(i=0..15){
        if((b[i]==(i+1)) & (test3_passed != false)){
            test3_passed = true;
        }else{
        test3_passed = false;
        }
    }

}