/**
 * File expression.js
 * Copyright Wolfgang Kuehn 2002,2003
 */


var eps = 1e-10;

function Stack() {
   this.stack = new Array();
   this.count = 0;
   this.pop = Stack_pop;
   this.push = Stack_push;
   this.depth = Stack_depth;
}

function raiseError(number, message) {
   stop();
   if (is.nav)
     foo.bar;
   else
     eval("throw new Error("+number+",'"+message+"')");
}


function Stack_pop() {
   if (this.count==0) {
      alert("Stack underflow!");
      raiseError(1, "Stack underflow!");
   }
   return this.stack[--this.count];
}

function Stack_push(elem) {
   this.stack[this.count++] = elem;
}

function Stack_depth() {
   return count;
}
  
  
  
var nums;
var ops;
var nn;
var oo;
var buffer;
var totalCount;
var count;
var doDump;
var result;
var expr;
var ni, oi, ti;
var isRunning;

var trees = new Array();

function bintree(k) {
   trees[k] = new Array();
   if (k==0)
     trees[k][0] = "n";
   else
     bintree(k-1);

   var n = 0;
   for (var j=0; j<k; j++)
      for (var i in trees[j])
	for (var l in trees[k-j-1])
	  trees[k][n++] = trees[j][i]+trees[k-j-1][l]+"o";
}

function swap(seq,i,j) {
   var x = seq[i];
   seq[i] = seq[j];
   seq[j] = x;
}

var n;
var min, max;

/*
 * Compute all permutations of length m for 
 * characters in sequence seq and store it in array perm.
 */
function permute(perm, seq, m) {
   n = 0;
   permute_internal(0, perm, seq, m);
}

function permute_internal(i, perm, seq, m) {
   var l = seq.length;
   for (var j=i; j<l; j++) {
      swap(seq,i,j);
      if (i+1<m)
	permute_internal(i+1, perm, seq, m);
      else {
	 perm[n] = new Array();
	 for (var k=0; k<m; k++)
	   perm[n][k] = seq[k];
	 n++;
      }
      swap (seq,j,i);
   }
}

/*
 * Compute all combinations of length m for 
 * characters in sequence seq and store it in array comb.
 */
function combine(comb, seq, m) {
   var l = seq.length;
   var j;
   pl = new Array();
   var f = 1;
   
   for (j=0; j<m; j++, f*=l)
     pl[j] = f;

   for (n=0; n<f; n++) {
      comb[n] = new Array(l);
      for (j=0; j<m; j++) {
	 comb[n][j] = seq[Math.round(n/pl[j])%l];
      }
   }
}

function start() {
   document.FORM.BUTTON.value = "CANCEL";
   isRunning = true;
}

function stop() {
   document.FORM.BUTTON.value = "result";
   isRunning = false;
}

function compute(mode) {
   
   if (isRunning) {
      if (mode==3)
	stop();
      return;
   }
   
   if (mode==3)
     start();
   
   document.FORM.FOO.value = document.FORM.MIN.value = 
   document.FORM.MAX.value = document.FORM.COUNT.value = "";
   
   result = document.FORM.RESULT.value;
   doDump = (result=="");
   min = Number.MAX_VALUE;
   max = Number.MIN_VALUE;
   
   nums = document.FORM.NUMS.value.match(/-?\d+/g);// Groups of signed digits

   ops = document.FORM.OPS.value.match(/\S+/g);// Groups of non-whitespace

   if (document.FORM.OPERATOR[0].checked && ops.length<nums.length-1) {
      alert("Must be at least "+(nums.length-1)+" operators!");
      raiseError(1,"Must be at least "+(nums.length-1)+" operators!");
   }
   
   for (var i=0; i<nums.length; i++)
     nums[i] = parseInt(nums[i]);
   
   nn = new Array();
   
   if (document.FORM.NUMBER[0].checked)
     permute(nn, nums, nums.length);
   else
     combine(nn, nums, nums.length);

   oo = new Array();     
     
   if (document.FORM.OPERATOR[0].checked)
     permute(oo, ops, nums.length-1);
   else
     combine(oo, ops, nums.length-1);

   bintree(nums.length-1);
   
   document.FORM.FOO.value = buffer = "";
   
   if (mode==0)
     for (var i in nn)
       buffer += i+": "+nn[i]+'\n';
   else if (mode==1)
     for (var i in oo)
       buffer += i+": "+oo[i]+'\n';
   else if (mode==2)
     for (var i in trees[nums.length-1])
       buffer += i+": "+trees[nums.length-1][i]+'\n';
   else {
      totalCount = trees[nums.length-1].length*nn.length*oo.length;
      count = 0;
      expr = new Array();
      ni = oi = ti = 0;
      nextExpr();
      return;
   }
   
   document.FORM.FOO.value = buffer;
}

function nextExpr() {
   var pattern = trees[nums.length-1][ti];
   
   for (var oi in oo) {
      for (var l=nj=oj=0; l<pattern.length; l++) {
	 if (pattern.charAt(l)=='n')
	   expr[l] = nn[ni][nj++];
	 else
	   expr[l] = oo[oi][oj++];
      }
      var r = evaluate(expr);
      if (r!=Number.NaN && Math.abs(r-Math.round(r))<eps) {
	 r = Math.round(r);
	 max = Math.max(max,r);
	 min = Math.min(min,r);
	 if (Math.abs(r-result)<eps || doDump) {
	    buffer += expr+" = "+r+"\n";
	    if (buffer.length>4000) {
	       document.FORM.FOO.value += buffer;
	       buffer = '';
	       document.FORM.COUNT.value = count+"/"+totalCount;
     	    }
	 }
      }
      count++;
   }
   
   ni++;
   if (ni==nn.length) {
      ni = 0;
      ti++;
   }
   if (ti<trees[nums.length-1].length && isRunning)
     window.setTimeout("nextExpr()",1);
   else {
      document.FORM.FOO.value += buffer;
      document.FORM.MIN.value = min;
      document.FORM.MAX.value = max;
      document.FORM.COUNT.value = count+"/"+totalCount;
      stop();
   }
}

function evaluate(expr) {
   var stack = new Stack();
   for (var i=0; i<expr.length; i++) {
      var op = expr[i];
      if (typeof(op)=="number")
	stack.push(op);
      else {
	 var y = stack.pop();
	 var x = stack.pop();
	 switch (op) {
	  case '+':
	    x = x+y;
	    break;
	  case '-':
	    x = x-y;
	    break;
	  case '*':
	 x = x*y;
	    break;
	  case '/':
	    if (y==0) return Number.NaN;
	    x = x/y;
	    break;
	  case '%':
	    x = x%y;
	    break;
	  case 'max':
	 x = Math.max(x,y);
	    break;
	  case 'min':
	 x = Math.min(x,y);
	    break;
	  default:
	    alert("Ilegal operator "+op+"!");
	    raiseError(1, "Ilegal operator "+op+"!");
	 }
	 stack.push(x);
      }
   }
   return stack.pop();
}