
// Benchmark programs from Stanford 
// Integer Benchmark Suite
// consisted of 7 programs :
//  bubble sort, tower of hanoi, matrix
//  multiplication, 
//  permutation, quick sort, 8-queens, prime 
//  by Sieve of Erasthones


// bubble sort, sort data 100 items 

global a[100];

bubble(n) {
  i = n;
  j = 0;
  while( i > 0 ) {
    while( j < n ) {
     if( a[j] > a[j+1] ) {
       t = a[j];
       a[j] = a[j+1];
       a[j+1] = t;
     }
     j = j+1;
    }
    i = i-1;
  }
}

main() {
  bubble(100);
}

// tower of hanoi 
// D is the number of disk
global num[4], D;	

mov(n, from, to) {
  if ( n == 1 ) {
    num[from] = num[from] - 1 ;
    num[to] = num[to] + 1;
    print(from," -> ", to, "\n");
  } else {
    other = 6 - from - to;
    mov(n-1, from, other);
    mov(1, from, to);
    mov(n-1, other, to);
  }
}

// move 5 disks from pole 1 to pole 3
main() {
  D = 5;
  num[0] = 0;
  num[1] = D;
  num[2] = 0;
  num[3] = 0;
  mov(D,1,3); 
}

// matrix multiplication 

global a[100], b[100], c[100];
// matrix size n x n : A = B * C

matmul(n) {			
  i = 0;
  while( i<n ) {
    j = 0;
    while( j<n ) {
      m = i*N + j;
      c[m] = 0;
      k = 0;
      while( k<n ) {
	c[m] = c[m] +(a[i*n + k]* b[k*n +j]);
	k = k+1;
      }
      j = j+1;
    }
    i = i+1;
  }
}

main() {
  matmul(10);
}

// permutation, generate a permuted sequence
// N is the length of sequence
global val[4], id, N;	

writeperm() {
  i = 0;
  while( i<N ) {
    print(val[i]," ");
    i = i+1;
  }
  print("\n");
}

visit(k) {
  id = id + 1;
  val[k] = id;
  if( id == (N-1) ) writeperm();
  t = 0;
  while ( t<N ) {
    if( val[t] == 0 ) visit(t);
    t = t+1;
  }
  id = id-1;
  val[k]= 0;
}

main() {
  N = 4;
  i = 0;
  while( i<N ) {
    val[i] = 0;
    i = i+1;
  }
  id = 0-1;
  visit(0);
}

// quick sort  27 June 97

global a[100]; // sort 100 integers

qsort(l,r) {
  if( r>l ) {
    v = a[r];
    i = l-1;
    j = r;
    s1 = 1;
    while( s1 ) {
      s2 = 1;
      while( s2 ) {
	i = i + 1;
	if( a[i] >= v ) s2 = 0;
      }
      s2 = 1;
      while( s2 ) {
	j = j -1;
	if( a[j] <= v ) s2 = 0;
      }
      t = a[i];
      a[i] = a[j];
      a[j] = t;
      if( j <= i ) s1 = 0;
    }
    a[j] = a[i];
    a[i] = a[r];
    a[r] = t;
    qsort(l,i-1);
    qsort(i+1,r);
  }
}

main() {
  qsort(0,100);
}

// 8-queens  27 June 97

global Q, Z, D;
global col[8], d45[15], d135[15], queen[8], 
	soln;

printboard() {
  i = 0;
  while( i<Q ) {
    print(queen[i], " ");
    i = i + 1;
  }
  soln = soln + 1;
  print("\n");
}

find(level) {
  if( level == Q ) {
    printboard();
  } else {
    i = 0;
    while( i<Q ) {
      if( (col[i] >= level) && 
	  (d45[level+i] >= level) &&
	  (d135[level+Q-1-i] >= level ) ) {
	queen[level] = i;
	col[i] = level;
	d45[level+i] = level;
	d135[level+Q-1-i] = level;
	find(level+1);
	col[i] = Z;
	d45[level+i] = Z;
	d135[level+Q-1-i] = Z;
      }
      i = i + 1;
    }
  }
}

main() {
  Q  = 8; Z = Q + 1; D = Q + Q - 1;
  soln = 0;
  i = 0;
  while( i<Q ) {
    col[i] = Z;
    i = i + 1;
  }
  i = 0;
  while( i < D ) {
    d45[i] = Z;
    d135[i] = Z;
    i = i + 1;
  }
  find(0);
  print("no of soln ", soln);
}

// prime number by Sieve of Erasthones 
// method  27 June 97

// find all primes that is less than 10000
global p[10000];  

sieve(n) {
  i = 0;
  while( i<n ) {
    if( p[i] ) {
      prime = i + i + 3;
      k = i + prime;
      while( k<n ) {
	p[k] = 0;
	k = k + prime;
      }
    }
    i = i + 1;
  }
}

main() {
  i = 0;
  while( i<10000 ) {
    p[i] = 1;
    i = i + 1;
  }
  sieve(10000);
}

