/** 
This file contains JavaScript functions to convert ASCII math notation
to presentation MathML. The conversion is done while the XHTML page 
loads, and should work with IE 5.5+MathPlayer and Mozilla/Netscape 7+.

Version of Dec 22 2003, (c) Peter Jipsen http://www.chapman.edu/~jipsen
Freely available for non-commercial use. 
Contact jipsen@chapman.edu for the latest version.
*/

symbols = [
//some greek symbols
 {input:"alpha",  tag:"mi", output:"α"},
 {input:"beta",   tag:"mi", output:"α"},
 {input:"chi",    tag:"mi", output:"α"},
 {input:"delta",  tag:"mi", output:"α"},
 {input:"Delta",  tag:"mi", output:"α"},
 {input:"epsilon", tag:"mi", output:"α"},
 {input:"varepsilon", tag:"mi", output:"α"},
 {input:"eta",    tag:"mi", output:"α"},
 {input:"gamma",  tag:"mi", output:"α"},
 {input:"Gamma",  tag:"mi", output:"α"},
 {input:"iota",   tag:"mi", output:"α"},
 {input:"kappa",  tag:"mi", output:"α"},
 {input:"lambda", tag:"mi", output:"α"},
 {input:"Lambda", tag:"mi", output:"α"},
 {input:"mu",     tag:"mi", output:"α"},
 {input:"nu",     tag:"mi", output:"α"},
 {input:"omega",  tag:"mi", output:"α"},
 {input:"Omega",  tag:"mi", output:"α"},
 {input:"phi",    tag:"mi", output:"α"},
 {input:"varphi", tag:"mi", output:"α"},
 {input:"Phi",    tag:"mi", output:"α"},
 {input:"pi",     tag:"mi", output:"α"},
 {input:"Pi",     tag:"mi", output:"α"},
 {input:"psi",    tag:"mi", output:"α"},
 {input:"rho",    tag:"mi", output:"α"},
 {input:"sigma",  tag:"mi", output:"α"},
 {input:"Sigma",  tag:"mi", output:"α"},
 {input:"tau",    tag:"mi", output:"α"},
 {input:"theta",  tag:"mi", output:"α"},
 {input:"Theta",  tag:"mi", output:"α"},
 {input:"upsilon", tag:"mi", output:"α"},
 {input:"Upsilon", tag:"mi", output:"α"},
 {input:"xi",     tag:"mi", output:"α"},
 {input:"Xi",     tag:"mi", output:"α"},
 {input:"zeta",   tag:"mi", output:"α"},

//binary operation symbols
 {input:"+",       tag:"mo", output:"+"},
 {input:"-",       tag:"mo", output:"-"},
 {input:"*",       tag:"mo", output:"*"},
 {input:"circ",  tag:"mo", output:"o"},
 {input:"\\",      tag:"mo", output:"\\"},
 {input:"//",       tag:"mo", output:"/"},
 {input:"divide", tag:"mo", output:"÷"},
 {input:"oplus", tag:"mo", output:"⊕"},
 {input:"otimes", tag:"mo", output:"⊗"},
 {input:"wedge", tag:"mo", output:"∧"},
 {input:"vee",   tag:"mo", output:"∨"},
 {input:"cup",   tag:"mo", output:"∪"},
 {input:"cap",   tag:"mo", output:"∩"},
 {input:"times", tag:"mo", output:"×"},

//binary relation symbols
 {input:"=",       tag:"mo", output:"="},
 {input:"ne",    tag:"mo", output:"≠"},
 {input:"neq",   tag:"mo", output:"≠"},
 {input:"le",    tag:"mo", output:"≤"},
 {input:"ge",    tag:"mo", output:"≥"},
 {input:"<",       tag:"mo", output:"&lt;"},
 {input:">",       tag:"mo", output:"&gt;"},
 {input:"&lt;",    tag:"mo", output:"&lt;"},
 {input:"&gt;",    tag:"mo", output:"&gt;"},
 {input:"prec",  tag:"mo", output:"prec"},
 {input:"succ",  tag:"mo", output:"succ"},
 {input:"in",    tag:"mo", output:"&isin;"},
 {input:"notin", tag:"mo", output:"&notin;"},
 {input:"supset", tag:"mo", output:"&sup;"},
 {input:"supseteq", tag:"mo", output:"&supe;"},
 {input:"subset", tag:"mo", output:"&sub;"},
 {input:"subseteq", tag:"mo", output:"&sube;"},
 {input:"equiv", tag:"mo", output:"&equiv;"},
 {input:"cong", tag:"mo", output:"&cong;"},
 {input:"approx", tag:"mo", output:"&asymp;"},

//logical symbols
 {input:"forall", tag:"mo", output:"&forall;"},
 {input:"exists", tag:"mo", output:"&exist;"},
 {input:"neg",    tag:"mo", output:"&not;"},

//miscellaneous symbols
 {input:"perp",   tag:"mo", output:"&perp;"},
 {input:"partial", tag:"mo", output:"&part;"},
 {input:"pm",     tag:"mo", output:"&plusmn;"},
 {input:"sum",    tag:"mo", output:"&sum;"},
 {input:"prod",   tag:"mo", output:"&prod;"},
 {input:"int",    tag:"mo", output:"&int;"},
 {input:"emptyset", tag:"mo", output:"&empty;"},
 {input:"infty",  tag:"mo", output:"&infin;"},
 {input:"aleph",  tag:"mo", output:"&alefsym;"},
 {input:"ldots",  tag:"mo", output:"..."},
 {input:"dollar", tag:"mo", output:"$"},
 {input:" ",      tag:"mo", output:"&nbsp;"},
 {input:"quad",   tag:"mo", output:"&nbsp;&nbsp;"},
 {input:"qquad",  tag:"mo", output:"&nbsp;&nbsp;&nbsp;&nbsp;"},
 {input:",",        tag:"mo", output:", "},
 {input:":",        tag:"mo", output:" : "},
 {input:"cdots",  tag:"mo", output:"&sdot;&sdot;&sdot;"},
 {input:"cdot",   tag:"mo", output:"&sdot;"},
 {input:"diamond", tag:"mo", output:"&loz;"},
 {input:"square", tag:"mo", output:"[]"},
 {input:"qed",    tag:"mo", output:"&diams;"},
 {input:"lim",    tag:"mo", output:"lim"},
 {input:"sin",    tag:"mo", output:"sin"},
 {input:"cos",    tag:"mo", output:"cos"},
 {input:"tan",    tag:"mo",  output:"tan"},
 {input:"cot",    tag:"mo", output:"cot"},
 {input:"sec",    tag:"mo", output:"sec"},
 {input:"csc",    tag:"mo", output:"csc"},
 {input:"log",    tag:"mo", output:"log"},
 {input:"ln",     tag:"mo",  output:"ln"},
 {input:"det",    tag:"mo", output:"det"},
 {input:"dim",    tag:"mo", output:"dim"},

//arrows
 {input:"uparrow", tag:"mo", output:"&uarr;"},
 {input:"downarrow", tag:"mo", output:"&darr;"},
 {input:"rightarrow", tag:"mo", output:"&rarr;"},
 {input:"to",     tag:"mo", output:"&rarr;"},
 {input:"leftarrow", tag:"mo", output:"&larr;"},
 {input:"leftrightarrow", tag:"mo", output:"&harr;"},
 {input:"Rightarrow", tag:"mo", output:"&rArr;"},
 {input:"Leftrightarrow", tag:"mo", output:"&hArr;"},

//bracket operations
 {input:"lfloor", tag:"mo", output:"|_"},
 {input:"rfloor", tag:"mo", output:"_|"},
 {input:"lceiling", tag:"mo", output:"|~"},
 {input:"rceiling", tag:"mo", output:"~|"},
 {input:"langle", tag:"mo", output:"&lt;"},
 {input:"rangle", tag:"mo", output:"&gt;"},

//commands with argument
sqrt = {input:"sqrt", tag:"msqrt", output:"mfrac"},
frac = {input:"/",    tag:"mfrac", output:"/", binary:true},
 {input:"_",          tag:"msub",  output:"_", binary:true},
 {input:"^",          tag:"msup",  output:"^", binary:true},
 {input:"mathbf",     tag:"mo",    output:"mathbf"},
 {input:"mbox",       tag:"mtext", output:"mbox"},
 {input:"text",       tag:"mtext", output:"text"},

//grouping braces
 {input:"(", tag:"mo", output:"(", leftBracket:true},
 {input:")", tag:"mo", output:")", rightBracket:true},
 {input:"[", tag:"mo", output:"[", leftBracket:true},
 {input:"]", tag:"mo", output:"]", rightBracket:true},
 {input:"{", tag:"mo", output:"{", leftBracket:true},
 {input:"}", tag:"mo", output:"}", rightBracket:true}

//abbreviations (add your own if you wish)
];

function add(arr, elt){    // the push method is not supported in IExplorer
  arr[arr.length] = elt;
}

function compareNames(s1,s2) {
  if (s1.input > s2.input) return 1
  else return -1;
}

names = []; //list of input symbols

function initSymbols() {
  symbols.sort(compareNames);
  for (var i=0; i<symbols.length; i++) names[i] = symbols[i].input;
}

initSymbols();

if (document.getElementById==null) 
  alert("This webpage requires a recent browser such as\
\nNetscape 7+ or Internet Explorer 6+MathPlayer")

function myCreateElementNS(s,t) {
  if (document.createElementNS==null)
    return document.createElement(s+t);
  else
    return document.createElementNS(s,t);
}

function tag(attrList,nodeList) {
  var t;
  if (typeof attrList == "string")
    t = myCreateElementNS("http://www.w3.org/1999/xhtml",attrList);
  else {
    t = myCreateElementNS("http://www.w3.org/1999/xhtml",attrList[0]);
    for (var i=1; i<attrList.length; i=i+2)
      t.setAttribute(attrList[i],attrList[i+1]);
  }
  if (typeof nodeList == "string")
;//    t.appendChild(document.createTextNode(nodeList));
  else if (nodeList!=undefined)
    for (var i=0; i<nodeList.length; i++) 
      if (typeof nodeList[i] == "string")
        t.appendChild(document.createTextNode(nodeList[i]));
      else t.appendChild(nodeList[i]);
if (document.createElementNS==null) 
  document.forms[0].elements[0].value = t.innerHTML;
  return t;
}

mathml = (document.createElementNS==null?
          "mml:":"http://www.w3.org/1998/Math/MathML");

function mtag(attrList,nodeList) {
alert("mtag attrList :"+attrList+":\n nodeList :"+nodeList+":");
  var t;
  if (typeof attrList == "string")
    t = myCreateElementNS(mathml,attrList);
  else {
    t = myCreateElementNS(mathml,attrList[0]);
    for (var i=1; i<attrList.length; i=i+2)
      t.setAttribute(attrList[i],attrList[i+1]);
  }
  if (typeof nodeList == "string")
    t.appendChild(document.createTextNode(nodeList));
  else if (nodeList!=undefined)
    for (var i=0; i<nodeList.length; i++) 
      if (typeof nodeList[i] == "string")
        t.appendChild(document.createTextNode(nodeList[i]));
      else t.appendChild(nodeList[i]);
if (document.createElementNS==null)
  document.forms[0].elements[0].value=t.innerHTML;
  return t;
}

function replaceChildNodes(node,nodeList){
  var n = node.childNodes.length;
  for (var i=0; i<n; i++)
    node.removeChild(node.firstChild);
  for (var i=0; i<nodeList.length; i++)
if (nodeList[i]!=null)
    node.appendChild(nodeList[i]);
}

function removeCharsAndBlanks(str,n) {
//remove n characters and any following blanks
  var st = str.slice(n);
  for (var i=0; i<st.length && st.charCodeAt(i)<=32; i=i+1);
  return st.slice(i);
}

function position(arr, str, n) { 
// return position >=n where str appears or would be inserted
// assumes arr is sorted
  if (n==0) {
    var h,m;
    n = -1;
    h = arr.length;
    while (n+1<h) {
      m = (n+h) >> 1;
      if (arr[m]<str) n = m; else h = m;
    }
    return h;
  } else
    for (var i=n; i<arr.length && arr[i]<str; i++);
  return i; // i=arr.length || arr[i]>=str
}

function getSymbol(str) {
//return maximal initial substring of str that appears in names
//return null if there is none
  var k = 0; //new pos
  var j = 0; //old pos
  var mk; //match pos
  var st;
  var tagst;
  var match = "";
  var more = true;
  for (var i=1; i<=str.length && more; i++) {
    st = str.slice(0,i); //initial substring of length i
    j = k;
    k = position(names, st, j);
    if (k<names.length && str.slice(0,names[k].length)==names[k]){
      match = names[k];
      mk = k;
      i = match.length;
    }
    more = k<names.length && str.slice(0,names[k].length)>=names[k];
  }
  if (match!="") return symbols[mk]; 
// if str[0] is a letter return maxsubstring of letters followed by numbers
  k = 1;
  st = str.slice(0,1);
  while (k<=str.length && ("A"<=st && st<="Z") || ("a"<=st && st<="z")) {
    st = str.slice(k,k+1);
    k++;
  }
  if (k>1) {
    st = str.slice(0,k-1);
    tagst = "mi";
  } else {
    k = 2;
    st = str.slice(0,1); //take 1 non-letter character
    tagst = "mo";
  }
  return {input:str.slice(0,k-1), tag:tagst, output:st};
}

/*
Parsing ASCII math expressions with the following grammar

c ::= greek letters | [A-z]+ | [0-9]+ | + | - | * | = | < | > | ... | // 
u ::= sqrt | lim_ | sum_ 
b ::= _ | ^ | /
l ::= ( | [ | {
r ::= ) | ] | }
S ::= c | lEr | uS
E ::= S+ | SbS

Each terminal symbol is translated into a corresponding mathml node.
E.g. \alpha -> mtag("mi","&#945;")
     \sin -> mtag("mo","sin")
     \sqrt{...} -> mtag("msqrt",[mtag(...)])
*/

function parseSexpr(str) { //parses str and returns [node,tailstr]
  var symbol;
  var node;
  var result;
  str = removeCharsAndBlanks(str,0);
  symbol = getSymbol(str);             //either a token or a bracket or empty
alert("getsS: \""+symbol.output+"\"");

  if (symbol == null || symbol.rightBracket || symbol.output=="") 
    return [null,str];
  str = removeCharsAndBlanks(str,symbol.input.length); 

  if (symbol.leftBracket) {                        //read (expr+)
    result = parseExpr(str);
alert("result: \""+result+"\"");
    node = mtag("mrow",
           [mtag(["mo","stretchy","false"],symbol.output)].concat(result[0]));
    return [node,result[1]];
  }
  else if (symbol == sqrt) {                       //read unary argument
    result = parseSexpr(str);
    node = mtag(symbol.tag,[result[0]]);
    return [node,result[1]];

  }
  else return [mtag(symbol.tag,symbol.output),str];
}

function removeBrackets(node) {
alert("removeBrackets");
  if (node.hasChildren) {
    var st = node.firstChild.nodeValue;
    if (st=="(" || st=="[" || st=="{") node.removeChild(node.firstChild);
  }
  if (node.hasChildren) {
    var st = node.lastChild.nodeValue;
    if (st==")" || st=="]" || st=="}") node.removeChild(node.lastChild);
  }
}

function parseExpr(str) {
  var symbol;
  var node;
  var result;
  var nodeList = [];
  do {
    result = parseSexpr(str);
    node = result[0];
    str = result[1];
    symbol = getSymbol(str);
alert("getsE:\""+symbol.output+"\"");
    if (symbol.binary) {
      str = removeCharsAndBlanks(str,symbol.input.length);
      result = parseSexpr(str);
      removeBrackets(result[0]);
      str = result[1];
      if (symbol == frac) removeBrackets(node);
      add(nodeList,mtag(symbol.tag,[node,result[0]]));
    } 
    else add(nodeList,node);
  } while (!symbol.rightBracket && !(symbol==null) && symbol.output!="")
  if (symbol.rightBracket) {
    str = removeCharsAndBlanks(str,symbol.input.length);
    add(nodeList,mtag(["mo","stretchy","false"],symbol.output));
  }
  return [nodeList,str];
}

function parseMath(str) {
  var result = parseExpr(str);
  return mtag("math",[mtag(["mstyle","mathcolor","Red"],result[0])]);
}

mathdelimit="\`";

function strarr2nodeList(arr) {
  var nl = [];
  var expr = false;
alert(arr);
  for (var i=0; i<arr.length; i++) {
    if (expr) add(nl,parseMath(arr[i]));
    else add(nl,tag("span",arr[i]));
    expr = !expr;
  }
  return nl;
}

function processNode(n) {
  if (n.childNodes.length == 0) {
    var str = n.nodeValue;
    if (!(str == null)) {
      var arr = str.split(mathdelimit);
      if (arr.length > 1) replaceChildNodes(n,strarr2nodeList(arr));
    }
  }
  else
    for (var i=0; i<n.childNodes.length; i++)
      processNode(n.childNodes[i]);
}

function translate() {
  body = document.getElementsByTagName("body")[0];
  processNode(body);
}